Concatenative Biology

There are several ways to categorize programming languages. One is to distinguish between applicative and concatenative evaluation. Most languages are applicative – functions are applied to data. In contrast, a concatenative language moves a single store of data or knowledge along a ‘pipeline’ with a sequence of functions each operating on the store in turn. The output of one function is the input of the next function, in a ‘threaded’ fashion. This sequence of functions is the program. Forth is an example of a concatenative language, with the stack serving as the data store that is passed along the thread of functions (‘words’). “Forth is a simple, natural computer language” – Charles Moore, inventor of Forth.

One of the great advantages of concatenative languages is the opportunity for extreme simplicity. Since each function really only needs to know about its own input, machinery, and output, there is a greatly reduced need for overall architecture. The big picture, or state, of the entire program is neither guiding nor informing each step. As long as a function can read, compute, and write, it can be an entity unto itself, with little compliance or doctrine to worry about. In fact, in Forth, beyond the stack and the threaded execution model, there’s precious little doctrine anyway!  Program structure is a simple sequence, with new words appended to the list (concatenated). The task of the programmer is just to get each word right, then move on to the next.

In nature, the concatenative approach is the only game in town. Small genetic changes occur due to several causes, random mutation being one of them. Each change is then put through the survivability sieve of natural selection, with large changes accumulating over large time scales (evolution). (Evolution is active across the entire spectrum of abstraction levels. Hierarchies emerge naturally, not through doctrine or design.)  Concatenation is the way by which these small changes are accumulated. Much of the epic and winding road of human evolution is recorded in our DNA, which is billions of letters long.

Concatenative DNA

This process can be seen happening right now in molecular biology. Consider the ribosome. This is the little machine inside a cell that reads a piece of RNA (a chain of nucleotides) and translates it into a protein (a chain of amino acids). There is no Master Control Program assigning names, delegating work, and applying functions. There is only a concatenative program, built up over the ages by evolution. So, basic life uses a fairly powerful and successful form of computation: DNA for storage, RNA for code, ribosome for computing, protein for application.
(and natural selection for testing) 🙂

We flatter ourselves when we talk of our ‘invention’ of levers, gears, factories, and computers. Nature had all that stuff and much more long before we ever came down from the trees. Math, engineering, and science are great not because of their products, but rather because they enable 3-pound hominid brains to explore nature and ponder the possibilities.

2 thoughts on “Concatenative Biology

  1. ryan

    I’ve read a bit about Forth over the past year, but your explanation of code/stack/threading has made the most sense to me. Thanks for the fascinating articles on Forth. I confess I haven’t used it much. Sure I downloaded gforth before, but all the ANS forth implementations are pretty barren by most modern language standards. The cool thing in my admittedly ignorant opinion is you can build the most miniscule language you need and abstract away when you need to. I still haven’t found a truly great tutorial for doing this yourself. JonesForth is neat, but assumes you know a decent amount of Assembly. It’d be nice if someone wrote a full tutorial from the ground up that goes over building one from scratch (both indirect and direct threaded) and implementing needed words to solve a selected problem or two. I’ll eventually do this myself if nobody else does 🙂

    Keep up the posting please!

    Reply
  2. Ken Boak

    Thank you for illustrating the link between DNA and Forth – very interesting reasoning.

    I am currently writing a subset of Forth, that uses single characters as functions – partly for brevity and partly for speed of communication.

    It’s up to the user to allocate each letter memorably to each function.

    Which leaves us printable ascii between 48 (space) and 127 as the complete wordset.

    a-z are used as internal functions
    Symbols – such as + – * / are used for maths, logical and stack functions
    A-Z are left to the user to write their application

    I named it SIMPL – Serial Interpreted Minimal Programming Language and it’s run on Arduino, ARM, and MSP430

    One example

    Take the classic washing machine program

    FILL
    HEAT
    AGITATE
    DRAIN
    FILL
    AGITATE
    DRAIN
    STOP

    That’s 40 characters and 10 separating spaces.

    In SIMPL it just becomes the string FHADFADS – about one sixth of the length. Whole programs can be conveyed in a small message such an SMS or a short wireless packet.

    Moreover the ascii value of each character can be directly decoded to provide a jump address – which saves a lot of traditional dictionary searching.

    I’m currently implementing it on an MSP430 with FRAM – but the long term aim is to create a cpu in an FPGA that executes the code directly, to achieve 100 times the processing throughput.

    So the aim is to have a lingua franca – that can be implemented on the tiniest $0.30 microcontroller to the fastest of GPUs – because we are always trying to interface widely differing computational devices together.

    A final thought – Forth is a natural language interpreter, that can plough its way through reams of words in a very short time – associating and executing functions to each word. So it could be used to process and act upon the sort of text files (G-Code and Gerber files spring to mind.) that control machine tools – like plotters, CNC routers and 3D printers. These are the sort of desktop tools of the 21st century – that would benefit from a simple control language.

    Keep up the fascinating posts on Forth and it’s philosophy.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *