Tacit programming
Tacit programming, also called point-free style, is a
Unix scripting uses the paradigm with pipes.
Examples
Python
Tacit programming can be illustrated with the following Python code. A sequence of operations such as the following:
def example(x):
return baz(bar(foo(x)))
... can be written in point-free style as the composition of a sequence of functions, without parameters:[3]
from functools import partial, reduce
def compose(*fns):
return partial(reduce, lambda v, fn: fn(v), fns)
example = compose(foo, bar, baz)
For a more complex example, the Haskell code p = ((.) f) . g
can be translated as:
p = partial(compose, partial(compose, f), g)
Functional programming
A simple example (in
sum (x:xs) = x + sum xs
sum [] = 0
However, using a fold we can replace this with:
sum xs = foldr (+) 0 xs
And then the argument is not needed, so this simplifies to
sum = foldr (+) 0
which is point-free.
Another example uses function composition:
p x y z = f (g x y) z
The following Haskell-like pseudo-code exposes how to reduce a function definition to its point-free equivalent:
p = \x -> \y -> \z -> f (g x y) z
= \x -> \y -> f (g x y)
= \x -> \y -> (f . (g x)) y
= \x -> f . (g x)
(* Here the infix compose operator "." is used as a curried function. *)
= \x -> ((.) f) (g x)
= \x -> (((.) f) . g) x
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
Note that, as stated previously, the points in 'point-free' refer to the arguments, not to the use of dots; a common misconception.[5]
A few programs have been written to automatically convert a Haskell expression to a point-free form.
APL family
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=: +/ % #
+/
sums the items of the array by mapping (/
) summation (+
) to the array. %
divides the sum by the number of elements (#
) in the array.
Euler's formula expressed tacitly:
cos =: 2 o. ]
sin =: 1 o. ]
Euler =: ^@j. = cos j. sin
(j.
is a primitive function whose monadic definition is 0j1
times x and whose dyadic definition is x+0j1×y
.) The same tacit computations expressed in Dyalog APL:
avg ← +⌿ ÷ ≢
cos ← 2 ○ ⊢
sin ← 1 ○ ⊢
EulerCalc← cos + 0j1 × sin ⍝ 0j1 is what's usually written as i
EulerDirect← *0J1×⊢ ⍝ Same as ¯12○⊢
⍝ Do the 2 methods produce the same result?
EulerCheck← EulerDirect=EulerCalc
EulerCheck ¯1 1 2 3
1 1 1 1
⍝ Yes, so far so good!
Stack-based
In
/fib
{
dup dup 1 eq exch 0 eq or not
{
dup 1 sub fib
exch 2 sub fib
add
} if
} def
Pipelines
Unix pipeline
In Unix scripting the functions are computer programs which receive data from standard input and send the results to standard output. For example,
sort | uniq -c | sort -rn
is a tacit or point-free composition which returns the counts of its arguments and the arguments, in the order of decreasing counts. The 'sort' and 'uniq' are the functions, the '-c' and '-rn' control the functions, but the arguments are not mentioned. The pipe '|' is the composition operator.
Due to the way pipelines work, it is only normally possible to pass one "argument" at a time in the form of a pair of standard input/output stream. Although extra file descriptors can be opened from named pipes, this no longer constitutes a point-free style.
jq
jq is a JSON-oriented programming language in which the '|' symbol is used to connect filters to form a pipeline in a familiar way. For example:
[1,2] | add
evaluates to 3. (Yes, the JSON array is a jq filter that evaluates to an array.)
Although similar to Unix pipelines, jq pipelines allow the incoming data to be sent to more than one recipient on the RHS of the '|' as though in parallel. For example, the program `add/length` will compute the average of the numbers in an array, so that:
[1,2] | add/length
evaluates to 1.5
Similarly:
[1,2] | [length, add, add/length]
evaluates to [2,3,1.5]
A dot ('.') can be used to define an attachment point on the RHS, e.g.:
1 | [., .]
evaluates to [1,1]
and similarly:
2 | pow(.; .)
evaluates to 4 since pow(x;y) is x to the power y.
Fibonacci sequence
A tacit jq program for generating the Fibonacci sequence would be:
[0,1] | recurse( [last, add] ) | first
Here, [0,1] is the initial pair to be taken as the first two items in the Fibonacci sequence. (The pair [1,1] could likewise be used for the variant definition.)
The alphabetic tokens are built-in filters: `first` and `last` emit the first and last elements of their input arrays respectively; and `recurse(f)` applies a filter, f, to its input recursively.
jq also allows new filters to be defined in a tacit style, e.g.:
def fib: [0,1] | recurse( [last, add] ) | first;
Composition of unary functions
In the section on Python in this article, the following Python definition is considered:
def example(x):
return baz(bar(foo(x)))
In point-free style, this could be written in Python as:
example = compose(foo, bar, baz)
In jq, the equivalent point-free definition would be:
def example: foo | bar | baz;
See also
- Combinatory logic
- Concatenative programming language
- Function-level programming
- Joy (programming language), modern highly tacit language
References
- ^ a b Manuel Alcino Pereira da Cunha (2005) Point-free Program Calculation
- ^ W. Neville Holmes, ed. (2006) Computers and People
- ^ "Name code not values". Concatenative.org. Retrieved 13 September 2013.
- ^ pipermail
- ^ "Pointfree - HaskellWiki". wiki.haskell.org. Retrieved 2016-06-05.
External links
- From Function-Level Programming to Pointfree Style
- Pure Functions in APL and J How to use tacit programming in any APL-like language
- Closed applicative languages 1971 - 1976 ff, in John W. Backus (Publications)