retro html formatted by nom
comments/suggestions to: mjb at nomlang dot org
<quote>
The stack, to recap, is a simple thing (or data-structure ) where you can put (data) items on top of the stack (one at a time), or take them off (and maybe use them for something) but you can't do anything else. I know you already knew that, but this post is about the power and artistry of the stack and the languages and people who use them. It is actually (or could be) a ripping yarn.
The simplest useful computer language yet invented is called FORTH. It also,
in my opinion, contains some of the most powerful ideas ever “invented
” in the field of computer science. FORTH actually used to be pretty
popular several decades ago, mainly because it is so simple and small it
will run on machines with not much memory or speed, and it can also be
implemented from scratch without having a PhD in compiler-writing.
Lets have a look at some forth code:
: gcd ( a b -- n ) begin dup while tuck mod repeat drop ;
: gcd ( a b -- n ) ?dup if tuck mod recurse then ;
What do we notice? Well, the code is pretty succinct and there seem to be a few English words in there, which is nice, since staring at zeros and ones is not for everybody, and some of the English words seem a bit familiar in the context of programming such as “begin” which seems like it could be starting a loop, maybe?
Actually, there is all sorts of amazing magic happening in the code snippets above, and all sorts of strange heresies for those who are accustomed to lovely modern computer languages and compilers. But you need heresies and magic when you have to fit an entire, bootable (yes bootable, that means no operating system) compiling language system into about 4K bytes of computer memory.
Forth is trying to muscle in on this essay (or glorified blog post).
But I won’t let it. Before we move on, let me just add that forth pops
up in the most unlikely places. Here is a list: A comet in outer space
called “Philæ” which was visited by a NASA craft which was running
FORTH; in the block-chain engine which runs bitcoin ("bitcoin script");
in the “Postscript” document printing language; in the Mac PowerPC
OpenFirmware; on various microcontroller systems written by
obstinate German enthusiasts.
Possibly the most essential feature of forth is that it contains a
stack (and usually 2 stacks). And a stack has one interesting
“super-power”:
it can deal with patterns that are inside other
patterns. That doesn't sound like much; it certainly doesn't sound like
a super-power, but it is. The idea of a pattern being inside another
pattern is the one-dimensional alphabetic equivalent of a dot being
inside a circle. If your software cannot recognise that something is
inside something else, then you have a pretty serious problem.
Here is a strange proposition: Steve Jobs built his career on the nexus between æsthetics and computer-science and he did it by understanding the power and artistry of stacks. That is a totally ridiculous statement, I hear you groan, so let me explain.
In the early 1990's Steve Jobs heard about something called Postscript (see above) and became dazzled and enamoured by it, for the simple reason that it bridged the worlds of computer code and art. Postscript allowed the possibility of beautiful typography and document layout, which was something important to Jobs ever since he happened to wander into a typography class at Reed College after actually officially dropping out. Postscript has the elegance of simplicity and mathematical completeness but also the potential to create printed artistry. Perhaps even more important than the language or technology itself for Jobs, was the fact that Postscript made him aware that this liminal art/science space could exist. Jobs tried to buy the Postscript company (Adobe) outright and when he couldn't, he entered into a lucrative (for Adobe) contract to use the technology.
Postscript was such an important idea for Jobs that he developed the “Display” Postscript" windowing system that was central to the NeXTSTEP operating system and which eventually became MacOS. Again, Jobs' motivation in using Postscript for the computer display was æsthetic. Furthermore, either Jobs or one of his underlings must have realised the power of the pure stack-machine FORTH language, because they funded the development of the OpenFirmware project which is a comprehensive hardware-booting FORTH implementation complete with it’s own TCP/IP stack.
Now my ridiculous statement starts to seem a bit more plausible.
But this article is not about FORTH or Steve Jobs, it is about the connect between science, art and the stack data-structure. What would be the next most-simple computer language after FORTH? Well, a very good candidate is the LISP computer language (I just enjoy typing these Donald Trump caps-lock words because it makes me feel like I am back in the 1980's). Lisp has lots and lots of parenthesis inside each other, or what we like to call “nested” parenthesis. Now if you don't have a spare stack or 2 lying around, then you just can't have a language with nested parenthesis. It's impossible.
Lets digress a little. In the 1950's an American academic called Noam Chomsky showed that all languages (human, computer, and alphabetic patterns) can be arranged in a hierarchy. It is pretty amazing that it took the human race so long to realise this, but it did and the realisation is also quite spectacular because language or alphabetic patterns are just a special case of patterns in general, and patterns in general are pretty much the most important intellectual artifact that you are ever going to encounter.
Anyway, right at the bottom of Mr Chomsky's hierarchy are the “regular languages” . These are pretty simple and we can describe them with phrases such as:
at least one 'A' followed by an 'X' or a 'Y' followed by 3 'B's
Computer scientists and linguists may call these things “languages” but everybody else just calls them “patterns”. So I will too. These patterns are mainly only useful to the average punter (Australian slang) if they need to search for a word that they have lost in a large document. These “regular” patterns have one big big big limitation: they have no idea if one pattern is “inside” or within 2 other patterns. You can probably predict what I am about to say: Regular languages can't handle this “inside” or “within” concept because the machine which is used to recognise them has no stack . And yes, machines can recognise patterns, and they don't even have to be digital-logic machines: if you had some time to kill, you could build a machine out of stickle-bricks that recognises simple text patterns.
If somebody wants to bamboozle you with words and also sound particularly intelligent they may use the phrase “push-down automaton” but it just means a machine that has a stack.
So LISP, because it has numerous nested parenthesis is definitely not a
regular language. Somewhere, somehow it must have a digital stack so that the
computer can actually compile or execute. Lisp is famous for it’s list data
structure. Hence the name. But LISP is so simple and elegant that almost the
only thing it needs apart from a list is a stack, just like FORTH. Really the
only differences between forth and lisp is that lisp has parentheses, is
written left-to-right ("postfix") rather than right-to-left
("reverse-polish") and Lisp can recognise, out-of-the-box, categories of
characters (punctuation, letters etc) whereas Forth just thinks every
character is either white-space or not-white-space.
There is a famous Lisp programmer and essayist, who I have only just heard about (I know, I know) called Paul Graham who has had a strangely super-sized influence on digital culture and world history and who is also another case-study in my thesis about art, digital science and stack-machines. Graham studied art in Florence and computer science at Harvard - which all sounds very pleasant - and through his writing promotes the interconnections between both. I justify my outrageous assertion that he has had a big influence on “world history” because he is the founder of the ycombinator tech startup “incubator” and he funded, mentored and employed Sam Altman in his company. Sam Altman went on to start OpenAI and then triggered the large-language-model “AI” chatbot revolution that we are all currently, apprehensively, living through.
What is more, Paul Graham, publishes his large collection of essays in Postscript format. That seems like a neat little conclusion to my blog post. But I haven't come close to justifying a link between stack-machines and the art/digital nexus. Here goes: I believe that the stack is the most important art-enabling data structure because it contains within itself the idea of “within” and that in turn enables the possibilities of curves, shapes and amorphous areas.
This may be a tenuous proposition but try this little experiment: write a
little stack-based string-register virtual machine with a couple of
instructions to push and pop and throw in a few other
string-registers just for the fun of it (how about a list for
example?) and then just watch the creative ideas start to flow.
I did, and the result is called nomlang