comment un langage de programmation purement fonctionnel se gère sans instructions d'affectation?

En lisant le célèbre SICP, j'ai trouvé que les auteurs semblent plutôt réticents à introduire la déclaration d'affectation dans Scheme au chapitre 3. J'ai lu le texte et je comprends en quelque sorte pourquoi ils le ressentent.

Comme Scheme est le premier langage de programmation fonctionnel sur lequel je connaisse quelque chose, je suis un peu surpris qu'il existe des langages de programmation fonctionnels (pas Scheme bien sûr) qui peuvent se passer d'affectations.

Prenons l'exemple du livre, l' bank accountexemple. S'il n'y a pas de déclaration d'affectation, comment faire? Comment changer la balancevariable? Je le demande parce que je sais qu'il existe des soi-disant langages fonctionnels purs et que, selon la théorie complète de Turing, cela peut aussi être fait.

J'ai appris le C, Java, Python et j'utilise beaucoup de devoirs dans chaque programme que j'ai écrit. C'est donc vraiment une expérience révélatrice. J'espère vraiment que quelqu'un pourra expliquer brièvement comment les affectations sont évitées dans ces langages de programmation fonctionnels et quel impact profond (le cas échéant) cela a sur ces langages.

L'exemple mentionné ci-dessus est ici:

(define (make-withdraw balance)
    (lambda (amount)
        (if (>= balance amount)
            (begin (set! balance (- balance amount))
                balance)
            "Insufficient funds")))

Cela a changé le balanceby set!. Pour moi, cela ressemble beaucoup à une méthode de classe pour changer le membre de la classe balance.

Comme je l'ai dit, je ne connais pas les langages de programmation fonctionnels, donc si je dis quelque chose de mal à leur sujet, n'hésitez pas à le signaler.

S'il n'y a pas de déclaration d'affectation, comment faire? Comment changer la variable de solde?

Vous ne pouvez pas modifier des variables sans une sorte d'opérateur d'affectation.

Je le demande parce que je sais qu'il existe des soi-disant langages fonctionnels purs et que, selon la théorie complète de Turing, cela peut aussi être fait.

Pas assez. Si une langue est Turing complete, cela signifie qu'elle peut calculer tout ce que n'importe quelle autre langue Turing complete peut calculer. Cela ne signifie pas qu'il doit avoir toutes les fonctionnalités des autres langues.

Ce n'est pas une contradiction qu'un langage de programmation complet Turing n'a aucun moyen de changer la valeur d'une variable, tant que pour chaque programme qui a des variables mutables, vous pouvez écrire un programme équivalent qui n'a pas de variables mutables (où "équivalent" signifie qu'il calcule la même chose). Et en fait, chaque programme peut être écrit de cette façon.

Concernant votre exemple: dans un langage purement fonctionnel, vous ne pourriez tout simplement pas écrire une fonction qui retourne un solde de compte différent à chaque appel. Mais vous seriez toujours en mesure de réécrire chaque programme, qui utilise une telle fonction, d'une manière différente.

Puisque vous avez demandé un exemple, considérons un programme impératif qui utilise votre fonction make -draw (en pseudo-code). Ce programme permet à l'utilisateur de retirer un compte, d'y déposer ou d'interroger le montant d'argent sur le compte:

account = make-withdraw(0)
ask for input until the user enters "quit"
    if the user entered "withdraw $x"
        account(x)
    if the user entered "deposit $x"
        account(-x)
    if the user entered "query"
        print("The balance of the account is " + account(0))

Voici un moyen d'écrire le même programme sans utiliser de variables mutables (je ne m'embêterai pas avec des E / S référentiellement transparentes car la question n'était pas à ce sujet):

function IO_loop(balance):
    ask for input
    if the user entered "withdraw $x"
        IO_loop(balance - x)
    if the user entered "deposit $x"
        IO_loop(balance + x)
    if the user entered "query"
        print("The balance of the account is " + balance)
        IO_loop(balance)
    if the user entered "quit"
        do nothing

 IO_loop(0)

La même fonction pourrait également être écrite sans utiliser de récursivité en utilisant un repli sur l'entrée utilisateur (ce qui serait plus idiomatique que la récursivité explicite), mais je ne sais pas si vous êtes encore familier avec les plis, donc je l'ai écrit dans un façon qui n'utilise rien que vous ne sachiez pas encore.

Vous avez raison, cela ressemble beaucoup à une méthode sur un objet. C'est parce que c'est essentiellement ce que c'est. La lambdafonction est une fermeture qui tire la variable externe balancedans sa portée. Avoir plusieurs fermetures qui se ferment sur les mêmes variables externes et avoir plusieurs méthodes sur le même objet sont deux abstractions différentes pour faire exactement la même chose, et l'une ou l'autre peut être implémentée en fonction de l'autre si vous comprenez les deux paradigmes.

La façon dont les langages fonctionnels purs gèrent l'état est la triche. Par exemple, dans Haskell si vous voulez lire l'entrée d'une source externe (ce qui n'est pas déterministe, bien sûr, et ne donnera pas nécessairement le même résultat deux fois si vous le répétez), il utilise une astuce monade pour dire "nous avons a obtenu cette autre variable de simulation qui représente l'état du reste du monde entier , et nous ne pouvons pas l'examiner directement, mais la lecture de l'entrée est une fonction pure qui prend l'état du monde extérieur et renvoie l'entrée déterministe de cet état exact restituera toujours, plus le nouvel état du monde extérieur. " (C'est une explication simplifiée, bien sûr. Lire sur la façon dont cela fonctionne réellement va sérieusement casser votre cerveau.)

Ou dans le cas de votre problème de compte bancaire, au lieu d'attribuer une nouvelle valeur à la variable, il peut renvoyer la nouvelle valeur comme résultat de la fonction, puis l'appelant doit la traiter dans un style fonctionnel, généralement en recréant toutes les données qui fait référence à cette valeur avec une nouvelle version contenant la valeur mise à jour. (Ce n'est pas une opération aussi volumineuse que cela pourrait paraître si vos données sont configurées avec le bon type d'arborescence.)

Les "opérateurs à affectations multiples" sont un exemple d'une caractéristique de langage qui, d'une manière générale, a des effets secondaires et est incompatible avec certaines propriétés utiles des langages fonctionnels (comme l'évaluation paresseuse).

Cela ne signifie cependant pas que l'affectation en général est incompatible avec un style de programmation purement fonctionnel (voir cette discussion par exemple), ni que vous ne pouvez pas construire de syntaxe qui autorise des actions qui ressemblent à des affectations en général, mais sont mis en œuvre sans effets secondaires. Cependant, créer ce type de syntaxe et y écrire des programmes efficaces est long et difficile.

Dans votre exemple spécifique, vous avez raison - l'ensemble! opérateur est une affectation. Ce n'est pas un opérateur libre d'effets secondaires, et c'est un endroit où Scheme rompt avec une approche purement fonctionnelle de la programmation.

En fin de compte, toute langue purement fonctionnelle va devoir rompre avec l'approche parfois purement fonctionnelle - la grande majorité des programmes utiles n'ont des effets secondaires. La décision de savoir où le faire est généralement une question de commodité, et les concepteurs de langage tenteront de donner au programmeur la plus grande flexibilité pour décider où rompre avec une approche purement fonctionnelle, en fonction de leur programme et de leur domaine de problème.

Dans un langage purement fonctionnel, on programmerait un objet de compte bancaire comme fonction de transformateur de flux. L'objet est considéré comme une fonction d'un flux infini de demandes des propriétaires de compte (ou de quiconque) à un flux potentiellement infini de réponses. La fonction démarre avec un solde initial et traite chaque demande dans le flux d'entrée pour calculer un nouveau solde, qui est ensuite renvoyé à l'appel récursif pour traiter le reste du flux. (Je me souviens que le SICP discute du paradigme du transformateur de flux dans une autre partie du livre.)

Une version plus élaborée de ce paradigme est appelée "programmation réactive fonctionnelle" discutée ici sur StackOverflow .

La façon naïve de faire des transformateurs de flux a quelques problèmes. Il est possible (en fait, assez facile) d'écrire des programmes bogués qui conservent toutes les anciennes demandes, gaspillant de l'espace. Plus sérieusement, il est possible de faire dépendre la réponse à la demande en cours de demandes futures. Des solutions à ces problèmes sont en cours d'élaboration. Neel Krishnaswami est la force derrière eux.

Avertissement : je n'appartiens pas à l'église de la programmation fonctionnelle pure. En fait, je n'appartiens à aucune église :-)

Il n'est pas possible de rendre un programme 100% fonctionnel s'il est censé faire quelque chose d'utile. (Si les effets secondaires ne sont pas nécessaires, alors la pensée entière aurait pu être réduite à un temps de compilation constant) Comme l'exemple de retrait, vous pouvez rendre la plupart des procédures fonctionnelles mais vous aurez éventuellement besoin de procédures qui ont des effets secondaires sortie sur console). Cela dit, vous pouvez rendre la plupart de votre code fonctionnel et cette partie sera facile à tester, même automatiquement. Ensuite, vous créez un code impératif pour faire l'entrée / sortie / base de données / ... qui nécessiterait un débogage, mais en gardant la plupart du code propre, ce ne sera pas trop de travail. Je vais utiliser votre exemple de retrait:

(define +no-founds+ "Insufficient funds")

;; functional withdraw
(define (make-withdraw balance amount)
    (if (>= balance amount)
        (- balance amount)
        +no-founds+))

;; functional atm loop
(define (atm balance thunk)
  (let* ((amount (thunk balance)) 
         (new-balance (make-withdraw balance amount)))
    (if (eqv? new-balance +no-founds+)
        (cons +no-founds+ '())
        (cons (list 'withdraw amount 'balance new-balance) (atm new-balance thunk)))))

;; functional balance-line -> string 
(define (balance->string x)
  (if (eqv? x +no-founds+)
      (string-append +no-founds+ "\n")
      (if (null? x)
          "\n"
          (let ((first-token (car x)))
            (string-append
             (cond ((symbol? first-token) (symbol->string first-token))
                   (else (number->string first-token)))
             " "
             (balance->string (cdr x)))))))

;; functional thunk to test  
(define (input-10 x) 10) ;; define a purly functional input-method

;; since all procedures involved are functional 
;; we expect the same result every time.
;; we use this to test atm and make-withdraw
(apply string-append (map balance->string (atm 100 input-10)))

;; no program can be purly functional in any language.
;; From here on there are imperative dirty procedures!

;; A procedure to get input from user is needed. 
;; Side effects makes it imperative
(define (user-input balance)
  (display "You have $")
  (display balance)
  (display " founds. How much to withdraw? ")
  (read))

;; We need a procedure to print stuff to the console 
;; as well. Side effects makes it imperative
(define (pretty-print-result x)
  (for-each (lambda (x) (display (balance->string x))) x))

;; use imperative procedure with atm.
(pretty-print-result (atm 100 user-input))

Il est possible de faire la même chose dans presque toutes les langues et de produire les mêmes résultats (moins de bugs), bien que vous deviez définir des variables temporaires dans une procédure et même muter des choses, mais cela n'a pas d'importance tant que la procédure agit réellement fonctionnel (les paramètres seuls déterminent le résultat). Je crois que vous devenez un meilleur programmeur dans n'importe quelle langue après avoir programmé un peu LISP :)

L'affectation est une mauvaise opération car elle divise l'espace d'état en deux parties, avant et après affectation. Cela entraîne des difficultés à suivre la façon dont les variables sont modifiées pendant l'exécution du programme. Les éléments suivants dans les langages fonctionnels remplacent les affectations:

1. Paramètres de fonction liés directement aux valeurs de retour
2. choisir différents objets à renvoyer au lieu de modifier des objets existants.
3. création de nouvelles valeurs évaluées paresseux
4. listant tous les objets possibles , pas seulement ceux qui doivent être en mémoire
5. pas d'effets secondaires