I’m working through the online book Crafting Interpreters, (which I highly recommend, if you’re curious about how such things are built). While going through it, I’m making a stab at translating the example code in the book (which is in Java) into Swift. This is not something I’m very familiar with, so I’m trying a couple different ways of tackling the development. I thought I’d write about what’s worked, and where I think I might have painted myself into a corner.
Replacing the Visitor Pattern with Protocols and Extensions
A lot of the example code takes advantage of classes and uses a fair number recursive calls. The author tackles some of the awkwardness of that by aggressively using a visitor pattern over Java classes. A clear translation win is leveraging Swift’s protocols and extensions to accommodate the same kind of setup. It makes it extremely easy to define an interface that you’d otherwise wrap into a visitor pattern (using a protocol), and use an extension to conform classes to the protocol. I think the end result is far easier to understand and read, which is huge for me – as this is not something I’ve tried before and I find a lot of the elements difficult to understand to start with.
Recursive Enumerations Replacing Classes
I approached this one with the initial thought of “I’ve no idea if this’ll work”. There are a number of “representation” classes that make up the tree structure that you build while parsing and interpreting. The author used a bit of code to generate the classes from a basic grammar (and then re-uses it as the grammar evolves within the book while we’re implementing things). This may not have been the wisest choice, but I went for hand-coding these classes, and while I was in there I tried using Enumerations. I have to admit, the section in The Swift Programming Language on enumerations had an interior section on Recursive Enumerations that used arithmetic expressions as an example. That really pushed me to consider that kind of thing for what in Java were structural classes. I had already known about, and enjoyed using, enumerations with associated types. It seemed like it could match pretty darned closely.
For processing expressions, I think it’s been a complete win for me. A bit of the code — one of those structural classes — looks akin to this:
public indirect enum Expression {
case literal(LiteralExpression)
case unary(UnaryExpression, Expression)
case binary(Expression, OperatorExpression, Expression)
case grouping(Expression)
case variable(Token)
case assign(Token, Expression)
}This lines up with the simple grammar rules I was implementing. Not all of the grammar you need works well for this basic structure. I think it’s been great for representing expressions in particular.
Results with Explicit Failure Types Replacing Java Exception
Let me start off with: This one may have been a mistake.
UPDATE: Yep, that was definitely a mistake.
A lot of the author’s code uses Java’s Exceptions as an explicit part of the control flow. You can almost do the same in Swift, but the typing and catching of errors is… a little stranger. The author was passing additional content back in the errors – using the exceptions to “pop all the way out of an evaluation” which could be many layers of recursion deep. So I thought, what the hell – lets see how Swift’s Result type works for this.
I took a portion of the interpreter code (the bit that evaluates expressions) and decided to convert it to returning a Result instead of throwing an exception. The protocol I set up for this started as the following:
public protocol Interpretable {
func evaluate(_ env: Environment) throws -> RuntimeValue
}
And I updated it to return a Result:
public protocol Interpretable {
func evaluate(_ env: Environment) -> Result<RuntimeValue, RuntimeError>
}
In terms of passing back additional data (as associated values within a RuntimeError – an enumeration), it worked beautifully. I could interrogate and pull out whatever I needed very easily.
The downside is that to access the innards of a returned result means that you have to use switch on it, and then deal with internals as cases. In almost all cases, I found I wanted to simply propagate a failure up from internal functions, so what I really wanted was something more like a JavaScript Promise (or a Swift Promise library) rather than a raw Result.
The Interpretable protocol applies to those recursive enumerations I showed a bit earlier, the end result was indentions-from-hell where I’m switching on this, that, and the other – making the code quite a bit more difficult to read than I think it needs to be. By itself, result doesn’t add all that much, but when added to switching based on the enumeration that made up the structural representation of the expressions, I had most of the “work” indented four to six layers in.
The upside is that everything is explicitly defined. Swift’s enforcement of exhaustive switch statements makes it so that the compiler “keeps me honest”. Just to share a taste of what I inflicted upon myself, here’s a portion of the evaluate function used within the interpreter:
extension Expression: Interpretable {
public func evaluate(_ env: Environment) -> Result<RuntimeValue, RuntimeError> {
switch self {
case let .literal(litexpr):
return litexpr.evaluate(env)
case let .assign(tok, expr):
switch expr.evaluate(env) {
case let .success(value):
do {
try env.assign(tok, value)
return .success(RuntimeValue.none)
} catch {
return .failure(RuntimeError.undefinedVariable(tok, message: "\(error)"))
}
case let .failure(err):
return .failure(err)
}
The layer that uses this, my Parser code, uses the throws type logic, so I have a few places where I end up with an “impedance mismatch” (apologies – you get my way-old idiomatic Electrical Engineering references here sometimes). The Parser class uses the exceptions, and the Expressions that it evaluates return Result types – so there’s translation that needs to happen between the two.
I’m going to keep running with it to see it through, but the jury is definitely out on “Was this a good idea?” I have been half-tempted to just go all-in and make the Parser return a result type, but honestly the whole code that ends up something like:
switch result {
case let .success(value):
// do something with the value
case let .failure(err):
// often propagating the error:
return .failure(err)Just felt so overwhelming that I stopped at the evaluating expressions.
Swift LOX
The language I’m implementing is called LOX, a creation of the author. The translation is in progress, but operational, and probably flawed in a number of ways. I’m not all the way through the book – next up is adding block syntax to the grammar, parser, and interpreter – but it’s coming along reasonably well.
If you want to look further at the translation-atrocities I’ve committed, feel free: the code is available at GitHub at https://github.com/heckj/slox. I’m going to carry it through at least another chapter or two to get the elements I wanted to learn for another project. Because of that, I expect it’ll evolve a bit from where it is today, but I may not ever fully enable the language. We’ll just have to wait and see.
Rhonabwy 