Aujourd'hui, nous terminons notre série d'articles sur la programmation fonctionnelle. Il s'est avéré 11 parties. Je pense que c'est une réussite. Dans cet article, nous implémentons une simple calculatrice de pile (également connue sous le nom de «notation polonaise inversée»). L'implémentation est presque entièrement basée sur des fonctions, avec un seul type spécial, et généralement sans comparaison avec l'échantillon, c'est donc un excellent terrain d'essai pour les concepts couverts dans notre série.
Je tiens à remercier @kleidemos séparément. C'est lui qui a été le principal traducteur et gestionnaire de toute la série d'articles. Je vous remercie!
Si vous n'êtes pas familier avec une telle calculatrice, cela fonctionne comme suit: les nombres sont poussés dans la pile et les opérations, telles que l'addition et la multiplication, choisissent des nombres en haut de la pile, puis remettent le résultat de l'opération.
Schéma de calcul simple sur la pile:
Avant de concevoir un tel système, vous devez vous demander comment il sera utilisé. En suivant une syntaxe semblable à Forth, nous donnerons à chaque action une étiquette appropriée afin que dans l'exemple ci-dessus, vous puissiez écrire quelque chose comme:
EMPTY ONE THREE ADD TWO MUL SHOW
Il est peut-être impossible d'obtenir exactement cette syntaxe, mais essayons de nous rapprocher le plus possible de cela.
Type de données de pile
Tout d'abord, vous devez définir la structure de données de la pile. Pour plus de simplicité, vous pouvez utiliser une liste de nombres à virgule flottante.
type Stack = float list
Mais il vaut mieux l'encapsuler dans un seul type d'union pour rendre le type plus visuel, comme ceci:
type Stack = StackContents of float list
Pourquoi est-il préférable de faire exactement cela, vous pouvez lire ici .
Créez maintenant une nouvelle pile en utilisant StackContents comme constructeur:
let newStack = StackContents [1.0;2.0;3.0]
Pour extraire le contenu d'une pile existante, utilisez le modèle correspondant à StackContents :
let (StackContents contents) = newStack // "contents" // float list = [1.0; 2.0; 3.0]
Fonction push
Ensuite, nous avons besoin d'un moyen de mettre des nombres sur cette pile. Pour ce faire, ajoutez simplement une nouvelle valeur en haut de la liste en utilisant " :: ".
Exemple de fonction:
let push x aStack = let (StackContents contents) = aStack let newContents = x::contents StackContents newContents
Cette fonctionnalité a un certain nombre de fonctionnalités qui méritent d'être discutées.
Tout d'abord, vous devez faire attention au fait que la structure de la list est immuable, ce qui signifie que la fonction doit prendre une pile existante et en retourner une nouvelle. Ce n'est pas seulement un changement dans une pile existante. En fait, toutes les fonctions de cet exemple auront un format similaire:
Input: Stack - Output: Stack
Deuxièmement, pourquoi les paramètres vont-ils dans cet ordre? Pourquoi la pile devrait-elle commencer ou durer? Dans la section sur la conception de fonctions avec application partielle, il a été dit que le paramètre le plus fréquemment modifié devait durer en dernier. Il sera bientôt possible de vérifier que ces recommandations sont suivies.
Enfin, la fonction peut être rendue plus concise en faisant correspondre le motif dans le paramètre de fonction lui-même, au lieu de la let dans le corps de la fonction.
La version réécrite:
let push x (StackContents contents) = StackContents (x::contents)
Bien mieux!
Au fait, regardez sa signature gracieuse:
val push : float -> Stack -> Stack
Comme mentionné précédemment , la signature nous en dit long.
Dans ce cas, je pourrais deviner ce que fait cette fonction, uniquement par sa signature, sans même savoir qu'elle s'appelle "push".
C'est une autre raison pour laquelle il était judicieux d'avoir des noms de type explicites. Si la pile n'était qu'une liste de nombres à virgule flottante, la fonction ne serait pas si auto-documentée.
D'une manière ou d'une autre, vérifiez:
let emptyStack = StackContents [] let stackWith1 = push 1.0 emptyStack let stackWith2 = push 2.0 stackWith1
Fonctionne très bien!
Stack top exposant utilisant push
Avec cette fonction simple, vous pouvez facilement définir une opération qui pousse un nombre spécifique sur la pile.
let ONE stack = push 1.0 stack let TWO stack = push 2.0 stack
Mais attendez une minute! Vous voyez que le paramètre de stack est mentionné des deux côtés de l'expression? En fait, il n'est pas nécessaire de le mentionner deux fois. Au lieu de cela, vous pouvez omettre le paramètre et écrire une fonction avec une application partielle:
let ONE = push 1.0 let TWO = push 2.0 let THREE = push 3.0 let FOUR = push 4.0 let FIVE = push 5.0
Maintenant, il est évident que si la fonction push avait un ordre de paramètres différent, la stack devrait être mentionnée deux fois.
Il convient également de définir une fonction qui crée une pile vide:
let EMPTY = StackContents []
Vérifiez les fonctions reçues:
let stackWith1 = ONE EMPTY let stackWith2 = TWO stackWith1 let stackWith3 = THREE stackWith2
Ces piles intermédiaires sont-elles ennuyeuses? Est-il possible de s'en débarrasser? Bien sûr! Notez que les fonctions ONE, TWO et THREE ont la même signature:
Stack -> Stack
Ainsi, ils sont parfaitement connectés entre eux! La sortie d'une fonction peut être entrée dans les éléments suivants:
let result123 = EMPTY |> ONE |> TWO |> THREE let result312 = EMPTY |> THREE |> ONE |> TWO
Sauter hors de la pile
Avec l'ajout à la pile compris, mais qu'en est-il de la fonction pop ?
Lors de la récupération de la pile, il est évidemment nécessaire de retourner le haut de la pile, mais est-ce juste cela?
Dans un style orienté objet, la réponse est oui . Mais dans le cas de la POO, la pile serait modifiée dans les coulisses, de sorte que l'élément supérieur serait supprimé.
Cependant, dans un style fonctionnel, la pile est immuable. Il n'y a qu'une seule façon de supprimer l'élément supérieur - créer une nouvelle pile sans cet élément. Pour que l'appelant ait accès à la nouvelle pile réduite, elle doit être renvoyée avec l'élément supérieur.
En d'autres termes, la fonction pop doit renvoyer deux valeurs, l'élément supérieur et la nouvelle pile. La façon la plus simple de le faire en F # est simplement d'utiliser un tuple.
Réalisation:
/// /// let pop (StackContents contents) = match contents with | top::rest -> let newStack = StackContents rest (top,newStack)
La fonction résultante est également très simple.
Comme précédemment, le contents extrait directement du paramètre.
Ensuite, le contenu du contents vérifié à l'aide de l'expression match..with .
Ensuite, l'élément supérieur est séparé du reste de la liste, une nouvelle pile est créée sur la base des éléments restants, et finalement tout cela est retourné sous la forme d'une paire de tuple.
Essayez d'exécuter ce code et voyez ce qui se passe. Vous obtiendrez une erreur de compilation!
Le compilateur a détecté un cas qui n'a pas été résolu - que se passe-t-il si la pile est vide?
Vous devez décider comment le gérer.
Je préfère généralement utiliser un état spécial pour l'erreur, mais dans ce cas particulier, j'ai préféré lever une exception. Version fixe de pop avec gestion des cas vides:
let pop (StackContents contents) = match contents with | top::rest -> let newStack = StackContents rest (top,newStack) | [] -> failwith "Stack underflow"
Vérifier:
let initialStack = EMPTY |> ONE |> TWO let popped1, poppedStack = pop initialStack let popped2, poppedStack2 = pop poppedStack
et test d'exception:
let _ = pop EMPTY
Fonctions arithmétiques
Maintenant que l'ajout et la suppression sont en place, vous pouvez commencer à travailler avec les fonctions "ajouter" et "multiplier":
let ADD stack = let x,s = pop stack // let y,s2 = pop s // let result = x + y // push result s2 // let MUL stack = let x,s = pop stack // let y,s2 = pop s // let result = x * y // push result s2 //
Test en ligne:
let add1and2 = EMPTY |> ONE |> TWO |> ADD let add2and3 = EMPTY |> TWO |> THREE |> ADD let mult2and3 = EMPTY |> TWO |> THREE |> MUL
Ça marche!
Refactoring du temps ...
De toute évidence, une quantité importante de code est dupliquée dans ces deux fonctions. Comment pouvons-nous résoudre ce problème?
Les deux fonctions extraient deux valeurs de la pile, leur appliquent une certaine fonction binaire, puis repoussent le résultat sur la pile. Vous pouvez sortir le code général dans la fonction binaire, qui prend une fonction mathématique avec deux paramètres:
let binary mathFn stack = // let y,stack' = pop stack // let x,stack'' = pop stack' // let z = mathFn xy // push z stack''
Notez que dans cette implémentation, différentes versions du «même» objet sont marquées avec un nombre différent de guillemets. En effet, les suffixes numériques peuvent facilement prêter à confusion.
Question: pourquoi les paramètres ont-ils exactement cet ordre, au lieu que mathFn vienne après la stack ?
Maintenant que vous avez une fonction binary , il est beaucoup plus facile de définir ADD et d'autres fonctions:
Première tentative d'implémentation d'ADD à l'aide du binary :
let ADD aStack = binary (fun xy -> x + y) aStack
Mais vous pouvez vous débarrasser de lambda, car il représente la définition exacte de la fonction intégrée + :
let ADD aStack = binary (+) aStack
Encore une fois, une application partielle peut être utilisée pour masquer le paramètre de pile. Définition finale:
let ADD = binary (+)
Définition d'autres fonctions mathématiques:
let SUB = binary (-) let MUL = binary (*) let DIV = binary (../)
Essayez-le en ligne:
let div2by3 = EMPTY |> THREE|> TWO |> DIV let sub2from5 = EMPTY |> TWO |> FIVE |> SUB let add1and2thenSub3 = EMPTY |> ONE |> TWO |> ADD |> THREE |> SUB
De même, vous pouvez créer une fonction auxiliaire pour les opérations unaires
let unary f stack = let x,stack' = pop stack push (fx) stack'
Et définissez quelques fonctions unaires:
let NEG = unary (fun x -> -x) let SQUARE = unary (fun x -> x * x)
Mode interactif:
let neg3 = EMPTY |> THREE|> NEG let square2 = EMPTY |> TWO |> SQUARE
Mettre tout cela ensemble | Tout mettre ensemble
Dans les exigences initiales, il a été mentionné que nous aimerions pouvoir afficher les résultats, il convient donc de définir la fonction SHOW.
let SHOW stack = let x,_ = pop stack printfn "The answer is %f" x stack //
Veuillez noter que dans ce cas, la nouvelle version de la pile reçue via pop est ignorée. Le résultat final est la pile d'origine, comme si elle n'avait jamais changé.
Enfin, vous pouvez écrire l'exemple suivant à partir des exigences d'origine
EMPTY |> ONE |> THREE |> ADD |> TWO |> MUL |> SHOW
Continuez
C'est amusant, mais que pouvez-vous faire d'autre?
Vous pouvez définir plusieurs fonctions supplémentaires:
/// let DUP stack = // let x,_ = pop stack // push x stack /// let SWAP stack = let x,s = pop stack let y,s' = pop s push y (push x s') /// let START = EMPTY
En utilisant ces fonctions supplémentaires, vous pouvez écrire quelques exemples élégants:
START |> ONE |> TWO |> SHOW START |> ONE |> TWO |> ADD |> SHOW |> THREE |> ADD |> SHOW START |> THREE |> DUP |> DUP |> MUL |> MUL // 27 START |> ONE |> TWO |> ADD |> SHOW // 3 |> THREE |> MUL |> SHOW // 9 |> TWO |> SWAP |> DIV |> SHOW // 9 div 2 = 4.5
Utiliser la composition au lieu du pipelining
Mais ce n'est pas tout. En fait, il existe une autre façon intéressante de représenter ces fonctions.
Comme indiqué précédemment, ils ont tous la même signature:
Stack -> Stack
Étant donné que l'entrée et la sortie sont du même type, ces fonctions peuvent également être combinées à l'aide de l'opérateur de composition >> , et pas seulement via des opérateurs pipelinés.
Quelques exemples:
// let ONE_TWO_ADD = ONE >> TWO >> ADD START |> ONE_TWO_ADD |> SHOW // let SQUARE = DUP >> MUL START |> TWO |> SQUARE |> SHOW // let CUBE = DUP >> DUP >> MUL >> MUL START |> THREE |> CUBE |> SHOW // let SUM_NUMBERS_UPTO = DUP // n >> ONE >> ADD // n+1 >> MUL // n(n+1) >> TWO >> SWAP >> DIV // n(n+1) / 2 START |> THREE |> SQUARE |> SUM_NUMBERS_UPTO |> SHOW
Dans chacun de ces exemples, une nouvelle fonction est définie à l'aide d'une composition d'autres fonctions. C'est un bon exemple d'une approche «combinatoire» de la fonctionnalité de construction.
Convoyeurs vs composition
Nous avons vu deux façons différentes d'utiliser notre modèle; utilisant des convoyeurs et une composition. Mais quelle est la différence? Et pourquoi préférer l'un à l'autre?
La différence est que les pipelines sont, en un sens, une opération de «transformation en temps réel». Au moment de l'utilisation du pipeline, les opérations sont effectuées immédiatement, via le transfert d'une pile spécifique.
D'un autre côté, la composition est quelque chose comme un «plan» que nous voulons implémenter, créant des fonctions à partir d'un ensemble de composants sans application directe.
Par exemple, vous pouvez créer un «plan» pour calculer le carré d'un nombre grâce à une combinaison de petites opérations:
let COMPOSED_SQUARE = DUP >> MUL
Je ne peux pas donner l'équivalent basé sur les pipelines.
let PIPED_SQUARE = DUP |> MUL
Cela entraînera une erreur de compilation. J'ai besoin d'une instance de pile spécifique pour que l'expression fonctionne:
let stackWith2 = EMPTY |> TWO let twoSquared = stackWith2 |> DUP |> MUL
Et même dans ce cas, je peux obtenir une réponse uniquement pour cette entrée particulière, et non un plan de calcul généralisé basé sur une entrée, comme dans l'exemple avec COMPOSED_SQUARE .
Une autre façon de créer un «plan» consiste à passer explicitement le lambda à des fonctions plus primitives:
let LAMBDA_SQUARE = unary (fun x -> x * x)
C'est une manière plus explicite (et probablement plus rapide), mais tous les avantages et la clarté de l'approche compositionnelle sont perdus.
En général, si possible, vous devez vous efforcer d'adopter une approche compositionnelle!
Code complet
Code complet pour tous les exemples ci-dessus:
// ============================================== // // ============================================== type Stack = StackContents of float list // ============================================== // // ============================================== /// let push x (StackContents contents) = StackContents (x::contents) /// /// let pop (StackContents contents) = match contents with | top::rest -> let newStack = StackContents rest (top,newStack) | [] -> failwith "Stack underflow" // ============================================== // () // ============================================== // // // let binary mathFn stack = let y,stack' = pop stack let x,stack'' = pop stack' let z = mathFn xy push z stack'' // // // let unary f stack = let x,stack' = pop stack push (fx) stack' // ============================================== // () // ============================================== /// let SHOW stack = let x,_ = pop stack printfn "The answer is %f" x stack // /// let DUP stack = let x,s = pop stack push x (push xs) /// let SWAP stack = let x,s = pop stack let y,s' = pop s push y (push x s') /// let DROP stack = let _,s = pop stack // s // // ============================================== // , // ============================================== // // ------------------------------- let EMPTY = StackContents [] let START = EMPTY // // ------------------------------- let ONE = push 1.0 let TWO = push 2.0 let THREE = push 3.0 let FOUR = push 4.0 let FIVE = push 5.0 // // ------------------------------- let ADD = binary (+) let SUB = binary (-) let MUL = binary (*) let DIV = binary (../) let NEG = unary (fun x -> -x) // ============================================== // , // ============================================== let SQUARE = DUP >> MUL let CUBE = DUP >> DUP >> MUL >> MUL let SUM_NUMBERS_UPTO = DUP // n >> ONE >> ADD // n+1 >> MUL // n(n+1) >> TWO >> SWAP >> DIV // n(n+1) / 2
Conclusion
Nous avons une simple calculatrice basée sur la pile. Nous avons vu comment, en commençant par quelques opérations primitives ( push , pop , binary , unary ) et d'autres, vous pouvez créer une DSL à part entière, facile à implémenter et à utiliser.
Comme vous pouvez le deviner, cet exemple était à peu près basé sur la langue Forth. Je recommande fortement le livre gratuit "Thinking Forth" , qui parle non seulement du langage Forth, mais aussi d'autres méthodes ( non orientées objet!) Pour décomposer des tâches qui sont également applicables à la programmation fonctionnelle en général.
J'ai eu l'idée de cet article sur le magnifique blog d' Ashley Feniello . Si vous souhaitez approfondir l'émulation d'un langage basé sur la pile basé sur F #, commencez par celui-ci. Amuse toi bien!
Ressources supplémentaires
Il existe de nombreux didacticiels pour F #, y compris des documents pour ceux qui viennent avec une expérience C # ou Java. Les liens suivants peuvent être utiles pour approfondir F #:
Plusieurs autres façons de commencer à apprendre le F # sont également décrites.
Enfin, la communauté F # est très conviviale pour les débutants. Il y a un chat très actif chez Slack, soutenu par la F # Software Foundation, avec des salles pour débutants que vous pouvez rejoindre librement . Nous vous recommandons fortement de le faire!
N'oubliez pas de visiter le site de la communauté russophone F # ! Si vous avez des questions sur l'apprentissage d'une langue, nous serons heureux d'en discuter dans les salles de chat:
À propos des auteurs de traduction
Traduit par @kleidemos
La traduction et les modifications éditoriales ont été apportées par les efforts de la communauté russophone des développeurs F # . Nous remercions également @schvepsss et @shwars d' avoir préparé cet article pour publication.