Scheme in Python

The Scheme in Python series has been completed! Since there are still a few readers of this blog and I haven’t yet setup domain forwarding, I’ll post the links page here.


The Scheme in Python project is a port of the Scheme in Scheme project. The goal is to implement a small subset of Scheme as an interpreter written in Python.

There are a number of goals for this project. First, implementing Scheme in Scheme allowed us to “cheat” a bit by having access to the Scheme reader and data structures. Using Python as the implementation language will force us to code the reader by hand and create new data structures where there isn’t a one-to-one mapping from Scheme to Python.

There are also two auxiliary goals to this project. Using Python should make this more accessible to programmers who are interested in language development, but are unfamiliar with Scheme. Also I’m using this project as a way to familiarize myself with branching and merging in git, so each post will correspond to a branch in the repository.

All the code for this project will be hosted on GitHub. The code is licensed under a BSD license if you are interested in forking it for any reason.

This series will focus on building a very simple interpreter for the purpose of learning the steps involved in building one. For this reason there will be no/very little error checking or optimization. This port will be slightly more complicated than Scheme in Scheme so if you are interested in an even simpler interpreter look here.

Part 0 | Reading from stdin

Part 1 | Numbers

Part 2 | Extending the read layer

Part 3 | Pairs and linked lists

Part 4 | Self-evaluating values

Part 5 | Assignment and define

Part 6 | scheme-syntax macro

Part 7 | Refactor and load

Part 8 | Primitive procedures and apply

Part 9 | Environments

Part 10 | lambda

* Most implementations of Scheme in Python use regular expressions in the reader. I chose to write a parser by hand so I could explain some of the details of parsing. As this is an educational exercise I think this is appropriate.

Other resources for writing a Scheme in Python

lis.py and lispy.py
Simple Schemes written by Peter Norvig.

Psyche
pyscheme
I haven’t got the chance to look at Psyche or pyscheme, but you may be interested in them as well.

Other resources for writing a Scheme in Scheme or other languages

Structure and Interpretation of Computer Programs
Chapter 4 onward covers designing and implementing a number of interpreters and was the inspiration for this interpreter.

An Incremental Approach to Compiler Construction (PDF)
Great paper on building a Scheme compiler from the ground up. Each step is simple and results in a fully working compiler.

Scheme from Scratch
The blog series that inspired and guided the development of the original Lispy. Even if you don’t know C (I didn’t at the time) you will still be able to follow along and construct your own Scheme. Peter’s coding style is easy and pleasant to read and he mentions tips for going in different directions for your own implementations.

A Self-Hosting Evaluator using HOAS (PDF)
An interesting implementation of Scheme using a Higher-Order Abstract Syntax representation. This paper, An Incremental Approach to Compiler Construction and SICP were the primary motivating forces behind my interest in PL design and implementation. The author, Eli Barzilay, has many other interesting papers at his site.

Chai – Math ∩ Programming
A series detailing the development of Chai (what appears to be a Scheme-like language). It is well written and currently in development. I’ll post more information when it’s available.

Scheme in Scheme
Another series that is just beginning about writing a bytecode interpreter. It appears to be put on hold as of April 2011.

Lisp in Scheme
An implementation of McCarthy’s original Lisp in Scheme.

Offline

Lisp in Small Pieces
Great book. Contains code for 11 interpreters and 2 compilers. Source code from the book available here.

Introducing Evo: The Original Purpose of Lispy

When I first envisioned the Lispy project I had only one goal in mind, which I’ll get to soon. As I started writing code, first in Scheme, then C then again in Scheme, the Lispy project evolved into something else. It changed into a platform for me to learn more about programming and the implementation of language features. Writing Lispy, in all its variations, has been a very educational and rewarding experience, so much so that I consider the project an overwhelming success, even though I didn’t realize the original purpose.

So what was the original purpose of Lispy? I’ll give you the tag line that I wrote when Lispy was nothing but an idea… Lispy is a distributed self-optimizing program by example language.

What does that mean? When I first became interested in programming I had 2 goals; to create a program like MetaStock (I’ve since written pyTrade) and to create Artificial Intelligence. Modest goals, I know. In my AI research I came across genetic programming and immediately took a liking to it, probably because I was still new to writing code and the idea that I could write code that wrote code fascinated me.

The main problem with genetic programming is that it is often difficult to write fitness tests for your problems. Somewhere along the way I noticed that programmers were writing fitness tests all the time in the form of unit tests for their code. In addition, the fact that 99% of the time the CPU sits idle while we browse reddit, kept rattling around in my head. Why not take advantage of those wasted cycles by using a programming language that used those cycles to optimize the code you just wrote?

Then I had another idea. Why write code at all? Why not just write the unit tests and let the code evolve on its own? It took me about an hour to realize that this wasn’t going to work on anything but the smallest applications. However another few weeks and I realized that, maybe it could work, given enough computers were running Lispy.

Anyway I have about 25 half-finished papers on Evo which I might get around to finishing and posting here. I’ll give the highlights and post a link to the github account where you can find more info. Evo is meant to be integrated with Lispy (though I don’t know when I’ll get around to that).

Evo is an evolutionary search based function optimizer. It provides an interface for defining new modules and functions as well as an evolutionary programming based method for optimizing those functions. Evo does not use the standard generational approach to GP, rather it uses “gene pools”, that contain functions of indefinite life, from which new functions can be evolved and tested one at a time.

When defining an Evo function you can choose to optimize it for speed, space or code length. Each function can have multiple gene pools that are each optimized for a different purpose. Using gene pools instead of a single population generational approach helps to avoid stagnation within the population as is a common occurrence with the standard generational model.

Evo is very much unfinished, however it can successfully run on its own and evolve solutions to problems. Because of this I am going to put the code out there in case anyone wishes to contribute. I used the implementation of Evo as an excuse to firm up my understanding of closures, as a result the majority of the program is written in a slightly OOP fashion. There is also a Tk based GUI for browsing modules and adding new functions and fitness tests, though its use is completely optional.

Without further ado, here’s the link to the Evo repo.

Scheme in Lispy

Now that we have our basic interpreter set up, it’s time to start writing some languages. Before we start experimenting with Lispy, we will implement a small subset of Scheme.

Implementing Scheme will let us test our implementation with a language that is already specified.

Create a new file, I’ll call it scheme_in_lispy.lispy, but you can name it whatever you like. We’ll be doing most of our work here so I’ll leave out the main lispy file.

We’ll start with define-primitive which we’ll simply copy from the old syntax.chicken, though we won’t use it until later.

(scheme-syntax define-primitive
  (lambda (expr env)
    (set-symbol! (car expr)
                 (make-primitive (eval (cadr expr)))
                 env)))

The first primitive form we’ll introduce is define. For this we’re going to do a little more copy and paste. Scheme’s define form is just a combination of our previous define and function. define sets a value to a symbol, but it also provides a shorthand for setting a lambda to a symbol (define (a x) x) is equivalent to (define a (lambda (x) x)). To figure out which one we need to produce, we only have to look at the first value in expr. If it is a symbol we just set the symbol name to the evaluated value. If it is a list we create a proc and set that as the value to symbol.

(scheme-syntax define
  (lambda (expr env)
    (if (list? (car expr))
        (set-symbol! (caar expr)
                     (make-proc (cdar expr)
                                (cdr expr)
                                env) env)
        (set-symbol! (car expr) (lispy-eval (cadr expr) env) env))))
(define a 42)
;===> #<unspecified>
a
;===> 42
(define (b x) x)
;===> #<unspecified>
(b 42)
;===> 42

lambda is simple after that. All we have to do is rip out the (make-proc …) procedure and drop it into lambda with one small change. With define we received a procedure definition as ((name arg-1 arg-2 arg-n) body), however an anonymous function does not have a name. We receive a lambda definition as ((arg-1 arg-2 arg-n) body).

(scheme-syntax lamb
  (lambda (expr env)
    (make-proc (car expr)
               (cdr expr)
               env)))
(define c (lambda (x) x))
;===> #<unspecified>
(c 42)
;===> 42
((lambda (y) y) 42)
;===> 42

if is a straight copy/paste from our old syntax file.

(scheme-syntax if
  (lambda (expr env)
    (if (lispy-eval (car expr) env)
        (lispy-eval (cadr expr) env)
        (lispy-eval (caddr expr) env))))
(if 1 2 3)
;===> 2
(if #f 2 3)
;===> 3

quote is one of the simplest forms in Scheme. All quote does is return its argument unevaluated.

(scheme-syntax quote
  (lambda (expr env)
    (car expr)))
(quote (+ 1 2))
;===> (+ 1 2)

set! is pretty simple too, it’s basically just a limited form of define.

(scheme-syntax set!
  (lambda (expr env)
    (set-symbol! (car expr) (lispy-eval (cadr expr) env) env)))
(set! a 42)
;===> #<unspecified>
a
;===> 42
(set! b (if #f 2 3))
;===> #<unspecified>
b
;===> 3
(set! c (lambda (x) x))
;===> #<unspecified>
(c 42)
;===> 42

begin is pretty straightforward, in fact we have already implemented it as eval-body (we used it for procedures).

(scheme-syntax begin
  (lambda (expr env)
    (eval-body expr env)))
(begin 1 2 3)
;===> 3
(begin (define x 42) x)
;===> 42

let is almost the same as begin, except we have to extend the environment with the given bindings before we evaluate the body of the let. This version uses cons cells instead of 2 element lists to set symbols. You could add support for (let ((x 35) (y 7)) …) if you like. Since making a Scheme is not my goal, I will not do that now.

(scheme-syntax let
  (lambda (expr env)
    (eval-body (cdr expr) (extend-environment (car expr) env))))
(let ((x . 35) (y . 7)) (if x x y))
;===> 35
x
;===> Error: Unbound symbol: x

equal? is easily snarfed from the underlying Scheme. equal? could also be defined using define-primitive (define-primitive equal? equal?).

(scheme-syntax equal?
  (lambda (expr env)
    (equal? (lispy-eval (car expr) env)
            (lispy-eval (cadr expr) env))))
(equal? 2 2)
;===> #t
(equal? 2 (if 1 2 3))
;===> #t
(equal? 1 2)
;===> #f

Finally we’ll snarf some primitives from the underlying Scheme to make our mini-Scheme a little more usable.

(define-primitive + +)
(define-primitive - -)
(define-primitive < <)
(define-primitive > >)
(define-primitive car car)
(define-primitive cdr cdr)
(define-primitive cons cons)
(define-primitive print print)
(+ 1 2)
;===> 3
(- 3 2)
;===> 1
(< 1 2)
;===> #t
(> 1 2)
;===> #f
(cons 1 2)
;===> (1 . 2)
(car (cons 1 2))
;===> 1
(cdr (cons 1 2))
;===> 2
(define (loop x) (if (< x 0) (print 'finished) (begin (print x) (loop (- x 1)))))
;===> #<unspecified>
(loop 3)
3
2
1
0
finished
;===> #<unspecified>

There is a lot that is left out, error handling and advanced features like call-with-current-continuation or macros, for example. But for a simple Scheme to help test the implementation of our interpreter this is just about all we need.

Most of the rest of Scheme can be implemented as derived forms from the primitives we just defined. What cannot be, can be implemented using our scheme-syntax macro.

Finally, here’s the full source of scheme_in_lispy.lispy for you to play with.

(scheme-syntax define-primitive
  (lambda (expr env)
    (set-symbol! (car expr)
                 (make-primitive (eval (cadr expr)))
                 env)))

(scheme-syntax define
  (lambda (expr env)
    (if (list? (car expr))
        (set-symbol! (caar expr)
                     (make-proc (cdar expr)
                                (cdr expr)
                                env) env)
        (set-symbol! (car expr) (lispy-eval (cadr expr) env) env))))

(scheme-syntax lambda
  (lambda (expr env)
    (make-proc (car expr)
               (cdr expr)
               env)))

(scheme-syntax if
  (lambda (expr env)
    (if (lispy-eval (car expr) env)
        (lispy-eval (cadr expr) env)
        (lispy-eval (caddr expr) env))))

(scheme-syntax quote
  (lambda (expr env)
    (car expr)))

(scheme-syntax set!
  (lambda (expr env)
    (set-symbol! (car expr) (lispy-eval (cadr expr) env) env)))

(scheme-syntax begin
  (lambda (expr env)
    (eval-body expr env)))

(scheme-syntax let
  (lambda (expr env)
    (eval-body (cdr expr) (extend-environment (car expr) env))))

(scheme-syntax equal?
  (lambda (expr env)
    (equal? (lispy-eval (car expr) env)
            (lispy-eval (cadr expr) env))))

(define-primitive + +)
(define-primitive - -)
(define-primitive < <)
(define-primitive > >)
(define-primitive car car)
(define-primitive cdr cdr)
(define-primitive cons cons)
(define-primitive print print)

GOTO Table of Contents