Commit | Line | Data |
---|---|---|
2539e6af KR |
1 | //****************************************************************************** |
2 | // MAL - step 8 - macros | |
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 | // | |
15 | var EVAL_level = 0 | |
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 | // | |
21 | let EVAL_leval_max = 500 | |
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 | // | |
27 | let TCO = true | |
28 | ||
29 | // Control whether or not we emit debugging statements in EVAL. | |
30 | // | |
31 | let DEBUG_EVAL = false | |
32 | ||
33 | let INDENT_TEMPLATE = "|----|----|----|----|----|----|----|----|" + | |
34 | "----|----|----|----|----|----|----|----|----|----|----|" + | |
35 | "----|----|----|----|----|----|----|----|----|----|----|" + | |
36 | "----|----|----|----|----|----|----|----|----|----|----|" + | |
37 | "----|----|----|----|----|----|----|----|----|----|----|" + | |
38 | "----|----|----|----|----|----|----|----|----|----|----|" + | |
39 | "----|----|----|----|----|----|----|----|----|----|----|" + | |
40 | "----|----|----|----|----|----|----|----|----|----|----|" + | |
41 | "----|----|----|----|----|----|----|----|----|----|----|" + | |
42 | "----|----|----|----|----|----|----|----|----|----|----|" + | |
43 | "----|----|----|----|----|----|----|----|----|----|----|" | |
2c4b8bd1 | 44 | var indent = String() |
2539e6af KR |
45 | |
46 | let kSymbolArgv = MalSymbol(symbol: "*ARGV*") | |
47 | let kSymbolConcat = MalSymbol(symbol: "concat") | |
48 | let kSymbolCons = MalSymbol(symbol: "cons") | |
49 | let kSymbolDef = MalSymbol(symbol: "def!") | |
50 | let kSymbolDefMacro = MalSymbol(symbol: "defmacro!") | |
51 | let kSymbolDo = MalSymbol(symbol: "do") | |
52 | let kSymbolEval = MalSymbol(symbol: "eval") | |
53 | let kSymbolFunction = MalSymbol(symbol: "fn*") | |
54 | let kSymbolIf = MalSymbol(symbol: "if") | |
55 | let kSymbolLet = MalSymbol(symbol: "let*") | |
56 | let kSymbolMacroExpand = MalSymbol(symbol: "macroexpand") | |
57 | let kSymbolQuasiquote = MalSymbol(symbol: "quasiquote") | |
58 | let kSymbolQuote = MalSymbol(symbol: "quote") | |
59 | let kSymbolSpliceUnquote = MalSymbol(symbol: "splice-unquote") | |
60 | let kSymbolUnquote = MalSymbol(symbol: "unquote") | |
61 | ||
62 | // Class to help control the incrementing and decrementing of EVAL_level. We | |
63 | // create one of these on entry to EVAL, incrementing the level. When the | |
64 | // variable goes out of scope, the object is destroyed, decrementing the level. | |
65 | // | |
66 | class EVAL_Counter { | |
67 | init() { | |
68 | ++EVAL_level | |
69 | } | |
70 | deinit { | |
71 | --EVAL_level | |
72 | } | |
73 | } | |
74 | ||
75 | // Parse the string into an AST. | |
76 | // | |
77 | func READ(str: String) -> MalVal { | |
78 | return read_str(str) | |
79 | } | |
80 | ||
81 | // Return whether or not `val` is a non-empty list. | |
82 | // | |
83 | func is_pair(val:MalVal) -> Bool { | |
84 | if !is_sequence(val) { return false } | |
85 | let list = val as MalSequence | |
86 | return !list.isEmpty | |
87 | } | |
88 | ||
89 | // Expand macros for as long as the expression looks like a macro invocation. | |
90 | // | |
91 | func macroexpand(var ast:MalVal, env:Environment) -> MalVal { | |
92 | while true { | |
93 | if !is_list(ast) { break } | |
94 | let ast_as_list = ast as MalList | |
95 | if ast_as_list.isEmpty { break } | |
96 | let first = ast_as_list.first() | |
97 | if !is_symbol(first) { break } | |
98 | let macro_name = first as MalSymbol | |
99 | let obj = env.get(macro_name) | |
100 | if obj == nil { break } | |
101 | if !is_closure(obj!) { break } | |
102 | let macro = obj! as MalClosure | |
103 | if !macro.is_macro { break } | |
104 | var new_env = Environment(outer: macro.env) | |
105 | let rest = ast_as_list.rest() | |
106 | let res = new_env.set_bindings(macro.args, with_exprs:rest) | |
107 | if is_error(res) { return res } | |
108 | ast = EVAL(macro.body, new_env) | |
109 | } | |
110 | return ast | |
111 | } | |
112 | ||
113 | // Evaluate `quasiquote`, possibly recursing in the process. | |
114 | // | |
115 | // As with quote, unquote, and splice-unquote, quasiquote takes a single | |
116 | // parameter, typically a list. In the general case, this list is processed | |
117 | // recursively as: | |
118 | // | |
119 | // (quasiquote (first rest...)) -> (cons (quasiquote first) (quasiquote rest)) | |
120 | // | |
121 | // In the processing of the parameter passed to it, quasiquote handles three | |
122 | // special cases: | |
123 | // | |
124 | // * If the parameter is an atom or an empty list, the following expression | |
125 | // is formed and returned for evaluation: | |
126 | // | |
127 | // (quasiquote atom-or-empty-list) -> (quote atom-or-empty-list) | |
128 | // | |
129 | // * If the first element of the non-empty list is the symbol "unquote" | |
130 | // followed by a second item, the second item is returned as-is: | |
131 | // | |
132 | // (quasiquote (unquote fred)) -> fred | |
133 | // | |
134 | // * If the first element of the non-empty list is another list containing | |
135 | // the symbol "splice-unquote" followed by a list, that list is catenated | |
136 | // with the quasiquoted result of the remaining items in the non-empty | |
137 | // parent list: | |
138 | // | |
139 | // (quasiquote (splice-unquote list) rest...) -> (items-from-list items-from-quasiquote(rest...)) | |
140 | // | |
141 | // Note the inconsistent handling between "quote" and "splice-quote". The former | |
142 | // is handled when this function is handed a list that starts with "quote", | |
143 | // whereas the latter is handled when this function is handled a list whose | |
144 | // first element is a list that starts with "splice-quote". The handling of the | |
145 | // latter is forced by the need to incorporate the results of (splice-quote | |
146 | // list) with the remaining items of the list containing that splice-quote | |
147 | // expression. However, it's not clear to me why the handling of "unquote" is | |
148 | // not handled similarly, for consistency's sake. | |
149 | ||
150 | func quasiquote(qq_arg:MalVal) -> MalVal { | |
151 | ||
152 | // If the argument is an atom or empty list: | |
153 | // | |
154 | // Return: (quote <argument>) | |
155 | ||
156 | if !is_pair(qq_arg) { | |
157 | return MalList(objects: kSymbolQuote, qq_arg) | |
158 | } | |
159 | ||
160 | // The argument is a non-empty list -- that is (item rest...) | |
161 | ||
162 | // If the first item from the list is a symbol and it's "unquote" -- that | |
163 | // is, (unquote item ignored...): | |
164 | // | |
165 | // Return: item | |
166 | ||
167 | let qq_list = qq_arg as MalSequence | |
168 | if is_symbol(qq_list.first()) { | |
169 | let sym = qq_list.first() as MalSymbol | |
170 | if sym == kSymbolUnquote { | |
171 | return qq_list.count >= 2 ? qq_list[1] : MalNil() | |
172 | } | |
173 | } | |
174 | ||
175 | // If the first item from the list is itself a non-empty list starting with | |
176 | // "splice-unquote"-- that is, ((splice-unquote item ignored...) rest...): | |
177 | // | |
178 | // Return: (concat item quasiquote(rest...)) | |
179 | ||
180 | if is_pair(qq_list.first()) { | |
181 | let qq_list_item0 = qq_list.first() as MalSequence | |
182 | if is_symbol(qq_list_item0.first()) { | |
183 | let sym = qq_list_item0.first() as MalSymbol | |
184 | if sym == kSymbolSpliceUnquote { | |
185 | let result = quasiquote(qq_list.rest()) | |
186 | if is_error(result) { return result } | |
187 | return MalList(array: [kSymbolConcat, qq_list_item0[1], result]) | |
188 | } | |
189 | } | |
190 | } | |
191 | ||
192 | // General case: (item rest...): | |
193 | // | |
194 | // Return: (cons (quasiquote item) (quasiquote (rest...)) | |
195 | ||
196 | let first = quasiquote(qq_list.first()) | |
197 | if is_error(first) { return first } | |
198 | ||
199 | let rest = quasiquote(qq_list.rest()) | |
200 | if is_error(rest) { return rest } | |
201 | ||
202 | return MalList(objects: kSymbolCons, first, rest) | |
203 | } | |
204 | ||
205 | // Perform a simple evaluation of the `ast` object. If it's a symbol, | |
206 | // dereference it and return its value. If it's a collection, call EVAL on all | |
207 | // elements (or just the values, in the case of the hashmap). Otherwise, return | |
208 | // the object unchanged. | |
209 | // | |
210 | func eval_ast(ast: MalVal, env: Environment) -> MalVal { | |
211 | if is_symbol(ast) { | |
212 | let symbol = ast as MalSymbol | |
213 | if let val = env.get(symbol) { | |
214 | return val | |
215 | } | |
216 | return MalError(message: "'\(symbol)' not found") // Specific text needed to match MAL unit tests | |
217 | } | |
218 | if is_list(ast) { | |
219 | let list = ast as MalList | |
220 | var result = [MalVal]() | |
221 | result.reserveCapacity(list.count) | |
222 | for item in list { | |
223 | let eval = EVAL(item, env) | |
224 | if is_error(eval) { return eval } | |
225 | result.append(eval) | |
226 | } | |
227 | return MalList(array: result) | |
228 | } | |
229 | if is_vector(ast) { | |
230 | let vec = ast as MalVector | |
231 | var result = [MalVal]() | |
232 | result.reserveCapacity(vec.count) | |
233 | for item in vec { | |
234 | let eval = EVAL(item, env) | |
235 | if is_error(eval) { return eval } | |
236 | result.append(eval) | |
237 | } | |
238 | return MalVector(array: result) | |
239 | } | |
240 | if is_hashmap(ast) { | |
241 | let hash = ast as MalHashMap | |
242 | var result = [MalVal]() | |
243 | result.reserveCapacity(hash.count * 2) | |
244 | for (k, v) in hash { | |
245 | let new_v = EVAL(v, env) | |
246 | if is_error(new_v) { return new_v } | |
247 | result.append(k) | |
248 | result.append(new_v) | |
249 | } | |
250 | return MalHashMap(array: result) | |
251 | } | |
252 | return ast | |
253 | } | |
254 | ||
255 | // Walk the AST and completely evaluate it, handling macro expansions, special | |
256 | // forms and function calls. | |
257 | // | |
258 | func EVAL(var ast: MalVal, var env: Environment) -> MalVal { | |
2c4b8bd1 | 259 | let x = EVAL_Counter() |
2539e6af KR |
260 | if EVAL_level > EVAL_leval_max { |
261 | return MalError(message: "Recursing too many levels (> \(EVAL_leval_max))") | |
262 | } | |
263 | ||
2c4b8bd1 KR |
264 | if DEBUG_EVAL { |
265 | indent = prefix(INDENT_TEMPLATE, EVAL_level) | |
266 | } | |
2539e6af KR |
267 | |
268 | while true { | |
269 | if is_error(ast) { return ast } | |
270 | if DEBUG_EVAL { println("\(indent)> \(ast)") } | |
271 | ||
272 | // Special handling if it's a list. | |
273 | ||
274 | if is_list(ast) { | |
275 | var list = ast as MalList | |
276 | ast = macroexpand(ast, env) | |
277 | if !is_list(ast) { return ast } | |
278 | list = ast as MalList | |
279 | ||
280 | if DEBUG_EVAL { println("\(indent)>. \(list)") } | |
281 | ||
282 | if list.isEmpty { | |
283 | return ast | |
284 | } | |
285 | ||
286 | let arg1 = list.first() | |
287 | if is_symbol(arg1) { | |
288 | let fn_symbol = arg1 as MalSymbol | |
289 | ||
290 | // Check for special forms, where we want to check the operation | |
291 | // before evaluating all of the parameters. | |
292 | ||
293 | if fn_symbol == kSymbolDef || fn_symbol == kSymbolDefMacro { | |
294 | if list.count != 3 { | |
295 | return MalError(message: "expected 2 arguments to def!, got \(list.count - 1)") | |
296 | } | |
297 | let arg1 = list[1] | |
298 | let arg2 = list[2] | |
299 | if !is_symbol(arg1) { | |
300 | return MalError(message: "expected symbol for first argument to def!") | |
301 | } | |
302 | let sym = arg1 as MalSymbol | |
303 | let value = EVAL(arg2, env) | |
304 | if is_error(value) { return value } | |
305 | if fn_symbol == kSymbolDefMacro { | |
306 | if is_closure(value) { | |
307 | let as_closure = value as MalClosure | |
308 | as_closure.is_macro = true | |
309 | } else { | |
310 | return MalError(message: "expected closure, got \(value)") | |
311 | } | |
312 | } | |
313 | return env.set(sym, value) | |
314 | } else if fn_symbol == kSymbolLet { | |
315 | if list.count != 3 { | |
316 | return MalError(message: "expected 2 arguments to let*, got \(list.count - 1)") | |
317 | } | |
318 | let arg1 = list[1] | |
319 | let arg2 = list[2] | |
320 | if !is_sequence(arg1) { | |
321 | return MalError(message: "expected list for first argument to let*") | |
322 | } | |
323 | let bindings = arg1 as MalSequence | |
324 | if bindings.count % 2 == 1 { | |
325 | return MalError(message: "expected even number of elements in bindings to let*, got \(bindings.count)") | |
326 | } | |
327 | var new_env = Environment(outer: env) | |
328 | for var index = 0; index < bindings.count; index += 2 { | |
329 | let binding_name = bindings[index] | |
330 | let binding_value = bindings[index + 1] | |
331 | ||
332 | if !is_symbol(binding_name) { | |
333 | return MalError(message: "expected symbol for first element in binding pair") | |
334 | } | |
335 | let binding_symbol = binding_name as MalSymbol | |
336 | let evaluated_value = EVAL(binding_value, new_env) | |
337 | if is_error(evaluated_value) { return evaluated_value } | |
338 | new_env.set(binding_symbol, evaluated_value) | |
339 | } | |
340 | if TCO { | |
341 | env = new_env | |
342 | ast = arg2 | |
343 | continue | |
344 | } | |
345 | return EVAL(arg2, new_env) | |
346 | } else if fn_symbol == kSymbolDo { | |
347 | if TCO { | |
348 | let eval = eval_ast(MalList(slice: list[1..<list.count-1]), env) | |
349 | if is_error(eval) { return eval } | |
350 | ast = list.last() | |
351 | continue | |
352 | } | |
353 | ||
354 | let evaluated_ast = eval_ast(list.rest(), env) | |
355 | if is_error(evaluated_ast) { return evaluated_ast } | |
356 | let evaluated_seq = evaluated_ast as MalSequence | |
357 | return evaluated_seq.last() | |
358 | } else if fn_symbol == kSymbolIf { | |
359 | if list.count < 3 { | |
360 | return MalError(message: "expected at least 2 arguments to if, got \(list.count - 1)") | |
361 | } | |
362 | let cond_result = EVAL(list[1], env) | |
363 | var new_ast = MalVal() | |
364 | if is_truthy(cond_result) { | |
365 | new_ast = list[2] | |
366 | } else if list.count == 4 { | |
367 | new_ast = list[3] | |
368 | } else { | |
369 | return MalNil() | |
370 | } | |
371 | if TCO { | |
372 | ast = new_ast | |
373 | continue | |
374 | } | |
375 | return EVAL(new_ast, env) | |
376 | } else if fn_symbol == kSymbolFunction { | |
377 | if list.count != 3 { | |
378 | return MalError(message: "expected 2 arguments to fn*, got \(list.count - 1)") | |
379 | } | |
380 | if !is_sequence(list[1]) { | |
381 | return MalError(message: "expected list or vector for first argument to fn*") | |
382 | } | |
383 | return MalClosure(eval: EVAL, args:list[1] as MalSequence, body:list[2], env:env) | |
384 | } else if fn_symbol == kSymbolQuote { | |
385 | if list.count >= 2 { | |
386 | return list[1] | |
387 | } | |
388 | return MalNil() | |
389 | } else if fn_symbol == kSymbolQuasiquote { | |
390 | if list.count >= 2 { | |
391 | if TCO { | |
392 | ast = quasiquote(list[1]) | |
393 | continue | |
394 | } | |
395 | return EVAL(quasiquote(list[1]), env) | |
396 | } | |
397 | return MalError(message: "Expected non-nil parameter to 'quasiquote'") | |
398 | } else if fn_symbol == kSymbolMacroExpand { | |
399 | if list.count >= 2 { | |
400 | return macroexpand(list[1], env) | |
401 | } | |
402 | return MalError(message: "Expected parameter to 'macroexpand'") | |
403 | } | |
404 | } | |
405 | ||
406 | // Standard list to be applied. Evaluate all the elements first. | |
407 | ||
408 | let eval = eval_ast(ast, env) | |
409 | if is_error(eval) { return eval } | |
410 | ||
411 | // The result had better be a list and better be non-empty. | |
412 | ||
413 | let eval_list = eval as MalList | |
414 | if eval_list.isEmpty { | |
415 | return eval_list | |
416 | } | |
417 | ||
418 | if DEBUG_EVAL { println("\(indent)>> \(eval)") } | |
419 | ||
420 | // Get the first element of the list and execute it. | |
421 | ||
422 | let first = eval_list.first() | |
423 | let rest = eval_list.rest() | |
424 | ||
425 | if is_builtin(first) { | |
426 | let fn = first as MalBuiltin | |
427 | let answer = fn.apply(rest) | |
428 | if DEBUG_EVAL { println("\(indent)>>> \(answer)") } | |
429 | return answer | |
430 | } else if is_closure(first) { | |
431 | let fn = first as MalClosure | |
432 | var new_env = Environment(outer: fn.env) | |
433 | let result = new_env.set_bindings(fn.args, with_exprs:rest) | |
434 | if is_error(result) { return result } | |
435 | if TCO { | |
436 | env = new_env | |
437 | ast = fn.body | |
438 | continue | |
439 | } | |
440 | let answer = EVAL(fn.body, new_env) | |
441 | if DEBUG_EVAL { println("\(indent)>>> \(answer)") } | |
442 | return answer | |
443 | } | |
444 | ||
445 | // The first element wasn't a function to be executed. Return an | |
446 | // error saying so. | |
447 | ||
448 | return MalError(message: "first list item does not evaluate to a function: \(first)") | |
449 | } | |
450 | ||
451 | // Not a list -- just evaluate and return. | |
452 | ||
453 | let answer = eval_ast(ast, env) | |
454 | if DEBUG_EVAL { println("\(indent)>>> \(answer)") } | |
455 | return answer | |
456 | } | |
457 | } | |
458 | ||
459 | // Convert the value into a human-readable string for printing. | |
460 | // | |
461 | func PRINT(exp: MalVal) -> String? { | |
462 | if is_error(exp) { return nil } | |
463 | return pr_str(exp, true) | |
464 | } | |
465 | ||
466 | // Perform the READ and EVAL steps. Useful for when you don't care about the | |
467 | // printable result. | |
468 | // | |
469 | func RE(text: String, env: Environment) -> MalVal? { | |
470 | if text.isEmpty { return nil } | |
471 | let ast = READ(text) | |
472 | if is_error(ast) { | |
473 | println("Error parsing input: \(ast)") | |
474 | return nil | |
475 | } | |
476 | let exp = EVAL(ast, env) | |
477 | if is_error(exp) { | |
478 | println("Error evaluating input: \(exp)") | |
479 | return nil | |
480 | } | |
481 | return exp | |
482 | } | |
483 | ||
484 | // Perform the full READ/EVAL/PRINT, returning a printable string. | |
485 | // | |
486 | func REP(text: String, env: Environment) -> String? { | |
487 | let exp = RE(text, env) | |
488 | if exp == nil { return nil } | |
489 | return PRINT(exp!) | |
490 | } | |
491 | ||
492 | // Perform the full REPL. | |
493 | // | |
494 | func REPL(env: Environment) { | |
495 | while true { | |
496 | if let text = _readline("user> ") { | |
497 | if let output = REP(text, env) { | |
498 | println("\(output)") | |
499 | } | |
500 | } else { | |
501 | println() | |
502 | break | |
503 | } | |
504 | } | |
505 | } | |
506 | ||
507 | // Process any command line arguments. Any trailing arguments are incorporated | |
508 | // into the environment. Any argument immediately after the process name is | |
509 | // taken as a script to execute. If one exists, it is executed in lieu of | |
510 | // running the REPL. | |
511 | // | |
512 | func process_command_line(args:[String], env:Environment) -> Bool { | |
513 | var argv = MalList() | |
514 | if args.count > 2 { | |
515 | let args1 = args[2..<args.count] | |
516 | let args2 = args1.map { MalString(unescaped: $0) as MalVal } | |
517 | let args3 = [MalVal](args2) | |
518 | argv = MalList(array: args3) | |
519 | } | |
520 | env.set(kSymbolArgv, argv) | |
521 | ||
522 | if args.count > 1 { | |
523 | RE("(load-file \"\(args[1])\")", env) | |
524 | return false | |
525 | } | |
526 | ||
527 | return true | |
528 | } | |
529 | ||
530 | func main() { | |
531 | var env = Environment(outer: nil) | |
532 | ||
533 | load_history_file() | |
534 | load_builtins(env) | |
535 | ||
536 | RE("(def! not (fn* (a) (if a false true)))", env) | |
537 | RE("(def! load-file (fn* (f) (eval (read-string (str \"(do \" (slurp f) \")\")))))", env) | |
538 | RE("(defmacro! cond (fn* (& xs) (if (> (count xs) 0) (list 'if (first xs) (if (> (count xs) 1) (nth xs 1) " + | |
539 | "(throw \"odd number of forms to cond\")) (cons 'cond (rest (rest xs)))))))", env) | |
540 | RE("(defmacro! or (fn* (& xs) (if (empty? xs) nil (if (= 1 (count xs)) (first xs) " + | |
541 | "`(let* (or_FIXME ~(first xs)) (if or_FIXME or_FIXME (or ~@(rest xs))))))))", env) | |
542 | ||
543 | env.set(kSymbolEval, MalBuiltin(function: { | |
544 | unwrap($0) { | |
545 | (ast:MalVal) -> MalVal in | |
546 | EVAL(ast, env) | |
547 | } | |
548 | })) | |
549 | ||
550 | if process_command_line(Process.arguments, env) { | |
551 | REPL(env) | |
552 | } | |
553 | ||
554 | save_history_file() | |
555 | } |