Part 6 – Summary
Add
Overview
Programming paradigms: Functional Object oriented
Logic programming
Imperative
Emphasis on functional programming in Haskell for the labs, however, the exam will be more balanced.Add
Main Topics
Types: subtypes, polymorphism, overloading
Semantics: Operational, denotational, axiomatic
Foundations: λ-calculus for functional, While language for imperative. λcalculus concepts explain many concepts found in modern programming languages. Unification for logic
programming.
Implementations: we’ve implemented them all in the labs, so you should have some ideas about memory usage, etc. Referentially transparent:
always gives the same answer.Add
Declarative: What. Imperative: How.
Ability to critically compare.
Revision
Imperative Languages: Programs are decomposed into
computation steps and routines are used to modularise the program. Fortran, Pascal, C are imperative.
Functional Languages: Based on the mathematical theory of functions. The focus is in what should be computed, not how it should be computed.
Object-oriented Languages: Emphasise the definition of hierarchies of objects.Add
Logic Languages: Programs describe a problem rather than defining an algorithmic implementation. The most well-known logic programming language is Prolog.
Implementation
Imperative languages: Programs mapped to memory manipulation instructions.
Declarative Languages: implemented through abstract machines, and thus do not map directly to memory manipulations.
▶ functional languages, e.g. Haskell: Lambda calculus
▶ logic programming, e.g. Prolog: resolution
Which are easier to implement? Efficiency?Add
Types
Functional: types very important in languages like Haskell. Every program, sub-program, has a type, and this is preserved under reduction.
Object oriented: subtypes. Types used to structure data
Imperative: where are types used here?
Prolog: types not really used (arity, mode) Main issues:
Polymorphism: parametric, ad hoc (what is the difference?)Add
Type checking/inference (what is the difference?)
Programming
Programming with languages like Haskell and Prolog: Easier to program?
Learning curve?
Data types – efficiency?
Add
Haskell I assume you have done all the lab exercises….
Ability to write a simple function.
Lists, Trees, pattern matching
Higher-order functions: write and use: map, fold, etc. Accumulating parameters: tail recursive functions.
Use some specific features of Haskell: data type declarations, pattern matching, list comprehension, etc.Add Types
Note: The type reconstruction algorithm (algorithm T) will not be examined, but knowledge of disagreement set and unification could be. Knowing how to give a program a type in Haskell.
How to type Haskell functions informally (see exercises)
Start with what you know, and build up. (Use the types of built-in functions also: head (or hd), tail (or tl), ++ (or app), etc.) Examples:
add1 x = x+1 tl
[1,2,3] apply f x = f x twice f x = f (f x)Add
(+) 3
(++) [True]
(x,y,z) -> y
Building derivations: Example: λxy.x : A → B → A Disagreement set and Unification
Checklist:
Can you unify two types? Draw type tree to help see the structure. Example: (((A → A) → B) → B and C → int
Add
Accumulating parameters
Know how to convert a given function to a version that uses an accumulating parameter. Example:
power x y = x* power x (y-1) power x y z = power x (y-1) z*x
Writing simple examples in CPS: factorial, reverse of list, etc. (So how to convert a simple function so that it is tail recursive.)Add Lambda calculus
Important topics:
Reduction: know how to reduce a lambda term. Reduction graphs. Show all reduction sequences.
Strategies: the order in which we reduce redexes
Normal forms: the answers (when we stop reducing)
Writing functions as a fixpoint of a functional
Add
Objects
Dynamic look-up, abstraction, subtyping and inheritance.
Multiple inheritance: problems with this, and how to overcomethem.
Add
Logic Programming
Declarative, knowledge-based programming: the program just describes the problem.
Advantages/Disadvantages?
Termination: order of the clauses important (relation with Haskell pattern matching)
Evaluate a simple Prolog program (to show understanding of
unification)Add
Exam
The format of the exam is standard:
Answer TWO OUT OF THREE questions
Candidates should answer ONLY TWO questions
The course is not over yet:
More exercises with solutions will be put on the web page to help with your revision.Add
Send me requests for specific topics if you want more.
Good luck!
