Bootstrapping a Forth in 46 lines of Moonscript code

There’s an article called Boostrapping a Forth in 40 lines of Lua code[sic]¹ that’s been around since around 2007. It’s a great article and I’d highly recommend reading it. However, I only recently found it after some interest in Forth.

This is the Forth outer interpreter in Lua from the above article reformatted a bit:

eval = function (str) return assert(loadstring(str))() end

subj = ""
pos = 1

parsebypattern = function (pat)
	local capture, newpos = string.match(subj, pat, pos)
	if newpos then
		pos = newpos
		return capture
	end
end

parsespaces	 = function () return parsebypattern("^([ \t]*)()") end
parseword	 = function () return parsebypattern("^([^ \t\n]+)()") end
parsenewline	= function () return parsebypattern("^(\n)()") end
parserestofline = function () return parsebypattern("^([^\n]*)()") end
parsewordornewline = function () return parseword() or parsenewline() end

getword = function ()
	parsespaces()
	return parseword()
end

getwordornewline = function ()
	parsespaces()
	return parsewordornewline()
end

_F = {}
_F["%L"] = function () eval(parserestofline()) end

mode= "interpret"
modes = {}

run = function () while mode ~= "stop" do modes[mode]() end end

interpretprimitive = function ()
	if type(_F[word]) == "function" then
		_F[word]()
		return true
	end
end

interpretnonprimitive = function () return false end -- stub
interpretnumber  = function () return false end -- stub
p_s_i = function () end -- print state, for "interpret" (stub)

modes.interpret = function ()
	word = getwordornewline() or ""
	p_s_i()
	local _ = interpretprimitive() or
			interpretnonprimitive() or
			interpretnumber() or
			error("Can't interpret: "..word)
end

This ends up being 56 lines of Lua code. However, without regard for readability, it’s easy to get the code < 30 lines of code. There are 11 lines of extra whitespace. In any case, it’s quite concise even as presented. The aforementioned article goes into implementing a few basic Forth words and some other domain specific languages. I’m, however, going to focus more on the implementation of the interpreter and the Forth word implementation. Some things you should note about the above code before moving on:

• pos and subj are global variables that must be set before calling run()
• The implementation focuses on defining the language syntax from within the interpreter with the ability to call Lua code
• As-is, it’s a bit awkward to be used by other code. I.e. it’s not structured like a normal Lua module. When I went about converting the code to Moonscript I wanted to try to take advantage of the features that Moonscript provides such as clases, modules, among others. This changes the design a bit, but I think it still provides a fair amount of flexibility. However, I couldn’t find a good way to use Lua or Moonscript within the interpreter like the original did. The actual lines of code ended up being 46 lines with 9 lines of extra white space.

import extend from require "moon"

export ^

class MiniForth
    new: (subj = "") =>
        @subject = subj
        @position = 1
        @dictionary = {}
        @mode = "interpret"
        @modes = {interpret: ->
            @word = @get_word_or_newline! or ""
            @p_s_i!
            @interpret_primitive! or @interpret_nonprimitive! or @interpret_number! or error string.format[[Can't interpret: "%s"]], @word
        }

    add_words: (words) => extend(@dictionary, words)

    parse_by_pattern: (pat) =>
        cap, newpos = string.match @subject, pat, @position
        if newpos
            @position = newpos
            cap

    parse_spaces: => @parse_by_pattern "^([ \t]*)()"
    parse_word: => @parse_by_pattern "^(%S+)()"
    parse_newline: => @parse_by_pattern "^(\n)()"
    parse_rest_of_line: => @parse_by_pattern "^([^\n]*)()"
    parse_word_or_newline: => @parse_word! or @parse_newline!

    get_word: =>
        @parse_spaces!
        @parse_word!

    get_word_or_newline: =>
        @parse_spaces!
        @parse_word_or_newline!

    interpret_primitive: => if type(@dictionary[@word]) == "function" then
        @dictionary[@word]!
        true

    interpret_nonprimitive: => false
    interpret_number: => false
    p_s_i: =>
    run: => while @mode != "stop" do @modes[@mode]!

I think the code is fairly straight forward. I converted many of the constructs from the Lua version, but within a class. The biggest things to note are:

• There is only one global variable, the class
• The class takes the subject as an argument (all the other members are accessible after construction.)
• add_words member function adds words to the dictionary (more on this later.)

Now, lets switch back to Lua code and examine how things are put implemented in miniforth.lua

subj = [==[
%L _F["\n"] = function () end
%L _F[""]   = function () mode = "stop" end
%L _F["[L"] = function () eval(parsebypattern("^(.-)%sL]()")) end
[L
    DS = { n = 0 }
    push = function (stack, x) stack.n = stack.n + 1; stack[stack.n] = x end
    pop  = function (stack) local x = stack[stack.n]; stack[stack.n] = nil;
    stack.n = stack.n - 1; return x endipt. I haven't done anything to examine potential limitations with the Moonscript version.
    _F["5"]   = function () push(DS, 5) end
    _F["DUP"] = function () push(DS, DS[DS.n]) end
    _F["*"]   = function () push(DS, pop(DS) * pop(DS)) end
    _F["."]   = function () io.write(" "..pop(DS)) end
L]
]==]

pos = 1
mode = "interpret"
run()

subj = "5 DUP * ."
pos = 1
mode = "interpret"
run()

This basically creates some new words within the dictionary. However, it does it from within the interpreter. First by creating a few basic words to handle new lines and empty lines (meaning “stop”.) Then a new word ("[L”) is created that aipt. I haven’t done anything to examine potential limitations with the Moonscript version.llows multiline Lua expressions. Then a datastack (“DS”) is created with two functions (“push” & “pop”), and then the rest of the words to make the subject “5 DUP * .” work as it would in Forth. This is put 5 on the stack, duplicate the top stack item, multiply the top two items on the stack, and printing the result.²

As I said, almost the entirety of the above is implemented from within the interpreter. This is in stark contrast to the Moonscript miniforth which implements everything outside the interpreter, in the class and subclasses.

class stack
    new: =>
        @s = {}

    peek: =>
        @s[#@s]

    push: (...) =>
        for n = 1, #arg do
            @s[#@s + 1] = arg[n]

    pop: (n = 1) =>
        x = {}
        while n > 0 do
            if #@s > 0
                table.insert x, @s[#@s]
                @s[#@s] = nil
            n -= 1
        unpack x

class MoonForth extends MiniForth
    new: (subj = "") =>
        super subj
        @DS = stack!
        @add_words {
            "5": -> @DS\push 5
            "DUP": -> @DS\push @DS\peek! if @DS\peek!
            "*": -> @DS\push @DS\pop! * @DS\pop!
            ".": -> io.write " " .. @DS\pop!
            "": -> @mode = "stop"
        }

mf = MoonForth [[ 5 DUP * . ]]
mf\run!

This code assumes all is in the same file (though I personally have them in separate files with the proper export & requires.) So I first go about implementing a stack class and then the MoonForth class’s constructor creates a stack member and adds the required words to the dictionary. The words themselves are quite similar. The way they’re added to the dictionary are very different. (However, the Lua version obviously could have been pure Lua pretty easily.)

I’ve also went a bit further with implementing many of the easy core words from ANS Forth

require "miniforth"
require "stack"

class MoonForth extends MiniForth
    new: (subj = "") =>
        super subj
        @DS = stack!
        @add_words {
            "?DUP": -> @DS\push @DS\peek! if @DS\peek! ~= 0
            "2DUP": ->
                s1, s2 = @DS\pop 2
                @DS\push s2, s1, s2, s1
            "DUP": -> @DS\push @DS\peek! if @DS\peek!
            "2DROP": -> @DS\pop 2
            "DROP": -> @DS\pop!
            "ROT": ->
                f, s, t = @DS\pop 3
                @DS\push f, t, s
            "SWAP": ->
                f, s = @DS\pop! 2
                @DS\push f, s

            "+": -> @DS\push @DS\pop! + @DS\pop!
            "-": ->
                @dictionary.SWAP!
                @DS\push @DS\pop! - @DS\pop!
            "*": -> @DS\push @DS\pop! * @DS\pop!
            "/": ->
                @dictionary.SWAP!
                @DS\push @DS\pop! / @DS\pop!
            "*/": ->
                @dictionary["/"]!
                @dictionary["*"]!
            "MOD": ->
                @dictionary.SWAP!
                @DS\push math.fmod @DS\pop!, @DS\pop!
            "NEGATE": -> @DS\push -1 * @DS\pop!

            "1+": ->
                @DS\push 1
                @dictionary["+"]!
            "1-": ->
                @DS\push 1
                @dictionary["-"]!

            ".": -> io.write " " .. @DS\pop!

            "ABS": -> @DS\push math.abs @DS\pop!
            "MAX": -> @DS\push math.max @DS\pop 2
            "MIN": -> @DS\push math.min @DS\pop 2

            "": -> @mode = "stop"
        }

    interpret_number: =>
        number = tonumber @word
        if number then
            @DS\push number
            true

mf = MoonForth [[ 4 1+ DUP * . ]]
mf\run!

In all, it was fun playing with Forth from Moonscript. I haven’t done anything to examine potential limitations with the Moonscript version. Some interesting possibilities might be to implement Forth words that interact with Löve or OpenResty. Really, with either miniforth implementation, it should be possible to have a Forth-like syntax usable anywhere Moonscript and Lua are supported.

Code for Miniforth can be downloaded from: https://github.com/losinggeneration/miniforth-moonscript