# Some may call it “pointless”, but I absolutely love the point-free tacit programming style. The level of brevity can be truly astounding! Some of the terseness comes from not having to mention parameter names all over the place and much of it comes from the relentless factoring that this style makes straight forward (the Factor language is well-named).

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 BackusFP (must read his Turing Award lecture) and most recently I’ve spent some time playing with Kona.

## It’s All About Composition Baby!

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!

## Composition Refresher Course

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

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).

## Composing n-Arity Functions

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.

## F# Embedded “Forth”

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

Each of these takes and returns a stack of floats. For example:

[42.]

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) []

[42.]

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!

## Conditionals

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:

## Recursion

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.]

[5040.0]

## Finale

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.]

[2.718281828]

Actually, I lied though. My favorite number is zero of course.

1. gasche says:

Note that in your article, the recursion is actually used in pointful manner, not pointfree : his REC constructor takes a function. It would be cooler to push a higher-order operator on the stack then push a REC word to build a recursive operator from it. I'm under the impression that you cannot do that because you stack is monomorphic (only floats).

I think it should be possible to hack in a ML-level language (possibly Haskell with GADTs) a typed representation of the stack. The royal way to do it, however, is to use depend types, as in this example of compilation of a small typed language to a small typed stack.

2. @gasche You're exactly right! I couldnâ€™t get around the recursion being done in a pointful manner  because the stack is only floats. If we could push functions (or quotations of words) onto the stack, that would be powerful. I know some stack languages (Joy and Factor for example) allow this and then have many combinators that take quotations as argument. Joy has a whole set of recursion combinator words that work exactly like that. Check out the â€śPractical recursion combinators in Joyâ€ť section near the bottom of this â€śRecursion Theory and Joyâ€ť paper: http://www.latrobe.edu.au/…/j05cmp.html

And now Iâ€™m going to have to study the link you gave. Thanks much!

3. Chris says:

Having had a little exposure to it in school, I generally like the idea of functional programming — but it strikes me as something that would be practical only for ivory-tower academics who can actually internalize and make use of the concepts of lambda calculus and "currying" (whatever that is; I can never remember, let alone understand).  I for one can't make heads or tails of even the first example in this article — hom(AxB, C) = hom(A, hom(B, C)).  That notation conveys absolutely nothing to me about what's supposed to be HAPPENING there.  It doesn't strike me as a function declaration OR a function implementation, so I don't really see what it is.  If it's supposed to actually mean something, you've failed if that's not at least a little bit clear to a 20+ year veteran of professional programming who is also currently a Master's degree student in Computer Science.  Frankly, anybody who has to program a reasonable volume of code in a reasonable volume of time, and convey the meaning of that code meaningfully to someone else in the same boat at the same level (i.e. who is not an ivory-tower, holier-than-thou type) is better off sticking to the imperative programming style of traditional languages.

4. @Chris wrote:

That notation conveys absolutely nothing to me about what's supposed to be

HAPPENING there.  It doesn't strike me as a function declaration OR a function

implementation, so I don't really see what it is.  If it's supposed to actually

mean something, you've failedâ€¦

Sorry about the notation. Itâ€™s F# code (all valid, executable as is), It descends from ML along with a bunch of other languages; an entirely different branch of the language tree to all the â€ścurly brace languagesâ€ť though. Itâ€™s about as natural for an ML-guy to read as curly braces and such are to those guys.

I use verbose syntax in imperative languages all day every day at work and I agree that imperative programming has a long life ahead of it in the industry. I disagree that functional programming is â€śpractical only for ivory tower academics.â€ť Iâ€™m not an academic. I spend the majority of my work day coding away on shipping products (seldom, but occasionally, in F#). While I can get joy out of shipping products and out of architecture-level elegance, the languages I generally use at work are not â€śfunâ€ť or elegant at all. This blog is about playing around with fun ideas. Itâ€™s a hobby, not â€śresearch.â€ť đź™‚

5. Itâ€™s a bummer that MSDN doesnâ€™t allow commenting here without a Live ID. I get tens of thousands of hits to this blog, but hardly any discussion. Thereâ€™s a little thread doing though over at: http://www.reddit.com/…/programming_is_pointless

@grauenwolf Does a good job enumerating the short comings of the point-free style when he says why he does want to see the x in let h x = f (g x)

This stuffâ€™s not for everyone I realize and, despite Factorâ€™s slogan â€śA practical stack languageâ€ť, itâ€™s not always practical. His points are very valid, but Iâ€™d like to give the counter points as well:

It tells me at a glance how many paramters the inner-most function expects.

True. So called â€śstack effectâ€ť comments are needed to keep it straight. In general though, I donâ€™t like having to â€ścodifyâ€ť information meant only for the human. Maybe something more structured than freeform comments to enable tool support to make it â€śglanceableâ€ť

It gives me a place to hang the data type if I want more clarity.

Very true. Again though, I would rather the types be inferred for me (not codified) and again perhaps with tool support for the human to see.

I can give x a real name like "Width" so you know what to pass

A stack effect comment can give it a name; again, not codifying information meant for the human rather than the compiler.

There are more ways to compose functions than just strict nesting. Sometimes I want f( x + g(x)).

Yep, so you can use + as a prefix function instead of an infix operator and then still do pure composition, but still youâ€™re wanting to pass x to two functions. Youâ€™d have to use a â€śdupâ€ť or some combinator (like Factorâ€™s â€śbiâ€ť – elasticdog.com/…/beginning-factor-shufflers-and-combinators) to handle that.

6. David Murphy says:

For the benefit of Chris, functional languages are used in anger in the real world too.  Erlang is heavily used in telecomms and breaking out elsewhere;  OCaml is being used by a major finance house and other forms of functional languages are being advertised for in real commercial companies.  There is a fairly widespread agreement that functional languages are very good for parallel processing development.

All programming language syntax is strange to someone who hasn't learnt it.  Ashley's blog is fascinating, but I think one needs to spend some time with learning F# to understand it all đź™‚