swift/step5_tco.swift

   1 //******************************************************************************
   2 // MAL - step 5 - tco
   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 kValDef           = make_symbol("def!")
  55 private let kValDo            = make_symbol("do")
  56 private let kValFn            = make_symbol("fn*")
  57 private let kValIf            = make_symbol("if")
  58 private let kValLet           = make_symbol("let*")
  59 private let kValTry           = make_symbol("try*")
  60
  61 private let kSymbolDef           = as_symbol(kValDef)
  62 private let kSymbolDo            = as_symbol(kValDo)
  63 private let kSymbolFn            = as_symbol(kValFn)
  64 private let kSymbolIf            = as_symbol(kValIf)
  65 private let kSymbolLet           = as_symbol(kValLet)
  66
  67 func substring(s: String, _ begin: Int, _ end: Int) -> String {
  68     return s[s.startIndex.advancedBy(begin) ..< s.startIndex.advancedBy(end)]
  69 }
  70
  71 // Parse the string into an AST.
  72 //
  73 private func READ(str: String) throws -> MalVal {
  74     return try read_str(str)
  75 }
  76
  77 // Perform a simple evaluation of the `ast` object. If it's a symbol,
  78 // dereference it and return its value. If it's a collection, call EVAL on all
  79 // elements (or just the values, in the case of the hashmap). Otherwise, return
  80 // the object unchanged.
  81 //
  82 private func eval_ast(ast: MalVal, _ env: Environment) throws -> MalVal {
  83     if let symbol = as_symbolQ(ast) {
  84         guard let val = env.get(symbol) else {
  85             try throw_error("'\(symbol)' not found")    // Specific text needed to match MAL unit tests
  86         }
  87         return val
  88     }
  89     if let list = as_listQ(ast) {
  90         var result = [MalVal]()
  91         result.reserveCapacity(Int(list.count))
  92         for item in list {
  93             let eval = try EVAL(item, env)
  94             result.append(eval)
  95         }
  96         return make_list(result)
  97     }
  98     if let vec = as_vectorQ(ast) {
  99         var result = [MalVal]()
 100         result.reserveCapacity(Int(vec.count))
 101         for item in vec {
 102             let eval = try EVAL(item, env)
 103             result.append(eval)
 104         }
 105         return make_vector(result)
 106     }
 107     if let hash = as_hashmapQ(ast) {
 108         var result = [MalVal]()
 109         result.reserveCapacity(Int(hash.count) * 2)
 110         for (k, v) in hash {
 111             let new_v = try EVAL(v, env)
 112             result.append(k)
 113             result.append(new_v)
 114         }
 115         return make_hashmap(result)
 116     }
 117     return ast
 118 }
 119
 120 private enum TCOVal {
 121     case NoResult
 122     case Return(MalVal)
 123     case Continue(MalVal, Environment)
 124
 125     init() { self = .NoResult }
 126     init(_ result: MalVal) { self = .Return(result) }
 127     init(_ ast: MalVal, _ env: Environment) { self = .Continue(ast, env) }
 128 }
 129
 130 // EVALuate "def!".
 131 //
 132 private func eval_def(list: MalSequence, _ env: Environment) throws -> TCOVal {
 133     guard list.count == 3 else {
 134         try throw_error("expected 2 arguments to def!, got \(list.count - 1)")
 135     }
 136     let arg1 = try! list.nth(1)
 137     let arg2 = try! list.nth(2)
 138     guard let sym = as_symbolQ(arg1) else {
 139         try throw_error("expected symbol for first argument to def!")
 140     }
 141     let value = try EVAL(arg2, env)
 142     return TCOVal(env.set(sym, value))
 143 }
 144
 145 // EVALuate "let*".
 146 //
 147 private func eval_let(list: MalSequence, _ env: Environment) throws -> TCOVal {
 148     guard list.count == 3 else {
 149         try throw_error("expected 2 arguments to let*, got \(list.count - 1)")
 150     }
 151     let arg1 = try! list.nth(1)
 152     let arg2 = try! list.nth(2)
 153     guard let bindings = as_sequenceQ(arg1) else {
 154         try throw_error("expected list for first argument to let*")
 155     }
 156     guard bindings.count % 2 == 0 else {
 157         try throw_error("expected even number of elements in bindings to let*, got \(bindings.count)")
 158     }
 159     let new_env = Environment(outer: env)
 160     for var index: MalIntType = 0; index < bindings.count; index += 2 {
 161         let binding_name = try! bindings.nth(index)
 162         let binding_value = try! bindings.nth(index + 1)
 163         guard let binding_symbol = as_symbolQ(binding_name) else {
 164             try throw_error("expected symbol for first element in binding pair")
 165         }
 166         let evaluated_value = try EVAL(binding_value, new_env)
 167         new_env.set(binding_symbol, evaluated_value)
 168     }
 169     if TCO {
 170         return TCOVal(arg2, new_env)
 171     }
 172     return TCOVal(try EVAL(arg2, new_env))
 173 }
 174
 175 // EVALuate "do".
 176 //
 177 private func eval_do(list: MalSequence, _ env: Environment) throws -> TCOVal {
 178     if TCO {
 179         let _ = try eval_ast(list.range_from(1, to: list.count-1), env)
 180         return TCOVal(list.last(), env)
 181     }
 182
 183     let evaluated_ast = try eval_ast(list.rest(), env)
 184     let evaluated_seq = as_sequence(evaluated_ast)
 185     return TCOVal(evaluated_seq.last())
 186 }
 187
 188 // EVALuate "if".
 189 //
 190 private func eval_if(list: MalSequence, _ env: Environment) throws -> TCOVal {
 191     guard list.count >= 3 else {
 192         try throw_error("expected at least 2 arguments to if, got \(list.count - 1)")
 193     }
 194     let cond_result = try EVAL(try! list.nth(1), env)
 195     var new_ast: MalVal
 196     if is_truthy(cond_result) {
 197         new_ast = try! list.nth(2)
 198     } else if list.count == 4 {
 199         new_ast = try! list.nth(3)
 200     } else {
 201         return TCOVal(make_nil())
 202     }
 203     if TCO {
 204         return TCOVal(new_ast, env)
 205     }
 206     return TCOVal(try EVAL(new_ast, env))
 207 }
 208
 209 // EVALuate "fn*".
 210 //
 211 private func eval_fn(list: MalSequence, _ env: Environment) throws -> TCOVal {
 212     guard list.count == 3 else {
 213         try throw_error("expected 2 arguments to fn*, got \(list.count - 1)")
 214     }
 215     guard let seq = as_sequenceQ(try! list.nth(1)) else {
 216         try throw_error("expected list or vector for first argument to fn*")
 217     }
 218     return TCOVal(make_closure((eval: EVAL, args: seq, body: try! list.nth(2), env: env)))
 219 }
 220
 221 // Walk the AST and completely evaluate it, handling macro expansions, special
 222 // forms and function calls.
 223 //
 224 private func EVAL(var ast: MalVal, var _ env: Environment) throws -> MalVal {
 225     EVAL_level++
 226     defer { EVAL_level-- }
 227     guard EVAL_level <= EVAL_leval_max else {
 228         try throw_error("Recursing too many levels (> \(EVAL_leval_max))")
 229     }
 230
 231     if DEBUG_EVAL {
 232         indent = substring(INDENT_TEMPLATE, 0, EVAL_level)
 233     }
 234
 235     while true {
 236         if DEBUG_EVAL { print("\(indent)>   \(ast)") }
 237
 238         if !is_list(ast) {
 239
 240             // Not a list -- just evaluate and return.
 241
 242             let answer = try eval_ast(ast, env)
 243             if DEBUG_EVAL { print("\(indent)>>> \(answer)") }
 244             return answer
 245         }
 246
 247         // Special handling if it's a list.
 248
 249         let list = as_list(ast)
 250         if DEBUG_EVAL { print("\(indent)>.  \(list)") }
 251
 252         if list.isEmpty {
 253             return ast
 254         }
 255
 256         // Check for special forms, where we want to check the operation
 257         // before evaluating all of the parameters.
 258
 259         let arg0 = list.first()
 260         if let fn_symbol = as_symbolQ(arg0) {
 261             let res: TCOVal
 262
 263             switch fn_symbol {
 264                 case kSymbolDef:            res = try eval_def(list, env)
 265                 case kSymbolLet:            res = try eval_let(list, env)
 266                 case kSymbolDo:             res = try eval_do(list, env)
 267                 case kSymbolIf:             res = try eval_if(list, env)
 268                 case kSymbolFn:             res = try eval_fn(list, env)
 269                 default:                    res = TCOVal()
 270             }
 271             switch res {
 272                 case let .Return(result):               return result
 273                 case let .Continue(new_ast, new_env):   ast = new_ast; env = new_env; continue
 274                 case .NoResult:                         break
 275             }
 276         }
 277
 278         // Standard list to be applied. Evaluate all the elements first.
 279
 280         let eval = try eval_ast(ast, env)
 281
 282         // The result had better be a list and better be non-empty.
 283
 284         let eval_list = as_list(eval)
 285         if eval_list.isEmpty {
 286             return eval
 287         }
 288
 289         if DEBUG_EVAL { print("\(indent)>>  \(eval)") }
 290
 291         // Get the first element of the list and execute it.
 292
 293         let first = eval_list.first()
 294         let rest = as_sequence(eval_list.rest())
 295
 296         if let fn = as_builtinQ(first) {
 297             let answer = try fn.apply(rest)
 298             if DEBUG_EVAL { print("\(indent)>>> \(answer)") }
 299             return answer
 300         } else if let fn = as_closureQ(first) {
 301             let new_env = Environment(outer: fn.env)
 302             let _ = try new_env.set_bindings(fn.args, with_exprs: rest)
 303             if TCO {
 304                 env = new_env
 305                 ast = fn.body
 306                 continue
 307             }
 308             let answer = try EVAL(fn.body, new_env)
 309             if DEBUG_EVAL { print("\(indent)>>> \(answer)") }
 310             return answer
 311         }
 312
 313         // The first element wasn't a function to be executed. Return an
 314         // error saying so.
 315
 316         try throw_error("first list item does not evaluate to a function: \(first)")
 317     }
 318 }
 319
 320 // Convert the value into a human-readable string for printing.
 321 //
 322 private func PRINT(exp: MalVal) -> String {
 323     return pr_str(exp, true)
 324 }
 325
 326 // Perform the READ and EVAL steps. Useful for when you don't care about the
 327 // printable result.
 328 //
 329 private func RE(text: String, _ env: Environment) -> MalVal? {
 330     if !text.isEmpty {
 331         do {
 332             let ast = try READ(text)
 333             do {
 334                 return try EVAL(ast, env)
 335             } catch let error as MalException {
 336                 print("Error evaluating input: \(error)")
 337             } catch {
 338                 print("Error evaluating input: \(error)")
 339             }
 340         } catch let error as MalException {
 341             print("Error parsing input: \(error)")
 342         } catch {
 343             print("Error parsing input: \(error)")
 344         }
 345     }
 346     return nil
 347 }
 348
 349 // Perform the full READ/EVAL/PRINT, returning a printable string.
 350 //
 351 private func REP(text: String, _ env: Environment) -> String? {
 352     let exp = RE(text, env)
 353     if exp == nil { return nil }
 354     return PRINT(exp!)
 355 }
 356
 357 // Perform the full REPL.
 358 //
 359 private func REPL(env: Environment) {
 360     while true {
 361         if let text = _readline("user> ") {
 362             if let output = REP(text, env) {
 363                 print("\(output)")
 364             }
 365         } else {
 366             print("")
 367             break
 368         }
 369     }
 370 }
 371
 372 func main() {
 373     let env = Environment(outer: nil)
 374
 375     load_history_file()
 376     load_builtins(env)
 377
 378     RE("(def! not (fn* (a) (if a false true)))", env)
 379     REPL(env)
 380
 381     save_history_file()
 382 }