Posted on Feb 3, 2022

100 Languages Speedrun: Episode 78: Better Whenever Interpreter with Python and SLY

A while back I covered Whenever - a language where the program is a todo list. Whenever has no functions, no variables, and the state is just a todo list. As long as there's something on it, it picks an item at random, and performs it.

For this episode, I want to create a better version of Whenever language. It's mostly backwards compatible with the original and can run every Whenever program I could find. However, behavior for edge cases isn't documented anywhere, and absolute compatibility isn't the goal.

I made the following changes to make it more convenient, while keeping the challenge level just high as before:

todo items can be identified by name, not just line number
todo items don't need to be in any specific order
empty lists are allowed
comments with // are allowed
semicolons are optional
you can mix print actions and counter actions in the same todo
if you name one of the todo items as start, program will begin with it as the only active action on the todo list
it uses much smarter execution model, so it can run much more ambitious programs than the original interpreter
it detects some infinite loops if no action can possibly happen and throws an error
it uses infinite precision integers
! is supported
I didn't add forget as it's listed as deprecated

How it works

There's a lot of code coming, and it's only somewhat commented, so here's the big picture overview:

you can run it with whenever.py whenever_file.txt
lexer and parser are implemented with SLY, I recently wrote about it, check it out if you need some help understanding how SLY works
WheneverLexer.py implements the lexer, which turns Whenever program into a stream of tokens like ["print", "(", '"Hello, World!"', ")"] - it also handles trivial things like removing comments
WheneverParser.py implements the parser, which turns that stream of tokens into a program
WheneverEval.py is all the code that evaluates Whenever expressions, dealing with all the operators, type conversions, and so on
whenever.py runs the program using the previous classes

I'll go into a bit of detail when I deal with each of the files.

Examples of Better Whenever Programs

I included all examples from previous episode, as well as all examples from official documentation, but since I want to improve the language I also included a few more.

math.txt, just a quick test script to check that operators have correct precedence:

a print(300 + 50 * 4 + 80 / 4 - (80 - 30) * 2)

fizzbuzz.txt, a simple program simplified to take advantage of new features like comments, no-semicolons, and start, but still using numbers for todo items:

// start start 10,11 // variables 2 2 3 3 4 4 // printing 5 defer((N(6) + N(7) + N(8) + N(9)) != 3) 6#-N(6),7#-N(7),8#-N(8),9#-N(9) 6 defer(N(3) == 0 || N(4) == 0) print(N(2)) 7 defer(3 || N(4) == 0) print("Fizz") 8 defer(N(3) == 0 || 4) print("Buzz") 9 defer(3 || 4) print("FizzBuzz") // loop logic 10 defer(5 || N(2) >= 100) 2,3,-3#((N(3)/3)*3),4,-4#((N(4)/5)*5),5,6,7,8,9,10 11 defer(5 || N(2) < 100) -2#N(2),-3#N(3),-4#N(4),-10#N(10)

fizzbuzz2.txt, same, but now with all todo items named, and ! used:

// start start loop,loopend // variables a a t t f f // printing prn defer((N(pn) + N(pf) + N(pb) + N(pfb)) != 3) -pn#N(pn),-pf#N(pf),-pb#N(pb),-pfb#N(pfb) pn defer(!t || !f) print(N(a)) pf defer(t || !f) print("Fizz") pb defer(!t || f) print("Buzz") pfb defer(t || f) print("FizzBuzz") // loop logic loop defer(prn || N(a) >= 100) a,t,-t#((N(t)/3)*3),f,-f#((N(f)/5)*5),prn,pn,pf,pb,pfb,loop loopend defer(prn || N(a) < 100) -a#N(a),-t#N(t),-f#N(f),-loop#N(loop)

`WheneverLexer.py`

This is the simplest file. Possibly improvements would be support for escape codes like \n in strings (but then print would need to change to stop autoprinting \n), and maybe some extra features like read or forget. I also didn't bother tracking line numbers, so error messages won't be great.

from sly import Lexer class WheneverLexer(Lexer): tokens = { PLUS, MINUS, TIMES, DIVIDE, LPAREN, RPAREN, COMMA, HASH, REL, NUM, ID, EOS, STRING, AND, OR, NOT, PRINT, DEFER, AGAIN, N, TRUE, FALSE, MOD } ignore = " \t\r" EOS = r"(\n|;|//[^\n]*\n)+" PLUS = r"\+" MINUS = r"-" TIMES = r"\*" DIVIDE = r"/" MOD = r"%" LPAREN = r"\(" RPAREN = r"\)" COMMA = "," HASH = "#" REL = r"<=|<|>=|>|==|!=" OR = r"\|\|" AND = "&&" NOT = "!" STRING = r'"[^"]*"' NUM = r"[0-9]+" ID = r"[a-zA-Z_][a-zA-Z0-9_]*" ID['again'] = AGAIN ID['defer'] = DEFER ID['false'] = FALSE ID['N'] = N ID['print'] = PRINT ID['true'] = TRUE def NUM(self, t): t.value = int(t.value) return t def STRING(self, t): t.value = t.value[1:-1] return t

SLY makes defining lexers really easy.

`WheneverParser.py`

The parser is long, but not really complicated. For AST I just use Python dictionaries, and I use explicit rules like exprm instead of precedence tables, as I'm more used to this style. SLY by default has really weird error handling (print error to stderr, do nothing), so we need to override it to throw proper exceptions. I used the same messages as would be printed.

For simplicity, I don't distinguish between identifier (basically symbols) and strings, so you can do N("loop") or print(Fizz), even though that shouldn't really be supported. It's largely harmless for now.

Most of the syntax is fairly obvious. One somewhat unusual thing I did was explicitly disallowing multiple comparison at the same level without parentheses, like (1 == 2 == 3 or 1 < 2 == 3 < 4), as that's just really confusing.

from sly import Parser from WheneverLexer import WheneverLexer class WheneverParser(Parser): tokens = WheneverLexer.tokens @_("") def program(self, p): return {} @_("EOS program") def program(self, p): return p.program @_("todo program") def program(self, p): program = p.program id, todo = p.todo if id in program: raise Exception(f"Duplicate todo id: {id}") program[id] = todo return program @_("id modifiers actions EOS") def todo(self, p): again = [] defer = [] for mod in p.modifiers: if "again" in mod: again.append(mod["again"]) if "defer" in mod: defer.append(mod["defer"]) return (p.id, {"again": again, "defer": defer, "actions": p.actions}) @_("") def modifiers(self, p): return [] @_("modifier modifiers") def modifiers(self, p): return [p.modifier] + p.modifiers @_("DEFER LPAREN expr RPAREN") def modifier(self, p): return {"defer": p.expr} @_("AGAIN LPAREN expr RPAREN") def modifier(self, p): return {"again": p.expr} @_("action") def actions(self, p): return [p.action] @_("action COMMA actions") def actions(self, p): return [p.action] + p.actions @_("id") def action(self, p): return {"action": "change", "id": p.id, "count": {"value": 1}} @_("MINUS id") def action(self, p): return {"action": "change", "id": p.id, "count": {"value": -1}} @_("id HASH expr") def action(self, p): return {"action": "change", "id": p.id, "count": p.expr} @_("MINUS id HASH expr") def action(self, p): return {"action": "change", "id": p.id, "count": {"op": "uminus", "a": p.expr}} @_("PRINT LPAREN expr RPAREN") def action(self, p): return {"action": "print", "arg": p.expr} # expr, going through all the priority levels  @_("exprlo") def expr(self, p): return p.exprlo ### expr logical or  @_("exprla") def exprlo(self, p): return p.exprla @_("exprlo OR exprla") def exprlo(self, p): return {"op": "||", "a": p.exprlo, "b": p.exprla} ### expr logical and  @_("exprr") def exprla(self, p): return p.exprr @_("exprla AND exprr") def exprla(self, p): return {"op": "&&", "a": p.exprla, "b": p.exprr} ### expr relational  ### do not support chaining them without parentheses  @_("expra") def exprr(self, p): return p.expra @_("expra REL expra") def exprr(self, p): return {"op": p.REL, "a": p.expra0, "b": p.expra1} ### expr additive  @_("expra PLUS exprm") def expra(self, p): return {"op": "+", "a": p.expra, "b": p.exprm} @_("expra MINUS exprm") def expra(self, p): return {"op": "-", "a": p.expra, "b": p.exprm} @_("exprm") def expra(self, p): return p.exprm ### expr multiplicative  @_("exprm TIMES expru") def exprm(self, p): return {"op": "*", "a": p.exprm, "b": p.expru} @_("exprm DIVIDE expru") def exprm(self, p): return {"op": "/", "a": p.exprm, "b": p.expru} @_("exprm MOD expru") def exprm(self, p): return {"op": "%", "a": p.exprm, "b": p.expru} #### expr unary  @_("expru") def exprm(self, p): return p.expru @_("value") def expru(self, p): return p.value @_("NOT expru") def expru(self, p): return {"op": "!", "a": p.expru} @_("MINUS expru") def expru(self, p): return {"op": "uminus", "a": p.expru} ### primitive value  @_("LPAREN expr RPAREN") def value(self, p): return p.expr # No reason to distinguish between foo and "foo" yet  @_("ID") def value(self, p): return {"value": p.ID} @_("NUM") def value(self, p): return {"value": p.NUM} @_("N LPAREN id RPAREN") def value(self, p): return {"N": p.id} @_("STRING") def value(self, p): return {"value": p.STRING} @_("TRUE") def value(self, p): return {"value": True} @_("FALSE") def value(self, p): return {"value": False} @_("ID") def id(self, p): return p.ID @_("NUM") def id(self, p): return p.NUM def error(self, token): if token: lineno = getattr(token, "lineno", 0) if lineno: raise Exception(f"sly: Syntax error at line {lineno}, token={token.type}") else: raise Exception(f"sly: Syntax error, token={token.type}") else: raise Exception("sly: Parse error in input. EOF")

`WheneverEval.py`

Evaluating expressions involves so much code I put it into a separate file. Whenever has unusual type coercions - for example 3 || !4 means N(3) > 0 || !(N(4) > 0). Whenever also converts everything to string if added to a string, and converts strings (just initial digits, or 0 if there aren't any initial digits) and booleans to ints when used in int context.

I make comparison operators >, <, >=, <=, ==, and != also convert to integers. Whenever doesn't really do anything useful with strings except printing them anyway, so there's never any point doing "foo" == "bar" anyway.

Things like type coercions are among things that could be improved, but that would cost backwards compatibility.

class WheneverEval: def __init__(self, program): self.program = program def int_eval_node(self, node): a = self.int_eval(node["a"]) b = self.int_eval(node["b"]) return (a, b) def int_eval(self, node): return self.int(self.eval(node)) def bool_eval(self, node): return self.bool(self.eval(node)) def str_eval(self, node): return self.str(self.eval(node)) # A lot of aggressive casting to int here  def eval(self, node): if "value" in node: return node["value"] if "N" in node: return self.program.counters[node["N"]] if "op" not in node: raise Exception(f"Neither op nor value? {node}") op = node["op"] if op == "-": (a, b) = self.int_eval_node(node) return a - b if op == "*": (a, b) = self.int_eval_node(node) return a * b if op == "/": (a, b) = self.int_eval_node(node) return a // b if op == "%": (a, b) = self.int_eval_node(node) return a % b # Not even clear about this one:  if op == "+": a = self.eval(node["a"]) b = self.eval(node["b"]) if isinstance(a, str) or isinstance(b, str): return self.str(a) + self.str(b) else: return self.int(a) + self.int(b) if op == "uminus": a = self.int_eval(node["a"]) return -a if op == "||": a = self.bool_eval(node["a"]) b = self.bool_eval(node["b"]) return a or b if op == "&&": a = self.bool_eval(node["a"]) b = self.bool_eval(node["b"]) return a and b if op == "!": a = self.bool_eval(node["a"]) return not a if op == "<": (a, b) = self.int_eval_node(node) return a < b if op == "<=": (a, b) = self.int_eval_node(node) return a <= b if op == ">": (a, b) = self.int_eval_node(node) return a > b if op == ">=": (a, b) = self.int_eval_node(node) return a >= b if op == "==": (a, b) = self.int_eval_node(node) return a == b if op == "!=": (a, b) = self.int_eval_node(node) return a != b raise Exception(f"TODO: Operation {op} not supported yet") def int(self, value): if isinstance(value, bool): if value == True: return 1 if value == False: return 0 if isinstance(value, int): return value if isinstance(value, str): if re.match(r"^-?\d+", value): return int(value) else: return 0 raise Exception(f"Invalid type {value}") def bool(self, value): if isinstance(value, bool): return value return self.program.counters[value] > 0 def str(self, value): if isinstance(value, bool): if value == True: return "true" if value == False: return "false" if isinstance(value, str): return value if isinstance(value, int): return str(value) raise Exception(f"Invalid type {value}")

`whenever.py`

And finally the main program.

The main execution loop is like this:

if there's start symbol, start with counters at {start: 1, evertyhing_else: 0}. Otherwise give everything starting counter of 1.
mark any rule like n n as trivial - these do nothing when executed, we still need to track their value, but we never need to actually run them, as program state is same before and after running it (we could ignore defer here etc. for more optimization)
as long as there's a nontrivial rule with nonzero counter, pick something at random at run it

Trivial next todo selection algorithm would result in exceedingly slow execution. For example fib from official documentation is so slow in it that it never finishes. With this improved interpreter it finishes in almost no time.

every time, we copy list of all nontrivial rules as actionable
we pick a rule at random from among actionable
we check if rule is deferred, if yes, we remove it from actionable set and try again
if program isn't finished, but all rules are trivial or deferred, we raise exception instead of doing infinite loop

This means if we have situation like this:

N(1) - 17167680177566 times, deferred while N(3) > 0
N(2) - 27777890035289 times, deferred while N(3) > 0
N(3) - 1 times, actionable

We don't have to keep re-rolling 17167680177566+27777890035289+1 times until we get to run todo item 3.

The algorithm is lazy, so we only check deferred rule if we rolled it, so normally it shouldn't slow us down. The interpreter is still not very optimized, and it's definitely possible to write very slow programs for it, but at least it avoids those exponential slowdowns for such very simple programs.

#!/usr/bin/env python3  import sys from WheneverLexer import WheneverLexer from WheneverParser import WheneverParser from WheneverEval import WheneverEval from random import randint class WheneverProgram: def __init__(self, path): self.path = path with open(path) as f: self.text = f.read() lexer = WheneverLexer() parser = WheneverParser() self.program = parser.parse(lexer.tokenize(self.text)) self.eval = WheneverEval(self) # A lot more optimizations are possible  # total is the sum of all nontrivial counters  def init_counters(self): self.total = 0 self.trivial = set() self.nontrivial = set() self.counters = {} has_start = ("start" in self.program) for id in self.program.keys(): if id == "start" or not has_start: starting_value = 1 else: starting_value = 0 self.counters[id] = starting_value is_trivial = (self.program[id] == {'again': [], 'defer': [], 'actions': [{'action': 'change', 'id': id, 'count': {'value': 1}}]}) if is_trivial: self.trivial.add(id) else: self.nontrivial.add(id) self.total += starting_value def is_deferred(self, id): for expr in self.program[id]["defer"]: if self.eval.bool_eval(expr): return True return False def random_todo(self, actionable, actionable_total): i = randint(0, actionable_total - 1) for id in actionable: i -= self.counters[id] if i < 0: return id raise Exception("Math failure") def execute_random_todo(self): actionable = self.nontrivial.copy() actionable_total = self.total while True: if actionable_total == 0: raise Exception("All actions are deferred") id = self.random_todo(actionable, actionable_total) if self.is_deferred(id): actionable.remove(id) actionable_total -= self.counters[id] else: self.execute_todo(id) return # defer is checked before we call this  def execute_todo(self, id): todo = self.program[id] again = todo["again"] remove_todo = True for expr in todo["defer"]: if self.eval.bool_eval(expr): remove_todo = False for action in todo["actions"]: self.execute_action(action) if remove_todo: self.update_counter(id, -1) def execute_action(self, action): action_type = action["action"] if action_type == "print": s = self.eval.str_eval(action["arg"]) print(s) elif action_type == "change": id = action["id"] count = self.eval.int_eval(action["count"]) self.update_counter(id, count) else: raise Exception(f"Unknown action: {action_type}") def update_counter(self, id, change): old_value = self.counters[id] new_value = old_value + change if new_value < 0: new_value = 0 self.counters[id] = new_value if id not in self.trivial: self.total += (new_value - old_value) def run(self): self.init_counters() while self.total > 0: self.execute_random_todo() if sum(self.counters.values()) != 0: raise Exception("Program entered do-nothing infinite loop") program = WheneverProgram(sys.argv[1]) program.run()

Should you try Better Whenever?

I think the improved version is much more friendly, as things like comments, variable names, start rule just make the whole coding process more pleasant, and you can focus on doing crazy things in a language with esoteric execution model without all the hassle of turning everything into numbers.

It also definitely helps that this interpreter avoids a lot of exponential slowdown.

Like everything else in this series, I hacked this program during one evening, so it's not perfect. If you're interested in improving it further, let me know, and I can setup proper repository, documentation, specs etc. for it.

This interpreter follows the original idea very closely, but it's definitely possible to do something more creative with the "program as todo list" idea, just like AsciiDots really evolved Befunge idea.