Intensional Logic in Context – from philosophy to technology

The most pervasive fallacy of philosophic thinking goes back to neglect of context.

Jon Dewey

What exactly is “intensional programming?” The easy answer is, programming in a language based on intensional logic. But that raises another, more important question, namely what is intensional logic? Logicians have been working on the answer for more than 2500 years.

The short answer is, logic in which the truth-value and more generally the meaning of an expression depends on an implicit context. Let me attempt to give you the full answer.

The term “intensional” itself is relatively recent. Carnap introduced it in the 1930s, based on Frege’s distinction between the “sense” and the “denotation” of an expression. In Frege’s terminology the denotation of an expression is just that – the particular object it (currently) denotes. (This is what Carnap and modern logicians call the “extension”). For example, “the President of France” currently [2021] denotes Emmanuel Macron.

On the other hand the “sense” (what we now call the “intension”) is the entire concept it represents – what we, at some level, intend when we write it. No one would claim that M Macron somehow sums up the whole concept of the French presidency.

Intensional logic is therefore the logic of expressions in which the intensions must be taken into account. These are very common in natural language. The French constitution specifies that the President is directly elected; and this is not the same as specifying that M Macron be directly elected.

The mysteries of intensionality.

Many famous paradoxes are based on the observation that intensional expressions seem to violate the basic law of substitution of equals for equals.

According to the latest announcements,

The number of planets = 8

Kepler, the famous astronomer, was well aware of the basic rules of arithmetic. We can be sure that

Kepler knew that 8 is a perfect cube

But if we substitute equals for equals in this latter assertion, we get

Kepler knew that the number of planets is a perfect cube

which is almost certainly false.

In one sense, the explanation is simple: the equation relates only the extensions of the two expressions, whereas “Kepler knew …” refers to the intension of “the number of planets”. But what sort of mathematical object is an intension?

Necessity and Possibility

Aristotle, the founder of formal logic, first addressed similar problems. It is often said that Aristotle’s logic is two-valued, but this is not correct. He carefully distinguished between assertions that are true but not necessarily so, and those that are true by necessity – that could not possibly be false. Aristotle classified these different ‘modes’ of truth and falsity He tried to extend his analysis of syllogisms to include those in which assumptions and/or conclusions were not simply true, but necessarily true, or only possibly true.

Necessity is, in our terminology, an intensional operator. We cannot always determine the truth of “necessarily P” knowing only the truth (extension) of P. P may be true but not necessarily so.

The Greek Stoics and the medieval Scholastics continued the tradition. During this entire period of more than two millennia, “modal” logic (the logic of necessity and possibility) was considered to be an integral part of formal logic.

Around 1900 Frege, Cantor, and Russell completed Leibniz’ program of mechanizing logic. Set theory and the predicate calculus are entirely extensional formalisms and deal with unchanging, immortal entities encountering each other in an empty context. Extensional logic proved very successful and Russell and Wittgenstein wasted no time generalizing their approach to to a whole philosophy, logical atomism. In this philosophy knowledge – in fact reality itself – can be described as a large collection of atomic facts evaluated in isolation.

Frege was aware that something (namely intensions) had been omitted. Efforts began almost immediately to extend mathematical logic to cover intensional phenomena (as they were later called).

Lewis and Langford formalize Modal Logic

The effort to recover modal logic began soon after, in the 1930s, when CI Lewis formalized his logic of “material implication”. He quickly dropped this, however, in favor of necessity and possibility. For these he introduced the symbols ☐ and <> which have since become standard.

In Kripke semantics, propositions are not normally either true or false; they are true in some worlds and false in others. The Kripke semantics of necessity and possibility formalizes the “alternate state of affairs” idea of Scotus. A proposition of the form ☐P is true at a world w iff P is true at all worlds w’ accessible from w. Dually, a proposition of the form <>P is true at a world w iff P is true at at some world w’ accessible from w.

Once the notion of possible world/context was formalized, it was easy to find new intensional formalisms that went beyond the traditional necessity/possibility.

The most important generalization, however, was to break any remaining ties with the ancient modalities and consider operators not defined by an accessibility relation. This means giving a semantics not just to modal logic, but to intensional logic in general. Credit for this primarily goes to Dana Scott. In 1969 he laid out a complete framework for a semantics of intensional logic in his (perhaps mistitled) Advice to Modal Logicians.

In Advice  Scott takes the basic idea of Kripke models and extends it to give a framework in which Carnap’s distinction between intension and extension can be formalized. In a “Scott model” we have a nonempty set I of reference points (essentially, possible worlds) but do not require that any accessibility relations be specified. Whatever the syntactic details of our language, propositions are not a priori absolutely true or false Their truth value varies from world to world; although they may happen to have the same value at each world. Scott calls the truth value of φ at a particular world the extension of φ at that world. The intension of φ, on the other hand, he takes to be the function that maps each world w to the extension of φ at w. In other words, the intension of a formula is an element of 2^I, 2 being the set {0,1}  of truth values.

In Scott’s approach, a (unary) intensional operator is simply a function that maps 2^I to 2^I. It may be defined in terms of an accessibility relation, but the framework allows for more general kinds of operators. As an example, he proposes a formalization of the present progressive tense (as in “I am eating”). He takes I to be the reals and defines [H]E to be true at time t iff E is true in some interval (however small) containing t.

Scott models are not restricted to propositional logics. They can also specify a collection D of 

individuals that serve as the extensions of terms. These individuals can be (understood to be) numbers, strings and lists, physical objects, people, organizations, etc. However intensional individuals denote elements of D^I — they may have different extensions at different worlds. The D^I are intensional objects elements or virtual individuals. They correspond to natural language phrases such as “the President of France” and Scott models can give us a clear explanation of the puzzles described at the beginning of this article.

For Scott an important challenge was dealing with intensional individuals that don’t exist at certain worlds. This has not proved (so far) to be a problem for intensional programming. For example, we assume the string “Hello World” is always available.

time x space x space -> floatingpoints

The Creation of Intensional Programming

This is not the place to present even a brief overview of work in intensional programming. However, We can explain the connection by presenting a Creation Myth that makes the connection clear (and also puts its creators in a more favorable light). According to the Myth, far sighted Computer Science researchers read and understood Advice and decided to use it prescriptively, as the basis for new programming languages and systems. The first language was Lucid,invented by the author and E. A. Ashcroft in 1974. (Now you know who the far sighted researchers were. However the Myth does not explain why they waited five years.)

The Creators chose (a family of) Scott models in which I is the set of natural numbers, interpreted as timepoints. For the individuals, they took (in the simplest case) D to be the set of integers. Their language included the operators first, next and fby, with next (for example) the intensional operator

from D^I → D^I such that



next(X) = λn X(n+1)

Programs consisted of equations defining program variables in terms of constants and each other. 

Program variables were therefore intensional integers.

At this point the Myth has the Creators look at what they had done, and see that it was Good (a few referee reports aside). They return for more Advice and found it; for example,

This situation is easily appreciated where I is the context of time-dependent statements; that is in the case where I represents the instants of time. For more general situations one must not think of the elements of I as anything as simple as instants of time or even possible worlds. In general we will have i= (w,t,p,a) where the index i has coordinates; for example w is a world, t is a time, p = (x, y, z) is a (3-dimensional) position in the world, a is an agent, etc. All these coordinates can be varied, possibly independently, and thus affect the truth of statements which have indirect references to these coordinates.

Intensional programming also used multiple dimensions almost from the beginning. It took a long time, however to realize that it was not enough to have (even a large) set of fixed predefined dimensions; or even an infinite, indexed collection of predefined dimensions. Eventually, the GLU system allowed user-declarable local dimensions.