[# INCLUDE TH/speedbar.blogme] [SETFAVICON dednat4/dednat4-icon.png] [SETFAVICON IMAGES/forthsun.png] [# (defun c () (interactive) (find-blogme3-sh0-if "miniforth-article")) (defun u () (interactive) (find-blogme-upload-links "miniforth-article")) ;; http://anggtwu.net/miniforth-article.html ;; http://anggtwu.net/miniforth-article.html#why-forth ;; file:///home/edrx/TH/L/miniforth-article.html ;; #] [lua: -- (find-eleimfile "quail/sgml-input.el" "‘") def [[ SMALL 1 body "$body" ]] def [[ ` 1 body "‘$body’" ]] def [[ `` 1 body "“$body”" ]] -- (find-anggfile "TH/blogme3.blogme") def [[ SPANSTYLE 2 style,body "$body" ]] def [[ TTSTYLE 2 style,body "$body" ]] def [[ PRESTYLE 2 style,body "
$body
" ]] def [[ BORDERLESSTABLE 1 body "
\n".. body.."
\n" ]] def [[ PREBOXSTYLE 2 style,body BORDERLESSTABLE(PRESTYLE(style, body)) ]] -- Forth: #6495ed (find-ecolors "CornflowerBlue") -- Tcl: #ff6a6a (find-ecolors "IndianRed1") -- Blogme: #FFda99 -- (find-angg ".emacs" "ee-choosecolor") -- (find-ecolor-links (ee-choosecolor "#be7326")) -- (find-ecolor-links "CornFlowerBlue") -- (find-ecolor-links "#ccddff") -- (find-ecolors) blogmestyle = "background: #ffda99" prestyle = "padding: 4px; margin: 1ex" def [[ TTBLOGME 1 body TTSTYLE(blogmestyle, body) ]] def [[ PREBOX 1 body PREBOXSTYLE( prestyle, body) ]] def [[ PREBOXBLOGME 1 body PREBOXSTYLE(blogmestyle.."; "..prestyle, body) ]] def [[ ORANGEBG 1 body BG("#ffda99", body) ]] def [[ MIMG 1 semiurl IMG("http://anggtwu.net/"..semiurl, "alt") ]] def [[ MIMG 1 semiurl IMG(""..semiurl, "alt") ]] def [[ LISTING 1 semiurl R("$semiurl.html", "http://anggtwu.net/$semiurl") ]] ] [htmlize [J Bootstrapping a Forth in 40 lines of Lua code] [SMALL [NARROW [P Author: Eduardo Ochs [BR] eduardoochs@gmail.com [BR] [R http://anggtwu.net/] [BR] [R http://www.lua.org/gems/] [BR] [R http://www.lua.org/gems/selected.html] [BR] Version: 2008feb17 [BR] [BR] Listings: [BR] [LISTING miniforth/miniforth5.lua] [BR] [LISTING miniforth/miniforth5.out] [BR] Preprint version: [BR] [R http://anggtwu.net/miniforth/miniforth-article.pdf] [# file:///home/edrx/TH/L/miniforth-article.html #] ] [P [BF Abstract:] The core of a conventional Forth system is composed of two main programs: an [IT outer interpreter], that interprets textual scripts, and an [IT inner interpreter], that runs bytecodes; the outer interpreter switches between an [`` immediate mode], where words as executed as soon as they are read, and a [`` compile mode], where the words being read are assembled into bytecodes to define new words.] [P In Forth all variables are accessible from all parts of the system. Several important words use that to affect the parsing: they read parts of the input text themselves, process that somehow, and advance the input pointer - and with that they effectively implement other languages, with arbitrary syntax, on top of the basic language of the outer interpreter.] [P Due mostly to cultural reasons, Forths tend to be built starting from very low-level pieces: first the inner interpreter, in Assembly or C, then the basic libraries and the outer interpreter, in Forth bytecodes, or - rarely - in C. We take another approach. If we consider that Lua is more accessible to us than C or Assembly - and thus for us Lua is [`` more basic] - then it is more natural to start from the outer interpreter, and the dictionary only has to have the definition for one word, one that means [`` interpret everything that follows, up to a given delimiter, as Lua code, and execute that]. An outer interpreter like that fits in less than 40 lines of Lua code, and it can be used to bootstrap a whole Forth-like language.] ]] [WITHINDEX [# # «.forth-via-examples» (to "forth-via-examples") # «.program-1» (to "program-1") # «.program-2» (to "program-2") # «.figure-1» (to "figure-1") # «.figure-2» (to "figure-2") # «.figure-3» (to "figure-3") # «.figure-4» (to "figure-4") # «.figure-5» (to "figure-5") # «.bootstrapping» (to "bootstrapping") # «.program-3a» (to "program-3a") # «.program-3b» (to "program-3b") # «.modes» (to "modes") # «.program-4» (to "program-4") # «.figure-6» (to "figure-6") # «.figure-7» (to "figure-7") # «.virtual-modes» (to "virtual-modes") # «.figure-8» (to "figure-8") # «.figure-9» (to "figure-9") # «.polynomials» (to "polynomials") # «.figure-10» (to "figure-10") # «.figure-11» (to "figure-11") # «.propositional-calculus» (to "propositional-calculus") # «.figure-12a» (to "figure-12a") # «.figure-12b» (to "figure-12b") # «.figure-13» (to "figure-13") # «.metalua» (to "metalua") # «.figure-14» (to "figure-14") # «.figure-15» (to "figure-15") # «.why-forth» (to "why-forth") # «.thanks» (to "thanks") # «.related-work» (to "related-work") # «.bibliography» (to "bibliography") #] [RULE ----------------------------------------] [P The real point of this article is to propose a certain way of implementing a Forth virtual machine; let's call this new way [`` mode-based]. The main loop of a mode-based Forth is just this:] [PREBOXBLOGME [' while mode ~= "stop" do modes[mode]() end]] [P In our mode-based Forth, that is implemented in Lua, and that we will refer to as [`` miniforth], new modes can be added dynamically very easily. We will start with a virtual machine that [`` knows] only one mode - [`` interpret], that corresponds to (less than) half of the "outer interpreter" of traditional Forths - and with a dictionary that initially contains [# knows] just one word, that means [`` read the rest of the line and interpret that as Lua code]; that minimal virtual machine fits in 40 lines of Lua, and is enough to bootstrap the whole system.] [P But, [`` Why Forth?], the reader will ask - [`` Forth is old and weird, why shouldn't we stick to modern civilized languages, and ignore Forth? What do you still like in Forth?] - My feeling here is that Forth is one of the two quintessential extensible languages, the other one being Lisp. Lisp is very easy to extend and to modify, but only within certain limits: its syntax, given by [` read], is hard to change(1). If we want to implement a little language (as in [<]Bentley[>]) with a free-from syntax on top of Lisp, and we know Forth, we might wonder that maybe the right tool for that would have to have characteristics from both Lisp and Forth. And this is where Lua comes in - as a base language for building extensible languages.] [# -------------------------------------------------- #] [sec «forth-via-examples» (to ".forth-via-examples") H2 1. Forth via examples] [P [IT (Disclaimer: I'm using the term "Forth" in a loose sense through this article. I will say more about this in the last section.)]] [P Any [`` normal] Forth has an interactive interface where the user types a line, then hits the [`` return] key, and then the Forth executes that line, word by word, and displays some output; our miniforth does not have an interactive interface, but most ideas still carry on. Here's a very simple program; the normal text is the user input, and the parts with a darker background are the output from the Forth system. Note that [`` words] are sequences on non-whitespace characters, delimited by whitespace.] [_name «program-1» (to ".program-1") ] [PREBOX 5 DUP * . [ORANGEBG 25 ok] ( program 1 ) ] [P The program above can be [`` read aloud] as this: [`` Put 5 on the stack; run [` [TT DUP]], i.e., duplicate the element on the top of the stack; multiply the two elements on the top of the stack, replacing them by their product; print the element at the top of the stack and remove it from the stack.]] [P Here's a program that defines two new functions ([`` words], in the Forth jargon):] [_name «program-2» (to ".program-2") ] [PREBOX : SQUARE DUP * ; [ORANGEBG ok] : CUBE DUP SQUARE * ; [ORANGEBG ok] 5 CUBE . [ORANGEBG 125 ok] ( program 2 ) ] [P It can be read aloud as this: [BR]   Define some new words: [BR]   [`` [TT SQUARE]]: run [TT DUP], then multiply; [BR]   [`` [TT CUBE]]: run [TT DUP], then run [TT SQUARE], then multiply; [BR] Now put 5 on the stack, [TT CUBE] it, and print the result. ] [P The words [TT SQUARE] and [TT CUBE] are represented in the memory as some kind of bytecode; different Forths use different kinds of bytecodes. Here we are more interested in [`` indirect threaded] Forths (see [' [Ertl]]) that store the dictionary in a separate region of the memory. Some possible representations would be like in figures 1, 2, and 3; in these box diagrams all numbers are in hexadecimal, and we are assuming a big-endian machine for simplicity. Figure 4 shows the [`` bytecode] representation that we will use in miniforth. It is not exactly a bytecode, as the memory cells can hold arbitrary Lua objects, not just bytes - but we will call it a [`` bytecode] anyway, by abuse of language.] [_name «figure-1» (to ".figure-1") (find-anggfile "miniforth/bytecodediag_1.png") ] [P [MIMG miniforth/bytecodediag_1.png]] [_name «figure-2» (to ".figure-2") (find-anggfile "miniforth/bytecodediag_2.png") ] [P [MIMG miniforth/bytecodediag_2.png]] [_name «figure-3» (to ".figure-3") (find-anggfile "miniforth/bytecodediag_3.png") ] [P [MIMG miniforth/bytecodediag_3.png]] [_name «figure-4» (to ".figure-4") (find-anggfile "miniforth/bytecodediag_4.png") ] [P [MIMG miniforth/bytecodediag_4.png]] [P Here's a trace of what happens when we run [TT CUBE] (from Program 2 and Figure 4) in miniforth:] [_name «figure-5» (to ".figure-5") ] [PREBOXBLOGME [' RS={ 5 } mode=head DS={ 5 } head="DOCOL" RS={ 7 } mode=forth DS={ 5 } instr="DUP" RS={ 8 } mode=forth DS={ 5 5 } instr=1 RS={ 8 1 } mode=head DS={ 5 5 } head="DOCOL" RS={ 8 3 } mode=forth DS={ 5 5 } instr="DUP" RS={ 8 4 } mode=forth DS={ 5 5 5 } instr="*" RS={ 8 5 } mode=forth DS={ 5 25 } instr="EXIT" RS={ 9 } mode=forth DS={ 5 25 } instr="*" RS={ 10 } mode=forth DS={ 125 } instr="EXIT" Figure 5: a trace of CUBE (Program 2, Figure 4) ]] [P Note that we don't have a separate variable for the instruction pointer (IP); we use the top of the return stack (RS) as IP.] [P The rightmost part of our traces always describe what is going to be executed, while the rest describes the current state. So, in the sixth line we have RS = { 8, 4 }, and we are going to execute the instruction in [TT [' memory[4]]], i.e., [`` [TT *]], in mode "forth".] [# -------------------------------------------------- #] [sec «bootstrapping» (to ".bootstrapping") H2 2. Bootstrapping miniforth] [P Program 3a is all that we need to bootstrap miniforth. It defines the main loop ([`` [TT run]]), one mode ([`` [TT interpret]]), the dictionary ([`` [TT _F]]), and one word in the dictionary: [`` [TT %L]], meaning [`` evaluate the rest of the current line as Lua code].] [_name «program-3a» (to ".program-3a") ] [PREBOXBLOGME [' -- Global variables that hold the input: subj = "5 DUP * ." -- what we are interpreting (example) pos = 1 -- where are are (1 = "at the beginning") -- Low-level functions to read things from "pos" and advance "pos". -- Note: the "pat" argument in "parsebypattern" is a pattern with -- one "real" capture and then an empty capture. 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 -- A "word" is a sequence of one or more non-whitespace characters. -- The outer interpreter reads one word at a time and executes it. -- Note that `getwordornewline() or ""' returns a word, or a newline, or "". getword = function () parsespaces(); return parseword() end getwordornewline = function () parsespaces(); return parsewordornewline() end -- The dictionary. -- Entries whose values are functions are primitives. _F = {} _F["%L"] = function () eval(parserestofline()) end -- The "processor". It can be in any of several "modes". -- Its initial behavior is to run modes[mode]() - i.e., -- modes.interpret() - until `mode' becomes "stop". mode = "interpret" modes = {} run = function () while mode ~= "stop" do modes[mode]() end end -- Initially the processor knows only this mode, "interpret"... -- Note that "word" is a global variable. 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 -- ( Program 3a: the core of miniforth ) ]] [P Program 3b is a first program in miniforth. It starts with only [`` [TT %L]] defined and it defines several new words: what to do on end-of-line, on end-of-text, and [`` [TT [<]L]], that evaluates blocks of Lua code that may span more than one line; then it creates a data stack and defines the words [`` [TT DUP]], [`` [TT *]], [`` [TT 5]], and [`` [TT .]], that operate on it.] [_name «program-3b» (to ".program-3b") ] [PREBOXBLOGME [' -- Our first program in MiniForth. -- It defines a meaning for newlines (they are no-ops; go ahead), -- for "" ("at end-of-text, change the mode to 'stop'"), -- and for "[L" - read everything until a "L]", and interpret -- what is between the "[L" and the "L] as Lua code, with eval. -- Then it creates a data stack ("DS") and four words - "5", "DUP", -- "*", "." - that operate on it. -- 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 end _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] ]=] -- Now run it. There's no visible output. pos = 1 mode = "interpret" run() -- At this point the dictionary (_F) has eight words. -- ( Program 3b: a first program in miniforth ) ]] [P After running Program 3b the system is already powerful enough to run simple Forth programs like, for example,] [PREBOXBLOGME 5 DUP * .] [P Note that to [`` run] that what we need to do is:] [PREBOXBLOGME subj = "5 DUP * ."; pos = 1; mode = "interpret"; run()] [P It is as if we were setting the memory (here the [`` [TT subj]]) and the registers of a primitive machine by hand, and then pressing its [`` run] button; clearly, that could be made better, but here we have other priorities.] [P The Programs 3a and 3b don't have support for non-primitives; this will have to be added later. Look at Figure 4; non-primitives, like [`` [TT SQUARE]], are represented in the bytecode as numbers - addresses of heads in the [TT [' memory[]]] - and we have not introduced neither the [TT memory] yet, nor the states [`` [TT head]] or [`` [TT forth]].] [P Note that the names of non-primitives do not appear in the [TT memory], only in the dictionary, [TT _F]. For convenience in such memory diagrams we will draw the names of non-primitives below their corresponding heads; in Figure 4 [TT [' _F["SQUARE"] = 1]] and [TT [' _F["CUBE"] = 5]].] [#  2008feb11: omitted the paragraph below  #] [# P [IT (Explain that we will not discuss the "textual representations" of bytecode here - like ": CUBE DUP SQUARE * ;" -, for reasons of space and clarity. Also, we will generally omit the definitions of functions and words from here on, as they can be reconstructed from the traces.)]] [# -------------------------------------------------- #] [sec «modes» (to ".modes") H2 3. Modes] [P When the inner interpret runs - i.e., when the mode is "head" or "forth"; see Figure 5 -, at each step the processor reads the contents of the memory at IP and processes it. When the outer interpreter runs, at each step it reads a word from [TT subj] starting at [TT pos], and processes it. There's a parallel between these behaviors...] [P I have never seen any references to "modes" in the literature about Forth. In the usual descriptions of inner interpreters for Forth the "head" mode is not something separate; it is just a transitory state that is part of the semantics of executing a Forth word. And the "interpret" and "compile" modes also do not exist - the outer interpreter is implemented as a Forth word containing a loop; it reads one word at a time, and depending on the value of a variable, [TT STATE], it either "interprets" or "compiles" that word. So, in a sense, "interpret" and "compile" are "virtual modes"...] [P Let me explain how I arrived at this idea of "modes" - and what I was trying to do that led me there.] [P Some words interfere in the variables of the outer interpreter. For example, ":" reads the word the [TT pos] is pointing at - for example, "SQUARE" -, adds a definition for that word ("SQUARE") to the dictionary, and advances [TT pos]; when the control returns to [TT modes.interpret()] the variable [TT pos] is pointing to the position after [TT SQUARE] - and [TT modes.interpret()] never tries to process the word [TT SQUARE]. Obviously, this can be used to implement new languages, with arbitrary syntax, on top of Forth.] [P Some words interfere on the variables of the inner interpreter - they modify the return stack. Let's use a more colorful terminology: we will speak of words that [`` eat text] and of words that [`` eat bytecode]. As we have seen, [`` [TT :]] is a word that eats text; numerical literals are implemented in Forth code using a word, [TT LIT], that eats bytecode. In the program below,] [_name «program-4» (to ".program-4") ] [PREBOX : DOZENS 12 * ; [ORANGEBG ok] 5 DOZENS . [ORANGEBG 60 ok] ( Program 4 ) ] [P the word [TT DOZENS] is represented in bytecode in miniforth as:] [_name «figure-6» (to ".figure-6") ] [PREBOXBLOGME memory = {"DOCOL", "LIT", 12, "*", "EXIT"} -- 1 2 3 4 5 -- DOZENS Figure 6: the bytecode for DOZENS (Program 4) ] [P When the [TT LIT] in [TT DOZENS] executes it reads the 12 that comes after it, and places it on the data stack; then it changes the return stack so that in the next step of the main loop the IP will be 4, not 3. Here is a trace of its execution; note that there is a new mode, "lit". The effect of "executing" the 12 in [TT [' memory[3]]] in mode "lit" is to put the 12 in DS.] [_name «figure-7» (to ".figure-7") ] [PREBOXBLOGME RS={ 1 } mode=head DS={ 5 } head="DOCOL" RS={ 2 } mode=forth DS={ 5 } instr="LIT" RS={ 3 } mode=lit DS={ 5 } data=12 RS={ 4 } mode=forth DS={ 5 12 } instr="*" RS={ 5 } mode=forth DS={ 60 } instr="EXIT" Figure 7: the trace for 5 DOZENS (Program 4, Figure 6) ] [P The code in Lua for the primitive [TT LIT] and for the mode [TT lit] can be synthesized from the trace. By analyzing what happens between steps 2 and 3 and 3 and 4, we see that [TT LIT] and [TT lit] must be:] [BE' _F["LIT"] = function () mode = "lit" end modes.lit = function () push(DS, memory[RS[RS.n]]) RS[RS.n] = RS[RS.n] + 1 mode = "forth" end ] [P so from this point on we will consider that the traces give enough information, and we will not show the corresponding code.] [P Note that different modes read what they will execute from different places: [TT head], [TT forth] and [TT lit] read from [TT [' memory[RS[RS.n]]]] (they eat bytecode); [TT interpret] and [TT compile] read from [TT subj], starting at [TT pos] (they eat text). Our focus here will be on modes and words that eat bytecode.] [#  ???  ] [# P [IT (I will not give more examples of words that eat text here. External examples: [R http://anggtwu.net/blogme3.html blogme3] and [R http://anggtwu.net/dednat4.html dednat4].)]] [# -------------------------------------------------- #] [sec «virtual-modes» (to ".virtual-modes") H2 4. Virtual Modes] [P How can we create words that eat bytecode, like [TT LIT], in Forth? In the program in Figure 8 the word [TT TESTLITS] call first [TT LIT], then [TT VLIT]; [TT VLIT] should behave similarly to [TT LIT], but [TT LIT] is a primitive and [TT VLIT] is not.] [_name «figure-8» (to ".figure-8") ] [PREBOXBLOGME [' memory = {"DOCOL", "R>P", "PCELL", "P>R", "EXIT", -- 1 2 3 4 5 -- VLIT <---------------\ -- | "DOCOL", "LIT", 123, 1, 234, "EXIT",} -- 6 7 8 9 10 11 -- TESTLITS Figure 8: a word (TESTLITS) that uses both LIT and VLIT ]] [_name «figure-9» (to ".figure-9") ] [PREBOXBLOGME [' t=0 RS={ 6 } mode=head PS={ } DS={ } head="DOCOL" t=1 RS={ 7 } mode=forth PS={ } DS={ } instr="LIT" t=2 RS={ 8 } mode=lit PS={ } DS={ } data=123 t=3 RS={ 9 } mode=forth PS={ } DS={ 123 } instr=1 t=4 RS={ 10 1 } mode=head PS={ } DS={ 123 } head="DOCOL" t=5 RS={ 10 2 } mode=forth PS={ } DS={ 123 } instr="R>P" t=6 RS={ 3 } mode=forth PS={ 10 } DS={ 123 } instr="PCELL" t=7 RS={ 4 } mode=pcell PS={ 10 } DS={ 123 } pdata=234 t=8 RS={ 4 } mode=forth PS={ 11 } DS={ 123 234 } instr="P>R" t=9 RS={ 11 5 } mode=forth PS={ } DS={ 123 234 } instr="EXIT" t=10 RS={ 11 } mode=forth PS={ } DS={ 123 234 } instr="EXIT" Figure 9: a trace of TESTLITS (Figure 8) ]] [P Figures 8 and 9 contain a full solution, so start by ignoring the cells 2, 3, and 4 of the memory, and the lines t=5 to t=8 of the trace. From t=5 to t=9 what we need to do is] [PREBOXBLOGME [' push(DS, memory[RS[RS.n - 1]]) RS[RS.n - 1] = RS[RS.n - 1] + 1 ]] [P where the -1 is a magic number: roughly, the number of [`` call frames] in the stack between the call to [TT VLIT] and the code that will read its literal data, negated. In other situations this could be -2, -3... One way to get rid of that magic number is to create a new stack - the [`` parsing stack] ([`` [TT PS]]) - and to have [`` parsing words] that parse bytecode from the position that the top of [TT PS] points to; then a word like [TT VLIT] becomes a variation of a word, [TT PCELL], that reads a cell from [TT [' memory[PS[PS.n]]]] and advances [TT [' PS[PS.n]]]. The code for [TT VLIT] in Figure 8 shows how that is done - we wrap [TT PCELL] as [`` [TT [' R>P PCELL P>R]]] - and from the trace in Figure 9 we can infer how to define these words.] [# (find-pilw3m "8.5.html") # (find-luamanualw3m "#pdf-error") #] [P Note that the transition from t=2 to t=3 corresponds to the transition from t=4 to t=10; the mode being [TT "lit"] corresponds to having the address of the head of [TT VLIT] at the top of [TT RS], and the mode being [TT "head"]; using this idea we can implement virtual modes in Forth. Better yet: it all becomes a bit simpler if we regard the mode as being an invisible element that is always above the top of [TT RS]. So, an imaginary mode [TT "vlit"] would be translated, or expanded, into a 1 (the head of [TT VLIT]), plus a mode [TT "head"]; or another word, similar to [TT VLIT], would just switch the mode to [TT "vlit"], and the action of that word would be to expand it into the head of [TT VLIT], plus the mode [TT "head"].] [# -------------------------------------------------- #] [sec «polynomials» (to ".polynomials") H2 5. A Bytecode for Polynomials] [P A polynomial with fixed numerical coefficients can be represented in memory as first the number of these coefficients, then the value of each of them; for example, [IT P](x) = 2x^3 + 3x^2 + 4x + 5.5 is represented as { ..., 4, 2, 3, 4, 5.5, ... }. We will call this representation - number of coefficients, then coefficients - the [`` data of the polynomial]. Let's start with a primitive, [TT PPOLY], that works like [TT PCELL], in the sense that it reads the data of the polynomial from the memory, starting at the position [TT [' PS[PS.n]]], and advancing [TT [' PS[PS.n]]] at each step. This [TT PPOLY] takes a value from the top of the data stack - it will be 10 in our examples - and replaces it by the result of applying [IT P] on it - [IT P](10), which is 2345.5.] [P By defining [TT POLY] from [TT PPOLY], as we defined [TT VLIT] from [TT PCELL] in Figure 8,] [PREBOX : POLY R>P PPOLY P>R ;] [P we get a word that eats bytecode; a call to [TT POLY] should be followed by data of a polynomial, just like [TT LIT] is followed by a number. And we can also do something else: we can create new heads, [TT DOPOLY] and [TT DOADDR], and represent polynomials as two heads followed by the data of the polynomial. The program in Figure 10, that tests this idea, has the trace in Figure 11.] [_name «figure-10» (to ".figure-10") ] [PREBOXBLOGME [' memory = {"DOPOLY", "DOADDR", 4, 2, 3, 4, 5.5, -- 1 2 3 4 5 6 7 -- P(X) &P(X) -- ^---------------------\ -- | "DOCOL", "LIT", 10, 1, "EXIT"} -- 8 9 10 11 12 -- TESTDOPOLY ( Figure 10: put 10 on the stack, call P(X) ) ]] [_name «figure-11» (to ".figure-11") ] [PREBOXBLOGME [' RS={ 8 } mode=head PS={ } DS={ } head="DOCOL" RS={ 9 } mode=forth PS={ } DS={ } instr="LIT" RS={ 10 } mode=lit PS={ } DS={ } data=10 RS={ 11 } mode=forth PS={ } DS={ 10 } instr=1 RS={ 12 1 } mode=head PS={ } DS={ 10 } head="DOPOLY" RS={ 12 forth } mode=ppolyn PS={ 3 } DS={ 10 } n=4 RS={ 12 forth } mode=ppolyc PS={ 4 } DS={ 10 } n=4 acc=0 coef=2 RS={ 12 forth } mode=ppolyc PS={ 5 } DS={ 10 } n=3 acc=2 coef=3 RS={ 12 forth } mode=ppolyc PS={ 6 } DS={ 10 } n=2 acc=23 coef=4 RS={ 12 forth } mode=ppolyc PS={ 7 } DS={ 10 } n=1 acc=234 coef=5.5 RS={ 12 forth } mode=ppolye PS={ 8 } DS={ 10 } acc=2345.5 RS={ 12 } mode=forth PS={ 8 } DS={ 2345.5 } instr="EXIT" (Figure 11: a trace for the program in Figure 10) ]] [P The trace above does not show what [TT &P(X)] does; the effect of running [TT &P(X)] is to put the address of the beginning of data of the polynomial, namely, 3, into the data stack. Note how a polynomial - that in most other languages would be a piece of passive data - in Forth is represented as two programs, [TT P(X)] and [TT &P(X)], that share their data. Compare that with the situation of closures in Lua - two closures created by the same mother function, and referring to variables that were local to that mother function, share upvalues.] [# -------------------------------------------------- #] [sec «propositional-calculus» (to ".propositional-calculus") H2 6. A Bytecode Language for Propositional Calculus] [P Here is another example. Let's write [`` [TT [Q =>]]] for [`` implies], and [`` [TT [Q &]]] for [`` and]. Then this,] [_name «figure-12a» (to ".figure-12a") ] [PREBOXBLOGME [' (Q=>R)=>((P&Q)=>(P&R)) ( Figure 12a: a proposition. ) ]] [P is a [`` formula], or a [`` proposition], in Propositional Calculus; incidentally, it is a tautology, i.e., always true.] [P In some situations, for example, if we want to find a proof for that proposition, or if we want to evaluate its truth value for some assignment of truth values to P, Q, and R, we need to refer to subformulas of that formula. If we represent it in bytecode using Polish Notation (not Reverse Polish Notation! Can you see why?) then this becomes trivial:] [_name «figure-12b» (to ".figure-12b") ] [PREBOXBLOGME [Q [' memory = { "=>", "=>", "Q", "R", "=>", "&", "P", "Q", "&", "P", "R" } -- 1 2 3 4 5 6 7 8 9 10 11 ( Figure 12b: the proposition in Figure 11 in Polish Notation. ) ]]] [P Subformulas can now be referred to by numbers - the position in the memory where they start. We can write a word to parse a proposition starting at some position in the memory; if that position contains a binary connective like [`` [TT [Q =>]]] or [`` [TT [Q &]]], then that word calls itself two times to parse the subformulas at the "left" and at the "right" of the connective. If the word memoizes the resulting structure by storing it in a table [TT formulas], then re-parsing the formula that starts at the position, say, 6, becomes very quick: the result is [TT [' formulas[6]]], and the pointer should be advanced to [TT [' formulas[6].next]]. Figure 13 shows the contents of that table after parsing the formula that starts at [TT [' memory[1]]].] [_name «figure-13» (to ".figure-13") ] [PREBOXBLOGME [' 1: { addr=1, cc="=>", l=2, r=5, next=12, name="((Q=>R)=>((P&Q)=>(P&R)))" } 2: { addr=2, cc="=>", l=3, r=4, next=5, name="(Q=>R)" } 3: { addr=3, next=4, name="Q" } 4: { addr=4, next=5, name="R" } 5: { addr=5, cc="=>", l=6, r=9, next=12, name="((P&Q)=>(P&R))" } 6: { addr=6, cc="&", l=7, r=8, next=9, name="(P&Q)" } 7: { addr=7, next=8, name="P" } 8: { addr=8, next=9, name="Q" } 9: { addr=9, cc="&", l=10, r=11, next=12, name="(P&R)" } 10: { addr=10, next=11, name="P" } 11: { addr=11, next=12, name="R" } ( Figure 13: the table "formulas" (for Figure 12b). ) ]] [# H2 A Preprocessor for TeX] [# -------------------------------------------------- #] [sec «metalua» (to ".metalua") H2 7. (Meta)Lua on Miniforth] [P The parser for the language for Propositional Calculus in the last section had to be recursive, but it didn't need backtracking to work. Here is a language that is evidently useful - even if at this context it looks like an academic exercise - and whose parser needs a bit of backtracking, or at least lookahead. Consider the following program in Lua:] [_name «figure-14» (to ".figure-14") ] [PREBOXBLOGME [' foo = function () local storage return function () return storage end, function (x) storage = x end end -- ( Figure 14 ) ]] [P It can be represented in bytecode in miniforth as:] [_name «figure-15» (to ".figure-13") ] [PREBOXBLOGME [Q [' memory = { "foo", "=", "function", "(", ")", "local", "storage", "return", "function", "(", ")", "return", "storage", "end", ",", "function", "(", "x", ")", "storage", "=", "x", "end", "end", "" } -- ( Figure 15 ) ]]] [P One way of [`` executing] this bytecode made of string tokens could be to produce in another region of the memory a representation in Lua of the bytecode language that the Lua VM executes; another would be to convert that to another sequence of string tokens - like what MetaLua ([' [Fleutot]]) does. Anyway, there's nothing special with our choice of Lua here - Lua just happens to be a simple language that we can suppose that the reader knows well, but it could have been any language. And as these parsers and transformers would be written in Lua, they would be easy to modify.] [# -------------------------------------------------- #] [sec «why-forth» (to ".why-forth") H2 8. Why Forth?] [#  2008feb11  P [IT (I am using the term "Forth" here in my own atypical sense... but two of my main interests with Forth were (1) understanding the underlying machine, (2) creating little languages - and my experiences using Forths that tried to follow the ANS Standard were very frustrating. This section is important because it gives context for everything that is happening in the rest of the paper, but it tells a story from a non-standard point of view, etc etc. I need to map its ideas, and maybe rewrite the section somehow to make it more "honest", and a bit clearer. Also, it's too big!...)]] [# P (Maybe the paragraph below?)] [P [IT Caveat lector:] there is no single definition for what is [`` Forth]... around 1994 the community had a big split, with some people working to create an ANSI Standard for Forth, and the creator of the language and some other people going in another direction, and not only creating new Forths that went against ideas of the Standard, but also stating that ANS Forth [`` was not Forth]. I can only write this section clearly and make it brief if I choose a [IT very] biased terminology; and also, I'm not going to be historically precise, either - I will simplify and distort the story a bit to get my points across. You have been warned!] [br] [P Forth was very popular in certain circles at a time when computers were much less powerful than those of today. Some of the reasons for that popularity were easy to quantify: compactness of programs, speed, proximity to machine code, simplicity of the core of the language - i.e., of the inner and the outer interpreters. None of these things matter so much anymore: computers got bigger and faster, their assembly languages became much more complex, and we've learned to take for granted several concepts and facilities - [TT malloc] and [TT free], high-level data structures, BNF - and now we feel that it is "simpler" to send characters through stdout than poking bytes at the video memory. Our notion of simplicity has changed.] [P Int the mid-90s came the ANS-Forth Standard, and with it a way to write Forth source that would run without changes in Forths with different memory models, on different CPU architectures. At about the same time the creator of the language, Chuck Moore, started to distance himself from the rest of the community, to work on Forths that were more and more minimalistic, and on specialized processors that ran Forth natively.] [P My experience with (non-Chuck-Moore-) Forth systems written before and after the ANS Standard was that in the pre-ANS ones the format of the bytecode was stated clearly, and users were expected to understand it; in Forths written after the Standard the bytecode was not something so mundane anymore - it became a technical detail, hidden under abstractions.] [P Old Forths were fun to use. When I was a teenager I spent hundreds of evenings playing with Forths on an IBM-PC - first FIG-Forth and MVP-Forth, then HS-Forth, a commercial Forth whose memory model (8086 machine code, dictionary and Forth definitions in different memory segments, indirect-threaded, no primitives, multiple heads) inspired some of the ideas in this paper. At one point I spent some weeks writing a program that constructed a "shadow image" of the Forth segment, with a letter or a number for each byte in a head, a "." for each byte in a Forth instruction, "_"s and "$"s for bytes in literal numbers and strings, "[Q <]"s and "[Q >]"s for the bytes that were addresses in backward or forward jumps (i.e., the two bytes following each call to [TT BRANCH] or [TT 0BRANCH]) - and spaces for the unknown bytes, as I didn't have the source for the whole core system, and some words were tricky to decompile... Then I printed the result, in five pages, each with a grid of 64x64 characters, and addresses at the borders; that gave me a map of all the bytes in words in the core system that were not defined in assembly language.] [P I've met many people over the years who have been Forth enthusiasts in the past, and we often end up discussing what made Forth so thrilling to use at that time - and what we can do to adapt its ideas to the computers of today. My personal impression is that Forth's main points were not the ones that I listed at the beginning of this section, and that I said that were easy to quantify; rather, what was most important was that nothing was hidden, there were no complex data structures around with [`` don't-look-at-this] parts (think on garbage collection in Lua, for example, and Lua's tables - beginners need to be convinced to see these things abstractly, as the concrete details of the implementation are hard), and [IT everything] - code, data, dictionaries, stacks - were just linear sequences of bytes, that could be read and modified directly if we wished to. We had total freedom, defining new words was quick, and experiments were quick to make; that gave us a sense of power that was totally different from, say, the one that a Python user feels today because he has huge libraries at his fingertips.] [P A Forth-like language built on top of Lua should be easier to integrate with the rest of the system than a "real" Forth written in C. Also, it's much easier to add new syntaxes and bytecode languages to a mode-based Forth than to a conventional one. And we are not forced to store only numbers in the memory; we can store also strings - I've used strings for primitives and heads here because this makes programs more readable -, or any other Lua objects, if we need to.] [P I do not intend to claim that miniforth is compact - in terms of memory usage -, or efficient, or useful for practical applications. But the natural ways for doing things in Forth were different from the ways that are natural in today's systems; and I believe that miniforth can be used to give to people glimpses into interesting ways of thinking that have practically disappeared, and that have become hard to communicate.] [#  2008feb11  P [IT (Mention, maybe: free-form syntax / linearized data structures (because the memory is linear) / some structures are hard to traverse: example, Forth words (which bytes are immediate data?) / traversing data structures in Forth was akin to executing programs (in little languages) / compare with the structures in C: structs and unions / a way of thinking that was close to how the machine really worked. ]] [#  2008feb11  P [IT (The paragraph above doesn't not make clear that the ease of access to Lua should make it easy to test ideas - i.e., "implement little languages" - on miniforth...)]] [sec «thanks» (to ".thanks") H3 Thanks] [P To Marc Simpson and Yuri Takhteyev for helpful discussions. [# IT (Details? Thanks the editors for their patience.)]] [sec «related-work» (to ".related-work") H3 Related work] [P After a draft of this article had been written Marc Simpson engaged in a long series of discussions with me about Forths, Lisp, SmallTalk, several approaches to minimality, etc, and at one point, over the course of one hectic weekend in december, 2007, he implemented a [IT usable] (rather than just experimental) dialect of Forth - based mainly on Frank Sergeant's Pygmy Forth and Chuck Moore's cmForth, and borrowing some ideas from this article - on top of Ruby ([`` RubyForth]), and later ported his system to Python and C. A port of it to Lua is underway.] [# ] [sec «bibliography» (to ".bibliography") H3 Bibliography] [P Jon Bentley: [IT More Programming Pearls], Addison-Wesley, 1990 (chapter 9: [IT Little Languages]).] [P James T. Callahan: HS-Forth (program and manual). Harvard Softworks, 1986-1993.] [P Anton Ertl: [IT Threaded Code]. Retrieved from: [R http://www.complang.tuwien.ac.at/forth/threaded-code.html].] [P Brad Rodriguez: [IT A BNF Parser in Forth]. From: [R http://www.zetetics.com/bj/papers/bnfparse.htm].] [P Fabien Fleutot: [IT MetaLua]. At: [R http://metalua.luaforge.net/].] [P Kein-Hong Man: [R http://luaforge.net/docman/view.php/83/98/ANoFrillsIntroToLua51VMInstructions.pdf A No-Frills Introduction to Lua 5.1 VM Instructions].] ] ] [# # (eev "cd ~/miniforth/; Scp bytecodediag_{3,4}.png edrx@anggtwu.net:slow_html/miniforth/") (find-sh "cd; for i in miniforth/bytecodediag_{1,2,3,4}.png; do cp -v $i ~/TH/L/$i; done") http://anggtwu.net/miniforth/bytecodediag_1.png http://anggtwu.net/miniforth/bytecodediag_2.png http://anggtwu.net/miniforth/bytecodediag_3.png Here are the definitions: Square: run dup, then multiply; Cube: run dup, then run square, then multiply; Now put 5 on the stack, cube it, and print the result. (1) I would like to complain also that the internal representation of objects in most Lisps is fixed: it's always based on atoms and conses. But that's not always true Nowadays everyone knows how Lisp can be extended by using, say, macros, but few people seem to be annoyed by the fact that the syntax of Lisp, given by "read", is fixed and hard to change, and that the internal representation of objects in Lisp is always based on lists (and conses), and this is hard to change too. Lisp is extensible ] [# # Local Variables: # coding: raw-text-unix # modes: (fundamental-mode blogme-mode) # End: #]