Tacit programming

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Tacit programming, also called point-free style, is a programming paradigm in which function definitions do not identify the arguments (or "points") on which they operate. Instead the definitions merely compose other functions, among which are combinators that manipulate the arguments. Tacit programming is of theoretical interest, because the strict use of composition results in programs that are well adapted for equational reasoning.[1] It is also the natural style of certain programming languages, including APL and its derivatives,[2] and concatenative languages such as Forth. Despite this following, the lack of argument naming gives point-free style a reputation of being unnecessarily obscure, hence the epithet "pointless style."[1]

For example, a sequence of operations in an applicative language like the following:

def example(x):
  y = foo(x)
  z = bar(y)
  w = baz(z)
  return w

...is written in point-free style as the composition of a sequence of functions, without parameters:[3]

def example: baz bar foo

The key idea in tacit programming is to assist in operating at the appropriate level of abstraction. That is, to translate the natural transformation given by currying:[dubious ]

 \hom(A \times B, C) \equiv \hom(A, \hom(B, C))

into computer functions, where the left represents the uncurried form of a function and the right the curried. hom(X, Y) denotes the homomorphisms from X to Y while, A × B denotes the Cartesian product of A and B.

Examples[edit]

Functional programming[edit]

A simple example (in Haskell) is a program which takes a sum of a list. A programmer might define a sum recursively using a pointed (cf. value-level programming) method as:

sum (x:xs) = x + sum xs
sum [] = 0

However by noting this as a fold the programmer could replace this with:

sum xs = foldr (+) 0 xs

And then the argument is not needed, so this can be replaced with

sum  = foldr (+) 0

which is point-free.

Another example uses the dot operator:

p x y z = f (g x y) z

We can simply group

f (g x y) z ≡ f ((g x) y) z ≡ (f .) (g x) y z ≡ ((f .) . g) x y z

so

p = (f .) . g

Finally, to see a complex example imagine a map filter program which takes a list, applies a function to it, and then filters the elements based on a criterion

mf criteria operator list = filter criteria (map operator list)

It can be expressed point-free[4] as

mf = (. map) . (.) . filter

APL family[edit]

In J, the same sort of point-free code occurs in a function made to compute the average of a list (array) of numbers:

 avg=: +/ % #

# counts the number of items in the array. +/ sums the items of the array. % divides the sum by the number of items

Stack-based[edit]

In stack-oriented programming languages (and concatenative ones, most of which are stack based), point-free methods are commonly used. For example a procedure to compute the Fibonacci numbers might look like:

/fib
{
   dup dup 1 eq exch 0 eq or not
   {
      dup 1 sub fib
      exch 2 sub fib
      add
   } if
} def

See also[edit]

References[edit]

  1. ^ a b Manuel Alcino Cunha (2005) Point-free Program Calculation
  2. ^ W. Neville Holmes, ed. (2006) Computers and People
  3. ^ "Name code not values". Concatenative.org. Retrieved 13 September 2013. 
  4. ^ pipermail

External links[edit]