Implementing a Programming Language in Swift — Part 9: Defining Functions

NOTE: This is the ninth part in a tutorial series on “Implementing a Programming Language in Swift.” Be sure to check out the previous ones.

In our last tutorial we went over the challenges of adding function support and designed how our functions should behave, what keywords, how we would handle scoping etc. To recap:

1. Our functions will use be of the format function name(parameter) { ... }
Where function is a keyword representing the start of a function definition.
2. We will simply ignore problems related to scoping by making all variables global and prevent the user from being able to shadow existing ones.

So where to begin?

This tutorial will be very similar to my tutorials on adding support for declaring variables. We will do this in four simple steps:

1. Add tokens function, {, } and ,.
2. Add struct FunctionDefinition and refactor our global identifiers dictionary to support both variables and functions.
3. Add parser method for FunctionDefinition.
4. Add parser method for calling a function.

Adding the Tokens

This is as simple as it gets. In our Token model we simply add these highlighted lines:

enum Token {
    typealias Generator = (String) -> Token?
    case op(Operator)
    case number(Float)
    case identifier(String)
    case parensOpen
    case parensClose
    case `var`
    case equals
    case function
    case curlyOpen
    case curlyClose
    
    case comma
    static var generators: [String: Generator] {
        return [
            "\\*|\\/|\\+|\\-": { .op(Operator(rawValue: $0)!) },
            "\\-?([0-9]*\\.[0-9]+|[0-9]+)": { .number(Float($0)!) },
           "[a-zA-Z_$][a-zA-Z_$0-9]*": { // ADDED - perfected
               guard $0 != "var" else { // ADDED
                   return .var
               }
               guard $0 != "function" else {
                   return .function
               }
               return .identifier($0)
           },
           "\\(": { _ in .parensOpen },
           "\\)": { _ in .parensClose },
           "\\=": { _ in .equals },
           "\\{": { _ in .curlyOpen },
           "\\}": { _ in .curlyClose },
           "\\,": { _ in .comma }
       ]
    }
}

Adding our FunctionDefinition

This needs a little bit of design. We need to ask ourselves the question “What is a function?”

Remember that we decided to go with the format function identifier(parameter) { ... }.

To support this type of function we to store the following:

• An Identifier
• Parameters
• Some indicator of where our code block begins and ends.

Before we begin implementing our node for functions we need to add support for FunctionDefinition in our identifiers dictionary which currently only supports Float values. To do this, let’s create a new enum called Definition which handles both variables and functions:

enum Definition {
    case variable(value: Float)
    case function(FunctionDefinition)
}

To fix build errors relating to the missing FunctionDefinition type simply create a temporary one:

struct FunctionDefinition: Node {
    // TODO: IMPLEMENT!
    func interpret() throws -> Node {
        return 1 // TODO: IMPLEMENT!
    }
}

Now let’s change our identifiers dictionary to use the new Definition type:

var identifiers: [String: Definition] = [
    "PI": .variable(value: Float.pi),
]

You will get two types of build errors in making this change:

1. guard let ... = identifiers[...] ... — This should now use guard case let .variable(...) = identifiers[...] ....
2. identifiers[...] = ... — This should now be something like identifiers[...] = .variable(...).

Fixed? Great! Just one more thing, this tutorial’s additions will require us to add two more errors to our Parser.Error enum:

case invalidParameters(toFunction: String)
case alreadyDefined(String)

Okay. We are now ready to implement the “real” FunctionDefiniton:

struct FunctionDefinition: Node {
    let identifier: String
    let parameters: [String]
    let block: Node
    func interpret() throws -> Float {
        identifiers[identifier] = .function(self)
        return 1 // 1 means SUCCESS
    }
}

Notice that we are returning a result of one from our interpretation of function definitions. This is a result of our language having no special return handling, it simply returns the result last of the last interpreted statement. The idea is that every valid code snippet should return a value.

Parsing FunctionDefinition

Compared to parsing variable declarations function definitions have one tricky bit and that is parameters. To separate this logic from our parseFunctionDefinition method let’s add another one called parseParameterList:

func parseParameterList() throws -> [Node] {
    var params: [Node] = []
    guard case .parensOpen = popToken() else {
        throw Error.expected("(")
    }
    while self.canPop {
        guard let value = try? parseValue() else {
            break
        }
        guard case .comma = peek() else {
            params.append(value)
            break
        }
        popToken()
        params.append(value)
    }
    guard canPop, case .parensClose = popToken() else {
        throw Error.expected(")")
    }
    return params
}

This function might look a little scary, but it’s really as simple as this:

1. Parse (.
2. Parse as many values using parseValue() as we can.
3. Parse ).
4. Return the values.

You might be wondering why we are using the parseValue() function here as the parameters in our function definitions should be simple strings. But if we use parseValue this function can be reused later on when we implement the parser function for function calls.

Simple enough? Awesome! Let’s add our parseFunctionDefinition function:

func parseFunctionDefinition() throws -> Node {
    guard case .function = popToken() else {
        throw Error.expected("function")
    }
    guard case let .identifier(identifier) = popToken() else {
        throw Error.expectedIdentifier
    }
    let paramNodes = try parseParameterList()
    // Convert the nodes to their String values
    let paramList = try paramNodes
        .map { node -> String in
            guard let string = node as? String else {
                throw Error.expectedIdentifier
            }
            return string
        }
    guard case .curlyOpen = popToken() else {
        throw Error.expected("{")
    }
    let startIndex = index
    while canPop {
        guard case .curlyClose = peek() else {
            index += 1
            continue
        }
        break
    }
    let endIndex = index
    guard case .curlyClose = popToken() else {
        throw Error.expected("}")
    }
    let codeBlock = try Parser(tokens: Array(tokens[startIndex..<endIndex])).parse()
    return FunctionDefinition(identifier: identifier,
                              parameters: paramList,
                              block: codeBlock)
}

To summarize:

1. Parse function.
2. Parse identifier.
3. Parse parameter list as [String].
4. Parse {.
5. We are now at the start index of our function’s code block. Store this value as startIndex.
6. Increment index until we find a closing curly bracket.
7. We are now at the end index of our function’s code block. Store this value as endIndex.
8. Create a FunctionDefinition and return it.

Awesome!

Now the only thing outstanding for parsing FunctionDefinition is to call our parseFunctionDefinition method inside our parse method:

func parse() throws -> Node { // ADDED: New parse method
    var nodes: [Node] = []
    while canPop {
        let token = peek()
        switch token {
        case .var:
            let declaration = try parseVariableDeclaration()
            nodes.append(declaration)
        case .function:
            let definition = try parseFunctionDefinition()
            nodes.append(definition)
        default:
            let expression = try parseExpression()
            nodes.append(expression)
        }
    }
    return Block(nodes: nodes)
}

Parsing Function Calls

First things first! We need a node for representing function calls:

struct FunctionCall: Node {
    let identifier: String
    let parameters: [Node]
    func interpret() throws -> Float {
        guard let definition = identifiers[identifier],
            case let .function(function) = definition else {

            throw Parser.Error.notDefined(identifier)
        }
        guard function.parameters.count == parameters.count else {
            throw Parser.Error.invalidParameters(toFunction: identifier)
        }
        let paramsAndValues = zip(function.parameters, parameters)
        // Temporarily add parameters to global index
        try paramsAndValues.forEach { (name, node) in

            guard identifiers[name] == nil else {
                throw RuntimeError.alreadyDefined(name)
            }
            identifiers[name] = .variable(value: try node.interpret())
        }
        let returnValue = try function.block.interpret()
        // Remove parameter values from global index after use
        paramsAndValues.forEach { (name, _) in
            identifiers.removeValue(forKey: name)
        }
        return returnValue
    }
}

Remember the design/shortcut of ignoring scope handling and disallowing shadowing. FunctionCall is the node where this happens.

If you examine our its interpret method you’ll notice this hacky functionality where we temporarily add parameters as variables to our global variable store.

So, we’ve got our FunctionCall, now it’s time to create a method for parsing it. This will be very similar to what we did when we added variable parsing. Let’s navigate to the parseValue method and replace the previous identifier parsing with the following highlighted snippet:

func parseValue() throws -> Node {
    switch (peek()) {
    case .number:
        return try parseNumber()
    case .parensOpen:
        return try parseParens()
    case .identifier:
        guard let identifier = try parseIdentifier() as? String else {
            throw Error.expectedIdentifier
        }
        guard canPop, case .parensOpen = peek() else {
            return identifier
        }
        let params = try parseParameterList()
        return FunctionCall(identifier: identifier,
                            parameters: params)
    default:
        throw Error.expectedExpression
    }
}

If a .parensOpen follows an .identifier we treat it as a function call other wise we simply return the identifier.

Finally: Update our Main Function

var code = """
function sum(a, b) {
    a + b
}
var five = 5
var six = 6
sum(five, six)
"""
let tokens = Lexer(code: code).tokens
let node = try Parser(tokens: tokens).parse()
do {
    print(try node.interpret() == 11) // true
} catch {
    print((error as? Parser.Error))
}

Soooo beautiful! 😍

But beware of the side effects of our laziness when dealing with scoping. Languages without scope handling can become really annoying:

function foo(param) {
    param
}
function bar(param) {
    var something = foo(5) Here we get an error as 5 will become foo's "param" but "param" already exists in bar's runtime
    something + param 
}
bar(6)

But let’s not beat ourselves up too much, we’ve implemented programming language. It’s completely useless for anything other than calculation as it only supports the Float type and doesn’t have support for logical “if” statements.

Speaking of which, next week we will fully complete our language by adding “if” statement support!

I hope you guys found this tutorial interesting and as always, don’t be shy to give feedback e.g. by clapping or writing a response.

P.S. Remember that you can follow me here on Medium for notifications on future tutorials.