Belkadan Software - Source - sicpelago/blob - scheme_primitives.py

   1 """This module implements the primitives of the Scheme language."""
   2
   3 import math
   4 import operator
   5 import sys
   6 from scheme_reader import Pair, nil
   7
   8 try:
   9     import turtle
  10 except:
  11     print("warning: could not import the turtle module.", file=sys.stderr)
  12
  13 class SchemeError(Exception):
  14     """Exception indicating an error in a Scheme program."""
  15
  16 class okay:
  17     """Signifies an undefined value."""
  18     def __repr__(self):
  19         return "okay"
  20
  21 okay = okay() # Assignment hides the okay class; there is only one instance
  22
  23 class Promise:
  24     def __init__(self, body, env):
  25         self.value = None
  26         self.body = body
  27         self.env = env
  28
  29     def __str__(self):
  30         return "(delay {0})".format(str(self.body))
  31
  32     def __repr__(self):
  33         return "Promise({0}, {1})".format(repr(self.body), repr(self.env))
  34
  35 class LambdaProcedure:
  36     """A procedure defined by a lambda expression or the complex define form."""
  37
  38     def __init__(self, formals, body, env):
  39         """A procedure whose formal parameter list is FORMALS (a Scheme list),
  40         whose body is the Scheme list BODY, and whose parent
  41         environment is the Frame ENV.  A lambda expression containing multiple
  42         expressions, such as (lambda (x) (display x) (+ x 1)) can be handled by
  43         using (begin (display x) (+ x 1)) as the body."""
  44         self.formals = formals
  45         self.body = body
  46         self.env = env
  47
  48     def __str__(self):
  49         return "(lambda {0} {1})".format(str(self.formals), ' '.join(str(b) for b in self.body))
  50
  51     def __repr__(self):
  52         args = (self.formals, self.body, self.env)
  53         return "LambdaProcedure({0}, {1}, {2})".format(*(repr(a) for a in args))
  54
  55 class MuProcedure:
  56     """A procedure defined by a mu expression, which has dynamic scope.
  57      _________________
  58     < Scheme is cool! >
  59      -----------------
  60             \   ^__^
  61              \  (oo)\_______
  62                 (__)\       )\/\
  63                     ||----w |
  64                     ||     ||
  65     """
  66
  67     def __init__(self, formals, body):
  68         """A procedure whose formal parameter list is FORMALS (a Scheme list),
  69         whose body is the single Scheme expression BODY.  A mu expression
  70         containing multiple expressions, such as (mu (x) (display x) (+ x 1))
  71         can be handled by using (begin (display x) (+ x 1)) as the body."""
  72         self.formals = formals
  73         self.body = body
  74
  75     def __str__(self):
  76         return "(mu {0} {1})".format(str(self.formals), str(self.body))
  77
  78     def __repr__(self):
  79         args = (self.formals, self.body)
  80         return "MuProcedure({0}, {1})".format(*(repr(a) for a in args))
  81
  82 ########################
  83 # Primitive Operations #
  84 ########################
  85
  86 class PrimitiveProcedure:
  87     """A Scheme procedure defined as a Python function."""
  88
  89     def __init__(self, fn, use_env=False):
  90         self.fn = fn
  91         self.use_env = use_env
  92         self.name = None
  93
  94     def __str__(self):
  95         if self.name:
  96             return '#[primitive ' + self.name + ']'
  97         return '#[primitive]'
  98
  99 _PRIMITIVES = []
 100
 101 def primitive(*names):
 102     """An annotation to convert a Python function into a PrimitiveProcedure."""
 103     def add(fn):
 104         proc = PrimitiveProcedure(fn)
 105         proc.name = names[0]
 106         for name in names:
 107             _PRIMITIVES.append((name,proc))
 108         return fn
 109     return add
 110
 111 def add_primitives(frame):
 112     """Enter bindings in _PRIMITIVES into FRAME, an environment frame."""
 113     for name, proc in _PRIMITIVES:
 114         frame.define(name, proc)
 115
 116 def check_type(val, predicate, k, name):
 117     """Returns VAL.  Raises a SchemeError if not PREDICATE(VAL)
 118     using "argument K of NAME" to describe the offending value."""
 119     if not predicate(val):
 120         msg = "argument {0} of {1} has wrong type ({2})"
 121         raise SchemeError(msg.format(k, name, type(val).__name__))
 122     return val
 123
 124 @primitive("boolean?")
 125 def scheme_booleanp(x):
 126     return x is True or x is False
 127
 128 def scheme_true(val):
 129     """All values in Scheme are true except False."""
 130     return val is not False
 131
 132 def scheme_false(val):
 133     """Only False is false in Scheme."""
 134     return val is False
 135
 136 @primitive("not")
 137 def scheme_not(x):
 138     return not scheme_true(x)
 139
 140 @primitive("eq?")
 141 def scheme_eqp(x, y):
 142     # This is a bit sloppy, we ought to be using 'is' for everything *except* numbers.
 143     # But representing symbols as Python strings makes that a bit fuzzier.
 144     if scheme_pairp(x) and scheme_pairp(y):
 145         return x is y
 146     return x == y
 147
 148 @primitive("equal?")
 149 def scheme_equalp(x, y):
 150     return x == y
 151
 152 @primitive("pair?")
 153 def scheme_pairp(x):
 154     return isinstance(x, Pair)
 155
 156 @primitive("null?")
 157 def scheme_nullp(x):
 158     return x is nil
 159
 160 @primitive("list?")
 161 def scheme_listp(x):
 162     """Return whether x is a well-formed list. Assumes no cycles."""
 163     while x is not nil:
 164         if not isinstance(x, Pair):
 165             return False
 166         x = x.second
 167     return True
 168
 169 @primitive("length")
 170 def scheme_length(x):
 171     if x is nil:
 172         return 0
 173     check_type(x, scheme_listp, 0, 'length')
 174     return len(x)
 175
 176 @primitive("cons")
 177 def scheme_cons(x, y):
 178     return Pair(x, y)
 179
 180 @primitive("car", "stream-car")
 181 def scheme_car(x):
 182     check_type(x, scheme_pairp, 0, 'car')
 183     return x.first
 184
 185 @primitive("cdr")
 186 def scheme_cdr(x):
 187     check_type(x, scheme_pairp, 0, 'cdr')
 188     return x.second
 189
 190 @primitive("promise?")
 191 def scheme_promisep(x):
 192     return isinstance(x, Promise)
 193
 194 @primitive("force")
 195 def scheme_force(x):
 196     check_type(x, scheme_promisep, 0, 'force')
 197     return x.force()
 198
 199 @primitive("stream-cdr")
 200 def scheme_stream_cdr(x):
 201     return scheme_force(scheme_cdr(x))
 202
 203
 204 @primitive("list")
 205 def scheme_list(*vals):
 206     result = nil
 207     for i in range(len(vals)-1, -1, -1):
 208         result = Pair(vals[i], result)
 209     return result
 210
 211 @primitive("append")
 212 def scheme_append(*vals):
 213     if len(vals) == 0:
 214         return nil
 215     result = vals[-1]
 216     for i in range(len(vals)-2, -1, -1):
 217         v = vals[i]
 218         if v is not nil:
 219             check_type(v, scheme_pairp, i, "append")
 220             r = p = Pair(v.first, result)
 221             v = v.second
 222             while scheme_pairp(v):
 223                 p.second = Pair(v.first, result)
 224                 p = p.second
 225                 v = v.second
 226             result = r
 227     return result
 228
 229 @primitive("string?")
 230 def scheme_stringp(x):
 231     return isinstance(x, str) and x.startswith('"')
 232
 233 @primitive("symbol?")
 234 def scheme_symbolp(x):
 235     return isinstance(x, str) and not scheme_stringp(x)
 236
 237 @primitive("number?")
 238 def scheme_numberp(x):
 239     return isinstance(x, int) or isinstance(x, float)
 240
 241 @primitive("integer?")
 242 def scheme_integerp(x):
 243     return isinstance(x, int) or (scheme_numberp(x) and round(x) == x)
 244
 245 @primitive("procedure?")
 246 def scheme_procedurep(x):
 247     return isinstance(x, LambdaProcedure) or isinstance(x, PrimitiveProcedure)
 248
 249 def _check_nums(*vals):
 250     """Check that all arguments in VALS are numbers."""
 251     for i, v in enumerate(vals):
 252         if not scheme_numberp(v):
 253             msg = "operand {0} ({1}) is not a number"
 254             raise SchemeError(msg.format(i, v))
 255
 256 def _arith(fn, init, vals):
 257     """Perform the fn fneration on the number values of VALS, with INIT as
 258     the value when VALS is empty. Returns the result as a Scheme value."""
 259     _check_nums(*vals)
 260     s = init
 261     for val in vals:
 262         s = fn(s, val)
 263     if round(s) == s:
 264         s = round(s)
 265     return s
 266
 267 @primitive("+")
 268 def scheme_add(*vals):
 269     return _arith(operator.add, 0, vals)
 270
 271 @primitive("-")
 272 def scheme_sub(val0, *vals):
 273     if len(vals) == 0:
 274         return -val0
 275     return _arith(operator.sub, val0, vals)
 276
 277 @primitive("*")
 278 def scheme_mul(*vals):
 279     return _arith(operator.mul, 1, vals)
 280
 281 @primitive("/")
 282 def scheme_div(val0, val1):
 283     try:
 284         return _arith(operator.truediv, val0, [val1])
 285     except ZeroDivisionError as err:
 286         raise SchemeError(err)
 287
 288 @primitive("quotient")
 289 def scheme_quo(val0, val1):
 290     try:
 291         return _arith(operator.floordiv, val0, [val1])
 292     except ZeroDivisionError as err:
 293         raise SchemeError(err)
 294
 295 @primitive("remainder")
 296 def scheme_modulo(val0, val1):
 297     try:
 298         return _arith(operator.mod, val0, [val1])
 299     except ZeroDivisionError as err:
 300         raise SchemeError(err)
 301
 302 @primitive("floor")
 303 def scheme_floor(val):
 304     _check_nums(val)
 305     return math.floor(val)
 306
 307 @primitive("ceil")
 308 def scheme_ceil(val):
 309     _check_nums(val)
 310     return math.ceil(val)
 311
 312 def _numcomp(op, x, y):
 313     _check_nums(x, y)
 314     return op(x, y)
 315
 316 @primitive("=")
 317 def scheme_eq(x, y):
 318     return _numcomp(operator.eq, x, y)
 319
 320 @primitive("<")
 321 def scheme_lt(x, y):
 322     return _numcomp(operator.lt, x, y)
 323
 324 @primitive(">")
 325 def scheme_gt(x, y):
 326     return _numcomp(operator.gt, x, y)
 327
 328 @primitive("<=")
 329 def scheme_le(x, y):
 330     return _numcomp(operator.le, x, y)
 331
 332 @primitive(">=")
 333 def scheme_ge(x, y):
 334     return _numcomp(operator.ge, x, y)
 335
 336 @primitive("even?")
 337 def scheme_evenp(x):
 338     _check_nums(x)
 339     return x % 2 == 0
 340
 341 @primitive("odd?")
 342 def scheme_oddp(x):
 343     _check_nums(x)
 344     return x % 2 == 1
 345
 346 @primitive("zero?")
 347 def scheme_zerop(x):
 348     _check_nums(x)
 349     return x == 0
 350
 351 ##
 352 ## Other operations
 353 ##
 354
 355 @primitive("atom?")
 356 def scheme_atomp(x):
 357     if scheme_booleanp(x):
 358         return True
 359     if scheme_numberp(x):
 360         return True
 361     if scheme_symbolp(x):
 362         return True
 363     if scheme_nullp(x):
 364         return True
 365     return False
 366
 367 @primitive("display")
 368 def scheme_display(val):
 369     if scheme_stringp(val):
 370         val = eval(val)
 371     print(str(val), end="")
 372     return okay
 373
 374 @primitive("print")
 375 def scheme_print(val):
 376     print(str(val))
 377     return okay
 378
 379 @primitive("newline")
 380 def scheme_newline():
 381     print()
 382     sys.stdout.flush()
 383     return okay
 384
 385 @primitive("error")
 386 def scheme_error(msg = None):
 387     msg = "" if msg is None else str(msg)
 388     raise SchemeError(msg)
 389
 390 @primitive("exit")
 391 def scheme_exit():
 392     raise EOFError