Tacit programming: Difference between revisions

Revision as of 07:47, 11 August 2020

Latest revision as of 21:14, 28 August 2025

(37 intermediate revisions by 23 users not shown)

Line 1:

{{Short description|Programming paradigmsparadigm}}

'''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 Cunha (|year=2005) [http|url=https://hdl.handle.net/1822/2869 |title=Point-free Program Calculation |degree=PhD |publisher=[[University of Minho]]}}</ref> It is also the natural style of certainsome [[programming languageslanguage]]s, including [[APL (programming language)|APL]] and its derivatives,<ref>W.{{cite Nevillebook |editor1-last=Holmes, ed|editor1-first=W. (Neville |year=2006) ''|title=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 unnecessarilyneedlessly obscure, hence the [[epithet]] "pointless style".<ref name="cunha2005"/>

[[Unix]] [[Command-line interface|scripting]] uses the paradigm with [[Pipeline (Unix)|pipes]].

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]]{{fact|date=June 2020}}

:<math> \hom(A \times B, C) \cong \hom(B, C^A)</math>

into computer functions, where the left represents the uncurried form of a function and the right the curried. ''C^A'' denotes the functionals from ''A'' to ''C'' (see also [[exponential object]]), while ''A'' × ''B'' denotes the [[Cartesian product]] of ''A'' and ''B''.{{fact|date=June 2020}}

==Examples==

Line 15 ⟶ 10:

<syntaxhighlight lang="python">

def example(x):

y =return baz(bar(foo(x)))

z = bar(y)

w = baz(z)

return w

</syntaxhighlight>

... iscan be written in point-free style as the composition of a sequence of functions, without parameters:<ref>{{cite web | url=http://concatenative.org/wiki/view/Concatenative%20language/Name%20code%20not%20values | title=Name code not values | publisher=Concatenative.org | accessdateaccess-date=13 September 2013}}</ref>

<syntaxhighlight lang="python">

from functools import partial, from functoolsreduce

def compose(*fns):

return partial(functools.reduce, lambda v, fn: fn(v), fns)

example = compose(bazfoo, bar, foobaz)

</syntaxhighlight>

For a more complex example, the [[Haskell]] code {{<code|1=>p = ((.) f) . g}}</code> can be translated as:

<syntaxhighlight lang="python">

p = partial(compose, partial(compose, f), g)

</syntaxhighlight>

===Functional programming===

A simple example (in [[Haskell (programming language)|Haskell]]) is a program which takescomputes athe sum of a list of numbers. AWe programmer mightcan define athe sum function recursively using a ''pointed'' style (cf. [[value-level programming|''value''-level programming]]) method as:

<syntaxhighlight lang="haskell">sum [] = 0

sum (x:xs) = x + sum xs</syntaxhighlight>

sum [] = 0

</syntaxhighlight>

However, by noting this asusing a [[fold (higher-order function)|fold]], thethis programmercan couldbe replace thisreplaced with:

<syntaxhighlight lang="haskell">

sum xs = foldr (+) 0 xs

</syntaxhighlight>

And then the argument is not needed, so this cansimplifies be replaced withto

<syntaxhighlight lang="haskell">

sum = foldr (+) 0

Line 59 ⟶ 48:

</syntaxhighlight>

The following Haskell-like pseudo-code[[pseudocode]] exposes how to reduce a function definition to its point-free equivalent:

<syntaxhighlight lang="haskell" line highlight="5">

p = \x -> \y -> \z -> f (g x y) z

= \x -> \y -> f (g x y)

Line 68 ⟶ 57:

= \x -> ((.) f) (g x)

= \x -> (((.) f) . g) x

= ((.) f) . g

</syntaxhighlight>

so

<syntaxhighlight lang="haskell">

p = ((.) f) . g

</syntaxhighlight>

Line 84 ⟶ 69:

<syntaxhighlight lang="haskell">

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

</syntaxhighlight>NoteAs that, as statedsuggested previouslyalready, the points in ''point-free'' refer to the arguments, not to the use of dots; a common misconception.<ref>{{Cite web |url=https://wiki.haskell.org/Pointfree#But_pointfree_has_more_points.21 |title=Pointfree - HaskellWiki|website=wiki.haskellHaskell.org Wiki |access-date=2016-06-05}}</ref>

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.

[[Euler's formula]] <math>e^{ix} = \cos x + i\sin x,</math> expressed tacitly:

<syntaxhighlight lang=j>

Line 106 ⟶ 93:

cos ← 2 ○ ⊢

sin ← 1 ○ ⊢

EulerCalc← cos + 0j1 × sin ⍝ 0j1 is what's usually written as i

j ← {⍺←0 ⋄ ⍺+0j1×⍵} ⍝ this part is not tacit

EulerDirect← *0J1×⊢ ⍝ Same as ¯12○⊢

Euler ← *∘j = cos j sin

⍝ 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!

</syntaxhighlight>

Line 113 ⟶ 105:

In [[stack-oriented programming language]]s (and [[concatenative programming language|concatenative ones]], most of which are stack based{{cn|date=January 2020}}), point-free methods are commonly used. For example, a procedure to compute the [[Fibonacci number]]s might look like the following in [[PostScript]]:

<syntaxhighlight lang="postscript">

/fib

{

dup dup 1 eq exch 0 eq or not

{

dup 1 sub fib

exch 2 sub fib

add

} if

} def

</syntaxhighlight>

===Unix pipelinePipelines===

====Unix pipeline====

{{main|Pipeline (Unix)}}

{{Further|Pipeline (Unix)}}

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]]. For example,

<syntaxhighlight lang="bash">

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 {{mono|sort}} and {{mono|uniq}} are the functions, the {{Code|-c}} and {{Code|-rn}} control the functions, but the arguments are not mentioned. The pipe <Code>|</code> is the composition operator.

Due to the way pipelines work, it is normally possible only 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.

====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 '|' is the composition operator.

In point-free style, this can 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 ==

Line 138 ⟶ 198:

* [[Function-level programming]]

* [[Joy (programming language)]], modern highly tacit language

* [[Pointless topology]]

==References==

Line 144 ⟶ 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]]