Mcarthy

Dans le langage mathématique il n’existe pas de notation idoine lorsqu’il s’agit d’exécuter une suite d’opérations selon une condition, sinon que de l’écrire en toutes lettres en dehors du langage mathématique.

Avec le formalisme de McCarthy dans les années 60, la notion d’exécution conditionelle ou paresseuse et de parties faibles apparait, ainsi que des notations abstraites proches de la logique venant avec.

Ce formalisme permet d’expliciter explicitement les étapes que l’on souhaite exécuter ou non via une notation idoine jusque là absente des mathématiques.

L’exécution conditionelle des blocs existait deja de facto dans le langage ALGOL, McCarthy leur a donné un formalisme mathématique et a introduit la notion d’evaluation paresseuse.

Evaluation paresseuse

Soient A() et B() deux suites qui convergent vers le resulat R a des vitesses differentes

Dans le pseudo-programme

if(equal(R , A() or B()))
then
    ...

Ici si le programe constate qu’une des deux suites converge plus rapidement vers le résultat R, on remarque que le programme peut être paresseux et stopper l’exécution d’une des deux suites et alouer toute sa ressource à l’autre.

Ces considérations sont académiques et n’ont pas d’équivalent dans la réalité mais par la nature court-circuitante et “paresseuse” des opérateurs && et ||, on les appelle parfois dans les années 70 « opérateurs de Mc Carthy ».

En C il n’est pas question d’exécution parellèle, mais l’évaluation paresseuse existe à plusieurs endroits de sa syntaxe suivant des règles strictes d’exécution séquentielle de gauche à droite et de haut en bas.

int y() {
    return 1;
}

int n() {
    return 0;
}

int main() {

    int a = 2;
    volatile int b = 0;

    int c = b && y(); // y() n'est pas exécuté
    int d = y() || n(); // n() n'est pas exécuté

    if(b) {
        ...; // sur les processeurs récents sera 
        // probablement pré-exécuté si pas d'effets de bord 
        // en pratique le processeur peut etre paresseux et ne rien
        // exécuter de ce bloc.
    } else {
        puts("ko"); // sera probablement exécuté en fonction 
        // de la valeur de b - qui peut varier sans qu'on puisse le prévoir
    }
}

References

A BASIS FOR A MATHEMATICAL THEORY OF COMPUTATION, JOHN McCARTHY 1961–1963 : http://jmc.stanford.edu/articles/basis/basis.pdf 🌍⤴

A Note on Conditional Expressions , Daniel P. Friedman and David S. Wise, 1978 : https://dl.acm.org/doi/pdf/10.1145/359642.359650 🌍⤴