Let's build a simple interpreter for APL - part 1 | mathspp

Blog

Let's build a simple interpreter for APL - part 1

13th May 2020

apl<br>interpreters<br>lsbasi-apl<br>programming<br>python

Foreword

First and foremost, let me give credit to Ruslan Spivak's Let's build a simple interpreter blog post series on building a Pascal interpreter. I first read the beginning of the series a couple of years ago and ended up creating the Roj programming language; this time I am going over the series again but with the purpose of building an interpreter for APL which is fairly distinct from Pascal.

I am writing an APL interpreter and writing about it because

it will help me learn APL;

I get to flex my Python skills and improve them;

I get to document what I did in order to get my code working;

I get to help you write your own APL interpreter if you decide to do so!

For those of you who know the LSBASI series, the numbering in my LSBASI series is not going to match Spivak's. This is because in this interpreter I need to worry about things Spivak did not have to and vice-versa, because APL and Pascal have so distinct characteristics in some aspects. On the other hand, the beginning is fairly similar and this post will present work that matches roughly what Spivak has by halfway of his 8th blog post.

The code

The code for this project is available at this GitHub repo so go ahead and star it ;) The source code for this part is just the rgspl1.py file: you can download it in order to try it out.

What we are aiming for

This blog post series will follow along my journey of building an APL interpreter and that is the end goal! To have a fully functional APL interpreter written in Python! That is going to be a lot of work ;)

Today's goal

In this blog post we will go through the basics to kickstart this project; in particular, we want to be able to parse simple APL statements with:

floats and integers (positive and negative - in APL we use ¯ to negate a number, e.g. ¯3 is \(-3\)) and vectors of those;

monadic and dyadic versions of the functions +-×÷;

the commute/switch operator ⍨;

parenthesized expressions;

Tokenizing

The first thing we need to do is take some APL source code and split it into tokens, getting rid of things we don't need - like whitespace - and finding what each character represents. For example, we look for numbers and decide if those are integers or floats or look at APL glyphs and attach them to their names.

This is the code for the Token class that defines the several types of tokens we are going to use today:

class Token:<br>"""Represents a token parsed from the source code."""

INTEGER = "INTEGER"<br>FLOAT = "FLOAT"<br>PLUS = "PLUS"<br>MINUS = "MINUS"<br>TIMES = "TIMES"<br>DIVIDE = "DIVIDE"<br>NEGATE = "NEGATE"<br>COMMUTE = "COMMUTE"<br>LPARENS = "LPARENS"<br>RPARENS = "RPARENS"<br>EOF = "EOF"

# Helpful lists of token types.<br>FUNCTIONS = [PLUS, MINUS, TIMES, DIVIDE]<br>MONADIC_OPS = [COMMUTE]

# What You See Is What You Get characters that correspond to tokens.<br>WYSIWYG = "+-×÷()⍨"<br># The mapping from characteres to token types.<br>mapping = {<br>"+": PLUS,<br>"-": MINUS,<br>"×": TIMES,<br>"÷": DIVIDE,<br>"(": LPARENS,<br>")": RPARENS,<br>"⍨": COMMUTE,

def __init__(self, type_, value):<br>self.type = type_<br>self.value = value

def __str__(self):<br>return f"Token({self.type}, {self.value})"

def __repr__(self):<br>return self.__str__()<br>After defining these token types and the __str__ and __repr__ methods (that allow us to print the token instances in a more friendly way) we need to be able to convert a string like 5 + 6 to the list of tokens [Token(EOF, None), Token(INTEGER, 5), Token(PLUS, +), Token(INTEGER, 6)].

Notice how the EOF token (end-of-file token) is the first one in the list. This is because I decided to tokenize the APL source code from right to left, as that is the execution order of APL. Hopefully this decision doesn't come and bite me later!

By the way, this might be a great moment to let you know that I make mistakes! Lots of them! If at a given point you have an idea to do something in a different way, please do try it out and then let me know in the comments below how it went.

Going back to our program, we already have the Token class, now we define our Tokenizer that takes a string and then builds the list of tokens. This is the beginning of the class:

class Tokenizer:<br>"""Class that tokenizes source code into tokens."""

def __init__(self, code):<br>self.code = code<br>self.pos = len(self.code) - 1<br>self.current_char = self.code[self.pos]

def error(self, message):<br>"""Raises a Tokenizer error."""<br>raise Exception(f"TokenizerError: {message}")

def advance(self):<br>"""Advances the cursor position and sets the current character."""

self.pos -= 1<br>self.current_char = None if self.pos<br>We instantiate this class with the string with APL code, for example with Tokenizer("5 + 6"). The error function is used as a helper function, to raise an exception when something goes wrong with the Tokenizer.

Finally, the advance function is a little utility function...