# 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 Backus’ FP (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 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).

## 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**

** **

**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**

**[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:

** **

**let**** QUADRATIC = DUP >> RROT >> MUL >> ROT >> ADD >> MUL >> ADD**

## 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 9^{th} decimal place:

** **

**> EULER_GEN [12.; 1.]**

**[2.718281828]**

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

See also: [StackOverflow] What are the advantages and disadvantages of point free style in functional program?

stackoverflow.com/…/5682884

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.

adam.chlipala.net/…/StackMachine.html

@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!

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

whatit is. If it's supposed to actually mean something, you've failed if that's not at least alittlebit 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,andconvey the meaning of that code meaningfully to someone else in the same boat at the same level (i.e. who isnotan ivory-tower, holier-than-thou type) is better off sticking to the imperative programming style of traditional languages.@Chris wrote:

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.” 🙂

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

doeswant 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

practicalstack language”, it’s not always practical. His points are very valid, but I’d like to give the counter points as well: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”

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.

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

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.

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 🙂

Check this out too: fsharpforfunandprofit.com/…/stack-based-calculator