Writing a Logo Interpreter

Creating vector graphics in Logo was the first time I wrote code. I wasn’t even aware I was coding. For me, it was plain fun with a little of math. And now, twenty years later I decided to write an interpreter of Logo programming language.

Logo is a simple programming language devised by Seymour Papert for educational purposes. A user can control the movement of a turtle which draws lines on the screen. There are four basic commands in Logo language:

• fd(100) moves the turtle 100 steps forward
• bk(100) move the turtle backwards by 100 steps
• rt(90) turns the turtle 90° to the right
• lt(90) turns the turtle 90° to the left

When we want to draw a square with sides of length 200, we can do this with the following code:

fd(200) rt(90) fd(200) rt(90) fd(200) rt(90) fd(200) rt(90)

We see that the two commands fd(100) rt(90) are repeated four times. We can achieve the same thing using:

repeat 4 [fd(100) rt(90)]

By default, the turtle has a pen attached and whenever it moves, a line is drawn. We can switch turtle to walking mode in which turtle moves without drawing by using penup command. To switch back to drawing mode, we can use pendown command. Here’s a code which draws two parallel lines.

fd(100) pu lf(90) pd lt(90) bk(100)

The icing on the cake are procedures which provide a way to encapsulate a collection of commands. Once a procedure has been created, it can be used the way a built-in command is used. We can draw two squares with the following code:

to square :length
  repeat 4 [forward(:length) right(90)]
end
    
square(100)

To execute some piece of code based on the evaluation of one or more conditions, we can use if-else statement.

if (:size < 5) [
  fd(:size)
] else [
  fd(5)
]

And that’s our Logo language reference. Now let’s focus on an interpreter.

An interpreter is a program that reads a code and turns it into something else. Our interpreter takes Logo code and creates vector graphics. Here is one of my favorite examples. This is the code:

to tree :size
  if (:size < 5) [
    fd(:size) bk(:size)
  ] else [
    fd(:size/3)  
    lt(30) tree(:size*2/3) rt(30)
    fd(:size/6)
    rt(25) tree(:size/2) lt(25)
    fd(:size/3)
    rt(25) tree(:size/2) lt(25)
    fd(:size/6)
    bk(:size)
  ]
end

tree(350)

And what comes out of intepreter looks like this:

Let’s outline the very basics of how it works. First, it transforms source code to tokens. It is called lexical analysis and it’s done by lexer. A token is a small unit of language. It might be a number, a variable or even a paren. Here’s an example.

{
  input: "repeat 4 [fd(100) rt(90)]"
  output:[
    { type: "repeat", value: "repeat" }, 
    { type: "number", value: "4" },
    { type: "lBracket", value: "[" },
    { type: "identifier", value: "fd" }
    { type: "lParen", value: "(" }, 
    { type: "number", value: "100" },
    { type: "rParen", value: ")" },
    { type: "identifier", value: "rt" }
    { type: "lParen", value: "(" }, 
    { type: "number", value: "90" },
    { type: "rParen", value: ")" },
    { type: "rBracket", value: "]" },
    { type: "eof", value: "" }]
}

Next step is parsing. It goes through tokens and builds a tree data structure called Abstract Syntax Tree, which represents the source code. Besides building up the data structure, it analyzes the input and checks that it conforms to expected structure.

{
  output: [{
    type: "repeatExpression",
    count: "4",
    statements: [
        { 
            type: "callExpression", 
            name: "fd",
            arguments: [{ type: "number", value: "200" }]
        },
        { 
            type: "callExpression", 
            name: "rt",
            arguments: [{ type: "number", value: "90" }]
        }
    ]
  }]
}

The last part is the evaluation. This is where the code is evaluated into meaningful output. The interpreter traverses each node in AST and transforms them the to drawing commands. Finally, those commands are used to turn the turtle and draw lines. What comes out of evaluator is the image:

Implementing an interpreter is not a piece of cake. The code is challenging and complex. I encourage you to check out interpreter I wrote. The interpreter’s code is divided into three major parts: lexer, parser and evaluator.

To make the interpreter accessible, I created a source code editor for macOS. The idea is super simple – you write code on the left-hand side of the screen and you get the image on the right.

I’m absolutely fascinated with Logo interpreter. It’s so much fun to play with. Writing the code and seeing the result as an image is an experience on its own.