One of the great things about Functional Programming languages is that they have very little syntax, which makes them great tools for writing short programs. In fact, there is so little syntax, that there are many Functional Programming languages that could be used with virtually all the examples in this book. A good Functional Programming language can copy an AST (and prefix expression too, rather conveniently!) with very little overhead. This makes them ideal tools for us.
There are plenty of freely available ones, and this CBOOK even has its own tiny version of Lisp, one of the most popular Functional Programming languages, built in. Try entering some simple prefix expressions and you’ll see how it works; it’s almost like using a calculator! Just enter an expression and click Run.
Notice that Lisp lets us put in multiple arguments, so (+ 1 2 3) is a legal expression. Try the standard operators and see if you can figure out how they work, for example things like:
(- 5 2 4)
(* 2 5 1)
(/ 10 5 2)
What this means is that not all operators are binary, even the ones that seem like they should be! Now what we have is an operator followed by list of operands.
Using more than two operands in prefix notation.
How about this example? (- 5 1 1)
If we run it through Lisp it gives us 3, but does that make sense? It is taking the tail of the list of numbers and subtracting them all from the head of the list.
Heads and tails in subtraction.
It turns out that these concepts of lists, heads and tails are extremely important for Functional Programming and the design of efficient programs. Let’s take a look at these next, but first we’ll take a quick detour and look at a more complete version of Lisp than this CBOOK has.