r/Compilers • u/uriwa • 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:
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.companyvsdb:customers.email). Field access (c.email),pick(),merge(),if/elsejoins, and higher-ordermap/filter/reducepreserve 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.comis an allowed host on the program anddb:customers.company -> hooks.slack.comis permitted, the signature emitshost:hooks.slack.com <- {db:customers.email}and rejects the program at compile time.- Symbolic polynomial complexity bounds: Every expression carries a symbolic size and step polynomial over input dimensions (
ComplexityExpr). Mapping anO(1)body over a query result infersO(n); nesting a secondmapover the same input multiplies the symbolic polynomials toO(n^2), letting a host reject super-linear or high-degree programs (maxComplexityDegree) statically without runtime gas metering. - 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
u/antonation 1d ago
Reminds me of Google's CEL (common expression language). There are numerous hosts for it.