This chapter is a culmination of many macro techniques we have looked at so far in this book. Using macro abstractions we have developed, we create an implementation of one of my favourite programming languages: forth. Although this implementation embodies most of the important ideas of forth, it is very different and lispy. Though there are certain interesting uses for the code in this chapter, its primary purpose is to teach the concepts and fundamentals of forth meta-programming to a lisp audience and to be a platform for discussing the central theme of this book—creating and using duality of syntax with macros.
Forth, more so than every language except lisp, has a rich, fascinating history and I'm grateful for having discovered it. For that reason, and for everything else, this chapter is dedicated with love to my father Brian Hoyte who introduced me to forth and to computer programming. This chapter was partially inspired by [THREADING-LISP] and by the research of Henry Baker[LINEAR-LISP][LINEAR-LISP-AND-FORTH].
Forth was the first programming language that was created and developed without strong government, academic, or corporate sponsors—or at least the first such language to succeed. Instead of being motivated by the needs of a large organisation, forth was independently invented by Chuck Moore around 1968 to solve his own computing needs in astronomy, hardware design, and more. Since then, forth has been distributed, implemented, and improved upon by a passionate grass-roots user community[EVOLUTION-FORTH-HOPL2]. Contrast forth with the MIT (and later DARPA) patronage of early lisps and COMMON LISP, IBM's FORTRAN, and AT&T's unix language C.
Because of these roots, and because of a generally different philosophy of the role of computer software and hardware, forth is different. Even more so than lisp, forth looks weird. But like lisp, forth looks weird for a reason: it was designed with more in mind than style. Forth is weird by design, and this design relates to macros.
Today, forth is most commonly seen in so-called embedded platforms—computers that are severely resource constrained. It is a testament to the design of forth that the language can be entirely implemented on almost every programmable computer system ever created. Forth is designed to be as easy as possible to implement and experiment with. In fact, creating a forth clone is so profoundly trivial that inventing a forth-style stack based language or two is almost a rite-of-passage for programmers interested in the design of programming languages. Some stack based languages that can trace roots back to forth and have made interesting contributions are PostScript and Joy.
Often important forth implementation decisions are based on the exact resources of the computer that forth is being implemented on. Forth programmers have devised a set of abstract registers that need to be either mapped into real registers, mapped into memory locations, or possibly implemented in a different way altogether. But what do we do if we are implementing a forth on lisp, an environment with unlimited potential and few restrictions? Rather than simply impose an arbitrary mapping of forth abstract registers into lisp code, we try to take a step back. What would forth look like if Chuck had a lisp machine? Rather than fitting forth to the capabilities of an arbitrary machine, real or virtual, we explore a minimal set of forth abstract registers, optimised for simplicity and capability when implemented on lisp.
But really, searching for an optimal set of abstract concepts is what Chuck did while he created forth, using his experience of dozens of different forth implementations on as many architectures. This is why forth is so great. Like lisp, forth represents a high local maximum in the space of language design, and also like lisp, forth is not so much a programming language or a set of standards, but instead a building material and collection of wisdom regarding what works and what doesn't.
The forth-registers variable is a list of symbols that represent abstract registers for our forth machine. Of course lisp doesn't think in terms of registers and fixnums, but instead variables and symbols. It may seem strange to start our development of a forth environment here, with just a list of variable names, but this is in fact always the first step in implementing a forth system. Creating a forth is an ingenious process of bootstrapping exceeded in beauty and cleverness only by lisp. A modest description of this process follows.
One of the characteristic features of forth is its direct access to the stack data structures used by your program both to pass parameters to subroutines and to keep track of your execution path throughout these subroutines. Forth is especially interesting because—unlike most programming languages—it separates these two uses of the stack data structure into two stacks you can fool with1. In a typical C implementation, the parameters of a function call and its so-called return address are stored in a single, variable-sized stack frame for every function invocation. In forth, they are two different stacks called the parameter stack and the return stack, which are represented as our abstract registers pstack and rstack. We use the COMMON LISP push and pop macros, meaning these stacks are implemented with cons cell linked lists instead of the array data structures used in most forths.
The abstract register pc is an abbreviation for program counter, a pointer to the code we are currently executing. What forth code is and how we can point to it will be explained shortly, as will our abstract registers compiling and dtable.
Another building block of forth is its concept of a dictionary. The forth dictionary is a singly linked list of forth words, which are similar to lisp functions2. Words are represented with a lisp structure. Structures are efficient slot-based data structures usually implemented as vectors. The name slot is for a symbol used to lookup the word in the dictionary. Notice that the forth dictionary is not stored alphabetically, but instead chronologically. When we add new words we append them onto the end of the dictionary so that when we traverse the dictionary the latest defined words are examined first. The last element of our dictionary is always stored in the abstract register dict. To traverse the dictionary, we start with dict and follow the prev pointer of the word structures, which either point to the previously defined word or to nil if we are at the last word3.
Given w, a word to lookup, and last, a dictionary to search, forth-lookup will return either a forth word structure or nil depending on whether the word w was found in the dictionary or not. The comparison function eql is used instead of eq because—unlike lisp—forth allows words to be named by numbers and other non-symbols.
The immediate slot of our forth word is a flag indicating whether the word is immediate or not. Immediacy is a forth meta-programming concept we will explore in depth shortly. For now here is a rough analogy to its lisp counterpart: immediate words are like lisp macros in that they are forth functions to be executed at compile time instead of run-time. What? Only lisp is supposed to have macros. While it is true that the COMMON LISP macro system is much more powerful than any other macro system—including the best forth implementations—forth has extension capabilities that surpass almost all other languages. Like lisp, this capability is the result of a design philosophy: if it's good enough for the language implementor, it's good enough for the application programmer. Like lisp, forth doesn't really recognise the notion of a primitive. Instead, it provides a set of meta-primitives that can be combined to build the language that you, the programmer, desire. Like lisp, and unlike most Blub languages, extending the language in novel ways through the use of macros is not only possible, but encouraged. Like lisp, forth is not about style, but instead, power.
In the previous section, we focused on abstract registers. These registers are an important focal point, and that is why forth philosophy considers them so fundamental, but these registers are actually just a component of a more general concept: abstract machines. Probably the most distinguishing property of different forth systems are their implementations of threaded code. What forth means by threaded code is very different from the conventional meaning of preemptive scheduled, shared-memory processes4. Forth threads have nothing to do with concurrency. They are a framework for talking about code compilation and meta-programming.
While lisp gives access to the tree data structure5 of symbols that your program is compiled from and to before being assembled into memory, forth provides no symbolic manipulation. Instead, forth gives access to this process of assembling—threading—the code into memory. Although to outsiders the most apparent features of forth are its stacks and postfix notation, it is actually threads that make forth what it is. Forth is about stacks in the same way that lisp is about lists. They just happen to be the most applicable data structures to use for solving meta-programming problems—what forth and lisp are both really about.
The classic style of threading is known as indirect threaded code but most modern forths are implemented with direct threaded code. The difference involves a level of indirection. The low-level efficiency implications of this indirection depend on the underlying processor and we will not get into details here. There are many good tutorials on forth threading[STARTING-FORTH][MOVING-FORTH]. In memory, these styles of threading both consist of adjacent cells, which are fixnum machine words representing pointers. A small piece of tight machine code called the inner interpreter is usually tailored for the processor being used because of its important job: to follow the pointers of these forth threads, interpreting their meanings as it goes along. The default behaviour when encountering a cell is to push the current program counter location onto the return stack and then point the program counter to whatever is contained in the cell. When the inner interpreter reaches the end of a thread, it pops the return stack and resumes execution at this location—where it left off6.
As you can imagine, this type of program storage makes for extremely small programs. A compiled forth word is just a consecutive array of fixnums, most of which represent pointers to other words. This has always been one of the advantages of forth. Because of the transparency in the threading of the program into memory, forth allows fine control over many programming trade-offs, including one of the most important: Execution speed versus program size. Threaded code lets us optimise our abstractions as close to our problems as possible, resulting in extremely fast, small programs. But just as lisp macros are about much more than just efficiency, so are forth threads. As much as lisp programmers, forth programmers tend to think of themselves as implementors instead of mere users. Forth and lisp are both about control—making your own rules.
There are at least two other common types of forth threading techniques: token threaded code and subroutine threaded code. These represent opposite directions to take when considering the speed versus size trade-off. Sometimes these threading techniques coexist with indirect and direct threaded code in the same forth. Token threading involves adding another level of indirection by using fixnums even smaller than pointers to represent words in the thread. At the other end of the spectrum is subroutine threading. This type of threaded code is becoming popular and the best modern forth compilers partially use subroutine threading. Instead of consecutive pointers to words for the inner interpreter to follow, subroutine threaded code stores inline machine instructions to call these pointers. In subroutine threaded code, the inner interpreter disappears—it is actually implemented by the hardware (or virtual machine). Subroutine threaded code is usually considered an opaque block, one that only a special, non-programmable compiler can manipulate. Especially when various optimisations are made to the code, these opaque blocks start to look nothing like uniform, cell-based threads. Almost all non-forth compilers compile only to subroutine threaded code and don't imagine that you would ever want to do anything else, leading to this peculiar definition:
A Flub is a language that only considers subroutine threaded code or a language implementation that only provides subroutine threaded code.
For example, C is a Flub because it only provides programmers means to create functions—opaque blocks of subroutine threaded code. Certainly we can implement an inner interpreter in C to handle indirect threaded code7 and bootstrap a stack-based language with this program, but then we are no longer programming in C. Almost all Blub languages are Flubs. Forth as an abstract machine is, as we've just described, not a Flub. As we will see, forth gives programmers/implementors lots of control over how their programs are compiled.
Is lisp a Flub? Interestingly, lisp was probably the first non-Flub programming language but has mostly turned into Flub. Although not strictly required to by the standard, most COMMON LISP compilers only compile functions to blocks of opaque machine code and, as such, are Flubs. But in very early versions of lisp, functions were stored as lists—a strange sort of code threading not entirely unlike forth threads. While this did allow some very clever run-time tricks, including giving meaning to cyclic code, it was hopelessly inefficient. Unlike forth's many types of threading—which have been efficiently implemented on almost all architectures—this internal representation for lisp functions was intolerable and lisp was changed to allow (extremely) efficient code. The consequence, for meta-programmers, is that most implementations of COMMON LISP are Flubs.
But there is a difference between features that are impossible to add to a language and features we can add with macros. With macros we can extend the language in any way we want and it remains lisp. COMMON LISP lacks threaded code in the same sense that it lacks continuations and first-class macros: they are omitted from the language deliberately and left for macro writers to implement as needed. One of the most important results of this chapter and its code is to show that even when they are Flubs, lisp languages can transform into non-Flub languages through macros. Non-Blub implies non-Flub, or, in other words, if you can't turn a language into a non-Flub, it must be a Blub. However, the opposite is not true. Non-Flub languages like forth remain Blubs and the most straightforward way to turn them into non-Blubs currently known is to implement lisp environments with them—and then you're programming lisp.
Instead of using consecutive memory cells to represent threads as with indirect/direct threaded code, our forth takes advantage of lisp's dynamic typing and cons cell list structure. We call this cons threaded code. The macro forth-inner-interpreter expands into code that is capable of following these cons cell linked-list threads. It might seem strange to start programming the logic for our forth environment here—with a macro designed to be expanded into some as-of-yet unknown expression—but this is in fact a desirable lisp programming pattern. Because macros let us start programming anywhere we want, why not start with the really interesting, driving bits of a program? These are the bits that will have the most influence on the program's ultimate design.
The definition of forth-inner-interpreter is itself a concise definition of what we mean by cons threaded code. The car of every cons cell is points to either a function, another cons cell, or some other lisp atom. Functions are executed as they are encountered. Notice that it is left for the function itself to update the pc register. If another cons cell is found in the thread it is assumed to indicate a subroutine call—a word invocation. Our inner interpreter will push the pc resume location onto the return stack and then jump to this new thread. If some other lisp atom is encountered, it is simply pushed onto the parameter stack and execution resumes at the next cell in our thread. The inner interpreter will return once it reaches the end of its thread and has no other threads to return to on its return stack.
But of course functions can't update the pc variable unless they are defined in its lexical scope8 so we employ another macro technique: instead of using defun, we create a similar interface that does something completely different. Def-forth-naked-prim feels similar to creating defun defined functions except that the code it expands into pushes the user provided forms onto a list stored in forth-prim-forms. Our eventual macros will use these forms to define the forth primitives inside its lexical scope. Because these forms will always be expanded into this environment, we are free to write code that uses all of our forth abstract registers like pc, pstack, etc.
Primitives defined with def-forth-naked-prim will not update the pc variable to the next cons cell in the thread. For the majority of primitives we should use def-forth-prim so the usual update is performed. Both of these macros expect the first argument to be a symbol used to refer to the primitive and the second to be a boolean indicating whether the primitive is immediate or not. The remainder of the arguments are lisp forms to be evaluated when the primitive is execute.
Eight simple primitives—none of them naked or immediate—are presented now. Nop is a dummy instruction that does nothing ("no operation"). The * primitive is the multiplication operator: it pops the top two values from the parameter stack, multiplies them together, then pushes the result back. Dup is short for "duplicate" and pushes the top value on the parameter stack onto the parameter stack again leaving two duplicate values. Swap will exchange the top two parameter stack elements using a very useful COMMON LISP macro: rotatef. It is no coincidence that forth also has (stack-based) rotation mechanisms. Print pops the parameter stack and prints it. >r transfers a value from the parameter stack to the return stack, r> does the opposite.
Does the name * violate our important variable capture rule from section 3.5, Unwanted Capture that forbids us from rebinding functions defined by COMMON LISP? No, because we haven't actually used this symbol to bind any functions—it's just the first element in one of the lists in forth-prim-forms. We have done nothing wrong. Symbols are independent from the functions or macros they are sometimes used to indicate. We can use any symbols anywhere, so long as we are careful to never violate our important variable capture rules. This only comes into play when writing lisp; we are writing forth.
If you remember nothing else from this book, remember the message of this section. Here we finally define and explain a concept we have touched upon throughout: duality of syntax. This section assumes you have read at least the three introductory chapters, chapter 6, Anaphoric Macros, and the preceding forth sections.
To most lisp programmers the fact that programming in lisp is more productive and, eventually, more natural than programming in Blub is empirically obvious, but answering why this is the case is much more difficult. While it's true that lisp gets its amazing power of expression from macros—and we have seen many interesting ones in this book and elsewhere—all explanations so far feel unsatisfactory. What is the real advantage of macros? A partial explanation certainly includes brevity, making your programs short. Here is its definition:
Let L be a programming language, F a feature in that programming language, and A an arbitrary program in L. F provides a brevity feature if A is shorter than it would be in a version of L without F.
Brevity features provide the basis and rational for the theory of brevity:
The effort required to construct a program is inversely proportional to the amount of brevity features available in the programming language used.
The theory of brevity is based on the idea that if your programming abstractions make the expression of programs very short and concise, writing them becomes easier because less code needs to be written. Our CL-PPCRE read macros are examples of brevity features: they shorten the rather long CL-PPCRE function names into concise, Perl-style expressions that save us key-strokes every time we use them. The theory of brevity is very applicable to writing small programs for which we know where we want to go when we start9. Unfortunately, most programs aren't like this. Most programs—at least the interesting ones—are created iteratively through a series of interactive write-test cycles that take into account feedback at each step along the way. Your abstractions may be brief, but if you're always having to change them to different (perhaps equally brief) abstractions, you likely won't save much effort. Instead of considering the length of the final program, maybe we should consider the length of the process required to get there.
In every language, programs end up looking different from how they start. Most programs start with just a simple sketch that is filled out and detailed as the author learns more about the problem. Before we come back to brevity and duality, this chapter walks us through the development of a simple program that will motivate the discussion: our forth environment.
Hm, where were we? Ah yes, we had rambled on a lot about abstract registers, abstract machines, and threaded code, as well as defining a word lookup utility called forth-lookup, an inner interpreter for our cons threaded code, and a system for collecting lists representing primitives in our forth system. But what will forth on lisp be? Well, what is the most natural form for any abstraction that mixes behaviour and state? Closures, of course. Our old friends, let and lambda. Hacking up this idea might give the following macro:
(defmacro new-forth ()
`(let ,forth-registers
(forth-install-prims)
(lambda (v)
(let ((word (forth-lookup v dict)))
(if word
(forth-handle-found)
(forth-handle-not-found))))))Our list of forth abstract registers, forth-registers, gets spliced directly into the expansion, initially binding all of the abstract registers to nil. Notice that we have left a lot of holes in the functionality of this macro. We have discovered that we are going to have to define a macro forth-install-prims which installs our primitive forms, as well as the macros forth-handle-found and forth-handle-not-found. But the most important thing we learn from this sketch is that, yes, this closure design looks like it could work. The idea, which came to us by just following the default lisp design, entails forth being a closure that is invoked once for every word we want to give it. Our sketch outlines an implementation for the following use case. Here we imagine creating a new forth environment:
(defvar my-forth (new-forth))
Here is some forth code for squaring the number 3 and printing the result:
3 dup * print
We could execute it on our forth environment like so:
(progn (funcall my-forth 3) (funcall my-forth 'dup) (funcall my-forth '*) (funcall my-forth 'print))
Although this is a clumsy interface to use, we are programming lisp so we know we can always create a macro to hide these details, and that is exactly what is done with the go-forth macro. Notice that go-forth uses the automatic once-only functionality of defmacro! because the first argument provided to go-forth is inside a loop defined with dolist and will probably not be evaluated exactly once as might be intended by users of the macro. With go-forth, feeding forth code into our forth environment becomes much cleaner:
(go-forth my-forth 3 dup * print)
At this point it might occur to us that we will eventually want to execute some forth bootstrapping code when creating new forth environments. So we need to be able to invoke the closure while creating it. This might require changing the program's let over lambda design or possibly creating some sort of wrapper function around our new-forth macro that uses the new-forth macro, loads in the standard library, and returns the resulting forth.
Because forth code is just a list of symbols and other atoms, our standard library that provides all of the bootstrapping we need (except for a few more primitives) can be stored in a list. The variable forth-stdlib keeps this list of forth code to be executed when new forths are created and the forth-stdlib-add macro expands into lisp code that will concatenate new forth code onto the forth-stdlib list.
What is the easiest way to adapt new-forth to support loading this standard library? Do you remember the alet macro we wrote in section 6.3, Alet and Finite State Machines? The purpose of this macro was to create a duality of syntax with COMMON LISP's let while binding the anaphoric variable this around the provided code. This refers to the result that will be returned from alet—the forth closure.
So changing our sketch is even easier than expected. All we have to do is change the first let symbol in our sketch to an alet and then add some code to load the standard environment into this, the forth closure10. We didn't have to re-arrange anything because alet's syntax was deliberately aligned with let's. Here is what this next iteration looks like:
(defmacro new-forth ()
`(alet ,forth-registers
(forth-install-prims)
(dolist (v forth-stdlib)
(funcall this v))
(lambda (v)
(let ((word (forth-lookup v dict)))
(if word
(forth-handle-found)
(forth-handle-not-found))))))Remember that alet introduces a layer of indirection using a closure and therefore makes our forth environment slightly less efficient. However, just as we don't know if this efficiency burden will be too much, we also don't know we won't end up needing this indirection. To eliminate the indirection, use the alet% macro defined just prior to alet.
Perhaps now, or perhaps later on when we're trying to build and debug our forth environment, it might occur to us that it would also be useful to be able to access the forth abstract registers from outside the forth environment. Unfortunately, these variables are closed over with a let over lambda. We will have to change our program again to make them accessible. There are, of course, many ways to do this. We could embed and return multiple closures in our forth environment, some of which could save and access the abstract registers, or we could re-consider our let over lambda strategy entirely. But before we do that, are there any dualities to help us? Remember plambda from section 6.7, Pandoric Macros? Its purpose was to create a duality of syntax with lambda, but one that creates closures that are actually open to the outside world. Changing our sketch to support this is a simple matter of prefixing a p character onto the lambda we return as our closure and adding the list of variables we want to export. Our list is conveniently available to us in forth-registers11. Our sketch becomes:
(defmacro new-forth ()
`(alet ,forth-registers
(forth-install-prims)
(dolist (v forth-stdlib)
(funcall this v))
(plambda (v) ,forth-registers
(let ((word (forth-lookup v dict)))
(if word
(forth-handle-found)
(forth-handle-not-found))))))With the forth closure opened up, we have available the following use case. This pushes five items onto a forth stack:
* (go-forth my-forth
1 2.0 "three" 'four '(f i v e))
NILAnd we can pandorically open my-forth to examine its parameter stack:
* (with-pandoric (pstack) my-forth
pstack)
((F I V E) FOUR "three" 2.0 1)This was the process performed to arrive at our final version of the macro new-forth. The final definition is identical to the last sketch except that it also sets the dtable abstract register to point to a hash-table (explained soon).
Programming, at least the interesting kind, is not about writing programs, but instead, changing them. In terms of productivity, brevity only takes us so far. We could rename lambda to, say, fn, but this brevity feature doesn't save much except for a few key-strokes here and there12. What does save us effort, however, is having lots of abstractions similar to lambda that we can use to change what code means without modifying the code itself much. Duality of syntax saves us effort.
Just like putting earmuffs on your special variable names can bite you by forcing you to add or remove asterisks if you change your mind about whether a variable should be special or lexical13, needlessly separating syntax and avoiding dualities can cause much pointless effort during programming. Another example: sharp quoting your lambda forms is a bad idea because it means you have just that much more to modify when you decide a function really needs to be an alambda or when you decide to use the lambda form in the function position of a list. Generalised variables also provide a very important duality: when writing macros, the same form can be spliced into expansions for both accessing and modifying the variable. COMMON LISP's dual meaning for the empty list and the false boolean value is yet another example—there is no real reason these two should be the same except for duality of syntax. Duality is also why this book has promoted closures instead of other CLOS features14 such as defclass and defmethod. There is usually less friction when modifying programs that use closures than when modifying programs that use classes and objects because we have so many good dualities of syntax for closures and because programming macros that build closures is more uniform15. With these and other examples in mind, we can finally give a clear definition of what is meant by duality of syntax:
Let L be a programming language, F a feature in that programming language, and A and B arbitrary programs in L. F provides a duality of syntax feature if the modifications required to change A into B become fewer than in a version of L without F.
Which leads to the theory of duality:
The effort required to construct a program is inversely proportional to the amount of dual syntax available in the programming language used.
While the concept of duality of syntax and the impact of its benefits are both quite clear, how to actually design good dualities is much less so. What are the most useful dualities in a certain language? How can we tell which of two different languages will provide better dualities of syntax for some given problem?
Because with lisp we control the programming language completely, we can design our language with as much or little dual syntax as we please. Following this train of thought is, in my opinion, the most fruitful area of programming language research today. Using lisp macros, just how similar can we make all of our disparate programs to one another so that changing them into new programs becomes that much easier16?
In both the definitions of brevity and duality, whether the feature F is effective or not depends on the programs being written or changed. Sometimes features that provide brevities or dualities can, in certain situations, actually increase the effort required. The best approach may be to provide as many useful brevity and duality features as possible while removing the ones that end up being more trouble than they are worth.
In this section, we really get forth going by filling in the holes left in the new-forth macro from the previous section. After having verified that the forth threading mechanism works, we bootstrap a forth programming environment and, along the way, explain what forth immediacy is and how it relates to lisp macros.
In the definition of new-forth, we left a hole in the macro that is to be filled by forth-install-prims. We would like to use a named abstraction without throwing out our lexical environment, so it must be a macro. The point of this macro is to compile and install the primitives into the forth dictionary when a new forth instance is created. Forth-install-prims expands into a progn form with each sub-form being an instruction to append a primitive word onto the dict linked list, wrap the provided code in a lambda, and set the word's name and immediate slots. In addition, the function created for each word by lambda, called thread, is added to our dtable hash-table (explained soon). Because all of these functions will be created in the scope of our original new-forth macro, they have full access to the forth environment specified by our abstract registers. Notice that the thread binding does not capture thread from any user provided code so we don't need to name it with a gensym.
We have said that forth provides a meta programming system not completely dissimilar from lisp's and that this system is based around a concept called immediacy. In traditional forths, there is a variable called state which is either zero or non-zero. If it is zero, the forth is considered to be in a regular interpreting (executing) state. If we give a word to forth in this state, that word will be looked up and executed. If, however, the base variable is non-zero, the forth is said to be in a compilation state. If we present a word to forth in this state, the address of the presented word is appended to the current thread being compiled—generally the most recently created word in the dictionary. There is one exception, however, and this is the important point about immediacy. If we are in compilation state and we are given an immediate word, that word will be executed instead of compiled. So, like lisp, forth allows us to execute arbitrary forth code at compile time.
Because we are building our forth as an abstract machine on lisp, we don't have to suffer arbitrary mappings of fixnum values to true and false. In lisp, we have a dynamic type system that lets us enjoy arbitrary mappings of all values to true and false. In place of the forth variable state, our forth system uses the compiling abstract register to store our compilation state as a lisp generalised boolean. The traditional forth words used to control the compilation state are [ and ], the open and close square brackets. [ takes us out of compilation mode and thus necessarily must be an immediate word. ] puts us back into compilation mode and so is only executed when we are interpret mode and doesn't have to be immediate. This choice of symbols may seem strange now but will become clearer in high level forth code. These square brackets allow us to designate a block of code to be executed in the middle of compiling a forth thread. In a certain sense, these brackets are like lisp's backquote and unquote operators. Here is how these words are usually used in forth code:
... compiled words ... [ interpret these words ] ... more compiled words ...
Like most of forth, these words are transparently specified which permits us use them in unusual ways. For example, these words aren't balanced in the same sense that lisp parenthesis are. If we choose, we can use them in the opposite direction:
... interpret these words ... ] compile these words [ ... more interpreted words ...
We even have the appearance of nesting, but this is not really nesting because we only have a single boolean state: Compiling or not-compiling.
... compiled words ... [ interpret these words ] compile these words [ interpret these words ] ... more compiled words ...
Our forth uses the forth-compile-in macro as an abbreviation macro. This macro compiles a forth word into our current thread, the thread of the last word created. Because our threads are represented by cons cells, we can use the lisp function nconc to simply append a pointer to the destination word's thread onto our current thread.
Another hole we left in the new-forth macro was what forth should do if it was able to lookup a provided word in the dictionary. This hole is filled by the macro forth-handle-found. This macro implements forth immediacy as described above. If we're compiling and the word looked up is not immediate, we compile it into our current thread. Otherwise we set our program counter pc to point to the thread of the looked up word and run the inner interpreter to execute the word. Recall that this macro will be expanded into a lexical environment in which word is bound to the looked-up forth word.
Our final hole in new-forth was what forth should do if it isn't able to find a word in its dictionary. Forth-handle-not-found fills this hole and implements some special cases. Recall that forth-handle-not-found will be expanded into a lexical environment that contains a binding v that refers to the value passed to forth. We also know that if this code is invoked, v will not refer to any word in the dictionary. If v is a symbol, forth-handle-not-found will throw an error. If the value is not a symbol, the behaviour is to push v onto the parameter stack or, if we are compiling, to compile it into the current thread. Two special cases are checked for, however. If v is a list with the first element quote, we push the quoted value onto the parameter stack. This is so that we can push symbols onto the parameter stack without them being interpreted as words. The second special case is if v is a list with the first element postpone. Postpone is an ANSI Forth word that unites and clarifies a couple traditional forth words. Postpone is used to always compile a word, even if that word is immediate. So, if we are in compilation mode a postponed immediate word will be compiled into our current thread even though it is immediate. Here is an example of postponing the [ word:
... compiling ... (postpone [) ... still compiling ...
With all the holes filled in our new-forth macro we are now in a position to create new forth instances with the new-forth macro. Earlier we created a special variable called my-forth with defvar. Even if we hadn't, we could implicitly declaim it special along with assigning it a value with a top-level setq17:
* (setq my-forth (new-forth)) #<Interpreted Function>
We can now use forth with the go-forth macro:
* (go-forth my-forth
2 3 * print)
6
NILBut so far we have only defined the words dup, *, and print. To do anything useful we will need more primitives. Like lisp, production quality forth implementations have a large number of words defined for programmer convenience. Over decades of use, many common programming patterns have been identified, abstracted into words, and then introduced into common forth vernacular. Like lisp, having the ability to extend the language defined as part of the language has resulted in much valuable experimentation. Because it is this philosophy and process we are investigating, we will not define many forth words that experienced forth programmers rely on. Instead, we aim for the minimal set of primitives required to explain forth's meta-programming system so we can compare it to lisp macros.
Three more primitives are defined, none of which are immediate or naked: create, name, and immediate. The create word appends a nameless word to the dictionary. Name pops a value from the parameter stack and sets the name of the last word in the dictionary to this value. Immediate simply sets the last word defined to be an immediate word. By default, words are not immediate.
Recall that we can execute code with our go-forth macro on our my-forth forth environment. Here we square the number 3 and print the result:
* (go-forth my-forth
3 dup * print)
9Do we have enough of forth to start bootstrapping forth with forth words itself? Although we don't really have defining words yet, thanks to the transparent specification of threaded code, we can begin to write forth words using forth. For example, here we use create to append a new empty word to the dictionary:
* (go-forth my-forth
create)
NILWe now use ] to begin compiling, add the words dup and * to the thread, then use [ to take us out of compilation mode:
* (go-forth my-forth
] dup * [)
NILNow we have a new word in our dictionary—one with a complete forth thread that, when executed by our inner interpreter, will square the number on the top of the stack. But this word isn't very useful unless we have a way of accessing it. We can give it a name using the word name. The name we assign will be the key we use to access our new thread:
* (go-forth my-forth
'square name)
NILNotice how the first value we passed to forth is quoted. Recall that we decided this behaviour should result in forth pushing the symbol square onto the parameter stack. This symbol is then consumed by the word name. Now that our word is named, we can evaluate it like any other word using the symbol square:
* (go-forth my-forth
3 square print)
9
NILSo the general technique for creating new words is the following pattern:
create ] ... compiled words ... [ 'whatever name
But we can use a bit of forth meta-programming to improve this interface. A definition of a new forth word, {, is added to the standard library. Its thread consists of two pointers, the first pointing to the word create and the second pointing to the word ]. So when the thread for this word is executed, it will append a new word to the dictionary and flip us into compilation mode. Forth generally uses the : word for this purpose, but this conflicts with lisp's use of : so we have elected to use { to start word definitions.
Similarly, we add a complementary word } to the standard library (replacing the traditional forth ;). There is actually no reason to define this word—the only thing it does is take us out of compilation state. We already have the word [ to do that for us. Despite this, defining { is useful because it gives us normal balanced brackets18 by creating a pair of words { and } that make defining new words intuitive.
We can now create a forth to take advantage of these new standard library features (throwing out our previous definition of the word square):
* (setq my-forth (new-forth)) #<Interpreted Function>
Here is what square looks like with the new word defining words { and }:
* (go-forth my-forth
{ dup * } 'square name)
NIL
* (go-forth my-forth
5 square print)
25And new threads can refer to our custom created words just as easily as primitives. Here is how we can define the word quartic as a thread with two pointers to our square word:
* (go-forth my-forth
{ square square } 'quartic name)
NIL(Expt 1/2 4) is indeed 1/16:
* (go-forth my-forth
1/2 quartic print)
1/16
NILBecause non-symbols are directly compiled into the forth thread and our inner interpreter treats non-functions as data items to push onto the stack when encountered, we can include numbers into a word definition:
* (go-forth my-forth
{ 3 } 'three name
three three * print)
9
NILRecall that we look up all elements passed to forth to see if they have been previously named in the dictionary using the eql function. The consequence of this is that we can use any lisp object to name a word. Here, we use a number19:
* (go-forth my-forth
{ 4.0 } '4 name
4 4 * print)
16.0
NILForth is an excellent language for learning how to use pointer scoping. Forth defines two simple operators that are used to read and write values from memory: @ (fetch) and ! (store). Because our forth words are stored in cons cells instead of memory words, dereferencing a pointer with fetch is implemented by taking the car of a pointer. Setting it with store is implemented by setting its car using setf. Fetch will pop a value from the parameter stack, assume it is a cons cell, fetch its car, then push that on the stack. Store will pop a value from the parameter stack, assume it is a cons cell, pop another value from the stack, and store it into the first value's car. For example, here is how we can create and print a cyclic list:
* (let ((*print-circle* t))
(go-forth my-forth
'(nil) dup dup ! print))
#1=(#1#)
NILSo now we're programming in forth using threaded code. Or are we? Did we ever leave lisp? The distinction between the two languages is so blurry that it can barely be discerned. The remainder of this chapter attempts to make this distinction even blurrier while explaining forth meta-programming further.
COMMON LISP has a lot of functions that we would like to be able to include in our forth threads. Forth-unary-word-definer expands into as many def-forth-prim forms as elements passed to its macro body. The elements are assumed to be symbols representing either functions or macros, but they could also be lambda forms. The only restriction with primitives named by lambda forms is that to invoke such primitives you will need to pass the same (eq) lambda form to the forth environment. Here is the expansion when passed one symbol, not:
* (macroexpand
'(forth-unary-word-definer
not))
(PROGN
(DEF-FORTH-PRIM NOT NIL
(PUSH (NOT (POP PSTACK))
PSTACK)))
TWe can use any COMMON LISP function that accepts one argument and forth-unary-word-definer will define a forth primitive that applies this function to the top element of the forth parameter stack.
An extension on this idea is forth-binary-word-definer which does the same thing except for operators that accept two values. The forth convention of treating the second-to-top element as the first argument to binary functions like - and / is enabled by creating a temporary let binding to hold the top element of the parameter stack. Here is an expansion for the word -:
* (macroexpand
'(forth-binary-word-definer
-))
(LET ()
(PROGN
(DEF-FORTH-PRIM - NIL
(LET ((#:TOP1767 (POP PSTACK)))
(PUSH (- (POP PSTACK) #:TOP1767)
PSTACK)))))
TExercise: When we use forth-binary-word-definer, how is it possible that we are able to treat macros like and and or as if they were first-class values?
Difficult exercise: Why was using a gensym (g!top) necessary for avoiding unwanted variable capture in forth-binary-word-definer? Hint: We've already discussed it in this section.
So these macros let us add various lisp functions to our forth primitive environment so we can use them from within forth. Here is an example use of a unary primitive, cadr:
* (go-forth my-forth
'(a (b) c) cadr print)
(B)
NILAnd a binary one, <:
* (go-forth my-forth
2 3 < print)
T
NILSo far our forth threads have been directed acyclic graphs, that is they consist of cons cell structure that doesn't point to itself anywhere (isn't self-referential) and which eventually terminates at our primitives, the leaves of the tree. For example, we can use pandoric macros to get at the thread that we created in the previous section when we defined the quartic word:
* (with-pandoric (dict) my-forth
(forth-word-thread
(forth-lookup 'quartic dict)))
((#<Interpreted Function> ;; square->|->dup
#<Interpreted Function>) ;; |->*
(#<Interpreted Function> ;; square->|->dup
#<Interpreted Function>)) ;; |->*The above comments only show it from the angle we printed the form in lisp. What we can't see from the code or the comments is that this thread structure is actually shared. To see that, use eq:
* (eq (car *) (cadr *)) T
Or look at it with *print-circle* set:
* (let ((*print-circle* t))
(print **)
t)
(#1=(#<Interpreted Function> ;; square->|->dup
#<Interpreted Function>) ;; |->*
#1#) ;; ————|
TThreaded code can allow forth amazing memory and size advantages. Entire forth systems are compiled code that is threaded together like this—from the network drivers to the highest level user programs. What's more, notice that we can cleanly extract the thread from quartic without taking a lot of extraneous other threads. For instance, we have many more primitives in our language, such as + and cadddr but they don't appear at all in the thread above. It's almost like we have a mark-sweep garbage collection algorithm that extracts only the threads that will be needed to execute a given forth word. In lisp this process is called tree shaking and is generally not very effective. In forth, however, it is extremely effective.
Unfortunately, the quartic thread we pandorically extracted from my-forth is not really that useful to us. It still permanently resides in the my-forth closure. That is, the lambda expressions representing the dup and * primitives have had their references to the forth abstract registers captured by an expansion of our macro, new-forth. Can we pull this code back up to the lisp macro surface so as to embed it in new programs? We will return to this soon but first we go a bit further into forth meta-programming.
At some level in any language—usually a level hidden from the programmer—it is necessary for code to be able to refer to itself. The most convincing example of this necessity is the observation that code needs to be able to refer to itself somehow in order to implement looping, recursion, and conditional expressions like if statements. The difference between Flub languages and non-Flub languages is that Flub prevents you from directly customising how and where self-references are inserted. But, as we are doing now, lisp's non-Blub status means we can make it a non-Flub.
Our forth system in its current state (without it being able to insert self-references) is almost a pure Flub. In a similar sense as to how pure functional languages deliberately define a language to be devoid of side-effects and non-static mappings, pure Flub languages are defined to be devoid of self-referential code constructs like loops and recursion. A consequence of this is that interpreting pure Flub threads will always terminate. Our forth environment is not completely pure because we can—and will—violate this, but is pure in the sense that if only used as so-far described will result in pure Flub threads. Pure Flub is not very useful so let's ruin the Flub purity of our forth environment. Instead of going in the Flub direction—towards Flub languages like COMMON LISP where code threading is opaque and inaccessible—let's go in the direction of forth and make this attribute of code macro customisable.
The branch-if primitive is the first naked primitive presented so far. Recall that naked primitives are primitives that don't update the program counter abstract register (pc) automatically. Instead, they must update it themselves. Branch-if will pop a value off the parameter stack. If the value is non-null, pc is set to the contents of the next cell in the thread being interpreted. If the value is nil, pc is resumed as usual except that it skips over the next cell in the thread being interpreted.
For example, the following creates a forth environment so we can take advantage of our new branch-if primitive, and defines two words: double and if-then-double.
* (go-forth (setq my-forth (new-forth))
{ 2 * } 'double name
{ branch-if double "Not doubling" print }
'if-then-double name)
NILDouble simply multiplies the top element of the parameter stack by two, doubling it. If-then-double requires two items on the parameter stack. The top element is consumed and the second from top element being doubled only if the top element was non-null. Notice that because the next value in the thread after branch-if is a pointer to another thread (double), control of execution is transfered to this other thread without pushing a resume location onto the return stack. In lisp this is called a tail-call. So if we pass nil20 to if-then-double then the branch is taken, no doubling happens, and the string is printed:
* (go-forth my-forth
4 'nil if-then-double print)
"Not doubling"
4
NILBut if the value is non-null, the branch is not taken, the doubling does happen, and the string is not printed:
* (go-forth my-forth
4 't if-then-double print)
8
NILThere is an easier way to exit from a word though, and it is implemented with a new word called exit. An interesting property of forth is that the word being called can decide whether or not it was a tail-call. Exit is a normal forth word and so is invoked as usual: forth pushes the current thread location onto the return stack and then sets the program counter to point to the start of the exit word. When exit is invoked, because it has direct access to the return stack with the primitives r> and >r, we can cause the calling word to never get back control of execution by simply removing the resume location from the return stack and dropping it out of existence. Here is an example use of exit:
* (go-forth my-forth
{ "hello" print
exit
;; Never gets here
"world" print } 'exit-test name
exit-test)
"hello"
NILSo branch-if implements a jump, or a goto instruction, possibly jumping to the value stored in the subsequent cell of the thread we are currently executing. Taking values from the thread you are currently executing is a common pattern in forth and requires naked primitives. Another primitive, compile, also uses this pattern. Compile is a naked primitive that will take the value of the next cell in the thread currently executing and then compile this value into the thread of the last word added to the dictionary—usually the word we are currently compiling. Here is a simple primitive that pushes the last cons cell of the thread being compiled onto the parameter stack. Our here is slightly different from the regular forth word here. In forth, here normally pushes the next location that will be compiled to instead of the last location compiled. This is because, in traditional forth, the memory location to be compiled next is known at this time—it will be the next adjacent memory cell. With cons threaded code we can't know this because we have not yet consed that memory.
With compile and here available we can now begin to write forth macros. Remember that when a forth word is immediate, at compile-time it will be executed instead of being compiled into the thread of the last word defined. In similar ways to how we can write macros to adapt and extend lisp, we can use immediate words to adapt and extend forth. In lisp, the basic data structures used for meta-programming are lists. In forth, the basic data structures are stacks.
You might have noticed that our forth environment doesn't even provide an if statement. We have a conditional branching primitive called branch-if, but so far this has only been useful for making tail-calls to other forth words. Recall that forth words are represented by threads and we can put a value for any thread into the cell jumped to by the branch-if. What if we put a value that leads to a part of the thread currently being compiled? We would have, in a sense, a tail-call to another part of our current forth word. Well, if statement is exactly that—a conditional tail call to the end of the if statement that is taken only when the condition is null.
Because we are programming completely in forth now, there is no need to add new primitives. To add an if statement to forth, we merely append some forth code to our standard library with the forth-stdlib-add macro. Notice that if is defined as an immediate word, meaning that it should only be used when compiling. But since it is immediate, it will be executed, not compiled. When immediate words are encountered, nothing is automatically compiled into the target thread. So if itself compiles in three words to the target thread: not, branch-if, and nop. It then executes the word here which leaves the address of the last compiled word (the nop) on the stack. It leaves it on the stack? That is a strange thing for a word to do at compile time. What stack does it leave it on? Technically, the stack in use at compile time is called the control stack. In most forths the control stack is one and the same as the parameter stack. The distinction is necessary because of the variety of ways that forth can be implemented. Sometimes, especially in cross-compilation environments, the control stack is completely separate from what will eventually be the parameter stack. But here—as with most interactive forth environments—we use the parameter stack for the control stack.
So, if pushes a value corresponding to a location where a nop was compiled. What use is this? The nop itself is not very important, but instead what precedes it. In the cell immediately before the nop there is a branch-if instruction compiled in. Whatever we change the value of the nop to be will be the location our inner interpreter branches to if the if condition turns out to be null.
But why did we put a nop there instead of the memory address? It's because we don't yet know the memory address. We need to wait for the programmer to execute another immediate word—then—which will consume the value left on the control stack by if. Then will compile in a nop itself and write the location of this nop over the nop compiled in by if. So all the words between the if and the then will be skipped over if the condition is null.
Abs is a word that makes use of if and then to calculate the absolute value of the top item on a stack. It simply checks if the value is below 0 and, if so, it calls another word, negate, to convert the negative value into its absolute value.
The most important reason why the control stack is used in this compilation process is because by using a stack it is possible to have control structures like if statements nest. That is, we can include if statements inside other if statements as long as we make sure to balance all if words with corresponding thens.
Because forth is a non-Flub language, how such threads are created and threaded together with control structures like if statements is transparently specified and open for us to adapt and extend. Most languages have an else clause associated with if statements; maybe we should add one too. Another immediate word else is added to the standard library. Else compiles into an unconditional branch to the terminating then so that if we took the true (secondary or consequent) branch, we will skip the false (tertiary or alternant) branch. Else then makes use of the value left on the stack by if to replace this nop with the location of the start of the else clause. It then leaves the location of its own nop on the stack for then to make use of. Because the behaviour we want then to perform is the same whether the location on the control stack was left by if or by else, then still works even if there is no else clause.
The word mod2 uses if, else, and then to reduce an integer to its natural residue under a modulus of 2. It pushes a 0 if the top of stack is even or a 1 if it is odd.
Because our conditionals perform tail-calls to other parts of the thread being compiled, there is no reason why we can't use the exact same techniques to create iteration constructs like loops. The most basic forth loop is defined by the begin and again immediate words. These two words provide a simple infinite loop and are implemented very similarly to if and then, except that the address saved on the control stack between seeing these two words corresponds to an address that should be compiled into a branch statement—not a location to compile an address. Here is a simple loop that counts down to 1 from a number provided on the stack and then exits from the word:
* (go-forth my-forth
{ begin
dup 1 < if drop exit then
dup print
1 -
again } 'countdown name
5 countdown)
5
4
3
2
1
NILNotice in the above example that an if and then construct is nested inside the begin-again loop. Thanks to forth's control stack it is perfectly acceptable to nest any control structures that respect the stack. To respect the stack, a control structure should avoid popping values it didn't push and should avoid leaving any extra values when finished. But just like we often choose to violate referential transparency when constructing lisp macros, in forth we often choose to not respect the stack when compiling. The following example is identical to the previous, except we don't use the word exit to escape from the loop. Instead, we flip into compile mode with the [ and ] words and swap the pointers placed there by if and begin so that we can use their matching then and again words out of order:
* (go-forth my-forth
{ begin
dup 1 >= if
dup print
1 -
[ swap ] again
then
drop
} 'countdown-for-teh-hax0rz name
5 countdown-for-teh-hax0rz)
5
4
3
2
1
NILIn the above, the code compiled by again, which is the code to bring us back to begin, is only executed inside the if statement. Very few other languages allow you access to the compiler in this way—only non-Flub languages to be precise. Because of this freedom, forth programmers are sometimes even more accustomed to macro combinations than are lisp programmers. Although the lisp code in this book uses macro combination techniques regularly, these techniques, and the leverage they can enable, aren't exploited to nearly their full possible extent by most existing lisp code. However, as this book has tried to illustrate, lisp is exceptionally well-suited to macro combinations. Such combination techniques are where I think some of the biggest wins in programmer productivity will be found in the next decade or so of language research.
So far this chapter has defined a minimalist forth environment and demonstrated some of the most important forth meta-programming concepts from a lispy perspective. Hopefully it has shown just how little effort it can take to design and implement a forth when you have the right tool (COMMON LISP). We can write forth programs to write forth programs—but we already knew that. That's what forth is all about. Further, because of lisp's macro system we can write lisp programs to write forth programs. But can we write forth programs to write lisp programs?
Recall that our forth threads are cons cells linked together and that the leaves of these trees are either functions (representing primitives) or atoms (representing data to push onto the parameter stack). Because we decided to make the forth abstract registers accessible through pandoric macros, writing utilities to acquire and print forth threads is easy. Get-forth-thread pandorically opens the forth closure forth passed to it then retrieves and returns the thread of the word given in word. Print-forth-thread prints this resulting thread with *print-circle* bound to t in case it contains cycles.
To demonstrate, suppose we define two forth words square and square3:
* (go-forth my-forth
{ dup * } 'square name
{ 3 square print } 'square3 name)
NILIn the compiled forth thread, all the symbols and other word information has been removed. All we have is a piece of list structure extracted from the dictionary of the forth my-forth:
* (print-forth-thread my-forth 'square3) (3 (#<Interpreted Function> #<Interpreted Function>) #<Interpreted Function>) T
The above code has no cycles and is thus a pure-Flub program. As said earlier, almost all interesting programs contain cycles. To create conditionals and loops we can use the naked forth primitive branch-if which allows us to change the pc abstract register to point somewhere indicated by the value in the subsequent cell in the forth thread being executed. We also were able to implement tail calls by directly accessing the return stack with >r and r>. Unlike most other languages, we can directly customise which calls are tail calls—even from inside the word being called.
But it seems we're missing one construct of central importance to lisp: recursion. Can a word call itself? We saw how we can use branch-if to jump back to the start of a word—tail recursion. What we would really like to do, however, is have a word call itself through the usual thread mechanism. To do this, it must have the start of its thread location stored as a cell in our thread so the current location is stored on the return stack and then it must set pc to the start of the word. So far none of our words has been able to make use of full recursion, however, because we don't name the word until we are done compiling it—it is inaccessible to us when we search the dictionary trying to compile a recursive call. Luckily, there is a simple trick we can use to get around this. We can simply flip out of compile mode and name the word we are compiling before we compile a recursive call. Here is an example definition of a fully recursive factorial calculator:
* (go-forth (setq my-forth (new-forth))
{ [ 'fact name ]
dup 1 -
dup 1 > if fact then
* })
NILSure enough, (fact 5) is 120:
* (go-forth my-forth
5 fact print)
120
NILExercise: Some forths use a word recurse which simply looks up the thread of the word currently being compiled and inserts it into the thread being compiled. This is called anonymous recursion. Write an immediate word that does this as an alternative to the above trick for implementing named recursion.
Fact's thread is more complicated than square3 above. It contains self-referential code:
* (print-forth-thread my-forth 'fact)
#1=(#2=#<Interpreted Function>
1 #<Interpreted Function> #2# 1
#<Interpreted Function>
#<Interpreted Function>
#<Interpreted Function>
#4=(#<Interpreted Function>
#<Interpreted Function>)
#1# . #4#)
TIn the above, #2# refers to the dup primitive and was compiled twice. #1# refers to the fact thread itself, implementing the recursion.
These structures look a lot like the lisp list structure that we use to write lisp programs, don't they? Because we understand the abstract machine that will execute these threads, we can, with a few restrictions explained shortly, compile these forth threads back into lisp list structure that can be inserted into an expression by a macro and compiled with our lisp compiler. This process is known as flubifying the code because we convert the compiled program from a uniform, programmable data structure (a thread) into an opaque, inaccessible block of code (a compiled COMMON LISP function).
There are, of course, major differences between forth threads and lisp list structure we can evaluate or insert into macros. First, the forth primitives are simple pointers to functions (displayed here as #<Interpreted Function>), but we need the lisp list structure that these functions were created with. Now is finally the time to explain the dtable abstract register we created. Dtable is a hash-table that gives a mapping from these functions to the list structure that created them, populated when the forth is created.
A large difference between forth threads and our lisp programs is that forth threads assume they can make use of a return stack—a concept that doesn't really exist in Flubs like COMMON LISP. We want to remove the need for our inner-interpreter code and, instead, let the lisp compiler handle this with regular lisp control structures like function calls and tagbody/go forms.
The remaining code in this chapter is presented differently than most of the rest of the code in this book in that its implementation is not described in detail, but rather from a high-level perspective. This is because the mechanics of the implementation are complicated and messy and, honestly, not that interesting. Suffice it to say that I suspect most lisp programmers would implement it similarly.
Flubify-aux is macro that expands into a function that takes a forth thread and converts it to a flubbed piece of lisp code, taking advantage of the fact that every non-primitive word is surrounded by a tagbody and so gensyms can be used as tags for gotos.
Assemble-flub is used heavily through flubify-aux as an abbreviation that checks a hash-table go-ht to see if there were any gos found on a previous pass that reference the location we are currently compiling. If they are, it adds the gensym tag chosen earlier for it to the tagbody form.
Flubify is the function that uses flubify-aux. It does the first pass, checking for branch-if instructions and building up the go-ht hash-table. It also recursively flubs all threads that are connected to our current thread. In fact, flubify can actually be doubly recursive—you just can't see it until you expand the use of flubify-aux. You can't see it, but lisp can. If referential transparency is a transparent pane of glass, here we are looking into a house of mirrors.
Compile-flubified takes a hash-table built by flubify and converts it into a form that uses labels to bind each of these flubbed threads into a function named in the function namespace by a gensym. Inside this scope, its expansion then funcalls the original thread (which is also flubbed).
Flubify-thread-shaker is the function that actually traverses our forth thread. It recursively shakes all connected forth threads. This means that it isolates just the relevant forth thread structure necessary to execute the given thread with the get-forth-thread utility, then translates each function into corresponding lisp code, skipping over if-branches and erroring on seeing a compile.
Forth-to-lisp is the ultimate function that the earlier macros and functions of this chapter facilitate. It takes a forth environment created by new-forth, looks up the thread indicated by the symbol passed as word, then returns corresponding lisp code to execute this thread. It first shakes the thread (recursively shaking all its connected threads), then applies the flubification procedure. Finally, it wraps a small amount of lisp code which implements the inner interpreter with regular lisp control structures.
To demonstrate, recall the forth words square and square3 we defined earlier. Again, here is how they were defined in the my-forth forth environment:
* (go-forth my-forth
{ dup * } 'square name
{ 3 square print } 'square3 name)
NILHere we convert the square3 thread to lisp:
* (forth-to-lisp my-forth 'square3)
(LET (PSTACK)
(LET ((#:G1814 (LAMBDA () ; dup
(PUSH (CAR PSTACK) PSTACK)))
(#:G1815 (LAMBDA () ; *
(PUSH (* (POP PSTACK)
(POP PSTACK))
PSTACK)))
(#:G1816 (LAMBDA () ; print
(PRINT (POP PSTACK)))))
(LABELS ((#:G1817 () ; square3
(TAGBODY
(PUSH '3 PSTACK)
(FUNCALL #'#:G1818)
(FUNCALL #:G1816)))
(#:G1818 () ; square
(TAGBODY
(FUNCALL #:G1814)
(FUNCALL #:G1815))))
(FUNCALL #'#:G1817))))Sure enough, the above is executable lisp code. If we wanted, we could compile it in somewhere using a macro. Or we could just eval it:
* (eval *) 9 NIL
To show how a forth thread with both branching and recursion is flubbed, here is a portion of the compiled lisp code from the forth word fact:
* (forth-to-lisp my-forth 'fact)
...
(LABELS ((#:G1803 () ; fact
(TAGBODY
(FUNCALL #:G1797) ; dup
(PUSH '1 PSTACK)
(FUNCALL #:G1798) ; -
(FUNCALL #:G1797) ; dup
(PUSH '1 PSTACK)
(FUNCALL #:G1799) ; >
(FUNCALL #:G1800) ; not
(IF (POP PSTACK) (GO #:G1804))
(FUNCALL #'#:G1803) ; fact
#:G1804
(FUNCALL #:G1801) ; nop
(FUNCALL #:G1802)))) ; *
(FUNCALL #'#:G1803)) ; fact
...So we wrote this program with forth but it is now lisp. We used the forth immediate words if and then to compile a conditional control structure that controls whether or not a recursion takes place. In place of a return stack, lisp will implement this recursion for us using its usual function calling infrastructure.
When testing this with eval, remember that the word fact assumes a value on the stack but we are starting with a fresh stack. To test this word we should create a wrapper word that adds the value to the stack. For example:
* (go-forth my-forth
{ 5 fact print } 'fact5 name)
NILWhich we can execute:
* (eval (forth-to-lisp my-forth 'fact5)) 120 NIL
As mentioned, because of the discrepancies between lisp and forth, our forth-to-lisp compiler has certain limitations. For instance, we no longer provide access to the return stack so any forth words that make use of r> or >r are forbidden. This includes exit, so our earlier word countdown will not function. However, because it doesn't use exit, countdown-for-teh-hax0rz will work. Because lisp programs are unable to access their return stacks, not all of forth's control structures can be implemented in Flub languages like COMMON LISP. Exercise: Add exit as a special case word that uses lisp blocks to return from a word.
Another restriction is that lisp code can't compile non-flub code so we can't translate forth words that use compile, such as if, then, begin, and again. Notice, of course, that forth threads created with these words can still be used to compile words, as above with fact. A final restriction is that, in forth, branch-if can jump to any thread, even if it was created inside a word different than we are currently executing. In lisp, we can only go to other locations within our tagbody. Forth allows non-local branches but general non-local branches cannot be done in Flubs like COMMON LISP.
Wait a second. Didn't we just avoid all these Flub restrictions when we were programming with our forth environment earlier? Yes. Macros allow us to convert programs to and from lisp. Thanks to macros, anything can be programmed in lisp.
All material is (C) Doug Hoyte unless otherwise noted or implied. All rights reserved.