# 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)
{
{
RETURN(x + y)
}
}

``````

## 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_] ;
``````

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 `RETURN`ed, 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.

View Github