Figured out the implementation, without scheduler for now. Just supports 2 coroutines connected through a single channel, where blocking read/write is always coroutine jump.
Conversation
Next step is analysis of task/channel network at compile time, then see what is necessary to implement the scheduler as a coroutine.
1
Compiler structure is surprisingly free of bad hacks. It all just meshes together, which makes me believe I'm on the right track. I.e. I'm not adding any "clever" extensions that complicate things.
1
Only one hack wrt partial evaluation. I don't think I can get around this because of the implicit embedding. The compiler at some point expects a collection of mutually recursive definitions, but it's not clear how to stop PE without annotation or more involved analysis.
1
So now it just stops (spawn! <closure>) PE when it finds a (begin (define ...) ...) form. At that point the lexical environment contains all parameters necessary to specialize the code per task.
1
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.
1
( 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.
Replying to
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*.
1
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
Show replies