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 //******************************************************************************
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.
15 private var EVAL_level = 0
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
21 private let EVAL_leval_max = 500
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).
27 private let TCO = true
29 // Control whether or not we emit debugging statements in EVAL.
31 private let DEBUG_EVAL = false
33 // String used to prefix information logged in EVAL. Increasing lengths of the
34 // string are used the more EVAL is recursed.
36 private let INDENT_TEMPLATE = "|----|----|----|----|----|----|----|----|" +
37 "----|----|----|----|----|----|----|----|----|----|----|" +
38 "----|----|----|----|----|----|----|----|----|----|----|" +
39 "----|----|----|----|----|----|----|----|----|----|----|" +
40 "----|----|----|----|----|----|----|----|----|----|----|" +
41 "----|----|----|----|----|----|----|----|----|----|----|" +
42 "----|----|----|----|----|----|----|----|----|----|----|" +
43 "----|----|----|----|----|----|----|----|----|----|----|" +
44 "----|----|----|----|----|----|----|----|----|----|----|" +
45 "----|----|----|----|----|----|----|----|----|----|----|" +
46 "----|----|----|----|----|----|----|----|----|----|----|"
48 // Holds the prefix of INDENT_TEMPLATE used for actual logging.
50 private var indent = String()
52 // Symbols used in this module.
54 private let kValArgv = make_symbol("*ARGV*")
55 private let kValConcat = make_symbol("concat")
56 private let kValCons = make_symbol("cons")
57 private let kValDef = make_symbol("def!")
58 private let kValDefMacro = make_symbol("defmacro!")
59 private let kValDo = make_symbol("do")
60 private let kValEval = make_symbol("eval")
61 private let kValFn = make_symbol("fn*")
62 private let kValIf = make_symbol("if")
63 private let kValLet = make_symbol("let*")
64 private let kValMacroExpand = make_symbol("macroexpand")
65 private let kValQuasiQuote = make_symbol("quasiquote")
66 private let kValQuote = make_symbol("quote")
67 private let kValSpliceUnquote = make_symbol("splice-unquote")
68 private let kValUnquote = make_symbol("unquote")
69 private let kValTry = make_symbol("try*")
71 private let kSymbolArgv = as_symbol(kValArgv)
72 private let kSymbolConcat = as_symbol(kValConcat)
73 private let kSymbolCons = as_symbol(kValCons)
74 private let kSymbolDef = as_symbol(kValDef)
75 private let kSymbolDefMacro = as_symbol(kValDefMacro)
76 private let kSymbolDo = as_symbol(kValDo)
77 private let kSymbolEval = as_symbol(kValEval)
78 private let kSymbolFn = as_symbol(kValFn)
79 private let kSymbolIf = as_symbol(kValIf)
80 private let kSymbolLet = as_symbol(kValLet)
81 private let kSymbolMacroExpand = as_symbol(kValMacroExpand)
82 private let kSymbolQuasiQuote = as_symbol(kValQuasiQuote)
83 private let kSymbolQuote = as_symbol(kValQuote)
84 private let kSymbolSpliceUnquote = as_symbol(kValSpliceUnquote)
85 private let kSymbolUnquote = as_symbol(kValUnquote)
87 func substring(s: String, _ begin: Int, _ end: Int) -> String {
88 return s[s.startIndex.advancedBy(begin) ..< s.startIndex.advancedBy(end)]
91 // Parse the string into an AST.
93 private func READ(str: String) throws -> MalVal {
94 return try read_str(str)
97 // Return whether or not `val` is a non-empty list.
99 private func is_pair(val: MalVal) -> Bool {
100 if let seq = as_sequenceQ(val) {
106 // Expand macros for as long as the expression looks like a macro invocation.
108 private func macroexpand(var ast: MalVal, _ env: Environment) throws -> MalVal {
110 if let ast_as_list = as_listQ(ast) where !ast_as_list.isEmpty,
111 let macro_name = as_symbolQ(ast_as_list.first()),
112 let obj = env.get(macro_name),
113 let macro = as_macroQ(obj)
115 let new_env = Environment(outer: macro.env)
116 let rest = as_sequence(ast_as_list.rest())
117 let _ = try new_env.set_bindings(macro.args, with_exprs: rest)
118 ast = try EVAL(macro.body, new_env)
125 // Evaluate `quasiquote`, possibly recursing in the process.
127 // As with quote, unquote, and splice-unquote, quasiquote takes a single
128 // parameter, typically a list. In the general case, this list is processed
131 // (quasiquote (first rest...)) -> (cons (quasiquote first) (quasiquote rest))
133 // In the processing of the parameter passed to it, quasiquote handles three
136 // * If the parameter is an atom or an empty list, the following expression
137 // is formed and returned for evaluation:
139 // (quasiquote atom-or-empty-list) -> (quote atom-or-empty-list)
141 // * If the first element of the non-empty list is the symbol "unquote"
142 // followed by a second item, the second item is returned as-is:
144 // (quasiquote (unquote fred)) -> fred
146 // * If the first element of the non-empty list is another list containing
147 // the symbol "splice-unquote" followed by a list, that list is catenated
148 // with the quasiquoted result of the remaining items in the non-empty
151 // (quasiquote (splice-unquote list) rest...) -> (items-from-list items-from-quasiquote(rest...))
153 // Note the inconsistent handling between "quote" and "splice-quote". The former
154 // is handled when this function is handed a list that starts with "quote",
155 // whereas the latter is handled when this function is handled a list whose
156 // first element is a list that starts with "splice-quote". The handling of the
157 // latter is forced by the need to incorporate the results of (splice-quote
158 // list) with the remaining items of the list containing that splice-quote
159 // expression. However, it's not clear to me why the handling of "unquote" is
160 // not handled similarly, for consistency's sake.
162 private func quasiquote(qq_arg: MalVal) throws -> MalVal {
164 // If the argument is an atom or empty list:
166 // Return: (quote <argument>)
168 if !is_pair(qq_arg) {
169 return make_list_from(kValQuote, qq_arg)
172 // The argument is a non-empty list -- that is (item rest...)
174 // If the first item from the list is a symbol and it's "unquote" -- that
175 // is, (unquote item ignored...):
179 let qq_list = as_sequence(qq_arg)
180 if let sym = as_symbolQ(qq_list.first()) where sym == kSymbolUnquote {
181 return qq_list.count >= 2 ? try! qq_list.nth(1) : make_nil()
184 // If the first item from the list is itself a non-empty list starting with
185 // "splice-unquote"-- that is, ((splice-unquote item ignored...) rest...):
187 // Return: (concat item quasiquote(rest...))
189 if is_pair(qq_list.first()) {
190 let qq_list_item0 = as_sequence(qq_list.first())
191 if let sym = as_symbolQ(qq_list_item0.first()) where sym == kSymbolSpliceUnquote {
192 let result = try quasiquote(qq_list.rest())
193 return make_list_from(kValConcat, try! qq_list_item0.nth(1), result)
197 // General case: (item rest...):
199 // Return: (cons (quasiquote item) (quasiquote (rest...))
201 let first = try quasiquote(qq_list.first())
202 let rest = try quasiquote(qq_list.rest())
203 return make_list_from(kValCons, first, rest)
206 // Perform a simple evaluation of the `ast` object. If it's a symbol,
207 // dereference it and return its value. If it's a collection, call EVAL on all
208 // elements (or just the values, in the case of the hashmap). Otherwise, return
209 // the object unchanged.
211 private func eval_ast(ast: MalVal, _ env: Environment) throws -> MalVal {
212 if let symbol = as_symbolQ(ast) {
213 guard let val = env.get(symbol) else {
214 try throw_error("'\(symbol)' not found") // Specific text needed to match MAL unit tests
218 if let list = as_listQ(ast) {
219 var result = [MalVal]()
220 result.reserveCapacity(Int(list.count))
222 let eval = try EVAL(item, env)
225 return make_list(result)
227 if let vec = as_vectorQ(ast) {
228 var result = [MalVal]()
229 result.reserveCapacity(Int(vec.count))
231 let eval = try EVAL(item, env)
234 return make_vector(result)
236 if let hash = as_hashmapQ(ast) {
237 var result = [MalVal]()
238 result.reserveCapacity(Int(hash.count) * 2)
240 let new_v = try EVAL(v, env)
244 return make_hashmap(result)
249 private enum TCOVal {
252 case Continue(MalVal, Environment)
254 init() { self = .NoResult }
255 init(_ result: MalVal) { self = .Return(result) }
256 init(_ ast: MalVal, _ env: Environment) { self = .Continue(ast, env) }
259 // EVALuate "def!" and "defmacro!".
261 private func eval_def(list: MalSequence, _ env: Environment) throws -> TCOVal {
262 guard list.count == 3 else {
263 try throw_error("expected 2 arguments to def!, got \(list.count - 1)")
265 let arg0 = try! list.nth(0)
266 let arg1 = try! list.nth(1)
267 let arg2 = try! list.nth(2)
268 guard let sym = as_symbolQ(arg1) else {
269 try throw_error("expected symbol for first argument to def!")
271 var value = try EVAL(arg2, env)
272 if as_symbol(arg0) == kSymbolDefMacro {
273 guard let closure = as_closureQ(value) else {
274 try throw_error("expected closure, got \(value)")
276 value = make_macro(closure)
278 return TCOVal(env.set(sym, value))
283 private func eval_let(list: MalSequence, _ env: Environment) throws -> TCOVal {
284 guard list.count == 3 else {
285 try throw_error("expected 2 arguments to let*, got \(list.count - 1)")
287 let arg1 = try! list.nth(1)
288 let arg2 = try! list.nth(2)
289 guard let bindings = as_sequenceQ(arg1) else {
290 try throw_error("expected list for first argument to let*")
292 guard bindings.count % 2 == 0 else {
293 try throw_error("expected even number of elements in bindings to let*, got \(bindings.count)")
295 let new_env = Environment(outer: env)
296 for var index: MalIntType = 0; index < bindings.count; index += 2 {
297 let binding_name = try! bindings.nth(index)
298 let binding_value = try! bindings.nth(index + 1)
299 guard let binding_symbol = as_symbolQ(binding_name) else {
300 try throw_error("expected symbol for first element in binding pair")
302 let evaluated_value = try EVAL(binding_value, new_env)
303 new_env.set(binding_symbol, evaluated_value)
306 return TCOVal(arg2, new_env)
308 return TCOVal(try EVAL(arg2, new_env))
313 private func eval_do(list: MalSequence, _ env: Environment) throws -> TCOVal {
315 let _ = try eval_ast(list.range_from(1, to: list.count-1), env)
316 return TCOVal(list.last(), env)
319 let evaluated_ast = try eval_ast(list.rest(), env)
320 let evaluated_seq = as_sequence(evaluated_ast)
321 return TCOVal(evaluated_seq.last())
326 private func eval_if(list: MalSequence, _ env: Environment) throws -> TCOVal {
327 guard list.count >= 3 else {
328 try throw_error("expected at least 2 arguments to if, got \(list.count - 1)")
330 let cond_result = try EVAL(try! list.nth(1), env)
332 if is_truthy(cond_result) {
333 new_ast = try! list.nth(2)
334 } else if list.count == 4 {
335 new_ast = try! list.nth(3)
337 return TCOVal(make_nil())
340 return TCOVal(new_ast, env)
342 return TCOVal(try EVAL(new_ast, env))
347 private func eval_fn(list: MalSequence, _ env: Environment) throws -> TCOVal {
348 guard list.count == 3 else {
349 try throw_error("expected 2 arguments to fn*, got \(list.count - 1)")
351 guard let seq = as_sequenceQ(try! list.nth(1)) else {
352 try throw_error("expected list or vector for first argument to fn*")
354 return TCOVal(make_closure((eval: EVAL, args: seq, body: try! list.nth(2), env: env)))
359 private func eval_quote(list: MalSequence, _ env: Environment) throws -> TCOVal {
361 return TCOVal(try! list.nth(1))
363 return TCOVal(make_nil())
366 // EVALuate "quasiquote".
368 private func eval_quasiquote(list: MalSequence, _ env: Environment) throws -> TCOVal {
369 guard list.count >= 2 else {
370 try throw_error("Expected non-nil parameter to 'quasiquote'")
373 return TCOVal(try quasiquote(try! list.nth(1)), env)
375 return TCOVal(try EVAL(try quasiquote(try! list.nth(1)), env))
378 // EVALuate "macroexpand".
380 private func eval_macroexpand(list: MalSequence, _ env: Environment) throws -> TCOVal {
381 guard list.count >= 2 else {
382 try throw_error("Expected parameter to 'macroexpand'")
384 return TCOVal(try macroexpand(try! list.nth(1), env))
387 // Walk the AST and completely evaluate it, handling macro expansions, special
388 // forms and function calls.
390 private func EVAL(var ast: MalVal, var _ env: Environment) throws -> MalVal {
392 defer { EVAL_level-- }
393 guard EVAL_level <= EVAL_leval_max else {
394 try throw_error("Recursing too many levels (> \(EVAL_leval_max))")
398 indent = substring(INDENT_TEMPLATE, 0, EVAL_level)
402 if DEBUG_EVAL { print("\(indent)> \(ast)") }
406 // Not a list -- just evaluate and return.
408 let answer = try eval_ast(ast, env)
409 if DEBUG_EVAL { print("\(indent)>>> \(answer)") }
413 // Special handling if it's a list.
415 var list = as_list(ast)
416 ast = try macroexpand(ast, env)
419 // Not a list -- just evaluate and return.
421 let answer = try eval_ast(ast, env)
422 if DEBUG_EVAL { print("\(indent)>>> \(answer)") }
427 if DEBUG_EVAL { print("\(indent)>. \(list)") }
433 // Check for special forms, where we want to check the operation
434 // before evaluating all of the parameters.
436 let arg0 = list.first()
437 if let fn_symbol = as_symbolQ(arg0) {
441 case kSymbolDef: res = try eval_def(list, env)
442 case kSymbolDefMacro: res = try eval_def(list, env)
443 case kSymbolLet: res = try eval_let(list, env)
444 case kSymbolDo: res = try eval_do(list, env)
445 case kSymbolIf: res = try eval_if(list, env)
446 case kSymbolFn: res = try eval_fn(list, env)
447 case kSymbolQuote: res = try eval_quote(list, env)
448 case kSymbolQuasiQuote: res = try eval_quasiquote(list, env)
449 case kSymbolMacroExpand: res = try eval_macroexpand(list, env)
450 default: res = TCOVal()
453 case let .Return(result): return result
454 case let .Continue(new_ast, new_env): ast = new_ast; env = new_env; continue
455 case .NoResult: break
459 // Standard list to be applied. Evaluate all the elements first.
461 let eval = try eval_ast(ast, env)
463 // The result had better be a list and better be non-empty.
465 let eval_list = as_list(eval)
466 if eval_list.isEmpty {
470 if DEBUG_EVAL { print("\(indent)>> \(eval)") }
472 // Get the first element of the list and execute it.
474 let first = eval_list.first()
475 let rest = as_sequence(eval_list.rest())
477 if let fn = as_builtinQ(first) {
478 let answer = try fn.apply(rest)
479 if DEBUG_EVAL { print("\(indent)>>> \(answer)") }
481 } else if let fn = as_closureQ(first) {
482 let new_env = Environment(outer: fn.env)
483 let _ = try new_env.set_bindings(fn.args, with_exprs: rest)
489 let answer = try EVAL(fn.body, new_env)
490 if DEBUG_EVAL { print("\(indent)>>> \(answer)") }
494 // The first element wasn't a function to be executed. Return an
497 try throw_error("first list item does not evaluate to a function: \(first)")
501 // Convert the value into a human-readable string for printing.
503 private func PRINT(exp: MalVal) -> String {
504 return pr_str(exp, true)
507 // Perform the READ and EVAL steps. Useful for when you don't care about the
510 private func RE(text: String, _ env: Environment) -> MalVal? {
513 let ast = try READ(text)
515 return try EVAL(ast, env)
516 } catch let error as MalException {
517 print("Error evaluating input: \(error)")
519 print("Error evaluating input: \(error)")
521 } catch let error as MalException {
522 print("Error parsing input: \(error)")
524 print("Error parsing input: \(error)")
530 // Perform the full READ/EVAL/PRINT, returning a printable string.
532 private func REP(text: String, _ env: Environment) -> String? {
533 let exp = RE(text, env)
534 if exp == nil { return nil }
538 // Perform the full REPL.
540 private func REPL(env: Environment) {
542 if let text = _readline("user> ") {
543 if let output = REP(text, env) {
553 // Process any command line arguments. Any trailing arguments are incorporated
554 // into the environment. Any argument immediately after the process name is
555 // taken as a script to execute. If one exists, it is executed in lieu of
558 private func process_command_line(args: [String], _ env: Environment) -> Bool {
559 var argv = make_list()
561 let args1 = args[2..<args.count]
562 let args2 = args1.map { make_string($0) }
563 let args3 = [MalVal](args2)
564 argv = make_list(args3)
566 env.set(kSymbolArgv, argv)
569 RE("(load-file \"\(args[1])\")", env)
577 let env = Environment(outer: nil)
582 RE("(def! not (fn* (a) (if a false true)))", env)
583 RE("(def! load-file (fn* (f) (eval (read-string (str \"(do \" (slurp f) \"\\nnil)\")))))", env)
584 RE("(defmacro! cond (fn* (& xs) (if (> (count xs) 0) (list 'if (first xs) (if (> (count xs) 1) (nth xs 1) " +
585 "(throw \"odd number of forms to cond\")) (cons 'cond (rest (rest xs)))))))", env)
587 env.set(kSymbolEval, make_builtin({
588 try! unwrap_args($0) {
589 (ast: MalVal) -> MalVal in
594 if process_command_line(Process.arguments, env) {