Queen's School of Computing

CISC 260/3.0 Programming Paradigms

Original Authors: Margaret Lamb and Bob Tennent
Last Revised: August 30, 2006

Calendar Description

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 languages.

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.


General Topics

  • recursion

  • lists and trees

  • type checking: polymorphic static types vs. dynamic type checking

  • use of accumulators for efficiency
Functional Languages
  • 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 programs

  • higher-order functions, including maps, filters, folds, and lambda expressions

  • lazy evaluation
Logic-based Languages
  • 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 recursion

  • negation as failure

  • use of "(green) cuts" for optimization
Possible Texts
  • 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, 1994.

  • D. Watt: Programming Language Concepts and Paradigms, Prentice-Hall International, 1990.

  • 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.