G6021 Comparative Programming
Part 6 – Summary
Part 6 – Summary
G6021 Comparative Programming
1/15
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.
Part 6 – Summary
G6021 Comparative Programming
2/15
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.
Declarative: What. Imperative: How. Ability to critically compare.
Part 6 – Summary
G6021 Comparative Programming
3/15
Revision
A programming language may enforce a particular style of programming, called a programming paradigm.
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.
Logic Languages: Programs describe a problem rather than defining an algorithmic implementation. The most well-known logic programming language is Prolog.
Part 6 – Summary
G6021 Comparative Programming
4/15
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?
Part 6 – Summary
G6021 Comparative Programming
5/15
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?) Type checking/inference (what is the difference?)
Part 6 – Summary
G6021 Comparative Programming
6/15
Programming
Programming with languages like Haskell and Prolog: Easier to program?
Learning curve?
Data types – efficiency?
Part 6 – Summary
G6021 Comparative Programming
7/15
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.
Part 6 – Summary
G6021 Comparative Programming
8/15
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)
(+) 3
(++) [True]
\(x,y,z) -> y
Building derivations: Example: ⊢ λxy.x : A → B → A
Part 6 – Summary
G6021 Comparative Programming
9/15
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
Part 6 – Summary
G6021 Comparative Programming
10/15
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.)
Part 6 – Summary
G6021 Comparative Programming
11/15
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
Part 6 – Summary
G6021 Comparative Programming
12/15
Objects
Dynamic look-up, abstraction, subtyping and inheritance.
Multiple inheritance: problems with this, and how to overcome them.
Part 6 – Summary
G6021 Comparative Programming
13/15
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)
Part 6 – Summary
G6021 Comparative Programming
14/15
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.
Send me requests for specific topics if you want more. Good luck!
Part 6 – Summary
G6021 Comparative Programming
15/15