Build Your Own Language, Part 6

Here I’m going to try my hand at creating the start of an interpreter. This obviously follows on from the previous posts in this series.

Keep in mind that in the last post we created the start of a runtime. That’s what’s going to allow our code to execute. The interpreter, however, is the module that evaluates the code. It reads the Abstract Syntax Tree (AST) produced by the parser and executes each action associated with the nodes, which are then executed by the runtime. So what have we done? Well, we created nodes in the parser. We’ve also created a ClassNode for a class definition.

However, in order for the interpreter to do its evaluating thing, a new method must be added to those node classes. Specifically, an eval method must be defined on them. This method will be responsible for evaluating that particular node. The interpreter part (the eval method) is the connector between the parser and the runtime of the language.

What that means is that I’m letting each node handle it’s own evaluation. This is not how things are generally done. Normally you would implement what’s called a Visitor pattern. The idea here is that you have a visitor class that you instantiate. You then encapsulate any desired evaluation operation in an object of type visitor. The visitor object then traverses the nodes of the tree. When a tree node “accepts” the visitor, it invokes a method on the visitor that includes the node type as an argument. The visitor will then execute the operation for that node. The Visitor is really an expression evaluator where the actual evaluation of the various operations are encapsulated in the visitor class.

I’ll be honest: I don’t know much about all that yet so I’m purposely glossing over numerous details. I fear I will have to know how to do this at some point. Anyway, let’s get started.

As with everything so far, we’ll start test-first. So create a interpreter_spec.rb file in your spec directory. Put the following in place:

I know I’m going to have to interpret some specific input, so I’ll do something similar to what I did in lexer_spec.rb and parser_spec.rb, which is include an input block that contains the data condition of the test.

What I’ll have to do here is have my test instantiate an interpreter and then evaluate that input. So here’s my start at a test:

So now create a file called interpreter.rb in your project directory. I can make a fairly good start at what I need in here. First I have to reference both the parser module and the runtime module. I’m going to have to instantiate the parser. I also need an eval method that will take in the input. So I’ll start with this in interpreter.rb:

But what goes in that eval method? I know I have to call the parse method on my parser to break the input into nodes. Then what I want to do is call the eval method. If you remember from the last post, in order to perform evaluation, you need an evaluation context. That’s the Runtime that we spent so much time working on in that last post. So I have to pass that context to whatever is getting parsed. So I believe that what has to go in my eval method is this:

If you try to run the test at this point, you’ll get an interesting error:

  1) Testing the Runtime should be able to define a class
     Failure/Error: == true
       private method 'eval' called for #<struct Nodes nodes=[#<struct ClassNode name="Movie">]>

You may remember the the goal of the parsing module was to break the input into nodes. We defined an ast.rb file to hold those nodes. Now I’m going to open those classes again — in the interpreter.rb file. All nodes are going to know how to evaluate themselves. They will also know how to return the result of their own evaluation.

So in the interpreter.rb file I’m going to add this:

It’s very important to see that I’m opening the Nodes class — originally defined in ast.rb — and putting in some additional functionality. The context being passed in is, as you can see from the previous code, the runtime. That means that the ocntext is the environment in which the node is being evaluated. In this case, the only environment I could be checking is the current class that the node is executing with or within.

What this means, however, is that I need to go through the collection of nodes that the parser has returned. Right now I don’t have a reference to that collection. I never tried to capture the set of all nodes that the parser went through. When testing the parser in isolation, I simply made sure it was handling the nodes I needed it to. But now we’re starting to hook up the parts of our language and so I need that collection.

What this means is that you have go back to that ast.rb file and grab this collection.

This nodes variable can now be used in my eval method in interpreter.rb:

A node here is going to be something like this:

#<struct ClassNode name="Movie">

What I want is the value, however.

How am I going to do that? Well, I have to have the ClassNode evaluate itself. What that means is that in my above iterator, I have to call an eval method for that particular node.

So now I have to open the ClassNode class again and create the eval method there. This is being done in interpreter.rb.

So what should go in there? Well, I need to locate the class. Then I need to register the class as a type of constant in the runtime.

That should make the test pass.

And … at this point I’ve done enough to realize that while I can make progress, I’m a bit in over my head. So this will effectively end this series of posts for the time being. I do plan on continuing this work and I’ll do another post when I have a fully working “product” to show. Hopefully, however, this series of posts was helpful for those who have either wanted to dabble in language creation or were just curious about it.


This article was written by Jeff Nyman

Anything I put here is an approximation of the truth. You're getting a particular view of myself ... and it's the view I'm choosing to present to you. If you've never met me before in person, please realize I'm not the same in person as I am in writing. That's because I can only put part of myself down into words. If you have met me before in person then I'd ask you to consider that the view you've formed that way and the view you come to by reading what I say here may, in fact, both be true. I'd advise that you not automatically discard either viewpoint when they conflict or accept either as truth when they agree.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.