Function composition (computer science)

Last updated

In computer science, function composition is an act or mechanism to combine simple functions to build more complicated ones. Like the usual composition of functions in mathematics, the result of each function is passed as the argument of the next, and the result of the last one is the result of the whole.

Contents

Programmers frequently apply functions to results of other functions, and almost all programming languages allow it. In some cases, the composition of functions is interesting as a function in its own right, to be used later. Such a function can always be defined but languages with first-class functions make it easier.

The ability to easily compose functions encourages factoring (breaking apart) functions for maintainability and code reuse. More generally, big systems might be built by composing whole programs.

Narrowly speaking, function composition applies to functions that operate on a finite amount of data, each step sequentially processing it before handing it to the next. Functions that operate on potentially infinite data (a stream or other codata) are known as filters, and are instead connected in a pipeline, which is analogous to function composition and can execute concurrently.

Composing function calls

For example, suppose we have two functions f and g, as in z = f(y) and y = g(x). Composing them means we first compute y = g(x), and then use y to compute z = f(y). Here is the example in the C language:

floatx,y,z;// ...y=g(x);z=f(y);

The steps can be combined if we don't give a name to the intermediate result:

z=f(g(x));

Despite differences in length, these two implementations compute the same result. The second implementation requires only one line of code and is colloquially referred to as a "highly composed" form. Readability and hence maintainability is one advantage of highly composed forms, since they require fewer lines of code, minimizing a program's "surface area". [1] DeMarco and Lister empirically verify an inverse relationship between surface area and maintainability. [2] On the other hand, it may be possible to overuse highly composed forms. A nesting of too many functions may have the opposite effect, making the code less maintainable.

In a stack-based language, functional composition is even more natural: it is performed by concatenation, and is usually the primary method of program design. The above example in Forth:

g f

Which will take whatever was on the stack before, apply g, then f, and leave the result on the stack. See postfix composition notation for the corresponding mathematical notation.

Naming the composition of functions

Now suppose that the combination of calling f() on the result of g() is frequently useful, and which we want to name foo() to be used as a function in its own right.

In most languages, we can define a new function implemented by composition. Example in C:

floatfoo(floatx){returnf(g(x));}

(the long form with intermediates would work as well.) Example in Forth:

  : foo g f ;

In languages such as C, the only way to create a new function is to define it in the program source, which means that functions can't be composed at run time. An evaluation of an arbitrary composition of predefined functions, however, is possible:

#include<stdio.h>typedefintFXN(int);intf(intx){returnx+1;}intg(intx){returnx*2;}inth(intx){returnx-3;}inteval(FXN*fs[],intsize,intx){for(inti=0;i<size;i++)x=(*fs[i])(x);returnx;}intmain(){// ((6+1)*2)-3 = 11FXN*arr[]={f,g,h};printf("%d\n",eval(arr,3,6));// ((6-3)*2)+1 = 7arr[2]=f;arr[0]=h;printf("%d\n",eval(arr,3,6));}

First-class composition

In functional programming languages, function composition can be naturally expressed as a higher-order function or operator. In other programming languages you can write your own mechanisms to perform function composition.

Haskell

In Haskell, the example foo = f  ∘  g given above becomes:

foo = f . g

using the built-in composition operator (.) which can be read as f after g or g composed with f.

The composition operator  ∘   itself can be defined in Haskell using a lambda expression:

(.)::(b->c)->(a->b)->a->cf.g=\x->f(gx)

The first line describes the type of (.) - it takes a pair of functions, f,  g and returns a function (the lambda expression on the second line). Note that Haskell doesn't require specification of the exact input and output types of f and g; the a, b, c, and x are placeholders; only the relation between f,  g matters (f must accept what g returns). This makes (.) a polymorphic operator.

Lisp

Variants of Lisp, especially Scheme, the interchangeability of code and data together with the treatment of functions lend themselves extremely well for a recursive definition of a variadic compositional operator.

(define(compose.fs)(if(null?fs)(lambda(x)x); if no argument is given, evaluates to the identity function(lambda(x)((carfs)((applycompose(cdrfs))x))))); examples(define(add-a-bangstr)(string-appendstr"!"))(definegivebang(composestring->symboladd-a-bangsymbol->string))(givebang'set); ===> set!; anonymous composition((composesqrtnegatesquare)5); ===> 0+5i

APL

Many dialects of APL feature built in function composition using the symbol ∘. This higher-order function extends function composition to dyadic application of the left side function such that A f∘g B is A f g B.

foo←f∘g

Additionally, you can define function composition:

o←{⍺⍺⍵⍵⍵}

In dialect that does not support inline definition using braces, the traditional definition is available:

∇r←(fog)xr←fgx∇

Raku

Raku like Haskell has a built in function composition operator, the main difference is it is spelled as ∘ or o.

my&foo=&f∘&g;

Also like Haskell you could define the operator yourself. In fact the following is the Raku code used to define it in the Rakudo implementation.

# the implementation has a slightly different line here because it cheatsprotosubinfix:<∘> (&?, &?) is equiv(&[~]) is assoc<left> {*}multisubinfix:<∘> () {*.self}# allows `[∘] @array` to work when `@array` is emptymultisubinfix:<∘> (&f) {&f}# allows `[∘] @array` to work when `@array` has one elementmultisubinfix:<∘> (&f, &g --> Block) {(&f).count>1??->|args{f|g|args}!!->|args{fg|args}}# alias it to the "Texas" spelling ( everything is bigger, and ASCII in Texas )my&infix:<o>:=&infix:<∘>;

Nim

Nim supports uniform function call syntax, which allows for arbitrary function composition through the method syntax . operator. [3] 

funcfoo(a:int):string=$afuncbar(a:string,count:int):seq[string]=foriin0..<count:result.add(a)funcbaz(a:seq[string])=foriina:echoi# equivalent!echofoo(5).bar(6).baz()echobaz(bar(6,foo(5)))

Python

In Python, a way to define the composition for any group of functions, is using reduce function (use functools.reduce in Python 3):

# Available since Python v2.6fromfunctoolsimportreducefromtypingimportCallabledefcompose(*funcs)->Callable[[int],int]:"""Compose a group of functions (f(g(h(...)))) into a single composite func."""returnreduce(lambdaf,g:lambdax:f(g(x)),funcs)# Examplef=lambdax:x+1g=lambdax:x*2h=lambdax:x-3# Call the function x=10 : ((x-3)*2)+1 = 15print(compose(f,g,h)(10))

JavaScript

In JavaScript we can define it as a function which takes two functions f and g, and produces a function:

functiono(f,g){returnfunction(x){returnf(g(x));}}// Alternatively, using the rest operator and lambda expressions in ES2015constcompose=(...fs)=>(x)=>fs.reduceRight((acc,f)=>f(acc),x)

C#

In C# we can define it as an Extension method which takes Funcs f and g, and produces a new Func:

// Call example://   var c = f.ComposeWith(g);////   Func<int, bool> g = _ => ...//   Func<bool, string> f = _ => ...publicstaticFunc<T1,T3>ComposeWith<T1,T2,T3>(thisFunc<T2,T3>f,Func<T1,T2>g)=>x=>f(g(x));

Ruby

Languages like Ruby let you construct a binary operator yourself:

classProcdefcompose(other_fn)->(*as){other_fn.call(call(*as))}endalias_method:+,:composeendf=->(x){x*2}g=->(x){x**3}(f+g).call(12)# => 13824

However, a native function composition operator was introduced in Ruby 2.6: [4] 

f=proc{|x|x+2}g=proc{|x|x*3}(f<<g).call(3)# -> 11; identical to f(g(3))(f>>g).call(3)# -> 15; identical to g(f(3))

Research survey

Notions of composition, including the principle of compositionality and composability, are so ubiquitous that numerous strands of research have separately evolved. The following is a sampling of the kind of research in which the notion of composition is central.

Large-scale composition

Whole programs or systems can be treated as functions, which can be readily composed if their inputs and outputs are well-defined. [5] Pipelines allowing easy composition of filters were so successful that they became a design pattern of operating systems.

Imperative procedures with side effects violate referential transparency and therefore are not cleanly composable. However if one considers the "state of the world" before and after running the code as its input and output, one gets a clean function. Composition of such functions corresponds to running the procedures one after the other. The monad formalism uses this idea to incorporate side effects and input/output (I/O) into functional languages.

See also

Notes

  1. ↑ Cox (1986), pp. 15–17
  2. ↑ DeMarco & Lister (1995), pp. 133–135.
  3. ↑ "Nim Manual: Method call syntax". nim-lang.org. Retrieved 2023-08-17.
  4. ↑ "Ruby 2.6.0 Released". www.ruby-lang.org. Retrieved 2019-01-04.
  5. ↑ Raymond (2003)

Related Research Articles

In programming languages, a closure, also lexical closure or function closure, is a technique for implementing lexically scoped name binding in a language with first-class functions. Operationally, a closure is a record storing a function together with an environment. The environment is a mapping associating each free variable of the function with the value or reference to which the name was bound when the closure was created. Unlike a plain function, a closure allows the function to access those captured variables through the closure's copies of their values or references, even when the function is invoked outside their scope.

Generic programming is a style of computer programming in which algorithms are written in terms of data types to-be-specified-later that are then instantiated when needed for specific types provided as parameters. This approach, pioneered by the ML programming language in 1973, permits writing common functions or types that differ only in the set of types on which they operate when used, thus reducing duplicate code.

In mathematics and computer science, a higher-order function (HOF) is a function that does at least one of the following:

In computer programming, an assignment statement sets and/or re-sets the value stored in the storage location(s) denoted by a variable name; in other words, it copies a value into the variable. In most imperative programming languages, the assignment statement is a fundamental construct.

In computer programming, a function object is a construct allowing an object to be invoked or called as if it were an ordinary function, usually with the same syntax. In some languages, particularly C++, function objects are often called functors.

In functional programming, a monad is a structure that combines program fragments (functions) and wraps their return values in a type with additional computation. In addition to defining a wrapping monadic type, monads define two operators: one to wrap a value in the monad type, and another to compose together functions that output values of the monad type. General-purpose languages use monads to reduce boilerplate code needed for common operations. Functional languages use monads to turn complicated sequences of functions into succinct pipelines that abstract away control flow, and side-effects.

In computer programming, the ternary conditional operator is a ternary operator that is part of the syntax for basic conditional expressions in several programming languages. It is commonly referred to as the conditional operator, ternary if, or inline if. An expression a ? b : c evaluates to b if the value of a is true, and otherwise to c. One can read it aloud as "if a then b otherwise c". The form a ? b : c is by far and large the most common, but alternative syntaxes do exist; for example, Raku uses the syntax a ?? b !! c to avoid confusion with the infix operators ? and !, whereas in Visual Basic .NET, it instead takes the form If(a, b, c).

In computer programming, operators are constructs defined within programming languages which behave generally like functions, but which differ syntactically or semantically.

In mathematics and in computer programming, a variadic function is a function of indefinite arity, i.e., one which accepts a variable number of arguments. Support for variadic functions differs widely among programming languages.

typedef is a reserved keyword in the programming languages C, C++, and Objective-C. It is used to create an additional name (alias) for another data type, but does not create a new type, except in the obscure case of a qualified typedef of an array type where the typedef qualifiers are transferred to the array element type. As such, it is often used to simplify the syntax of declaring complex data structures consisting of struct and union types, although it is also commonly used to provide specific descriptive type names for integer data types of varying sizes.

Tacit programming, also called point-free style, is a programming paradigm in which function definitions do not identify the arguments 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. It is also the natural style of certain programming languages, including APL and its derivatives, and concatenative languages such as Forth. The lack of argument naming gives point-free style a reputation of being unnecessarily obscure, hence the epithet "pointless style".

C++11 is a version of the ISO/IEC 14882 standard for the C++ programming language. C++11 replaced the prior version of the C++ standard, called C++03, and was later replaced by C++14. The name follows the tradition of naming language versions by the publication year of the specification, though it was formerly named C++0x because it was expected to be published before 2010.

In computer programming, an anonymous function is a function definition that is not bound to an identifier. Anonymous functions are often arguments being passed to higher-order functions or used for constructing the result of a higher-order function that needs to return a function. If the function is only used once, or a limited number of times, an anonymous function may be syntactically lighter than using a named function. Anonymous functions are ubiquitous in functional programming languages and other languages with first-class functions, where they fulfil the same role for the function type as literals do for other data types.

In mathematics and computer science, apply is a function that applies a function to arguments. It is central to programming languages derived from lambda calculus, such as LISP and Scheme, and also in functional languages. It has a role in the study of the denotational semantics of computer programs, because it is a continuous function on complete partial orders. Apply is also a continuous function in homotopy theory, and, indeed underpins the entire theory: it allows a homotopy deformation to be viewed as a continuous path in the space of functions. Likewise, valid mutations (refactorings) of computer programs can be seen as those that are "continuous" in the Scott topology.

The syntax and semantics of PHP, a programming language, form a set of rules that define how a PHP program can be written and interpreted.

In computer science, partial application refers to the process of fixing a number of arguments of a function, producing another function of smaller arity. Given a function , we might fix the first argument, producing a function of type . Evaluation of this function might be represented as . Note that the result of partial function application in this case is a function that takes two arguments. Partial application is sometimes incorrectly called currying, which is a related, but distinct concept.

<span class="mw-page-title-main">LFE (programming language)</span>

Lisp Flavored Erlang (LFE) is a functional, concurrent, garbage collected, general-purpose programming language and Lisp dialect built on Core Erlang and the Erlang virtual machine (BEAM). LFE builds on Erlang to provide a Lisp syntax for writing distributed, fault-tolerant, soft real-time, non-stop applications. LFE also extends Erlang to support metaprogramming with Lisp macros and an improved developer experience with a feature-rich read–eval–print loop (REPL). LFE is actively supported on all recent releases of Erlang; the oldest version of Erlang supported is R14.

Kotlin is a cross-platform, statically typed, general-purpose high-level programming language with type inference. Kotlin is designed to interoperate fully with Java, and the JVM version of Kotlin's standard library depends on the Java Class Library, but type inference allows its syntax to be more concise. Kotlin mainly targets the JVM, but also compiles to JavaScript or native code via LLVM. Language development costs are borne by JetBrains, while the Kotlin Foundation protects the Kotlin trademark.

<span class="mw-page-title-main">Nim (programming language)</span> Programming language

Nim is a general-purpose, multi-paradigm, statically typed, compiled high-level systems programming language, designed and developed by a team around Andreas Rumpf. Nim is designed to be "efficient, expressive, and elegant", supporting metaprogramming, functional, message passing, procedural, and object-oriented programming styles by providing several features such as compile time code generation, algebraic data types, a foreign function interface (FFI) with C, C++, Objective-C, and JavaScript, and supporting compiling to those same languages as intermediate representations.

A callable object, in computer programming, is any object that can be called like a function.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.