pyscheme --- Scheme in Python

[Releases] [News] [Notes] [Download pyscheme-1.6.tar.gz] [LICENSE] [README] [CHANGES]

Introduction

pyscheme is an implementation of the Scheme language in Python. This interpreter tries to follow the design of the metacircular evaluator in the classic textbook, The Structure and Interpretation of Computer Programs. This implementation supports only a limited subset of Scheme, and my hope is to get it good enough so that it can support the register-machine simulator in SICP. And since most of this stuff is derived from material in SICP, it seems appropriate to license PyScheme under the MIT license.

Scheme is a very minimal language, which little syntax to get in the way of actually programming things. In this sense, I think it shares much of the feeling of Python programming. Here's an example session with pyscheme:

$ python pyscheme/scheme.py
Welcome to PyScheme!  Type: (QUIT) to quit.

[PyScheme] >>> (define (factorial x)
[......1)] >>>    (if (= x 0)  
[......2)] >>>        1
[......2)] >>>        (* x (factorial (- x 1)))))
OK
[PyScheme] >>> (factorial 5)
120
[PyScheme] >>> (define (map f l)
[......1)] >>>    (cond ((null? l) '())
[......2)] >>>          (else (cons (f (car l))             
[......4)] >>>                      (map f (cdr l))))))
OK
[PyScheme] >>> (map factorial '(1 2 3 4 5 6))
[1, 2, 6, 24, 120, 720]
[PyScheme] >>> (define foo 'unquote)
OK
[PyScheme] >>> '(hey look I support ,foo)
['HEY', 'LOOK', 'I', 'SUPPORT', 'UNQUOTE']


;; PyScheme 1.0 stuff:
[PyScheme] >>>  ((lambda (x) (list x (list (quote quote) x))) 
[......1)] >>>   (quote (lambda (x) (list x (list (quote quote) x)))))
((lambda (x) (list x (list (quote quote) x))) (quote (lambda (x) (list x (list (quote quote) x)))))
[PyScheme] >>> (append '(1 2 3) (list 4 5 '(6)) 7)
(1 2 3 4 5 (6) . 7)
[PyScheme] >>> (quit)
bye

There are a few oddities and bugs with the code that are commented in scheme.py. I certainly don't mean for this to be useful or anything! *grin* Still, I hope that someone gets a kick out of it.

• pyscheme-1.6.tar.gz September 18, 2004: too many things to list here. I've summarized the changes here: [CHANGES]
• pyscheme-1.51.tar.gz September 8, 2004: added MIT license entries. Also modified __init__.py to make importing a little more pleasant.
• pyscheme-1.5.tar.gz September 7, 2004: lots of extensive changes to the interpreter, and a lot of bug fixes. CALL/CC and tail recursion elimination are in. Furthermore, the interpreter itself should only consume a constant amount of stack space. See notes below for details.
• pyscheme-1.0.tar.gz January 23, 2002: Hey, we have honest-to-goodness pairs! Thanks to Seth David Schoen for a patch to allow (cons 1 2) to work. Also, the set-car! and set-cdr! functions finally work. Another radical change underneath the surface is the implementation of environment frames using Python dictionaries.
• pyscheme-0.6.tar.gz January 2, 2002: Fixed the display of Scheme expressions so they don't look like Python lists. (Suggested by Seth David Schoen)
• pyscheme-0.5.tar.gz January 1, 2002: The New Year's release! This supports quite a bit of Scheme, including LET and UNQUOTE.
• pyscheme-0.01.tar.gz Really buggy code. I wouldn't look at it.

Just polished off Release 1.6. I've also moved my development off of my laptop onto a Subversion repository. Subversion is so nice!

2004/09/08

I have just found a few more "Lisp in Python" implementations on the web. I'll try to catalog them here, and then perhaps I can steal some features from them when I have more time.

There's a Lisp implementation by William Annis called PyLisp. I'm sorry I missed the comp.lang.python thread about it. Chris Meyers has written a Lisp as part of his Python for Fun book. Miles Egan has written lython, which looks very interesting because it compiles Lisp down to Python bytecode.

So there are obviously a lot of deranged people out there. *grin*

2004/08/29

Hey, I've been cited! The Psyche project appears to be another Scheme implementation in Python. His code actually looks a LOT cleaner than mine, and Yigal Duppen has written good documentation. This is something I need to work on.

It's been about two years since I revisited the code. But I've added continuations and tail-call elimination to my latest sources! I do have to fix a few embarassing bugs, and as soon as I polish up a few more things, I'll make a formal release. Now that I'm starting to understand EOPL, I'm psyched to make pyscheme a little bit more functional.

There are a few significant changes I've made to pyscheme. The main interpreter is now written in continuation passing style (CPS), which allows me to implement call/cc.

I've also tried to make sure that the evaluation of a program doesn't grow control context. CPS is one part of that, and the other is the use of a technique called trampolined style. So even evil expressions like:

[PyScheme] >>> (define (factorial x)
[......1)] >>>   (if (= x 0) 1 (* x (factorial (- x 1)))))
ok
[PyScheme] >>> (factorial 5000)
422857792660554352220106420023358440539078667462664674884
978240218135805270810820069089904787170638753708474665730
068544587848606668381273633721089377278763127939036305... [cut]

I made a presentation at the last Bay Area Python Users Group meeting with notes on how PyScheme is implemented. I'll try to put some CPS tutorial up there too to make the topic more approachable.

Back to python.