A simple and fun Scheme interpreter written in C++ (C++11).

Scheme is a simple but powerful functional language first developed in the 1990s at MIT.

I've enjoyed reading Peter Norvig's blog (How to Write a (Lisp) Interpreter (in Python)), in which he writes a Scheme interpreter in 90+ lines of Python. The C++ implementation is a bit more challenging and I thought I'd give it a try.

UC Berkley's CS61A: Structure and Interpretation of Computer Programs has also been very helpful.

The interpreter is divided into 2 parts.

1. Parsing (Lexical Analysis)
  - Read input program
  - Break program into tokens
  - Analysis of tokens according our Abstract Syntax Tree
2. Evaluation & Execution 
  - Tokens are processed according to the semantics of Scheme
  - Carry out the computation

Storing Scheme Expressions

• Scheme objects - defined in SList.cpp
• Environment - stored as STL unordered_map

Overview of internal processes

Program => Parse => Abstract Syntax Tree => eval => result

Simple Demo Program

(define square (lambda (x) (* x x))
=> LAMBDA
(define pi 3.1416)
=> 3.141600
(if (> pi (square (pi))) (square (pi)) else (sin (sqrt (square (pi)))))
=> -0.000007

GNU g++ -std=c++11

To clone this repo to your local machine:

$ git clone
$ cd SchemePlusPlus

Compile and Link:

$ make build

Run:

$ ./scheme

Clean:

$ make clean

quote, '
if ... else ...
define
set!
lambda
+, -, *, /, >, <, >=, <=
=, eqv?
abs
append
apply
begin
car
cdr
cons
length
list
list?
map
max
min
null?
number?
procedure?
symbol?
mod
sqrt
sin
cos
tan
asin
acos
atan

• FormattedIO.cpp: reading input from stdin
• Parser.cpp: lexical analysis
• SList.cpp: stores any scheme expression
• NativeProcedures.cpp: defines the standard Scheme procedures
• Environment.cpp: execution environement, can be nested
• Main.cpp: REPL

Feel free to contribute and/or create new issues

I use SemVer for versioning. For the versions available, see the tags on this repository.

• Joshua Sun - github

See also the list of contributors who participated in this project.

This project is licensed under the MIT License - see the LICENSE file for details

• Peter Norvig, Director of Research, Google Inc.