I'm stoked because I finally found how to represent the PE tricks in Staapl (Forth-style language) in something that is not too weird. This might actually be useful in a broader sense.
Conversation
( In Staapl it's something that I discovered accidentally: peephole optimization works by treating the compiled instruction stream as a data stack for macros. A hack. Not something I could translate to a language with bindings and expressions. )
1
But in this Scheme implementation, the partial evaluation is defined in a direct way.
An eye opener for me. It seems it was necessary to just try to implement it to see the structure of the problem.
1
Removing use of statement expressions :-)
I had to implement a different approach for the C switch statement anyway so this is not a big change. Infra is already there.
1
Generated C code is running. 2 coroutine example.
I've ended up specializing all code for each task, which then gets rid of a task pointer. Coroutine call is now just save return adress + save optional argument + goto. All context is accessible from one "global" pointer.
1
Next up is a scheduler that can be inlined. Will be a bit more work... Prob build the static task network in first pass, then specialize at each blocking point.
1
Nope next up was realizing that coroutines without synchronization primitives (other than yield/call other coroutine) cannot really be called concurrent. Making this explicit removes some magic.
1
1
It only becomes concurrent once the tasks are decoupled, i.e. not explicitly resuming each other, but isolated by scheduler. task->sched->task are still coroutine calls. Obvious now, but took a while to figure out that's what the code was trying to tell me.
1
Cleaned up some more. I think this is pretty much it for the coroutine part. Building the compiler as a modified interpreter was the trick. Should have listened. When there's an interpreter available you can just modify it slightly and run it. Basically gives PE mostly for free.
1
Cleaned up the scheme->lua compiler to use the factored out macros. The base language is now just: lambda,if,set!,let* with begin + local defs -> letrec -> set! + let*.
Replying to
I think this will be useful to release as a rocks library.
Help me find a pun that includes Lua, in the style of conniver,scheme,gambit,racket etc...
1
Maybe "lure" would be a good one.
1
Name is reserved: luarocks.org/modules/zwizwa
Not packaged correctly yet, but there's a stripped down github repository to support the Lua rock.
1
Got distracted with the Scheme->Lua compiler. Been debugging it to try to get it to the point where it can run the Ribbit VM.
1
Starting to understand why people are tempted to bootstrap compilers. Doing this in Lua works up to a point, but I'm starting to really miss pattern matching, and the only way out I see is to use the Scheme-in-Lua to bootstrap a Scheme to write a pattern matcher.
1
This is getting out of hand...
Also I don't think I'm ever going to write a direct output compiler again. ( Best way to learn is to make told-you-so mistakes. )
You really want to be able to clean up the output in an additional pass, even if it is just for debugging
1
1
Once you leave AST/Sexpr domain it's game over.
1
But what I did find out (probably re-invent) is that it makes sense to generate the output as a token stream even if it generating a nested expression, at least for compilers written in semi-imperative style.
1
Probably artifact of trying to do this in one pass. Seems to be mostly about the pretty-printer. Splitting up in more passes, the intermediate passes do want to be pure.
1
Made a draft of a simple recursive matcher. Thing is, with s-expressions available and Lua's interned strings for memoization, there's a lot of room for building small s-expression based DSLs inside lua.
1
{"(add ,a ,b)", function(m) return m.a + m.b end}
1
Added quotation support to the reader.
1
But I also discovered that the pattern can be represented as a function (HOAS), and that you can basically turn any parameterized data constructor into a matcher.
This blew my mind.
1
1
I think I need to read more...
1
This has to be common knowledge. Just where do I start reading to find these things out?
1
Anyways I am stoked because it looks like being stuck with Lua is not going to be such a problem. Especially taking into account that we're using LuaJIT, and that implementing "string DSLs" is probably still going to be pretty fast.
1
In this light, interned strings, tables (finite functions), and table object identity as primitives are not so bad.
1
Split it up further into frontend (macro exp, beta red, let insertion, var rename), simplification pass (block flattening), and ir + lua pretty printer. Not complete but looking a lot better.
1
So... this is turning into a thing. Wrote a bit more at the luarocks page luarocks.org/modules/zwizwa
1
Getting quite obsessed. My wife is worried. Haven't been this obsessed in ages. Focused on the Scheme->Lua compiler V2 for a bit, the multipass one. I got it wrapped to a point where it's possible to write a Lua module in Scheme:
1
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.
1
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
Show replies