Let Over Lambda -- 50 Years of Lisp
by Doug Hoyte
Lisp Moving Forth Moving Lisp
Weird By Design
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.
FORTH-REGISTERS(defvar forth-registers
'(pstack rstack pc
dict compiling dtable))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.
FORTH-WORD(defstruct forth-word name prev immediate thread)
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.
FORTH-LOOKUP(defun forth-lookup (w last)
(if last
(if (eql (forth-word-name last) w)
last
(forth-lookup
w (forth-word-prev last)))))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.
Cons Threaded Code
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.
FORTH-INNER-INTERPRETER(defmacro forth-inner-interpreter ()
`(loop
do (cond
((functionp (car pc))
(funcall (car pc)))
((consp (car pc))
(push (cdr pc) rstack)
(setf pc (car pc)))
((null pc)
(setf pc (pop rstack)))
(t
(push (car pc) pstack)
(setf pc (cdr pc))))
until (and (null pc) (null rstack))))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.
PRIM-FORMS;; Prim-form: (name immediate . forms)
(defvar forth-prim-forms nil)
(defmacro def-forth-naked-prim (&rest code)
`(push ',code forth-prim-forms))
(defmacro def-forth-prim (&rest code)
`(def-forth-naked-prim
,@code
(setf pc (cdr pc))))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.
BASIC-PRIM-FORMS(def-forth-prim nop nil)
(def-forth-prim * nil
(push (* (pop pstack) (pop pstack))
pstack))
(def-forth-prim drop nil
(pop pstack))
(def-forth-prim dup nil
(push (car pstack) pstack))
(def-forth-prim swap nil
(rotatef (car pstack) (cadr pstack)))
(def-forth-prim print nil
(print (pop pstack)))
(def-forth-prim >r nil
(push (pop pstack) rstack))
(def-forth-prim r> nil
(push (pop rstack) pstack))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.
Duality of Syntax, Defined
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))GO-FORTH
(defmacro! go-forth (o!forth &rest words)
`(dolist (w ',words)
(funcall ,g!forth w)))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.
FORTH-STDLIB(defvar forth-stdlib nil)
(defmacro forth-stdlib-add (&rest all)
`(setf forth-stdlib
(nconc forth-stdlib
',all)))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)NEW-FORTH(defmacro new-forth ()
`(alet ,forth-registers
(setq dtable (make-hash-table))
(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))))))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.
Going Forth
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.
FORTH-INSTALL-PRIMS;; Prim-form: (name immediate . forms)
(defmacro forth-install-prims ()
`(progn
,@(mapcar
#`(let ((thread (lambda ()
,@(cddr a1))))
(setf dict
(make-forth-word
:name ',(car a1)
:prev dict
:immediate ,(cadr a1)
:thread thread))
(setf (gethash thread dtable)
',(cddr a1)))
forth-prim-forms)))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.
FORTH-PRIMS-COMPILATION-CONTROL(def-forth-prim [ t ; <- t means immediate (setf compiling nil)) (def-forth-prim ] nil ; <- not immediate (setf compiling t))
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 ...FORTH-COMPILE-IN
(defmacro forth-compile-in (v)
`(setf (forth-word-thread dict)
(nconc (forth-word-thread dict)
(list ,v))))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.
FORTH-HANDLE-FOUND(defmacro forth-handle-found ()
`(if (and compiling
(not (forth-word-immediate word)))
(forth-compile-in (forth-word-thread word))
(progn
(setf pc (list (forth-word-thread word)))
(forth-inner-interpreter))))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.
FORTH-HANDLE-NOT-FOUND(defmacro forth-handle-not-found ()
`(cond
((and (consp v) (eq (car v) 'quote))
(if compiling
(forth-compile-in (cadr v))
(push (cadr v) pstack)))
((and (consp v) (eq (car v) 'postpone))
(let ((word (forth-lookup (cadr v) dict)))
(if (not word)
(error "Postpone failed: ~a" (cadr v)))
(forth-compile-in (forth-word-thread word))))
((symbolp v)
(error "Word ~a not found" v))
(t
(if compiling
(forth-compile-in v)
(push v pstack)))))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.
FORTH-PRIMS-DEFINING-WORDS(def-forth-prim create nil (setf dict (make-forth-word :prev dict))) (def-forth-prim name nil (setf (forth-word-name dict) (pop pstack))) (def-forth-prim immediate nil (setf (forth-word-immediate dict) t))
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 nameFORTH-START-DEFINING
(forth-stdlib-add
create
] create ] [
'{ 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.
FORTH-STOP-DEFINING(forth-stdlib-add
{ (postpone [) [
'} name immediate)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
NILMEMORY-PRIMS(def-forth-prim @ nil
(push (car (pop pstack))
pstack))
(def-forth-prim ! nil
(let ((location (pop pstack)))
(setf (car location) (pop pstack))))Forth 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.
Going Forther
FORTH-UNARY-WORD-DEFINER(defmacro forth-unary-word-definer (&rest words)
`(progn
,@(mapcar
#`(def-forth-prim ,a1 nil
(push (,a1 (pop pstack))
pstack))
words)))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.
FORTH-BINARY-WORD-DEFINER(defmacro! forth-binary-word-definer (&rest words)
`(progn
,@(mapcar
#`(def-forth-prim ,a1 nil
(let ((,g!top (pop pstack)))
(push (,a1 (pop pstack)
,g!top)
pstack)))
words)))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)))))
TFORTH-AND-LISP-WORDS(forth-unary-word-definer not car cdr cadr caddr cadddr oddp evenp) (forth-binary-word-definer eq equal + - / = < > <= >= max min and or)
Exercise: 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.
BRANCH-IF(def-forth-naked-prim branch-if nil
(setf pc (if (pop pstack)
(cadr pc)
(cddr pc))))The branch-if primitive is the first naked primitive presented so far. Recall that naked primitives are primitives that don't update the program c
0 Comments
Log in to join the conversation.No comments yet. Be the first to share your thoughts.