2017-04-24
Shen Language Port for Wasp Lisp
This post intersects two of my favourite lispy languages. Shen is a functional programming language with a number of interesting features. These include:
- Optional static type checking
- Pattern matching
- Integrated Prolog system
- Parsing libraries
I've written about Shen Prolog before which gives a bit of a feel for the language.
Wasp Lisp is a small Scheme-like lisp with lightweight concurrency and the ability to send bytecode across the network. It's used in the MOSREF secure remote injection framework. I've written a number of posts about it.
A feature of Shen is that it is designed to run on top of a lighter weight lisp called KLambda. KLambda has only about 46 primitives, many of which already exist in lisp systems, making it possible to write compilers to other languages without too much work. There exist a few Shen ports already. I wanted to port Shen to Wasp Lisp so I can experiment with using the pattern matching, Prolog and types in some of the distributed Wasp code I use.
Wasp Lisp is not actively developed but the author Scott Dunlop monitors the github repository and processes pull requests. Shen requires features that Wasp Lisp doesn't currently support, like real numbers. I maintain a fork on github that implements the features that Shen needs and any features that apply back to core Wasp Lisp I'll upstream.
This port is heavily based on the Shen Scheme implementation. Much of the code is ported from Scheme to Wasp Lisp and the structure is kept the same. The license for code I wrote is the same as the Shen Scheme License, BSD3-Clause.
The Shen Source is written in the Shen language. Using an existing Shen implementation this source is compiled to Klambda:
$ shen-chibi
(0-) (load "make.shen")
(1-) (make)
compiling ...
To port to another language then becomes writing a KLambda interpreter or compiler. In this case it's a compiler from KLambda to Wasp Lisp. Implementing the primitives is also required but there aren't many of them. Some of the characters that KLambda uses in symbols aren't compatible with the Wasp reader so I used an S-expression parser to read the KLambda code and then walked the tree converting expressions as it went. This is written in Wasp code, converted from the original Scheme. In hindsight it probably would have been easier to write this part in Shen and bootstrap it in another Shen instance to make use of Shen's parsing and pattern matching libraries.
Shen makes heavy use of tail calls in code meaning some form of tail call optimisation is needed to be efficient. In a previous post I mentioned some places where Wasp doesn't identify tail calls. These are cases Shen hit a lot, causing performance issues. I made some changes to the optimizer to identify these cases and it improved the Shen on Wasp runtime performance quite a bit.
Current Port State
This is a very early version. I've only just got it working. The Shen tests pass with the exception of the Proof Assistant test which hangs when loading.
Note 2017-04-26: The bug with the proof assistant test not passing is now fixed. It was caused by an integer overflow when computing complexities within the Shen prolog code. Wasp integers are smaller than other Shen implementations which is why none of them hit the issue. The binaries have been updated with this fix.
The port is slower than I'd like - about half the speed of the Shen C interpreter and significantly slower than Shen Scheme and Shen on SBCL. I've done some work on optimizing tail calls in the fork of the Wasp VM for Shen but there's much more work on the entire port that could improve things.
Binaries
The following compiled binaries are available:
shen_static.bz2. This is a static 64-bit linux binary with no dependancies. It should run on any 64-bit Linux system. Decompress with:
$ bunzip2 shen_static.bz2
$ chmod +x shen_static
$ ./shen_static
shen_macos.bz2. 64-bit binary for Mac OS. Decompress with bunzip2 as above.
shen.zip. The zip file contains a Windows 64-bit binary, shen.exe. It should run on any modern 64-bit Windows system.
Building
First step, build the fork of Wasp Lisp needed to run:
$ git clone --branch shen https://github.com/doublec/WaspVM wasp-shen
$ cd wasp-shen
$ make install
Follow the prompts for the location to install the wasp lisp binaries and add that bin directory of that location to your path:
$ export PATH=$PATH:/path/to/install/bin
Shen is provided in source code format from the Shen Sources github repository. The code is written in Shen. It needs a working Shen system to compile that code to KLambda, a small Lisp subset that Shen uses as a virtual machine.
This KLamda code can be found in the kl directory in the shen-wasp repository. These KLambda files are compiled to Wasp Lisp and stored as compiled code in the compiled directory. The shen wasp repository includes a recent version of these files. To generate, or re-generate, run the following commands:
$ git clone https://github.com/doublec/shen-wasp
$ cd shen-wasp
$ rlwrap wasp
>> (import "driver")
>> (compile-all)
Compiling toplevel.kl
Compiling core.kl
Compiling sys.kl
Compiling sequent.kl
Compiling yacc.kl
Compiling reader.kl
Compiling prolog.kl
Compiling track.kl
Compiling load.kl
Compiling writer.kl
Compiling macros.kl
Compiling declarations.kl
Compiling types.kl
Compiling t-star.kl
This will create files with the Wasp Lisp code in the compiled/*.ms files, and the compiled bytecode in compiled/*.mo files.
Creating a Shen executable can be done with:
$ waspc -exe shen shen.ms
$ chmod +x shen
$ rlwrap ./shen
Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 20.0
running under Wasp Lisp, implementation: WaspVM
port 0.3 ported by Chris Double
(0-)
Note that it takes a while to startup as it runs through the Shen and KLambda initialization.
Running from the Wasp REPL
Shen can be run and debugged from the Wasp REPL. To load the compiled code and run Shen:
$ rlwrap wasp
>> (import "driver")
>> (load-all)
>> (kl:shen.shen)
Shen, copyright (C) 2010-2015 Mark Tarver
www.shenlanguage.org, Shen 20.0
running under Wasp Lisp, implementation: WaspVM
port 0.3 ported by Chris Double
(0-)
When developing on the compiler it's useful to use eval-all instead of load-all. This will load the KLambda files, compile them to Scheme and eval them:
>> (eval-all)
>> (kl:shen.shen)
...
A single input line of Shen can be entered and run, returning to the Wasp REPL with:
>> (kl:shen.read-evaluate-print)
(+ 1 2)
3:: 3
KLambda functions can be called from Wasp by prefixing them with kl:. For example:
>> (kl:shen.read-evaluate-print)
(define factorial
1 -> 1
X -> (* X (factorial (- X 1))))
factorial:: factorial
>> (kl:factorial 10)
:: 3628800
Shen allows introspecting compiled Shen functions and examining the KLambda code. From the Wasp REPL this is useful for viewing the KLambda and comparing with the generated Wasp Lisp:
>> (kl:ps 'factorial)
:: (defun factorial (V1172) (cond (...) (...)))
>> (pretty (kl:ps 'factorial))
(defun factorial (V1172 ) (cond ((= 1 V1172 ) 1 ) (#t (* V1172 (factorial (- V1172 1 ) ) ) ) ) ) :: null
>> (pretty (kl->wasp (kl:ps 'factorial)))
(begin (register-function-arity (quote factorial ) 1 )
(define (kl:factorial V1172)
(cond
((kl:= 1 V1172) 1)
(#t (* V1172 (kl:factorial (- V1172 1))))))
(quote factorial ) ) :: null
Cross Compilation
Wasp binaries are a small Wasp VM stub plus the compiled Lisp code appended to it. This makes building for other platforms easy as long as you have the stub for that platform. Wasp can be built for Android and static binaries via musl are possible.
I've made the following stubs available for building binaries for other systems:
Decompress them and copy into the lib/waspvm-stubs directory where Wasp Lisp was installed. Shen can then be built on any host platform for 64 bit linux, 64 bit Linux static binaries, 64 bit Windows or 64 bit Mac OS with:
$ waspc -exe shen -platform linux-x86_64 shen.ms
$ waspc -exe shen_static -platform static-linux-x86_64 shen.ms
$ waspc -exe shen.exe -platform win-x86_64 shen.ms
$ waspc -exe shen_macos -platform Darwin-x86_64 shen.ms
Learning Shen
Some places to go to learn Shen:
- The Shen OS Kernel Manual has a good overview of what the open source version of Shen can do.
- Shen System Functions
- Kicking the tires of Shen Prolog
- Shen, A Sufficiently Advanced Lisp
- Shen Trick Shots
- The Book of Shen
