The pattern matcher that has enabled most of the refactoring of the Lua code is now exposed in Scheme as well, so I can start writing compiler passes in Scheme.
Conversation
Plan is to refactor the SMC Scheme to C state machine compiler to a Scheme dialect, so I can host it in Racket as well as Lure. This would decouple the frivolous distraction (Lure) from the thing I originally set out to do (SMC).
1
Almost done with 'parameterize'. That + pattern matching + basic (non-tail recursive) Scheme should be enough to implement the rest of the compilers / interpreters.
1
One thing I'm not happy with is the lack of space-safe tail recursion. There is a trampoline to implement letrec-like forms but semantics is not 100% correct. Seems that compiling these to loops requires a bit more analysis than I can currently do, so not implementing it.
1
Does create some incentive to not write explicit recursion and use combinators. Fold and friends are implemented as loops.
1
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.
Replying to
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
Still wrong.. moving code around is tricky. Where to hide the bodies.
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