Xah Lee
2010-11-08 05:35:55 UTC
new article.
• 〈What's Point-free Programing?〉
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 the position of words is just
function application or composition. So, it's like a strict postfix or
prefix syntax. (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.)
Here's a explanation. We'll use lisp notation because it's the most
clear.
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 Syntax
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 bracket parameters are no longer necessary. The following are
examples of linear syntax.
The most familiar linear syntax is unix pipe. For exmaple, we write 「x
| h | g | f」 to mean 「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 comes 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 // h
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」.
What is Point-Free Programing
Few things to remember what Wikipedia call “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 possible, is mostly caused by:
* The lang allows only function of one parameter.
* The lang support linear notation. (prefix or postfix)
When a multi-parameter function is needed, the lang either support
function decomposition (OCaml, Haskell), or you are forced to use a
list as its parameter (somewhat APL, J).
Xah ∑ http://xahlee.org/ ☄
• 〈What's Point-free Programing?〉
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 the position of words is just
function application or composition. So, it's like a strict postfix or
prefix syntax. (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.)
Here's a explanation. We'll use lisp notation because it's the most
clear.
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 Syntax
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 bracket parameters are no longer necessary. The following are
examples of linear syntax.
The most familiar linear syntax is unix pipe. For exmaple, we write 「x
| h | g | f」 to mean 「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 comes 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 // h
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」.
What is Point-Free Programing
Few things to remember what Wikipedia call “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 possible, is mostly caused by:
* The lang allows only function of one parameter.
* The lang support linear notation. (prefix or postfix)
When a multi-parameter function is needed, the lang either support
function decomposition (OCaml, Haskell), or you are forced to use a
list as its parameter (somewhat APL, J).
Xah ∑ http://xahlee.org/ ☄