The Many Functions of Functor

Posted on October 22, 2014

Although I became most familiar with the word through exposure to Category Theory, I knew that “functor” had at least a couple of other meanings in other contexts. I’d looked up its history before, but neglected to write it down. Now I won’t have to do it again!

The Players: Carnap, Quine, Tarski

According to a number of sources, “functor” entered the lexicon via the work of Rudolf Carnap. Carnap studied philosophy, physics, and mathematics at university, including several courses in mathematics and logic from Gottlob Frege. He later studied the theory of relativity at Berlin, where Einstein was professor of physics.

His dissertation concerned an axiomatic system for space-time theory, which was written from a philosophical point of view. Thereafter he became involved with the Vienna Circle of philosophers and ended up as a leading member. This group advanced the philosophy of logical positivism and was deeply concerned with the philosophy and practice of science.

In 1929, Carnap met Alfred Tarski, a Polish logician from the Lvov-Warsaw school of philosophy who was developing a logical basis for the meaning of truth. A few years later, he moved to Prague to become a professor and wrote the 1934 book The Logical Syntax of Language, which contains (as far as I am aware) the first use of “functor”. I will return to the book in a moment, after making a few more of Carnap’s connections apparent.

In Prague, Carnap met the philosophers Willard van Orman Quine and Charles Morris. When World War II broke out, they helped Carnap escape to the United States, where he remained. Tarski escaped Poland to the USA as well, and the trio of Carnap, Quine, and Tarski were thus able to meet (along with other leading philosophers and logicians) for a year at Harvard to work on the leading issues of analytical philosophy.

Carnap’s Logical Syntax of Language

As part of his desire to put the practice of science on firm logical ground, Carnap wanted to have an appropriate understanding of language that could be used to properly express scientific truths. Logical Syntax creates a formal system, a meta-language, with which to reason about constructs of natural language.

The meta-language defines syntactic constructs belonging to four categories:

  1. A fixed set of 11 symbols
  2. (Numerical) variables
  3. Constant numerals
  4. Predicates
  5. Functors

The point was to remove ambiguity of names and to add precision by designating things numerically as much as possible.

Basic forms

Designation of things was done positionally by numerical coordinates rather than by symbolic name. Positional numerals were defined inductively from 0 designating the initial position and primes marking successive positions. The traditional Arabic numerals were introduced as shorthand, as well as the possibility of tupling numbers to represent higher-dimensional positions.

Expressing properties of things was done via predicates over positions. These could express direct properties of things or relationships between things, but in a symbolic manner via the name-form of the predicate.

In order to represent properties numerically, the idea of functor was introduced. Functors were similar in form to predicates, in that they had a name-form and took numeric arguments, but instead of representing facts and/or relations they represented another numeric value.

Expressions

Valid combinations of the basic forms create expressions. Two important kinds of expressions were “sentences” and “numerical expressions.”

Sentences express logical truth value, so the expression of a predicate form is a sentence. Some of the symbols are combining forms that create sentences as well, such as equations.

Expressions of functors, on the other hand, are always numerical expressions. Numeric expression was very important to Carnap for the precise transmission of scientific detail, so he valued this precision of functor expression over the more “vague” relative or symbolic nature of predicate expressions.

Although Carnap’s concept of functor seems similar to that of a mathematical function, it is actually quite different. Functions are always a fixed relation between numbers, but functors may represent numerical observations of the world as well, such as the example given early on of the temperature-functor that has the numeric value of the temperature of its argument.

Connection to Category Theory

Saunders Mac Lane, one of the founders of Category Theory, was an associate of Carnap’s at the University of Chicago and was given the English translation of Logical Syntax of Language in 1938 for review. He was not particularly interested in the philosophical aspects of Carnap’s usage of “functor”, but in it he saw a perfect candidate to resolve a similar notational dilemma in Category Theory.

So, the Category Theory notion of “functor” is related to Carnap’s original usage by similarity of role, as a stand-in for something “function-like” in some aspect, rather than being related by definition or usage. Steve Awodey, an associate of Mac Lane’s and a category theorist himself, remarked that the word “functor” may end up being “Carnap’s most far-reaching contribution to modern mathematics.”

Quine’s Predicate-Functor Logic

Quine, Tarski, and Carnap conversed about Carnap’s logical syntax while they were together at Harvard, and it seems to have influenced Quine’s thinking about logic. He certainly adopted the term “functor”, though he expanded its meaning. Quine thought that Carnap’s connective symbols, e.g. the equality symbol that generates equations, should be replaced by more general operators that construct sentences via composition.

Quine later referred to these operators as “predicate-functors” (possibly following Carnap’s convention of naming a sort of functor by its domain, e.g. “temperature-functor”) and developed an algebraic logic based around them.

He later gave a more general definition to the term “functor” itself, encompassing this new role as a generator of sentences rather than a numeric relation. It should also be noted that while Carnap was concerned with discussing language in general, including natural language, Quine was primarily interested in formal logic systems. In particular, his Predicate Functor Logic was an alternative to Combinatory Logic that avoided higher-order functions and the resulting encroachment of set theory into the system, which he viewed as outside the scope of logic.

Categorical Grammar

Tarski’s early career was influenced by his thesis advisor Stanislaw Lesniewski and also by the other prominent Lvov-Warsaw philospher Kazimierz Ajdukiewicz. Lesniewski worked in the field of ontology and was particularly interested in semantic categories; this use of “category” is due to Husserl and can be traced back to Aristotle.

Ajdukiewicz applied the notion of categories to the syntax of language to create the field of categorical grammar. The syntactic structure was thought to determine the semantic meaning in reasonable languages, thus the borrowed categorical terminology.

Syntactic categories are an equivalence class of expressions such that a sentence containing one of these sentences remains a sentence when it is substituted for any other expression that is a member of the same category. As such, syntactic categories are essentially the same as the types of Russell.

There are two kinds of categories; basic categories, which are enumerated in the definition of the language, and all others are complex (derived) categories. Expressions in complex categories are created by combining other expressions via a special kind of “functor” expression. These other expressions are called “arguments” to the functor, and the new compound expression is the functor’s “value”.

Although Ajdukiewicz’s early work on syntactic categories predated Logical Syntax of Language, it seems likely that the field of Categorical Grammar was influenced both directly via the text, which shared similar goals, and probably also via the influence of Tarski and Quine who made use of it (if not for precisely the same purposes) in their own work.

Categorical Grammar is primarily concerned with matters of natural language, but Joachim Lambek’s work on the Lambek Calculus drew it somewhat back towards mathematics and logic. Lambek Calculus resembles in some ways Alonzo Church’s Lambda Calculus (of the simply typed variety), Quine’s Functor Predicate Logic, and combinatory logic.

Of parenthetical interest is the fact that the logicians of the Lvov-Warsaw school preferred to place their functors at the front of their arguments; by this practice they allowed expressions to be unambiguous without parentheses. This practice became known as “Polish Notation”, which is familiar to many users of Hewlett Packard calculators by way of its similarly bracketless Reverse Polish Notation.

Functors in Programming

The use of functor via its Category Theory interpretation is familiar to many functional programmers today. It has a direct, though not all-encompassing, presence in Haskell via the Functor type class. Perhaps not quite so familiar is the linguistic interpretation as used by Prolog. And the SML Module language uses the term functor; although this can be interpreted in the categorical sense, it also makes sense from the perspective of Quine’s Predicate Functor Logic. C++’s use of functor to mean “function-like object” seems to be another repurposing of the word along the lines of Mac Lane’s.