Système de programmation fonctionnel

Le terme Functional Programming System (en abrégé FP system ) décrit un concept de langages de programmation fonctionnels développé par John W. Backus . Backus est parti de l'observation que les langages de programmation courants représentent les programmes informatiques comme une manipulation de données sérialisée à petite échelle, car ils sont basés sur le modèle de machine de von Neumann. Selon Backus, cela entraîne deux problèmes. D'une part, que les programmes de von Neumann sont difficiles à paralléliser. D'autre part, qu'il est difficile d'argumenter formellement sur les propriétés des programmes de Von Neumann ou de les transformer. Le système de programmation fonctionnelle résout ces problèmes en construisant un programme à partir d' une composition . Ce faisant, de plus grandes quantités de données structurées sont transmises d'une fonction à l'autre, ce qui permet techniquement un traitement parallèle. Backus a également envisagé de faire de ce mode de fonctionnement la base d'une nouvelle architecture informatique tirant parti de cette possibilité. ${\ style d'affichage P}$${\ displaystyle P = F_ {n} \ circ F_ {n-1} \ circ F_ {n-2} \ circ .. \ circ F_ {1}}$

Dans un discours à l'occasion de la remise des Turing Awards à Backus en 1977, ce dernier a présenté l'idée de systèmes FP. Le titre de la conférence était : La programmation peut-elle être libérée du style von Neumann ? Un style fonctionnel et son algèbre de programmes . Dans un autre essai, Backus a décidé d'utiliser le terme programmation au niveau des fonctions .

Programme fonctionnel de calcul du produit scalaire

Avec le calcul du produit scalaire, Backus donne un exemple instructif pour l'application du Système de Programmation Fonctionnelle .

La fonction ("Inner Product"), qui détermine le produit scalaire de deux vecteurs, est composée du calcul concaténé des trois fonctions et (dans cet ordre), qui s'exprime comme une composition de fonctions comme suit : ${\ IP de style d'affichage}$${\ displaystyle Trans, (\ alpha \ fois)}$${\ style d'affichage (/ +)}$

${\ displaystyle {\ begin {aligned} IP & = (/ +) \ circ (\ alpha \ times) \ circ Trans \ end {aligned}}}$

Voici une fonction qui transpose une matrice . En FP, par exemple, cette relation est notée comme suit pour une matrice : ${\ displaystyle Trans}$${\ displaystyle {\ bigl (} {\ begin {smallmatrix} 3 & 4 \\ 7 & 1 \\ - 1 & 0 \ end {smallmatrix}} {\ bigr)}}$

${\ displaystyle {\ begin {aligned} Trans (<< 3.4>, <7.1>, <- 1.0 >>) & = << 3.7, -1>, <4.1.0 >> \ end {aligned}}}$

Les symboles et désignent les fonctionnelles . Ceux-ci prennent d'autres fonctions pour créer de nouvelles fonctions. In der Form reprend la fonction de multiplication à deux chiffres et fournit une fonction qui s'applique à tous les éléments d'une liste de paires passée. Le résultat du calcul est alors la liste des produits individuels. Dans les langages de programmation modernes, cela est principalement appelé fonctionnel . Backus les nomme aussi . ${\ style d'affichage \ alpha}$${\ style d'affichage /}$${\ style d'affichage (\ alpha \ fois)}$${\ style d'affichage \ alpha}$${\ style d'affichage \ fois}$${\ style d'affichage \ fois}$${\ style d'affichage \ alpha}$mapApplyToAll

La fonction correspond finalement à peu près à la fonction ou à la programmation fonctionnelle habituelle. Backus le nomme , ce qui signifie que l'expression représente une fonction qui insère l'opération entre deux éléments dans une liste donnée . Donc ça s'applique . ${\ style d'affichage /}$reducefoldInsert${\ style d'affichage (/ +)}$${\ style d'affichage +}$${\ style d'affichage (/ +) (<2,3,4>) = 2 + 3 + 4 = 9}$

Le calcul de la fonction produit scalaire est appliqué aux deux vecteurs et peut alors être compris comme suit : ${\ IP de style d'affichage}$${\ style d'affichage <1,2,3>}$${\ style d'affichage <6,5,4>}$

${\ displaystyle {\ begin {aligned} & IP: << 1,2,3>, <6,5,4 >> \\ & = (/ +) \ circ (\ alpha \ times) \ circ trans: < < 1,2,3>, <6,5,4 >> \\ & = (/ +) \ circ (\ alpha \ times) :( trans: << 1,2,3>, <6,5, 4 >>) \\ & = (/ +): ((\ alpha \ fois): << 1,6>, <2,5>, <3,4 >>) \\ & = (/ +): < \ fois : <1,6>, \ fois : <2,5>, \ fois : <3,4 >> \\ & = (/ +) : <6,10,12> \\ & = + : < 6, + : <10.12 >> \\ & = 28 \ end {aligned}}}$

Le processus arithmétique représente ainsi un pipeline de traitement sans état interne, qui convertit l'entrée en sortie en trois étapes de travail distinctes. Les étapes de travail elles-mêmes peuvent être parallélisées à différents degrés. Il serait également possible de créer un pipeline matériel pour le programme . ${\ IP de style d'affichage}$

Notations dans le système FP

Backus utilise une notation qui est vaguement basée sur des conventions mathématiques et la complète avec les expressions conditionnelles de McCarthy et une représentation récursive pour les boucles WHILE. Il est crucial que chaque entité représente une fonction et soit donc compatible avec l' opérateur de composition . ${\ displaystyle \ circ}$

Des nombres comme sélecteurs

Le langage de programmation vectorielle APL a eu une influence décisive sur le système de programmation fonctionnelle basé sur Combinator de John Backus, qui fonctionne sans liste de variables lambda ; à la place, des sélecteurs (nombres) sont utilisés pour choisir des valeurs dans une séquence.

1:<x1,...,xn> → x1i:<x1,...,xi,...,xn> → xi

Nombre fixe de combineurs / formes fonctionnelles

Combinant...	... Façonner
application	f : x	= f (x)
composition	(f o g) : x	= f (g (x))
construction	[ f 1 , f 2 , ... , f n ]  : x	= < f 1 : x , f 2 : x , ... , f n : x >
état	(p → f ; g) : x	= Si p: x = T alors f: x sinon , si p: x = F alors g: x sinon ⊥
constant	~ x : oui	= Si y = ⊥ alors ⊥ sinon x
Insérer	( / f) : < x 1 , x 2 , ..., x n >	= f : < x 1 , f : < x 2 , ... f : < x n-1 , x n >>>
S'applique à tous	( Α f): < x 1 , x 2 , ..., x n >	= < f : x 1 , f : x 2 , ..., f : x n >
Binaire à Unaire	bu fx
Alors que la boucle	( tandis que pf): x	= Si p: x = T puis ( tandis que pf) : (f : x) sinon , si p: x = F , alors x sinon ⊥

et la définition des fonctions monadiques :

Def Name ≡ Term

Avec ⊥ Backus signifiait la valeur « bottom », une valeur comme « undefined » ou « exception ». T et F sont les valeurs pour "vrai" et "faux".

Poursuite du développement des systèmes de PF

Une équipe composée de John Backus, John Williams et Edward Wimmers a développé le successeur FL (Function-Level Programming) au IBM Almaden Research Center en 1989 . Avec ce concept, on devrait être capable de réorganiser les programmes aussi confortablement que l'on peut réarranger les équations en mathématiques, la transparence référentielle devait être garantie pour cela. Cela devrait servir une nouvelle dimension de l'optimisation des programmes (EFL). Avec FL, Backus a voulu faire de « l'informatique d'alors » une discipline d'ingénierie. Encore une fois, d'autres développements de FL sont J (application comme APL) et PLASM, un langage de programmation pour la géométrie.

Implémentations de PF

• FP INTERACTIF, page d'aide pour ce
• Compilateur FP qui se compile en C, repo en
• Interprète Fp en Lisp
• Trivia FP, repo FP à
• Plasm ( P rogrammation La nguage pour S olide M odeling), un langage de programmation fonctionnelle pour une utilisation en CAO , qui , à l' université Roma Tre est développé.

Voir également

• Langage de programmation algébrique

Littérature

• Wolfram-Manfred Lippe : Programmation Fonctionnelle et Applicative : Bases, Langages, Techniques d'Implémentation . 1ère édition. Springer , Berlin 2009, ISBN 978-3-540-89091-1 ( aperçu limité dans la recherche de livres Google). 
• Alberto Paoluzzi ea : Programmation géométrique pour la conception assistée par ordinateur . 1ère édition. Wiley , Chichester 2003, ISBN 978-0-471-89942-6 ( aperçu limité dans Google Recherche de Livres). 

Preuve individuelle

1. ↑ Lippe 2009, p 73.
2. ↑ Can programmation se libérer du von Neumann style? Un style fonctionnel et son algèbre de programmes Université de Stanford, 1978 (PDF; 2,87 Mo)
3. ↑ Programmes de niveau fonctionnel en tant qu'objets mathématiques (PDF)
4. ↑ INTERACTIVE FP
5. ↑ INTERACTVE FP - Aide
6. ↑ Furry Paws , un compilateur FP
7. ↑ fp-interprète en Lisp
8. ↑ interprète FP, créé en Delphi
9. ↑ Langage fonctionnel PLASM pour le calcul avec la géométrie. Alberto Paoluzzi ( Université de Rome III ), consulté le 27 novembre 2010 . 

liens web

• Critique de l'essai Backus d' Edsger W. Dijkstra (PDF; 143 ko)
• John Backus : Programmation au niveau des fonctions et langage FL , 1987 (vidéo)
• Le projet FL : conception d'un langage fonctionnel (PDF; 315 ko)
• Manuel de langue FL, parties 1 et 2 (PDF; 20 Mo)
• Introduction à FL et PLASM (PDF)
• PF (anglais)
• Scripts vers FP Systems