Probably all of you are familiar with the imperative programming paradigm and some of you may know about the functional paradigm, but I recently discovered and fell in love with the third one: concatenative. Let me tell you all about it using opaque examples and bad simplifications!
Trigger warning: section about functional programming is very simplified and I don't have proper education to go in more depth on this topic.
Imperative paradigm
The easy one
Imperative programming (IP) is what most people are familiar with as the majority of the most popular languages heavily support this paradigm. An algorithm in this paradigm is described as a series of orders (imperatives) that the machine executes to get the desired result.
Its popularity comes from the fact that hardware languages are imperative in nature: the processor reads commands one after another executing them in order. Higher level languages were built on top of lower level ones by people familiar with this low level imperativeness. They made these languages imperative too to facilitate efficient compilation or interpretation.
IP has a theoretical basis on Alan Turing's interpretation of computation - the Turing Machine. It's a hypothetical machine that consists of a memory that can be read one cell at a time and directives, which based on the current cell's content can change its value or move to another cell. That's roughly what happens in the processor, albeit in a much more sophisticated way. Not much thought is actually given to Turing's computationnal model directly when programming imperatively.
Functional paradigm
The elegant one
Functional programming (FP) stems from a different basis for computation theory - Alonzo Church's Lambda Calculus. In this model everything is a function that takes a single argument (another function) and returns a new function as a result. That may seem useless - what can you possibly do with just functions? - until you realize that you can define certain functions to represent numbers. If you do this well it is easy to define functions that act as mathematical operations, tuples, arrays, classes and any other thing you know from imperative programming and the whole algorithm ends up being defined as a function from program input to program output. In practice languages define these core concepts for you so you can use your familiar mathematical notation and focus on higher level stuff.
At first this looks like a weird way of writing normal code which doesn't translate that well into machine language. There is actually a grain of truth in the second statement, functional environments have their ways of efficiently translating their code into imperative machine language, though.
The power of FP lays not in how well it can emulate IP, but in what is different between them: just like imperative is close to the hardware, functional is close to maths. This puts off many people. Why would I care about mathematical basis of my code? It is supposed to operate on real data on a physical machine, not in the realm of theoretical constructs. And to that functional programmers answer: why not both?
People who actually learned this in college could tell you a lot about advantages of FP, but there are a couple of things I find particularly neat about it (except for the quirkiness of everything being a function): it doesn't allow for global variables* (or any variables at all), every function works only with information it got on its input, and types.
*If you don't know yet why globals are bad then let me google that for you.
Types
Basically all I know about FP
In IP types are tied to the physical representation of data: integers are a couple of bytes, strings are arrays of bytes, floats are also a couple of bytes but interpreted differently and so on. In FP there is no data, just functions, so types are based on certain properties of these functions, and data is defined as functions that fit these types. Integer is anything that has properties of an integer and can be used as an integer in functions that require integers as input. This makes types just sets of things that belong in this type. If something belongs to a set of integers it is an integer.
It allows to assign types to functions based on the input they require and output they give. Negation for example can have type int -> int because it takes an integer and returns an integer. Addition would be int -> int -> int because it takes an integer and returns a function that takes another integer that returns an integer - a sum of the previous ones. It is not defined for any other input, so it doesn't make sense to give it any other input. It's not that the function will throw an error if this happens: because you know exactly which function uses which types you can check during compile-time if a function receives input that is outside its input type and raise a compilation error. This prevents bad practices based on passing around data of unknown type and with careful code almost eliminates runtime errors.
From this comes the most amazing thing ever: because your whole program is a function in a pure mathematical sense you can prove its correctness. It's not easy and some languages hide the mathematical concepts so deep that it becomes impossible, but in some functional languages you can definitely prove your program does what you think it does. Ever got tired of writing unit tests for your application? Switch to FP and prove that your program will give correct output every time! Isn't that cool?
Why need anything else?
Isn't two enough?
You might think that between hardware efficiency of IP and mathematical purity of FP everyone should find their perfect way of coding, but we can do better! The solution would be to take the imperative paradigm and make it functional. Every IP program can be translated to FP by making each order a function that takes the program's state, transforms it and outputs a new state. If you do that to a normal imperative program then the state would contain all the declared variables and each function would have access to any of them making global variables a problem again. It requires some changes.
The solution most concatenative languages go for is to replace the variables with a stack. Each function can only access the top of the stack (actually a couple of top values), but getting to deeper values is hard which discourages attempts to recreate global variables. Each function can be treated as a functions that takes some arguments and returns some values depending on how it modifies the top of the stack. In this scheme it is even possible to make a whole type system by stating exactly what values the function expects at the top of the stack and what values it leaves there, and all that while retaining the imperative "do this then that" style of coding.
Concatenative syntax
What makes it so awesome
Concatenative programming (CP) takes from FP the fact that a program consists entirely of functions. If you join it with the fact that each function always takes in the state and spits out another state for the next function to take you realize there is no need for parentheses at all - you can just list functions one by one as they should be executed and the state passes through all of them in order. It is reflected by naming conventions: CP functions are called words, and can be any string of non-white characters because only them have any syntactical meaning.
Because each word exists as a standalone function that doesn't really care what's to the left or to the right you can freely mix and match words to create programs. If you have two programs then just writing them one after another will result in a program that runs the first one and passes its output to the second one -- hence the name "concatenative". This freedom of splitting and joining means that if you use certain word sequences often you can (and you should) define a new word that does the same job. Then you can assign this new word a (possibly) more verbose name, which makes the code cleaner - this is called factoring and is the superpower of CP. In fact you should be doing it in every paradigm, but CP makes it blatantly easy.
With good factoring the code should be self-documenting and each word definition shouldn't exceed 3 lines of code. Here you can see an example of a word that takes a game ID and an API key for Neptune's Pride and fetches game info using the API:
: fetch-game ( game-id api-key -- game-json/error-json )
prepare-params
prepare-post-data
game-url fetch-json
;
Obviously each of those four words used here is defined in an earlier section of the vocabulary, but they are of similar size and complexity. The programming language I'm using is called Factor to emphasize how important it is to factor out common code, or just any code that looks too complicated. Factoring groups code into small, understandable words which then make bigger words, which then make bigger words and so on. It is truly a marvel.
Which languages are concatenative?
Not many actually...
Most modern popular languages support both FP and IP despite being IP-based, but there is no viable way to support CP without huge syntax changes. This means we are left with whatever languages are designed to be CP from the start, and most of them are getting pretty old.
The first CP language (so old that they didn't use the word "concatenative" for it yet) is Forth. It's pretty low level and compiles to very fast code but lacks many modern features and useful libraries. Despite that it can be a good intro to the CP world.
A semi-modern language based on Forth is Factor which I presented earlier. Factor incorporates a primitive type system and a more functional-style control flow. It has a lot of useful and well documented libraries as its community was very active back in the day. It's not entirely dead now, but it's not very alive either.
There is a (not very long) list of concatenative languages at concatenative wiki, although most of them are either dead or unfinished. I say it with sorrow, but despite its power the concatenative paradigm is just another esoteric idea now.
Conclusion
What follows
Despite lack of support for the concatenative paradigm I'm still charmed by its simplicity and ease of factorisation and I will continue to play with concatenative languages for a while which may result in a couple more posts of a more practical nature. If you know a concatenative language that you can recommend (even as a curiosity) please drop a line below. See you soon with some tutorials on an old, unusable language.
Top comments (0)