pyscheme --- Scheme in Python

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


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/
Welcome to PyScheme!  Type: (QUIT) to quit.

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

;; 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)

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


News and Ramblings


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


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*


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.

PyScheme Implementation Details

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)))))
[PyScheme] >>> (factorial 5000)
068544587848606668381273633721089377278763127939036305... [cut]
won't break the system, even though there are no tail calls here.

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.