A tiny lisp implemented in Lua

lualisp.lua

io.stdout:setvbuf("no")

-- turns an input string into a list of tokens
-- where tokens are strings
function tokenize(input)
    local result = {}
    local token = ""
    local inString = false

    for i=1, #input do
        local char = input:sub(i,i)

        if char == "\"" then inString = not inString end

        if not inString and (char == " " or char == "(" or char == ")") then
            if #token >= 1 then
                table.insert(result, token)
                token = ""
            end

            if char ~= " " then table.insert(result, char) end
        else
            token = token .. char
        end
    end

    return result
end

-- turns a flat list of tokens into a list of lists of tokens according to the parenthesis
-- also turns atoms into more appropriate datatypes, like numbers into numbers
function readFromTokens(tokens)
    assert(#tokens > 0, "unexpected EOF")

    local token = table.remove(tokens, 1)

    if token == "(" then
        local list = {}

        while tokens[1] ~= ")" do
            table.insert(list, readFromTokens(tokens))
        end
        
        -- remove the closing paren
        local token = table.remove(tokens, 1)

        return list
    else
        assert(token ~= ")", "unexpected )")

        -- if the token can be parsed as a number, convert it into a number
        local number = tonumber(token)
        if number then return number end

        -- otherwise just keep it as a string
        return token
    end
end

function parse(input)
    return readFromTokens(tokenize(input))
end

-- creates a new environment for the program
function createEnvironment(inherit)
    local env = {
        ["+"] = function (x, y) return x + y end,
        ["-"] = function (x, y) return x - y end,
        ["*"] = function (x, y) return x * y end,
        ["/"] = function (x, y) return x / y end,
        [">"] = function (x, y) return x > y end,
        ["<"] = function (x, y) return x < y end,
        ["<="] = function (x, y) return x <= y end,
        [">="] = function (x, y) return x >= y end,
        ["=="] = function (x, y) return x == y end,
        begin = function (...) return select(select("#", ...), ...) end, -- returns the last token in its list
        print = function (...)
            -- print all the elements in the list
            for i=1, select("#", ...) do
                local this = select(i, ...)
                if this then
                    print(type(this) == "string" and this:sub(2,#this-1) or this)
                end
            end
        end,
    }

    -- add every lua math function into the default environment
    for i, v in pairs(math) do env[i] = v end

    -- if a symbol lookup returns nothing, look in the parent environment
    -- if there is no parent environment, this does nothing so it's fine
    return setmetatable(env, {__index = inherit})
end

-- evaluates expressions in an enviroment
function eval(x, env)
    if type(x) == "string" then
        if x:sub(1,1) == "\"" and x:sub(#x,#x) == "\"" then
            -- return strings as they are, don't dereference them in the environment
            return x
        end
        return env[x]
    end

    if type(x) == "number" then
        return x
    end

    if x[1] == "if" then
        return eval(x[2], env) and eval(x[3], env) or eval(x[4], env)
    end

    if x[1] == "define" then
        local result = eval(x[3], env)
        env[x[2]] = result
        return result
    end

    if x[1] == "lambda" then
        local lambda = {
            params = x[2],
            body = x[3],
            env = createEnvironment(env)
        }

        return setmetatable(lambda, {__call = function (self, ...)
            for i, param in ipairs(self.params) do
                self.env[param] = select(i, ...)
            end

            return eval(self.body, self.env)
        end})
    end

    -- call the function using the 2nd list element and up as arguments
    -- argify takes out the list elements as arguments to be used in the function using multireturns
    local function argify(n)
        if n < #x then
            return eval(x[n], env), argify(n+1)
        end
        return eval(x[n], env)
    end

    return eval(x[1], env)(argify(2))
end

local global = createEnvironment()

if arg[1] then
    -- run the file mode
    local contents = io.open(arg[1]):read("*a"):gsub("\n", "")
    print(eval(parse(contents), global))
else
    -- repl mode
    io.input(io.stdin)
    while true do
        io.write "lualisp> "
        local input = io.read()
        if input == "exit" then break end
        local success, parsed = xpcall(function () return parse(input) end, print)
        if success then
            local success, result = xpcall(function () return eval(parsed, global) end, print)
            if success then
                print(result)
            else
                global = createEnvironment()
            end
        else
            global = createEnvironment()
        end
    end
end