Tacit programming

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

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 APL and J and especially in stack or concatenative languages, such as PostScript, Forth, Joy, and Factor. Outside of the APL and J communities, tacit programming is referred to as point-free style,[1] or more pithily as pointless programming, because of the lack of explicit arguments, or points.

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:[2]

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:

 \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)

can be expressed point-free[3] 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. ^ "Pointfree". HaskellWiki. Retrieved 2008-05-09. 
  2. ^ "Name code not values". Concatenative.org. Retrieved 13 September 2013. 
  3. ^ pipermail

External links[edit]