Merge pull request #378 from asarhaddon/test-macro-not-changing-function
[jackhill/mal.git] / swift / step9_try.swift
1 //******************************************************************************
2 // MAL - step 9 - try
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 private 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 private 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 private let TCO = true
28
29 // Control whether or not we emit debugging statements in EVAL.
30 //
31 private let DEBUG_EVAL = false
32
33 // String used to prefix information logged in EVAL. Increasing lengths of the
34 // string are used the more EVAL is recursed.
35 //
36 private let INDENT_TEMPLATE = "|----|----|----|----|----|----|----|----|" +
37 "----|----|----|----|----|----|----|----|----|----|----|" +
38 "----|----|----|----|----|----|----|----|----|----|----|" +
39 "----|----|----|----|----|----|----|----|----|----|----|" +
40 "----|----|----|----|----|----|----|----|----|----|----|" +
41 "----|----|----|----|----|----|----|----|----|----|----|" +
42 "----|----|----|----|----|----|----|----|----|----|----|" +
43 "----|----|----|----|----|----|----|----|----|----|----|" +
44 "----|----|----|----|----|----|----|----|----|----|----|" +
45 "----|----|----|----|----|----|----|----|----|----|----|" +
46 "----|----|----|----|----|----|----|----|----|----|----|"
47
48 // Holds the prefix of INDENT_TEMPLATE used for actual logging.
49 //
50 private var indent = String()
51
52 // Symbols used in this module.
53 //
54 private let kValArgv = make_symbol("*ARGV*")
55 private let kValCatch = make_symbol("catch*")
56 private let kValConcat = make_symbol("concat")
57 private let kValCons = make_symbol("cons")
58 private let kValDef = make_symbol("def!")
59 private let kValDefMacro = make_symbol("defmacro!")
60 private let kValDo = make_symbol("do")
61 private let kValEval = make_symbol("eval")
62 private let kValFn = make_symbol("fn*")
63 private let kValIf = make_symbol("if")
64 private let kValLet = make_symbol("let*")
65 private let kValMacroExpand = make_symbol("macroexpand")
66 private let kValQuasiQuote = make_symbol("quasiquote")
67 private let kValQuote = make_symbol("quote")
68 private let kValSpliceUnquote = make_symbol("splice-unquote")
69 private let kValUnquote = make_symbol("unquote")
70 private let kValTry = make_symbol("try*")
71
72 private let kSymbolArgv = as_symbol(kValArgv)
73 private let kSymbolCatch = as_symbol(kValCatch)
74 private let kSymbolConcat = as_symbol(kValConcat)
75 private let kSymbolCons = as_symbol(kValCons)
76 private let kSymbolDef = as_symbol(kValDef)
77 private let kSymbolDefMacro = as_symbol(kValDefMacro)
78 private let kSymbolDo = as_symbol(kValDo)
79 private let kSymbolEval = as_symbol(kValEval)
80 private let kSymbolFn = as_symbol(kValFn)
81 private let kSymbolIf = as_symbol(kValIf)
82 private let kSymbolLet = as_symbol(kValLet)
83 private let kSymbolMacroExpand = as_symbol(kValMacroExpand)
84 private let kSymbolQuasiQuote = as_symbol(kValQuasiQuote)
85 private let kSymbolQuote = as_symbol(kValQuote)
86 private let kSymbolSpliceUnquote = as_symbol(kValSpliceUnquote)
87 private let kSymbolUnquote = as_symbol(kValUnquote)
88 private let kSymbolTry = as_symbol(kValTry)
89
90 func substring(s: String, _ begin: Int, _ end: Int) -> String {
91 return s[s.startIndex.advancedBy(begin) ..< s.startIndex.advancedBy(end)]
92 }
93
94 // Parse the string into an AST.
95 //
96 private func READ(str: String) throws -> MalVal {
97 return try read_str(str)
98 }
99
100 // Return whether or not `val` is a non-empty list.
101 //
102 private func is_pair(val: MalVal) -> Bool {
103 if let seq = as_sequenceQ(val) {
104 return !seq.isEmpty
105 }
106 return false
107 }
108
109 // Expand macros for as long as the expression looks like a macro invocation.
110 //
111 private func macroexpand(var ast: MalVal, _ env: Environment) throws -> MalVal {
112 while true {
113 if let ast_as_list = as_listQ(ast) where !ast_as_list.isEmpty,
114 let macro_name = as_symbolQ(ast_as_list.first()),
115 let obj = env.get(macro_name),
116 let macro = as_macroQ(obj)
117 {
118 let new_env = Environment(outer: macro.env)
119 let rest = as_sequence(ast_as_list.rest())
120 let _ = try new_env.set_bindings(macro.args, with_exprs: rest)
121 ast = try EVAL(macro.body, new_env)
122 continue
123 }
124 return ast
125 }
126 }
127
128 // Evaluate `quasiquote`, possibly recursing in the process.
129 //
130 // As with quote, unquote, and splice-unquote, quasiquote takes a single
131 // parameter, typically a list. In the general case, this list is processed
132 // recursively as:
133 //
134 // (quasiquote (first rest...)) -> (cons (quasiquote first) (quasiquote rest))
135 //
136 // In the processing of the parameter passed to it, quasiquote handles three
137 // special cases:
138 //
139 // * If the parameter is an atom or an empty list, the following expression
140 // is formed and returned for evaluation:
141 //
142 // (quasiquote atom-or-empty-list) -> (quote atom-or-empty-list)
143 //
144 // * If the first element of the non-empty list is the symbol "unquote"
145 // followed by a second item, the second item is returned as-is:
146 //
147 // (quasiquote (unquote fred)) -> fred
148 //
149 // * If the first element of the non-empty list is another list containing
150 // the symbol "splice-unquote" followed by a list, that list is catenated
151 // with the quasiquoted result of the remaining items in the non-empty
152 // parent list:
153 //
154 // (quasiquote (splice-unquote list) rest...) -> (items-from-list items-from-quasiquote(rest...))
155 //
156 // Note the inconsistent handling between "quote" and "splice-quote". The former
157 // is handled when this function is handed a list that starts with "quote",
158 // whereas the latter is handled when this function is handled a list whose
159 // first element is a list that starts with "splice-quote". The handling of the
160 // latter is forced by the need to incorporate the results of (splice-quote
161 // list) with the remaining items of the list containing that splice-quote
162 // expression. However, it's not clear to me why the handling of "unquote" is
163 // not handled similarly, for consistency's sake.
164 //
165 private func quasiquote(qq_arg: MalVal) throws -> MalVal {
166
167 // If the argument is an atom or empty list:
168 //
169 // Return: (quote <argument>)
170
171 if !is_pair(qq_arg) {
172 return make_list_from(kValQuote, qq_arg)
173 }
174
175 // The argument is a non-empty list -- that is (item rest...)
176
177 // If the first item from the list is a symbol and it's "unquote" -- that
178 // is, (unquote item ignored...):
179 //
180 // Return: item
181
182 let qq_list = as_sequence(qq_arg)
183 if let sym = as_symbolQ(qq_list.first()) where sym == kSymbolUnquote {
184 return qq_list.count >= 2 ? try! qq_list.nth(1) : make_nil()
185 }
186
187 // If the first item from the list is itself a non-empty list starting with
188 // "splice-unquote"-- that is, ((splice-unquote item ignored...) rest...):
189 //
190 // Return: (concat item quasiquote(rest...))
191
192 if is_pair(qq_list.first()) {
193 let qq_list_item0 = as_sequence(qq_list.first())
194 if let sym = as_symbolQ(qq_list_item0.first()) where sym == kSymbolSpliceUnquote {
195 let result = try quasiquote(qq_list.rest())
196 return make_list_from(kValConcat, try! qq_list_item0.nth(1), result)
197 }
198 }
199
200 // General case: (item rest...):
201 //
202 // Return: (cons (quasiquote item) (quasiquote (rest...))
203
204 let first = try quasiquote(qq_list.first())
205 let rest = try quasiquote(qq_list.rest())
206 return make_list_from(kValCons, first, rest)
207 }
208
209 // Perform a simple evaluation of the `ast` object. If it's a symbol,
210 // dereference it and return its value. If it's a collection, call EVAL on all
211 // elements (or just the values, in the case of the hashmap). Otherwise, return
212 // the object unchanged.
213 //
214 private func eval_ast(ast: MalVal, _ env: Environment) throws -> MalVal {
215 if let symbol = as_symbolQ(ast) {
216 guard let val = env.get(symbol) else {
217 try throw_error("'\(symbol)' not found") // Specific text needed to match MAL unit tests
218 }
219 return val
220 }
221 if let list = as_listQ(ast) {
222 var result = [MalVal]()
223 result.reserveCapacity(Int(list.count))
224 for item in list {
225 let eval = try EVAL(item, env)
226 result.append(eval)
227 }
228 return make_list(result)
229 }
230 if let vec = as_vectorQ(ast) {
231 var result = [MalVal]()
232 result.reserveCapacity(Int(vec.count))
233 for item in vec {
234 let eval = try EVAL(item, env)
235 result.append(eval)
236 }
237 return make_vector(result)
238 }
239 if let hash = as_hashmapQ(ast) {
240 var result = [MalVal]()
241 result.reserveCapacity(Int(hash.count) * 2)
242 for (k, v) in hash {
243 let new_v = try EVAL(v, env)
244 result.append(k)
245 result.append(new_v)
246 }
247 return make_hashmap(result)
248 }
249 return ast
250 }
251
252 private enum TCOVal {
253 case NoResult
254 case Return(MalVal)
255 case Continue(MalVal, Environment)
256
257 init() { self = .NoResult }
258 init(_ result: MalVal) { self = .Return(result) }
259 init(_ ast: MalVal, _ env: Environment) { self = .Continue(ast, env) }
260 }
261
262 // EVALuate "def!" and "defmacro!".
263 //
264 private func eval_def(list: MalSequence, _ env: Environment) throws -> TCOVal {
265 guard list.count == 3 else {
266 try throw_error("expected 2 arguments to def!, got \(list.count - 1)")
267 }
268 let arg0 = try! list.nth(0)
269 let arg1 = try! list.nth(1)
270 let arg2 = try! list.nth(2)
271 guard let sym = as_symbolQ(arg1) else {
272 try throw_error("expected symbol for first argument to def!")
273 }
274 var value = try EVAL(arg2, env)
275 if as_symbol(arg0) == kSymbolDefMacro {
276 guard let closure = as_closureQ(value) else {
277 try throw_error("expected closure, got \(value)")
278 }
279 value = make_macro(closure)
280 }
281 return TCOVal(env.set(sym, value))
282 }
283
284 // EVALuate "let*".
285 //
286 private func eval_let(list: MalSequence, _ env: Environment) throws -> TCOVal {
287 guard list.count == 3 else {
288 try throw_error("expected 2 arguments to let*, got \(list.count - 1)")
289 }
290 let arg1 = try! list.nth(1)
291 let arg2 = try! list.nth(2)
292 guard let bindings = as_sequenceQ(arg1) else {
293 try throw_error("expected list for first argument to let*")
294 }
295 guard bindings.count % 2 == 0 else {
296 try throw_error("expected even number of elements in bindings to let*, got \(bindings.count)")
297 }
298 let new_env = Environment(outer: env)
299 for var index: MalIntType = 0; index < bindings.count; index += 2 {
300 let binding_name = try! bindings.nth(index)
301 let binding_value = try! bindings.nth(index + 1)
302 guard let binding_symbol = as_symbolQ(binding_name) else {
303 try throw_error("expected symbol for first element in binding pair")
304 }
305 let evaluated_value = try EVAL(binding_value, new_env)
306 new_env.set(binding_symbol, evaluated_value)
307 }
308 if TCO {
309 return TCOVal(arg2, new_env)
310 }
311 return TCOVal(try EVAL(arg2, new_env))
312 }
313
314 // EVALuate "do".
315 //
316 private func eval_do(list: MalSequence, _ env: Environment) throws -> TCOVal {
317 if TCO {
318 let _ = try eval_ast(list.range_from(1, to: list.count-1), env)
319 return TCOVal(list.last(), env)
320 }
321
322 let evaluated_ast = try eval_ast(list.rest(), env)
323 let evaluated_seq = as_sequence(evaluated_ast)
324 return TCOVal(evaluated_seq.last())
325 }
326
327 // EVALuate "if".
328 //
329 private func eval_if(list: MalSequence, _ env: Environment) throws -> TCOVal {
330 guard list.count >= 3 else {
331 try throw_error("expected at least 2 arguments to if, got \(list.count - 1)")
332 }
333 let cond_result = try EVAL(try! list.nth(1), env)
334 var new_ast: MalVal
335 if is_truthy(cond_result) {
336 new_ast = try! list.nth(2)
337 } else if list.count == 4 {
338 new_ast = try! list.nth(3)
339 } else {
340 return TCOVal(make_nil())
341 }
342 if TCO {
343 return TCOVal(new_ast, env)
344 }
345 return TCOVal(try EVAL(new_ast, env))
346 }
347
348 // EVALuate "fn*".
349 //
350 private func eval_fn(list: MalSequence, _ env: Environment) throws -> TCOVal {
351 guard list.count == 3 else {
352 try throw_error("expected 2 arguments to fn*, got \(list.count - 1)")
353 }
354 guard let seq = as_sequenceQ(try! list.nth(1)) else {
355 try throw_error("expected list or vector for first argument to fn*")
356 }
357 return TCOVal(make_closure((eval: EVAL, args: seq, body: try! list.nth(2), env: env)))
358 }
359
360 // EVALuate "quote".
361 //
362 private func eval_quote(list: MalSequence, _ env: Environment) throws -> TCOVal {
363 if list.count >= 2 {
364 return TCOVal(try! list.nth(1))
365 }
366 return TCOVal(make_nil())
367 }
368
369 // EVALuate "quasiquote".
370 //
371 private func eval_quasiquote(list: MalSequence, _ env: Environment) throws -> TCOVal {
372 guard list.count >= 2 else {
373 try throw_error("Expected non-nil parameter to 'quasiquote'")
374 }
375 if TCO {
376 return TCOVal(try quasiquote(try! list.nth(1)), env)
377 }
378 return TCOVal(try EVAL(try quasiquote(try! list.nth(1)), env))
379 }
380
381 // EVALuate "macroexpand".
382 //
383 private func eval_macroexpand(list: MalSequence, _ env: Environment) throws -> TCOVal {
384 guard list.count >= 2 else {
385 try throw_error("Expected parameter to 'macroexpand'")
386 }
387 return TCOVal(try macroexpand(try! list.nth(1), env))
388 }
389
390 // EVALuate "try*" (and "catch*").
391 //
392 private func eval_try(list: MalSequence, _ env: Environment) throws -> TCOVal {
393 // This is a subset of the Clojure try/catch:
394 //
395 // (try* expr (catch exception-name expr))
396
397 guard list.count >= 2 else {
398 try throw_error("try*: no body parameter")
399 }
400
401 do {
402 return TCOVal(try EVAL(try! list.nth(1), env))
403 } catch let error as MalException {
404 guard list.count >= 3,
405 let catch_list = as_sequenceQ(try! list.nth(2)) where catch_list.count >= 3,
406 let _ = as_symbolQ(try! catch_list.nth(0)) else
407 {
408 throw error // No catch parameter
409 }
410 let catch_name = try! catch_list.nth(1)
411 let catch_expr = try! catch_list.nth(2)
412 let catch_env = Environment(outer: env)
413 try catch_env.set_bindings(as_sequence(make_list_from(catch_name)),
414 with_exprs: as_sequence(make_list_from(error.exception)))
415 return TCOVal(try EVAL(catch_expr, catch_env))
416 }
417 }
418
419 // Walk the AST and completely evaluate it, handling macro expansions, special
420 // forms and function calls.
421 //
422 private func EVAL(var ast: MalVal, var _ env: Environment) throws -> MalVal {
423 EVAL_level++
424 defer { EVAL_level-- }
425 guard EVAL_level <= EVAL_leval_max else {
426 try throw_error("Recursing too many levels (> \(EVAL_leval_max))")
427 }
428
429 if DEBUG_EVAL {
430 indent = substring(INDENT_TEMPLATE, 0, EVAL_level)
431 }
432
433 while true {
434 if DEBUG_EVAL { print("\(indent)> \(ast)") }
435
436 if !is_list(ast) {
437
438 // Not a list -- just evaluate and return.
439
440 let answer = try eval_ast(ast, env)
441 if DEBUG_EVAL { print("\(indent)>>> \(answer)") }
442 return answer
443 }
444
445 // Special handling if it's a list.
446
447 var list = as_list(ast)
448 ast = try macroexpand(ast, env)
449 if !is_list(ast) {
450
451 // Not a list -- just evaluate and return.
452
453 let answer = try eval_ast(ast, env)
454 if DEBUG_EVAL { print("\(indent)>>> \(answer)") }
455 return answer
456 }
457 list = as_list(ast)
458
459 if DEBUG_EVAL { print("\(indent)>. \(list)") }
460
461 if list.isEmpty {
462 return ast
463 }
464
465 // Check for special forms, where we want to check the operation
466 // before evaluating all of the parameters.
467
468 let arg0 = list.first()
469 if let fn_symbol = as_symbolQ(arg0) {
470 let res: TCOVal
471
472 switch fn_symbol {
473 case kSymbolDef: res = try eval_def(list, env)
474 case kSymbolDefMacro: res = try eval_def(list, env)
475 case kSymbolLet: res = try eval_let(list, env)
476 case kSymbolDo: res = try eval_do(list, env)
477 case kSymbolIf: res = try eval_if(list, env)
478 case kSymbolFn: res = try eval_fn(list, env)
479 case kSymbolQuote: res = try eval_quote(list, env)
480 case kSymbolQuasiQuote: res = try eval_quasiquote(list, env)
481 case kSymbolMacroExpand: res = try eval_macroexpand(list, env)
482 case kSymbolTry: res = try eval_try(list, env)
483 default: res = TCOVal()
484 }
485 switch res {
486 case let .Return(result): return result
487 case let .Continue(new_ast, new_env): ast = new_ast; env = new_env; continue
488 case .NoResult: break
489 }
490 }
491
492 // Standard list to be applied. Evaluate all the elements first.
493
494 let eval = try eval_ast(ast, env)
495
496 // The result had better be a list and better be non-empty.
497
498 let eval_list = as_list(eval)
499 if eval_list.isEmpty {
500 return eval
501 }
502
503 if DEBUG_EVAL { print("\(indent)>> \(eval)") }
504
505 // Get the first element of the list and execute it.
506
507 let first = eval_list.first()
508 let rest = as_sequence(eval_list.rest())
509
510 if let fn = as_builtinQ(first) {
511 let answer = try fn.apply(rest)
512 if DEBUG_EVAL { print("\(indent)>>> \(answer)") }
513 return answer
514 } else if let fn = as_closureQ(first) {
515 let new_env = Environment(outer: fn.env)
516 let _ = try new_env.set_bindings(fn.args, with_exprs: rest)
517 if TCO {
518 env = new_env
519 ast = fn.body
520 continue
521 }
522 let answer = try EVAL(fn.body, new_env)
523 if DEBUG_EVAL { print("\(indent)>>> \(answer)") }
524 return answer
525 }
526
527 // The first element wasn't a function to be executed. Return an
528 // error saying so.
529
530 try throw_error("first list item does not evaluate to a function: \(first)")
531 }
532 }
533
534 // Convert the value into a human-readable string for printing.
535 //
536 private func PRINT(exp: MalVal) -> String {
537 return pr_str(exp, true)
538 }
539
540 // Perform the READ and EVAL steps. Useful for when you don't care about the
541 // printable result.
542 //
543 private func RE(text: String, _ env: Environment) -> MalVal? {
544 if !text.isEmpty {
545 do {
546 let ast = try READ(text)
547 do {
548 return try EVAL(ast, env)
549 } catch let error as MalException {
550 print("Error evaluating input: \(error)")
551 } catch {
552 print("Error evaluating input: \(error)")
553 }
554 } catch let error as MalException {
555 print("Error parsing input: \(error)")
556 } catch {
557 print("Error parsing input: \(error)")
558 }
559 }
560 return nil
561 }
562
563 // Perform the full READ/EVAL/PRINT, returning a printable string.
564 //
565 private func REP(text: String, _ env: Environment) -> String? {
566 let exp = RE(text, env)
567 if exp == nil { return nil }
568 return PRINT(exp!)
569 }
570
571 // Perform the full REPL.
572 //
573 private func REPL(env: Environment) {
574 while true {
575 if let text = _readline("user> ") {
576 if let output = REP(text, env) {
577 print("\(output)")
578 }
579 } else {
580 print("")
581 break
582 }
583 }
584 }
585
586 // Process any command line arguments. Any trailing arguments are incorporated
587 // into the environment. Any argument immediately after the process name is
588 // taken as a script to execute. If one exists, it is executed in lieu of
589 // running the REPL.
590 //
591 private func process_command_line(args: [String], _ env: Environment) -> Bool {
592 var argv = make_list()
593 if args.count > 2 {
594 let args1 = args[2..<args.count]
595 let args2 = args1.map { make_string($0) }
596 let args3 = [MalVal](args2)
597 argv = make_list(args3)
598 }
599 env.set(kSymbolArgv, argv)
600
601 if args.count > 1 {
602 RE("(load-file \"\(args[1])\")", env)
603 return false
604 }
605
606 return true
607 }
608
609 func main() {
610 let env = Environment(outer: nil)
611
612 load_history_file()
613 load_builtins(env)
614
615 RE("(def! not (fn* (a) (if a false true)))", env)
616 RE("(def! load-file (fn* (f) (eval (read-string (str \"(do \" (slurp f) \")\")))))", env)
617 RE("(defmacro! cond (fn* (& xs) (if (> (count xs) 0) (list 'if (first xs) (if (> (count xs) 1) (nth xs 1) " +
618 "(throw \"odd number of forms to cond\")) (cons 'cond (rest (rest xs)))))))", env)
619 RE("(defmacro! or (fn* (& xs) (if (empty? xs) nil (if (= 1 (count xs)) (first xs) " +
620 "`(let* (or_FIXME ~(first xs)) (if or_FIXME or_FIXME (or ~@(rest xs))))))))", env)
621
622 env.set(kSymbolEval, make_builtin({
623 try! unwrap_args($0) {
624 (ast: MalVal) -> MalVal in
625 try EVAL(ast, env)
626 }
627 }))
628
629 if process_command_line(Process.arguments, env) {
630 REPL(env)
631 }
632
633 save_history_file()
634 }