Perm url with updates: http://xahlee.org/comp/point-free_programing.html
What's Point-free Programing?
Xah Lee, 2010-11-07
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: The Concepts and Confusions of Prefix, Infix, Postfix and Fully Nested 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 or postfix, and the paren to mark parameters are no longer necessary. The following are examples of linear syntax.
The most familiar linear notation is unix pipe. For exmaple:
x | h | g | f
means 「f(g(h(x)))」 or in lisp nested notation as 「(f (g (h x)))」.
In other functional languages, 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 (e.g. 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 (e.g. 「x h g f」), are postfix notations, because argument comes first, functions come after. Those starting with argument at the right (e.g. 「f g h x」) are prefix notations. (See: The Concepts and Confusions of Prefix, Infix, Postfix and Fully Nested 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 function definition may be like this in postfix notation:
# square function
or prefix notation:
function square #
This defines 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 application. (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 and h, such that 「(f x y) = ((g x) y)」, where the result of 「(g x)」 is a function we'll call “h”, and result of 「(h y)」 will equal to 「(f x y)」.
It's hard to think how could one concretly 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” in computer science. (See: What is Currying in a Computer Language?))
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 making point-free syntax for function definition, is reduced to making 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, in 「(function (x) (g (f x)))」, we have in traditional math notation 「 f(x) := g(f(x))」. Now, since all functions have just 1 parameter, we simply don't need to write it anymore. So, we write 「(function (g (f)))」, and it's assumed that in the deepest level it's always a function, and some argument is to be fed to it.
In functonal 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:
- It is about a particular syntax for function definition.
- When defining a function, no symbol is used for function parameter.
And this syntax is made possible by:
- All functions in the lang are functions of one parameter only.
- Support linear notation. (prefix or postfix)
And allowing function of 1 parameter only is made possible by:
- Multi-param are just functions of 1 param of a list (APL, J).
- Support function decomposition (OCaml, Haskell)
Posts
