Show pair.py syntax highlighted
"""Implementation of pairs for Python.
Pairs are like linked lists in Python. For historical reasons, we use
the following funny names to construct and destructure lists:
cons(head, tail) --- constructs a ConsPair that consists of a
head and a tail.
car(pair) --- returns the head of a ConsPair.
cdr(pair) --- returns the tail of a ConsPair.
Scheme's lists are built up of pair chains terminated by NIL.
The reason we use a separate factory function --- cons() --- instead
of directly using the ConsPair is because we may want the freedom to
change implementation later on. In SICP, in fact, there's a totally
screwy implementation that uses lambdas entirely, with no real data
structure.
There are a few more convenience functions here to rapidly make these
pair structures. For example, there's a list() function here that,
given a set of arguments, produces a pair chain.
"""
__license__ = "MIT License"
"""This module is not 'from pair import *' safe! Particularly because
we define a few functions here that have names that conflict with
builtins. Let's enforce this restriction."""
__all__ = []
from sets import Set
from symbol import Symbol
from error import SchemeError
import pogo
"""The NIL atom. There should be only one!"""
NIL = []
class ConsPair(list): pass
def isNull(x):
return x is NIL
def isPair(p):
return type(p) is ConsPair
def cons(head, rest):
"""Returns the concatentation of head with rest."""
return ConsPair([head, rest])
def car(p):
"""Returns the head of the pair."""
if not isPair(p):
raise SchemeError, "CAR --- argument is not a pair."
if p is NIL:
raise SchemeError, "CAR --- cannot take CAR of empty list."
else:
return p[0]
def cdr(p):
"""Returns the tail of the pair."""
if not isPair(p):
raise SchemeError, "CDR --- argument is not a pair."
if p is NIL:
raise SchemeError, "CDR --- cannot take CDR of empty list."
else:
return p[1]
def cddr(p):
return cdr(cdr(p))
def cdddr(p):
return cdr(cdr(cdr(p)))
def cadr(p):
return car(cdr(p))
def caddr(p):
return car(cdr(cdr(p)))
def cadddr(p):
return car(cdr(cdr(cdr(p))))
def setCarBang(pair, element):
"""Sets the head of the pair to the element."""
if not isPair(pair):
raise SchemeError, "SET-CAR! --- cannot set car of non-pair."
pair[0] = element
return Symbol("ok")
def setCdrBang(pair, element):
"""Sets the tail of the pair to the element."""
if not isPair(pair):
raise SchemeError, "SET-CAR! --- cannot set car of non-pair."
pair[1] = element
return Symbol("ok")
## Hmm... some of these functions really belong in builtins.py.
def isList(p):
"""Returns True if p refers to a list-like structure.
Note: loopy structures don't qualify as lists.
"""
seenPairIds = Set()
while True:
if id(p) in seenPairIds:
return 0
seenPairIds.add(id(p))
if isNull(p): return 1
if not isPair(p): return 0
p = cdr(p)
def isDottedPair(p):
"""Returns True if p refers to an improper list, where the cdr is
not a pair."""
if not isPair(p): return 0
elif isPair(cdr(p)) or isNull(cdr(p)): return 0
else: return 1
def length(p):
"""Returns the length of p. Assumes that p is a list."""
if not isList(p): raise SchemeError, "LENGTH --- not a list"
length = 0
while True:
if isNull(p): return length
length += 1
p = cdr(p)
def reverse(p):
"""Reverses a list."""
if not isList(p): raise SchemeError, "REVERSE --- not a list"
result = NIL
while not isNull(p):
result = cons(car(p), result)
p = cdr(p)
return result
def listMap(f, p):
"""Maps a function f across p."""
if not isList(p): raise SchemeError, "MAP --- not a list"
resultsRev = NIL
while not isNull(p):
resultsRev = cons(f(car(p)), resultsRev)
p = cdr(p)
return reverse(resultsRev)
def c_listMap(c_f, p, cont, allow_improper_lists=False):
"""Maps a function f across p, but in a continuation-passed style.
'c_f' is a function that takes a 2-tuple (element, cont),
the element and the continuation.
'cont' is the continutation we apply on the mapped list.
If the optional keyword parameter 'allow_improper' is set to True,
then we'll also allow mapping across improper lists.
"""
if isNull(p):
return pogo.bounce(cont, NIL)
if not isPair(p):
if allow_improper_lists:
return pogo.bounce(c_f, p, cont)
else:
raise SchemeError, "CMAP --- not a list"
def c_head(head_val):
def c_tail(tail_val):
return pogo.bounce(cont, cons(head_val, tail_val))
return pogo.bounce(c_listMap, c_f, cdr(p), c_tail,
allow_improper_lists)
return pogo.bounce(c_f, car(p), c_head)
def append(*lists):
"""Appends all lists together."""
appended_list = lists[-1]
for i in xrange(len(lists)-2, -1, -1):
next_list = lists[i]
appended_list = pogo.pogo(
c_appendTwo(next_list, appended_list, pogo.land))
return appended_list
def c_appendTwo(front, back, cont):
"""Appends two lists together. Written in continuation passing style."""
if not isList(front): raise SchemeError, "MAP --- not a list"
if not isList(back): raise SchemeError, "MAP --- not a list"
if isNull(front):
return pogo.bounce(cont, back)
def c(appendedRest):
return pogo.bounce(cont, cons(car(front),
appendedRest))
return pogo.bounce(c_appendTwo, cdr(front), back, c)
def toPythonList(pair):
"""Does a shallow conversion of a pair list chain to a Python list."""
if not isList(pair): raise SchemeError, "not a list"
elements = []
while not isNull(pair):
elements.append(car(pair))
pair = cdr(pair)
return elements
"""Let's save the old version of Python's list function."""
list_in_underlying_python = list
def list(*elements):
"""Does a shallow conversion of a Python list to a pair chain.
Warning: this does have the same name as the builtin list() function
in Python.
"""
result = list_in_underlying_python(elements)
result.reverse()
return reduce(lambda x, y: cons(y, x), [NIL] + result)
######################################################################
try:
import unittest
class PairTests(unittest.TestCase):
def testNull(self):
self.assert_(isList(NIL))
def testReversal(self):
self.assertEquals(list(1, 2, 3, 4, 5),
reverse(list(5, 4, 3, 2, 1)))
def testMapping(self):
self.assertEquals(list(2, 4, 6, 8),
listMap(lambda x: x*2, list(1, 2, 3, 4)))
def testAppendTwo(self):
self.assertEquals(list(1, 2, 3, 4),
pogo.pogo(c_appendTwo(list(1, 2),
list(3, 4),
pogo.land)))
def testContinuationMapping(self):
def c_square(x, cont):
return pogo.bounce(cont, x**2)
self.assertEquals(cons(4, 9),
pogo.pogo(c_listMap(c_square, cons(2, 3),
pogo.land,
allow_improper_lists=True)))
self.assertRaises(SchemeError,
pogo.pogo,
pogo.bounce(c_listMap, c_square,
cons(2, 3), pogo.land))
self.assertEquals(list(1, 4, 9, 16),
pogo.pogo(c_listMap(c_square,
list(1, 2, 3, 4),
pogo.land)))
if __name__ == '__main__':
unittest.main()
except ImportError:
pass
See more files for this project here