What's Point-free Programing? (point-free function syntax)

By Xah Lee. Date:

This page explains what's point-free programing, and how is it possible.

Discovered a new programing language. Factor (programming language). Quote:

Factor is a stack-oriented programming language created by Slava Pestov. Factor is dynamically typed and has automatic memory management, as well as powerful metaprogramming features. The language has a single implementation featuring a self-hosted optimizing compiler and an interactive development environment. The Factor distribution includes a large standard library.

What's interesting is that it's called Concatenative programming language. Quote:

A concatenative programming language is one in which all terms denote functions and the juxtaposition of terms denotes function composition.[dead link][1] The combination of a compositional semantics with a syntax that mirrors such a semantics makes concatenative languages highly amenable to algebraic manipulation and formal analysis.[2]

Basically, it's another interesting advance of functional programing. Now, every “word” is a function, and a sequence of words effective means function chaining or composition. So, it's like a strict postfix or prefix syntax but without operators. (See: Concepts and Confusions of Prefix, Infix, Postfix and Lisp Notations)

Point-free programming

Another new jargon i learned is Point-free programming (aka “tacit programing”, “pointless programing”). Here's a quote:

Tacit programming is a programming paradigm in which a function definition does not include information regarding its arguments, using combinators and function composition (but not λ-abstraction) instead of variables. The simplicity behind this idea allows its use on several programming languages, such as J programming language and APL and especially in stack or concatenative languages, such as PostScript, Forth, Joy or Factor. Outside of the APL and J communities, tacit programming is referred to as point-free style[1], or more pithily as pointless programming. This is because of the relation between how definitions are done in pointless topology and how they are done in this style.

Basically, what that means is the elimination of formal parameters in function definitions. (similar to what Combinator notation is trying to do.)

How is It Possible to Not Have Variables in Function Definition?

here's a typical form of a function definition (using JavaScript):

function f(x,y) { return x+y;}

How is it possible to eliminate the variables? How do you specify where the argument goes?

Answer: thru some “tricks” of syntax, and theory of function.

Allow Functions of 1 Parameter Only

First, is to allow definition of functions of 1 parameter only. And all functions in the lang are all just single-parameter functions. This is done in 2 basic ways.

Multi-parameter as a List

The most simple way, is to consider multi-parameters function as function of a single parameter of a list. So, for example, if you need to define f(x,y), you can define it as a function that takes a list f(mylist), where the “mylist” is a list of 2 elements.

Function De-composition (aka Currying)

We'll discuss this later, below.

Linear Notation

Once the language allows only function of 1 parameter, then the syntax can be made into a linear form, either as prefix notation or postfix notation, and the parenthesis to mark parameters are no longer necessary. The following are examples of linear syntax.

The most familiar linear notation is unix pipe. For example:

x | h | g | f

means f(g(h(x))) or in lisp nested notation as (f (g (h x))). 〔►see Unix Pipe as Functional Language

In other functional languages such as OCaml 〔►see OCaml Tutorial: Function〕, this can be written simply as:

f g h x

or

x h g f

In the above, the space is a implicit operator, meaning function application.

In some lang with object oriented flavor, a “dot” syntax is popular (For example, JavaScript, Ruby, Java), like this:

x.h.g.f

or like this (perl):

x -> h -> g-> h

Those starting with the argument x and apply functions from left to right (For example, x h g f), are postfix notations, because argument comes first, functions come after. Those starting with argument at the right (For example, f g h x) are prefix notations. (See: Concepts and Confusions of Prefix, Infix, Postfix and Lisp Notations)

Here's Mathematica's prefix syntax:

f @ g @ h @ x

And the following is Mathematica's postfix syntax:

x // h // g // f

Dropping the Parameter

Now, if a functional lang allows only functions of one single parameter, and if its syntax is a uniform prefix or postfix linear syntax, then a expression of function (definition) may be like this in prefix notation:

function square #

or postfix notation:

# square function

Here, the function is a keyword for function definition (like perl's sub, lisp's lambda, JavaScript's function or Mathematica's Function.). The square # is the definition body. The # the formal parameter.

This expresses a function that squares a number. That is, it computes x^2. Now, notice, that every function definition will always have a dummy variable at the end of the line. So, it is syntactically redundant. We can simply drop it, and change the semantics of the “function” keyword to always assume there's a parameter.

Function Decomposition (Currying)

There is another technique for point-free programing syntax, by the theory of function decomposition. That is, instead of requiring multi-parameter function to take a list as argument, the lang automatically decompose any function of multi-parameter into a sequence of 1-param function applications. (aka function chaining)

Suppose you have a function of 2 parameters (f x y) (using lisp syntax here). Here, the “x” and “y” are called formal parameters (aka dummy variables). In a trivial math theory, any function of 2 parameters can be reduced to sequential application of functions of 1 parameter. That is, for any function f of 2 parameters, there exist functions g, such that (f x y) = ((g x) y).

Remember, the result of (g x) is a function. Let's call it “h”.

It's hard to think how could one concretely define g, or what g could be in some abstract function mapping model, but it's easy to think of it as the result of evaluating f with one of its parameter assumed as a constant. When you evaluate f with one of its parameter given, say (f 2 y) you get a function with 1 single parameter the y. That's your h, which is g evaluated at 2: (g 2).

(The process of de-composing function is sometimes called “currying”. 〔►see What's Currying in Computer Science?〕)

By this argument of reducing 2 parameters to 1, it follows that a function of n parameters can be expressed by a composition of functions that all have just 1 parameter. In other words, functions with 1 parameter is all you need, when thinking about the theoretical aspects of functions.

Languages like Haskell and OCaml, functions of multiple parameters are automatically de-composed into a sequence of functions of 1 parameter, in the syntax as well as at compiler level. In fact, the syntax used to define multi-param function, is just a variant syntax that is syntactically equivalent to the syntax for sequential application functions of 1 parameter. (See: OCaml Tutorial: Function)

So now, the task of devising point-free syntax for function definition, is reduced to devising a syntax for functions of 1 variable, but without using a symbol to represent dummy variable at all. This is now trivial, because you simply don't need to write that dummy variable, and always assume there's a variable to go with the function.

For example, suppose we want to define a function f, in traditional math notation: f(x) := g(f(x)). In lisp syntax, it's (function (x) (g (f x))). Now, if all functions in the language can have just 1 parameter, we simply don't need to write the “x” anymore. So, we write (function (g (f))), and just assume that in the deepest level a argument is to be fed to it. (the “deepest level” is the “right most” part in prefix notation, or “left most” in post-fix notation.)

In functional langs like Haskell, OCaml, Mathematica, they have prefix or postfix syntax. For example, g f x means (g (f x)). In this linear syntax, with point-free style, you simply don't need to write the x anymore, because it's always just the last part. You automatically assume the last part will be a argument. So you simply write g f.

Summary

Here's a few things to remember what “point-free programing” is:

And this syntax is made possible by:

And allowing function of 1-parameter-only is made possible by: