Programming Computable Functions: Difference between revisions

Browse history interactively

← Previous edit

Content deleted Content added

VisualWikitext

Revision as of 14:59, 31 July 2006 edit Wipe (talk \| contribs) 1,342 edits m (oops) ← Previous edit		Latest revision as of 14:06, 6 July 2025 edit undo 2003:ef:3745:9400:7255:4619:879b:400a (talk) →Syntax: function type Tag: Visual edit
(64 intermediate revisions by 41 users not shown)
Line 1: {{Short description\|A typed functional language}} The '''Programming language for Computable Functions''', or '''PCF''', is a typed [[Functional programming\|functional language]] introduced by [[Gordon Plotkin]] in [[1977]]. It is based on the Logic of Computable Function ([[LCF]]) by [[Dana Scott]]. It can be considered as a simplified version of modern typed functional languages such as [[ML programming language\|ML]]. {{Infobox programming language \| name = Programming Computable Functions \| screenshot = <!-- Filename --> \| screenshot caption = \| sampleCode = \| paradigm = [[Functional programming\|functional]] \| family = \| designers = [[Dana Scott]],<br/>[[Robin Milner]],<br/>[[Gordon Plotkin]] \| released = {{Start date and age\|1977\|12}} \| latest release version = Full Abstraction \| latest release date = {{Start date and age\|2000\|12\|15\|df=yes}} \| typing = \| memory management = \| scope = \| programming language = \| discontinued = Yes \| platform = \| operating system = \| license = \| file ext = \| file format = <!-- or: \| file formats = --> \| website = <!-- {{URL\|www.example.com}} --> \| implementations = \| dialects = \| influenced by = \| influenced = }} In [[computer science]], '''Programming Computable Functions''' ('''PCF'''), or '''Programming with Computable Functions''', or '''Programming language for Computable Functions''', is a [[programming language]] which is [[Type system\|typed]] and based on [[functional programming]], introduced by [[Gordon Plotkin]] in 1977,<ref name="Plotkin 1977"/> based on prior unpublished material by [[Dana Scott]].{{Efn\|"PCF is a programming language for computable functions, based on LCF, Scott’s logic of computable functions."{{r\|name=Plotkin 1977}} ''Programming Computable Functions'' is used by {{harv\|Mitchell\|1996}}.}} It can be considered as an extended version of the [[typed lambda calculus]], or a simplified version of modern typed functional languages such as [[ML (programming language)\|ML]] or [[Haskell]]. A [[fully abstract]] model for PCF was first given by [[Robin ~~Milner\|~~Milner]].<ref name="Milner (1977)."/> However, since Milner's model was essentially based on the syntax of PCF it was considered less than satisfactory.<ref (name="Ong, 1995)."/> The first two fully abstract models not employing syntax were formulated during the 1990s. These models are based on [[game semantics]]<ref (name="Hyland ~~and Ong,~~ 2000;"/><ref name="Abramsky~~, Jagadeesan, and Malacaria,~~ 2000)"/> and [[Kripke logical relations]].<ref (name="O'Hearn ~~and~~1995"/> ~~Riecke~~For a time it was felt that neither of these models was completely satisfactory, ~~1995)~~since they were not effectively presentable. However, Ralph Loader demonstrated that no effectively presentable fully abstract model could exist, since the question of program equivalence in the finitary fragment of PCF is not decidable.<ref name="Loader 2001"/> ==~~External link~~Syntax== The ''[[data type]]s'' of PCF are inductively defined as * '''nat''' is a type * For types ''σ'' and ''τ'', there is a function type ''σ'' → ''τ'' A ''context'' is a list of pairs ''x : σ'', where ''x'' is a variable name and ''σ'' is a type, such that no variable name is duplicated. One then defines typing judgments of terms-in-context in the usual way for the following syntactical constructs: * [http://www.cs.bham.ac.uk/~mhe/papers/RNC3.pdf Introduction to RealPCF] * Variables (if ''x : σ'' is part of a context ''Γ'', then ''Γ'' ⊢ ''x'' : ''σ'') ~~==Sources==~~ * Application (of a term of type ''σ'' → ''τ'' to a term of type ''σ'') * [[λ-abstraction]] * The '''[[Fixed-point combinator#Y combinator\|Y]]''' fixed point combinator (making terms of type ''σ'' out of terms of type ''σ'' → ''σ'') * The successor ('''succ''') and predecessor ('''pred''') operations on '''nat''' and the constant '''0''' * The conditional '''if''' with the typing rule: : <math> \frac{ \Gamma \; \vdash \; t \; : \textbf{nat} , \quad \quad \Gamma \; \vdash \; s_0 \; : \sigma , \quad \quad \Gamma \; \vdash \; s_1 \; : \sigma } { \Gamma \; \vdash \; \textbf{if}(t,s_0,s_1) \; : \sigma } </math> : ('''nat'''s will be interpreted as booleans here with a convention like zero denoting truth, and any other number denoting falsity) ==Semantics== {{ cite journal <!-- todo: operational semantics --> ~~\| author = Abramsky, S., Jagadeesan, R., and Malacaria, P.~~ ~~\| title = Full Abstraction for PCF~~ ===Denotational semantics=== ~~\| journal = Information and Computation~~ A relatively straightforward semantics for the language is the '''Scott model'''. In this model, ~~\| date= 2000~~ ~~\| pages = 409-470~~ Types are interpreted as certain [[___domain theory\|domains]]. ~~\| volume = 163~~ <math>[\![ \textbf{nat} ]\!] := \mathbb{N}_{\bot}</math> (the natural numbers with a bottom element adjoined, with the flat ordering) ~~\| issue = 2~~ <math>[\![ \sigma \to \tau \, ]\!]</math> is interpreted as the ___domain of [[Scott-continuous]] functions from <math>[\![\sigma]\!] \,</math> to <math>[\![\tau]\!] \,</math>, with the pointwise ordering. ~~\| id = {{doi\|10.1006/inco.2000.2930}}~~ * A context <math>x_1 : \sigma_1, \; \dots, \; x_n : \sigma_n</math> is interpreted as the product <math>[\![\sigma_1]\!] \times \; \dots \; \times [\![\sigma_n]\!]</math> }} * Terms in context <math>\Gamma \; \vdash \; x \; : \; \sigma</math> are interpreted as continuous functions <math>[\![\Gamma]\!] \; \to \; [\![\sigma]\!]</math> {{ cite journal * Variable terms are interpreted as projections ~~\| author = Hyland, J. M. E. and Ong, C.-H. L.~~ Lambda abstraction and application are interpreted by making use of the [[cartesian closed]] structure of the category of domains and continuous functions ~~\| title = On Full Abstraction for PCF~~ '''Y''' is interpreted by taking the [[least fixed point]] of the argument ~~\| journal = Information and Computation~~ ~~\| date= 2000~~ This model is not fully abstract for PCF; but it is fully abstract for the language obtained by adding a ''[[parallel or]]'' operator to PCF.<ref name="Hyland 2000"/>{{rp\|293}} ~~\| pages = 285-408~~ ~~\| volume = 163~~ \|== ~~issue~~Notes = 2= {{Notelist}} ~~\| id = {{doi\|10.1006/inco.2000.2917}}~~ }} == References == {{ cite journal {{Reflist\|refs= ~~\| author = O'Hearn, P. W. and Riecke, J. G~~ <ref name="Plotkin 1977">{{cite journal ~~\| title = Kripke Logical Relations and PCF~~ \|last1=Plotkin ~~\| journal = Information and Computation~~ \|first1=Gordon D. ~~\| date = 1995~~ \|author1-link=Gordon Plotkin ~~\| pages = 107-116~~ \|date=December 1977 ~~\| volume = 120~~ \|title=LCF considered as a programming language ~~\| issue = 1~~ \|journal=Theoretical Computer Science ~~\| id = {{doi\|10.1006/inco.1995.1103}}~~ \|volume=5 }} \|issue=3 \|pages=223–255 \|doi=10.1016/0304-3975(77)90044-5 \|url=http://homepages.inf.ed.ac.uk/gdp/publications/LCF.pdf \|doi-access=free }}</ref> <ref name="Milner 1977">{{cite journal \|last1=Milner \|first1=Robin \|author1-link=Robin Milner \|date=February 1977 \|title=Fully abstract models of typed λ-calculi \|journal=Theoretical Computer Science \|volume=4 \|issue=1 \|pages=1–22 \|doi=10.1016/0304-3975(77)90053-6 \|url=https://www.pure.ed.ac.uk/ws/files/15112912/1_s2.0_0304397577900536_main.pdf \|hdl=20.500.11820/731c88c6-cdb1-4ea0-945e-f39d85de11f1 \|hdl-access=free }}</ref> <ref name="Ong 1995">{{cite book \|last1=Ong \|first1=C.-H. L. \|year=1995 \|title=Handbook of Logic in Computer Science \|chapter=Correspondence between Operational and Denotational Semantics: The Full Abstraction Problem for PCF \|editor1-last=Abramsky \|editor1-first=S. \|editor2-last=Gabbay \|editor2-first=D. \|editor3-last=Maibau \|editor3-first=T. S. E. \|pages=269–356 \|publisher=Oxford University Press \|chapter-url=http://users.comlab.ox.ac.uk/luke.ong/publications/ \|access-date=2006-01-19 \|archive-url=https://web.archive.org/web/20060107195328/http://users.comlab.ox.ac.uk/luke.ong/publications/ \|archive-date=2006-01-07 \|url-status=dead }}</ref> <ref name="Hyland 2000">{{cite journal \|last1=Hyland \|first1=J. M. E. \|last2=Ong \|first2=C.-H. L. \|date=15 December 2000 \|title=On Full Abstraction for PCF \|journal=Information and Computation \|volume=163 \|issue=2 \|pages=285–408 \|doi=10.1006/inco.2000.2917\|url=https://ora.ox.ac.uk/objects/uuid:63c54392-39f3-46f1-8a68-e6ff0ec90218 \|doi-access=free }}</ref> <ref name="Abramsky 2000">{{cite journal \|last1=Abramsky \|first1=S. \|last2=Jagadeesan \|first2=R. \|last3=Malacaria \|first3=P. \|date=15 December 2000 \|title=Full Abstraction for PCF \|journal=Information and Computation \|volume=163 \|issue=2 \|pages=409–470 \|doi=10.1006/inco.2000.2930 \|url=http://qmro.qmul.ac.uk/xmlui/handle/123456789/13604 \|doi-access=free }}</ref> <ref name="O'Hearn 1995">{{cite journal \|last1=O'Hearn \|first1=P. W. \|last2=Riecke \|first2=J. G. \|year=1995 \|title=Kripke Logical Relations and PCF \|journal=Information and Computation \|volume=120 \|issue=1 \|pages=107–116 \|doi=10.1006/inco.1995.1103 \|url=https://surface.syr.edu/lcsmith_other/3 \|doi-access=free }}</ref> <ref name="Loader 2001">{{cite journal \|last1=Loader \|first1=R. \|year=2001 \|title=Finitary PCF is not decidable \|journal=Theoretical Computer Science \|volume=266 \|issue=1–2 \|pages=341–364 \|doi=10.1016/S0304-3975(00)00194-8 \|doi-access=free }}</ref> }} {{cite journal \|last1=Scott \|first1=Dana S. \|author1-link=Dana Scott \|year=1969 \|title=A type-theoretic alternative to CUCH, ISWIM, OWHY \|journal=Unpublished Manuscript \|url=https://www.cs.cmu.edu/~kw/scans/scott93tcs.pdf }} Appeared as {{cite journal \|last1=Scott \|first1=Dana S. \|author1-link=Dana Scott \|year=1993 \|title=A type-theoretic alternative to CUCH, ISWIM, OWHY \|journal=[[Theoretical Computer Science (journal)\|Theoretical Computer Science]] \|volume=121 \|pages=411–440 \|doi=10.1016/0304-3975(93)90095-b \|doi-access=free}} {{cite book \|last1=Mitchell ~~\| author = Ong, C.-H. L.~~ \|first1=John C. ~~\| year = 1995~~ \|author1-link=John C. Mitchell ~~\| title = Handbook of Logic in Computer Science~~ \|year=1996 ~~\| chapter = Correspondence between Operational and Denotational Semantics: The Full Abstraction Problem for PCF~~ \|title=Foundations for Programming Languages ~~\| editor = Abramsky, S., Gabbay, D., and Maibau, T. S. E.~~ \|isbn=9780262133210 ~~\| pages = 269-356~~ \|chapter=The Language PCF ~~\| publisher = Oxford University Press~~ \|publisher=MIT Press ~~\| url = http://users.comlab.ox.ac.uk/luke.ong/publications/index.html~~ \|chapter-url=https://theory.stanford.edu/~jcm/books/fpl-chap2.ps }} {{ cite journal ~~\| author = Plotkin, G. D.~~ ~~\| title = LCF considered as a programming language~~ ~~\| journal = Theoretical Computer Science~~ ~~\| date= 1977~~ ~~\| pages = 223-255~~ ~~\| volume = 5~~ ~~\| id = {{doi\|10.1016/0304-3975(77)90044-5}}~~ }} ==External links== ~~{{compu-lang-stub}}~~ * [http://www.cs.bham.ac.uk/~mhe/papers/RNC3.pdf Introduction to RealPCF] * [https://web.archive.org/web/20071213234103/http://www.cs.pomona.edu/classes/cs131/Parsers/parsePCF.sml Lexer and Parser for PCF written in SML] [[Category:Programming languages created in 1977]] [[Category:Academic programming languages]] [[Category:Educational programming languages]] [[Category:Functional languages]] [[Category:Programming language theory]] <!-- Hidden categories below --> [[Category:Articles with example code]]