CPSC 312
Functional and Logic Programming
Winter Session 2014/2015 - Term 1
Course Information
Instructor:
Kurt Eiselt
eiselt@cs.ubc.ca
Teaching Assistants:
TBA
Office Hours:
TBA
Official Calendar Description:
Principles of symbolic computing, using languages based upon first-order logic and the lambda calculus. Algorithms for implementing such languages.
Applications to artificial intelligence and knowledge representation.
Unofficial Instructor Description:
If you're a UBC student who has fulfilled the prerequisites for this course, then you've done some programming in Java or C++. These programming
languages, like many languages, are imperative programming languages. Imperative programs are written as sequences of instructions that change or
mutate program state. The instructions themselves correspond fairly closely to machine-level instructions that move data from memory to registers, modify
the data, and then move the modified data back to memory. An imperative programming language thus constrains the programmer to define a solution to a
problem in terms of the computer's low-level architecture. Wait, you say, aren't Java and C++ object-oriented languages? Well, sure, adding concepts like
classes and objects to a language puts some useful distance between the programmer and the computer architecture and provides additional flexibility when
considering possible solutions, but when you get down to the task of writing Java methods, you're writing imperative programs. Imperative programming
languages are good for tackling many computational problems but they are by no means the best tools for solving all computational problems.
CPSC 312 exposes students to two other programming paradigms, the functional programming paradigm and the logic programming paradigm, each of which
provides a very different perspective on computation than the imperative paradigm. If you've taken CPSC 110, as most of you have, you were doing
functional programming in CPSC 110 up until the time you encountered mutable state. CPSC 312 will build on what you learned there, but you'll still learn lots
of new things about functional programming in CPSC 312. In CPSC 312, the functional languages are represented by Haskell and the logic languages are
represented by Prolog. Each of these languages will require you to think about computation in ways you probably never have before. That's really the point of
this course. As the noted computer scientist Alan Perlis once said, "A language that doesn't affect the way you think about programming is not worth knowing."
One other thing: As the course title says, this is a "programming" course, so if you're not fond of programming, you might look elsewhere for a course to
fill out your schedule. Learning two (or maybe three, or even four, depending on how things go) new programming languages while trying to integrate two very
different styles of thinking with what you already know will, for some students, require far more practice than is provided by the homework assignments. If you
don't like programming, then you're less likely to practice as much as you need to, which may in turn have an unfortunate impact on your exam performance.
I'm not trying to scare you away. I just want you to understand that this course can be challenging.
Textbooks:
The Art of Prolog (Second Edition), Leon Sterling and Ehud Shapiro, MIT Press, 1994.
Haskell: The Craft of Functional Programming (Third Edition), Simon Thompson, Addison-Wesley, 2011.
Programming Language:
You can download the Glasgow Haskell Compiler (GHC) platform at http://hackage.haskell.org/platform/
You can download SWI Prolog at http://www.swi-prolog.org/Download.html
Tentative Grading Scheme:
Assignments (several) 10%
Projects (2)* 20%
Midterm exam** 25%
Final exam*** 45%
* You must earn at least 50% of the possible marks on each of the two projects in order to pass the course, regardless of the marks you have received
for other evaluated components. Also, the projects are team-based projects. You will be working with one other person (or possibly with two other people
if there are an odd number of students in the course). We do not allow solo efforts on projects. If you don't want to work with other students, you should
not take CPSC 312.
** You must earn at least 50% of the possible marks on the midterm examination in order to pass the course, regardless of the marks you have received
for other evaluated components.
*** You must earn at least 50% of the possible marks on the final examination in order to pass the course, regardless of the marks you have received
for other evaluated components.
Very Tentative Schedule based on a combination of schedules from previous times I have taught this course (this schedule could change significantly):
Kurt Eiselt
eiselt@cs.ubc.ca
Teaching Assistants:
TBA
Office Hours:
TBA
Official Calendar Description:
Principles of symbolic computing, using languages based upon first-order logic and the lambda calculus. Algorithms for implementing such languages.
Applications to artificial intelligence and knowledge representation.
Unofficial Instructor Description:
If you're a UBC student who has fulfilled the prerequisites for this course, then you've done some programming in Java or C++. These programming
languages, like many languages, are imperative programming languages. Imperative programs are written as sequences of instructions that change or
mutate program state. The instructions themselves correspond fairly closely to machine-level instructions that move data from memory to registers, modify
the data, and then move the modified data back to memory. An imperative programming language thus constrains the programmer to define a solution to a
problem in terms of the computer's low-level architecture. Wait, you say, aren't Java and C++ object-oriented languages? Well, sure, adding concepts like
classes and objects to a language puts some useful distance between the programmer and the computer architecture and provides additional flexibility when
considering possible solutions, but when you get down to the task of writing Java methods, you're writing imperative programs. Imperative programming
languages are good for tackling many computational problems but they are by no means the best tools for solving all computational problems.
CPSC 312 exposes students to two other programming paradigms, the functional programming paradigm and the logic programming paradigm, each of which
provides a very different perspective on computation than the imperative paradigm. If you've taken CPSC 110, as most of you have, you were doing
functional programming in CPSC 110 up until the time you encountered mutable state. CPSC 312 will build on what you learned there, but you'll still learn lots
of new things about functional programming in CPSC 312. In CPSC 312, the functional languages are represented by Haskell and the logic languages are
represented by Prolog. Each of these languages will require you to think about computation in ways you probably never have before. That's really the point of
this course. As the noted computer scientist Alan Perlis once said, "A language that doesn't affect the way you think about programming is not worth knowing."
One other thing: As the course title says, this is a "programming" course, so if you're not fond of programming, you might look elsewhere for a course to
fill out your schedule. Learning two (or maybe three, or even four, depending on how things go) new programming languages while trying to integrate two very
different styles of thinking with what you already know will, for some students, require far more practice than is provided by the homework assignments. If you
don't like programming, then you're less likely to practice as much as you need to, which may in turn have an unfortunate impact on your exam performance.
I'm not trying to scare you away. I just want you to understand that this course can be challenging.
Textbooks:
The Art of Prolog (Second Edition), Leon Sterling and Ehud Shapiro, MIT Press, 1994.
Haskell: The Craft of Functional Programming (Third Edition), Simon Thompson, Addison-Wesley, 2011.
Programming Language:
You can download the Glasgow Haskell Compiler (GHC) platform at http://hackage.haskell.org/platform/
You can download SWI Prolog at http://www.swi-prolog.org/Download.html
Tentative Grading Scheme:
Assignments (several) 10%
Projects (2)* 20%
Midterm exam** 25%
Final exam*** 45%
* You must earn at least 50% of the possible marks on each of the two projects in order to pass the course, regardless of the marks you have received
for other evaluated components. Also, the projects are team-based projects. You will be working with one other person (or possibly with two other people
if there are an odd number of students in the course). We do not allow solo efforts on projects. If you don't want to work with other students, you should
not take CPSC 312.
** You must earn at least 50% of the possible marks on the midterm examination in order to pass the course, regardless of the marks you have received
for other evaluated components.
*** You must earn at least 50% of the possible marks on the final examination in order to pass the course, regardless of the marks you have received
for other evaluated components.
Very Tentative Schedule based on a combination of schedules from previous times I have taught this course (this schedule could change significantly):
|
Week 1 Week 2 Week 3 Week 4 Week 5 Week 6 Week 7 Week 8 Week 9 Week 10 Week 11 Week 12 Week 13 |
Dates
Sept. 4 Sept. 9, 11 Sept. 16, 18 Sept. 23, 25 Sept. 30, Oct. 2 Oct. 7, 9 Oct. 14, 16 Oct. 21, 23 Oct. 28, Oct. 30 Nov. 4, 6 Nov. 13 Nov. 18, 20 Nov. 25, 27 |
Readings for the week
Readings below are from the Haskell text Ch. 1: Introducing Functional Programming Ch. 2: Getting Started with Haskell and GHCi Ch. 3: Basic Types and Definitions Ch. 4: Designing and Writing Programs Ch. 5: Data Types, Tuples and Lists Ch. 6: Programming with Lists Ch. 7: Defining Functions over Lists Ch. 10: Generalization: Patterns of Computation Ch. 11: Higher-Order Functions Ch. 17: Lazy Programming (sections 17.1 through 17.8) Midterm exam is on October 2 Lecture topics to be determined Readings below are from the Prolog text Ch. 1: Basic Constructs Ch. 2: Database Programming Ch. 3: Recursive Programming Ch. 4: The Computational Model of Logic Programs Ch. 6: Pure Prolog Ch. 7: Programming in Pure Prolog Ch. 12: Extra-Logical Predicates (section 12.2) Ch. 14: Nondeterministic Programming (sections 14.1 and 14.2) Ch. 8: Arithmetic (sections 8.1 and 8.2) Ch. 16: Second-Order Programming (section 16.1) Ch. 11: Cuts and Negation (sections 11.1 and 11.4) Ch. 19: Definite Clause Grammars and Natural Language Erlang I Erlang II Erlang III Project 2 demos Final exam is to be determined |