CS计算机代考程序代写 data structure Lambda Calculus interpreter COM S 342 final review

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