This course is the first of three core computer science courses on programming. It introduces students to the field of computer science as a discipline for solving problems through computation and provides the foundation for more advanced courses on programming and software development. Data structures and algorithms, the key concepts at the core of computer science, receive their first treatment in this course. The course addresses both functional and imperative programming paradigms.
The course covers functional programming in depth, developing the core idea of functions operating on data structures. Students learn the organization of programming languages using types, how programs are evaluated (reduction), functional composition, recursive functions, algebraic data types, pattern matching, parametric polymorphism, higher-order functions. Students also gain exposure to structural induction and proof, introduction to asymptotic analysis of basic data structures, abstract data types, modules, laziness, and streams. The functional paradigm demonstrates elegant solutions to many programming problems.
The course also introduces imperative programming as an alternative paradigm to functional programming, highlighting similarities and contrasting differences. Students learn the basic ingredients of imperative programs: mutable variables, sequencing, conditionals, iteration, functions, eager evaluation, and side effects.
The course also introduces students to standard productivity tools for software development that will be used throughout the course and remainder of the computer science degree. These include distributed software revision control systems.
The Advanced version of this course covers these topics in more depth, allowing students to deepen their understanding and experience.
Upon successful completion of this course, students will be able to:
- Apply fundamental programming concepts, using a functional programming language, to solve simple problems.
- Understand basic types and the benefits of static typing.
- Distinguish language definition from implementation, syntax and parsing from semantics and evaluation.
- Describe, understand and evolve programs, via documentation, testing, and debugging.
- Discuss, use, and apply the fundamentals of data structures, algorithms, and design; create, implement, and debug algorithms for solving simple problems, including recursively, using divide-and-conquer, and via decomposition.
- Discuss basic algorithmic analysis for simple algorithms; determine appropriate algorithmic approaches to a problem (brute-force, greedy, divide-and-conquer, recursive backtracking, heuristic, dynamic programming).
- Describe and apply alternative computational paradigms to simple problems.
- Understand the legal context for protection of software as intellectual property.
Course Outline & Introduction COMP3610/COMP6361 — Principles of Programming Languages Clem Baker-Finch Australian National University Semester 2, 2015 COMP3610/6361 — Course Outline 1 Lectures: • 3 – 4pm Thursday Engineering Lecture Theatre • 10 – 12am Friday Engineering Lecture Theatre Most, but not all, lecture slots will be used. Web Site: http://cs.anu.edu.au/courses/COMP3610/ http://cs.anu.edu.au/courses/COMP6361/ Lecture recordings should appear on the COMP3610/6361 Wattle site. COMP3610/6361 — Course Outline 2 Class Discussion Forum: We will be using Piazza for class discussions, Q&As, etc. https://piazza.com/anu.edu.au/summer2015/comp36106361/home You should be registered and have received an email notification. COMP3610/6361 — Course Outline 3 Pracs and Tutorials: • Commence week 2 • 8 or 9 classes spread over the semester • Two hours per week Fridays 12 – 2pm, N115/116 or N101 • Watch the course website for schedule and exercises These will be longer exercises and practical programming tasks. They may take longer than the lab session to complete and you are expected to finish them in your own time if necessary. It is important, and expected, that you will have made a genuine attempt at the exercises before the laboratory class or tutorial. COMP3610/6361 — Course Outline 4 Assessment • There will be two assignments with a combined weight of 40%. Each will have fixed deadlines and will be due near weeks 7 and 12. • There will be a 3 hour final exam with a weight of 60%. It will be open book. • Your final mark will be the sum of those components. • Consistent scaling may occur across all students. • Final marks are also moderated by the School of Computer Science examiners meeting. The content and assessment of COMP3610 and COMP6361 are identical. COMP3610/6361 — Course Outline 5 What is this subject about? “Principles of programming languages. . . ” • Foundations of programming languages, e.g. lambda calculus, fixpoint theory • The recognition and translation of programming languages • Proving properties of programs with a mechanical proof assistant • The semantics of programming languages Programs and programming languages as artefacts — objects of study in their own right. Unifying theme: “The unreasonable effectiveness of logic in computer science” — Phil Wadler. COMP3610/6361 — Course Outline 6 What is this subject NOT about? • This is not a (“how to”) programming course. • It is not about any particular programming languages. • It does not teach programming skills. • We assume you are a reasonably proficient programmer, comfortable with writing functions over recursive data structures (e.g. trees), at least. • In lectures and pracs, the main languages of instruction will be Haskell and C. The Coq proof assistant also uses a functional language somewhat similar to Haskell. COMP3610/6361 — Course Outline 7 Assumed Knowledge • COMP2600 Foundations of Software Engineering: This is a warning label — if you didn’t pass/like/enjoy 2600, don’t go here. • COMP2300 Introduction to Computer Systems: Less important, but we will assume some familiarity with run-time structures and the relation between programming languages and their machine representation. More generally: • Familiarity with elementary logic and natural deduction; • At least passing familiarity with functional programming; • Curiosity about how compilers work, why programming languages look the way they do, and how we might reason about programs. COMP3610/6361 — Course Outline 8 Functional Programming If you haven’t used a functional language like Haskell before, then start today! • A fine introductory text book is Thompson: “Haskell – the Craft of Functional Programming,” Addison-Wesley. • The first-year COMP1100 website has some very good resources: http://cs.anu.edu.au/student/comp1100/1-Resources-References • Dirk Pattinson (co-lecturer in this course) has produced some excellent Haskell video tutorials: http://users.cecs.anu.edu.au/˜dpattinson/Haskell/ COMP3610/6361 — Course Outline 9 Proposed syllabus • Introduction What is a programming language; Brief Haskell refresher • Fixpoint theory of recursive functions Computational intuition; Fixed points; Reduction strategies • Proving properties of programs Using the Coq interactive proof assistant; Dirk Pattinson will be teaching this section of the course • Recognition and translation of languages Top-down and bottom-up parsers; Scanner and parser generators • Semantics of programming languages Operational semantics; Denotational semantics; Abstract Interpreters COMP3610/6361 — Course Outline 10 Useful Textbooks • Pierce et al: “Software Foundations,” http://www.cis.upenn.edu/˜bcpierce/sf/current/ • Nielson & Nielson: “Semantics with Applications,” Wiley, 1992. (Basic.) • Winskell: “The Formal Semantics of Programming Languages,” MIT Press, 1993. (Better, but more mathematically sophisticated.) • Gunter:“Semantics of Programming Languages – Structures and Techniques,” MIT Press, 1992. (Excellent, somewhat advanced.) • Pierce: “Types and Programming Languages,” MIT Press, 2002. (Excellent.) • Aho, Sethi & Ullman: “Compilers: Principles, Techniques, and Tools,” Addison-Wesley. (An absolute classic. There are numerous edition.) • Levine, Mason & Brown: “lex & yacc”, O’Reilly & Associates, 1992. COMP3610/6361 — Course Outline 11 Haskell ‘Refresher’ ... COMP3610/6361 — Course Outline 12 Laziness • Consider the functions const and loop. const :: a -> b -> a const x y = x What is the value of const 4 100? loop :: Int -> Int loop n = loop (n + 1) What is the value of loop 2? Now, what is the value of const 4 (loop 2) ? Is that what you expected? What other outcomes might seem reasonable? COMP3610/6361 — Course Outline 13 In Haskell we can define a list of all the even numbers in sequence: evens :: [ Integer ] evens = [0 , 2 ..] If we ask for the 5th even number: evens !!5 why doesn’t Haskell attempt to calculate the whole list first? How would you expect other languages to behave? COMP3610/6361 — Course Outline 14 Semantics and evaluation order • Strict vs non-strict semantics: – strict semantics: the argument is evaluated first: const 4 (loop 2) = ⊥ (undefined) – non-strict semantics: the application is evaluated first: const 4 (loop 2) = 4 the argument is evaluated only if its value is actually required. • Applicative-order vs normal-order evaluation: – applicative-order evaluation (arguments first) implements strict semantics – normal-order evaluation (application first) implements non-strict semantics COMP3610/6361 — Course Outline 15 Haskell has lazy evaluation Lazy evaluation combines normal-order evaluation and sharing: • Never evaluate something until/unless you have to (normal-order) • Never evaluate something more than once (sharing) (In practice things aren’t that simple — different implementations are more or less successful with sharing in particular. The points above are more like aspirations. . . ) COMP3610/6361 — Course Outline 16 Laziness aids program decomposition • It allows you to use infinite data structures – Infinite data structures are specified the same way as finite data structures. – Only as much of a data structure as demanded by its context is constructed. More importantly: • It allows you to decompose algorithms as generate-and-test – in imperative languages generating and testing must be interleaved – in lazy languages generating and testing can be separated COMP3610/6361 — Course Outline 17 Example: Newton’s square root algorithm √ x = lim an n→∞ where an+1 = (an + x/an )/2 and a0 is an arbitrary starting value. The infinite sequence of approximations starting at a0 is given by iterate ( next x) a0 where: next :: Float -> Float -> Float next x a = (a + x/a )/2 COMP3610/6361 — Course Outline 18 How good an approximation do we want? Let’s say 4 decimal places: close :: Float -> Float -> Bool close a x = abs (x - a ˆ2) < 0.00001 Putting it together: sqrtNewton :: Float -> Float -> Float sqrtNewton x a0 = head ( dropWhile ( not . close ) ( iterate ( next x) a0 )) where next x a = (a + x/a )/2 close a = abs (x - a ˆ2) < 0.00001 Exercise: Modify the program so answers are 4 significant figures rather than decimal places. COMP3610/6361 — Course Outline 19 Cyclic definitions • An infinite list of 1s: ones :: [ Integer ] ones = 1 : ones • The fibonacci numbers: fibs :: [ Integer ] fibs = 1 : 1 : zipWith (+) fibs ( tail fibs ) -- alternative using list comprehension : fibs ’ = 1 : 1 : [x + y | (x , y) <- zip fibs ’ ( tail fibs ’)] COMP3610/6361 — Course Outline 20 • Hamming numbers. An ordered list containing all integers whose only prime factors are 2, 3 and 5 — i.e. all integers of the form 2i × 3 j × 5k , for i, j, k ≥ 0 hamming :: [ Integer ] hamming = 1 : merge ( map (2 *) hamming ) ( merge ( map (3 *) hamming ) ( map (5 *) hamming )) where merge combines two lists to give an ordered list with no duplicates: merge (x: xs ) (y: ys ) | x < y = x: merge xs (y: ys ) | x == y = x: merge xs ys | x > = y: merge (x: xs ) ys COMP3610/6361 — Course Outline y 21 Take care . . . • e.g. 4 ‘elem‘ [0, 2 ..] = 4 ‘elem‘ (0 : 2 : 4 : 6 : ...) = True • but = = = 3 ‘elem‘ [0, 2 ..] 3 ‘elem‘ (0 : 2 : 4 : 6 : ...) 3 ‘elem‘ (4 : 6 : ...) ⊥ • e.g. filter (< 10) [n ˆ 2 | n <- [1 ..]] = 1 : 4 : 9 : ⊥ • but takeWhile (< 10) [n ˆ 2 | n <- [1 ..]] = 1 : 4 : 9 :  COMP3610/6361 — Course Outline 22 Homework: • Read the Countdown Problem paper on the course website. • Carefully work through the process and the provided code. • Experiment. • Write some Haskell programs, or at least revisit some you wrote in the past. COMP3610/6361 — Course Outline 23