2017-10-18 31 views
2

Comment écrire une fonction factorielle sans utiliser la récursion en utilisant le lambda-calcul? Ce qui signifie que la notation mathématique n'est pas implémentée dans un langage de programmation particulier.Fonction factorielle du lambda-calcul non-récursif

+1

une boucle commençant à N qui multiplie N * - N jusqu'à ce que N soit 1? –

+3

Quand vous dites "sans utiliser de récursivité", voulez-vous dire "sans un combinateur de points fixes"? Si c'est le cas, c'est impossible. – sepp2k

+1

@GradyPlayer Le calcul lambda est constitué uniquement de fonctions. Il n'y a pas de boucles. – molbdnilo

Répondre

1

Si par « sans l'utilisation de la récursivité » vous voulez dire sans récursion général et donc sans points fixes (ou auto applications), nous pouvons simplement observer que la fonction factoriel est récursive primitive (qui est, itératif, en essence), et il existe un codage très général et simple de la récursion primitive au moyen de l'itération (fournie par les chiffres de l'église) et des paires. Je vais discuter du cas général qui est très instructif. Soit < M, N> soit un codage de paires, et que fst et snd soient les projections associées. Par exemple, vous pouvez définir

<M,N> = λz. z M N 
fst = λp. p (λxy.x) 
snd = λp. p (λxy.y) 

On suppose d'avoir une définition récursive primitive (sans paramètres, par souci de simplicité)

f(0) = a 
f(x+1) = h(x,f(x)) 

a et h ont déjà été définis.

L'idée générale consiste à utiliser une fonction auxiliaire f 'où

     f'(x) = <x,f(x)> 

Ainsi, f' (0) = < 0, a>, et compte tenu de la paire p = < x, f (x)> = f '(x), nous construisons la paire suivante < x + 1, f (x + 1)> en calculant le successeur sur le premier composant et en appliquant h à la paire d'arguments (que, profitant de notre encodage de paires, revient simplement à passer la suite h en entrée de la paire p).

En résumé,

next = λp.< succ (fst p), p h> 

Enfin, pour calculer f (n), nous devons itérer n fois la fonction suivante à partir de < 0, a>, puis prenez la deuxième composante:

f = λn. snd (n next <0,a>) 
+0

En utilisant le nombre d'église pour conduire l'itération est une bien meilleure réponse pour ce faire sans l'effet de la récursivité - grande réponse – naomik

+0

Merci. Cette technique m'a été expliquée par Gérard Huet il y a plus de 30 ans, mais je ne suis pas sûr de qui devrait être crédité pour cela. Peut-être que quelqu'un connaît la réponse. –

7

je n'ai pas dit tout ce que je ne voulais pas

Par « sans l'utilisation de la récursivité » vous devez dire « sans fonction qui se fait appeler par son nom »

Quoi qu'il en soit, nous allons écrire factoriel

fact := λn. zero? n one (mult n (fact (dec n)))

maintenant, nous ne soucions pas particulièrement environ zero?, mult, dec, ou même one dans cet exemple; vous pouvez mettre en œuvre ceux de votre propre - nous voulons juste enlever le gras, par nom récursion,

... fact (dec n)

La meilleure façon de faire est d'appliquer un lambda à lui-même - rencontrer le U Combinator

U := λf. f f 

maintenant, nous pouvons envelopper notre expression originale dans un lambda, et appliquer U

fact := U (λf. λn. zero? n one (mult n (??? (dec n))))

Mais qu'est-ce que nous avons mis en place des fact ??? - Rappelez-vous que f est une référence à la lambda externe elle-même, donc pour que ce soit le même cas dans la prochaine "itération", nous devons appliquer f à elle-même, tout comme U fait - en fait, vous pouvez penser de U comme une sorte de miroir, et votre fonction peut refléter dans ce miroir afin de se reproduire; mais cette fois, sans utiliser un nom^_^

fact := U (λf. λn. zero? n one (mult n (f f (dec n))))

Oui, oui, mais encore plus astucieux remarquerez que vous pouvez utiliser le miroir (U) directement dans le lambda, trop

fact := U (λf. λn. zero? n one (mult n (U f (dec n))))

U agrandie sans

nous savons comment développer l'intérieur - nous l'avons écrit que manière la première fois

fact := U (λf. λn. zero? n one (mult n (f f (dec n))))

maintenant étendre l'U externe

fact := (λf. λn. zero? n one (mult n (f f (dec n)))) (λf. λn. zero? n one (mult n (f f (dec n))))

ça marche?

tous les chiffres de l'église représentés comme

#N
fact := U λf. λn. zero? n #1 (mult n (U f (dec n))) 

fact #4 

U (λf. λn. zero? n #1 (mult n (U f (dec n))) #4 

(λf. f f) (λf. λn. zero? n #1 (mult n (U f (dec n))) #4 

(λf. λn. zero? n #1 (mult n (U f (dec n))) (λf. λn. zero? n #1 (mult n (U f (dec n))) #4 

(λn. zero? n #1 (mult n (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec n))) #4 

zero? #4 #1 (mult #4 (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec #4))) 

zero? #4 #1 (mult #4 (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (deC#4))) 

// (zero? #4); false; returns second argument 
(mult #4 (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (deC#4))) 

// which is #4 * ... 
(U (λf. λn. zero? n #1 (mult n (U f (dec n))) (deC#4)) 

// which is ... 
(U (λf. λn. zero? n #1 (mult n (U f (dec n))) #3) 

// which is equivalent to... 
fact #3 

// so ... 
(mult #4 (fact #3)) 

// repeating this pattern ... 
(mult #4 (mult #3 (fact #2)) 
(mult #4 (mult #3 (mult #2 (fact #1))) 
(mult #4 (mult #3 (mult #2 (mult #1 (fact #0)))) 
(mult #4 (mult #3 (mult #2 (mult #1 #1)))) 
(mult #4 (mult #3 (mult #2 #1))) 
(mult #4 (mult #3 #2)) 
(mult #4 #6) 
#24 

démonstration en javascript

Allez-y et afficher la puissance de l'U combinateur avec vos globes oculaires très propres!

const U = 
 
    f => f (f) 
 
    
 
const fact = 
 
    U (f => n => 
 
    n === 0 ? 1 : n * U (f) (n - 1)) 
 
    
 
console.log (fact (4)) // 24

Et encore une fois comme une expression lambda pur

console.log (
 
    (f => n => n === 0 ? 1 : n * f (f) (n - 1)) 
 
    (f => n => n === 0 ? 1 : n * f (f) (n - 1)) 
 
     (4) 
 
) // 24

récursion mutuelle

L'extrait ci-dessus illustre une propriété très importante de ce processus récursif: mutually recursive. Comme vous pouvez le voir, il y a réellement deux (quoique les mêmes) fonctions entraînant la récursivité; A appelle B, B appelle A - Cependant, dans le cas du combinateur U, il n'y a qu'une seule fonction qui est appliquée à elle-même, donc elle active direct recursion - le lambda s'appelle lui-même en utilisant son paramètre, pas son nom (lambdas ne sont pas un nom pour appeler)


Y?

Because I said so

le combinateur U est un peu lourd parce qu'il attend à l'utilisateur de « refléter » la fonction afin de se reproduire - si nous pouvions fournir le lambda externe avec une fonction qui est le miroir lui-même?

U := λf. f f 
Y := λg. U (λf. g (U f)) 

Je vais vous montrer à nouveau la même définition, mais sur deux lignes pour que vous puissiez voir les « miroirs » et leurs positions

 /g, user's function 
     /
     // outer reflection 
    // 
Y := λg. U (λf. ... ) 
       g (U f) 
       \ 
        \ call g with inner reflection

Alors maintenant, chaque fois que vous appliquez Y à tout lambda (g), son paramètre est la fonction pour calculer la lambda elle-même - changer fact à

fact := Y (λf. λn. zero? n one (mult n (f (dec n))))

expansion Y

Y := λg. U (λf. g (U f))    // expand inner U 
Y := λg. U (λf. g (f f))    // expand outer U 
Y := λg. (λf. g (f f)) (λf. g (f f))

qui est la définition que vous voyez là dans wikipedia; juste alpha-renommé


Je viens d'avoir une découverte profonde

Dérivation Y de U ci-dessus, j'ai vu quelque chose que je ne l'ai jamais vu auparavant - un caché B

Y := λg. U (λf. g (U f)) 

B := λf. λg. λx. f (g x) 

Y' := λg. U (B g U) 

One des plus belles choses que j'ai jamais vues - and it works too; pas que nous devrions avoir des raisons de penser que ce ne serait pas ...

#lang lazy 

(define B (λ (f) 
      (λ (g) 
       (λ (x) 
       (f (g x)))))) 

(define U (λ (f) 
      (f f))) 

(define Y (λ (g) 
      (U ((B g) U)))) 

(define fact (Y (λ (f) 
        (λ (n) 
        (if (= n 0) 
         1 
         (* n (f (sub1 n)))))))) 

(fact 4) ;; 24 

Haskellers

Avez-vous déjà vu Y exprimé en?

Y = U . (. U) 
    where U f = f f 
+0

'U f = f f' ne correspondra pas à Haskell. –

+0

@AaditMShah merci - je n'ai pas pris le temps de le tester dans ghci; Je ne l'ai jamais vu de cette façon^_^ – naomik

+0

Je préfère la définition 'y f = f (y f)' comme vous pouvez voir la récursivité se dérouler naturellement ainsi que la paresse de témoin en action, empêchant les boucles infinies. Aussi, ['Yoshihiko Futamura = Futamura (Yoshihiko Futamura)'] (http://fi.ftmr.info). [Je suis tellement méta, même cet acronyme.] (Https://www.xkcd.com/917/) = D –