@davedoesdev/mce v0.0.7

:prewrap!:

Description

This is a continuation-passing metacircular evaluator for the Scheme language, with support for serializing the state of execution. Implementations are provided in Scheme (of course), C++, JavaScript and WebAssembly.

It consists of the following components:

Macro expansion:: Derived forms are expanded to basic forms in link:scm/expand.scm[].

Conversion to continuation-passing style:: The program is converted to CPS form as decribed http://rawgit.davedoesdev.com/davedoesdev/mce/master/doc/dissertation.pdf#page=42[here]. See the scan function in link:scm/mce.scm[], which is roughly as described http://rawgit.davedoesdev.com/davedoesdev/mce/master/doc/dissertation.pdf#page=46[here].

Executing the CPS:: The CPS form is executed by repeatedly stepping through its state, as decribed http://rawgit.davedoesdev.com/davedoesdev/mce/master/doc/dissertation.pdf#page=56[here]. See the run function in link:scm/mce.scm[].

State-saving mechanism:: The state of the program can be serialized to a string at any point of its execution, as decribed http://rawgit.davedoesdev.com/davedoesdev/mce/master/doc/dissertation.pdf#page=48[here]. See the mce-save and mce-restore functions in link:scm/mce.scm[].

Stateless servers:: An experimental Web framework is provided which serializes the whole program state into a HTML document when user interaction is required. The state is restored when the browser POSTs back the user input form. The framework is modelled after the stateless server arrangement described http://rawgit.davedoesdev.com/davedoesdev/mce/master/doc/dissertation.pdf#page=103[here].

The macro expansion and CPS conversion components are implemented in Scheme. The CPS execution component has Scheme, C++, JavaScript and WebAssembly implementations.

Building

Scheme

You'll need to install the https://www-sop.inria.fr/indes/fp/Bigloo/[Bigloo] Scheme compiler to build them. Once you've done that:

make -C scm

You should end up with executables expand, scan and mce in the link:scm[] directory. expand does macro expansion, scan does CPS conversion and mce executes the CPS form.

C++

If you have a modern C++ compiler, then this should work:

make -C cpp

You should end up with executable mce in the link:cpp[] directory. This executes CPS forms produced by scm/scan.

JavaScript

Make sure you have https://nodejs.org/[Node.js] installed and then run:

pushd js
npm install
popd

The CPS execution component is in link:js/mce.mjs[].

WebAssembly

Install https://github.com/CraneStation/wasi-sdk[wasi-sdk] to /opt/wasi-sdk and then:

make -C cpp/wasm

You should end up with mce.wasm in the link:cpp/wasm[] directory. This is the CPS execution component. You'll need a WebAssembly runtime which supports https://github.com/CraneStation/wasmtime/blob/master/docs/WASI-overview.md[WASI] to run it, for example https://github.com/CraneStation/wasmtime[wasmtime] or https://nodejs.org/dist/latest-v13.x/docs/api/wasi.html[Node.js].

Running the examples

There are a number of examples in the link:examples[] directory.

To run, say link:examples/test-loop.scm[], using the Scheme execution engine:

./scm/expand < examples/test-loop.scm | ./scm/scan | ./scm/mce

To run the same example using the C++ engine:

./scm/expand < examples/test-loop.scm | ./scm/scan | ./cpp/mce

And using the JavaScript engine:

./scm/expand < examples/test-loop.scm | ./scm/scan | node js/main.mjs

And using the WebAssembly engine:

./scm/expand < examples/test-loop.scm | ./scm/scan | wasmtime cpp/wasm/mce.wasm

or

./scm/expand < examples/test-loop.scm | ./scm/scan | node --experimental-wasi-unstable-preview1 js/run_wasm.mjs

Of course, you can write the CPS form to a file so you only have to do it once, for example:

./scm/expand < examples/test-loop.scm | ./scm/scan > test-loop.cps
./scm/mce < test-loop.cps
./cpp/mce < test-loop.cps
node --experimental-wasi-unstable-preview1 js/main.mjs < test-loop.cps
wasmtime cpp/wasm/mce.wasm < test-loop.cps
node js/run_wasm.mjs < test-loop.cps

State-saving

The example link:examples/test-state2.scm[] demonstrates state-saving by serializing a continuation to standard output.

If you run it like this:

./scm/expand < examples/test-state2.scm | ./scm/scan | ./scm/mce

You should see the serialized continuation written to standard output.

You can pipe the output into ./scm/mce, ./cpp/mce, ./js/mce.mjs, wasmtime cpp/wasm/mce.wasm or js/run_wasm.mjs and it will resume where it left off:

$ ./scm/expand < examples/test-state2.scm | ./scm/scan | ./scm/mce | ./cpp/mce
0
1
2
3
4
5
save 21774
restore 21775
6
7
8
9
10

You can see the continuation was saved here in one process (21774) and restored in another (21775).

Of course, you can mix and match engines, for example passing state from a JavaScript engine to a Scheme one:

$ ./scm/expand < examples/test-state2.scm | ./scm/scan | node --experimental-modules js/main.mjs | ./scm/mce 
0
1
2
3
4
5
save 22137
restore 22136
6
7
8
9
10

or from a Scheme engine to a WebAssembly one:

$ ./scm/expand < examples/test-state2.scm | ./scm/scan | ./scm/mce | wasmtime cpp/wasm/mce.wasm 
0
1
2
3
4
5
save 1025
restore -1
6
7
8
9
10

Note the WebAssembly process ID is always -1 because https://github.com/CraneStation/wasi-libc[wasi-libc] doesn't implement getpid.

C++ (and WebAssembly) garbage collector

The C++ engine implements a simple stop-and-copy garbage collector:

• Shared pointers are used throughout to ensure data is released when not referenced by the program.
• Weak pointers to data that can form cycles (pairs, vectors and lambdas) are stored in a global table, indexed by the underlying pointer value.
• When a shared pointer to a pair, vector or lambda is released, the corresponding entry is deleted from the table.
• When the number of entries in the table exceeds a certain threshold:
  1. The current computation state is serialized to a string.
  2. All pairs, vectors and lambdas in the table have their contents nulled.
  3. The table is cleared.
  4. The current computation state is restored from the string.

You can change the threshold by using the --gc-threshold argument to ./cpp/mce or wasmtime cpp/wasm/mce.wasm --. The default value is 100000.

link:examples/test-mem.scm[] can be used to check the garbage collector is working. It runs in a loop creating cycles.

Stateless servers

A serverless deployment for https://zeit.co/now[Zeit Now] can be found in the link:stateless[] directory. This restores a program state received in a POST request and runs it, passing the user input in the form. The program can then process the input and generate a new HTML page (with the program's state serialized into it).

An example which displays a number and lets the user increase or decrease it can be found in link:examples/stateless/counter.scm[]:

source,scheme

.counter.scm

(let loop ((i 0)) (define (next form) (loop ((if (assoc "up" form) + -) i 1))) `(body form (@ action ,(get-config "url") method "post") ,i " " (input (@ type "hidden" name "state" value ,next)) (input (@ type "submit" name "up" value "Up"))

    (input (@ type "submit" name "down" value "Down"))))

First, make the cryptographic keys by running:

./certs/make_stateless_keys.sh

This produces certs/stateless_priv.pem and certs/stateless_pub.pem which are used to sign and verify program state so arbritary untrusted state isn't executed.

Next, generate the initial program state by running:

./examples/stateless/make.sh

This generates stateless/counter.html.

To test this out locally:

cd stateless
npm install # you only need to do this once
now dev

and then visit http://localhost:3000/counter.html

When you're ready to deploy to Zeit Now, run:

now

Note you'll need to use now secret add to tell Zeit Now about your keys for signing and verifying program state:

now secret add stateless-priv-pem -- "$(grep STATELESS_PRIV_PEM .env | sed 's/[^=]*=//')"
now secret add stateless-pub-pem -- "$(grep STATELESS_PUB_PEM .env | sed 's/[^=]*=//')"

You can then visit /counter.html on your deployed site.

Mine is available at https://stateless.davedoesdev.now.sh/counter.html if you want to take a look.