aboutsummaryrefslogtreecommitdiffstats
path: root/minimal.py
blob: 8a282dabc83d0977e44082ba1fe48d111afa3b72 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
"""
    null -> None
    pair -> <use tuples>
    boolean (true/false) -> True/False
    number -> number
    identifier/symbol -> string


    const (atomic values)
    lambda
    quote (s-expr "one level down")
    identifier (a symbol to be looked up in the context)
    cond (conditional expression)
"""

def is_atom(x):
    return x is () or type(x) not in (None, tuple, list, dict)

def is_boolean(x):
    return x in (True, False)

def is_number(x):
    return type(x) in (int, float, long)

def is_zero(x):
    return x == 0

def is_null(x):
    return x is ()

def is_eq(a, b):
    return a == b

def is_builtin(x):
    return x in ('lambda', 'quote', 'cond', 'else', 'cons', 'car', 'cdr',
                 'null?', 'eq?', 'atom?', 'zero?', 'number?',
                 '+', '-', '*', '/')

# because python does not allow circular function definitions, and action
# functions call out to meaning(), which depends on some actions, we'll use an
# "action lookup table" to handle function references ourself.
# A more "pythonic" way to do this might be to use an object.
actions = dict()

def meaning(x, ctx):
    action = None
    if is_atom(x):
        if is_number(x) or is_boolean(x) or is_builtin(x):
            action = actions['identity']
        else:   # an identifier
            action = actions['lookup']
    elif type(x) is tuple:
        if x[0] is 'quote':
            action = actions['quote']
        elif x[0] is 'cond':
            action = actions['cond']
        elif x[0] is 'lambda':
            action = actions['lambda']
        elif type(x[0]) is tuple:
            action = actions['apply']
        else:   # some other identifier, either builtin or not
            action = actions['apply']
    else:
        raise ValueError("Unexpected expression: %s" % x)
    return action(x, ctx)

def meaning_list(l, ctx):
    return tuple([meaning(x, ctx) for x in l])

def identity_action(x, ctx):
    return x
actions['identity'] = identity_action

def lookup_action(x, ctx):
    if not x in ctx:
        ValueError("Unknown identifier: %s" % x)
    else:
        return ctx[x]
actions['lookup'] = lookup_action

def quote_action(x, ctx):
    if len(x) != 2:
        ValueError("Improper quote usage: %s" % x)
    return x[1]
actions['quote'] = quote_action

def cond_action(x, ctx):
    for line in x[1:]:
        if line[0] == 'else':
            return meaning(line[1], ctx)
        elif meaning(line[0], ctx):
            return meanint(line[1], ctx)
        else:
            # "unspecified"
            return None
actions['cond'] = cond_action

def lambda_action(x, ctx):
    return ('procedure', x[1], x[2:], ctx.copy())
actions['lambda'] = lambda_action

def apply_action(x, ctx):
    if is_builtin(x[0]):
        args = meaning_list(x[1:], ctx)
        if x[0] is 'cons':
            return (args[0], ) + args[1]
        elif x[0] is 'car':
            return args[0][0]
        elif x[0] is 'cdr':
            return args[0][1]
        elif x[0] is 'null?':
            return is_null(args[0])
        elif x[0] is 'eq?':
            return is_eq(args[0], args[1])
        elif x[0] is 'atom?':
            return is_atom(args[0])
        elif x[0] is 'zero?':
            return is_zero(args[0])
        elif x[0] is 'number?':
            return is_number(args[0])
        elif x[0] is '+':
            return args[0] + args[1]
        elif x[0] is '-':
            return args[0] - args[1]
        elif x[0] is '*':
            return args[0] * args[1]
        elif x[0] is '/':
            return args[0] / args[1]
        else:
            raise Exception("Unexpected builtin: %s" % x[0])
    elif type(x[0]) is tuple:
        proc = meaning(x[0], ctx)
        if proc[0] is not 'procedure':
            raise Exception("Not applicable: %s" % str(proc))
        variables = proc[1]
        body = proc[2]
        closure = proc[3].copy()
        args = meaning_list(x[1:], ctx)
        for i in range(len(variables)):
            closure[variables[i]] = args[i]
        for expr in body:
            ret = meaning(expr, closure)
        return ret
    else:
        raise Exception("Unexpected... thing...: %s" % str(x[0]))
actions['apply'] = apply_action

def value(x):
    return meaning(x, dict())

def test():
    # ((lambda (x) (+ 1 x)) 5) ; 6
    v = value( (('lambda', ('x',), ('+', 1, 'x')), 5) )
    assert(v is 6)
    return True

if __name__=='__main__':
    print(test())