2.1. Function

The term “function” has a multilateral spectrum of meanings. In mathematics it refers to “an expression which contains a variable term and whose meaning or truth is determined when concrete values of the variable are specified” (Merriam–Webster, 2002). In sociology, function is defined as “an individual or an organizational unit performing a group of related acts and processes” (Merriam–Webster, 2002). In software engineering, function refers to a part of the requirements that “specify the software functionality that the developers must build into the product to enable users to accomplish their tasks” (Wiegers, 2003). In engineering design, function is defined as “an activity by which a thing fulfills its purpose” (Oxford University Press, 2003). In AI, function is usually mentioned along with the terms behavior, goal, and purpose with respect to system's inner and outer environments (Simon, 1969). In addition, it has strong connections with the notion of making efforts to obtain a certain result (mainly in engineering design), a certain future event (Bigelow & Pargetter, 1987), or to the notion of something good (e.g., survival in natural system or efficiency for designed artifacts; Sorabji, 1964).

Typical definitions of function in engineering design are: function as intended behavior and function as purpose (Chakrabarti, 1998) and typical viewpoints are objective and subjective viewpoints. The following are a few common definitions:

In the objective viewpoint of function, a goal describes some outcome toward which certain activities of a system or of its components are directed. It is argued that the goal and function can be used interchangeably, depending on the way of viewing the system (or a part of it) and where to put the boundary. Looking at the system externally, the effect will be regarded as a functional ascription. However, from the perspective of the system itself, it can be considered as a goal that guides the organization of resources internal to the system (Lind, 1988). Some have differentiated between the goal and function concepts, arguing that although sometimes the end product of a goal directed processes is a function, it is not necessarily so (Nagel, 1977a), and even the function may be different from the achievement of goals (Wright, 1973).

In the subjective viewpoint of function, the function of a system is addressed with reference to the external intention of humans. The term intention is usually used in the narrow sense of a kind of plan that includes a structural and behavioral representation of a system and its future effects. In this sense, function and behavior of a system are closely related.

In some works, functions are classified as: conscious functions, that is, functions with respect to a conscious designer or creator; and natural functions, that is, functions build naturally into a system (see Section 3.1). Some schools of thoughts have argued against such distinction. For instance, evolutionary Darwinism has denied entities having natural function.

2.2. FR

FR is a collective term for a variety of theories and techniques that enable people to explain the presence and function of artifacts in a containing system; to derive the purpose of the artifact, and to explain how the function can be achieved. FR is sometimes called functional analysis (FA; mainly in sociology and engineering design) or functional explanation (FE; mainly in biology). The ultimate goal of FR is enhancing the commonsense reasoning with the functional ability.

FR as a commonsense theory usually consists of three parts:

1. Ontology describing the domain and the entities in the domain;
2. Representation scheme for modeling the entities and their interactions;
3. Reasoning method for inferring and explaining how the entities function.

Three typical definitions of FR in engineering design are the following:

2.3. FR-based system

An FR-based system is an implementation of one or more FR theories in a computer program. A typical FR-based system incorporates the following:

1. Representational mechanisms of function and/or goal (purpose) concepts. For example, a database of artifacts and their functions.
2. Description mechanisms of state, structure, or behavior. For example, a modeling and model-based simulation tool.
3. Inference (i.e., explanation and reasoning) mechanisms to derive and explain functions based on an FR theory.
4. Presentation mechanisms. For example, a graphical user interface.

3.1. FR in biology and sociology

FE is extensively used in biology, sociology and engineering design. (Some works seek to unify the explanation of function in biology, sociology, and engineering design, such as Beckner, 1969.) Originally, FR theories were devoted to explain the presence of entities in a containing system (Hempel, 1959; Cummins, 1974; Nagel, 1977a, 1977b). The containing system is a living organism, an organization, or a designed artifact. In biology, FR tries to answer questions, such as “why does a giraffe have a long neck?” and tries to discover the function of an organ in an organism, such as the function of the heart in the human body. These are usually called natural functions.

In sociology, FR is used to explore the necessary conditions of existence of a social system and in a structural–functional approach that employs the concept of function as a link between relatively stable structural categories. FR research in sociology is governed by Malinkowski's principle: “All social phenomena have beneficial consequences (intended or unintended, recognized or unrecognized) that explains them” and a weaker version of this principle was mentioned by Merton: “Whenever social phenomena have consequences that are beneficial, unintended and unrecognized, they can also be explained by these consequences.” (Elster, 1983). Some researchers have argued against the use of FR in sociology in the very same way as one explains the biological phenomenon. The reason is that in biology the optimal consequence is much stronger than the beneficial consequence in sociology.

Plato and Aristotole were among the earliest philosophers talking about functions. Plato described the function of an item conferring to some good. This idea still exists in some works such as Sorabji's natural functions connected with the notion of something good (Sorabji, 1964), or Canfield's explaining function by its usefulness to the containing system (Canfield, 1964). Later, philosophers from Spinoza to those of the late nineteenth century were engaged with explaining the design into nature using teleological notions of means and ends (Allan, 1952).

Among the recent works, apart from the Beckner's theory of FE using positive and negative evidences (Beckner, 1969), the rest of the FR theories are either derivations or reformulations of the works by Hempel and Nagel (Hempel, 1959; Nagel, 1977b). Among the followers are Lehman (1965), Ayala (1970), and Ruse (1971).

Hempel (1959) provided an analysis of functional ascription in terms of sufficient conditions. In contrast, Nagel (1977b) tried to specify the necessary conditions. These two attempts were somehow problematic in scientific terms. As Cummins (1974) mentioned, “Any analysis in terms of sufficient conditions may lead to a schema with true premises but invalid, and any formulation specifying necessary conditions may yield to a valid but unsound explanation.”

Two other works are worthy of mention: Wright's etiological theory (1973, 1976), and Cummins' (1974) functional ascription. In Wright's etiological theory of function the unification of functional and causal explanations is the central idea (Wright, 1973, 1976). According to this theory the function of an entity is explainable in terms of its history, not its present behavior. For instance, when etiologists define the function of the kidneys in human body, they would take how it is evolved to function and ignore what it does at present. Therefore, it is possible to make distinction between success by function and success by accident. The genetic algorithm is considered as a computational model for etiological theory of function.

Cummins (1975) argued against the validity of the underlying assumptions of traditional FEs and suggested an alternative scheme: functional ascription to an item is ascribing a capacity to the item that can be recognized by its role in an analysis of some capacity of a containing system. These theories are reviewed in Section 5.

3.2. FR techniques in engineering design

In engineering design, there is an implicit assumption that even the most fanciful assemblies (e.g., buildings, devices, hardware, and software) have practical functions to fulfill. The structure–behavior–function framework is considered as one of the dominant methods for analysis of engineering artifacts. Cases such as function of physical components (e.g., a pedal) in a designed artifact (e.g., a bicycle) are discussed and functional decomposition is a popular method for designing real (e.g., an electric power plant) and virtual (e.g., software) artifacts.

Although software system designers developed the concept of functional decomposition and structural analysis in the 1960s, the idea of using functional concept in engineering design, the AI way, was first mentioned by Herbert Simon with respect to system's inner and outer environment (Simon, 1969). The idea was later presented by Freeman and Newell (1971). Recent advances in AI, computation theories, and distributed systems have led to new interpretation and implementation of the FR theories in programs. In typical systems, the initially given data consists of artifacts (objects, processes, or mechanisms), and a formal or semiformal description of their physical structure, behavior or functions. The outcome is describing and explaining the function of an artifact in terms of the structure or behavior of its components and their functions. These are mainly inspired by the Beckner's theory (1969; first-generation FR systems), Cummins' (1974) analytical explanation and the capacity concept, Nagel's causal/FE of goal-directed processes (1977a; second-generation systems) and Canfield's usability concept (1964; modern FR systems). There is also a shift of attention from justification of the theory to practical implementations. (See Section 5 for details of the FR theories.)

FR-based systems in engineering design can be classified in three groups:

• Planning and design approaches: a method for design verification (Murakami & Nakajima, 1988); a method for capturing qualitative design knowledge (Pu & Badler, 1988); a method for hierarchical design using functional knowledge (Acar & Ozguner, 1990); a design evaluation using functional knowledge (Bradshaw & Young, 1991); a scheme for FR in conceptual design (Chakrabarti & Bligh, 2001); and a function and behavior representation in conceptual mechanical design (Deng, 2002).
• Conceptualization approaches: scripts, plans, goals, and understanding (Shank & Abelson, 1977); a method for functional representation and compilation (Sembugamoorthy & Chandrasekaran, 1986); a functional representation through consolidation (Bylander, 1988); a representation and planning method (Tezza & Trucco, 1988); temporal and cohesive clustering of functional knowledge (Shekar, 1990); a functional representation of mechanical devices (Keuneke, 1991); a qualitative function formation technique (Far, 1999); a scheme for FR in conceptual design (Chakrabarti & Bligh, 2001); and a function and behavior representation in conceptual mechanical design (Deng, 2002).
• Explanation-based approaches: an explanation-based method for electronic circuits (DeKleer & Brown, 1984); explanation-based methods for fault diagnosis (Fink, 1985; Fink & Lusth, 1987); explanation-based methods for higher order mechanical devices (Faltings, 1987, 1990); an explanation of serial assemblies (Dormoy & Raiman, 1988); an explanation-based method for mechanical devices (Joskowicz & Addanki, 1988); an explanation-based method for fault diagnosis using hierarchical knowledge (Abu-Hanna et al., 1991); teleological descriptions for designed artifacts (Franke, 1991); FR in failure modes and effect analysis (Russumanno & Bonnell, 1996); and a qualitative function formation technique (Far, 1999).

Planning and design approaches (sometimes called CAD approaches) take advantage of the representational FR theories. In this case, a representation of a functional concept exists prior to any realization of the object having such a function, and such a representation contributes to the process of bringing that object into being (Bigelow & Pargetter, 1987). Planning problem is devising a plan that can achieve some functions while satisfying some constraints. Planning approaches have a finite set of symbols, standing for activities, and a finite set of rules showing the possible interactions between activities. The problems considered are composition, decomposition, and verification of the plan. Design problem is devising a device that can achieve some functions while satisfying some constraints. Design approaches have a finite set of symbols, standing for components, and a finite set of rules showing the possible interactions among components. The problems considered are composition, decomposition, and verification of the design. A common limitation of planning and design approaches is that they can only deal with the entities falling within their defined symbol set. Although being good and efficient, they can at most support the user through providing a more abstract (i.e., higher level) planning (or design) environment, more useful than detailed planning (or geometric design), leading to an increase of the quality and efficiency of planning (or design) task.

Conceptualization approaches suggest a hierarchical classification scheme for the functional concepts, define classes objectively, and aggregate objects into classes. The class types are defined by functional primitives. The necessity and sufficiency of the primitives, and whether they are appropriate for functional representation in terms of means–ends hierarchy (Rasmussen, 1985, 1990) is somehow doubtful. A main problem is that almost all of the methods try to define the primitives objectively: assign meaning to the behavior of the objects at the first place, and then recover it as a function.

In explanation-based approaches traces of qualitative reasoning in explaining function of artifacts in pioneer FR systems can be found along with the three major theories of qualitative physics, that is, the qualitative process theory (Forbus, 1984) influenced deriving function for mechanical devices (see Faltings, 1990; Kara & Stahovich, 2002), qualitative confluence theory (DeKleer & Brown, 1984) has influenced explanation of function of electronic circuits (see DeKleer, 1984) and qualitative simulation (Kuipers, 1986) has led to explaining function of designed artifacts (see Franke, 1991). There exists an analogy between the explanation-based FR systems and explanation-based learning (EBL) techniques (Ellman, 1989). The above three FR methods each resemble a kind of EBL using either chunking or generalization.

3.2.1. First-generation FR-based systems: Direct match

The first-generation systems using functional knowledge start with either a semiformal description of physical structure (design verification approaches) or a description of shape (conceptualization approaches). In addition, systems starting with natural language instructions have been reported (Asai et al., 1990). Figure 1 shows the basic building blocks of the first-generation systems. They process input data and relate it to a functional concept that has already been recorded in the database. The functions in the database can either be rigid symbolic names for a property of a given artifact, or include some attributes filled by the data measured or interpreted from the real world. Being good as they are, none of those first-generation systems can assign several functions to an artifact or provide solution to all of the FR problems (see Section 4). The main drawback of the first-generation systems is the restricted view of the direct list matching inferences. All the artifact and functions are identified in advance, and the essence is recorded in one or more of the three-structure function databases.

First-generation functional reasoning systems.

4.1. Informal description

Traditionally, biology, engineering design, and AI are considered as FR problems.

4.2. Classification of FR problems

FR problems can be classified into four groups: identification, explanation, selection, and verification problems (see Fig. 2).

Functional reasoning problems.

5.1. Allan's theory

Allan (1952) states the following:

This is the intuitive form of functional ascription in terms of “means” (i.e., x) and “ends” (i.e., y), but not of much use in terms of validity and expressive power. The difficulty is that the above two conditions (a) and (b) do not represent a one–one mapping from the means to the ends sets. There might occur (not occur) many things other than y when x occurs (not occurs), and which one is the “end” for x is not clear. Revised versions of this theory are suggested below.

5.2. Beckner's theory

Beckner (1969) states the following: “The component c ∈ C has function f ∈ F in a system S if there is a set of circumstances in which f occurs when S has c, and f does not occur when S does not have c,” where C is a set of components (c), S is a set of components comprising the system (S ⊂ C), and F is a set of functions of the components (f).

This can be formulated logically as

where V is a possible situation (in a logical sense) and FUNCTION and HAS are logical predicates.

A main criticism of this theory is that expression (2) cannot be easily verified. There might be situations (∃V) that (HAS(S,c); FALSE) but (FUNCTION (f,c): TRUE); and if limiting S = C, ∀V, (HAS(S,c): TRUE). Therefore, it is not necessary for S to have c to occur f. For instance, if the function of heart is to circulate blood in the body, it can be realized also without heart, may be using an artificial pump.

Beckner's (1969) theory is built based on the assumption that the function is a property of its host system, and the interactions with the external world are lumped together in the “circumstances.” Therefore, it is difficult to use this theory to explain the function of a component other than its most frequent one. Furthermore, it cannot be used in situations when an arrangement of components is exhibiting a single function.

From the engineering implementation point of view, each component must be related to at least a function concept in the database, and each function concept has to be related to several components. Such data structures can be represented using a relational database, and would be manageable even when the number of components and associated functions grow. The only problem is that when generating FEs, every component–function pair must be associated with a list of conditions under which the component can exhibit the given function. The list may be incomplete (that is, conditions are not sufficiently specified) or become extensive (that is, too many conditions are given). Theoretically, this list can grow beyond control (what is usually called a “frame problem” in theoretical AI). Most of the first-generation FR-based systems implicitly have Beckner's (1969) theory as their underlying theory (see Section 3.2.1).

5.3. Canfield's theory

Canfield's (1964) theory states the following: “A function of the component c in system S is f means that c does f, and that f is useful to S.”

This can be formulated logically as

where C is a set of components (c); S is a set of components comprising the system (s ⊂ C); F is a set of functions of the components (f); V is a possible situation (in a logical sense); and FUNCTION, HAS, and USEFUL are logical predicates.

It is argued that this theory is difficult to apply to explain functions of designed artifacts, mainly due to difficulties in identifying the system S. In addition, meeting (3) and (4) is neither necessary nor sufficient for something to be a function (Wright, 1973). It is not necessary because artifacts may be “designed” to have a certain function, even if they might be useless to a particular user. There might be some cases where c is designed to do f but cannot do it, except under certain circumstances (e.g., the function of a door knob is to maintain the door closed, but in case of fault this cannot be manifested). It is not sufficient because c might do some other useful things also, which is not considered as its function. Canfield (1964) also believes that a function is a property of its host system.

From an engineering implementation point of view, besides those problems mentioned for Beckner's (1969) theory, verifying whether c can do f may be straightforward (i.e., through using simulation and causal reasoning), but verifying its “usefulness” to S is not trivial. For each association between a component and a function in the database, the enabling conditions and an additional usefulness attribute (which may depend on the enabling condition) must be specified. Some of the modern FR-based systems with usability concerns use Canfield's (1964) theory as their underlying theory (see Section 3.2.3).

5.4. Wright's theory

Wright (1973, 1976) argues that explaining “natural” and “conscious” functions should follow the same pattern. In his etiological theory, the functional and causal explanations are considered together: a functional statement “function of the component c in system S is f ” is equivalent to asserting “component c in system S in order to do f .” In other words, the function of c in S is f if and only if

1. f is a consequence of c's presence in S and
2. the component c is in S because f is a consequence of c's presence in S.

The first statement addresses that f is a causal consequence of c, and the second statement indicates the component c is selected in S for the sake of f, that is, “why the component c is present in S.”

One of the benefits of this theory is the ability to make distinction between success by function and success by accident (Wright, 1973; Millikan, 1989). In biological systems statement 2 can be evaluated with reference to natural selection. Many theorists who adopted Wright's (1973, 1976) theory have also extended it by introducing natural selection into their definitions (Walsh, 1996).

There are critics to this theory. First, it may not be possible to derive f as a causal consequence of c (at least for some biological systems whose causal mechanisms are not fully explored); and second, being in S may not be because f is a consequence of c, but because of a “belief” that it is so (Nagel, 1977a, 1977b) and the belief is a subjective external assertion not a genuine property of the system itself.

Matthen has extended Wright's (1973, 1976) theory by introducing a functional structure among the functions via utilizing a set of facts (model) used to subordinate one function to another as means to ends (Matthen, 1988).

Wright's (1973, 1976) theory is nevertheless an important FR theory in terms of binding causal and FA and paving the way for a model-based approach to FR.

5.5. Hempel and Nagel's theories

Hempel's (1959) formulation of FE is the following:

The explanation has the following pattern:

1. During period T in environment V, the system S is in proper working order.
2. If the system S is in proper working order, condition n must be satisfied.
3. If component c is present in S, then the effect of component c's presence in S satisfies the condition n.

Hempel (1959) explains his theory along with an example: “The heartbeat in vertebrates has the function of circulating blood through the organism.” Heartbeats may bring about other things like heart sound that does not serve for survival of the organism, and thus not considered as its function. In other words, what a component contributes to a system needs to serve for some good (e.g., survival in biological systems) to the system to be considered as a function. In addition, the heartbeat serves for survival of the organism only if many other conditions for proper working of the system are met such as that there are no ruptures of the aorta, that there is enough oxygen in the environment in which the organism is located, and so forth.

Hempel (1959) pointed out that there are some problems with formulating FEs in accordance with his model, such as the functional equivalence problem, stating that what can be explained by FE is not that there is a component in a certain system at a certain time, but that there are at least one of some functionally equivalent components in a certain system at a certain time. According to his example, a FE “The heartbeat in vertebrates has the function of circulating blood through the organism” in fact explains the presence of (at least) one of functional alternatives in vertebrates that serve to circulate blood, not the presence of heart in vertebrates. In other words, this formulation is not logically sound. Statement 3 is not a necessary condition (although it is sufficient) for the performance of function. There may be some other components exhibiting the same function; therefore, the presence of c in S cannot be explained.

Nagel (1977a, 1977b) argued for changing statement 3 to a necessary condition “if and only if component c is present in S.” Nagel's formulation of FE is the following:

1. During period T the system S is in environment V.
2. During period T and in stated circumstances, the system S does f.
3. If during period T the system S is in environment V, then if S performs f the component c is present in f.

Statement 6 indicates a necessary condition for performing f. Once again, a basic critique is that although the explanation is logically sound it may not be valid any more in certain cases, such as redundant components exhibiting a shared function, for example, two file servers used redundantly in a computer system.

These two theories each specify either necessary or sufficient conditions for functioning components. However, the above discussion suggest that what is often called functionalism is best viewed, not as a body of doctrine or theory advancing tremendously general principles such as the principle of universal functionalism, but rather as a program for research guided by certain heuristic maxims or “working hypotheses” (Hempel, 1959). In other words, FEs are useful to show scientists a course of their researches and help them discover new relationships between phenomena, but they have hardly any worth in terms of scientific explanation and prediction.

From practical applicability point of view, a one–one relation between a component and a functional concept is necessary. If such a database can be developed, the theory can be successfully used to explain functions of various components.

5.6. Cummins' theory

The basic assumptions in the conventional interpretation of functional ascription to objects are the following (Cummins, 1974):

1. The main purpose of functional characterization in commonsense world is to explain the “presence” of components that are functionally characterized.
2. The component is said to perform its function with respect to a containing system (or another component), if it affects the containing system (or another component) in the sense of either contributing to the performance of some activity of, or the maintenance of some condition in that containing system (or another component).

Cummins (1974) argues against those assumptions, and suggests an alternative FR scheme: functional ascription to an object is ascribing a “capacity” (or disposition) to the component that can be recognized by its role in an analysis of some capacity of a containing system. He believes that functional statements are actually disposition statements, and FE is actually explaining such dispositions:

If a function of component c in system S is f, then c has a disposition to f in S. To attribute a disposition d to a component c is to assert that the behavior of c is subject to (exhibits or would exhibit) a certain lawlike regularity…. To say that c has d is to say that c would manifest d were any of a certain range of events to occur.

In Cummins' (1974, 1975) theory, the capacity of a containing system is explained analytically by decomposing it into a number of other capacities and an analytical explanation of the capacities will lead to the function: If those capacities can be explained in terms of some general laws and together amount to the analyzed capacity, then each individual capacity can be interpreted as a function.

Cummins's (1974, 1975) theory is the foundation of the model-based approach to FR, common in AI. Subsumption is the basis of structuring taxonomy; it can be viewed as a class hierarchy connecting concepts using “is-a” relations. The idea of subsumption and analytical explanation of capacities (dispositions) is used implicitly in many FR-based systems in planning, resource allocation, and explanation-based systems that use multilayer concepts for behavior and function.