swift/step7_quote.swift

   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 }