little-scheme-in-go

A Little Scheme in Go

This is a small interpreter of a subset of Scheme. It implements almost the same language as

• little-scheme-in-crystal
• little-scheme-in-cs
• little-scheme-in-dart
• little-scheme-in-java
• little-scheme-in-kotlin
• little-scheme-in-lisp
• little-scheme-in-php
• little-scheme-in-python
• little-scheme-in-ruby
• little-scheme-in-typescript

and also their meta-circular interpreter, little-scheme in 760 lines of Go 1.14 (and it uses an arithmetic package, goarith, which has 604 lines of Go; it has 1364 lines of Go in total).

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

How to run

$ go build
go: downloading github.com/nukata/goarith v0.3.0
$ ./little-scheme-in-go
> (+ 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.

> Goodbye
$ 

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

$ cat ../little-scheme/examples/yin-yang-puzzle.scm
;; The yin-yang puzzle 
;; cf. https://en.wikipedia.org/wiki/Call-with-current-continuation

((lambda (yin)
   ((lambda (yang)
      (yin yang))
    ((lambda (cc)
       (display '*)
       cc)
     (call/cc (lambda (c) c)))))
 ((lambda (cc)
    (newline)
    cc)
  (call/cc (lambda (c) c))))

;; => \n*\n**\n***\n****\n*****\n******\n...
$ ./little-scheme-in-go ../little-scheme/examples/yin-yang-puzzle.scm | head

*
**
***
****
*****
******
*******
********
*********
$ ./little-scheme-in-go ../little-scheme/scm.scm < ../little-scheme/examples/nqu
eens.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))
$ 

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

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

The implemented language

• Symbol is defined as type Symbol string and its values will be interned with sync.Map.

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

• (error reason arg) panics with an ErrorString "Error: reason: arg". The type ErrorString is defined as type ErrorString string. The procedure error is based on SRFI-23.

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

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

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