feeley

I'm really excited about this work, although I haven't read the code or paper yet. It seems to me Fractal would be ideal for running benchmarks for compilers so that the OS-induced noise is kept to a minimum.

Author: do you see issues with that use case?

Related:

The Gambit Scheme REPL that comes with a tutorial, supports threads in the browser and has a JS FFI: https://try.gambitscheme.org

Gambit in emacs in the browser: https://feeley.github.io/gambit-in-emacs-in-the-browser/

An alternative to Scrappy is the free CodeBoot web app (https://codeboot.org), which allows you to create web apps in Python that are fully encapsulated in a URL. No installation is required—neither for the developer nor the user. Below is an example of a math practice app with simple user interaction through dialogs. To create a web app URL, right-click the "play" button and choose the type of link you want to generate.

https://app.codeboot.org/5.3.1/?init=.fbWF0aF9wcmFjdGljZS5we...

For more complex UIs, CodeBoot provides an FFI for accessing the DOM directly from Python code. For example here is a dice throwing app with a button to roll the dice again. The text in the button has translations to multiple languages and will adjust to the browser's default.

https://app.codeboot.org/5.3.1/?init=.fZGljZS5weQ==~XQAAgADq...

I have designed 2 web based code playgrounds that you may find interesting.

https://try.gambitscheme.org is a playground for the Scheme language (specifically Gambit Scheme). It has a REPL and a code editor that saves files in the browser local storage. It also has a tutorial for learning the basics of Scheme.

https://codeboot.org is a playground for Python (there's an old version that supports JavaScript and we may resurrect it at some point). It was specifically designed as a simple IDE to teach programming to beginners and is in use at the Université de Montréal. Aside from the simple and intuitive UI, it has two important features for teaching:

1) Fine granularity single-stepping of Python code to help teach students how the computer goes about executing the code. It displays a bubble containing the variables in scope and their values.

2) It can bundle programs and the current state of execution in a URL that can be embedded in documents (HTML, PDF, PowerPoint, Keynote, etc) so that coding examples can be executed by the students in a single click. It also allows students to create simple web apps that require no installation and can easily be shared with others (because the URL contains all the relevant code of the app). You will find examples of this feature on the following pages:

https://codeboot-org.github.io/presentations/

https://codeboot-org.github.io/cegep/ (in french, but just click on the images)

I just posted the same link to HN 3 days after you, purely by coincidence. Does it mean we are stuck in an endless tail-call loop on this topic?

The try.gambitscheme.org web app has most of these features and more:

- REPL history with up/down arrows (explained on the landing page's README)

- You can use the "help" procedure to browse the full documentation

- TAB key for autocompletion

- In addition to the REPL there is a code editor to edit programs stored in the browser

- The system supports multiple threads, one REPL per thread

- There is a builtin tutorial to learn the basics of Scheme with examples executable in the REPL with a single click on a "run" button

- The REPL supports single stepping the execution of code

- Easy interface to JS with the SIX syntax extension, e.g. (let ((msg "hello")) \console.log(`msg, 1+2/3))

- The error messages are clear and precise giving the file and line number and highlighting in yellow the piece of code (in the REPL or file) that raised the exception. Just try this in both systems to see the difference:

    > (define (f x) (/ 1 (* x x)))
    > (f 5)
    > (f "hello") ;; the * procedure will raise an exception and highlight "(* x x)"

How does it compare to https://try.gambitscheme.org ?

I'm not sure what you mean by "minimal set of instructions". What is more important for bootstrapping is to restrict the programming style used to write the compiler. So if that was the goal I would implement pointers and maybe arrays, and not implement other types such as structs (which can be useful but add complexity to the compiler, i.e. it is no longer the case that a value fits in a machine word). Functions and function call would obviously be useful to add. But that's about it.

What I'd love to do someday is to write a compiler for a fairly complete C subset in POSIX shell. The goal would be to use only a POSIX shell and this compiler to compile TCC, and then use TCC to bootstrap gcc, all from source. This would be a great tool for reproducible builds from source. If someone here finds this interesting and would like to help out, please reach out to me.

tinyc.c was designed to illustrate three things at once in a second year course on concepts of programming languages. The course had 4 parts: imperative programming (using C), functional programming (using Scheme), and logic programming (using Prolog), and programming language implementation. For the imperative programming part it was important to show enough of the C language for the following operating systems course, so we needed to show C manual memory management and pointers in a rather detailed way. So tinyc.c was principally an example of programming with pointers, including pointer arithmetic such as *pc++. It was indirectly an example of compiler and interpreter, subjects we also covered in the course. I have also used parts of the compiler in a third year compiler course but not as the basis of a project. I have always asked (forced?) my students to use Scheme to implement their compiler projects... a much friendlier language than C for compiler writing.

Haven't looked at what it would take to support C89 (or other) fully. Certainly it is possible to extend the compiler in small increments to implement more stuff: all the operators, local variables, arrays, pointers, functions, etc. The hardest part I would say is implementing types (starting with the C syntax for types!) and also handling the memory allocation for them. Nothing too complex when you know what you are doing. My personal interest is with higher-level languages and I have worked on various Scheme systems over the last 30 years. If you like small language implementations then take a look at Ribbit which is feature-full with a tiny VM. Also check out sectorlisp (not my work) which is a fascinating tour de force.

To be clear, I'm not claiming to be the first to have used the name Tiny-C, just that the confusion with TCC is not intentional. Your links to DDJ are great an bring back memories of the good old days when there was much to learn from reading DDJ and Byte magazine!

That's not on my TODO! But Gambit does have support for TCC. For example you can use TCC to compile a file to a dynamically loadable object file (aka shared library). The compilation is faster than gcc and the code size is typically smaller too:

  $ cat hello.scm
  (display "hello!\n")
  $ gsc hello.scm
  $ gsi hello.o1
  hello!
  $ ls -l hello.o1   # this is generated by gcc
  -rwxrwxr-x 1 feeley feeley 18152 Mar 13 17:16 hello.o1
  $ rm hello.o1
  $ gsc -cc "tcc -shared" hello.scm
  $ gsi hello.o1
  hello!
  $ ls -l hello.o1   # this is generated by tcc
  -rwxrwxr-x 1 feeley feeley 4432 Mar 13 17:17 hello.o1

Author here. Just for context tinyc.c was created in 2000 (I found the file in my archives and the last modification date is January 12, 2001). I was not aware at the time of Fabrice Bellard's work which after all won the IOCCC in 2001, so the confusion with TCC was not intentional. My tinyc.c was meant to teach the basics of compilers in a relatively accessible way, from parsing to AST to code generation to bytecode interpreter. And yes it is the subset of C that is tiny, not a tiny compiler for the full C language.

If you want full Scheme running on top of JS in the browser: https://try.gambitscheme.org

It has tail calls, continuations and even green threads (SRFI 18 compliant), and a decentralized module system that can load libraries directly from github and a JS FFI! See this paper for advanced examples that you can copy-paste to the REPL: http://www.iro.umontreal.ca/~feeley/papers/BelangerFeeleyELS...

Gambit supports the R7RS module system and has a decentralized module system that can automatically download libraries from git repositories. Take a look at the "Libraries" section of the online REPL's tutorial for a few examples, or just type at the REPL:

  > (module-whitelist-add! '(github.com/feeley))
  > (import (github.com/feeley/roman demo))

This paper might be helpful if you want to know why it was designed that way:

https://www.iro.umontreal.ca/~feeley/papers/HamelFeeleyELS20...

The FFI with JavaScript is nice. Have a look at this paper, in particular the examples that can be copy-pasted to https://try.gambitscheme.org:

https://www-labs.iro.umontreal.ca/~feeley/papers/BelangerFee...

I'm not sure what part of your project is web-based and what you mean by "web-based". Do you mean executing Lisp/Scheme code on the browser side or the server side? In any case you should consider Gambit Scheme that has a complete JavaScript backend. For example check out the https://try.gambitscheme.org site to see the online REPL in action.

An important design goal for the POSIX shell version of the RVM is to depend on the fewest external tools possible. Each dependency brings with it a portability risk because unix tools can be subtly different between environments (for example macOS vs linux, and even between linuxes, and even between versions of the same distribution of linux).

So the core of the RVM has no dependencies with external tools (i.e. it is in "pure" shell script). The only dependencies are for I/O, namely for the "putchar" RVM primitive and the "getchar" RVM primitive (both of which do byte-at-a-time binary I/O on stdin and stdout). For putchar the shell "printf" (which is usually builtin) command is used, specifically

    printf \\$((byte/64))$((byte/8%8))$((byte%8))

For getchar is is not possible to use the shell "read" command because it does not handle null bytes on stdin (and we want Ribbit to support binary I/O). This is admittedly somewhat of an artificial constraint given that Ribbit will probably be mostly used for text processing, like to write compilers that map source code text to target code text. So getchar is implemented with

    set `sed q | od -v -A n -t u1`

and then the next byte on stdin is available using $1 and "shift" is used to move to the next byte. The call to sed is to read each line separately (useful to implement a REPL where you enter a command which is executed before having to enter the next command). Both "sed" and "od" are standard unix tools. Moreover we checked that those set of options have existed for a long time (at least the early 1990's). It would be interesting to test many POSIX shells to verify Ribbit's portability (we used bash, dash, zsh and ksh for our testing).

The low performance of the POSIX shell RVM is due to two things. First, the shell's interpreter is not fast. The simple loop

    n=10000000; while [ $n -gt 0 ]; do n=$((n-1)); done

runs about 5000 times slower with bash than the equivalent JavaScript code run with nodejs, which is implemented with a JIT. Secondly, the POSIX shell does not have arrays so it is necessary to use the shell "eval" command to do indexing. For example a[i]=0 becomes

    eval a$i=0

As you can imagine the RVM implementation uses arrays all over the place for implementing access to the RVM's stack and Scheme objects (both of which are implemented using a garbage collected heap, which is conceptually an array of 3 field records and implemented in the shell as 3 "arrays").

The POSIX shell version of Ribbit was designed to be as portable as possible, only relying on a POSIX shell to run Scheme code. This can be useful in a context where you only have a POSIX shell at hand and you want to bootstrap a more efficient set of development tools (C compiler, editor, etc) and you don't mind waiting a day or two for the build to complete. It is also useful when you want a reproducible build pipeline and the only tool you trust is the shell.

Ribbit achieves a 4K footprint, but that just means the size of the Ribbit VM plus the size of the compacted compiled code. The uncompacted code is stored in RAM in the form of linked "ribs" (3 cell objects, or 6/12/24 bytes depending on the word size) and this is not very memory efficient compared to a bytecode representation. So it takes on the order of 64K RAM to run the REPL, which is about 1000 lines of Scheme code. So a rule of thumb is about 64 bytes of RAM per line of Scheme code. You can use that ratio to determine how large of a Scheme program will fit on your specific device.

The Ribbit design is optimized for a setting where the program is communicated say over the Web before it is executed, so it is important to minimize the footprint = transfer time.

The go implementation of the RVM is not yet finished. I would say the reference implementations are the JavaScript, Python and Scheme ones. They were written in that order and build up on various ways of expressing things compactly. Originally there was no minification step so the code was written with short identifiers and few comments (the size of the source code is the metric for the "footprint" of the system and comments count). To understand the code it helps to read the following paper that explains the Ribbit VM: http://www.iro.umontreal.ca/~feeley/papers/YvonFeeleyVMIL21.... .

I wrote TCO in the title because with "proper tail calls" the title exceeded the allowed limit on hacker news! Moreover most people will know the term TCO and less the more precise term proper tail calls. You are of course correct that tail calls are a required aspect of the Scheme specification even though many implementations that call themselves "Scheme" don't implement this fully.

You need a Scheme interpreter (Gambit, Chicken or Guile have been tested) to run the Ribbit AOT compiler. The Ribbit AOT compiler will compile a Scheme program to one of the supported target languages: C, JavaScript, Python, Scheme or POSIX shell script. Ribbit has been designed for a small footprint, so the generated target code is quite compact (as small as 2-4 KB for small programs). This is much more compact than any other existing Scheme system. Moreover the system is very portable to other target languages because Ribbit is implemented with a tiny virtual machine. There are ports underway to Java, Scala, Lua, Rust, go, Ruby, Haskell, and Idriss. This means a larger program in any of these languages can embed the Ribbit VM for scripting or other purposes.

Ribbit is also bootstrapped (it can compile itself). This means that you only need another Scheme system for the initial step of the bootstrap to compile the Ribbit compiler to one of the supported target languages. After this step the Ribbit compiler only needs an implementation of the target language to run. For example, you can use the Gambit interpreter to compile the Ribbit compiler to a POSIX shell script (about 64K bytes). After this is done then you only need a POSIX shell to compile any Scheme program to C, JavaScript, Python, or POSIX shell script.

In its current state the POSIX shell target is mostly a proof of concept to demonstrate that the Ribbit VM is extremely portable. One area of practical use is for bootstrapping compilers for other languages using minimal tools (see the Mes project https://bootstrappable.org/projects/mes.html for bootstrapping gcc to have a reproducible build process for gcc). With Ribbit's POSIX shell target it would be possible to build gcc on any system that has a POSIX shell (without needing other build tools like a C compiler, linker, etc).

It is almost instantaneous:

    % /usr/bin/time gsi rsc.scm -t c -l min repl-min.scm
            0.06 real         0.05 user         0.00 sys
    % gcc -O3 repl-min.scm.c
    % echo "(define f (lambda (n) (if (< n 2) n (+ (f (- n 1)) (f (- n 2))))))(f 25)" | /usr/bin/time ./a.out
    > 0
    > 75025
    >
            0.10 real         0.10 user         0.00 sys

My guess is that you were using an old version of Gambit (before I added the support for older versions of Gambit).

The work on Ribbit is not driven by a specific application. It started as a challenge to write the smallest footprint implementation of Scheme after being inspired by the "sectorlisp" system (which has now reached an amazing milestone of just 0.5 KB!). However sectorlisp doesn't have a GC, continuations, tail-calls, etc so the comparison is a bit apples-to-oranges.

The main advantages of the RVM are its small size and its portability. This is particularly useful for code mobility. The exact same Scheme code can run on the desktop, in the browser, on the web server, on a microcontroller, an Excel spreadsheet, a shell script, etc etc And because continuations are a good way to represent the state of a running process I foresee applications where a running program migrates easily from one environment to the other by serializing the continuation (a game running in your desktop browser could be migrated to the browser on your phone to continue playing on the subway ride back home).

Concerning "functional-style programming (avoiding mutation) inherently uses more ram than a more mutation-heavy style" it greatly depends on how smart your compiler is. A smart one can in some cases generate the same code. An example that comes to mind is a tail-recursive function that adds numbers from a list. The functional program has no mutations but a compiler doing TCO can generate the same code as an imperative program that uses mutations.

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 .

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
      >

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

Ribbit's max library contains most of the R4RS predefined procedures (even call/cc). The main things missing are variadic procedures (unfortunately this includes the "list" procedure so you need to replace (list 1 2 3) by (cons 1 (cons 2 (cons 3 '())))) and also all the file opening operations. There is read-char, write-char, etc but they only do console I/O. These things could be added at the price of a larger footprint. One simple way to do this is to have the RVM run the code of a meta-circular Scheme evaluator written in Scheme.

If you are interested in building a a self-contained HTML document that embeds a full featured Scheme implementation, you should look into Gambit. Check out https://try.gambitscheme.org

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.