Skip to content
A Scheme interpreter with first-class continuations in circa 800 lines of TypeScript code
TypeScript JavaScript HTML
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
example
LICENSE
README.md
arith.ts
scm.ts

README.md

A Little Scheme in TypeScript

This is a small interpreter of a subset of Scheme in circa 800 lines of TypeScript 3.5/Node.js 12. It implements the same language as

and their meta-circular interpreter, little-scheme.

You can run it on web browsers by giving appropriate values to readStringFrom and write and by setting stdInOnData (and stdInOnEnd) as the callback(s) of an asynchronous input. Refer to the head and tail of scm.ts for these variables and function(s). See https://nukata.github.io/little-scheme-in-typescript/example/ for a simple example.

As a Scheme implementation, it optimizes tail calls and handles first-class continuations properly.

How to run

$ tsc -strict -t ESNext --outFile scm.js scm.ts
$ node scm.js
> (+ 5 6)
11
> (cons 'a (cons 'b 'c))
(a b . c)
> (list
| 1
| 2
| 3
| )
(1 2 3)
> 

Or just use example/scm.js, which I provided by compiling scm.ts in the same way as above.

$ node example/scm.js
> (+ 7.8 9)
16.8
> 

Press EOF (e.g. Control-D) to exit the session.

> Goodbye
$ 

You can also open example/index.html or https://nukata.github.io/little-scheme-in-typescript/example/ with a modern web browser to run scm.js.

$ open example/index.html
$ open https://nukata.github.io/little-scheme-in-typescript/example/

How to run your Scheme script

You can run node scm.js with a Scheme script. Examples are found in little-scheme; download it at .. and you can try the following:

$ node scm.js ../little-scheme/examples/yin-yang-puzzle.scm

*
**
***
****
*****
******
*******
********
*********
^C
$ node scm.js ../little-scheme/examples/amb.scm
((1 A) (1 B) (1 C) (2 A) (2 B) (2 C) (3 A) (3 B) (3 C))
$ node scm.js ../little-scheme/examples/nqueens.scm
((5 3 1 6 4 2) (4 1 5 2 6 3) (3 6 2 5 1 4) (2 4 6 1 3 5))
$ node scm.js ../little-scheme/scm.scm < ../little-scheme/examples/nqueens.scm
((5 3 1 6 4 2) (4 1 5 2 6 3) (3 6 2 5 1 4) (2 4 6 1 3 5))
$ 

Press INTR (e.g. Control-C) to terminate the yin-yang-puzzle.

Put a "-" after the script in the command line to begin a session after running the script.

$ node scm.js ../little-scheme/examples/fib90.scm -
2880067194370816120
> (globals)
(apply call/cc globals error = < * - + symbol? eof-object? read newline display
list not null? pair? eqv? eq? cons cdr car fibonacci)
> (fibonacci 16)
987
> (fibonacci 1000)
43466557686937456435688527675040625802564660517371780402481729089536555417949051
89040387984007925516929592259308032263477520968962323987332247116164299644090653
3187938298969649928516003704476137795166849228875
> 

The implemented language

Scheme Expression Internal Representation
numbers 1, 2.3 bigint or number
#t true
#f false
strings "hello, world" string
symbols a, + class Sym
() null
pairs (1 . 2), (x y z) class Cell
closures (lambda (x) (+ x 1)) class Closure
built-in procedures car, cdr class Intrinsic
continuations class Continuation
  • Integers are represented by bigint, which is supported by TypeScipt 3.2 and later, Node.js 10.4 and later, Firefox 68 and later etc. On the platforms that do not support bigint (e.g. Safari 12.1), integers are represented by number automatically. See tryToParse in arith.ts.

The implementation is similar to those of little-scheme-in-dart and little-scheme-in-cs.

Expression types

  • v [variable reference]

  • (e0 e1...) [procedure call]

  • (quote e)
    'e [transformed into (quote e) when read]

  • (if e1 e2 e3)
    (if e1 e2)

  • (begin e...)

  • (lambda (v...) e...)

  • (set! v e)

  • (define v e)

For simplicity, this Scheme treats (define v e) as an expression type.

Built-in procedures

(car lst) (not x) (eof-object? x)
(cdr lst) (list x ...) (symbol? x)
(cons x y) (call/cc fun) (+ x y)
(eq? x y) (apply fun arg) (- x y)
(eqv? x y) (display x) (* x y)
(pair? x) (newline) (< x y)
(null? x) (read) (= x y)
(error reason arg) (globals)
  • (error reason arg) throws an error with the message "Error: reason: arg". It is based on SRFI-23.

  • (globals) returns a list of keys of the global environment. It is not in the standard.

See GlobalEnv in scm.ts for the implementation of the procedures except call/cc and apply.
call/cc and apply are implemented particularly at applyFunction in scm.ts.

I hope this serves as a handy model of how to write a Scheme interpreter in TypeScript/JavaScript.

You can’t perform that action at this time.