kite

kite is an interpreter for the Scheme language written in Swift. It reads source code, turns it into S-expressions and runs them on an abstract machine in which the whole course of the program is ordinary data, not a stack of Swift calls. That single decision is what makes the hardest parts of Scheme possible: first-class continuations and tail recursion with no depth limit.

The whole language lives in the KiteCore library, and the kite program is a thin layer on top: a REPL for interactive work and a runner for .scm files. The same interpreter can be embedded in any Swift app.

In Scheme, code and data share the same shape. The reader therefore does not build a separate syntax tree, it returns lists, symbols, numbers and strings, exactly the values the program and the macros later work on.

The quote, backquote, comma and ,@ shorthands expand straight away into quote, quasiquote, unquote and unquote-splicing. The reader skips line comments, nested block comments and the #; comment, which switches off the whole next expression.

A naive interpreter evaluates a subexpression by calling itself, so every level of a Scheme program is another frame on the Swift stack. kite works differently. Evaluation is a loop that moves between three states: evaluate an expression in an environment, return a value to a continuation, or apply a procedure to its arguments.

The continuation, what to do with the value next, is a plain chain of frames: pick the if branch, add the argument and evaluate the next one, assign the result to a variable, move to the next expression in begin. The Swift stack does not grow with the program, because the whole history of the computation sits in that structure.

Variables live in lexical environments. Each procedure call creates a new frame pointing at the environment where the procedure was defined, so a lambda closes over the variables around it and set! changes them where they were defined. A procedure takes a fixed number of arguments, the rest as a list in the (a . rest) form, or all of them as a single list, and apply spreads a list back into arguments.

Scheme has no loops in the usual sense, a loop is a procedure that calls itself. For such code to spin forever, a call in tail position must not take up memory. In kite the body of a procedure is evaluated with the same continuation the call arrived with, so the last expression in an if, cond or begin leaves nothing for later.

A named let loop of a million steps and mutual recursion between two procedures both run in constant space, with no stack overflow.

Since the continuation is data, call/cc is simple: it wraps the current continuation in a value and hands it to a procedure. Calling that value drops whatever the program was doing and returns to the remembered point with a new result. Here is an early exit from a loop when the list contains a zero:

A continuation can also be called after its expression has already returned, and more than once. That is enough to build a loop, a generator or a jump back to an earlier point of the computation. The same frames carry dynamic-wind, which runs the exit and entry code on the way when a continuation jumps across it, exception handling with with-exception-handler, and multiple return values through call-with-values.

define-syntax with syntax-rules adds new forms to the language. Patterns match a macro call with literals, the _ symbol and ellipses, nested ones in templates included, and a macro can expand recursively into itself. let-syntax and letrec-syntax give locally scoped macros, and when and unless are ordinary macros from the interpreter's prelude.

Every expansion gets its own mark and tags the symbols the template introduces with it. The tmp inside swap! is therefore never confused with a user variable of the same name, and the swap gives (20 10) instead of leaving both values unchanged.

The core of the evaluator knows only a handful of forms: quote, if, define, set!, lambda and begin. Everything else is rewritten into them before evaluation, so the machine stays small and every derived form inherits tail calls and continuations from the core.

Temporary variables get fresh names, so neither or nor cond with => shadows variables from user code. quasiquote handles nesting and splicing lists with ,@.

Integers are computed on the machine type, and when addition, subtraction or multiplication overflows it, the result moves to a hand-written arbitrary-precision implementation. BigInt has division with remainder, GCD, exponentiation, integer square root and conversion between number bases, so the factorial of one hundred comes out exact to the last digit.

Dividing integers gives an exact fraction reduced by the GCD, and floating point only appears once a float enters the computation. modulo and remainder differ in the sign of the result exactly as Scheme requires.

Started with no arguments, kite opens a REPL with a kite> prompt. An expression spread over several lines waits until it is closed, and the following lines get a ... prompt. The result is printed in a form you can paste back as code, and an error ends only the current expression, not the whole session.

Given a file name, kite runs a .scm program, prints errors to standard error and exits with code 1, so it fits into scripts. The interpreter is also an ordinary class of the KiteCore library: a Swift app creates it, passes it source code, gets the result back and captures display output with its own function.

Each layer has its own XCTest suite: the reader, the evaluator with its special forms, tail recursion, re-entrant call/cc, macros and BigInt arithmetic. On top of that the example programs run end to end, and the test compares their output character for character.