COM S 342 final review
Exam time:
=====
Tue-Thur 9:45am, 2 hours (excluding special accommodation)
Open book, open note (review before exam)
Canvas
Good luck!
Friday for questions
=====
Questions are based on the following topics: lambda calculus, reflang, typelang, logic
programming (high order functions, funclang programming)
Type of questions:
● Multiple-choice questions (concepts and understanding), problem solving as
homework questions
● Exercise problem solving within the time limit
Show steps of your problem solving to get partial credits
=======
Review
Lambda calculus:
Concepts
1. Smallest programming language
2. Pure functional programming language
3. simulate all the computations that Turing machine can compute
4. alpha-renaming, beta-reduction (function application)
5. Lazy evaluation, only when beta-reduction terminates then the evaluation order
does not matter
Problem solving
beta-reduction:
1. Parsing (structure: function/function parameter)
2. Function application
Church-encoding (succ, one, zero, true, false, identify patterns: identity function, self
application)
Reflang:
Concepts
● Side effect versus pure functional programming
● Aliasing
● Heap: typed heap, untyped heap, management through garbage collector
automatically or by developers through language operators
Problem solving:
● Reflang program understanding
● Reflang programing (high order functions, data structure simulation: link list,
binary tree, …)
● Reflang interpreter programming
TypeLang:
Concepts:
What is a type? Why do we need type?
Default type, developer can define a type
Static typed language, dynamic typed language
Strongly typed languages, weakly typed languages
Typing rules, type rule, type checking and type inferences
Top
——
Bottom
Problem solving:
TypeLang programming (understand the programs, write the TypeLang programs)
TypeLang interpreter (type checking rules and implementation of type checking rules,
design of type checking rules)
Logic programming
Concepts
● Declarative programming languages
● Based on first order logic
● Interpreter: theorem proving: deductive reasoning
● Unification, backtracking
Problem solving
Logic programming
1. Logic puzzle: look for constraints, e.g., hw9Q4, lecture notes example
2. Numbers: hw9 Q2, Q3
gcd(0,B,C) :- C = B.
gcd(A,B,C) :- H is B mod A, gcd(H,A,C).
3. List: recursion: length, append, reserve, sum
Hw9 Q2b: duplicate solution understanding: considering the following example
[1,2,3], 2, [2,2,3,3], 0
[2,3], 2, [2,2,3,3],2
[1,2,3], 2, [1,2,2,3,3], 1
[1,2,3], 2, [2,2,3,3], 0
4. Parser: composer
a. Slides: last example, hw9q5