Compiler/Interpreter Work Writeup

General Research
1

General line of investigation: find ways to compile Scheme or Elixir to RISC Zero programs with reasonable performance

Investigation 1 (inactive)

Compile Chicken Scheme to C for execution in RISC Zero

  • Steps:
    • Modify the Chicken Scheme compiler source code and compile it with RISC Zero toolchain to obtain static libraries for riscv32m architecture
    • Write functions in Scheme and use Chicken Scheme compiler to compile them into C
    • Create RISC Zero project that links in the above static library and has a Rust entry point that calls the C code (produced by calling Chicken Scheme compiler)
  • Outcomes:
    • The approach works and resource logics could theoretically be written in Chicken Scheme
  • Challenges:
    • Performance: 5! written in Scheme takes 80 minutes to prove on RISC Zero, cause is likely the size of the Chicken Scheme runtime (which supports garbage collection, continuations, ā€¦)
    • The Chicken Scheme runtime has to be slightly patched because the RISC Zero toolchain does not support things like TCP or file access - users donā€™t have to deal with this though
    • The Chicken Scheme API for C code to be able to call Chicken Scheme functions has to be learned - users donā€™t have to deal with this though
    • The Chicken Scheme runtime calls some undefined functions like sbrk - these have to be identified and defined inside the RISC Zero project
  • Possible future steps (none were taken because a different approach was chosen at the end of ideation):
    • Try to optimize the process so that 5! takes less time
    • Try to simplify each step in the compilation process - maybe certain commands donā€™t need certain flags?
    • Produce highly detailed instructions on how to reproduce this Chicken Scheme compilation process
  • Links:

Investigation 2 (inactive)

Make an interpreter for a Scheme-like DSL in Rust, and run the interpreter in RISC Zero

  • Steps:
    • Define a small Scheme-like DSL (i.e. has macros, limited continuations, first class functions) that would compile nicely to C
    • Write an interpreter in Rust for this DSL and run this interpreter inside RISC Zero
  • Outcomes:
    • Programs written in the Scheme-like DSL work and are much faster than those from invegation 1 (computing 5! takes 3 minutes)
  • Challenges:
    • Performance: 5! written in Scheme takes 3 minutes to prove on RISC Zero compared to the same code written in C taking 5 seconds
  • Links:

Investigation 3 (inactive)

Make compiler in Rust to compile from Scheme-like DSL to C for execution on RISC Zero

  • Steps:
    • Define a small Scheme-like DSL (i.e. has macros, limited continuations, first class functions) that would compile nicely to C
    • Write a compiler in Rust from this DSL to C
    • Create RISC Zero project that has a Rust entry point that simply calls the above C code (produced by running the above compiler on DSL code)
  • Outcomes:
    • Programs written in the Scheme-like DSL work and are much faster than those from invegation 2 (computing 5! takes 5 seconds)
  • Challenges:
    • This approach only works if the DSL remains similar enough to C to allow a direct translation to C (without additional runtimes)
    • Unfamiliarity: the language is neither Scheme nor is it C, so people would have to learn the limitations/features that are unique to the language
  • Notes:
    • This was the chosen approach, hence investigation 1 ceased
  • Links:

Investigation 4 (the formally chosen approach, active):

Embed Scheme-like DSL inside Elixir and use compiler written in Elixir to compile to C

Investigation 5 (requested experimental approach, active)

Compile one of the Elixir compilerā€™s intermediate representations to something that runs on RISC Zero

  • Steps:
    • Figure out which of the Elixir compilerā€™s intermediate representations translate most nicely to C, C++, Rust, or RV32M assembly
    • For expediency, I chose to compile BEAM bytecode to C because this pair looked the most similar
    • Only the single-threaded subset of BEAM bytecode would be supported - no message passing, actors, spawning, ā€¦
    • Hand translated some BEAM bytecode to C to increase confidence that this approach could work
    • Currently writing a compiler to automate this translation, almost covered enough BEAM bytecode instructions to test some simple Elixir functions (like factorial)
  • Outcomes: none yet
  • Benefits:
    • No new language would need to be invented, since we are kind of giving Elixir an alternative backend
  • Challenges:
    • BEAM bytecode doesnā€™t seem to be well documented - but thereā€™s usually some resource on the internet or the BEAM source code itself to understand semantics
    • BEAM bytecode is slightly lower level than C and can explicitly create/destroy stack frames and refer to return addresses, this does not convert nicely to C - but this challenge can sometimes be sidestepped
    • Exactly specifying the exact subset of Elixir that would be supported by the subset of BEAM bytecode that we would support
  • Future steps:
    • Hopefully produce a demo in a few days so that stakeholders can determine whether this is a direction they would prefer
  • Links:
    • None yet, should have something in a few days
2 Likes
Rv32im + ecall as the lowest-level ISA/API
Rv32im + ecall as the lowest-level ISA/API
2

Thank you for the comprehensive write-up! I have a few questions:

What are these, exactly? Do you have a brief summary/writeup (or could you summarize here)?

What is ā€œS@Jamheme codeā€ (maybe a typo)? Do you have a few small examples of this?

Do we aim to benchmark ā€œ5!ā€ compiled via this method (which seems to be our reference)? I think thatā€™d be helpful to do ASAP as performance is a make-or-break criterion here.

I have one final question, perhaps also directed to @l4e21 and @mariari:

If the primary goals of language selection and compiler design here are the following (in no particular order of precedence):

  • Speed of application prototyping (how quick applications can be prototyped)
  • Speed of proof generation (should be comparable to C, a little bit slower is fine)
  • Ease of experimentation with application development abstractions and compatibility with future Anoma-level ideas

ā€“ then how would you compare the BEAM compilation approach (where applications would be written in Elixir) vs. an approach where we take this Scheme-like DSL and attempt to build AL abstractions on top of it (with no Elixir involved)? I understand that the performance comparison just requires that we finish the investigation 5 benchmarks, but Iā€™m curious as to what you think of these two approaches in terms of application prototyping speed and ease of abstraction experimentation / compatibility with future AL ideas.

3

The BEAM compilation approach simplifies the stack. The scheme approach means that we need to have a base of functions which are marked as compiling to our scheme. This can be done via a simple macro

@scheme
def foo(x, y) do
  x + y * 23
end

However, what this means is we canā€™t just pull random code here, and we have to consider what to port over. The upshot of this is that we can reuse a lot of standard Elixir libraries so even complex logic shouldnā€™t be changed.

However it does mean there are questions like how do we compile maps that preserve semanticsā€¦

Now, if we chose the BEAM compiled code it means we can just put arbitrary erlang code that doesnā€™t call send or spawns a thread. Which is a large subset of elixir/erlang since Erlang/Elixir lets you write things sequentially but deploy concurrently.

For AL, this gives us a lot more freedom in how we produce and integrate the code. Namely on the road to an AL compiler we can do things like take our scry functions and just see if they work, without having to mark all the macros and callls on the way. For the full AL compiler this likely has benefits as well. If we accept a post ordering resource machine, we can probably even do compilation online and play with different ideas of source code online. Whereas with the scheme version weā€™d be limited by our willingness to put put decorators and touch dependencies we donā€™t own.

Further for the end user it simplifies design and use, no longer would there be a potential for a scheme error or worrying about not having a scheme compatible function. So it should make testing and iterating easier for everyone involved if we can manage it.

1 Like
4

What are these, exactly? Do you have a brief summary/writeup (or could you summarize here)?

Hi. Limitations by language:

  • In L2C: functions are similar to Rust functions (fn) in the specific sense that they cannot access the local variables of parent functions. This is because they are denested and compiled into ordinary top-level C functions. The DSLā€™s nesting is still useful to allow inline definitions of functions at their point of use. Nesting is also useful to control the scope of function definitions.
  • In Elixir DSL: functions are more like Rust closures in the specific sense that they can access the local variables of their parent functions. This is because they are compiled using GCC nested functions. These functions are a little unsafe because they cannot outlive their parent functions, or in other words closures cannot escape. Escape attempts will result in segmentation faults. This limitation is due to GCCā€™s implementation of nested functions using trampolines on the stack.
  • In L2C: full continuations are not supported. Only escape continuations are supported - i.e you can only call a continuation to exit the current scope. (This functionality could probably be generalized to support jumping up and down the current call stack.) I chose this approach because full continuations seem to be more complex to compile seemingly requiring that the full state of the stack be saved for later use - and this probably would not be efficient.
  • In Elixir DSL: no continuations are supported. They could be supported to some extent through escape continuations, but were not included in @l4e21 ā€˜s Elixir DSL. Probable reasons for their exclusion: not required by users, and the fact that itā€™s probably an unusual variation to call/cc.
  • No garbage collection. Garbage collection for compiled DSL programs should be possible, but might cause noticeable slow down within the zkVM. I guess we still have to figure out what specifically caused the Chicken Scheme experiments to be so slow.

So briefly: no garbage collection, closureā€™s must not escape, and continuations are invalidated when their stack frames dies. Also, a few minor syntactical changes were made to simplify the interpreter and compiler work. So this language is not quite Scheme nor is it C.

What is ā€œS@Jamheme codeā€ (maybe a typo)? Do you have a few small examples of this?

Thanks, this is a typo - my mistake. I meant that @l4e21 had already defined a DSL and written an interpreter for it at the time when I started writing the compiler. So the compiler had to conform to this language as much as possible.

Examples of the DSL:

1 Like
A Roadmap for AL