# Programming is “Pointless”

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

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

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

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