Commit | Line | Data |
---|---|---|
2539e6af KR |
1 | //****************************************************************************** |
2 | // MAL - step 5 - tco | |
3 | //****************************************************************************** | |
4 | // This file is automatically generated from templates/step.swift. Rather than | |
5 | // editing it directly, it's probably better to edit templates/step.swift and | |
6 | // regenerate this file. Otherwise, your change might be lost if/when someone | |
7 | // else performs that process. | |
8 | //****************************************************************************** | |
9 | ||
10 | import Foundation | |
11 | ||
12 | // The number of times EVAL has been entered recursively. We keep track of this | |
13 | // so that we can protect against overrunning the stack. | |
14 | // | |
425305df | 15 | private var EVAL_level = 0 |
2539e6af KR |
16 | |
17 | // The maximum number of times we let EVAL recurse before throwing an exception. | |
18 | // Testing puts this at some place between 1800 and 1900. Let's keep it at 500 | |
19 | // for safety's sake. | |
20 | // | |
425305df | 21 | private let EVAL_leval_max = 500 |
2539e6af KR |
22 | |
23 | // Control whether or not tail-call optimization (TCO) is enabled. We want it | |
24 | // `true` most of the time, but may disable it for debugging purposes (it's | |
25 | // easier to get a meaningful backtrace that way). | |
26 | // | |
425305df | 27 | private let TCO = true |
2539e6af KR |
28 | |
29 | // Control whether or not we emit debugging statements in EVAL. | |
30 | // | |
425305df | 31 | private let DEBUG_EVAL = false |
2539e6af | 32 | |
b3ec2290 KR |
33 | // String used to prefix information logged in EVAL. Increasing lengths of the |
34 | // string are used the more EVAL is recursed. | |
35 | // | |
425305df | 36 | private let INDENT_TEMPLATE = "|----|----|----|----|----|----|----|----|" + |
2539e6af KR |
37 | "----|----|----|----|----|----|----|----|----|----|----|" + |
38 | "----|----|----|----|----|----|----|----|----|----|----|" + | |
39 | "----|----|----|----|----|----|----|----|----|----|----|" + | |
40 | "----|----|----|----|----|----|----|----|----|----|----|" + | |
41 | "----|----|----|----|----|----|----|----|----|----|----|" + | |
42 | "----|----|----|----|----|----|----|----|----|----|----|" + | |
43 | "----|----|----|----|----|----|----|----|----|----|----|" + | |
44 | "----|----|----|----|----|----|----|----|----|----|----|" + | |
45 | "----|----|----|----|----|----|----|----|----|----|----|" + | |
46 | "----|----|----|----|----|----|----|----|----|----|----|" | |
b3ec2290 KR |
47 | |
48 | // Holds the prefix of INDENT_TEMPLATE used for actual logging. | |
49 | // | |
425305df | 50 | private var indent = String() |
2539e6af | 51 | |
b3ec2290 KR |
52 | // Symbols used in this module. |
53 | // | |
425305df KR |
54 | private let kValDef = make_symbol("def!") |
55 | private let kValDo = make_symbol("do") | |
56 | private let kValFn = make_symbol("fn*") | |
57 | private let kValIf = make_symbol("if") | |
58 | private let kValLet = make_symbol("let*") | |
59 | private let kValTry = make_symbol("try*") | |
60 | ||
61 | private let kSymbolDef = as_symbol(kValDef) | |
62 | private let kSymbolDo = as_symbol(kValDo) | |
63 | private let kSymbolFn = as_symbol(kValFn) | |
64 | private let kSymbolIf = as_symbol(kValIf) | |
65 | private let kSymbolLet = as_symbol(kValLet) | |
66 | ||
67 | func substring(s: String, _ begin: Int, _ end: Int) -> String { | |
68 | return s[s.startIndex.advancedBy(begin) ..< s.startIndex.advancedBy(end)] | |
2539e6af KR |
69 | } |
70 | ||
71 | // Parse the string into an AST. | |
72 | // | |
425305df KR |
73 | private func READ(str: String) throws -> MalVal { |
74 | return try read_str(str) | |
2539e6af KR |
75 | } |
76 | ||
77 | // Perform a simple evaluation of the `ast` object. If it's a symbol, | |
78 | // dereference it and return its value. If it's a collection, call EVAL on all | |
79 | // elements (or just the values, in the case of the hashmap). Otherwise, return | |
80 | // the object unchanged. | |
81 | // | |
425305df KR |
82 | private func eval_ast(ast: MalVal, _ env: Environment) throws -> MalVal { |
83 | if let symbol = as_symbolQ(ast) { | |
84 | guard let val = env.get(symbol) else { | |
85 | try throw_error("'\(symbol)' not found") // Specific text needed to match MAL unit tests | |
86 | } | |
87 | return val | |
88 | } | |
89 | if let list = as_listQ(ast) { | |
90 | var result = [MalVal]() | |
91 | result.reserveCapacity(Int(list.count)) | |
92 | for item in list { | |
93 | let eval = try EVAL(item, env) | |
94 | result.append(eval) | |
95 | } | |
96 | return make_list(result) | |
97 | } | |
98 | if let vec = as_vectorQ(ast) { | |
99 | var result = [MalVal]() | |
100 | result.reserveCapacity(Int(vec.count)) | |
101 | for item in vec { | |
102 | let eval = try EVAL(item, env) | |
103 | result.append(eval) | |
104 | } | |
105 | return make_vector(result) | |
106 | } | |
107 | if let hash = as_hashmapQ(ast) { | |
108 | var result = [MalVal]() | |
109 | result.reserveCapacity(Int(hash.count) * 2) | |
110 | for (k, v) in hash { | |
111 | let new_v = try EVAL(v, env) | |
112 | result.append(k) | |
113 | result.append(new_v) | |
114 | } | |
115 | return make_hashmap(result) | |
2539e6af | 116 | } |
425305df | 117 | return ast |
2539e6af KR |
118 | } |
119 | ||
425305df | 120 | private enum TCOVal { |
b3ec2290 KR |
121 | case NoResult |
122 | case Return(MalVal) | |
123 | case Continue(MalVal, Environment) | |
124 | ||
125 | init() { self = .NoResult } | |
126 | init(_ result: MalVal) { self = .Return(result) } | |
127 | init(_ ast: MalVal, _ env: Environment) { self = .Continue(ast, env) } | |
b3ec2290 KR |
128 | } |
129 | ||
130 | // EVALuate "def!". | |
131 | // | |
425305df KR |
132 | private func eval_def(list: MalSequence, _ env: Environment) throws -> TCOVal { |
133 | guard list.count == 3 else { | |
134 | try throw_error("expected 2 arguments to def!, got \(list.count - 1)") | |
b3ec2290 | 135 | } |
425305df KR |
136 | let arg1 = try! list.nth(1) |
137 | let arg2 = try! list.nth(2) | |
138 | guard let sym = as_symbolQ(arg1) else { | |
139 | try throw_error("expected symbol for first argument to def!") | |
b3ec2290 | 140 | } |
425305df | 141 | let value = try EVAL(arg2, env) |
b3ec2290 KR |
142 | return TCOVal(env.set(sym, value)) |
143 | } | |
144 | ||
145 | // EVALuate "let*". | |
146 | // | |
425305df KR |
147 | private func eval_let(list: MalSequence, _ env: Environment) throws -> TCOVal { |
148 | guard list.count == 3 else { | |
149 | try throw_error("expected 2 arguments to let*, got \(list.count - 1)") | |
b3ec2290 | 150 | } |
425305df KR |
151 | let arg1 = try! list.nth(1) |
152 | let arg2 = try! list.nth(2) | |
153 | guard let bindings = as_sequenceQ(arg1) else { | |
154 | try throw_error("expected list for first argument to let*") | |
b3ec2290 | 155 | } |
425305df KR |
156 | guard bindings.count % 2 == 0 else { |
157 | try throw_error("expected even number of elements in bindings to let*, got \(bindings.count)") | |
b3ec2290 | 158 | } |
425305df KR |
159 | let new_env = Environment(outer: env) |
160 | for var index: MalIntType = 0; index < bindings.count; index += 2 { | |
161 | let binding_name = try! bindings.nth(index) | |
162 | let binding_value = try! bindings.nth(index + 1) | |
163 | guard let binding_symbol = as_symbolQ(binding_name) else { | |
164 | try throw_error("expected symbol for first element in binding pair") | |
b3ec2290 | 165 | } |
425305df | 166 | let evaluated_value = try EVAL(binding_value, new_env) |
b3ec2290 KR |
167 | new_env.set(binding_symbol, evaluated_value) |
168 | } | |
169 | if TCO { | |
170 | return TCOVal(arg2, new_env) | |
171 | } | |
425305df | 172 | return TCOVal(try EVAL(arg2, new_env)) |
b3ec2290 KR |
173 | } |
174 | ||
175 | // EVALuate "do". | |
176 | // | |
425305df | 177 | private func eval_do(list: MalSequence, _ env: Environment) throws -> TCOVal { |
b3ec2290 | 178 | if TCO { |
425305df | 179 | let _ = try eval_ast(list.range_from(1, to: list.count-1), env) |
b3ec2290 KR |
180 | return TCOVal(list.last(), env) |
181 | } | |
182 | ||
425305df KR |
183 | let evaluated_ast = try eval_ast(list.rest(), env) |
184 | let evaluated_seq = as_sequence(evaluated_ast) | |
b3ec2290 KR |
185 | return TCOVal(evaluated_seq.last()) |
186 | } | |
187 | ||
188 | // EVALuate "if". | |
189 | // | |
425305df KR |
190 | private func eval_if(list: MalSequence, _ env: Environment) throws -> TCOVal { |
191 | guard list.count >= 3 else { | |
192 | try throw_error("expected at least 2 arguments to if, got \(list.count - 1)") | |
b3ec2290 | 193 | } |
425305df KR |
194 | let cond_result = try EVAL(try! list.nth(1), env) |
195 | var new_ast: MalVal | |
b3ec2290 | 196 | if is_truthy(cond_result) { |
425305df | 197 | new_ast = try! list.nth(2) |
b3ec2290 | 198 | } else if list.count == 4 { |
425305df | 199 | new_ast = try! list.nth(3) |
b3ec2290 | 200 | } else { |
425305df | 201 | return TCOVal(make_nil()) |
b3ec2290 KR |
202 | } |
203 | if TCO { | |
204 | return TCOVal(new_ast, env) | |
205 | } | |
425305df | 206 | return TCOVal(try EVAL(new_ast, env)) |
b3ec2290 KR |
207 | } |
208 | ||
209 | // EVALuate "fn*". | |
210 | // | |
425305df KR |
211 | private func eval_fn(list: MalSequence, _ env: Environment) throws -> TCOVal { |
212 | guard list.count == 3 else { | |
213 | try throw_error("expected 2 arguments to fn*, got \(list.count - 1)") | |
b3ec2290 | 214 | } |
425305df KR |
215 | guard let seq = as_sequenceQ(try! list.nth(1)) else { |
216 | try throw_error("expected list or vector for first argument to fn*") | |
b3ec2290 | 217 | } |
425305df | 218 | return TCOVal(make_closure((eval: EVAL, args: seq, body: try! list.nth(2), env: env))) |
b3ec2290 KR |
219 | } |
220 | ||
2539e6af KR |
221 | // Walk the AST and completely evaluate it, handling macro expansions, special |
222 | // forms and function calls. | |
223 | // | |
425305df KR |
224 | private func EVAL(var ast: MalVal, var _ env: Environment) throws -> MalVal { |
225 | EVAL_level++ | |
226 | defer { EVAL_level-- } | |
227 | guard EVAL_level <= EVAL_leval_max else { | |
228 | try throw_error("Recursing too many levels (> \(EVAL_leval_max))") | |
2539e6af KR |
229 | } |
230 | ||
2c4b8bd1 | 231 | if DEBUG_EVAL { |
425305df | 232 | indent = substring(INDENT_TEMPLATE, 0, EVAL_level) |
2c4b8bd1 | 233 | } |
2539e6af KR |
234 | |
235 | while true { | |
425305df | 236 | if DEBUG_EVAL { print("\(indent)> \(ast)") } |
2539e6af | 237 | |
b3ec2290 KR |
238 | if !is_list(ast) { |
239 | ||
240 | // Not a list -- just evaluate and return. | |
241 | ||
425305df KR |
242 | let answer = try eval_ast(ast, env) |
243 | if DEBUG_EVAL { print("\(indent)>>> \(answer)") } | |
b3ec2290 KR |
244 | return answer |
245 | } | |
246 | ||
2539e6af KR |
247 | // Special handling if it's a list. |
248 | ||
425305df KR |
249 | let list = as_list(ast) |
250 | if DEBUG_EVAL { print("\(indent)>. \(list)") } | |
2539e6af | 251 | |
b3ec2290 | 252 | if list.isEmpty { |
425305df | 253 | return ast |
b3ec2290 | 254 | } |
2539e6af | 255 | |
b3ec2290 KR |
256 | // Check for special forms, where we want to check the operation |
257 | // before evaluating all of the parameters. | |
258 | ||
259 | let arg0 = list.first() | |
425305df KR |
260 | if let fn_symbol = as_symbolQ(arg0) { |
261 | let res: TCOVal | |
b3ec2290 KR |
262 | |
263 | switch fn_symbol { | |
425305df KR |
264 | case kSymbolDef: res = try eval_def(list, env) |
265 | case kSymbolLet: res = try eval_let(list, env) | |
266 | case kSymbolDo: res = try eval_do(list, env) | |
267 | case kSymbolIf: res = try eval_if(list, env) | |
268 | case kSymbolFn: res = try eval_fn(list, env) | |
b3ec2290 KR |
269 | default: res = TCOVal() |
270 | } | |
271 | switch res { | |
272 | case let .Return(result): return result | |
273 | case let .Continue(new_ast, new_env): ast = new_ast; env = new_env; continue | |
274 | case .NoResult: break | |
2539e6af | 275 | } |
b3ec2290 | 276 | } |
2539e6af | 277 | |
b3ec2290 | 278 | // Standard list to be applied. Evaluate all the elements first. |
2539e6af | 279 | |
425305df | 280 | let eval = try eval_ast(ast, env) |
2539e6af | 281 | |
b3ec2290 | 282 | // The result had better be a list and better be non-empty. |
2539e6af | 283 | |
425305df | 284 | let eval_list = as_list(eval) |
b3ec2290 | 285 | if eval_list.isEmpty { |
425305df | 286 | return eval |
b3ec2290 | 287 | } |
2539e6af | 288 | |
425305df | 289 | if DEBUG_EVAL { print("\(indent)>> \(eval)") } |
b3ec2290 KR |
290 | |
291 | // Get the first element of the list and execute it. | |
292 | ||
293 | let first = eval_list.first() | |
425305df | 294 | let rest = as_sequence(eval_list.rest()) |
b3ec2290 | 295 | |
425305df KR |
296 | if let fn = as_builtinQ(first) { |
297 | let answer = try fn.apply(rest) | |
298 | if DEBUG_EVAL { print("\(indent)>>> \(answer)") } | |
b3ec2290 | 299 | return answer |
425305df KR |
300 | } else if let fn = as_closureQ(first) { |
301 | let new_env = Environment(outer: fn.env) | |
302 | let _ = try new_env.set_bindings(fn.args, with_exprs: rest) | |
b3ec2290 KR |
303 | if TCO { |
304 | env = new_env | |
305 | ast = fn.body | |
306 | continue | |
2539e6af | 307 | } |
425305df KR |
308 | let answer = try EVAL(fn.body, new_env) |
309 | if DEBUG_EVAL { print("\(indent)>>> \(answer)") } | |
b3ec2290 | 310 | return answer |
2539e6af KR |
311 | } |
312 | ||
b3ec2290 KR |
313 | // The first element wasn't a function to be executed. Return an |
314 | // error saying so. | |
2539e6af | 315 | |
425305df | 316 | try throw_error("first list item does not evaluate to a function: \(first)") |
2539e6af KR |
317 | } |
318 | } | |
319 | ||
320 | // Convert the value into a human-readable string for printing. | |
321 | // | |
425305df | 322 | private func PRINT(exp: MalVal) -> String { |
2539e6af KR |
323 | return pr_str(exp, true) |
324 | } | |
325 | ||
326 | // Perform the READ and EVAL steps. Useful for when you don't care about the | |
327 | // printable result. | |
328 | // | |
425305df KR |
329 | private func RE(text: String, _ env: Environment) -> MalVal? { |
330 | if !text.isEmpty { | |
331 | do { | |
332 | let ast = try READ(text) | |
333 | do { | |
334 | return try EVAL(ast, env) | |
335 | } catch let error as MalException { | |
336 | print("Error evaluating input: \(error)") | |
337 | } catch { | |
338 | print("Error evaluating input: \(error)") | |
339 | } | |
340 | } catch let error as MalException { | |
341 | print("Error parsing input: \(error)") | |
342 | } catch { | |
343 | print("Error parsing input: \(error)") | |
344 | } | |
2539e6af | 345 | } |
425305df | 346 | return nil |
2539e6af KR |
347 | } |
348 | ||
349 | // Perform the full READ/EVAL/PRINT, returning a printable string. | |
350 | // | |
425305df | 351 | private func REP(text: String, _ env: Environment) -> String? { |
2539e6af KR |
352 | let exp = RE(text, env) |
353 | if exp == nil { return nil } | |
354 | return PRINT(exp!) | |
355 | } | |
356 | ||
357 | // Perform the full REPL. | |
358 | // | |
425305df | 359 | private func REPL(env: Environment) { |
2539e6af KR |
360 | while true { |
361 | if let text = _readline("user> ") { | |
362 | if let output = REP(text, env) { | |
425305df | 363 | print("\(output)") |
2539e6af KR |
364 | } |
365 | } else { | |
425305df | 366 | print("") |
2539e6af KR |
367 | break |
368 | } | |
369 | } | |
370 | } | |
371 | ||
372 | func main() { | |
425305df | 373 | let env = Environment(outer: nil) |
2539e6af KR |
374 | |
375 | load_history_file() | |
376 | load_builtins(env) | |
377 | ||
378 | RE("(def! not (fn* (a) (if a false true)))", env) | |
379 | REPL(env) | |
380 | ||
381 | save_history_file() | |
382 | } |