Programmation Fonctions calculables – Wikipedia wiki

Posted on by
before-content-x4

Un article de Wikipédia, l’encyclopédie libre

after-content-x4

Un langage fonctionnel tapé

En informatique, Programmation des fonctions calculables (PCF) est un langage fonctionnel tapé introduit par Gordon Plotkin en 1977, [d’abord] Basé sur des documents précédents non publiés par Dana Scott. [note 1] Il peut être considéré comme une version étendue du calcul Lambda tapé ou une version simplifiée des langages fonctionnels dactylographiques modernes tels que ML ou Haskell.

Un modèle entièrement abstrait pour PCF a été donné pour la première fois par Robin Milner. [2] Cependant, comme le modèle de Milner était essentiellement basé sur la syntaxe de PCF, il était considéré comme moins que satisfaisant. [3] Les deux premiers modèles entièrement abstraits n’utilisant pas de syntaxe ont été formulés au cours des années 1990. Ces modèles sont basés sur la sémantique de jeu [4] [5] et les relations logiques Kripke. [6] Pendant un certain temps, il a été estimé qu’aucun de ces modèles n’était complètement satisfaisant, car ils n’étaient pas efficacement présentables. Cependant, le chargeur Ralph a démontré qu’aucun modèle entièrement abstrait efficacement présentable ne pouvait exister, car la question de l’équivalence du programme dans le fragment finitaire du PCF n’est pas décideable. [7]

Le les types de PCF est défini par induction comme

  • nat est un type
  • Pour les types un et T , il y a un type un → T

UN contexte est une liste de paires X: P , où X est un nom variable et un est un type, tel qu’aucun nom de variable n’est dupliqué. On définit ensuite les jugements de saisie des termes en contexte de la manière habituelle pour les constructions syntaxiques suivantes:

after-content-x4
  • Variables (si X: P fait partie d’un contexte C , alors C ⊢ X : un )
  • Application (d’un terme de type un → T à un terme de type un )
  • Λ-abstraction
  • Le ET Combinateur à points fixe (fabrication des termes de type un hors des conditions de type un → un )
  • Le successeur ( succ ) et le prédécesseur ( avant ) opérations sur nat et la constante 0
  • Le conditionnel si avec la règle de frappe:
( nat S sera interprété comme des booléens ici avec une convention comme Zero dénotant la vérité, et tout autre nombre indiquant la fausseté)

Sémantique [ modifier ]]

Sémantique dénotationnelle [ modifier ]]

Une sémantique relativement simple pour la langue est la Modèle Scott . Dans ce modèle,

Ce modèle n’est pas entièrement abstrait pour PCF; mais il est entièrement abstrait pour la langue obtenue en ajoutant un parallèle ou Opérateur sur PCF. [4] : 293

  1. ^ “PCF est un langage de programmation pour les fonctions calculables, basée sur LCF, la logique de Scott des fonctions calculables.” [d’abord] Programmation des fonctions calculables est utilisé par (Mitchell 1996). Il est également appelé Programmation avec des fonctions calculables ou Langue de programmation pour les fonctions calculables .

Les références [ modifier ]]

  1. ^ un b Plotkin, Gordon D. (1977). “LCF considéré comme un langage de programmation” (PDF) . Informatique théorique . 5 (3): 223–255. est ce que je: 10.1016 / 0304-3975 (77) 90044-5 .
  2. ^ Milner, Robin (1977). “Modèles entièrement abstraits de λ-calculi typés” (PDF) . Informatique théorique . 4 : 1–22. est ce que je: 10.1016 / 0304-3975 (77) 90053-6 . HDL: 20.500.11820 / 731C88C6-CDB1-4EA0-945E-F39D85DE11F1 .
  3. ^ Ong, C.-H. L. (1995). “Correspondance entre la sémantique opérationnelle et dénotationnelle: le problème de l’abstraction complet pour PCF” . À Abramsky, S.; Gabbay, D.; Maibau, T. S. E. (éd.). Manuel de logique en informatique . Oxford University Press. pp. 269–356. Archivé de l’original le 2006-01-07 . Récupéré 2006-01-19 .
  4. ^ un b Hyland, J. M. E. & Ong, C.-H. L. (2000). “Sur une abstraction complète pour PCF” . Informations et calculs . 163 (2): 285–408. est ce que je: 10.1006 / inco.2000.2917 .
  5. ^ Abramsky, S., Jagadeesan, R. et Malacaria, P. (2000). “Abstraction complète pour PCF” . Informations et calculs . 163 (2): 409–470. est ce que je: 10.1006 / inco.2000.2930 . {{cite journal}} : CS1 Maint: plusieurs noms: liste des auteurs (lien)
  6. ^ O’Hearn, P. W. & Riecke, J. G (1995). “Kripke Logical Relations et PCF” . Informations et calculs . 120 (1): 107–116. est ce que je: 10.1006 / inco.1995.1103 .
  7. ^ Loader, R. (2001). “Le PCF finitaire n’est pas décidable” . Informatique théorique . 266 (1–2): 341–364. est ce que je: 10.1016 / S0304-3975 (00) 00194-8 .

Liens externes [ modifier ]]

after-content-x4