CISC 260/3.0 Programming Paradigms
Original Authors: Margaret Lamb and Bob Tennent
Last Revised: August 30, 2006
Review of imperative programming features. Introduction to other
widely used programming paradigms. Functional programming languages,
such as LISP and Haskell. Higher order functions, lazy evaluation,
abstract and recursive types, structural induction, symbolic
expressions. Logic programming languages, such as PROLOG. Operational
interpretation of predicates and terms, proof search, unification,
backtracking. Typical applications.
Prerequisite: CISC 124/3.0
Prerequisite or corequisite: CISC 204/3.0
- Most students will need to use functional and/or logical languages
in later courses and/or professional work.
- Exposure to different ways of thinking about programming can improve
programming skills, even when using traditional imperative languages.
- Functional and logic-based languages allow very elegant and
well-structured solutions to many problems.
- It is essential that students learn how to learn new programming
It is not an aim of this course to "convert" students to exclusive use
of any non-standard paradigm.
It seeks to give students a basic level of competence in a
functional language (such as Haskell or LISP) and a logic-based language
(such as PROLOG). While learning these languages, we compare and
contrast them with each other and with procedural and object-oriented
languages such as Java or C. Other non-standard paradigms (programming
reactive systems, discrete-event simulation, tree transformations, etc.)
may be briefly discussed if time permits.
The courses to which this course is a prerequisite are
- CISC-352/3.0 (Artificial Intelligence)
- CISC-453/3.0 (Topics in Artificial Intelligence)
- CISC-465/3.0 (Foundations of Programming Languages)
- COGS-300/3.0 (Programming Cognitive Models)
This course is required in BMCO, COGS, CSCI, SODE, COMP-M-BCH, and COMP-G-BCP.
- lists and trees
- type checking: polymorphic static types vs. dynamic type checking
- use of accumulators for efficiency
- the basic idea of a functional language: programming with
mathematical-style functions, without assignable variables and jumps
- using structural induction to prove properties of functional
- higher-order functions, including maps, filters, folds, and lambda
- lazy evaluation
- the basic idea of operational interpretation of a logical language:
facts, rules and queries
- the declarative meaning of a logical program: how goals may be
inferred from facts and rules
- the procedural meaning of a logical program: how the programming
language searches for and applies facts and rules, including pattern
matching rules and backtracking
- making intelligent use of recursive rules while avoiding infinite
- negation as failure
- use of "(green) cuts" for optimization
- S. Thompson: Haskell, The Craft of Functional Programming, Addison-Wesley 1999.
- I. Bratko: PROLOG Programming for Artificial Intelligence, Pearson
Education, 3rd edition, 2001.
- R. Sethi: Programming Languages, Concepts and Constructs, Addison-Wesley,
2nd edition, 1996.
- H. Bal and D. Grune: Programming Language Essentials, Addison Wesley,
- D. Watt: Programming Language Concepts and Paradigms, Prentice-Hall
- A. Davie: An Introduction to Functional Programming Systems Using Haskell,
Cambridge University Press, 1992.
- R. Bird: Introduction to Functional Programming Using Haskell, Prentice
Hall, 2nd edition, 1998.
- W. Clocksin and C. Mellish: Programming in Prolog, Using the ISO
Standard, Springer, 5th edition, 2003.
- L. Sterling and E. Shapiro: The Art of Prolog, Advanced Programming
Techniques, The MIT Press, 2nd edition, 1994.