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

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: """Represents a token parsed from the source code."""

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

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

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

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

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

def __repr__(self): return self.__str__() 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: """Class that tokenizes source code into tokens."""

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

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

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

self.pos -= 1 self.current_char = None if self.pos < 0 else self.code[self.pos]

# ... 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 that moves the "cursor" of the tokenizer to the left and redefines the helper variable holding the current_char.

When we have gone through all of the APL code and we reach the end of the string (which really is the beginning because we are going from right to left) we set the current_char to None so we know there is nothing more to handle. With this skeleton built, this is the rest of the class: class Tokenizer:

# ...

def skip_whitespace(self): """Skips all the whitespace in the source code."""

while self.current_char and self.current_char in " \t": self.advance()

def get_integer(self): """Parses an integer from the source code."""

end_idx = self.pos while self.current_char and self.current_char.isdigit(): self.advance() return self.code[self.pos+1:end_idx+1]

def get_number_token(self): """Parses a number token from the source code."""

parts = [self.get_integer()] # Check if we have a decimal number here. if self.current_char == ".": self.advance() parts.append(".") parts.append(self.get_integer()) # Check for a negation of the number. if self.current_char == "¯": self.advance() parts.append("-")

num = "".join(parts[::-1]) if "." in num: return Token(Token.FLOAT, float(num)) else: return Token(Token.INTEGER, int(num))

def get_wysiwyg_token(self): """Retrieves a WYSIWYG token."""

char = self.current_char if char in Token.mapping: self.advance() return Token(Token.mapping[char], char)

self.error("Could not parse WYSIWYG token.")

def get_next_token(self): """Finds the next token in the source code."""

self.skip_whitespace() if not self.current_char: return Token(Token.EOF, None)

if self.current_char in "0123456789": return self.get_number_token()

if self.current_char in Token.WYSIWYG: return self.get_wysiwyg_token()

self.error("Could not parse the next token...")

def tokenize(self): """Returns the whole token list."""

tokens = [self.get_next_token()] while tokens[-1].type != Token.EOF: tokens.append(self.get_next_token()) return tokens[::-1] With the code above, the expression 5 -⍨ ¯2.3 would get tokenized into [Token(EOF, None), Token(INTEGER, 5), Token(MINUS, -), Token(COMMUTE, ⍨), Token(FLOAT, -2.3)] if we ran print(Tokenizer("5 -⍨ ¯2.3").tokenize()). Don't believe me? Just copy the expression 5 -⍨ ¯2.3 and then paste it into the read-eval-print-loop you get when you run the script. Finding structure in the Token list Now that we have all the tokens, we want to represent them in a more structured way. For that purpose we will build what is called an Abstract Syntax Tree (check Spivak's 7th LSBASI post). This AST structure will make it much easier for us to interpret an APL program; the price we have to pay is in building the tree first, which we do by traversing the Token list (from right to left once more) and then determining what are scalars, what are arrays, what are operators and what are dyadic/monadic functions. This is the job our AST will do. After that, interpreting a program becomes really easy. In order to know how to build the AST I started by coming up with a grammar for the subset of the APL language I wanted to implement. A grammar is just a notational tool that we use to specify what types of statements make sense in a language. In our case, we build a grammar to specify what types of statements make sense in APL. After banging my head against the wall so much it started to crack,

after a lot of thought, a lot of drafting and after some help from a friendly bunch at the APL Orchard, I wrote down this grammar that is supposed to be read from right to left: PROGRAM := EOF STATEMENT STATEMENT := ( ARRAY FUNCTION | FUNCTION

)* ARRAY ARRAY := ( "(" STATEMENT ")" | SCALAR )+ SCALAR := INTEGER | FLOAT FUNCTION := F | FUNCTION "⍨" F := "+" | "-" | "×" | "÷" Each line represents a rule, which may depend on rules below it, until we reach rules like the F or SCALAR rules, which can be checked by just looking at the tokens we have at hands. The way this grammar works is (reading the rules from top to bottom and from right to left because that is how APL interprets its programs):

A program is a statement followed by the end of the file; A statement is an array, followed by 0 or more occurrences of, either a single function (these will be monadic functions) or a function followed by another array (these will be dyadic functions); An array is 1 or more of a scalar or a parenthesized statement; A scalar is either an integer token or a float token; A function is a commute operator and a function, or just a single f; An f is just a short name for the set of all APL functions we know: +-×÷.

Notice how there's rules that reference each other and rules that reference rules higher up in the hierarchy; these self-references and recursions enrich our grammar but make the AST slightly harder to parse. The way we turn these rules into code to build the AST is simple; first we define types for the different nodes our AST is going to have, which for now are scalars, arrays, dyadic functions, monadic functions and operators: class ASTNode: """Stub class to be inherited by the different types of AST nodes.

The AST Nodes are used by the Parser instances to build an Abstract Syntax Tree out of the APL programs. These ASTs can then be traversed to interpret an APL program.