Most of my exposure to it has been in stack languages like Forth, Joy, Cat, Factor, RPL and others with a shallow dive into J, K and APL and a look at John Backus’ FP (must read his Turing Award lecture) and most recently I’ve spent some time playing with Kona.
I mentioned briefly at the start of my TransForth series that a very nice way of thinking about programming in concatenative languages is to consider words to be stack->stack functions and then it becomes all about composition. What you’re doing is defining words in terms of composition of other words and threading a stack through them. Haskell uses a simple dot (.) for composition. Most stack languages use nothing! As Erik Meijer says, the most important operator in a language should be given the lightest-weight syntax. You can think of the whitespace between words as the composition operator.
One of my answers on Stack Overflow gave me the idea for this post. I realized that indeed we could build a simple point-free stack language without leaving F# at all. In fact it can all be done in a pure functional way. Keep in mind that this is just an experiment. Don't take it too literally or too seriously. The idea isn't to actually use this for anything real. The idea is to demonstrate the equivalence of "definitions" and "words" in concatenative languages to composition and stack->stack functions. Let's give it a try!
Given functions f and g (let’s say implementing squaring and doubling respectively):
let f x = x * x
let g x = x * 2
We can define a new function h, that combines the two (doubles and then squares):
let h x = f (g x)
It’s the x we don’t want to see and, wait a minute, this f (g x) is the very definition of composition itself.
let compose g f x = f (g x)
Given a function from a -> b and a function from b -> c, it returns a new function directly from a -> c. It’s the ultimate in higher order functional programming; a function that takes functions as arguments and returns a function as a result. You can do a lot with this useful little thing; in fact you can do everything.
In F#, “compose” is spelled >>. Not quite as nice as using whitespace as in Forth but it’ll do. This is very similar to the pipeline operator |> which can be thought of as threading an argument through a series of functions. If we rewrite our h using the pipeline operator it’s very clear that x is being given solely to be piped through:
let h x = x |> g |> f
With composition, we can sort of cancel out the x on each side and define it in a most succinct way:
let h = g >> f
Beautiful! The x has vanished, yet we end up with the same double-square function (for example, h 3 gives 36 in all three forms we’ve used).
One problem with composing a pair of functions is that not only do the argument types need to match, but the number of arguments must match as well. You may want to compose a sum function (adding two arguments) with a square function (taking a single argument) to get a function returning the square of the sum. This seems like a perfectly reasonable thing to do but it doesn’t work:
let sum x y = x + y // int -> int -> int
let sqr x = x * x // int -> int
let sumsqr = sum >> sqr // Type mismatch!
The trick is to use an n-arity collection type as the single argument for everything! Stack languages use a stack. You could potentially use some other data structure. Stacks are nice because then, without naming values, return values may be left as arguments being referenced only by position relative to the top of the stack. In this particular case, sum would pop two values, add them together and push back the result which would then be consumed by sqr.
If you’ve been following the TransForth series you’ll recognize most of these Forth words. I’ll even capitalize them to make it look like TransForth.
Let’s get started with some basic arithmetic functions:
let dyadic f = function (x : float) :: y :: t -> f y x :: t
let monadic f = function x :: t -> f x :: t
let ADD = dyadic (+)
let SUB = dyadic (-)
let MUL = dyadic (*)
let DIV = dyadic (/)
Each of these takes and returns a stack of floats. For example:
> [33.;9.] |> ADD
We can define a LIT function meant to be partially applied to produce a literal-pushing function:
let LIT n t = n :: t
And then convert to pure composition. We still need to plumb through an initial empty stack:
> (LIT 33. >> LIT 9. >> ADD) 
Wonderful! We can add some of the normal stack manipulation words:
let DROP = function _ :: t -> t
let DUP = function x :: t -> x :: x :: t
let SWAP = function x :: y :: t -> y :: x :: t
let OVER = function (_ :: x :: _ as t) -> x :: t
let ROT = function x :: y :: z :: t -> z :: x :: y :: t
let CLEAR _ = 
And even start defining them in terms of each other:
let DDROP = DROP >> DROP
let RROT = ROT >> ROT
let DDUP = OVER >> OVER
let NIP = SWAP >> DROP
let TUCK = SWAP >> OVER
let SQUARE = DUP >> MUL
let CUBE = DUP >> DUP >> MUL >> MUL
If you squint, this is looking a lot like Forth (: CUBE DUP DUP MUL MUL ;).
With one more primitive NAND function we can then define Boolean logic (using -1. and 0. as truth values as in Forth):
let NAND = dyadic (fun a b -> if not (a = -1. && b = -1.) then -1. else 0.)
let NOT = DUP >> NAND
let AND = NAND >> NOT
let OR = NOT >> SWAP >> NOT >> NAND
let NOR = OR >> NOT
let XOR = DDUP >> AND >> RROT >> NOR >> NOR
let XNOR = XOR >> NOT
With that and one more comparison primitive we can define greater-than (GT) and equal-to (EQ) and proceed to define the others in terms of them:
let comp f = dyadic (fun a b -> if f a b then -1. else 0.)
let GT = comp (>)
let EQ = comp (=)
let LT = DDUP >> GT >> RROT >> EQ >> OR >> NOT
let LEQ = DDUP >> LT >> RROT >> EQ >> OR
let GEQ = DDUP >> GT >> RROT >> EQ >> OR
let NEQ = EQ >> NOT
This is looking pretty good!
Implementing an if-then-else construct is a little trickier. In Forth it’s done with compile-time insertion of branches, but in a pure functional world what we want is a higher order function. Much like LIT takes an argument and returns a stack->stack function to be used in composition, IF will take two functions as arguments and return something composable. The two functions represent the true and false cases. That is, IF will execute one or the other depending on the top of the stack:
let IF t f = function x :: s -> (if x = -1. then t else f) s
If you want something more like an if-then without an else, just pass a no-op identity function for one of the cases:
let NOP = id
We can now define some words requiring conditionals:
let ABS = DUP >> LIT 0. >> LT >> IF (LIT -1. >> MUL) NOP
let MIN = DDUP >> GT >> IF SWAP NOP >> DROP
let MAX = DDUP >> LT >> IF SWAP NOP >> DROP
Notice that the arguments to IF are themselves just compositions. For fun and to show that we can define somewhat useful things, here is the quadratic formula (ax² + bx + c, but factored to x(ax + b) + c) - expecting x, a, b and c from the stack:
let QUADRATIC = DUP >> RROT >> MUL >> ROT >> ADD >> MUL >> ADD
Now we’re getting into some crazy territory. We could make higher-order words like LOOP, REPEAT, and such but, as I’ve said before, recursion is the new iteration. All the cool kids prefer it :-)
Let’s trying making the old favorite factorial function with a recursive definition similar to:
let rec fac n = if n > 1 then n * fac (n - 1) else n
…but in our completely point-free style. I’d love to just use F#’s rec keyword and say:
let ONE = LIT 1.
let rec FAC = DUP >> ONE >> GT >> IF (DUP >> ONE >> SUB >> FAC >> MUL) NOP
However, this can’t possibly make sense and we get an error complaining that FAC is, not just calling itself but is, defined in terms of itself.
Now be sure you’re sitting down for this part. If you’ve never seen this before you may have your mind blown. We’re about to pull the crazy Y-combinator out of the toolbox. This function is so cool that people have it tattooed to themselves.
let rec Y f x = f (Y f) x
It looks simple enough. The Y combinator essentially takes a function which is not recursive and returns a version of it that is. How does it do it? Magic! The function given to the Y combinator is expected to itself take a function (and a value) which it’s able to use to recurse. The Y combinator generates this by applying itself to the function given! I really should write a separate post explaining this but, to stick to the “pointless” topic at hand, let’s just see it in action. A rewrite of our plain F# factorial function from above would look like:
let fac = Y (fun f n -> if n > 1 then n * f (n - 1) else n)
Notice there’s no rec keyword (and no fac in the body), yet it works! We can do the same for our Forth-style version:
let FAC = Y (fun REC ->
(DUP >> ONE >> GT >> IF (DUP >> ONE >> SUB >> REC >> MUL) NOP))
It's a bummer that we can't avoid doing this in a pointful manner (the REC argument), but it works nicely:
> FAC [7.]
For a finale, and using our FAC to demonstrate that you can compose recursive functions, let’s calculate my favorite number (the constant e) using the power series:
We can run the series to some finite k and it quickly converges; in fact to n-decimal places with a max k of n+3.
let EULER_GEN = Y (fun REC -> DUP >> FAC >> ONE >> SWAP >> DIV >> ROT >> ADD >> SWAP >> ONE >> SUB >> DUP >> LIT 0. >> GT >> IF REC DROP)
Given a max k (of 12) and an initial seed value (of 1) it spits out e to the 9th decimal place:
> EULER_GEN [12.; 1.]
Actually, I lied though. My favorite number is zero of course.