Design Jsend Prototype

[EduardoRFS]

This should track the design for the backend used during the prototype. The main goal is to have the language fully supported in a JavaScript environment.

Goals

• Pipeline
• Functions
• Fixpoint
• Big stack
• TCO
• Runtime
• Primitives
• Externals
• Modules

[EduardoRFS]

Pipeline

Currently the jsend pipeline will include 2 trees, untyped tree(utree), an untyped version of the teika tree, in the future it should be close to 1:1 with the code written after having annotations removed and the javascript tree(jtree) a simplified version of JS used as the compilation target.

Normalization

While ideally the untyped tree is 1:1 with the typed tree, currently it is likely easier to just emit the code after being reduced to the normal form, this may lead to a LOT of additional code being generated but it should be solved in the future.

Flow

Ttree -[Untype]> Utree -[Emit]> Jtree -[Print]> String

Post-prototype

The current pipeline is simple and is probably not ideal for long as it is not really susceptible to that many optimizations, additionally it would be nice preserve types until the JS generation, this is possible even with CPS due to self types.

[EduardoRFS]

Functions, fixpoint, big stack and TCO

Both functions and fixpoints will be compiled to functions, fixpoints are currently erased during untyping as they can be easily replaced by functions on an untyped calculus, this may not be ideal in the future.

Functions will be compiled to generators by default to prevent stack overflows as that is a crucial part of the Teika design.

Big stack & TCO

Any Teika compliant backend should by default treat the stack as an implementation detail, supporting big stacks is a must and while complete tail call elimination while potentially not a must, at least local tail call recursion should be optimized.

In JS this means emitting generators or CPSifying everything, the latter is likely faster and more powerful in the long term, but the former will be chosen as it is an easier compilation target and can be optimized.

Optimizations

Generators are inevitably slow in JS as such the most important optimization in Teika is to reduce their cost and avoid them as much as possible, this can be achieved by having "unboxed" returns in JS which can be handled by instanceof on the runtime.

Post-prototype

Reducing generators as much as possible by doing whatever analysis can be done, will probably be the main source of optimization post-prototype for a while.

[EduardoRFS]

Runtime

The Teika runtime for the prototype has the goal of allowing "readable" code generation while preserving all the stack properties above, additionally due to Teika prototype relying on currying and generators, this means that a lot of magic must be provided.

$run and $jmp

The entrypoint to Teika code is $run which will take any generator instance and support yield of nested generators, this function essentially needs to track the stack manually. At the end after executing the code it just returns the unwrapped value, this is essentially a monadic engine.

To support TCO any function in Teika can return a generator with $jmp, so on every return $run will do an instanceof $jmp to check if it should reuse the current stack frame. The details of how $jmp and $run interacts will likely change many times but at least for the prototype this is how it will probably be done.

$curry

Due to currying + generators the generated code becomes quite noisy on function calls, so a simple optimization is to do magic currying directly in JS, transforming yield (yield f(1))(2) in yield f(1)(2) to achieve this all Teika functions must be wrapped at definition with $curry.

Additionally because of $curry another simple code improvement is to fuse nested functions function* (x) { return function* (y) { return x; } } into function* (x, y) {return x } and by wrapping it in $curry it can be called in both ways.

Post-prototype

Assuming that Teika preserves the "big interpreter" approach of mapping directly to JS, the runtime can be improved in many ways, like supporting non-generator functions and supporting direct call without $curry.

Alternatively Teika could move to a "small interpreter" approach, by compiling to a stack machine and then interpreting the stack machine instead of running it directly, this could be especially interesting if WASM becomes a major target as then the same code could be used both on the JS side and WASM side.