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