Exercice SICP 1.10

J’ai terminé la lecture du premier chapitre de SICP et j’ai commencé à m’attaquer aux exercices qui se sont entassés au fur et à mesure de ma progression. Initialement, je pensais les faire directement durant ma lecture mais ma flemme ajoutée à mon envie d’avancer dans la lecture du bouquin m’y ont découragé. L’avantage de devoir revenir maintenant sur les exercices c’est que j’ai la possibilité de revoir - par la pratique cette fois-ci - les concepts que j’ai passivement lu dans le livre. A mon avis celà devrait graver d’autant mieux la matière dans mon esprit…. Soit mais bon maintenant le titre de ce billet n’attendait ni plus ni moins la solution de l’exercice 1.10! Donc nous y voilà, je mets ici ma solution parce qu’elle m’a pris pas mal de ligne à l’expliquer et je ne veux pas trop poluer ma page dédiée aux exercices de SICP… Cet exercice propose de prédire le résultat de la fonction d’Ackermann (générateur de grands nombres très rapide grâce à la récursivité) au vu de certains paramètres donnés. La fonction d’Ackermann est fournie par le livre:

(define (A x y)
    (cond ( (= y 0) 0)
            ( (= x 0) (* 2 y))
            ( (= y 1) 2)
    (else (A (- x 1) (A x (- y 1))))))

Mon objectif a été de résoudre qu’un seul des trois exercices proposés:

(A 2 4)
 

(A 1 (A 2 3))
 

(A 2 3) = 16
 
(A 1 (A 2 2))
 

(A 2 2) = 4
 
(A 1 (A 2 1))
 
(A 1 2)
 
(A 1 2)
 
(A 0 (A 1 1))
 
(A 0 2)
 
4
 

(A 1 4) = 16
 
(A 0 (A 1 3))
 
(A 1 3)
 
(A 0 (A 1 2))
 
(A 0 4) = 8
 

(A 1 16) = 2 ^16 = 65536

En espérant être assez clair, j’ai procédé la fonction en suivant l ‘applicative-order pour ne pas finir avec une ligne immense mais plutôt remplacer chaque appel de fonction avec la valeur calculée. Ce qui finalement nous amène à (A 1 16). A ce moment-là, j’aurais pu continuer le processing jusque trouver la solution mais on peut constater une abstraction lorsque la fonction d’Ackerman est appelée suivant le motif (A 1 n):

• (A 1 2) = 4
• (A 1 3) = 8
• (A 1 4) = 16

Autrement dit, (A 1 n) = 2 ^ n et donc (A 1 16) = 2 ^ 16 = 65536. Trouver ce motif permet en plus de répondre à la 2ème partie de la question:

(define (f n) (A 0 n)) = 2*n
(define (g n) (A 1 n)) = 2^n
(define (h n) (A 2 n)) = 2 ^ 2 ^ 2 ... n fois

La dernière se retrouve également dans la preuve de (A 2 4):

• (A 2 3) = 16 = 2 ^ 2 ^ 2

• (A 2 2) = 4 = 2 ^ 2

• (A 2 1) = 2 = 2 ^ 1 (cas spécial dans la fonction)

Si ce genre d’exercices vous intéressent, je ne peux que vous conseiller la lecture de SICP!

order_evaluation#Applicative_order