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
|
# A partial Scheme implementation in Julia
# null -> nothing
# pair -> Pair type
# boolean (true/false) -> true/false
# number -> Number
# identifier/symbol -> symbol
is_atom(x) = x == () || !(x == nothing ||
typeof(x) <: Tuple ||
typeof(x) <: Array ||
typeof(x) <: Dict)
is_null(x) = x == ()
is_zero(x) = x == 0
is_eq(a, b) = a == b
is_number(x) = typeof(x) <: Number
is_boolean(x) = x == true || x == false
is_builtin(x) = x in (:lambda, :quote, :cond, :else, :cons, :car, :cdr,
:isnull, :iseq, :isatom, :iszero, :isnumber,
:+, :-, :*, :/, +, -, *, /)
identity_action(x, ctx) = x
lookup_action(x, ctx) = ctx[x]
quote_action(x, ctx) = length(x) == 2 ? x[2] : throw(ErrorException())
function cond_action(x, ctx)
for line in x[2:end]
if line[1] == :else
return meaning(line[2], ctx)
elseif meaning(line[1], ctx)
return meaning(line[2], ctx)
else
# "unspecified"
return nothing
end
end
end
function lambda_action(x, ctx)
return (:procedure, x[2], x[3:end], copy(ctx))
end
function apply_action(x, ctx)
if is_builtin(x[1])
action = x[1]
args = [meaning(y, ctx) for y in x[2:end]]
if action == :cons
return tuple(args[1], args[2])
elseif action == :car
return args[1][1]
elseif action == :cdr
return args[1][2]
elseif action == :isnull
return is_null(args[1])
elseif action == :iseq
return is_eq(args[1], args[2])
elseif action == :isatom
return is_atom(args[1])
elseif action == :iszero
return is_zero(args[1])
elseif action == :isnumber
return is_number(args[1])
elseif action == :+ || action == +
return args[1] + args[2]
elseif action == :- || action == -
return args[1] - args[2]
elseif action == :* || action == *
return args[1] * args[2]
elseif action == :/ || action == /
return args[1] / args[2]
else
throw(ErrorException("Unexpected builtin: $(x[0])"))
end
elseif typeof(x[1]) <: Tuple
proc = meaning(x[1], ctx)
if proc[1] != :procedure
throw(ErrorException("Not applicable: $(str(proc))"))
end
variables = proc[2]
body = proc[3]
closure = copy(proc[4])
args = [meaning(y, ctx) for y in x[2:end]]
for i in 1:length(variables)
closure[variables[i]] = args[i]
end
ret = nothing
for expr in body
ret = meaning(expr, closure)
end
return ret
else
throw(ErrorException("Unexpected... thing...: $(x[1])"))
end
end
function meaning(x, ctx)
action = nothing
if is_atom(x)
if is_number(x) || is_boolean(x) || is_builtin(x)
return identity_action(x, ctx)
elseif typeof(x) <: Symbol
return lookup_action(x, ctx)
end
elseif typeof(x) <: Tuple
if x[1] == :quote
return quote_action(x, ctx)
elseif x[1] == :cond
return cond_action(x, ctx)
elseif x[1] == :lambda
return lambda_action(x, ctx)
elseif typeof(x[1]) <: Tuple
return apply_action(x, ctx)
else # some other identifier, either builtin or not
return apply_action(x, ctx)
end
end
throw(ErrorException("Unexpected expression: $x"))
end
function value(ast)
return meaning(ast, Dict())
end
function test_minimal_scheme()
@assert 6 == value( ((:lambda, (:x, ), (+, 1, :x)), 5) )
value( (:car, (:quote, (1, 2, 3, 4))) )
end
|
