6 ms·

A small scheme VM, compiler, and REPL in 4k

94 points by dannyobrien 5y ago

throwaway81523 5y ago
Paper is acm-walled but code repo is https://github.com/udem-dlteam/ribbit https://github.com/udem-dlteam/ribbit . I would like to have seen Hedgehog Lisp ( https://github.com/sbp/hedgehog https://github.com/sbp/hedgehog ) in the comparison chart, since it has actually been used for practical projects. Its VM is around 20KB of object code. 4KB is impressively tiny, but any machine where 4k vs 20k makes a big difference is unlikely to have enough ram to run garbage collected applications. That seems to call more something more like Forth rather than Scheme. Hedgehog is a somewhat weird functional dialect of Lisp and I've been wanting for a while to convert it to a Scheme subset (mostly just using Scheme syntax instead of defun, etc) so people would be more familiar with it. Added: paper is here http://www.iro.umontreal.ca/~feeley/papers/YvonFeeleyVMIL21.pdf http://www.iro.umontreal.ca/~feeley/papers/YvonFeeleyVMIL21....
- deleted 5y ago
  [deleted]
- rcarmo 5y ago
  Added to https://taoofmac.com/space/dev/lisp https://taoofmac.com/space/dev/lisp along with a few others, since I'm fascinated by this kind of thing.
  - feeley 5y ago
    In your list you say "small and portable Scheme implementation with AOT compilation and 4K footprint". However the presence of an AOT compiler is not the most interesting part. The distinguishing feature is that in 4K there is a REPL that uses a dynamic compiler to do the "eval". In other words, the code entered at the REPL runs essentially as fast as if it was compiled by the AOT compiler.
    - throwaway81523 5y ago
      It seems to me (granted I haven't gotten it to work reliably at all yet) that the REPL is somewhat fragile, and I wonder if it might be easier as well as smaller to use a remote (tethered) compiler, as some Forth systems do. Re the repl, I may have figured out what went wrong with user-defined functions. Instead of saying (define (sq x) (* x x)) I apparently have to say (define sq (lambda (x) (* x x))). Maybe that is documented in the paper, which I still have to read.
- bsder 5y ago
  The rib encoding looks very clever. I need to digest the full implications of that. > 4KB is impressively tiny, but any machine where 4k vs 20k makes a big difference is unlikely to have enough ram to run garbage collected applications. Yeah, the paper itself says that the heap was 240K. A 4K system isn't very helpful if your heap is 240K. I'd like to see how this runs (if at all) with a 4K heap. Deceptively straightforward things like map and apply can cons up a whopping amount of intermediate garbage. > I would like to have seen Hedgehog Lisp ( https://github.com/sbp/hedgehog https://github.com/sbp/hedgehog ) in the comparison chart, since it has actually been used for practical projects Links to projects?
  - djwatson24 5y ago
    I agree the optimization looks backwards to me - in most of the microcontrollers I work on, the flash program space can easily be multiple megabytes, but the ram is usually the limiter around 128-512k.
    - feeley 5y ago
      The introduction in the paper explains the motivation for Ribbit: The use case which has motivated our work is code mobility where an executable program can be embedded in a document, email, or website. In that use case the size of the program must be small to minimize the transmission or loading time or to satisfy space constraints, such as the size of a disk boot sector, the URL length limit and the UDP packet size. On the other hand, the space used while the program is executing is of secondary importance. So the main target application is not microcontrollers, even if it can obviously be used for some microcontrollers (for example a 1-2$ ESP32-C3 has 400 KB of RAM). One of the possible applications of Ribbit is to implement the RVM (Ribbit VM) in the Excel spreadsheet formula language (which will soon be turing-complete with the addition of the LAMBDA form) to be able to program spreadsheets in Scheme. The execution environment has lots and lots of RAM, but you want the .xls file itself (which contains the RVM) to be as small as possible so it can easily be sent in emails, etc.
      - pumanoir 5y ago
chubot 5y ago
Code looks very cool There's even a Python implementation with 1 space indentation :) https://github.com/udem-dlteam/ribbit/blob/main/src/host/py/rvm.py https://github.com/udem-dlteam/ribbit/blob/main/src/host/py/...
neilv 5y ago
Non-ACM-paywalled paper from the home page of Marc Feeley: http://www-labs.iro.umontreal.ca/~feeley/papers/YvonFeeleyVMIL21.pdf http://www-labs.iro.umontreal.ca/~feeley/papers/YvonFeeleyVM...
throwaway81523 5y ago
I was unable to build ribbit from the git repo under Debian. The compile-all.sh script complained about absence of "gambit", and after installing gambc (Debian's gambit package) and changing the "gambit" command in the build script to gsc (gambit compiler), the script still throws error messages. I might mess with it some more, but I'm unfamiliar with the tool chain, so at first look I don't know what to try next. Did anyone else have better luck?
- feeley 5y ago
  You need to install Gambit HEAD, then you can: % cd src % gsi rsc.scm -m -t py -l max repl-max.scm % python3 repl-max.scm.py > (+ 1 (* 2 3)) 7 or for the C version: % gsi rsc.scm -m -t c -l max repl-max.scm % gcc -DCPROG -o repl-max.scm.exe repl-max.scm.c % ./repl-max.scm.exe > (+ 1 (* 2 3)) 7 To install Gambit follow the instructions here: https://github.com/gambit/gambit https://github.com/gambit/gambit
  - throwaway81523 5y ago
    Ah thanks, I'll try that. I made a little progress earlier and found that compilation was failing because some functions like (script-file) were not defined. Maybe those are in HEAD. It would be nice if the compilation process stayed with reasonably portable Scheme.
    - feeley 5y ago
      The Ribbit compiler was developed using Gambit but most of the code is portable. I rewrote a few parts with cond-expand to port rsc.scm to older versions of Gambit and also Guile and Chicken. If you pull the latest commit the Ribbit system should work with any of those Scheme systems. The README also contains usage instructions, here is a relevant part: The Ribbit compiler is written in Scheme and can be executed with Gambit, Guile or Chicken. It has been tested with Gambit v4.7.5 and above. For the best experience install Gambit from https://github.com/gambit/gambit https://github.com/gambit/gambit . Currently Ribbit supports the target languages C, JavaScript, Python and Scheme which are selectable with the compiler's `-t` option with `c`, `js`, `py`, and `scm` respectively. The compacted RVM code can be obtained with the target `none` which is the default. The `-m` option causes a minification of the generated program. This requires a recent version of Gambit. The `-l` option allows selecting the Scheme runtime library (located in the `lib` subdirectory). The `min` library has the fewest procedures and a REPL that supports the core Scheme forms only. The `max` library has most of the R4RS predefined procedures, except for file I/O. The `max-tc` library is like `max` but with run time type checking. The default is the `max-tc` library. Here are a few examples: Use Gambit to compile the minimal REPL to JavaScript and execute with nodejs: % cd src % gsi rsc.scm -t js -l min repl-min.scm % echo "(define f (lambda (n) (if (< n 2) n (+ (f (- n 1)) (f (- n 2))))))(f 25)" | node repl-min.scm.js > 0 > 75025 >

94 points by dannyobrien 5y ago

Paper is acm-walled but code repo is https://github.com/udem-dlteam/ribbit https://github.com/udem-dlteam/ribbit . I would like to have seen Hedgehog Lisp ( https://github.com/sbp/hedgehog https://github.com/sbp/hedgehog ) in the comparison chart, since it has actually been used for practical projects. Its VM is around 20KB of object code. 4KB is impressively tiny, but any machine where 4k vs 20k makes a big difference is unlikely to have enough ram to run garbage collected applications. That seems to call more something more like Forth rather than Scheme. Hedgehog is a somewhat weird functional dialect of Lisp and I've been wanting for a while to convert it to a Scheme subset (mostly just using Scheme syntax instead of defun, etc) so people would be more familiar with it. Added: paper is here http://www.iro.umontreal.ca/~feeley/papers/YvonFeeleyVMIL21.pdf http://www.iro.umontreal.ca/~feeley/papers/YvonFeeleyVMIL21....

deleted 5y ago
[deleted]
rcarmo 5y ago
Added to https://taoofmac.com/space/dev/lisp https://taoofmac.com/space/dev/lisp along with a few others, since I'm fascinated by this kind of thing.
- feeley 5y ago
  In your list you say "small and portable Scheme implementation with AOT compilation and 4K footprint". However the presence of an AOT compiler is not the most interesting part. The distinguishing feature is that in 4K there is a REPL that uses a dynamic compiler to do the "eval". In other words, the code entered at the REPL runs essentially as fast as if it was compiled by the AOT compiler.
  - throwaway81523 5y ago
    It seems to me (granted I haven't gotten it to work reliably at all yet) that the REPL is somewhat fragile, and I wonder if it might be easier as well as smaller to use a remote (tethered) compiler, as some Forth systems do. Re the repl, I may have figured out what went wrong with user-defined functions. Instead of saying (define (sq x) (* x x)) I apparently have to say (define sq (lambda (x) (* x x))). Maybe that is documented in the paper, which I still have to read.
bsder 5y ago
The rib encoding looks very clever. I need to digest the full implications of that. > 4KB is impressively tiny, but any machine where 4k vs 20k makes a big difference is unlikely to have enough ram to run garbage collected applications. Yeah, the paper itself says that the heap was 240K. A 4K system isn't very helpful if your heap is 240K. I'd like to see how this runs (if at all) with a 4K heap. Deceptively straightforward things like map and apply can cons up a whopping amount of intermediate garbage. > I would like to have seen Hedgehog Lisp ( https://github.com/sbp/hedgehog https://github.com/sbp/hedgehog ) in the comparison chart, since it has actually been used for practical projects Links to projects?
- djwatson24 5y ago
  I agree the optimization looks backwards to me - in most of the microcontrollers I work on, the flash program space can easily be multiple megabytes, but the ram is usually the limiter around 128-512k.
  - feeley 5y ago
    The introduction in the paper explains the motivation for Ribbit: The use case which has motivated our work is code mobility where an executable program can be embedded in a document, email, or website. In that use case the size of the program must be small to minimize the transmission or loading time or to satisfy space constraints, such as the size of a disk boot sector, the URL length limit and the UDP packet size. On the other hand, the space used while the program is executing is of secondary importance. So the main target application is not microcontrollers, even if it can obviously be used for some microcontrollers (for example a 1-2$ ESP32-C3 has 400 KB of RAM). One of the possible applications of Ribbit is to implement the RVM (Ribbit VM) in the Excel spreadsheet formula language (which will soon be turing-complete with the addition of the LAMBDA form) to be able to program spreadsheets in Scheme. The execution environment has lots and lots of RAM, but you want the .xls file itself (which contains the RVM) to be as small as possible so it can easily be sent in emails, etc.
    - pumanoir 5y ago

chubot 5y ago

Code looks very cool There's even a Python implementation with 1 space indentation :) https://github.com/udem-dlteam/ribbit/blob/main/src/host/py/rvm.py https://github.com/udem-dlteam/ribbit/blob/main/src/host/py/...

neilv 5y ago

Non-ACM-paywalled paper from the home page of Marc Feeley: http://www-labs.iro.umontreal.ca/~feeley/papers/YvonFeeleyVMIL21.pdf http://www-labs.iro.umontreal.ca/~feeley/papers/YvonFeeleyVM...

throwaway81523 5y ago

I was unable to build ribbit from the git repo under Debian. The compile-all.sh script complained about absence of "gambit", and after installing gambc (Debian's gambit package) and changing the "gambit" command in the build script to gsc (gambit compiler), the script still throws error messages. I might mess with it some more, but I'm unfamiliar with the tool chain, so at first look I don't know what to try next. Did anyone else have better luck?

feeley 5y ago
You need to install Gambit HEAD, then you can: % cd src % gsi rsc.scm -m -t py -l max repl-max.scm % python3 repl-max.scm.py > (+ 1 (* 2 3)) 7 or for the C version: % gsi rsc.scm -m -t c -l max repl-max.scm % gcc -DCPROG -o repl-max.scm.exe repl-max.scm.c % ./repl-max.scm.exe > (+ 1 (* 2 3)) 7 To install Gambit follow the instructions here: https://github.com/gambit/gambit https://github.com/gambit/gambit
- throwaway81523 5y ago
  Ah thanks, I'll try that. I made a little progress earlier and found that compilation was failing because some functions like (script-file) were not defined. Maybe those are in HEAD. It would be nice if the compilation process stayed with reasonably portable Scheme.
  - feeley 5y ago
    The Ribbit compiler was developed using Gambit but most of the code is portable. I rewrote a few parts with cond-expand to port rsc.scm to older versions of Gambit and also Guile and Chicken. If you pull the latest commit the Ribbit system should work with any of those Scheme systems. The README also contains usage instructions, here is a relevant part: The Ribbit compiler is written in Scheme and can be executed with Gambit, Guile or Chicken. It has been tested with Gambit v4.7.5 and above. For the best experience install Gambit from https://github.com/gambit/gambit https://github.com/gambit/gambit . Currently Ribbit supports the target languages C, JavaScript, Python and Scheme which are selectable with the compiler's `-t` option with `c`, `js`, `py`, and `scm` respectively. The compacted RVM code can be obtained with the target `none` which is the default. The `-m` option causes a minification of the generated program. This requires a recent version of Gambit. The `-l` option allows selecting the Scheme runtime library (located in the `lib` subdirectory). The `min` library has the fewest procedures and a REPL that supports the core Scheme forms only. The `max` library has most of the R4RS predefined procedures, except for file I/O. The `max-tc` library is like `max` but with run time type checking. The default is the `max-tc` library. Here are a few examples: Use Gambit to compile the minimal REPL to JavaScript and execute with nodejs: % cd src % gsi rsc.scm -t js -l min repl-min.scm % echo "(define f (lambda (n) (if (< n 2) n (+ (f (- n 1)) (f (- n 2))))))(f 25)" | node repl-min.scm.js > 0 > 75025 >