Tackled something I wanted to do for a long time: compile blocking code to a C state machine without introducing new dependencies. I probably just want Rust async, but that's not happening at this point.
Conversation
What I ended up with is all kinds of wrong and was tremendously fun to write. This fits in a project that is bare metal C, but already has a test system written in Lua, so I used Lua as the implementation language.
Replying to
First considered to re-use Lua syntax but couldn't figure that out, so switched to Scheme. The compiler implements a Scheme subset (let*, if, for, and first order functions). A module maps to a C function, tail calls map to goto, and non-tail calls are inlined.
1
1
The main "work" it does is to figure out whether intermediate variables can be compiled to C variables, or need to go into a struct to survive a yield (which is C return).
1
1
The compiler uses A-Normal Form (ANF). Is under 1K lines of Lua.
github.com/zwizwa/uc_tool
1
Still just a toy. Bugs likely. Current "test" is
github.com/zwizwa/uc_tool
1
Anything that crosses an SM_READ macro (the blocking call) is stored in a C struct. The rest goes on the C stack. This is ANF with constants bound to variables as well, to make implementation simpler. C compiler can take care of optimizing those away.
1
The yield/block points are (later) implemented on top of this protothread code. See e.g. SM_WAIT
1
Started adding support for CSP rendezvous (csp.h in uc_tools, written in hard-to-use C macros).
Added support for zero-copy mode. Eventually this needs to be fast (for the app: 137k int/sec on 72MHz CM3). Might need to specialize the scheduler further.
1
BTW doing this in Lua isn't all that bad. Of course refactoring is hard, but doable at this 1kloc complexity level.
However manual let-insertion is annoying. Older Haskell code used a state-continuation monad for that, which is really convenient. Almost magic.
2
End of winter break. Experiment succeeded. Anything more complex needs better abstraction. Feeling a Racket itch coming up...
1
C output doesn't look too bad. Compiles to invocation of csp.h macros for event setup (CSP_EVT_BUF), blocking select call (CSP_SEL) and case statement for dispatch.
1
From select form in
github.com/zwizwa/uc_tool
2
Moving on to Racket since I'm already in Scheme land and this isn't so type-heavy. Wish I didn't have to choose between Racket and Haskell... I'd like to somehow bridge the effort, since both approaches are useful in that they provide different perspectives.
1
Wondering why I made the choice of Racket over Haskell. Can think of two things: at this point, Racket brings more joy. I really miss Scheme macros.
But maybe more so: I am reluctant to introduce Haskell into a team with essentially all embedded systems people.
1
1
The distance between Lua and Javascript (which are already used) and Scheme is much less than the jump over to Haskell. While a great tool, it is also a big time investment to learn a completely different perspective.
1
(should have stuck to a single thread...)
Got distracted by writing a Scheme interpreter, which then made me realize that I need one anyway for partial evaluation so that got integrated into the state machine compiler.
1
Cleaned up the Lua compiler code a bit and then it became easy to write a simple Scheme to Lua compiler using it. (Just lambda, application, if, and top level module). This mixes well with LuaJIT.
1
Then I realized this could also be slightly modified to create a higher order syntax representation HOAS in Lua (representing syntax as functions). Not sure yet if this is just another distraction or a better way to represent the compilers/evaluators.
1
Oleg says so. Who am I to question. Anyways I don't know yet what is better for my case: go the macro route & focus on easy syntax extension, or go the HOAS route, build a fixed DSL and focus on adding partial evaluation annotation.
1
And yes I'm heading towards re-implementing a dumbed down untyped version of MetaOCaml in a 1kloc Scheme compiler written in Lua. Don't do as I do this is just for play.
1
1
Read the MetaOCaml stuff here:
okmij.org/ftp/ML/MetaOCa
1
I think I figured out a sane semantics: Scheme file contains start function, which spawns tasks (closures). Conceptually those closures run in a new task context, but they can be specialized to C state machine code.
1
The neat part here is that any scheme code can be used to construct a network of connected tasks, and that network structure is what is compiled to C.
1
This resembles some form of hibernation, where the start codes runs on workstation, code hibernates before state machine receives events. The image then resumes on target machine and starts processing events.
1
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.
1
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
Show replies