La théorie des ensembles consiste à regrouper des objets (les éléments) dans des collections (les ensembles d’objets). Par exemple si on veut regrouper les éléments a et b :

on peut mettre une enveloppe (« patatoïde ») autour des 2 éléments :

Mais la paire obtenue n’est pas un couple, puisque d’une part on ne peut distinguer les rôles de a et b, d’autre part si a = b, on n’obtiendra qu’un singleton alors qu’un couple doit vraiment avoir deux élements (le premier élément, et le deuxième élément).

Envelopper séparément a et b ne résout pas le problème :

En effet cela produit 2 singletons (ensembles à un seul élément chacun, et si a = b on n’aura qu’un seul singleton, avec de surcroît l’absence d’ordre entre les singletons.

Voici une autre manière d’emballer qui permet un vrai accouplement et pas seulement un appariement :

Tout d’abord, les couples (a,b) et (b,a) sont bel et bien différents l’un de l’autre :

(a,b)	(b,a)

Ensuite, le couple (a,a) peut être modélisé par cette technique :

Chez Alfred North Whitehead et Bertrand Russel, la théorie des ensembles permet de construire les entiers :

L’ensemble vide modélise l’entier 0 :

1. En emballant 0 on obtient 1 :

   

2. En emballant 0 et 1 on obtient 2 :

   

3. En emballant 0, 1 et 2 on obtient 3 :

   

La construction des entiers naturels par des ensembles remonte à Von Neumann.

Une algèbre de Boole, comme son nom l’indique, est munie d’une addition (notée +) et d’une multiplication (notée ×). Mais il est possible d’y définir aussi une relation d’ordre, comme le constata George Boole en 1847 : Dans le chapitre XI des lois de la pensée, il propose de dire que a≤b lorsqu’il existe c tel que a=b×c [1].

On connaît un tel c vérifiant a=b×c : c’est a lui-même. La définition moderne de l’inégalité dans une algèbre de Boole est

a ≤ b si et seulement si a×b=a

Cette relation d’ordre n’est pas totale : il n’est pas certain, si on choisit au hasard deux éléments a et b d’une algèbre de Boole, que a≤b ou b≤a. Par contre, dans l’algèbre de Boole à deux éléments (appelée ici « l’algèbre de Boole » par opposition à « une algèbre de Boole »), on a

• 0≤0
• 0≤1
• 1≤1

mais pas 1≤0 : la relation d’ordre est alors totale.

Dans son article cité ci-dessous, Kuratowski transporte cette relation d’ordre sur le couple (a,b) en modélisant ce couple par une fonction f vérifiant f(0)=a et f(1)=b.

Cela revient à modéliser le couple a→b par le diagramme sagittal

0→a
1→b

Comme on a 0≤1, la relation d’ordre entre 0 et 1 se transmet à a et b, donnant la relation d’ordre a≤b. Dans le langage moderne des catégories et foncteurs (voir la partie sur les monades) on peut dire que si l’algèbre de Boole 0→1 est une catégorie, alors la fonction étudiée par Kuratowski est un foncteur vers la catégorie à deux élements a→b.

Le couple (a,a) peut alors être construit par la fonction constante

0→a
1→a

Et les couples (a,b) et (b,a) sont effectivement différents :

On verra plus bas que c’est de cette manière (avec 0 et 1 vus comme adresses mémoire) que les couples sont implémentés dans les ordinateurs. La même idée est reprise dans le λ-calcul.

Mais cette définition n’est pas, on le verra plus bas, celle adoptée par Kuratowski : elle est circulaire car pour définir une fonction, on doit avoir déjà la notion de couple.

Cantor et Frege proposaient de modéliser le couple (a,b) comme ensemble des relations R telles que aRb. Cette définition est circulaire car une relation est un ensemble de couples.

En 1914, Felix Hausdorff propose cette modélisation du couple (a,b) :

La ressemblance avec l’idée initiale de Kuratowski (voir la partie sur l’algèbre de Boole) cache le fait que cette définition ne fonctionne pas si a=0 ou b=1.

À la même époque, Norbert Wiener propose cette autre modélisation :

L’idée est de séparer a et b par des emballages différents. Cette définition est correcte, mais on a vu ci-dessus qu’il y a plus simple (moins de papier d’emballage nécessaire).

En 1921, Casimir Kuratowski s’intéresse, comme on l’a déjà vu dans la partie sur l’algèbre de Boole, à l’idée de définir un couple comme un ensemble muni d’une relation d’ordre :

On constate que Kuratowski utilise l’expression paire ordonnée plutôt que le mot couple et la notation des parenthèses pour désigner les ensembles et pas les n-uplets. Voici son modèle pour le couple (a,b) :

Il est très proche du modèle de Tarski-Grothendieck, à part que a est suremballé. Ce souci constant de mettre les éléments a et b au même niveau est dû à la crainte (chez Wiener comme chez Kuratowski) du paradoxe de Russel.

Pourquoi Kuratowski a-t-il abandonné la définition un couple est un ensemble ordonné au profit de cette construction ? Parce que là encore, la définition est circulaire, la relation d’ordre étant une relation, donc un ensemble de couples.

En 1931, Kurt Gödel écrit ceci dans son célèbre article [2] :

Cela correspond à ce modèle, intermédiaire entre celui de Kuratowski et celui de Tarski-Grothendieck :

Gödel propose aussi cette variante :

On remarque que Gödel parle de geordnete Paare comme Kuratowski, et note lui aussi les ensembles entre parenthèses. Il a besoin de parler de relations (pour la logique des prédicats) et définit une relation (ou un prédicat) comme un ensemble de couples. C’est à cette occasion qu’il construit un couple comme un ensemble d’ensembles.

C’est chez Bourbaki que la modélisation vue ci-avant semble être apparue pour la première fois.

Dans la mathématique bourbakiste, on a donc cette construction :

• Une fonction est un ensemble de couples.
• Un couple est un ensemble (dont l’un des éléments est lui-même une paire ou un singleton).
• La notion d’ensemble est primitive et tout le reste est basé dessus.

Pour Alonzo Church, la situation est plutôt inverse :

• La notion de fonction est primitive (« tout est fonction »).
• L’encodage de Church permet alors de construire les couples à partir des fonctions, dans le λ-calcul.
• Les couples sont tellement omniprésents qu’il est possible de modéliser les listes par les couples.
• Munie d’une fonction de hachage, une liste peut alors modéliser un ensemble.

On verra plus bas comment les couples permettent de modéliser des listes. Pour la construction du couple (a,b) en λ-calcul, c’est plutôt simple : on applique la fonction a à la fonction b. Le λ-calcul de Church étant non typé, il est en effet possible d’appliquer une fonction à elle-même (modélisation du couple (a,a) en appliquant la fonction a à elle-même). Et le résultat de l’application de a à b n’est pas nécessairement le même qu’en appliquant la fonction b à a.

Cependant on préfère appliquer une fonction aux deux arguments a et b : le couple (a,b) est donc modélisé par la fonction qui, à toute fonction z, associe z(a,b) :

Pour utiliser les couples, il faut trois choses :

• une projection sur le premier élément (notée par des crochets couple[0] en Python) nommée first ci-après ;
• une projection second sur le second élément (notée couple[1] en Python) ;
• un constructeur de couple, noté cons ci-après.

La première projection est visible dans la moitié gauche de cette image (la moitié droite est le couple (a,b) comme on l’a vu ci-dessus :

Voici les étapes du λ-calcul (réductions successives) mené sur first (a,b) :

On retrouve bien a comme réduction finale : le premier élément du couple (a,b) est bien a.

Quant à la seconde projection, elle donne, appliquée au couple (a,b), la valeur finale b, comme on le voit sur les étapes de cette réduction (seconde projection dans la moitié gauche, couple (a,b) dans la moitié droite) :

Enfin, comme on a vu plus haut comment le couple (a,b) est représenté en λ-calcul, la fonction cons de construction d’un couple est simplement la fonction qui, à xet y, associe le couple (x,y) :

C’est John McCarthy, à la fin des années 1950, qui a le premier programmé le λ-calcul sur un ordinateur. Il s’agissait d’un IBM 704 dont chaque instruction machine mesure 36 bits. Le calcul de l’adresse mémoire sur laquelle il fallait opérer, se fait en soustrayant deux parties de l’instruction :

• L’adresse de base appelée content of adress register, abrégé en CAR (15 bits sur les 36),
• et un décrément permettant un adressage plus fin, et stocké dans un champ de 15 bits appelé content of decrement register, abrégé en CDR.

MacCarthy choisit de stocker le premier élément d’un couple dans le CAR, et le second dans le CDR. Voici une vérification de ce fait par une séance de Scheme [3] :

> '(a b)
(a b)
> (car '(a b))
a
> (cdr '(a b))
(b)

La réponse ressemble au modèle de Tarski-Grothendiek vu ci-avant mais si (b) est entre parenthèses contrairement à a, c’est parce qu’en réalité (a b) n’est pas un couple mais une liste, comme on le verra un peu plus bas.

Il a fallu mettre devant (a b) le symbole quote, encore utilisé aujourd’hui en calcul formel, pour ne pas évaluer le couple (a,b). Cela est dû à ce qu’en programmation fonctionnelle, par défaut, le couple (a,b) représente l’application de la fonction a à la fonction b [4]. Par exemple l’évaluation de (cube 3) est l’application de la fonction cube au nombre 3 :

> (define (cube x) (* x x x))
cube
> (cube 3)
27

La suite de la construction de McCarthy passe par un nouvel objet appelé nil :

> nil
()

Enfin, en plaçant un nombre a dans le car d’un couple, et un pointeur vers un autre couple dans le cdr, McCarthy modélise une liste dont le premier élément est a et le reste est la liste restant après avoir enlevé a. Les couples (car,cdr) permettent ainsi à McCarthy de représenter des listes en machine, et il a appelé le langage obtenu du nom de List Processor, abrégé en Lisp. Lisp est donc un langage de programmation spécialisé dans le traitement de listes, et les couples ont servi à McCarthy à modéliser les listes de façon récursive. Avec un vocabulaire particulier :

• le premier élément d’une liste s’appelle son car,
• la liste privée de son premier élément (c’est une liste donc) est le cdr,
• le second élément de la liste est le car de son cdr, abrégé en cadr,
• la liste privée de ses deux premiers éléments est le cddr (cdr du cdr de la liste de départ)
• le troisième élément de la liste est la car du cddr soit le caddr de la liste :

> (define L '(1 2 3 4))
L
> L
(1 2 3 4)
> (car L)
1
> (cdr L)
(2 3 4)
> (cadr L)
2
> (caddr L)
3

Dans les langages de programmation qui ont succédé à Lisp, les couples sont typiquement représentés en machine par deux éléments stockés à des adresses consécutives.

La notion de couple (a,b) se généralise

• aux triplets (a,b,c)
• aux quadruplets (a,b,c,d)
• aux quintuplets (a,b,c,d,e)

et plus généralement aux n-uplets [5]. Les anglo-saxons utilisent la lettre « t » au lieu de « n » et abrègent t-uplet en tuple. C’est le terme qui a été gardé en Python :

Un couple est un tuple à deux éléments.

Le stockage en mémoire d’un couple est probablement assez similaire à celui de Lisp : deux objets côte à côte en mémoire. Par exemple l’expression

a.__sizeof__()

affiche 28 si a est une liste de deux entiers, et 20 seulement si a est un couple de deux entiers. Ceci signifie qu’un couple d’entiers occupe 20 octets en mémoire, alors que chaque entier occupe 14 octets. Les 4 octets de différence doivent être consacrés, au moins en partie, au type de l’entier (« int »).

Python peut aussi dessiner un couple avec son module graphviz, puisqu’un couple n’est jamais qu’un graphe orienté à deux sommets. Pour dessiner le couple (a,b) on peut

• mettre a dans le sommet A ;
• mettre b dans le sommet B ;
• dessiner une arête allant du sommet A au sommet B.

Cela donne ce script avec export au format png du couple dessiné :

from graphviz import Digraph

arrow = Digraph(format="png")

arrow.node('A','a')
arrow.node('B','b')
arrow.edge('A','B')

arrow.render('flèche',view=True)

Voici le dessin obtenu :

Dans cet article de l’Encyclopédie, d’Alembert écrit que

on appelle quantités variables en Géométrie, les quantités qui varient suivant une loi quelconque. Telles sont les abscisses & les ordonnées des courbes, leurs rayons osculateurs, &c.

On les appelle ainsi par opposition aux quantités constantes, qui sont celles qui ne changent point, comme le diametre d’un cercle, le parametre d’une parabole, &c.

On exprime communément les variables par les dernieres lettres de l’alphabet x, y, z.

Pour les encyclopédistes, une variable possède donc un nom (pour l’« exprimer ») et une quantité.

Un modèle de mémoire informatique a été proposé en 1977 par Dana Scott, comme fonction qui, à un emplacement mémoire, associe son contenu :

Ainsi, à un lieu L, on associe une valeur V. Ce que Scott nomme lieu correspond au nom de la variable [6].

Comme une fonction est un ensemble de couples, une variable est donc un couple :

1. Son premier élément est le nom de la variable (de type str c’est-à-dire élément d’un langage).
2. Son second élément est la valeur de la variable (souvent un nombre, mais pas nécessairement).

Voici une petite expérience en Python, pour prouver qu’une variable est effectivement un couple : sur une calculatrice, il y a un bouton var permettant de voir les variables. En Python, c’est la fonction globals qui permet de connaître les variables.

Au début on a quelque chose comme

>>> globals()
{'__package__': None, '__name__': '__main__', '__spec__': None, '__doc__': None, '__loader__': <class '_frozen_importlib.BuiltinImporter'>, '__builtins__': <module 'builtins' (built-in)>}

Ensuite on crée une variable v par affectation :

v = 3

Et v est apparu dans le dictionnaire des variables :

>>> globals()
{'__package__': None, '__name__': '__main__', 'v': 3, '__spec__': None, '__doc__': None, '__loader__': <class '_frozen_importlib.BuiltinImporter'>, '__builtins__': <module 'builtins' (built-in)>}

On voit que la variable v est apparue et que son premier élément est bien entre guillemets : c’est un nom. Les couples sont peut-être peu reconnaissables dans cette écriture d’un dictionnaire Python, mais ils sont bel et bien stockés sous le nom d’« items » :

>>> globals().items()
dict_items([('__package__', None), ('__name__', '__main__'), ('v', 3), ('__spec__', None), ('__doc__', None), ('__loader__', <class '_frozen_importlib.BuiltinImporter'>), ('__builtins__', <module 'builtins' (built-in)>)])

La variable v qu’on a créée ci-dessus apparaît sous cette forme :

('v', 3)

ce qui confirme que Python est conforme au modèle de Scott et Strachey.

Pour l’instant, la programmation de Sofus en Python fait appel à la programmation objet : dans Sofus (en Python), une variable est un objet doté de méthodes « sofusiennes » comme le doublement. Dans Python, comme on l’a vu ci-dessus, une variable est un couple (item d’un dictionnaire). Il suffit alors de créer un dictionnaire appelé valeur (voir ci-dessous les variables de bash pour la raison de ce nom) et qui contiendra les variables de Sofus :

valeur = {}

def vérifier(nom):
    if nom not in valeur:
        raise Exception("La variable "+nom+" n'existe pas")

La fonction vérifier a pour but d’afficher un message d’erreur en français si on essaye d’appliquer une fonction sofusienne à une variable qui n’existe pas. Une variable qui n’existe pas est une variable dont le nom ne figure pas parmi les clés (on appelle clé le premier élement du couple) du dictionnaire.

Comment construire ce fameux dictionnaire de variables ? Comme toujours en Python, on crée une variable par une affectation, qui consiste à accoupler un nom de variable avec une valeur (ici, numérique) :

def affecter(nom,valeur_initiale):
    valeur[nom] = valeur_initiale

Cette fonction, en apparence très simple, fait beaucoup de choses :

• Si la variable n’existe pas, Python la crée (en ajoutant le couple (nom,valeur_initiale) au dictionnaire valeur).
• Sinon, Python remplace la valeur actuelle de la variable par valeur_initiale.

Si on veut incrémenter la variable entière de nom n, on n’écrit pas

affecter('n',n+1)

mais

affecter('n',valeur['n']+1)

de manière similaire à bash que l’on verra plus bas. Mais il est plus simple dans ce cas, d’utiliser

augmenter_de('n',1)

En effet le code source de Sofus est entièrement partagé entre

• les 4 opérations :

def augmenter_de(nom,incrément):
    vérifier(nom)
    valeur[nom] += incrément
def diminuer_de(nom,décrément):
    vérifier(nom)
    valeur[nom] = décrément
def multiplier_par(nom,facteur):
    vérifier(nom)
    valeur[nom] *= facteur
def diviser_par(nom,diviseur):
    vérifier(nom)
    if diviseur == 0:
        valeur[nom] = float('inf')
    else:
        valeur[nom] /= diviseur

(avec le choix de diviser par 0 sans erreur blocante pour permettre le calcul de fonctions homographiques)

• les fonctions sofusiennes :

def inverser(nom):
    vérifier(nom)
    if valeur[nom] == 0:
        valeur[nom] = float('inf')
    else:
        valeur[nom] = 1/valeur[nom]
def doubler(nom):
    vérifier(nom)
    valeur[nom] *= 2
def tripler(nom):
    vérifier(nom)
    valeur[nom] *= 3
def quadrupler(nom):
    vérifier(nom)
    valeur[nom] *= 4
def quintupler(nom):
    vérifier(nom)
    valeur[nom] *= 5

• et les fonctions sur les pourcentages :

def augmenter_pourcent(nom,pourcentage):
    vérifier(nom)
    valeur[nom] *= (1+pourcentage/100)
def diminuer_pourcent(nom,pourcentage):
    vérifier(nom)
    valeur[nom] *= (1-pourcentage/100)
def multiplier_pourcent(nom,pourcentage):
    vérifier(nom)
    valeur[nom] *= pourcentage/100
def diviser_pourcent(nom,pourcentage):
    vérifier(nom)
    if pourcentage == 0:
        valeur[nom] = float('inf')
    else:
        valeur[nom] /= pourcentage/100

C’est tout ! Avec l’ajout de tests de parité pour programmer la suite de Collatz, voici l’intégralité du langage de programmation Sofus :

valeur = {}

def vérifier(nom):
    if nom not in valeur:
        raise Exception("La variable "+nom+" n'existe pas")

def affecter(nom,valeur_initiale):
    valeur[nom] = valeur_initiale
def augmenter_de(nom,incrément):
    vérifier(nom)
    valeur[nom] += incrément
def diminuer_de(nom,décrément):
    vérifier(nom)
    valeur[nom] = décrément
def multiplier_par(nom,facteur):
    vérifier(nom)
    valeur[nom] *= facteur
def diviser_par(nom,diviseur):
    vérifier(nom)
    if diviseur == 0:
        valeur[nom] = float('inf')
    else:
        valeur[nom] /= diviseur

def inverser(nom):
    vérifier(nom)
    if valeur[nom] == 0:
        valeur[nom] = float('inf')
    else:
        valeur[nom] = 1/valeur[nom]
def doubler(nom):
    vérifier(nom)
    valeur[nom] *= 2
def tripler(nom):
    vérifier(nom)
    valeur[nom] *= 3
def quadrupler(nom):
    vérifier(nom)
    valeur[nom] *= 4
def quintupler(nom):
    vérifier(nom)
    valeur[nom] *= 5
def est_pair(nom):
    vérifier(nom)
    return valeur[nom]%2 == 0
def est_impair(nom):
    vérifier(nom)
    return valeur[nom]%2 == 1
def est_divisible_par(nom,diviseur):
    vérifier(nom)
    if diviseur == 0:
        return False
    else:
        return valeur[nom]%diviseur == 0


def augmenter_pourcent(nom,pourcentage):
    vérifier(nom)
    valeur[nom] *= (1+pourcentage/100)
def diminuer_pourcent(nom,pourcentage):
    vérifier(nom)
    valeur[nom] *= (1-pourcentage/100)
def multiplier_pourcent(nom,pourcentage):
    vérifier(nom)
    valeur[nom] *= pourcentage/100
def diviser_pourcent(nom,pourcentage):
    vérifier(nom)
    if pourcentage == 0:
        valeur[nom] = float('inf')
    else:
        valeur[nom] /= pourcentage/100

En enregistrant le code source ci-dessus sous le nom de sofus.py il suffit, pour programmer en Sofus, de commencer son script (ou d’entrer dans la console)

from sofus import *

Par exemple, pour calculer une valeur approchée du nombre d’Or, ce script convient :

affecter('phi',1)
for _ in range(20):
    inverser('phi')
    augmenter_de('phi',1)

Après cela, on obtient la valeur approchée en évaluant l’expression

valeur['phi']

Un autre exemple, issu du programme de 1^re générale :

Quelle est la hauteur (nombre de disques) de la plus petite tour de Hanoï qu’on ne peut résoudre en moins d’un million de mouvements ?

On a besoin de deux variables, disques qui compte les disques, et déplacements qui est le nombre minimum de déplacements nécessaires permettant de résoudre la tour de Hanoï. Pour 0 disques, il y a 0 déplacements :

affecter('disques',0)
affecter('déplacements',0)
while valeur['déplacements']<1e6:
    augmenter_de('disques',1)
    doubler('déplacements')
    augmenter_de('déplacements',1)

et pour étudier la suite de Collatz :

affecter('u',65)
while valeur['u']>1:
    if est_impair('u'):
        tripler('u')
        augmenter_de('u',1)
    diviser_par('u',2)
    print(valeur['u'])

On a évoqué ci-dessus la fonction qui, au nom d’une variable, associe la valeur de cette variable. C’est cette fonction que Scott appelle état de la machine. Cette fonction est notée, en bash, par le symbole « dollar ». Ainsi la séquence suivante n’a pas le même effet qu’en Python :

♟️ variable=3

♟️ echo variable
variable

Le type essentiel de bash est la chaîne de caractères, on n’a donc pas besoin d’utiliser les guillemets pour préciser que le mot qu’on écrit est une chaîne de caractères. Du coup on a demandé à bash d’afficher (« echo ») le mot variable et non le contenu de la variable. Ceci par contre donne un comportement similaire à celui de Python :

♟️ variable=3

♟️ echo $variable
3

L’expression $variable signifie « ce qui est dans la variable », dans la droite ligne de la théorie de Scott et Strachey.

Le second type de base de bash est l’entier naturel. Ci-dessus bash a compris que 3 n’est pas une chaîne de caractères mais un nombre (entier).

L’incrémentation de la variable v (passage de la valeur 3 à la valeur 4) ne peut toutefois être faite en affectant v à la valeur $v+1 :

♟️ v=3
♟️ echo v+1
v+1
♟️ echo $v+1
3+1
♟️ echo $(($v+1))
4
♟️ echo $v
3
♟️ let "v=$v+1"
♟️ echo $v
4

Ce résumé « la valeur de la variable » par le symbole « $ » n’est pas spécifique de bash, on le trouve également en perl et en php.

Voici une application à Sofus (simplifié car ne portant que sur des entiers) :

#!/bin/bash
function afficher {
    cowsay -f koala $(($1))
}
function mettre {
    let "$3=$1"
}
function augmenter {
    let "$1=$1+$3"
}
function diminuer {
    let "$1=$1-$3"
}
function multiplier {
    let "$1=$1*$3"
}
function diviser {
    let "$1=$1/$3"
}
function doubler {
    let "$1=$1*2"
}
function tripler {
    let "$1=$1*3"
}
function quadrupler {
    let "$1=$1*4"
}
function quintupler {
    let "$1=$1*5"
}
function sextupler {
    let "$1=$1*6"
}
function octupler {
    let "$1=$1*8"
}
function décupler {
    let "$1=$1*10"
}

L’avantage de cette version par rapport à la version Python est qu’elle ne nécessite pas de parenthèses pour écrire les fonctions, ce qui donne à la programmation dans cette version de Sofus, une plus grande proximité avec la langue française. Par exemple si le code source ci-dessus a été téléchargé sous le nom sofus.sh et rendu exécutable [7] :

♟️ source sofus.sh
♟️ mettre 13 dans v
♟️ afficher v
 ____
< 13 >
 ----
  \
   \
       ___  
     {~._.~}
      ( Y )
     ()~*~()   
     (_)-(_)   
♟️ tripler v
♟️ afficher v
 ____
< 39 >
 ----
  \
   \
       ___  
     {~._.~}
      ( Y )
     ()~*~()   
     (_)-(_)   
♟️ augmenter v de 1
♟️ afficher v
 ____
< 40 >
 ----
  \
   \
       ___  
     {~._.~}
      ( Y )
     ()~*~()   
     (_)-(_)   
♟️ diviser v par 2
♟️ afficher v
 ____
< 20 >
 ----
  \
   \
       ___  
     {~._.~}
      ( Y )
     ()~*~()   
     (_)-(_)   
♟️

Supposons pour simplifier l’exposé que les variables ont des valeurs réelles ; alors selon la théorie de Scott

• Une variable est un couple de la forme (s,x) où s∈L (un langage) et x∈R (valeur réelle).
• Un état de l’ordinateur est donc une fonction L→R
• Le type d’une instruction est alors (L→R)→(L→R) (effet de bord).
• Un programme est une suite d’instructions, c’est-à-dire une fonction qui, à tout indice n∈N, associe une instruction. Le type d’un programme est donc N→((L→R)→(L→R)).

Pour peu qu’un programme implémente une fonction R→R, l’implémentation est plus compliquée que la fonction implémentée. Ceci explique peut-être qu’il ait fallu attendre les années 1970 pour que Scott et Strachey créent (pour la première fois) une sémantique des programmes informatiques.