Let Over Lambda

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