Computer Science 340 (Detailed Information)

Introduction

The main theme of the course is to teach two alternative models of computation to the student: functional programming (by introducing Haskell), and logic programming (by introducing Prolog). To round out the academic value of the course, we will spend a little time talking about programming languages in general. We will talk a little about syntax and semantics, we will see how language features are realized, and how to evaluate the features of a language.

Functional and logic programming languages are, at a very superficial level, quite different from the languages that most modern students are taught from day one. But on a deeper level, the differences are not as great as it might seem at first. The main difference is perspective. All programming languages formalize the idea of computation. Each language paradigm looks at computation from a slightly different angle. By learning how to look at computation from different angles, the student's skills are strengthened, and the number of ways to think about problem solving with computation is increased.

Neither Haskell nor Prolog is used widely in industry. But it is a reality that in the "real world," a computer scientist will be required to learn new languages (even ones that have not been invented yet!) and quickly become productive using them. The skill of learning a new language will no doubt benefit the student as much as or more than learning any particular programming language.

Prolog

A crash course in Prolog.
Topics

  1. Database Prolog: facts, rules and simple recursion
  2. Unification and Resolution
  3. Pure Prolog: recursive data structures,
  4. Non-deterministic programming
  5. Full Prolog
  6. Meta-circular interpreters
  7. *Constraint Logic Programming
  8. *Definite clause grammars
  9. *The formal underpinnings of logic programming.
  10. *Mini-project: A functional programming language in Prolog

Haskell

A condensed first course in functional programming. Some practice before the theory.
Topics

  1. Expressions, functions, evaluation
  2. Recursion
  3. Types, polymorphic types
  4. Type inference
  5. Currying
  6. Higher-order functions
  7. Lazy evaluation, and infinite datastructures
  8. *Monads
  9. *Lambda Calculus: The formal underpinnings of functional programming.
  10. *Mini-project: A Prolog-like language in Haskell