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 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 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 let TCO = true
  28
  29 // Control whether or not we emit debugging statements in EVAL.
  30 //
  31 let DEBUG_EVAL = false
  32
  33 let INDENT_TEMPLATE = "|----|----|----|----|----|----|----|----|" +
  34     "----|----|----|----|----|----|----|----|----|----|----|" +
  35     "----|----|----|----|----|----|----|----|----|----|----|" +
  36     "----|----|----|----|----|----|----|----|----|----|----|" +
  37     "----|----|----|----|----|----|----|----|----|----|----|" +
  38     "----|----|----|----|----|----|----|----|----|----|----|" +
  39     "----|----|----|----|----|----|----|----|----|----|----|" +
  40     "----|----|----|----|----|----|----|----|----|----|----|" +
  41     "----|----|----|----|----|----|----|----|----|----|----|" +
  42     "----|----|----|----|----|----|----|----|----|----|----|" +
  43     "----|----|----|----|----|----|----|----|----|----|----|"
  44
  45 let kSymbolDef              = MalSymbol(symbol: "def!")
  46 let kSymbolDo               = MalSymbol(symbol: "do")
  47 let kSymbolFunction         = MalSymbol(symbol: "fn*")
  48 let kSymbolIf               = MalSymbol(symbol: "if")
  49 let kSymbolLet              = MalSymbol(symbol: "let*")
  50
  51 // Class to help control the incrementing and decrementing of EVAL_level. We
  52 // create one of these on entry to EVAL, incrementing the level. When the
  53 // variable goes out of scope, the object is destroyed, decrementing the level.
  54 //
  55 class EVAL_Counter {
  56     init() {
  57         ++EVAL_level
  58     }
  59     deinit {
  60         --EVAL_level
  61     }
  62 }
  63
  64 // Parse the string into an AST.
  65 //
  66 func READ(str: String) -> MalVal {
  67     return read_str(str)
  68 }
  69
  70 // Perform a simple evaluation of the `ast` object. If it's a symbol,
  71 // dereference it and return its value. If it's a collection, call EVAL on all
  72 // elements (or just the values, in the case of the hashmap). Otherwise, return
  73 // the object unchanged.
  74 //
  75 func eval_ast(ast: MalVal, env: Environment) -> MalVal {
  76     if is_symbol(ast) {
  77         let symbol = ast as MalSymbol
  78         if let val = env.get(symbol) {
  79             return val
  80         }
  81         return MalError(message: "'\(symbol)' not found")    // Specific text needed to match MAL unit tests
  82     }
  83     if is_list(ast) {
  84         let list = ast as MalList
  85         var result = [MalVal]()
  86         result.reserveCapacity(list.count)
  87         for item in list {
  88             let eval = EVAL(item, env)
  89             if is_error(eval) { return eval }
  90             result.append(eval)
  91         }
  92         return MalList(array: result)
  93     }
  94     if is_vector(ast) {
  95         let vec = ast as MalVector
  96         var result = [MalVal]()
  97         result.reserveCapacity(vec.count)
  98         for item in vec {
  99             let eval = EVAL(item, env)
 100             if is_error(eval) { return eval }
 101             result.append(eval)
 102         }
 103         return MalVector(array: result)
 104     }
 105     if is_hashmap(ast) {
 106         let hash = ast as MalHashMap
 107         var result = [MalVal]()
 108         result.reserveCapacity(hash.count * 2)
 109         for (k, v) in hash {
 110             let new_v = EVAL(v, env)
 111             if is_error(new_v) { return new_v }
 112             result.append(k)
 113             result.append(new_v)
 114         }
 115         return MalHashMap(array: result)
 116     }
 117     return ast
 118 }
 119
 120 // Walk the AST and completely evaluate it, handling macro expansions, special
 121 // forms and function calls.
 122 //
 123 func EVAL(var ast: MalVal, var env: Environment) -> MalVal {
 124     var x = EVAL_Counter()
 125     if EVAL_level > EVAL_leval_max {
 126         return MalError(message: "Recursing too many levels (> \(EVAL_leval_max))")
 127     }
 128
 129     let indent = INDENT_TEMPLATE.substringToIndex(
 130         advance(INDENT_TEMPLATE.startIndex, EVAL_level, INDENT_TEMPLATE.endIndex))
 131
 132     while true {
 133         if is_error(ast) { return ast }
 134         if DEBUG_EVAL { println("\(indent)>   \(ast)") }
 135
 136         // Special handling if it's a list.
 137
 138         if is_list(ast) {
 139             var list = ast as MalList
 140             if DEBUG_EVAL { println("\(indent)>.  \(list)") }
 141
 142             if list.isEmpty {
 143                 return ast
 144             }
 145
 146             let arg1 = list.first()
 147             if is_symbol(arg1) {
 148                 let fn_symbol = arg1 as MalSymbol
 149
 150                 // Check for special forms, where we want to check the operation
 151                 // before evaluating all of the parameters.
 152
 153                 if fn_symbol == kSymbolDef {
 154                     if list.count != 3 {
 155                         return MalError(message: "expected 2 arguments to def!, got \(list.count - 1)")
 156                     }
 157                     let arg1 = list[1]
 158                     let arg2 = list[2]
 159                     if !is_symbol(arg1) {
 160                         return MalError(message: "expected symbol for first argument to def!")
 161                     }
 162                     let sym = arg1 as MalSymbol
 163                     let value = EVAL(arg2, env)
 164                     if is_error(value) { return value }
 165                     return env.set(sym, value)
 166                 } else if fn_symbol == kSymbolLet {
 167                     if list.count != 3 {
 168                         return MalError(message: "expected 2 arguments to let*, got \(list.count - 1)")
 169                     }
 170                     let arg1 = list[1]
 171                     let arg2 = list[2]
 172                     if !is_sequence(arg1) {
 173                         return MalError(message: "expected list for first argument to let*")
 174                     }
 175                     let bindings = arg1 as MalSequence
 176                     if bindings.count % 2 == 1 {
 177                         return MalError(message: "expected even number of elements in bindings to let*, got \(bindings.count)")
 178                     }
 179                     var new_env = Environment(outer: env)
 180                     for var index = 0; index < bindings.count; index += 2 {
 181                         let binding_name = bindings[index]
 182                         let binding_value = bindings[index + 1]
 183
 184                         if !is_symbol(binding_name) {
 185                             return MalError(message: "expected symbol for first element in binding pair")
 186                         }
 187                         let binding_symbol = binding_name as MalSymbol
 188                         let evaluated_value = EVAL(binding_value, new_env)
 189                         if is_error(evaluated_value) { return evaluated_value }
 190                         new_env.set(binding_symbol, evaluated_value)
 191                     }
 192                     if TCO {
 193                         env = new_env
 194                         ast = arg2
 195                         continue
 196                     }
 197                     return EVAL(arg2, new_env)
 198                 } else if fn_symbol == kSymbolDo {
 199                     if TCO {
 200                         let eval = eval_ast(MalList(slice: list[1..<list.count-1]), env)
 201                         if is_error(eval) { return eval }
 202                         ast = list.last()
 203                         continue
 204                     }
 205
 206                     let evaluated_ast = eval_ast(list.rest(), env)
 207                     if is_error(evaluated_ast) { return evaluated_ast }
 208                     let evaluated_seq = evaluated_ast as MalSequence
 209                     return evaluated_seq.last()
 210                 } else if fn_symbol == kSymbolIf {
 211                     if list.count < 3 {
 212                         return MalError(message: "expected at least 2 arguments to if, got \(list.count - 1)")
 213                     }
 214                     let cond_result = EVAL(list[1], env)
 215                     var new_ast = MalVal()
 216                     if is_truthy(cond_result) {
 217                         new_ast = list[2]
 218                     } else if list.count == 4 {
 219                         new_ast = list[3]
 220                     } else {
 221                         return MalNil()
 222                     }
 223                     if TCO {
 224                         ast = new_ast
 225                         continue
 226                     }
 227                     return EVAL(new_ast, env)
 228                 } else if fn_symbol == kSymbolFunction {
 229                     if list.count != 3 {
 230                         return MalError(message: "expected 2 arguments to fn*, got \(list.count - 1)")
 231                     }
 232                     if !is_sequence(list[1]) {
 233                         return MalError(message: "expected list or vector for first argument to fn*")
 234                     }
 235                     return MalClosure(eval: EVAL, args:list[1] as MalSequence, body:list[2], env:env)
 236                 }
 237             }
 238
 239             // Standard list to be applied. Evaluate all the elements first.
 240
 241             let eval = eval_ast(ast, env)
 242             if is_error(eval) { return eval }
 243
 244             // The result had better be a list and better be non-empty.
 245
 246             let eval_list = eval as MalList
 247             if eval_list.isEmpty {
 248                 return eval_list
 249             }
 250
 251             if DEBUG_EVAL { println("\(indent)>>  \(eval)") }
 252
 253             // Get the first element of the list and execute it.
 254
 255             let first = eval_list.first()
 256             let rest = eval_list.rest()
 257
 258             if is_builtin(first) {
 259                 let fn = first as MalBuiltin
 260                 let answer = fn.apply(rest)
 261                 if DEBUG_EVAL { println("\(indent)>>> \(answer)") }
 262                 return answer
 263             } else if is_closure(first) {
 264                 let fn = first as MalClosure
 265                 var new_env = Environment(outer: fn.env)
 266                 let result = new_env.set_bindings(fn.args, with_exprs:rest)
 267                 if is_error(result) { return result }
 268                 if TCO {
 269                     env = new_env
 270                     ast = fn.body
 271                     continue
 272                 }
 273                 let answer = EVAL(fn.body, new_env)
 274                 if DEBUG_EVAL { println("\(indent)>>> \(answer)") }
 275                 return answer
 276             }
 277
 278             // The first element wasn't a function to be executed. Return an
 279             // error saying so.
 280
 281             return MalError(message: "first list item does not evaluate to a function: \(first)")
 282         }
 283
 284         // Not a list -- just evaluate and return.
 285
 286         let answer = eval_ast(ast, env)
 287         if DEBUG_EVAL { println("\(indent)>>> \(answer)") }
 288         return answer
 289     }
 290 }
 291
 292 // Convert the value into a human-readable string for printing.
 293 //
 294 func PRINT(exp: MalVal) -> String? {
 295     if is_error(exp) { return nil }
 296     return pr_str(exp, true)
 297 }
 298
 299 // Perform the READ and EVAL steps. Useful for when you don't care about the
 300 // printable result.
 301 //
 302 func RE(text: String, env: Environment) -> MalVal? {
 303     if text.isEmpty { return nil }
 304     let ast = READ(text)
 305     if is_error(ast) {
 306         println("Error parsing input: \(ast)")
 307         return nil
 308     }
 309     let exp = EVAL(ast, env)
 310     if is_error(exp) {
 311         println("Error evaluating input: \(exp)")
 312         return nil
 313     }
 314     return exp
 315 }
 316
 317 // Perform the full READ/EVAL/PRINT, returning a printable string.
 318 //
 319 func REP(text: String, env: Environment) -> String? {
 320     let exp = RE(text, env)
 321     if exp == nil { return nil }
 322     return PRINT(exp!)
 323 }
 324
 325 // Perform the full REPL.
 326 //
 327 func REPL(env: Environment) {
 328     while true {
 329         if let text = _readline("user> ") {
 330             if let output = REP(text, env) {
 331                 println("\(output)")
 332             }
 333         } else {
 334             println()
 335             break
 336         }
 337     }
 338 }
 339
 340 func main() {
 341     var env = Environment(outer: nil)
 342
 343     load_history_file()
 344     load_builtins(env)
 345
 346     RE("(def! not (fn* (a) (if a false true)))", env)
 347     REPL(env)
 348
 349     save_history_file()
 350 }