Building A New Programming Language In Ruby: The Interpreter
Tags: ruby
Published: 2021-09-14 20:42:49

*This article was originally written by [Alex Braha Stoll](https://www.honeybadger.io/blog/stoffle-interpreter-2/#authorDetails) on the [Honeybadger Developer Blog](https://www.honeybadger.io/blog/stoffle-interpreter-2/).*  

> ## Full Source on Github
>
> A complete implementation of the Stoffle programming language is available at [GitHub](https://github.com/alexbrahastoll/stoffle). Feel free to open an issue if you find bugs or have questions.

In this blog post, we're going to start implementing the interpreter for Stoffle, a toy programming language built entirely in Ruby. You can read more about this project in the [first part of this series](https://www.honeybadger.io/blog/stoffle-introduction/).

The interpreter we are going to build is commonly referred to as a tree-walk interpreter. In the previous post of this series, we built a parser to transform a flat sequence of tokens into a tree data structure (an abstract syntax tree, or AST for short). As you might be imagining, our interpreter has the job of going through the AST created by our parser and breathing life into a Stoffle program. I find this last step the most exciting one of this language implementation journey. When building the interpreter, everything finally clicks, and we are able to see Stoffle programs running for real!

I'm going to show and explain the interpreter's implementation in two parts. In this first part, we are going to get the basics working: variables, conditionals, unary and binary operators, data types, and printing to the console. We are reserving the more meaty stuff (function definition, function calling, loops, etc.) for the second and last post on implementing our interpreter.

## A Quick Recap of the Lexer and Parser

Before we dive in and start implementing the interpreter, let's quickly remind ourselves what we did in the previous posts of this series. First, we built the lexer, which transforms raw source code into tokens. Then, we implemented the parser, the component responsible for morphing tokens into a tree structure (the AST). To sum up, here are the transformations we have observed so far:

**State 0: Source**

```
my_var = 1
```

**State 1: Lexer transforms raw source code into tokens**

```
[:identifier, :'=', :number]
```

**State 2: Parser transforms tokens into an Abstract Syntax Tree**

![The AST for a variable binding](https://www.honeybadger.io/images/blog/posts/building-interpreter-ruby/stoffle-ast-var-binding.png)

## It's All About Walking

Now that we have an AST, our job is to write code to walk this structure. We have to write Ruby code that can give life to what each node in our AST describes. If we have a node that describes a variable binding, for example, our task is to write Ruby code that is able to somehow store the result of the right-hand side of our variable binding expression and to have this storage space associated with (and accessible through) the name given to the variable.

As we did in previous parts of this series, we are going to explore the implementation by going through all the important lines of code involved in handling an example program. The piece of Stoffle code we have to interpret is the following:

```stoffle
num = -2
if num > 0
  println("The number is greater than zero.")
else
  println("The number is less than or equal to zero.")
end
```

This is the AST produced for the same program:

![Sample Program's AST](https://www.honeybadger.io/images/blog/posts/building-interpreter-ruby/stoffle-ast-interpreter-part-1.png)

## The First Step in Our Walk

As you probably remember from the last post in this series, a Stoffle AST always has as its root an `AST::Program` node. This root generally has multiple children. Some of them will be shallow (think of the AST produced for a simple variable assignment). Other children can be the root of quite deep subtrees (think of a loop with many lines inside its body). This is the Ruby code we need to start walking through the AST that was passed in to our interpreter:

```ruby
module Stoffle
  class Interpreter
    attr_reader :program, :output, :env

    def initialize
      @output = []
      @env = {}
    end

    def interpret(ast)
      @program = ast

      interpret_nodes(program.expressions)
    end

    private

    def interpret_nodes(nodes)
      last_value = nil

      nodes.each do |node|
        last_value = interpret_node(node)
      end

      last_value
    end

    def interpret_node(node)
      interpreter_method = "interpret_#{node.type}"
      send(interpreter_method, node)
    end

    #...

  end
end
```

When a new `Interpreter` is instantiated, right from the get-go we create two instance variables: `@output` and `@env`. The former's responsibility is to store, in chronological sequence, everything our program has printed out. Having this information at hand is very useful when writing automated tests or debugging. The responsibility of `@env` is a bit different. We named it as such as a reference to "environment". As the name may suggest, its function is to hold the state of our running program. One of its functions will be to implement the binding between an identifier (e.g., a variable name) and its current value.

The `#interpret_nodes` method loops through all the children of the root node (`AST::Program`). Then, it calls `#interpret_node` for each individual node.

`#interpret_node` is simple but nonetheless interesting. Here, we use a bit of Ruby metaprogramming to call the appropriate method for handling the node type currently at hand. For example, for an `AST::VarBinding` node, the `#interpret_var_binding` method is the one that gets called.

## Invariably, We Have to Talk About Variables

The first node we have to interpret in the AST of the example program we are going through is an `AST::VarBinding`. Its `@left` is an `AST::Identifier`, and its `@right` is an `AST::UnaryOperator`. Let's take a look at the method responsible for interpreting a variable binding:

```ruby
def interpret_var_binding(var_binding)
  env[var_binding.var_name_as_str] = interpret_node(var_binding.right)
end
```

As you can see, it's pretty straightforward. We add (or overwrite) a key-value pair to the `@env` Hash.

The key is the name of the variable (`#var_name_as_str` is just a helper method equivalent to `var_binding.left.name`). At the moment, all variables are global. We will handle scoping in the next post.

The value is the result of interpreting the expression on the right-hand side of the assignment. To do that, we use `#interpret_node` again. Since we have an `AST::UnaryOperator` on the right-hand side, the next method that gets called is `#interpret_unary_operator`:

```ruby
def interpret_unary_operator(unary_op)
  case unary_op.operator
  when :'-'
    -(interpret_node(unary_op.operand))
  else # :'!'
    !(interpret_node(unary_op.operand))
  end
end
```

The semantics of Stoffle's supported unary operators (`-` and `!`) are the same as in Ruby. As a consequence, the implementation could not be simpler: we apply Ruby's `-` operator to the result of interpreting the operand. The usual suspect, `#interpret_node`, appears yet again here. As you may remember from the AST of our program, the operand for `-` is an `AST::Number` (the number `2`). This means our next stop is at `#interpret_number`:

```ruby
def interpret_number(number)
  number.value
end
```

The implementation of `#interpret_number` is a piece of cake. Our decision to adopt a Ruby float as the representation of number literals (this happens in the lexer!) pays off here. The `@value` of the `AST::Number` node already holds our desired internal representation of numbers, so we just retrieve it.

With that, we finish interpreting the first direct child of `AST::Program`. Now, to conclude interpreting our program, we must handle its other, more hairy, child: a node of type `AST::Conditional`.

## Terms and Conditions May Apply

Back in `#interpret_nodes`, our best friend `#interpret_node` is called again to interpret the next direct child of `AST::Program`.

```ruby
def interpret_nodes(nodes)
  last_value = nil

  nodes.each do |node|
    last_value = interpret_node(node)
  end

  last_value
end
```

The method responsible for interpreting an `AST::Conditional` is `#interpret_conditional`. Before taking a look at it, however, let's refresh our memories by reviewing the implementation of `AST::Conditional` itself:

```ruby
class Stoffle::AST::Conditional < Stoffle::AST::Expression
  attr_accessor :condition, :when_true, :when_false

  def initialize(cond_expr = nil, true_block = nil, false_block = nil)
    @condition = cond_expr
    @when_true = true_block
    @when_false = false_block
  end

  def ==(other)
    children == other&.children
  end

  def children
    [condition, when_true, when_false]
  end
end
```

Ok, so `@condition` holds an expression that will either be truthy or falsey; `@when_true` holds a block with one or more expressions to be executed in case the `@condition` is truthy, and `@when_false` (the `ELSE` clause) holds the block to be run in case `@condition` happens to be falsey.

Now, let's take a look at `#interpret_condition`:

```ruby
def interpret_conditional(conditional)
  evaluated_cond = interpret_node(conditional.condition)

  # We could implement the line below in a shorter way, but better to be explicit about truthiness in Stoffle.
  if evaluated_cond == nil || evaluated_cond == false
    return nil if conditional.when_false.nil?

    interpret_nodes(conditional.when_false.expressions)
  else
    interpret_nodes(conditional.when_true.expressions)
  end
end
```

Truthiness in Stoffle is the same as in Ruby. In other words, in Stoffle, only `nil` and `false` are falsey. Any other input to a condition is truthy.

We first evaluate the condition by interpreting the expression being held by `conditional.condition`. Let's take a look at the AST of our program again to figure out what node we are dealing with:

![Sample Program's AST](https://www.honeybadger.io/images/blog/posts/building-interpreter-ruby/stoffle-ast-interpreter-part-1.png)

It turns out that we have an `AST::BinaryOperator` (the `>` used in `num > 0`). Okay, it’s the same path again: first `#interpret_node`, which calls `#interpret_binary_operator` this time:

```ruby
def interpret_binary_operator(binary_op)
  case binary_op.operator
  when :and
    interpret_node(binary_op.left) && interpret_node(binary_op.right)
  when :or
    interpret_node(binary_op.left) || interpret_node(binary_op.right)
  else
    interpret_node(binary_op.left).send(binary_op.operator, interpret_node(binary_op.right))
  end
end
```

Our logical operators (`and` and `or`) can be considered binary operators, so we handle them here as well. Since their semantic is equivalent to Ruby's `&&` and `||`, the implementation is plain sailing, as you can see above.

Next is the section of the method we are most interested in; this section handles all other binary operators (including `>`). Here, we can leverage Ruby's dynamism in our favor and come up with a very concise solution. In Ruby, binary operators are available as methods in the objects participating in an operation:

```ruby
-2 > 0           # is equivalent to
-2.send(:'>', 0) # this
# and the following line would be a general solution,
# very similar to what we have in the interpreter
operand_1.send(binary_operator, operand_2)
```

> ## A Verbose Implementation of Binary Operators
>
> As you saw, our implementation of binary operators is very concise. If Ruby was not such a dynamic language, or the semantics of the operators were different between Ruby and Stoffle, we could not have coded the solution in this fashion.
>
> If you ever find yourself in such a position as a language designer/implementer, you can always fall back on a simple (but not that elegant) solution: using a switch construct. In our case, the implementation would look somewhat like this:
>
> ```ruby
> # ... inside #interpret_binary_operator ...
>
> case binary_op.operator
> when :'+'
>   interpret_node(binary_op.left) + interpret_node(binary_op.right)
> # ... other operators
> end
> ```

Before going back to `#interpret_conditional`, let's take a quick detour to make sure nothing is overlooked. If you remember the program we are interpreting, the `num` variable is used in the comparison (using the binary operator `>`) we just explored together. How did we retrieve the left operand (i.e., the value stored in the `num` variable) of that comparison? The method responsible for that is `#interpret_identifier`, and its implementation is easy-peasy:

```ruby
def interpret_identifier(identifier)
  if env.has_key?(identifier.name)
    env[identifier.name]
  else
    # Undefined variable.
    raise Stoffle::Error::Runtime::UndefinedVariable.new(identifier.name)
  end
end
```

Now, back to `#interpret_conditional`. In the case of our little program, the condition evaluated to a Ruby `false` value. We use this value to determine whether we have to execute the IF or the ELSE branch of the conditional structure. We proceed to interpret the ELSE branch, whose associated block of code is stored in `conditional.when_false`. Here, we have an `AST::Block`, which is very similar to the root node of our AST (`AST::Program`). The block, likewise, potentially has a bunch of expressions that need to be interpreted. For this purpose, we also use `#interpret_nodes`.

```ruby
def interpret_conditional(conditional)
  evaluated_cond = interpret_node(conditional.condition)

  # We could implement the line below in a shorter way, but better to be explicit about truthiness in Stoffle.
  if evaluated_cond == nil || evaluated_cond == false
    return nil if conditional.when_false.nil?

    interpret_nodes(conditional.when_false.expressions)
  else
    interpret_nodes(conditional.when_true.expressions)
  end
end
```

The next AST node we have to handle is an `AST::FunctionCall`. The method responsible for interpreting a function call is `#interpret_function_call`:

```ruby
def interpret_function_call(fn_call)
  return if println(fn_call)
end
```

As we discussed in the beginning of the article, function definition and function calling will be covered in the next post in this series. Therefore, we are only implementing a special case of function calling. In our tiny toy language, we provide `println` as part of the runtime and implement it directly in the interpreter here. It's a good enough solution, considering the objectives and scope of our project.

```ruby
def println(fn_call)
  return false if fn_call.function_name_as_str != 'println'

  result = interpret_node(fn_call.args.first).to_s
  output << result
  puts result
  true
end
```

The first and only argument of our `AST::FunctionCall` is an `AST::String`, which gets handled by `#interpret_string`:

```ruby
def interpret_string(string)
  string.value
end
```

In `#interpret_string`, we have the exact same case of `#interpret_number`. An `AST::String` already holds a ready-to-use Ruby string value, so we just have to retrieve it.

Now, back to `#println`:

```ruby
def println(fn_call)
  return false if fn_call.function_name_as_str != 'println'

  result = interpret_node(fn_call.args.first).to_s
  output << result
  puts result
  true
end
```

After storing the function argument (converted to a Ruby string) in `result`, we have two more steps to complete. First, we store what we are about to print to the console in `@output`. As explained previously, the idea here is to be able to easily inspect what was printed (and in what order). Having this at hand makes our life easier when debugging or testing the interpreter. Finally, to implement printing something to the console, we use Ruby's `puts`.

## Execution Matters

Now that we have explored everything that is necessary to implement the bare-bones of Stoffle, let's create a very basic executable to see our interpreter in action.

```ruby
#!/usr/bin/env ruby

require_relative '../lib/stoffle'

path = ARGV[0]
source = File.read(path)
lexer = Stoffle::Lexer.new(source)
parser = Stoffle::Parser.new(lexer.start_tokenization)
interpreter = Stoffle::Interpreter.new

interpreter.interpret(parser.parse)

exit(0)
```

> __TIP:__ To use Stoffle's interpreter from anywhere, remember to add the executable to your PATH.

It's finally time to run our program. If everything works well, we should see the string "The number is less than or equal to zero" printed to the console. This is exactly what happens when we run the interpreter:

![Stoffle Interpreter Running](https://www.honeybadger.io/images/blog/posts/building-interpreter-ruby/stoffle-interpreter-running.png)

> __TIP:__ If you have the interpreter installed, try changing the `num` variable in our sample program so that it holds a number greater than zero. As expected, now the IF branch will get executed, and the string "The number is greater than zero" will be printed out.

## Wrapping Up

In this post, we saw the beginnings of Stoffle's interpreter. We implemented enough of the interpreter for it to handle some of the language basics: variables, conditionals, unary and binary operators, data types, and printing to the console. In the next and final part on the interpreter, we will tackle the remaining bits required for us to have our little toy language working as designed: variable scoping, function definition, function calling, and loops. I hope you had fun reading the article (I certainly had fun writing it!), and we’ll see you soon in the next post in the series!