Les fonctions (récursives) décortiquées

Frédéric Cabestre
@fcabestre
I'm not a number, I'm a freelance.
— Number 6, The Prisoner
Goto Considered Harmful

Théorie

« Un jour j'irai vivre en Théorie,
car en Théorie tout se passe bien. »
— Pierre Desproges

λ-Calcul

$x$
Variable
$\lambda x.\,M$
Abstraction
$M\,N$
Application
$\lambda x.\,(f\,x) \rightarrow f$
$\eta$-reduction
$\lambda x.\,M[x] \rightarrow \lambda y.\,M[y]$
$\alpha$-conversion
$(\lambda x.\,M)\:E \rightarrow M[x:=E]$
$\beta$-reduction
Rejected

Stratégies d'Évaluation


                        public static int Add(int x, int y) => x + y;
            
C#

                        Add(Add(19, 42), Add(13, 17))
            
C#

Stratégies d'Évaluation


              
                
                
            Add(Add(19, 42), Add(13, 17))

            Add(19 + 42, Add(13, 17))

            Add(61, Add(13, 17))

            Add(61, 13 + 17)

            Add(61, 30)

            61 + 30

            91
                
                    
Stricte
Presque tous les langages ! 

                    
                
                
            Add(Add(19, 42), Add(13, 17))

            Add(19, 42) + Add(13, 17)

            19 + 42 + Add(13, 17)
    
            61 + Add(13, 17)
    
            61 + 13 + 17
    
            61 + 30

            91
                
                    
Non Stricte
Algol60, Miranda, Lazy ML, Clean,
R, Haskell

Sémantique

Donner un sens aux expressions syntaxiques
d'un langage dans un autre langage
Informelle : Manuel de programmation
Formelle : Axiomatique, Dénotationnelle, Opérationnelle

OCaml

Original CAM paper

OCaml

ZINC paper

Pratique

« En théorie, il n'y a pas de différence entre la théorie et la pratique.
Mais en pratique, il y en a une. »
— Yogi Berra

Compilation

Sorte de sémantique formelle
Instruction Set Architecture
Virtuelle (JVM, CLI, WASM...)
Concrète (x86, ARM...)
Fossé sémantique

Commençons simple...


                        let Add x y = x + y
            
F#

                        public static int Add(int x, int y) => x + y;
            
C#
Arguments passés à la fonction (valeurs associée à x et y)
Les variables locales (scalaires, tableau, structures...)
Les résultats de calculs intermédiaires (par exemple x + y)
Le point (adresse) de retour

Commençons simple...

Enregistrement d'activation
... Ou activation frame
... Ou activation record
Qui a pensé au mot pile... ou stack pour les anglophiles ?

FORTRAN

FORmula TRANslator (avril 1957 - John Backus)

FORTRAN

J. Backus

FORTRAN

FORmula TRANslator (avril 1957 - John Backus)
F66 apparition de SUBROUTINE et FUNCTION (mars 1966)
Allocation statique à côté du code de la fonction
Plusieurs instances de la même fonction ?
F77 récursivité supportée par certains compilateurs (avril 1978)
F90 récursivité officielle, RECURSIVE (standard ANSI 1992)

Récursivité simple

Un cas de base ou cas d'arrêt
Un cas général définit au rang $n$ en fonction du rang $n - 1$

                        let rec Fact = function
                            | 0u -> 1u
                            | (n: uint) -> n * Fact(n - 1u)
            
F#

Récursivité simple

Un cas de base ou cas d'arrêt
Un cas général définit au rang $n$ en fonction du rang $n - 1$

                        let rec Fact = function
                            | 0u -> 1u
                            | (n: uint) -> n * Fact(n - 1u)
            
F#

Récursivité simple

Un cas de base ou cas d'arrêt
Un cas général définit au rang $n$ en fonction du rang $n - 1$

                        let rec Fact = function
                            | 0u -> 1u
                            | (n: uint) -> n * Fact(n - 1u)
            
F#

                        public static uint Fact(uint n) => n switch
                        {
                            0u => 1u,
                            _ => n * Fact(n - 1)
                        };
            
C#

Récursivité mutuelle

Plusieurs fonctions récursives se définissant
les unes part rapport aux autres

                        let rec IsEven =
                            function
                            | 0u -> true
                            | (n: uint) -> IsOdd(n - 1u)
                        
                        and IsOdd =
                            function
                            | 1u -> true
                            | (n: uint) -> IsEven(n - 1u)
            
F#

Récursivité mutuelle

Plusieurs fonctions récursives se définissant
les unes part rapport aux autres

                        let rec IsEven =
                            function
                            | 0u -> true
                            | (n: uint) -> IsOdd(n - 1u)
                        
                        and IsOdd =
                            function
                            | 1u -> true
                            | (n: uint) -> IsEven(n - 1u)
            
F#

Récursivité mutuelle

Plusieurs fonctions récursives se définissant
les unes part rapport aux autres

                        let rec IsEven =
                            function
                            | 0u -> true
                            | (n: uint) -> IsOdd(n - 1u)
                        
                        and IsOdd =
                            function
                            | 1u -> true
                            | (n: uint) -> IsEven(n - 1u)
            
F#

Récursivité mutuelle

Plusieurs fonctions récursives se définissant
les unes part rapport aux autres

                        let rec IsEven =
                            function
                            | 0u -> true
                            | (n: uint) -> IsOdd(n - 1u)
                        
                        and IsOdd =
                            function
                            | 1u -> true
                            | (n: uint) -> IsEven(n - 1u)
            
F#

Mise en œuvre

Plusieurs instances d'une même fonction
Enregistrement créé à l'activation de la fonction
Récupérable dès sa désactivation
$\Rightarrow$ Pile

Mise en œuvre


        Main
          Fact(2)
            Fact(1)
              Fact(0)
            Fact(1)
          Fact(2)
        Main
                    
C#

Pile non inclue

Évolution Des Processeurs

Architectures...
à accumulateur
à pile et processeurs langages
à registres généraux
Reduced Instruction Set Computer
John Cocke [IBM], David Patterson [Berkeley]

Évolution Des Processeurs

David Patterson
David Patterson

Évolution Des Processeurs

Architectures...
à accumulateur
à pile et processeurs langages
à registres généraux
Reduced Instruction Set Computer
John Cocke [IBM], David Patterson [Berkeley]
Dec Alpha, IBM POWER, SPARC... (1980 et après)
ARM, M1 et RISC-V (aujourd'hui)

Évolution Des Processeurs

Moins d'instructions plus élémentaires
Plus de registres généraux
   [x86]       CALL / RET + pile
[ARM]       BL + registre 14
Plus de responsabilité au compilateur
Mais plus d'optimisations possibles
Exemple : Fonctions feuilles

Appel terminal

La dernière action d'une fonction est un appel de fonction

                        let rec FactTailRecursive acc =
                            function
                            | 0u -> acc
                            | (n: uint) -> FactTailRecursive (n * acc) (n - 1u)
            
F#

                        public static uint FactTailRecursive(uint acc, uint n) => n switch
                        {
                            0u => acc,
                            _ => FactTailRecursive(n * acc, n - 1)
                        };
            
C#

Appel terminal

Puisqu'il ne restera plus rien à faire au retour de la fonction appelée...
Autant réutiliser l'enregistrement d'activation courant !
Économie d'allocation (espace constant)
Style par continuation
Récursivité terminale

Mise en œuvre


        Main
          Fact(1, 2)
            Fact(2, 1)
              Fact(2, 0)
        Main
                    
C#

Code Généré



          .method public hidebysig static unsigned int32
            FactTailRecursive(unsigned int32 acc, unsigned int32 n
            ) cil managed
          {
            [...]
            IL_0000: ldc.i4.1
            IL_0001: brtrue.s     IL_0004
        
            IL_0003: nop
        
            IL_0004: ldarg.1      // n
            IL_0005: brfalse.s    IL_0009
            IL_0007: br.s         IL_000d
        
            IL_0009: ldarg.0      // acc
            IL_000a: stloc.0      // V_0
            IL_000b: br.s         IL_001b
        
            IL_000d: ldarg.1      // n
            IL_000e: ldarg.0      // acc
            IL_000f: mul
            IL_0010: ldarg.1      // n
            IL_0011: ldc.i4.1
            IL_0012: sub
            IL_0013: call         unsigned int32 CSharp.Factorial::FactTailRecursive(
                                      unsigned int32, unsigned int32
                                  )
            IL_0018: stloc.0      // V_0
            IL_0019: br.s         IL_001b
        
            IL_001b: ldc.i4.1
            IL_001c: brtrue.s     IL_001f
        
            IL_001e: nop
        
            IL_001f: ldloc.0      // V_0
            IL_0020: ret
          } 
                    
IL (C#)


          .method public static unsigned int32
            FactTailRecursive(unsigned int32 acc, unsigned int32 _arg1
            ) cil managed
          {
              [...]
              IL_0000: ldarg.1      // _arg1
              IL_0001: stloc.0      // V_0
        
              IL_0002: ldloc.0      // V_0
              IL_0003: switch       (IL_000e)
              IL_000c: br.s         IL_0010
        
              IL_000e: ldarg.0      // acc
              IL_000f: ret
        
              IL_0010: ldloc.0      // V_0
              IL_0011: stloc.1      // n
        
              IL_0012: ldloc.1      // n
              IL_0013: ldarg.0      // acc
              IL_0014: mul
              IL_0015: ldloc.1      // n
              IL_0016: ldc.i4.1
              IL_0017: sub
              IL_0018: starg.s      _arg1
              IL_001a: starg.s      acc
              IL_001c: br.s         IL_0000
          } 
                    
IL (F#)

Code Généré



          .method public hidebysig static unsigned int32
            FactTailRecursive(unsigned int32 acc, unsigned int32 n
            ) cil managed
          {
            [...]
            IL_0000: ldc.i4.1
            IL_0001: brtrue.s     IL_0004
        
            IL_0003: nop
        
            IL_0004: ldarg.1      // n
            IL_0005: brfalse.s    IL_0009
            IL_0007: br.s         IL_000d
        
            IL_0009: ldarg.0      // acc
            IL_000a: stloc.0      // V_0
            IL_000b: br.s         IL_001b
        
            IL_000d: ldarg.1      // n
            IL_000e: ldarg.0      // acc
            IL_000f: mul
            IL_0010: ldarg.1      // n
            IL_0011: ldc.i4.1
            IL_0012: sub
            IL_0013: call         unsigned int32 CSharp.Factorial::FactTailRecursive(
                                      unsigned int32, unsigned int32
                                  )
            IL_0018: stloc.0      // V_0
            IL_0019: br.s         IL_001b
        
            IL_001b: ldc.i4.1
            IL_001c: brtrue.s     IL_001f
        
            IL_001e: nop
        
            IL_001f: ldloc.0      // V_0
            IL_0020: ret
          } 
                    
IL (C#)


          .method public static unsigned int32
            FactTailRecursive(unsigned int32 acc, unsigned int32 _arg1
            ) cil managed
          {
              [...]
              IL_0000: ldarg.1      // _arg1
              IL_0001: stloc.0      // V_0
        
              IL_0002: ldloc.0      // V_0
              IL_0003: switch       (IL_000e)
              IL_000c: br.s         IL_0010
        
              IL_000e: ldarg.0      // acc
              IL_000f: ret
        
              IL_0010: ldloc.0      // V_0
              IL_0011: stloc.1      // n
        
              IL_0012: ldloc.1      // n
              IL_0013: ldarg.0      // acc
              IL_0014: mul
              IL_0015: ldloc.1      // n
              IL_0016: ldc.i4.1
              IL_0017: sub
              IL_0018: starg.s      _arg1
              IL_001a: starg.s      acc
              IL_001c: br.s         IL_0000
          } 
                    
IL (F#)

Comment rebondir ?

En utilisant un trampoline
Retourner une valeur qui exprime
un « reste à faire » ou un résultat
Invoquer le « reste à faire » dans une boucle
ou retourner le résultat

Trampoline


                public interface ITailRec<out T> {
                    public T Run() { ... }
                }
        
                public struct Return<T> : ITailRec<T> {
                    public T Value { get; init; }
                }
        
                public struct Suspend<T> : ITailRec<T> {
                    public Func<ITailRec<T>> Thunk { get; init; }
                }
            
C#

                public static ITailRec<uint> FactTrampoline(uint acc, uint n) => n switch {
                            0 => new Return<uint> { Value = acc },
                            _ => new Suspend<uint> { Thunk = () => FactTrampoline(n * acc, n - 1) 
                        }
                    };
                }
            
C#

Trampoline


                FactTrampoline(1, 3).Run()
            
C#

                public interface ITailRec<out T> {
                    public T Run() {
                        var current = this;
                        for (;;)
                            switch (current) {
                                case Return<T> @return: return @return.Value;
                                case Suspend<T> suspend:
                                    current = suspend.Thunk();
                                    break;
                            }
                    }
                }
            
C#

Coda

« La théorie, c'est quand on sait tout et que rien ne fonctionne.
La pratique, c'est quand tout fonctionne et que personne ne sait pourquoi.
Ici, nous avons réuni théorie et pratique :
Rien ne fonctionne... Et personne ne sait pourquoi !
— Albert Einstein

Et ensuite ?

Fonctions d'ordre supérieur
Continuations de premier ordre
Coroutines
...

Ressources

Modern Compiler Implementation in ML Modern Compiler Implementation in ML

Ressources

Types and Programming Languages
The ZINC Experiment [PDF]
Wikipedia [Web]
Frédéric Cabestre
@fcabestre

Merci