Scheme Interpreter in Rust

This project implements a lexer, parser, and an evaluator for a minimal subset of Scheme. It is written from scratch in Rust.

Check out the companion blog post, Building a minimal Scheme Interpreter in Rust, for a guided walkthrough of the code.

Main Features

• Lexer: Breaks up input string (source code) into a sequence of tokens.
• Parser: Parses Scheme expressions into an abstract syntax tree (AST).
• Evaluator: Evaluates expressions according to Scheme semantic rules.
• Environment handling: Manages variable scope and function definitions.

• Numbers: Supports 64-bit integer and floating point numbers, with 'pi' being defined in the standard environment.
• Arithmetic operations: Supports basic arithmetic operations (+, -, *, /).
• Comparison operations: Supports comparison operators (>, <, =, >=, <=).
• Variable definitions: Allows user-defined variables.
• Function definitions: Allows user-defined functions with support for recursion.
• Conditional expressions: Supports the evaluation of 'if' expressions.
• REPL: A Read-Eval-Print Loop for interactive programming.

Example Usage

You can start the REPL by running the following in your shell:

$ cargo run

In the REPL, you can enter Scheme expressions and evaluate them. Here are some examples:

schemer>
(+ 2 2)
 ==> 4
schemer>
(+ 2 2 3)
 ==> 7
schemer>
(- 4 2)
 ==> 2
schemer>
(+ 10 5 (- 10 3 3))
 ==> 19
schemer>
(* x 2)
 ==> 10
schemer>
(pow 2 16)
 ==> 65536
schemer>
(define r 10)
 ==> r
schemer>
(* pi (* r r))
 ==> 314.1592653589793
schemer>
(>= 4 2)
 ==> true
schemer>
(if (> 2 4 ) 1 2)
 ==> 2
schemer>
(define (sum a b) (+ a b))
 ==> sum
schemer>
(sum 10 20)
 ==> 30
schemer>
(define (square x) (* x x))
 ==> square
schemer>
(square 5)
 ==> 25
schemer>
(define (circle-area r) (* pi (* r r)))
 ==> circle-area
schemer>
(circle-area 3)
 ==> 28.274333882308138
schemer>
(define (fact n) (if (<= n 1) 1 (* n (fact (- n 1)))))
 ==> fact
schemer>
(fact 10)
 ==> 3628800
schemer>
(define (cube x) (define (square x) (* x x)) (* x (square x)))
 ==> cube
schemer>
(cube 3)
 ==> 27

Tests

To run all the tests for the project use:

$ cargo test