/little-scheme-in-cs

A Scheme interpreter with first-class continuations in circa 900 lines of C# 8

Primary LanguageC#MIT LicenseMIT

A Little Scheme in C#

This is a small interpreter of a subset of Scheme in circa 900 lines of C# 8 (including a small arithmetic library arith.cs in circa 200 lines). 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.

How to run

With Mono 6.12.0:

$ csc -o -r:System.Numerics.dll arith.cs scm.cs
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

$ mono scm.exe
> (+ 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
$

With .NET 6.0.9:

$ dotnet build -c Release
MSBuild version 17.3.1+2badb37d1 for .NET
  Determining projects to restore...
  Restored /Users/suzuki/proj/little-scheme-in-cs/scm.csproj (in 38 ms).
  scm -> /Users/suzuki/proj/little-scheme-in-cs/bin/Release/net6.0/scm.dll

Build succeeded.
    0 Warning(s)
    0 Error(s)

Time Elapsed 00:00:00.65
$ ./bin/Release/net6.0/scm
> (+ 5 6)
11
>

And so on.

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...
$ mono scm.exe ../little-scheme/examples/yin-yang-puzzle.scm | head

*
**
***
****
*****
******
*******
********
*********
^C
$ mono scm.exe ../little-scheme/examples/amb.scm
((1 A) (1 B) (1 C) (2 A) (2 B) (2 C) (3 A) (3 B) (3 C))
$ mono scm.exe ../little-scheme/examples/dynamic-wind-example.scm 
(connect talk1 disconnect connect talk2 disconnect)
$ mono scm.exe ../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))
$ mono scm.exe ../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.

$ mono scm.exe ../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

Scheme Expression Internal Representation
numbers 1, 2.3 int, double or BigInteger
#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

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

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) throws 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 GlobalEnv in scm.cs for the implementation of the procedures except call/cc and apply.
call/cc and apply are implemented particularly at ApplyFunction in scm.cs.

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