I've seen two different concepts referred to by the term "function":

  • A small part of a program specified by the composition of constants and other functions as paramaters, such as the "functions" in Lisp
  • A set of tuples, as referred to in formal logic, which is not necessarily computable

The first concept is very fundamental to software design. The second concept is very fundamental to formal reasoning. However, a task I've been working on is analyzing software with formal logic, so the conflation of the terms is a bother.

Is there any agreed upon, concise, unambiguous terminology to distinguish these two ideas? I can think of several verbose terms, such as "Computable Function" and "General Function", but imagine having to type that out with the specification of every modular component.

Any references, ideas, or supported opinions are appreciated, thanks.


A (mathematical) function $f$ with domain $X$ and range $Y$ is a set of pairs $(x,y) \in X \times Y$ such that for each $x \in X$ there is exactly one pair of the form $(x,y)$; we say that $f(x) = y$.

A computable function $f$ is a function computed by some program.

A function in a programming language is an entity whose exact definition depends on the programming language. For example, in Pascal a function is a subroutine returning a value, in C a function is any subroutine, and in functional languages a function is either a declared subroutine or an "anonymous" function arising as some lambda expression.

Summarizing, the meaning of function depends on context. In a mathematical context or in some parts of theoretical computer science (say, complexity theory), a function is an arbitrary mapping; this is also probably the case in programming language theory, but I'm not qualified to say. In software engineering the meaning might depend on context. Computable functions (also known as recursive functions) are always called that.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.