Does create some incentive to not write explicit recursion and use combinators. Fold and friends are implemented as loops.
Conversation
Added interpreter for the IR that can do proper tail calls and uses continuations internally. This is something I did before long ago, directly for core Scheme. Now in ANF it's a lot simpler as there is just one kind of continuation (chained remainders of blocks = typical stack).
1
This multi-pass approach is really useful. Hard to see exactly how it all fits together without actually trying to factor it. It is a puzzle but the end point feels natural somehow.
1
Also found this, for when I grow up: docs.racket-lang.org/nanopass/index
1
Wrote a new state machine compiler on top of the block IR as a pass that extends the IR with labels and goto. This one is much more general than the first attempt.
1
Main idea: Inline every closure application, keeping track of instantiated closures indexed by the current continuation. If the same function is encountered more than once for the same continuation, it's a loop, and application can be replaced with a goto to a previous instance.
1
This works for nested loops, without the need for special loop forms (it's all lambdas). All loop forms can then be Scheme macros.
1
Took a good while to figure out _where_ to put the function bodies to not mess up lexical scope for downward closures until I realized that they can just be inlined if there is a proper stop criterion for the tail recursion.
1
Non-tail recursion will still blow up this way, but this is explicitly not part of the problem.
1
On to testing...
1
There's a path now that feeds the SM compiler output IR back to Scheme for interpretation, so I can at least test execution and scope errors.
1
I think I solved the scope errors. Time for some more testing: start with Scheme program that contains trace calls. Interpret one directly, compile the other to state machine form then back to Scheme, and compare traces.
1
Found a lot more corner cases with testing. Also some very surprising things that unexpectedly work wrt. moving lambdas around, which makes me think I should really go all in on "partial evaluation as a UI".
1
This is dynamically typed, but staged. A type error is something that doesn't doesn't survive compile time evaluation and or doesn't specialize to state machine form. I'm thinking that might be good enough as guard rail.
1
Or.. add an actual type system. Playing with this is reshaping the way I think about managing my future "C life". I cannot escape C nor do I want to, but I can write a whole lot more in a Schemish language + ad hoc compile time checks than I originally thought was possible.
1
Doodled a bit to combine new SM compiler with the new interpreter for partial evaluation, but seem to have lost my stride after 2 weeks of putting out fires at work...
1
Two more weeks of exhaustion.. But picked it up again. Lure Scheme: added preliminary Erlang, JavaScript and GDB script backends, and started working on dataflow analysis (liveness) for the state machine compiler to implement state variable allocation across suspend points.
1
Still existential questions about what this thing is supposed to be. For now it's self-propelling. Something something Scheme, microcontrollers and test systems.
1
In related news, I contributed a Lua backend to Ribbit VM. I'd like to integrate that somehow. There is some overlap, though my main aim is compilation.
1
Anyways I think I know what I want: rebuild the ideas of Staapl (interactive tethered development), but build it on top of standard tools (GDB & C) using a lowest common denominator language (Scheme or Scheme subset) as a focal point.
1
Actually surprised I got compilation from Scheme to GDB script working with so little effort. It can now do functions, if/then/else and while loops (from named let or single-def letrec, with support for nesting).
1
1
Managed to encode anonymous functions - see gist. Unfortunately due to global variables only, there is no re-entrancy. E.g. nested 'map' won't work. Can't think of a simple solution, so will probably resort to inlining.
1
Possible solutions: use nested data structures on target, but this requires target memory. GDB can host arrays so could implement memory which could host a low level VM + GC, but that seems a bit far-fetched.
1
This needed a break apparently... I know where to go next: build something with RTIC first, then see how to mesh the state machine compiler with something that maps to RTIC or some stripped down C version of the RTIC idea (use Cortex M NVIC as a scheduler).
2