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, WebAssembly and C.

It consists of the following components:

Macro expansion

Derived forms are expanded to basic forms in scm/expand.scm.

Conversion to continuation-passing style

The program is converted to CPS form as decribed here. See the scan function in scm/mce.scm, which is roughly as described here.

Executing the CPS

The CPS form is executed by repeatedly stepping through its state, as decribed here. See the run function in 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 here. See the mce-save and mce-restore functions in 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 here.

Core runtime

Only booleans, numbers, vectors and binary arrays are implemented in the runtimes. Other types are implemented at language level. Pairs are 2-length vectors and characters, symbols and strings are tagged binary arrays.

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

Building

Scheme

You’ll need to install the 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 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 cpp directory. This executes CPS forms produced by scm/scan.

JavaScript

Make sure you have Node.js installed and then run:

pushd js
npm install
popd

The CPS execution component is in js/mce.js.

WebAssembly

Install wasi-sdk to /opt/wasi-sdk and then:

make -C cpp/wasm

You should end up with mce.wasm in the cpp/wasm directory. This is the CPS execution component. You’ll need a WebAssembly runtime which supports WASI to run it, for example wasmtime or Node.js.

C

Run:

make -C c

You should end up with executable mce in the c directory. This executes CPS forms produced by scm/scan.

Running the examples

There are a number of examples in the examples directory.

To run, say 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.js

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.js

Using the C engine:

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

Note: the --bconvert-out option converts the CPS form (JSON format) into a binary format that the C engine understands. There is a corresponding --bconvert-in option which converts C engine binary format to JSON format that the other engines understand.

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.js < test-loop.cps
wasmtime cpp/wasm/mce.wasm < test-loop.cps
node js/run_wasm.js < test-loop.cps
./cpp/mce --bconvert-out < test-loop.cps | ./c/mce

State-saving

The example 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.js, wasmtime cpp/wasm/mce.wasm or js/run_wasm.js 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.js | ./scm/mce
0
1
2
3
4
5
save 22137
restore 22136
6
7
8
9
10

or from a C++ engine to a C one:

$ ./scm/expand < examples/test-state2.scm | ./scm/scan | ./cpp/mce | ./cpp/mce --bconvert-out | ./c/mce
0
1
2
3
4
5
save 676481
restore 676483
6
7
8
9
10

or from a C engine to a Scheme one:

$ ./scm/expand < examples/test-state2.scm | ./scm/scan | ./cpp/mce --bconvert-out | ./c/mce | ./cpp/mce --bconvert-in | ./scm/mce
0
1
2
3
4
5
save 676630
restore 676632
6.0
7.0
8.0
9.0
10.0

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 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.

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

C garbage collector

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

• Memory is allocated from a large fixed-size byte array.

• Memory allocated from the byte array is never individually freed.

• Once the amount of memory allocated exceeds a certain threshold:

  1. A new large fixed-size byte array is created.

  2. The current computation state and its reachable data is copied from the current array to the new array.

  3. The current array is freed.

  4. The new array becomes the current array.

You can change the array size using the --memory-capacity argument to ./c/mce. The default is 10 (Mebibytes).

You can change the threshold using the --gc-threshold argument. The default is 8 (Mebibytes).

Stateless servers

A serverless deployment for Netlify Functions can be found in the 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 examples/stateless/counter.scm:

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 a cryptographic key by running:

./stateless/make_key.sh

This produces stateless/key which is 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.

Follow the Netlify CLI instructions to link your repository with Netlify:

npm install netlify-cli -g
netlify login
netlify init

Then visit your repository’s site on Netlify and in Settings→Build & deploy→Environment (https://app.netlify.com/sites/XXX/settings/deploys#environment) add an environment variable called STATELESS_KEY with value set to the content of the stateless/key file.

You should now be able to use the example at https://XXX.netlify.app/counter.html.

Mine is available at https://mce-stateless.netlify.app/counter.html if you want to take a look.

If you want to try it out locally, you can do:

netlify build # you only need to do this once
netlify dev

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