Quill is a small stack language. Write run_quill(program, limit), where program is a list of source lines, and return the list of output lines the program produces. Lines are numbered from 1.
Values. A value is an integer (any size) or a string. The text form of an integer is its decimal representation (with - if negative); the text form of a string is the string itself. A value is false if it is the integer 0 or the empty string, and true otherwise.
Reading a line. Scan it from left to right:
- Spaces separate tokens. Outside a string literal,
#starts a comment that runs to the end of the line. - A string literal starts with
"and ends at the next"that is not escaped. Inside it,\"is a quote,\\is a backslash and\nis a newline character; any other use of a backslash makes the line invalid. The closing quote must be followed by a space, a#or the end of the line, and a string that is never closed makes the line invalid. - Any other token is a word: a maximal run of characters that are not a space,
#or". A word directly followed by"makes the line invalid. - If the first token is a word ending in
:, it is a label and the rest of the word must be an identifier (a letter or_, then letters, digits or_). A label must not be defined twice; the second definition makes its line invalid. - The next token, if any, is the instruction name (a word from the table below) and the tokens after it are its arguments. Each instruction takes exactly the arguments listed. An integer literal is an optional
-followed by one or more digits;Nis one or more digits;NAMEis an identifier;Lis an identifier that must be a label defined somewhere in the program. Anything else makes the line invalid. - A line with no instruction (blank, only a comment, or only a label) is an empty line.
If any line is invalid, the program does not run and the output is exactly ["error at line K: syntax"], where K is the smallest invalid line number.
Running. The machine has a value stack, a table of global variables, a stack of call frames (each holding a return line and its own local variables) and a stack of handlers. Execution starts at line 1 with everything empty. After a line, execution continues with the next line unless the instruction jumps. Jumping to label L continues at the line that defines L. Execution stops normally after halt or when it moves past the last line (even inside a call).
Empty lines are passed over and are not instructions. Every executed instruction counts one step. If limit instructions have already been executed and another instruction is about to run, append "limit reached" to the output and stop.
In the table, "pop b, then a" means b is the top value and a the one below it, and both are removed. An instruction that needs k values when fewer than k are on the stack fails with stack underflow (this is checked before any type check).
| Instruction | Effect |
|---|---|
push X |
push X, an integer literal or a string literal |
pop |
remove the top value |
dup |
push a copy of the top value |
swap |
exchange the top two values |
over |
pop b, then a; push a, b, a |
rot |
pop c, then b, then a; push b, c, a |
pick N |
push a copy of the value N places below the top (pick 0 copies the top); underflow if the stack has N or fewer values |
depth |
push the number of values on the stack |
add |
pop b, then a; two integers give a + b, otherwise push the text form of a followed by the text form of b |
sub |
pop b, then a; push a - b |
mul |
pop b, then a; two integers give a * b; one string and one integer (either order) give the string repeated that many times (none if the integer is 0 or negative); two strings: type error |
div |
pop b, then a; the quotient a / b rounded toward zero |
mod |
pop b, then a; a - b * q where q is the div result |
neg |
pop a; push -a |
not |
pop a; push 1 if a is false, else 0 |
eq |
pop b, then a; push 1 if they are the same kind of value and equal, else 0 |
lt |
pop b, then a; push 1 if a < b, else 0; integers compare numerically, strings by character codes (as in Python); an integer and a string: type error |
len |
pop a string; push its length |
str |
pop a; push its text form |
num |
pop a; an integer is pushed back unchanged; a string that is an optional - followed by one or more digits is pushed as that integer; any other string: bad number |
at |
pop i, then s; push the one-character string s[i], where a negative i counts from the end as in Python; index out of range if there is no such character |
print |
pop a; append its text form to the output |
store NAME |
pop a; if the current frame has a local NAME, set it; otherwise set the global NAME |
load NAME |
push the current frame's local NAME if there is one, otherwise the global NAME; undefined variable if neither exists |
local NAME |
create (or reset) the local NAME of the current frame with the value 0; no frame outside any call |
jmp L |
jump to L |
jz L |
pop a; jump to L if a is false |
jnz L |
pop a; jump to L if a is true |
call L |
push a new frame (no locals, returning to the next line) and jump to L |
ret |
remove the current frame, discard every handler installed while that frame was current, and continue at its return line; no frame if there is none |
try L |
install a handler that remembers L, a copy of the whole value stack and the number of frames |
untry |
remove the most recently installed handler; no handler if there is none |
throw |
pop a; fail with the text form of a as the message |
halt |
stop |
sub, div, mod and neg need integers, len needs a string, and at needs an integer i and a string s; anything else is a type error. div and mod by zero fail with division by zero. Only the current frame's locals are visible: a called routine does not see its caller's locals.
Failures. When an instruction on line K fails with a message M: if no handler is installed, append "error at line K: M" and stop. Otherwise remove the most recently installed handler, set the value stack to its saved copy with the string M pushed on top, remove frames until only the saved number remain, and jump to its label. Variables are not restored.
Examples
Input: program = ['push 3', 'top: dup', 'print', 'push 1', 'sub', 'dup',
'jnz top', 'pop', 'push "done"', 'print'], limit = 100
Output: ['3', '2', '1', 'done']
Input: program = ['push 1', 'psh 2', 'print'], limit = 100
Output: ['error at line 2: syntax']
Input: program = ['a: jmp a'], limit = 5
Output: ['limit reached']
Constraints
0 <= len(program) <= 200; each line has at most 100 characters, all printable ASCII or spaces (no tabs).0 <= limit <= 10**5- Error messages are exactly the ones named above:
stack underflow,type error,division by zero,bad number,index out of range,undefined variable,no frame,no handler, or the text thrown bythrow.
Goals
- Turn a long precise specification into a working interpreter
- Separate lexing, validation and execution cleanly
- Implement exceptions that unwind both the value stack and the call stack