Некоторое время назад я рассказывал о Whenever — языке, в котором программа представляет собой список дел. В Whenever нет ни функций, ни переменных, а состояние — это просто список дел. Пока в нем что-то есть, он выбирает элемент наугад и выполняет его.
Для этого эпизода я хочу создать улучшенную версию языка Whenever. Он в основном обратно совместим с оригиналом и может выполнять все программы Whenever, которые я смог найти. Однако поведение для крайних случаев нигде не документировано, а абсолютная совместимость не является целью.
Я сделал следующие изменения, чтобы сделать его более удобным, сохранив при этом уровень сложности таким же высоким, как и раньше:
- элементы todo могут быть идентифицированы по имени, а не только по номеру строки
- пункты todo не обязательно должны быть расположены в определенном порядке
- разрешены пустые списки
- разрешены комментарии с
// - точки с запятой необязательны
- вы можете смешивать действия
printи действия счетчика в одном todo - если вы назовете один из элементов todo как
start, программа начнется с него как с единственного активного действия в списке todo - использует более умную модель выполнения, поэтому может выполнять более амбициозные программы, чем оригинальный интерпретатор
- он обнаруживает некоторые бесконечные циклы, если ни одно действие не может произойти, и выбрасывает ошибку
- использует целые числа бесконечной точности
- Я не стал добавлять
forget, так как он внесен в список устаревших.
Как это работает
Здесь много кода, и он только немного прокомментирован, так что вот общий обзор:
- вы можете запустить его с помощью
whenever.py whenever_file.txt - лексер и парсер реализованы с помощью SLY, я недавно писал об этом, посмотрите, если вам нужна помощь в понимании того, как работает SLY.
Я буду вдаваться в подробности, когда буду разбираться с каждым из этих файлов.
Примеры лучших программ
Я включил все примеры из предыдущего эпизода, а также все примеры из официальной документации, но поскольку я хочу улучшить язык, я также включил еще несколько.
math.txt, просто быстрый тестовый скрипт для проверки того, что операторы имеют правильный приоритет:
a print(300 + 50 * 4 + 80 / 4 - (80 - 30) * 2)
fizzbuzz.txt, простая программа, упрощенная для использования новых возможностей, таких как комментарии, отсутствие запятых и start, но все еще использующая числа для элементов todo:
// 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, то же самое, но теперь все пункты названы по имени, и используется !:
// 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
Это самый простой файл. Возможным улучшением может быть поддержка кодов, таких как n в строках (но тогда print должен быть изменен, чтобы остановить автоматическую печать n), и, возможно, некоторые дополнительные функции, такие как read или forget. Я также не потрудился отслеживать номера строк, поэтому сообщения об ошибках будут не очень хорошими.
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 = " tr"
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 позволяет очень просто определять лексеры.
WheneverParser.py.
Парсер длинный, но не очень сложный. Для AST я просто использую словари Python, и я использую явные правила типа exprm вместо таблиц прецедентов, так как я больше привык к такому стилю. SLY по умолчанию имеет очень странную обработку ошибок (печатает ошибку на stderr, ничего не делает), поэтому нам нужно переопределить ее, чтобы бросать правильные исключения. Я использовал те же сообщения, которые будут выводиться на печать.
Для простоты я не делаю различий между идентификатором (в основном символами) и строками, так что вы можете сделать N("loop") или print(Fizz), хотя на самом деле это не должно поддерживаться. На данный момент это в основном безвредно.
Большая часть синтаксиса достаточно очевидна. Одна несколько необычная вещь, которую я сделал, это явное запрещение множественного сравнения на одном уровне без круглых скобок, например (1 == 2 == 3 или 1 < 2 == 3 < 4), так как это просто очень запутывает.
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
Оценка выражений включает в себя так много кода, что я вынес ее в отдельный файл. Whenever имеет необычные коэрцитивы типов — например, 3 || !4 означает N(3) > 0 || !(N(4) > 0). Whenever также преобразует все в строку, если добавить к строке, и преобразует строки (только начальные цифры, или 0, если нет начальных цифр) и булевы в инты, если они используются в контексте int.
Операторы сравнения >, <, >=, <=, == и != также преобразуются в целые числа. Whenever не делает ничего полезного со строками, кроме их печати, поэтому в любом случае нет смысла делать "foo" == "bar".
Такие вещи, как коэрцитивность типов, можно улучшить, но это будет стоить обратной совместимости.
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
И, наконец, основная программа.
Основной цикл выполнения выглядит следующим образом:
- если есть символ
start, начинаем со счетчиков{start: 1, evertyhing_else: 0}. В противном случае дайте всему начальный счетчик, равный 1. - Пометьте любое правило типа
n nкак тривиальное — они ничего не делают при выполнении, нам все еще нужно отслеживать их значение, но нам никогда не нужно их выполнять, так как состояние программы одинаково до и после их выполнения (мы можем игнорировать defer здесь и т.д. для большей оптимизации). - пока существует нетривиальное правило с ненулевым счетчиком, выбирайте что-нибудь наугад при его выполнении.
Тривиальный алгоритм выбора следующего todo приведет к чрезвычайно медленному выполнению. Например, fib из официальной документации выполняется настолько медленно, что никогда не завершается. С этим улучшенным интерпретатором он завершается практически мгновенно.
- каждый раз мы копируем список всех нетривиальных правил как
actionable - мы выбираем случайное правило из числа
actionable - проверяем, является ли правило отложенным, если да, то удаляем его из набора
actionableи пробуем снова - если программа не завершена, но все правила тривиальны или отложены, мы выдаем исключение, а не делаем бесконечный цикл.
Это означает, что если у нас такая ситуация:
- N(1) — 17167680177566 раз, отложено while N(3) > 0
- N(2) — 27777890035289 раз, отложено, пока N(3) > 0
- N(3) — 1 раз, выполнимо
Нам не нужно повторять 17167680177566+27777890035289+1 раз, пока мы не выполним пункт 3.
Алгоритм ленивый, поэтому мы проверяем отложенное правило, только если мы его прокрутили, так что обычно это не должно нас замедлять. Интерпретатор все еще не очень оптимизирован, и для него определенно можно писать очень медленные программы, но, по крайней мере, он позволяет избежать экспоненциального замедления для таких простых программ.
#!/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()
Стоит ли вам попробовать Better Whenever?
Я думаю, что улучшенная версия намного более дружелюбна, поскольку такие вещи, как комментарии, имена переменных, правило start просто делают весь процесс кодирования более приятным, и вы можете сосредоточиться на выполнении безумных вещей на языке с эзотерической моделью выполнения без всех этих хлопот по преобразованию всего в числа.
Также определенно помогает то, что этот интерпретатор позволяет избежать многих экспоненциальных замедлений.
Как и все остальное в этой серии, я взломал эту программу за один вечер, поэтому она не идеальна. Если вы заинтересованы в ее дальнейшем улучшении, дайте мне знать, и я смогу создать для нее соответствующий репозиторий, документацию, спецификации и т.д.
Этот интерпретатор очень точно следует оригинальной идее, но с идеей «программа как список дел» определенно можно сделать что-то более творческое, так же как AsciiDots действительно развил идею Befunge.
Код
Все примеры кода для этой серии будут находиться в этом репозитории.
Код для эпизода Better Whenever Interpreter with Python and SLY доступен здесь.