College Board Pseudocode Interpreter

A playground for this interpreter is up on my website.

This project is a mostly-functioning interpreter for College Board’s pseudocode specified on the AP Computer Science Principles Exam reference sheet. It’s implemented in JavaScript for a simple web playground. The interpreter is a simple tree walker which walks an AST generated by a recursive descent parser.

Making this was heavily inspired by Robert Nystron’s book Crafting Interpreters after I implemented Lox in TypeScript.

TODO

  • The INPUT native procedure isn’t implemented yet, but it should be simple to make a nice interface for it since the interpreter already uses async/await.
  • Errors are thrown in the console, but they should appear in the UI. …Actually, error handling is just really bad in general, so that needs to be fixed.
  • Binary operations don’t check for operand types; this is bad because some undefined operations mean that programs can escape into unallowed types like strings because of JavaScript’s type casting.
  • There might be bugs that need fixing; this wasn’t tested extensively.

Sample Code

Shown below are a few sample programs that show off some features.

Recursive fibbonacci numbers

PROCEDURE fib(n)
{
	IF(n ≤ 1)
	{
		RETURN(n)
	}
	RETURN(fib(n - 1) + fib(n - 2))
}

i ← 1
REPEAT 10 TIMES
{
	DISPLAY(fib(i))
	i ← i + 1
}
Factorial numbers with a list

list ← [1, 1]

REPEAT 10 TIMES
{
	length ← LENGTH(list)
	next ← list[length] * length
	APPEND(list, next)
}

DISPLAY(list)
Closures

PROCEDURE add(x)
{
	PROCEDURE addX(y)
	{
		RETURN(x + y)
	}
	RETURN(addX)
}

add5 ← add(5)

DISPLAY(add5(10))

Operator Precedence

Operators Associativity Description
Right Assignment
OR Left Logical OR
AND Left Logical AND
NOT Right Logical NOT
=, Left Equality
<, , >, Left Comparison
+, - Left Addition
*, /, MOD Left Multiplication
- Right Unary Negation
..(..), ..[..] Left Calls or Indexes
(...) Left Parentheses

Grammar

This is a slightly more formalized version of the grammar from the official reference sheet.

program         : statements ;

statements      : statement* ;

block           : "{" statements "}" ;

statement       : exprStmt
                | procedureStmt
                | ifStmt
                | repeatStmt
                | forEachStmt
                | returnStmt ;

exprStmt        : expr ;

ifStmt          : "IF" "(" expr ")" block ( "else" block )? ;

repeatStmt      : "REPEAT" "UNTIL" "(" expr ")" block
                | "REPEAT" expr "TIMES" block ;

forEachStmt     : "FOR" "EACH" ID "IN" expr block ;

procedureStmt   : "PROCEDURE" ID "(" params? ")" block ;

params          : ID ( "," ID )* ;

returnStmt      : "RETURN" "(" expr ")" ;

expr            : ( ID | ( call "[" expr "]" ) ) ( "←" expr )
                | or ;

or              : and ( "OR" and )* ;

and             : not ( "AND" not )* ;

not             : ( "NOT" )? equality ;

equality        : relational ( ( "=" | "≠" ) relational )* ;

relational      : arithmetic ( ( ">" | "≥" | "<" | "≤" ) arithmetic )* ;

arithmetic      : term ( ( "+" | "-" ) term )* ;

term            : factor ( ( "*" | "/" | "MOD" ) factor )* ;

factor          : ( "-" )? call ;

call            : primary ( ( "(" exprList? ")" ) | ( "[" expr "]" ) )* ;

primary         : NUMBER
                | ID
                | "[" exprList? "]"
                | "(" expr ")" ;

exprList        : expr ( "," expr )* ;

NUMBER          : DIGIT+ ;
ID              : ALPHA ( ALPHA | DIGIT )* ;

DIGIT           : [0-9] ;
ALPHA           : [a-zA-Z_] ;

Differences and Additions

There are a few differences or additions to the original reference sheet in this grammar. These include but are not necessarily limited to:

  1. AND and OR don’t have a specified precendece on the reference sheet, but in most languages, OR has a lower precedence than AND, so that was added to the grammar.
  2. The College Board doesn’t specify that logical operators should short-circuit, but it’s pretty logical that they should exist.
  3. College Board doesn’t say anything about variable scoping and assignment, so I went with block-scoping. When an assignment expression is used, if the variable on the left-hand side is not already declared, it is declared in the current block. If the variable already exists in a parent scope, then that variable is used. This way, the only way to shadow a variable is through procedure parameters.
  4. It’s never specified what type of values can be RETURNed, so everything is allowed. Allowing procedures to be returned has the side effect of adding closures.
  5. College Board doesn’t define a behavior for displaying lists or procedures from the DISPLAY procedure, so there were a few arbitrary decisions to support this.
  6. Obviously College Board doesn’t specify how to handle errors, so this interpreter is relatively lenient with types; it uses the same truthiness and mostly the same casting rules as JavaScript.
  7. Newlines don’t have any meaning in the grammar; the end of an expression is the end of the statement. That means that code such as:
a ← 1 b ← 1

is equivalent to:

a ← 1
b ← 1

This has some implications for writing code, because it’s possible to write write code like:

a ← 1
(4 + 5)

which looks like it should be two separate statements, but is actually equivalent to:

a ← 1(4 + 5)

which is clearly an error.

GitHub

View Github