--
-- strelnokoff.lua
-- Strelnokoff interpreter in Lua
--
-- Copyright (c) 2001-2024 Chris Pressey, Cat's Eye Technologies
-- This file is distributed under a 2-clause BSD license.
-- For more information, see the following file in the LICENSES directory:
-- SPDX-License-Identifier: LicenseRef-BSD-2-Clause-X-Strelnokoff
--
require "bigint"
use_bigint = false
ZERO = BigInt(0)
function zero()
if use_bigint then
return ZERO
else
return 0
end
end
ONE = BigInt(1)
function one()
if use_bigint then
return ONE
else
return 0
end
end
--
-- Debug
--
debug_what = ""
do_debug = function(what, fn)
if debug_what:find(what) then
fn()
end
end
debug = function(what, s)
do_debug(what, function() print("--> (" .. s .. ")") end)
end
render = function(v, count)
if not count then count = 0 end
if count > 100 then return "!!OVERFLOW!!" end
if type(v) == "table" then
local s = "{"
local key, value
for key, value in pairs(v) do
s = s .. render(key, count + 1) .. ": " .. render(value, count + 1) .. ","
end
return s .. "}"
else
return tostring(v)
end
end
--
-- Variant Records (for AST)
--
function make_vrecord(config)
return {
maker = function(tag)
local fields = config[tag]
if not fields then
error("Undefined tag: " .. tag)
end
return function(...)
local num_args = select("#", ...)
if num_args ~= #fields then
error(
"Arity error: expected " .. tostring(#fields) ..
" for " .. tag .. ", got " .. tostring(num_args)
)
end
return {
tag = tag,
field_values = {...}
}
end
end,
case = function(obj, cases)
local tag = obj.tag
local field_values = obj.field_values
local fields = config[tag]
if not fields then
error("Undefined tag: " .. tostring(tag))
end
if #fields ~= #field_values then
error(
"Arity error for tag: " .. tostring(tag) .. ", expected " .. tostring(#fields) ..
" got " .. tostring(#field_values) .. " (" .. render(obj) .. ")"
)
end
local sel = cases[tag] or cases.otherwise
if not sel then
error("No case for tag: " .. tag)
end
return sel(table.unpack(obj.field_values))
end
}
end
--
-- AST
--
local AST = make_vrecord({
program = {"assignments"},
assignment = {"varname", "expr"},
binop = {"op", "lhs", "rhs"},
action = {"action", "mode", "expr"},
literal = {"val"},
varaccess = {"name"},
})
local Program = AST.maker("program")
local Assignment = AST.maker("assignment")
local BinOp = AST.maker("binop")
local Action = AST.maker("action")
local Literal = AST.maker("literal")
local VarAccess = AST.maker("varaccess")
--
-- Scanner
--
local Scanner = {}
Scanner.new = function(source)
local self = {
source = source,
pos = 1,
token = nil,
toktype = nil,
}
setmetatable(self, {__index = Scanner})
self:scan()
return self
end
function Scanner:scan_space()
local a, b, done
while not done do
a, b = string.find(self.source, "^%s+", self.pos)
if a == self.pos then
self.pos = b + 1
else
a, b = string.find(self.source, "^REM[^\n]*\n", self.pos)
if a == self.pos then
self.pos = b + 1
else
done = true
end
end
end
end
function Scanner:scan()
self:scan_space()
local patterns = {
{"number", "%d+"},
{"ident", "[_%a][_%w]*"},
{"char", "'.'"},
{"symbol", "."},
}
for _, pair in ipairs(patterns) do
local pattern = "^" .. pair[2]
local a, b = string.find(self.source, pattern, self.pos)
if a == self.pos then
self.token = self.source:sub(a, b)
self.toktype = pair[1]
self.pos = b + 1
debug("scanner", "scanned '" .. self.token .. "', pos now " .. tostring(self.pos))
return
end
end
self.token = nil
self.toktype = "EOF"
end
function Scanner:expect(expected)
if self.token ~= expected then
error("Expected '" .. expected .. "' but found '" .. self.token .. "'")
end
self:scan()
end
function Scanner:dump_remaining()
print("what remains is '" .. self.source:sub(self.pos) .. "'")
end
function Scanner:run_scanner()
print(self.token, self.toktype, self.pos)
while self.toktype ~= "EOF" do
self:scan()
print(self.token, self.toktype, self.pos)
end
end
if TEST then
s = Scanner.new([[REM THIS IS A COMMENT
REM YOU BETCHA
and the rest
is histor123y 123yes 'C'razy
]])
s:run_scanner()
end
--
-- Parser
--
local Parser = {}
Parser.new = function(source)
local self = {
scanner = Scanner.new(source),
}
setmetatable(self, {__index = Parser})
return self
end
function Parser:consume_token()
local t = self.scanner.token
self.scanner:scan()
return t
end
function Parser:expect_toktype(toktype)
if self.scanner.toktype ~= toktype then
error("Expected " .. toktype .. " but found " .. self.scanner.toktype .. " '" .. self.scanner.token .. "'")
end
local t = self.scanner.token
self.scanner:scan()
return t
end
function Parser:program()
local assignments = {}
while self.scanner.toktype ~= "EOF" do
local assignment = self:assignment()
table.insert(assignments, assignment)
end
return Program(assignments)
end
function Parser:assignment()
local varname = self:expect_toktype("ident")
debug("parser", "varname: " .. varname)
self.scanner:expect("=")
local expr = self:expression0()
return Assignment(varname, expr)
end
function Parser:expression0()
local expr, t, rhs
expr = self:expression1()
while self.scanner.token == "=" or self.scanner.token == ">" do
t = self:consume_token()
rhs = self:expression1()
expr = BinOp(t, expr, rhs)
end
return expr
end
function Parser:expression1()
local expr, t, rhs
expr = self:expression2()
while self.scanner.token == "+" or self.scanner.token == "-" do
t = self:consume_token()
rhs = self:expression2()
expr = BinOp(t, expr, rhs)
end
return expr
end
function Parser:expression2()
local expr, t, rhs
expr = self:expression3()
assert(expr ~= nil)
while self.scanner.token == "*" or self.scanner.token == "/" do
t = self:consume_token()
rhs = self:expression3()
assert(rhs ~= nil)
expr = BinOp(t, expr, rhs)
end
return expr
end
function Parser:expression3()
local action
local mode = "int"
if self.scanner.token == "PRINT" then
action = "PRINT"
self.scanner:scan()
elseif self.scanner.token == "INPUT" then
action = "INPUT"
self.scanner:scan()
end
if self.scanner.token == "CHAR" then
mode = "char"
self.scanner:scan()
end
local expr = self:primitive()
if action == "PRINT" then
return Action("print", mode, expr)
else
return expr
end
end
function Parser:primitive()
debug("parse", "primitive " .. self.scanner.toktype)
if self.scanner.toktype == "number" then
local val = tonumber(self.scanner.token)
if use_bigint then val = BigInt(val) end
local expr = Literal(val)
self.scanner:scan()
return expr
elseif self.scanner.toktype == "char" then
local val = string.byte(self.scanner.token, 2)
if use_bigint then val = BigInt(val) end
local expr = Literal(val)
self.scanner:scan()
return expr
elseif self.scanner.token == "(" then
self.scanner:scan()
local expr = self:expression0()
self.scanner:expect(")")
return expr
else
local name = self:expect_toktype("ident")
debug("parse", "primitive varaccess " .. name)
return VarAccess(name)
end
end
--
-- Evaluator
--
store = {}
local render_store = function()
s = "{"
for key, value in pairs(store) do
if use_bigint then
local mt = getmetatable(value)
assert(mt ~= nil, "expected value to be bigint, instead it is " .. render(x))
end
s = s .. key .. "=" .. tostring(value) .. ", "
end
s = s .. "}"
return s
end
local evaluate
evaluate = function(ast)
assert(ast ~= nil, "ast is nil")
debug("eval", render(ast))
local result = AST.case(ast, {
program = function(assignments)
local index, result
local done = false
while not done do
-- TODO: narrow down the set of assignments to only those
-- we haven't got their "useless" flag set. If that set
-- is empty, terminate. If not, pick randomly from it.
index = math.random(1, #assignments)
debug("pick", "program: chose " .. tostring(index))
debug("monitor", "monitor BEFORE step: " .. render_store())
result = evaluate(assignments[index])
-- TODO: check the result to see if the assignment had
-- any effect. If it did not, set the "useless" flag on
-- this assignment. If it did, clear the "useless" flag
-- on all assignments.
debug("monitor", "monitor AFTER step: " .. render_store())
end
end,
assignment = function(varname, expr)
debug("eval", "assignment: " .. varname .. " = " .. render(expr))
local result = evaluate(expr)
store[varname] = result
return result
end,
binop = function(op, lhs, rhs)
debug("eval", "binop: " .. op .. "(" .. render(lhs) .. "," .. render(rhs) .. ")")
local lval, rval
if op == "+" then
lval = evaluate(lhs)
rval = evaluate(rhs)
return lval + rval
elseif op == "-" then
lval = evaluate(lhs)
rval = evaluate(rhs)
return lval - rval
elseif op == "*" then
lval = evaluate(lhs)
-- short-circuiting multiplication
if lval == zero() then
return lval
else
rval = evaluate(rhs)
return lval * rval
end
elseif op == "/" then
lval = evaluate(lhs)
rval = evaluate(rhs)
-- division by zero yields zero
if rval == zero() then
return rval
else
if use_bigint then
return lval / rval
else
return lval // rval
end
end
elseif op == "=" then
lval = evaluate(lhs)
rval = evaluate(rhs)
if lval == rval then
return one()
else
return zero()
end
elseif op == ">" then
lval = evaluate(lhs)
rval = evaluate(rhs)
if lval > rval then
return one()
else
return zero()
end
else
error("Not implemented BinOp: " .. op)
end
end,
action = function(action, mode, expr)
debug("eval", "action: " .. action .. " " .. mode .. " " .. render(expr))
local r
local val = evaluate(expr)
r = tostring(val)
if mode == "char" then
r = string.char(tonumber(r))
end
io.stdout:write(r)
io.stdout:flush()
return val
end,
literal = function(val)
return val
end,
varaccess = function(varname)
local v = store[varname]
if v == nil then
debug("eval", "varaccess: " .. varname .. " is empty, returning 0")
return zero()
else
debug("eval", "varaccess: " .. varname .. " is " .. tostring(v))
return v
end
end,
})
assert(result ~= nil, "result of evaluating " .. render(ast) .. " was nil")
return result
end
--
-- Loader
--
local load_file = function(filename)
local f = assert(io.open(filename, "r"))
local program_text = f:read("*all")
f:close()
return program_text
end
--
-- Main
--
function main(arg)
math.randomseed(os.time())
local filename
while #arg > 0 do
if arg[1] == "--debug" then
table.remove(arg, 1)
debug_what = arg[1]
elseif arg[1] == "--use-bigint" then
use_bigint = true
elseif arg[1] ~= "" then
filename = arg[1]
end
table.remove(arg, 1)
end
local program_text = load_file(filename)
local p = Parser.new(program_text)
local ast = p:program()
debug("ast", render(ast))
local result = evaluate(ast)
debug("result", result)
end
if arg ~= nil then
main(arg)
end