HourOfCode++? Checkout: http://jupyter.cs.brynmawr.edu/hub/dblank/public/HourOfCodePlusPlus.ipynb

# Implementing Scheme in Python¶

## Complete with Continuations, Nondeterminsitic search, and No Stack Limits¶

This notebook is a summary of the explorations in CS245: Programming Languages at Bryn Mawr College Department of Computer Science, by Douglas Blank. If you have questions or comments, please use the comments at the bottom of this notebook.

This notebook describes the basic techniques of implementing Scheme in Python in Continuation-Passing Style (CPS), and call-with-current-continuation. A more rich implementation of Scheme-in-Python is Calysto Scheme. You can read some documention about it here, and see a debugging video here.

Goal: explore implementing the core of a real Scheme in Python in 50 cells.

First, we need to write some parsing code so that Python will be able to read Scheme's symbolic expressions, also called "s-expressions".

We start at the lowest level, taking a string and return a list of strings broken up based on white space and brackets.

In :
from __future__ import print_function

def lexer(string):
retval = []
current = ""
for i in range(len(string)):
if string[i] in ["(", "[", ")", "]"]:
if current:
retval.append(current)
current = ""
retval.append(string[i])
elif string[i] in [" ", "\t", "\n"]:
if current:
retval.append(current)
current = ""
else:
current += string[i]
if current:
retval.append(current)
return retval

In :
lexer("(this is a (test) of 1 [thing])")

Out:
['(', 'this', 'is', 'a', '(', 'test', ')', 'of', '1', '[', 'thing', ']', ')']

The output of lexer is just a list of parts. We now pass that to reader which will create lists, and turn strings of numbers into actual numbers:

In :
def reader(lexp):
current = None
stack = []
for item in lexp:
if item.isdigit():
if current is not None:
current.append(eval(item))
else:
current = eval(item)
elif item in ["[", "("]:
if current is not None:
stack.append(current)
current = []
elif item in ["]", ")"]:
if stack:
stack[-1].append(current)
current = stack.pop(-1)
else:
pass
else:
if current is not None:
current.append(item)
else:
current = item
return current

In :
reader(lexer("(this is a (test) of 1 or 2 [things])"))

Out:
['this', 'is', 'a', ['test'], 'of', 1, 'or', 2, ['things']]

If we wanted, we could also parse quoted strings and floating-point numbers in reader. We'll add those later.

Now, we are ready to construct s-expressions. Our goal is to feed the output of reader into parser, and have the parser create Abstract Syntax Tree.

First, we define in Python all of the functions and classes that we will need to process s-expressions, including: car, cdr, and cons:

In :
class Symbol(str):
"Class to define symbols, which should be unique items"
def __repr__(self):
return str.__repr__(self)[1:-1] # don't show quotation marks

EmptyList = Symbol("()")
void = Symbol("<void>")

class Cons(object):
def __init__(self, car, cdr):
self.car = car
self.cdr = cdr
def __repr__(self):
if self.car == "closure-exp":
return "#<procedure>"
retval = ""
current = self
while current is not EmptyList and isinstance(current, Cons):
if retval != "":
retval += " "
retval += str(current.car) # recursion here!
current = current.cdr
if current is not EmptyList:
retval += " . " + str(current)
return "(%s)" % retval

class String(str):
"Class to wrap strings so that we can define repr"
def __repr__(self):
return '"%s"' % str.__repr__(self)[1:-1]
def __str__(self):
return self.__repr__()

def List(*args):
retval = EmptyList
for arg in reversed(args):
retval = cons(arg, retval)
return retval

def car(exp):
return exp.car
return exp.cdr.car
return exp.cdr.cdr.car
return exp.cdr.cdr.cdr.car

def cdr(exp):
return exp.cdr
def cddr(exp):
return exp.cdr.cdr
def cdddr(exp):
return exp.cdr.cdr.cdr
def cddddr(exp):
return exp.cdr.cdr.cdr.cdr

def cons(item1, item2):
return Cons(item1, item2)

def length(item, handler):
current = item
count = 0
while current is not EmptyList and isinstance(current, Cons):
current = current.cdr
count += 1
if current is not EmptyList:
return handler("Attempt to take length of improper list")
return count

def rac(item):
current = item
previous = None
while current is not EmptyList:
previous = current.car
current = current.cdr
return previous

## We use "_q" in Python to represent "?" in Scheme.

def pair_q(item):
return isinstance(item, Cons)

def null_q(lst):
return lst is EmptyList


Note that we create classes for Symbols and Cons cells. We use the Symbol class to both make unique items, and to be able to represent Symbols as we wish. We use the Cons class to create linked-lists made of cons cells, and to be able to format these as Scheme lists.

Now, we construct a set of tagged-lists so that the parser can identify each of the "special forms".

In :
def lit_exp(value):
return List("lit-exp", value)

def if_exp(test_exp, then_exp, else_exp):
return List("if-exp", test_exp, then_exp, else_exp)

def let_exp(variables, values, body):
return List("let-exp", variables, values, body)

def var_exp(symbol):
return List("var-exp", symbol)

def assign_exp(symbol, value):
return List("assign-exp", symbol, value)

def define_exp(symbol, value):
return List("define-exp", symbol, value)

def app_exp(f, args):
return List("app-exp", f, args)

def procedure_exp(variables, body):
return List("procedure-exp", variables, body)

def closure_exp(env, variables, body):
return List("closure-exp", env, variables, body)

def begin_exp(exps):
return List("begin-exp", exps)

## and a utility function for defining closure?:
def closure_q(item):
return pair_q(item) and car(item) == "closure-exp"


And now the parser:

In :
def sexp(item):
"""
Takes an Python list of items and returns Scheme s-exp.
"""
if isinstance(item, list):
return List(*map(sexp, item)) # recursion!
else:
return item

def parser(pyexp):
"""
Reads in a Python list of things, and returns a sexp.
Uses Python stack for recursion.
"""
if isinstance(pyexp, int):
return lit_exp(pyexp)
elif isinstance(pyexp, str):
return var_exp(pyexp)
elif pyexp == "quote":
return lit_exp(sexp(pyexp))
elif pyexp == "set!":
return assign_exp(pyexp, parser(pyexp))
elif pyexp == "define":
return define_exp(pyexp, parser(pyexp))
elif pyexp == "begin":
return begin_exp(List(*map(parser, pyexp[1:])))
elif pyexp == "if":
if len(pyexp) == 3:
return if_exp(parser(pyexp), parser(pyexp), lit_exp(EmptyList))
else:
return if_exp(parser(pyexp), parser(pyexp), parser(pyexp))
elif pyexp == "let":
return let_exp(List(*[pair for pair in pyexp]),
List(*map(parser, [pair for pair in pyexp])),
parser(pyexp))
elif pyexp == "lambda":
return procedure_exp(List(*pyexp), parser(pyexp))
else:
return app_exp(parser(pyexp), List(*map(parser, pyexp[1:])))


The parser is so short! That is mostly because of Scheme's prefix notation.

Let's try parsing a few expressions:

In :
parser(reader(lexer("(let ((x 1)(y 2)) x)")))

Out:
(let-exp (x y) ((lit-exp 1) (lit-exp 2)) (var-exp x))

Now, let's add the pieces necessary to build an interpreter.

We need to be able to represent boolean values. For now, we will use 0 to represent #f (False). Anything else is #t (True). Note that this is different from Python's idea of true/false. For example, in Python [] and (,) are considered false.

In :
def true_q(value):
if value == 0:
return False
else:
return True


An environment will be a Python list of [variable, value] pairs. Later we can add Lexial Address to make lookup O(1).

When we extend an environment (when we evaluate a let or lambda) we will make a new "frame"... a list of variable/value pairs append onto the front of an existing environment:

In :
def list_to_vector(lst):
retval = []
current = lst
while current is not EmptyList:
retval.append(current.car)
current = current.cdr
return retval

def extend_env(vars, vals, env):
return [map(list,zip(list_to_vector(vars),
list_to_vector(vals))), env]


When we look up a variable, we will actually return the [variable, value] pair (or return False):

In :
def lookup_binding(symbol, env, first_frame_only=False):
frame = env
for pair in frame:
if pair == symbol:
return pair
if not first_frame_only and len(env) > 1:
return lookup_binding(symbol, env)
else:
return False


And now we are ready to define the interpreter.

We write the interpreter, here called evaluator, in Continuation Passing Style, or CPS. This version is still recursive, but this won't have any impact on our Scheme recursive programs. Our Scheme functions won't use Python's stack---eventually.

First, we wrote the evaluator in regular form. Then we converted it to CPS. Note that:

1. We use a third and fourth parameter to evaluator (handler and k) that represent the error and computation continuations, respectively
2. We use Python functions (closures) to represent continuations
3. We pass results to the continuation via apply_cont
4. Any place where there is still computation to be done, we construct a new continuation using Python's lambda

To see more examples of converting Python code into Continuation Passing Style, see:

In :
def evaluator(exp, env, handler, k):
if car(exp) == "lit-exp":
elif car(exp) == "var-exp":
elif car(exp) == "let-exp":
extend_env(variables, values, env), handler, k))
elif car(exp) == "if-exp":
lambda value: eval_if_cont(value, exp, env, handler, k))
elif car(exp) == "assign-exp":
lambda value: eval_assign_cont(value, variable, env, handler, k))
elif car(exp) == "define-exp":
lambda value: eval_define_cont(value, variable, env, handler, k))
elif car(exp) == "procedure-exp":
elif car(exp) == "app-exp":
lambda all: eval_apply_cont(v, all, env, handler, k)))
elif car(exp) == "begin-exp":
lambda all: apply_cont(k, rac(all)))
else:
return handler("invalid abstract syntax: %s" % exp)

def eval_assign_cont(value, variable, env, handler, k):
binding = lookup_binding(variable, env)
if binding:
binding = value
else:
return handler("No such variable: '%s'" % variable)
return apply_cont(k, value)

def eval_define_cont(value, variable, env, handler, k):
binding = lookup_binding(variable, env, True)
if binding:
binding = value
else:
env.append([variable, value])
return apply_cont(k, None)

def eval_if_cont(value, exp, env, handler, k):
if true_q(value):
else:

def evaluator_map(exp, env, handler, k):
if null_q(exp):
return apply_cont(k, EmptyList)
else:
return evaluator(car(exp), env, handler,
lambda v1: evaluator_map(cdr(exp), env, handler,
lambda rest: apply_cont(k, cons(v1, rest))))

def eval_apply_cont(f, args, env, handler, k):
if closure_q(f):
return evaluator(body, extend_env(parameters, args, env), handler, k)
else:
return f(args, env, handler, k)


Now, we construct a toplevel environment with some primitives, like +, -, *, print, etc. Primitives are written in CPS.

In :
import operator

def sub_prim(args, env, handler, k):
return apply_cont(k, apply(operator.sub, list_to_vector(args)))

def mul_prim(args, env, handler, k):
return apply_cont(k, apply(operator.mul, list_to_vector(args)))

def div_prim(args, env, handler, k):
return apply_cont(k, apply(operator.div, list_to_vector(args)))

def equal_sign_prim(args, env, handler, k):
a = car(args)
return apply_cont(k, 1 if a == b else 0)

def less_than_prim(args, env, handler, k):
a = car(args)
return apply_cont(k, 1 if a < b else 0)

def cons_prim(args, env, handler, k):

def print_prim(args, env, handler, k):
print(*list_to_vector(args))
return apply_cont(k, void)

def input_prim(args, env, handler, k):
prompt = ""
if length(args, handler) > 0:
prompt = car(args)
retval = raw_input(prompt)
return apply_cont(k, retval)

def length_prim(args, env, handler, k):
return apply_cont(k, length(car(args), handler))

def list_prim(args, env, handler, k):
return apply_cont(k, args)

def not_prim(args, env, handler, k):
return apply_cont(k, 0 if true_q(car(args)) else 1)

def pair_q_prim(args, env, handler, k):
return apply_cont(k, 1 if pair_q(car(args)) else 0)

def error_prim(args, env, handler, k):
return apply_cont(handler, car(args))

def null_q_prim(args, env, handler, k):
return apply_cont(k, 1 if null_q(car(args)) else 0)

def car_prim(args, env, handler, k):
return apply_cont(k, car(car(args)))

def cdr_prim(args, env, handler, k):
return apply_cont(k, cdr(car(args)))

def map_prim(args, env, handler, k):
f = car(args)
if null_q(args):
return apply_cont(k, args)
else:
return eval_apply_cont(f, args, env, handler,
lambda v: map_prim(List(f, cdr(args)), env, handler,
lambda rest: apply_cont(k, cons(v, rest))))

def for_each_prim(args, env, handler, k):
f = car(args)
if null_q(args):
return apply_cont(k, args)
else:
return eval_apply_cont(f, args, env, handler,
lambda v: map_prim(List(f, cdr(args)), env, handler,
lambda rest: apply_cont(k, cons(v, rest))))

def callcc_prim(args, env, handler, k):
proc = car(args)
fake_k = lambda args, env, handler, k2: apply_cont(k, car(args))
return eval_apply_cont(proc, List(fake_k), env, handler, k)

toplevel_env = [[["()", EmptyList],
["not", not_prim],
["pair?", pair_q_prim],
["error", error_prim],
["null?", null_q_prim],
["map", map_prim],
["car", car_prim],
["cdr", cdr_prim],
["-", sub_prim],
["*", mul_prim],
["/", div_prim],
["=", equal_sign_prim],
["<", less_than_prim],
["cons", cons_prim],
["print", print_prim],
["input", input_prim],
["length", length_prim],
["list", list_prim],
["call/cc", callcc_prim]]]


Note that all of the primitives are defined using CPS as well. That allows us to implement exotic functions, such as call-with-current-continuation (call/cc) as shown.

Finally, we define a method to apply the continuation and a short-cut for running programs.

In :
def apply_cont(k, v):
return k(v)

def scheme(exp):
toplevel_env,
lambda error: error,
lambda v: v)


And now, we are ready to compute!

In :
scheme("(cons 1 2)")

Out:
(1 . 2)
In :
scheme("(+ 1 2)")

Out:
3
In :
scheme("(length (list 1 2))")

Out:
2
In :
scheme("(if (+ 1 2) 6 7)")

Out:
6
In :
scheme("((lambda (n) (+ n 1)) 42)")

Out:
43
In :
scheme("(if 0 2 3)")

Out:
3
In :
scheme("(if 1 2 3)")

Out:
2
In :
scheme("(+ 1 (error 23))")

Out:
23
In :
scheme("(print 12 56)")

12 56

Out:
<void>
In :
scheme("(begin (print 1 3) (+ 2 3) (+ 3 3) 4)")

1 3

Out:
4
In :
scheme("(map (lambda (n) (print n)) (quote (1 2 3 4)))")

1
2
3
4

Out:
(<void> <void> <void> <void>)

We can define global recursive functions:

In :
scheme("(define factorial (lambda (n) (if (= n 1) 1 (* n (factorial (- n 1))))))")

In :
scheme("factorial")

Out:
#<procedure>
In :
scheme("(factorial 1)")

Out:
1
In :
scheme("(factorial 5)")

Out:
120

Unfortunately, we are still using Python's stack. So this fails:

In :
try:
scheme("(factorial 1000)")
except:
print("Crashed Python's stack!")

Crashed Python's stack!


But we do have continuations, even being able to reach in and grab the current continuation:

In :
scheme("(call/cc (lambda (cc) (cc cc)))")

Out:
<function __main__.<lambda>>

That would be a handy function... let's define it!

In :
scheme("""
(define current-continuation
(lambda ()
(call/cc (lambda (cc)
(cc cc)))))
""")

In :
scheme("""
(begin
(print 1)
(print 2)
(print 3)
(define resume (current-continuation))
(print 4)
(print 5)
(print 6)
)
""")

1
2
3
4
5
6

Out:
<void>

But, we can go back in time and run the code starting at the point where we grabbed the continuation:

In :
scheme("(resume resume)")

4
5
6

Out:
<void>

And do it again and again and ...

In :
scheme("(resume resume)")

4
5
6

Out:
<void>

## Amb - nondeterministic programming¶

Now that we have call/cc we can implement the amb operator (called "choose" in Calysto Scheme).

We will keep track of decision points in a fail-stack. Each time we "fail", we will go back to that point in the computation and resume computing again, with the next choice.

In :
scheme("(define fail-stack (quote ()))")

scheme("""
(define fail
(lambda ()
(if (not (pair? fail-stack))
(error (quote ()))
(begin
(let ((back-track-point (car fail-stack)))
(begin
(set! fail-stack (cdr fail-stack))
(back-track-point back-track-point)))))))
""")

scheme("""
(define amb
(lambda (choices)
(let ((cc (current-continuation)))
(if (null? choices)
(fail)
(if (pair? choices)
(let ((choice (car choices)))
(begin
(set! choices (cdr choices))
(set! fail-stack (cons cc fail-stack))
choice)))))))
""")

scheme("""
(define assert
(lambda (condition)
(if (not condition)
(fail)
1)))
""")

In :
scheme("(amb (list 1 2 3))")

Out:
1
In :
scheme("(fail)")

Out:
2
In :
scheme("(fail)")

Out:
3
In :
scheme("(fail)")

Out:
()

We're looking for dimensions of a legal right triangle using the Pythagorean theorem:

$a^2 + b^2 = c^2$

And, we want the second side (b) to be the shorter one:

$b < a$

We can express the problem as three variables and two asserts:

In :
scheme("(define fail-stack (quote ()))")

In :
try:
scheme("""
(let ((a (amb (list 1 2 3 4 5 6 7)))
(b (amb (list 1 2 3 4 5 6 7)))
(c (amb (list 1 2 3 4 5 6 7))))
(begin
(assert (= (* c c) (+ (* a a) (* b b))))
(assert (< b a))
(print (list a b c))
)
)
""")
except:
print("Crashed Python's stack again!")

Crashed Python's stack again!


## Getting rid of Python's stack¶

It turns out to be very easy to stop using Python's stack for our function calls. We will delay executing continuations. So, instead of apply k to v, instead we just package it up.

We then implement a very simple trampoline that will execute the continuation. This won't crash Python's stask because we execute each continuation outside of the recursive calls:

In :
def apply_cont(k, v):
return List("<continuation>", k, v)

def continuation_q(exp):
return pair_q(exp) and car(exp) == "<continuation>"

def trampoline(result):
while continuation_q(result):
return result

def scheme(exp):
return trampoline(evaluator(parser(reader(lexer(exp))), toplevel_env, lambda e: e, lambda v: v))


Now, we can evaluate much deeper recursive calls than Python:

In :
scheme("(factorial 1000)")

Out:
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000L

In fact, this would run forever:

scheme("""
(define loop
(lambda ()
(loop)))
(loop)
""")


This loop doesn't use up memory as it runs... once started, it has zero additional impact.

And now we can solve the Pythagorean mystery:

In :
scheme("(define fail-stack (quote ()))")

scheme("""
(let ((a (amb (list 1 2 3 4 5 6 7)))
(b (amb (list 1 2 3 4 5 6 7)))
(c (amb (list 1 2 3 4 5 6 7))))
(begin
(assert (= (* c c) (+ (* a a) (* b b))))
(assert (< b a))
(print (list a b c))
)
)
""")

(4 3 5)

Out:
<void>

How do the runtimes compare between Python and Scheme-in-Python?

In :
%%time
scheme("(factorial 900)")

CPU times: user 148 ms, sys: 18.8 ms, total: 167 ms
Wall time: 138 ms

Out:
67526802209645841583879061361800814224269427869589384312198268703685091643180416969132446952698303794226010370578672908593198347699886928591906501031587651846976759681112609524787093848004428636186893395272784450630354080243217646658024696659065951793757223520229235577548653833681102170973893746054649126415909143150172860721156685810655759230011450132992176454983227538696340112610447029002337004887877266387704586077293585433151612518800147764461182680822867092786694982831838641800997499819339206579415325649748486265233918911087114592440896594062675914294925816719862178374679272092637524786939036290035924271782253738059886933923447877769583003016705363339031413069155837518524761078342052635475632113169618774549275701480106933362990003732589370593557325299434734459295866728988740794174654391479926000848846686708729736713207285203712732201272410830836913052635365082888725171636081587151603468291106754640398232146673627370895934090777828827549554232436190464827998683927179246029919443251026464452337939599198528297828591122689960620361238248313158071643395848405047261412680039877733761849874447323867911712630023171745968278465780558568067035013885275080292137360491875164947724464221693533755035300065350065137490832039523382963747026185653050331832380991844842560750923543775188582096487476950254418365198999674684417286265442786651594404781622946901879166382930714196908227460133027605817864877377712193142137625430353718448269390732615776645283198828602917680224041088993892610506802195917247838900106910698057030379190571057605849323113308634452008179881165616449767648354161225066967961297609698742737923389391615207441152319392845687673311899247085327703421862972871644495409572259985563215471482083325653231777113271326579970310755604973969708949477374254974480294652427022436705380184064008853457214518515270985563195412993145274057688634448812449445800617631162768243125606424844709372022149908463572254912654907763445758543980999149122998104378965626781898655221443263601405152073199706585080288735040205417371277253096243200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000L
In :
def fact(n):
if n == 1:
return 1
else:
return n * fact(n - 1)

In :
%%time

fact(900)

CPU times: user 648 µs, sys: 67 µs, total: 715 µs
Wall time: 639 µs

Out:
67526802209645841583879061361800814224269427869589384312198268703685091643180416969132446952698303794226010370578672908593198347699886928591906501031587651846976759681112609524787093848004428636186893395272784450630354080243217646658024696659065951793757223520229235577548653833681102170973893746054649126415909143150172860721156685810655759230011450132992176454983227538696340112610447029002337004887877266387704586077293585433151612518800147764461182680822867092786694982831838641800997499819339206579415325649748486265233918911087114592440896594062675914294925816719862178374679272092637524786939036290035924271782253738059886933923447877769583003016705363339031413069155837518524761078342052635475632113169618774549275701480106933362990003732589370593557325299434734459295866728988740794174654391479926000848846686708729736713207285203712732201272410830836913052635365082888725171636081587151603468291106754640398232146673627370895934090777828827549554232436190464827998683927179246029919443251026464452337939599198528297828591122689960620361238248313158071643395848405047261412680039877733761849874447323867911712630023171745968278465780558568067035013885275080292137360491875164947724464221693533755035300065350065137490832039523382963747026185653050331832380991844842560750923543775188582096487476950254418365198999674684417286265442786651594404781622946901879166382930714196908227460133027605817864877377712193142137625430353718448269390732615776645283198828602917680224041088993892610506802195917247838900106910698057030379190571057605849323113308634452008179881165616449767648354161225066967961297609698742737923389391615207441152319392845687673311899247085327703421862972871644495409572259985563215471482083325653231777113271326579970310755604973969708949477374254974480294652427022436705380184064008853457214518515270985563195412993145274057688634448812449445800617631162768243125606424844709372022149908463572254912654907763445758543980999149122998104378965626781898655221443263601405152073199706585080288735040205417371277253096243200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000L

So, the Scheme-in-Python runs about 2 magnitudes slower than Python for a program that has lots of recursive function calls. That's not good, but there are some things we can do to improve that a bit. But for many programmers, this is a price worth paying for the additional power (e.g., continuations, call/cc, and no stack limit).

## Summary¶

We have examined how one could implement the "hard parts" of Scheme in Python. But there are still more things to do:

• Error checking: to make the concepts easy to see, we left out most error checking. We should add that in a manner that doesn't slow down processing too much.
• Add Lexical Address: use indexing to get variable values rather than sequential search.
• Feedback when there is an error: we could easily add stack-like traces to this Scheme that look just like Python's. That would address one of Guido's concerns. Read that, compare to this code, and you'll see why Guido is wrong.
• There is still recursion (and thus stack use) in the interpreter: we need to get rid of the evaluator and sexp recursions. We can do that by turning recursive calls into a type of continuation, or rewriting parts in iterative forms. Of course, our Scheme will remain stack-free.
• Macros: we will need to write a define-syntax. But that is an independent function performed in the parser.
• Integrate with Python. This is easy: call Python functions, call Scheme functions from Python, import Python modules.

There are many subtleties left to discover! You may want to start with this code and add to it to get to a complete Scheme implementation. Try the below exercises to get started.

All of the above (and more!) have been done in Calysto Scheme. However, Calysto Scheme was written in Scheme and converted to Python (similar to the above) via an automated process (well, 1k lines of Python written by hand, and 8k lines of Python generated by Calico Scheme). You can read more about the project here.

We hope that this was useful!

# Exercises¶

Try implementing the following (roughly listed from easiest to hardest):

1. Test all of the special forms. Report any errors to mailto:dblank@cs.brynmawr.edu.
2. Add error checking. For example, currently if you attempt to take the car of a non-pair or access undefined variables, you get an ugly error. Use the handler to return errors.
3. Add double-quoted strings to the language.
4. Add floating-point numbers to the language.
5. Add missing functions, like: atom?.
6. Add eq? that uses " obj1 is obj2" to compare objects.
7. Add a Boolean type/class and use it rather than zero/one for True/False. Make it show as #t/#f.
8. Add quote symbol to the parser so that 'item expands to (quote item).
9. Add trace-lambda to the language to help with debugging.
10. Add a stack-trace to show "stack-like" output when there is an error (eg, keep track of app-exp entrance and exit).
11. Add cond special form to the language. You will need else (which could be defined to be True).
12. Try some of your homework solutions to see if the version of Scheme in Python can do everything that Calysto Scheme can do. If not, add it!