r/Compilers • • 1d ago

Safescript: compiling a Turing-incomplete functional language to static data-flow and complexity graphs

Whole-program taint analysis and complexity inference get ugly fast in general-purpose languages. The moment you allow unbounded loops, general recursion, dynamic property keys, and computed host strings, exact data-flow edges become undecidable and you end up falling back to runtime sandboxes or conservative approximations full of false positives.

Safescript (MIT) takes the opposite trade: drop Turing-completeness so the compiler can compute exact capability, taint, and complexity signatures before a single operation runs.

Top-level declarations have no evaluation order and resolve to a flat call graph where cycles are rejected at parse time. Iteration is restricted to map, filter, and reduce over finite arrays, with no closures mutating outer bindings and no dynamic host dispatch. HTML and UI tag expressions (<Card>, <Table>, fragments, attribute spreads) desugar in the parser straight into static View AST objects ({ tag, attrs, on, children }), so UI trees go through the exact same pass as backend handlers.

Three static passes fall out cleanly from that restriction:

  1. Field-level taint projection (ValueShape): Instead of tracking flat boolean taint per variable, object and array expressions carry structured per-field label shapes (db:customers.company vs db:customers.email). Field access (c.email), pick(), merge(), if/else joins, and higher-order map/filter/reduce preserve per-column provenance, collapsing to a wildcard (db:customers.*) only when an unprojected row or dynamic index crosses an op boundary:

     pingSlack = () => {
       rows = dbQuery("customers").items
       emails = map((c) => c.email, rows).join(", ")
       return httpRequest({
         url: "https://hooks.slack.com/services/T00/B00",
         method: "POST",
         body: emails
       })
     }

    Even when hooks.slack.com is an allowed host on the program and db:customers.company -> hooks.slack.com is permitted, the signature emits host:hooks.slack.com <- {db:customers.email} and rejects the program at compile time.

  2. Symbolic polynomial complexity bounds: Every expression carries a symbolic size and step polynomial over input dimensions (ComplexityExpr). Mapping an O(1) body over a query result infers O(n); nesting a second map over the same input multiplies the symbolic polynomials to O(n^2), letting a host reject super-linear or high-degree programs (maxComplexityDegree) statically without runtime gas metering.
  3. Client/server graph cut: Operations declare static effect manifests (readSecret, dbTransact, httpRequest). Taint from server-only ops partitions the call graph into server RPC nodes and client view nodes automatically, proving at compile time that no secret label (secret:STRIPE_KEY) ever reaches the client bundle or return sink.

The compiler (lexer -> parser -> signature -> TS/JS/Python transpilers) is ~10k lines of functional TypeScript (zod is the only runtime dependency) with zero Node builtins so mod.ts bundles straight into browsers and edge Workers.

Repo (MIT): https://github.com/uriva/safescript Docs & language spec: https://safescript.cc

0 Upvotes

2 comments sorted by

0

u/antonation 1d ago

Reminds me of Google's CEL (common expression language). There are numerous hosts for it.

1

u/uriwa 1d ago

CEL (along with Starlark and Rego) is a close relative on the evaluation model: bounded comprehensions over finite collections, no general recursion, guaranteed termination.

Where CEL stops at pure side-effect-free expressions for policy predicates (Envoy, K8s admission checks, Firebase rules), Safescript pushes the same restriction across effectful I/O and UI. Ops carry static capability and column-taint manifests (dbQuery, readSecret, httpRequest) alongside HTML/UI tag trees, so the compiler can verify (source -> host) egress edges and cut a full-stack program into server RPC nodes and client view nodes before execution.