PCF Summary Report
研究报告代写 Here is the study report of PCF, which stands for programming with computable functions. Although it is not a real programming language
September 2, 2018
1 Overview 研究报告代写
Here is the study report of PCF, which stands for programming with computable functions. Although it is not a real programming language used in practice, it provides the basic skeleton and ideas for some advanced programming languages like Scala and Haskell. It is an extended version of the typed lambda calculus or a simplified version of modern typed functional languages.研究报告代写
There are two parts to define PCF, the syntax and evaluation rules. The syntax gives detailed rules of how to write correct PCF program while evalua- tion rules illustrate methods for reasoning the program. This summary firstly overview the syntax and then analyze more about different equivalence relations on terms.
1.1 Syntax 研究报告代写
For syntax, the base types of PCF are boolean and natural number and recursion is included for function call. Actually the typing rules for PCF is just those of simply-typed lambda calculus together with some additional constructs that deals with booleans, natural numbers and recursion.
1.2 Equivalence Relation
1.2.1 Axiomatic equivalence
For the equivalence relations, there are three notions defined in PCF, namely ax- iomatic equivalence, operation equivalence and denotational equivalence. They give different features of PCF.研究报告代写
Axiomatic equivalence is based on βη equivalence in simply typed lambda calculus. It consists of all beta and h axioms of the simply-typed lambda calcu- lus, together with one congruence rule for each term constructor and additional rules for terms like pred() zero iszero() succ().
1.2.2 Operational Relation 研究报告代写
Operational semantics is more complicated. Formally, two terms M,N are oper- ationally equivalent in symbols M=N, if for all closed and closing context C[-]
of observable type and all values V[1, p. 106].
C[M ] ⇓ V ⇔ C[N ] ⇓ V (1)
For PCF, the observable type is Boolean or natural number. Furthermore, as a refinement of operational equivalence, operational approximation is also defined. We say M operationally approximate N in symbols M op N , if for all closed and closing context C[-] of observable type and all values V[1, p. 106].
C[M ] ⇓ V ⇒ C[N ] ⇓ V (2)
Operational equivalence is very important for real programming languages, which can be used for code optimization and compiler optimizations. For two pieces of code M and N, if we can reason that M is operational equivalent to N, then we can replace N with M safely without any side effects. For code optimization M is usually a better version of implementation. Similarly, for 研究报告代写 compiler optimizations it usually means replacing a piece of code N with another piece without knowing much about the programmatic context during compile time.
However, this feature sometimes cause problems. When new features is added into the programming language, the previous safe replacement might be- come error prone and unstable. That is mainly because operational equivalence is defined in terms of context. When new context is changed, the previous in- distinguishable code piece M and N might become distinguishable. An example would be when parallelism feature is added to the programming language, some operational equal code pieces might become different due to shared variables.
1.2.3 Denotational equivalence 研究报告代写
The finally equivalence relation is denotational equivalence. Denotational se- mantics means to give meaning to a language by interpreting its terms as math- ematical objects. This is done by describing a function that maps syntactic objects (e.g., types, terms) to semantic objects (e.g., sets, elements). This func- tion is called an interpretation or meaning function[1, p. 93].
The denotational semantics of PCF is defined in terms of cpos. It extends the cpo semantics of the simply-typed lambda calculus. Two PCF terms M and N of equal types are denotationally equivalent, in symbols M ±den N , if
[[M ]] = [[N ]]. We also write M ±den N if [[M ]] ± [[N ]] [1, p. 116].References 研究报告代写
[1] P. Selinger, “Lecture notes on the lambda calculus,” arXiv preprint arXiv:0804.3434, 2008.
其他代写：web代写 program代写 cs作业代写 analysis代写 app代写 Programming代写 homework代写 source code代写 考试助攻 finance代写 Exercise代写 代写CS C++代写 java代写 r代写
