Scheme Interpreter Written in Python

Introduction:

Python 3 based interpreter for the Scheme programming language. Scheme is a simple but powerful functional programming language. It is statically scoped and a properly tail recursive dialect of the Lisp programming language¹. The supported Scheme scope of this interpreter closely resembles the R5RS version of Scheme but does not completely follow defined functionality.

Implementation:

Interpreting expressions required evaluation of terms like nil and simple types like numbers and strings to then print them back to the user. The next step is to evaluate expressions like (+ 2 2). In Scheme, simple expressions have the following form (operator operand1 operand2). The idea is to parse operator and operands between matching sets of parentheses. What about more complex/nested expressions like (+ (* 2 2) 2)? In order to parse nested expressions, recursion is applied to matching parentheses until we complete the evaluation.

Other features like conditionals (e.g. (and [test 1] [test 2] ...)) were then implemented to further support complex functions along with operands which support multiple statements (e.g. (begin (statement 1) (statement 2))).

Finally lambdas and named lambdas (i.e. functions) were implemented to support looping — remember that Scheme does not have loop functionality — using recursion in combination with the above expressions and operands to create a flexible functional language.

Try this:

Basics:

Python 3	Scheme
x = 7	(define x 7)
y = x + 3	(define y (+ x 3))
"return this" if y > 1 else "we will not return this"	(if (> y 1) "return this" "we will not return this")

Fibonacci number:

Let’s generate the Fibonacci sequence² up to x:

$ (define (fib x) (if (<= x 2) 1 (+ (fib (- x 1)) (fib (- x 2)))))
$ (define (runfib x) (if (<= x 0) 0 (begin (print (fib x)) (runfib (- x 1))))) 

Create a list:

$ (define list_x (cons “string 1” (cons “string 2” nil)))
$ list_x
$ (“string 1” “string 2”)

References:

1. R5RS Scheme Summary [Web Page]. https://schemers.org/Documents/Standards/R5RS/HTML/
2. Multiple Editors (2021). Fibonacci number. Wikipedia. https://en.wikipedia.org/wiki/Fibonacci_number