GitHub - nukata/little-scheme-in-python: A Scheme interpreter with first-class continuations in circa 500 lines of Python code

A Little Scheme in Python

This is a small (458 lines) interpreter of a subset of Scheme. It runs on both Python 2.7 and Python 3.8. It implements almost the same language as

and their meta-circular interpreter, little-scheme.

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

The implementation has been revised along with little-scheme-in-go since v3.0. See archived folder for the previous implementation.

How to run

Run scm.py to start a Scheme session.

$ ./scm.py
> (+ 5 6)
11
> (cons 'a (cons 'b 'c))
(a b . c)
> (list
| 1
| 2
| 3
| )
(1 2 3)
>

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

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

$ cat ../little-scheme/examples/fib90.scm
;; Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1. 
;; cf. https://oeis.org/A000045
(define fibonacci
  (lambda (n)
    (define _fib
      (lambda (i F_i F_i+1)
        (if (= i n)
            F_i
          (_fib (+ i 1) F_i+1 (+ F_i F_i+1)))))
    (_fib 0 0 1)))                      ; i=0, F(0)=0, F(1)=1

(display (fibonacci 90))
(newline)
;; => 2880067194370816120
$ ./scm.py ../little-scheme/examples/fib90.scm
2880067194370816120
$

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

$ ./scm.py ../little-scheme/examples/fib90.scm -
2880067194370816120
> (fibonacci 0)
0
> (fibonacci 1)
1
> (fibonacci 16)
987
> (fibonacci 1000)
43466557686937456435688527675040625802564660517371780402481729089536555417949051
89040387984007925516929592259308032263477520968962323987332247116164299644090653
3187938298969649928516003704476137795166849228875
>

You can also run little-scheme with scm.py.

$ ./scm.py ../little-scheme/scm.scm
(+ 5 6)
=> 11
(list
1
2
3
)
=> (1 2 3)

$ ./scm.py ../little-scheme/scm.scm < ../little-scheme/examples/fib90.scm
2880067194370816120
$

The implemented language

Scheme Expression	Internal Representation
numbers `1`, `2.3`	`int` or `float` (or `long`)
`#t`	`True`
`#f`	`False`
strings `"hello, world"`	`class SchemeString`
symbols `a`, `+`	interned `str`
`()`	`NIL`, a singleton of `List`
pairs `(1 . 2)`, `(x y z)`	`class Cell (List)`
closures `(lambda (x) (+ x 1))`	`class Closure`
built-in procedures `car`, `cdr`	`class Intrinsic`

Continuations are represented by Python tuples of the form (operation, value, next continuation) and will be passed by call/cc to its argument.
Python's native string type str has intern function. It is reasonable to use it as Scheme's symbol type.

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)	(`display` x)	(`+` n1 n2)
(`cdr` lst)	(`newline`)	(`-` n1 n2)
(`cons` x y)	(`read`)	(`*` n1 n2)
(`eq?` x y)	(`eof-object?` x)	(`<` n1 n2)
(`pair?` x)	(`symbol?` x)	(`=` n1 n2)
(`null?` x)	(`call/cc` fun)	(`number?` x)
(`not` x)	(`apply` fun arg)	(`globals`)
(`list` x ...)	(`error` reason arg)

(error reason arg) raises an exception 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 GLOBAL_ENV in scm.py for the implementation of the procedures except call/cc and apply.
call/cc and apply are implemented particularly at apply_function in scm.py.

I hope this serves as a popular model of how to write a Scheme interpreter in Python.