G6021 Comparative Programming
G6021 Comparative Programming
Copyright By PowCoder代写 加微信 powcoder
Part 6 – Summary
Part 6 – Summary G6021 Comparative Programming 1 / 15
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
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
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
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
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.)
add1 x = x+1
tl [1,2,3]
apply f x = f x
twice f x = f (f x)
(++) [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.
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
Dynamic look-up, abstraction, subtyping and inheritance.
Multiple inheritance: problems with this, and how to overcome
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
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
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com