Marist College Dept of Computing Technology
Theory of Programming Languages – Exam #1
Student:
Inductive Specifications
10 points
1. Write an inductive specification for the set { 3 + 7k | k∈N } in the Top-Down style. 5
2. Write an inductive specification for { (1+4m, 2n–2) | m,n∈N } in the Bottom-Up style. 5
CMPT 331 – Exam #1 1 of 6 Fall 2020
Dept of Computing Technology 3. What are the three essential operations of the interface to the reference ADT of Chapter 4?.
Along with the name of each operation, classify each as constructor/observer/mutator. 5 Name Classification
a. b. c.
4. Why is is useful to enforce the separation of interface from implementation (i.e., the abstraction boundary) of an ADT? Provide a concrete example to help justify your explanation. 5
Marist College
Data Abstraction
15 points
5. Apart from the formal parameter(s) and the body of the function, what else does the closure ADT encapsulate? Why is this necessary for correct evaluation of the function at call-time? Give a concrete example if possible. 5
CMPT 331 – Exam #1 2 of 6 Fall 2020
Marist College
Dept of Computing Technology
45 points
See the “Specification of the H– Language” in the Appendix to answer the questions below.
6. Fill in abstract syntax names for the H– grammar in the Appendix. 5
7. Write a syntactic derivation to prove that the string below is a valid H– program. 15
let f = \ x -> if x then 10 else 5 in f 1
Syntactic Derivation
CMPT 331 – Exam #1 3 of 6 Fall 2020
Marist College Dept of Computing Technology 8. Draw an Abstract Syntax Tree diagram corresponding to a parse of the program above. 15
CMPT 331 – Exam #1 4 of 6 Fall 2020
Marist College
Dept of Computing Technology
Language Syntax & Semantics
30 points
9. Suppose that we want to explicit Boolean literals to the H– language.
a. Write two new EBNF productions for these literals. 5
b. Write two inference rules that specify the semantics of these new literals. 5
10. Suppose that we wish to add a new kind of expression known as a case-of expression, which acts like a kind of switch-case or if-else-if conditional with multiple outcomes. An example of a case-of expression is: case f x of 0 -> 1; 1 -> 3; 2 -> 5; 3 -> 7; _ -> 0
The value of the above expression is 0 when the function’s return value is none of 0, 1, 2, or 3.
a. Write an EBNF production for this expression using the Kleene plus notation. 5
b. Write the necessary inference rule(s) to specify the desired semantics of this expression. 15
CMPT 331 – Exam #1 5 of 6 Fall 2020
Marist College
Dept of Computing Technology
Appendix: Specification of the H– Language
Formal Grammar
1. Prog
2. Exp
3. 4.
5.
6. FExp
7.
8. AExp
9.
::= Exp
::=\Var->Exp ::=letVar=ExpinExp
::= if Exp then Exp else Exp ::= FExp
::= AExp
::= FExp AExp
::= Var
::= Literal
(a-program (exp))
::= Int
12. Implicit production for Int.
where an Int is just an integer and a Var begins with a lowercase letter and contains only letters or underscore. Note that the abstract syntax names are not given above.
Informal Semantics
The H– language is an extremely limited subset of the Haskell language. Programs are expressions, which come in four different varieties – lambdas, let expressions, if-else conditionals, and function applications. Both lambdas and function applications may be nested to implement currying multiple arguments. Variables are declared only by lambdas and let expressions and have lexical scoping. There are only two data types – integers and booleans. Booleans can only becreated by implicit conversion from an integer (e.g., if 1 then 10 else 5).
10. Literal
11. Implicit production for Var.
CMPT 331 – Exam #1 6 of 6 Fall 2020