Content deleted Content added
Petermsiegel (talk | contribs) |
→Functional programming: base case before the recursive case |
||
| (20 intermediate revisions by 12 users not shown) | |||
Line 1:
{{Short description|Programming paradigm}}
'''Tacit programming''', also called '''point-free style''', is a [[programming paradigm]] in which function definitions do not identify the [[parameter (computer science)|arguments]] (or "points") on which they operate. Instead the definitions merely [[function composition (computer science)|compose]] other functions, among which are [[Combinatory logic|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 logic|equational]] reasoning.<ref name="cunha2005">{{cite thesis |last1=Cunha |first1=Manuel Alcino Pereira da
{{Programming paradigms}}▼
▲'''Tacit programming''', also called '''point-free style''', is a [[programming paradigm]] in which function definitions do not identify the [[parameter (computer science)|arguments]] (or "points") on which they operate. Instead the definitions merely [[function composition (computer science)|compose]] other functions, among which are [[Combinatory logic|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 logic|equational]] reasoning.<ref name="cunha2005">Manuel Alcino Pereira da Cunha (2005) [http://hdl.handle.net/1822/2869 Point-free Program Calculation]</ref> It is also the natural style of certain [[programming languages]], including [[APL (programming language)|APL]] and its derivatives,<ref>W. Neville Holmes, ed. (2006) ''Computers and People''</ref> and [[concatenative programming language|concatenative languages]] such as [[Forth (programming language)|Forth]]. The lack of argument naming gives point-free style a reputation of being unnecessarily obscure, hence the epithet "pointless style".<ref name="cunha2005"/>
[[Unix]] [[Command-line interface|scripting]] uses the paradigm with [[Pipeline (Unix)|pipes]].
==Examples==
Line 15 ⟶ 12:
return baz(bar(foo(x)))
</syntaxhighlight>
...
<syntaxhighlight lang="python">
Line 25 ⟶ 22:
</syntaxhighlight>
For a more complex example, the [[Haskell]] code
<syntaxhighlight lang="python">▼
p = partial(compose, partial(compose, f), g)
===Functional programming===
A simple example (in [[
<syntaxhighlight lang="haskell">sum [] = 0
sum (x:xs) = x + sum xs</syntaxhighlight>
However, using a [[fold (higher-order function)|fold]],
<syntaxhighlight lang="haskell">
sum xs = foldr (+) 0 xs
Line 54 ⟶ 48:
</syntaxhighlight>
The following Haskell-like
<syntaxhighlight lang="haskell" line highlight="5">
p = \x -> \y -> \z -> f (g x y) z
= \x -> \y -> f (g x y)
Line 75 ⟶ 69:
<syntaxhighlight lang="haskell">
mf = (. map) . (.) . filter
</syntaxhighlight>
A few programs have been written to automatically convert a Haskell expression to a point-free form.
===APL family===
In the language [[J (programming language)|J]], the same sort of point-free code occurs in a function made to compute the average of a list (array) of numbers:
<syntaxhighlight lang=j>avg=: +/ % #</syntaxhighlight>
<code>+/</code> sums the items of the array by mapping (<code>/</code>) summation (<code>+</code>) to the array. <code>%</code> divides the sum by the number of elements (<code>#</code>) in the array.
Line 99 ⟶ 93:
cos ← 2 ○ ⊢
sin ← 1 ○ ⊢
⍝ Do the 2 methods produce the same result?
EulerCheck←
EulerCheck ¯1 1 2 3
1 1 1 1
Line 122 ⟶ 116:
</syntaxhighlight>
===
====Unix pipeline====
{{
In Unix scripting the functions are computer programs which receive data from [[Standard streams|standard input]] and send the results to [[Standard streams|standard output]].
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.
Due to the way pipelines work, it is
====jq====
[[jq (programming language)|jq]] is a [[JSON]]-oriented programming language in which the <code>|</code> 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 <code>|</code> as though in parallel. For example, the program <code>add/length</code> 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 (<code>.</code>) 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 <code>pow(x;y)</code> 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, <code>[0,1]</code> is the initial pair to be taken as the first two items
in the Fibonacci sequence. (The pair <code>[1,1]</code> 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 <code>recurse(f)</code> 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:
▲<syntaxhighlight lang="python">
def example(x):
return baz(bar(foo(x)))
</syntaxhighlight>
▲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.
In point-free style, this can be written in Python as:
▲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 descriptor]]s can be opened from [[named pipe]]s, this no longer constitutes a point-free style.
example = compose(foo, bar, baz)
In jq, the equivalent point-free definition would be:
def example: foo | bar | baz;
== See also ==
Line 143 ⟶ 203:
==External links==
* [https://function-level.github.io/ From Function-Level Programming to Pointfree Style]
* [http://portal.acm.org/citation.cfm?id=114065&dl=GUIDE&coll=GUIDE Pure Functions in APL and J] How to use tacit programming in any APL-like language
* [http://dirkgerrits.com/publications/john-backus.pdf#section.8 Closed applicative languages 1971 - 1976 ff], in John W. Backus (Publications)
▲{{Programming paradigms navbox}}
[[Category:Programming paradigms]]
[[Category:Programming language comparisons]]
<!-- Hidden categories below -->
[[Category:Articles with example Haskell code]]
[[Category:Articles with example Python (programming language) code]]
| |||