Représenter des nombres négatifs et de complexes à l'aide Lambda Calcul

Question

La plupart des tutoriels sur Lambda Calcul fournir des exemples où Entiers positifs et booléens peuvent être représentés par des fonctions. Qu'en est-1 et i?

Answer 1

Tout d'abord encoder des nombres naturels et des paires, comme décrit par jmad.

$ représentent un entier k $ comme une paire de nombres naturels $ (a, b) de telle sorte que $ $ k = a - b $. Ensuite, vous pouvez définir les opérations habituelles sur les nombres entiers comme (en utilisant la notation Haskell pour $ \ lambda $ -calcul):

neg = \k -> (snd k, fst k)
add = \k m -> (fst k + fst m, snd k + snd m)
sub = \k m -> add k (neg m)
mul = \k m -> (fst k * fst m + snd k * snd m, fst k * snd m + snd k * fst m)

Le cas de nombres complexes est similaire en ce sens qu'un nombre complexe est codé sous la forme d'une paire de nombres réels. Mais une question plus compliquée est de savoir comment coder reals. Ici, vous devez faire plus de travail:

1. Encode un nombre rationnel $ q $ en tant que paire $ (k, a) $ où $ $ k est un nombre entier, $ a $ est naturel, et $ q = k / (1 + a) $.
2. Encode un nombre réel $ x $ par $ fonction f $ telle que pour chaque $ naturel k \ in \ mathbb {N} $, $ f k $ code pour un nombre rationnel $ q $ tel que $ | x - q | <2 ^ {- k} $. En d'autres termes, un vrai est codé comme une séquence de rationals convergeant vers elle au taux $ k \ mapsto 2 ^ {- k}. $

L'encodage est reals beaucoup de travail et vous ne voulez pas le faire réellement dans le $ \ lambda $ -calcul. Mais voir par exemple le sous-répertoire etc/haskell de Marshall pour une implémentation simple de reals dans le plus pur Haskell. Cela pourrait, en principe, être traduit au pur $ \ lambda $ -calcul.

Answer 2

Lambda-calcul peuvent coder la plupart des structures de données et les types de base. Par exemple, vous pouvez encode une paire de termes existant dans le lambda-calcul, en utilisant la même Church encodage que vous voyez habituellement pour coder des entiers non négatifs et booléen:

$$ \ mbox {} = paire ?xyz.zxy $$ $$ \ mbox {} = fst ?p.p (?xy.x) $$ $$ \ mbox {} = SND ?p.p (?xy.y) $$

Alors la paire $ (a, b) $ est $ p = (\ mbox {paire} ab) $ et si vous voulez revenir $ a et $ b $ que vous pouvez faire $ (\ mbox {fst} p) $ et $ (\ mbox {} p SND) $.

Cela signifie que vous pouvez facilement représenter des nombres entiers positifs et négatifs avec une paire: le signe sur la gauche et la valeur absolue à droite. Le signe est d'être une valeur booléenne qui spécifie si le nombre est positif. Le droit est un nombre naturel en utilisant le codage Eglise.

$$ (signe, n) $$

Et maintenant que vous avez des entiers relatifs. La multiplication est facile à définir, il vous suffit d'appliquer le $ \ mbox {} $ XOR fonction sur le signe et la multiplication de sur des nombres naturels sur la valeur absolue:

$$ \ mbox {} mult _Z = ?ab. \ Mbox {} paire ~~ (\ mbox {} XOR (\ mbox {} a SGO) (\ mbox {} b SGO)) ~~ (\ mbox {} mult _N (\ mbox {} SND a) (\ mbox {} SND b)) $$

Pour définir l'ajout, vous devez comparer deux nombres naturels et la soustraction d'utilisation lorsque les signes sont différents, donc ce n'est pas un ?-terme, mais vous pouvez l'adapter si vous voulez vraiment:

$$ \ mbox {} add _Z = ?ab. \ Left \ {\ begin {array} {} ll (\ Mbox {true}, \ mbox {} add _N (\ mbox {} SND a) (\ mbox {} SND b)) et \ mbox {if} a=0?b=0 \\ (\ Mbox {false}, \ mbox {} add _N (\ mbox {} SND a) (\ mbox {} SND b)) et \ mbox {if} a <0?b <0 \\ (\ Mbox {true}, \ mbox {sub} _N (\ mbox {} SND a) (\ mbox {} SND b)) et \ mbox {if} a=0?b <0? | a | = | b | \\ (\ Mbox {false}, \ mbox {sub} _N (\ mbox {} SND b) (\ mbox {} SND a)) et \ mbox {if} a=0?b <0? | a | <| b | \\ (\ Mbox {true}, \ mbox {sub} _N (\ mbox {} SND b) (\ mbox {} SND a)) et \ mbox {if} a <0?b=0? | a | <| b | \\ (\ Mbox {false}, \ mbox {sub} _N (\ mbox {} SND a) (\ mbox {} SND b)) et \ mbox {if} a <0?b=0? | a | = | b | \\ \ End {array} \ right. $$

mais la soustraction est vraiment facile à définir:

$$ \ mbox {} moins _Z = Àa. \ Mbox {} paire (\ mbox {} pas (\ mbox {} fst a)) (\ mbox {} SND a) $$ $$ \ mbox {sub} _Z = ?ab. \ Mbox {} add _Z (a) (\ mbox {} moins _Zb) $$

Une fois que vous avez des nombres entiers positifs et négatifs que vous pouvez définir entiers complexes très facilement: il est juste une paire de deux entiers $ (a, b) $ qui représente $ a + b \ mbox {i} $. Ensuite, l'addition est point sage et la multiplication est comme d'habitude, mais je ne vais pas l'écrire, il devrait être facile :

$$ \ mbox {add} _ {Z [\ mbox {i}]} = ?z_1z_2. \ Mbox {} paire (\ Mbox {} add _Z (\ mbox {} fst z_1) (\ mbox {} fst Z_2)) (\ Mbox {} add _Z (\ mbox {} SND z_1) (\ mbox {} SND Z_2)) $$