PC & Mobile

Lambda calcul implémenté en dactylographie

Lambda calcul implémenté en dactylographie


Prélude

Ceci est un article sur la programmation typographique et fonctionnelle. Ce n'est pas un article sur la théorie du calcul Lambda.

Nous allons implémenter le calcul Lambda dans Typescript afin d’exercer la programmation fonctionnelle. Nous allons faire cela en résolvant un problème simple en utilisant uniquement des constructions Lambda calcul.

En fin de compte, peut-être que les bases de la théorie seront plus claires.

Le problème et la langue

Le problème à résoudre est simple: si 2 chiffres n et m sont égaux, puis reviennent n + m sinon, retour m - n.

Mais nous avons un langage qui ne nous permet d'utiliser que la construction suivante

x => y // fonction anonyme avec 1 paramètre (c'est-à-dire une fonction unaire) 

X et y peut être tout. X et y peut même être des fonctions, de sorte que ce qui suit est également une construction valide dans notre langage

x => y => z => z (x) (y) // x est le paramètre et la valeur renvoyée est y => z => z (x) (y)

En d’autres termes, pour résoudre le problème, nous n’avons que des fonctions anonymes (fonctions de «grosse flèche», par exemple). Pas de Javascript Nombres, non == ou === opérateurs, non si alors sinon. Juste des fonctions. Rappelez-vous, pour le reste de l'article, que

nous avons juste des fonctions.

Lambda calcul

Le Lambda Calculus nous donne la base théorique pour résoudre ce problème en utilisant seulement des fonctions. En fait, le calcul Lambda résout tout problème informatique en utilisant simplement des fonctions.

Qu'est-ce que le calcul Lambda? Il existe de nombreuses sources qui fournissent de bonnes descriptions. Pour les besoins de cet article, le calcul Lambda est simplement le fait que nous pouvons utiliser uniquement des fonctions anonymes pour résoudre notre problème.

Nous voulons voir ici comment concrétiser ce concept, en mettant en œuvre le calcul Lambda avec Typescript et en résolvant notre problème. Dans le processus, nous utiliserons beaucoup, ou mieux, exclusivement programmation fonctionnelle techniques, depuis

nous avons juste des fonctions.

Considérant que le calcul Lambda est également à la base de la programmation fonctionnelle, alors oui, on peut dire nous allons coder les racines Functional Programming in Typescript.

Le code complet pour la solution du problème et d'autres constructions Lambda calculus peut être trouvé ici.

Nombres sans chiffres

Notre problème commence par 2 chiffres mais nous ne pouvons pas utiliser les nombres Javascript car

nous avons juste des fonctions.

Nous devons donc inventer un moyen de définir le concept de nombre en utilisant des fonctions.

Commençons par dire que les nombres ZERO, ONE et TWO sont représentés respectivement par

ZERO = f => x => x // dans le lambda calcul c'est λf.λx.x
ONE = f => x => f (x) // dans le lambda calcul c'est λf.λx.fx
DEUX = f => x => f (f (x)) // dans le calcul lambda c'est λf.λx.f (fx)

Si F est une fonction et X est une valeur, ZÉRO résultats X jamais appliquer F à tout UN renvoie le résultat de l'application F à X une fois que et DEUX le résultat de l'application F à X deux fois. Donc, en gros, c’est notre convention: un nombre est représenté par combien de fois une fonction F est appliqué à l'argument X.

Donc, le mécanisme est clair. Un numéro n représente l'application d'une fonction F à un argument X n fois. Rappelez-vous ce concept, nous l'utiliserons plus tard. À propos, on appelle cela le codage des nombres par l'église. C'est la convention utilisée par l'inventeur du calcul Lambda, Alonzo Church, pour représenter des nombres naturels.

La fonction successeur

Jusqu'ici, nous avons codé en dur les 3 premiers nombres, mais nous devons trouver un moyen plus flexible, un moyen plus intelligent de définir des nombres. Cette manière nous est fournie par la fonction Successeur

SUCC = n => f => x => f (n (f) (x)) // équivalent à λn.λf.λx.f (nfx)

Ça n'a pas l'air immédiat, non? Mais raisonnons à ce sujet.

Commençons par le cas de n égal à ZÉRO. Si n est ZÉRO (rappelez-vous que ZÉRO a été défini comme f => x => x) que d'appliquer SUCC (n) à ZÉRO, c'est-à-dire en remplaçant n avec la définition de ZÉRO, on a

Substitutions dans SUCC (ZERO) pour atteindre UN

Si on essaye SUCC (ONE) en appliquant la même substitution mécanique que nous obtenons DEUX. ensuite SUCC (DEUX) est TROIS et ainsi de suite.

Quelques mots sur le currying

Nous venons de définir

SUCC = n => f => x => f (n (f) (x))

Pour être pédant on peut dire que SUCCest un une fonction qui prend un paramètre, net retourne un une fonction qui prend un paramètre, Fet retourne un une fonction qui prend un paramètre, Xet fait éventuellement quelque chose avec n F et X.

Donc on peut dire que SUCC est une fonction de 3 paramètres, n F et X et que ces paramètres sont appliqués un à la fois. Cette application partielle de paramètres uniques est appelée currying.

A partir de maintenant, nous parlerons librement des fonctions de m paramètres, avec m ≥ 1, même si derrière ce concept il y a toujours le currying mécanisme puisque les fonctions Lambda par définition sont unaires, c’est-à-dire n’acceptent qu’un seul paramètre.

Ajoutons quelques types

Si nous regardons la structure d'un nombre, tel que défini par notre convention, nous voyons 2 choses

  • un nombre est une fonction qui prend 2 paramètres, F et Xet retourne quelque chose
  • le premier paramètre F elle-même doit être une fonction unaire puisqu'elle peut être appliquée à X dans le corps de chaque numéro

Donc, nous pouvons commencer à définir certains types dans Typescript

tapez uF = (x: any) => any; // fonction unaire
tapez NUMBER = (f: uF) => (x: any) => any; // le type de nombres

Et puis aussi la fonction SUCC peut être tapé

SUCC = (n: NUMBER): NUMBER => (f: uF) => (x: quelconque) => f (n (f) (x));

Dactylographie nous donne la possibilité d’ajouter des types aux définitions de fonctions, ce qui peut nous aider grandement à nous guider, via Intellisense et la vérification des types, en particulier lorsque les problèmes que nous voulons résoudre se compliquent.

Mais si ce sont des «nombres», pouvons-nous les voir comme des nombres normaux?

Le codage d'église pour les nombres consiste à appliquer une fonction à un argument n fois. C'est bien, mais…

Pouvons-nous les voir comme des nombres normaux, comme 0, 1, 2, 36, 49, 112?

Oui nous pouvons. Si on passe comme F une fonction qui incrémente de 1 un nombre Javascript et X Pour le numéro JavaScript 0, nous obtenons le numéro Javascript correspondant au numéro encodé par l'Église, comme on peut le voir dans l'exemple suivant.

Obtenir le codage Javascript de l'église numéro 2

En même temps, si on change la fonction F et la valeur initiale, alors nous pouvons voir nos nombres encodés par l'Église avec différents formats. Ici, par exemple, un numéro d'église n est transformé en une chaîne de n caractères *.

Booléens sans Booléens

Avec les booléens, nous devons faire face au même problème qu'avec les nombres. Nous devons définir Vrai et Faux dans un langage qui n’a pas de tels concepts, un langage où

nous avons juste des fonctions.

Encore une fois, nous revenons à une convention. Voici l'intuition: dans l'opérateur ternaire Javascript, condition? première seconde, Vrai des moyens pour choisir la première option et Faux signifie choisir la seconde.

Nous utilisons ici la même convention, le codage d’Eglise pour les booléens, c’est-à-dire

// TRUE et FALSE sont des fonctions binaires, ils attendent 2 paramètres
TRUE = X => y => X // TRUE renvoie le premier paramètre
FAUX = x => y => y // FALSE renvoie le seconde paramètre

Nous allons maintenant voir comment cette convention s’avère bien fonctionner avec les opérateurs booléens.

La fonction AND

Voyons maintenant comment construire une fonction qui se comporte comme ET, c’est-à-dire qu’il doit s’attendre à deux arguments booléens codés par Church, p et qet retourne VRAI seulement si les deux arguments sont VRAI.

ET doit avoir la forme suivante

AND = p => q => .... // p et q sont des booléens codés par l'Église

p et q sont les seules choses que nous avons, alors nous ferions mieux de les utiliser dans le corps de la fonction.

Nous essayons de commencer la mise en œuvre du corps avec p , qui est elle-même une fonction binaire puisqu'il s'agit d'un booléen encodé par l'église.

AND = p => q => p (_) (_) // p attend 2 arguments

Si p est FAUX , par définition de FAUX il choisit le deuxième argument. Mais si p est FAUX, alors le résultat de ET doit être FAUX et donc le deuxième argument après p doit être FAUX.

AND = p => q => p (_) (FALSE) // si p est faux, le second argument est sélectionné

Si p est VRAI alors par définition de VRAI le premier argument après p est choisi. Mais dans ce cas, le résultat de ET dépend de la valeur de q. Si q est VRAI alors le résultat est VRAI , FAUX autrement. Mais cela signifie que le premier argument après p est q lui-même.

AND = p => q => p (q) (FALSE) // si p est vrai, il sélectionne q comme résultat

Nous pouvons maintenant faire la dernière simplification. Le deuxième argument de p est FAUX et est choisi seulement quand p est FAUX. Ce qui signifie que nous pouvons substituer FAUX avec p pour la version finale de la fonction

ET = p => q => p (q) (p)

Même la version symétrique fonctionne

ET = p => q => q (p) (q)

Avec des méthodes similaires, tous les autres opérateurs booléens peuvent être trouvés.

Nous pouvons ajouter des types aux booléens encodés par Church et tester l'exactitude de notre logique, comme dans cet exemple.

La fonction AND dactylographiée et testée

Comparaisons sans opérateurs de comparaison

Notre problème nous demande de comparer 2 nombres, mais nous n'avons pas d'opérateurs de comparaison comme == ou ===,

nous avons juste des fonctions.

Nous devons trouver une stratégie différente. Ours avec moi sur ce voyage.

Une façon de vérifier si 2 chiffres n et m sont égal est de vérifier si n est lessThanOrEqual à m et m est lessThenOrEqual à n. En supposant que nous ayons une fonction LEQ (m) (n) qui revient VRAI si mest lessThanOrEqual n, on peut alors définir le EQ fonctionne comme

EQ (m) (n) = ET (LEQ (m) (n)) (LEQ (m) (n))

Maintenant, nous devons définir LEQ.

Supposons que nous avons 2 fonctions, SUB et ISZERO, définies comme suit:

  • SUB (m) (n) soustrait n de m de sorte que, si n est supérieur à m , le résultat est toujours ZÉRO sinon, c'est m-n
  • ISZERO (n) résultats VRAI si n est ZÉRO, FAUX autrement

Nous pouvons maintenant exprimer LEQ comme

LEQ (m) (n) = ISZERO (SUB (m) (n))

Eh bien, nous nous retrouvons maintenant avec le problème de la définition EST ZÉRO et SOUS.

Vérifier si un nombre est zéro

EST ZÉRO est une fonction qui attend un nombre codé par l'église comme paramètre. Un numéro encodé par l'église n est elle-même une fonction binaire, et c'est la seule chose qui nous est donnée afin que nous puissions mieux l'utiliser d'une manière ou d'une autre

ISZERO (n) = n (X) (y) // nous devons trouver le bon X et y

Commençons par le cas où n est ZÉRO, c'est à dire. n = f => x => x. ZÉRO par définition, retourne toujours le deuxième paramètre, donc y doit être VRAI.

ISZERO (n) = n (X) (TRUE) // nous devons trouver le bon X pour n pas ZERO

Voyons maintenant n = UN, c'est à dire. n = f => x => f (x). Dans ce cas, F doit toujours revenir FAUX pour toute valeur de X. Ce qui signifie que f = x => FALSE.

Donc finalement EST ZÉRO est

ISZERO (n) = n (x => FALSE) (TRUE)

Nous pouvons le tester avec le code suivant

Soustraire n de m

Si nous avions une fonction PRED (n) qui retourne le prédécesseur de n alors on pourrait dire que pour soustraire n de m est équivalent à appliquer n fois la PRED fonction à m. Mais, si vous vous souvenez de ce que nous avons dit au début lorsque nous avons introduit le codage Church pour les nombres, n elle-même représente l'application d'une fonction F à un argument X n fois. En d'autres termes

SUB (m) (n) = n (PRED) (m)

Maintenant, avec un acte de foi, acceptons la définition suivante de PRED

const PRED = n => f => x => n (g => h => h (g (f))) (u => x) (u => u)

Pour ceux qui sont intéressés, il existe une explication de PRED à la fin de cet article.

Somme n à m

De la même manière que nous avons construit SOUS nous pouvons construire SOMME en utilisant la fonction Successeur comme

SOMME (n) (m) = n (SUCC) (m)

Maintenant nous pouvons construire la solution

Est-ce qu'on se souvient encore du problème initial?

si (n = m) {
retourne n + m; // retourne la somme si n et m sont égaux
} autre {
retourne n - m; // retourne la différence si elle n'est pas égale
}

Maintenant, nous avons tous les outils pour le résoudre avec un langage où

nous avons juste des fonctions ..

Regarde ça

EQ (n) (m) // renvoie VRAI si n et m sont égaux, FAUX sinon
(SUM (n) (m)) // argument choisi si EQ renvoie TRUE
(SUB (n) (m)) // argument choisi si EQ renvoie FALSE

C’est exactement la solution à notre problème, comme le prouve le code suivant:

Plus de détails et de tests peuvent être vus dans le repo.

À propos, si nous substituons EQ SOMME SOUS et tout le reste des définitions que nous avons ajoutées par souci de commodité, le code de notre solution est le suivant:

Code de solution affichant uniquement des fonctions anonymes

Enfin: qu’en est-il pour un programmeur fonctionnel?

Nous avons joué juste avec des fonctions. Nous les avons définis, passés en arguments, attendus en paramètres, évalués. Nous nous sommes familiarisés avec eux pour les utiliser comme citoyens de première classe dans notre code.

Nous avons effectué des exercices qui nous ont aidés à comprendre la dynamique et les mécanismes d’utilisation des fonctions avec une approche de programmation fonctionnelle.

Par exemple, si nous voyons cela

FLIP = f => a => b => f (b) (a)

nous comprenons que c'est une façon d'utiliser F avec l'ordre des paramètres inversé. Et un équivalent FLIP peut être trouvé dans lodash et Rambda bibliothèques. Les autres magies implémentées par les bibliothèques de PF devraient maintenant être plus claires. Si tel est le cas, nous avons atteint l'objectif de cet article.

Pour ceux qui sont vraiment intéressés: comment construire la fonction PRED en utilisant des paires

Qu'est-ce que c'est?

x => y => f => f (x) (y)

C'est un paire, un vecteur à 2 dimensions., en fait, le moyen de coder un paire avec des fonctions.

Considérer ce qui suit

const PAIR = x => y => f => f (x) (y);
const myPair = PAIR (1) (2);

myPair est une structure qui contient 1 et 2 comme ses valeurs immuables. Nous avons juste besoin de passer une fonction à myPair pour spécifier ce que nous voulons faire avec ses valeurs.

Une paire de n et m peut être défini en utilisant la notation (n, m).

Si nous voulons obtenir la deuxième valeur d'un paire, nous pouvons simplement passer la fonction FALSE au paire

SECOND = p => p (FALSE) // où p est un paire

comme nous pouvons le tester avec le code suivant

De même, la fonction PREMIER est

FIRST = = p => p (VRAI) // où p est un paire

Nous pouvons maintenant définir une autre fonction, PHI, comme suit

PHI = p => PAIRE (SECONDE (p)) (SUCCESSEUR (SECONDE (p))) // p est une paire

PHI transforme le paire (m, n) dans un nouveau paire (n, n + 1).

Alors,

  • PHI (0,0) résultats (0,1)
  • PHI (PHI (0,0)) équivaut à PHI (0,1) qui retourne (1,2)
  • PHI (PHI (PHI (0,0) équivaut à PHI (1,2) qui retourne (2,3)

En extrapolant on peut dire que n applications de PHI à (0,0) retourner le paire (n-1, n). Ce qui conduit à la définition de PRED comme

PRED = n => PREMIER (n (PHI) (PAIRE (ZERO) (ZERO)))

Il existe d'autres moyens de construire la fonction PRED, mais c'est probablement la plus naturelle à suivre.

Remerciements

Cet article s’inspire de 2 excellents discours de Gabriel Lebec (@glebec) «Lambda Calculus» et «Un groupe de fonctions». Je recommande vraiment à toute personne intéressée par l'argument de l'observer attentivement.

Show More

SupportIvy

SupportIvy.com : Un lieu pour partager le savoir et mieux comprendre le monde. Meilleure plate-forme de support gratuit pour vous, Documentation &Tutoriels par les experts.

Related Articles

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Close
Close