CS 381: Programming Language Fundamentals (Summer 2006)

Course Description

CS 381, Programming Languages, is a four-credit course for undergraduate students. This course gives an introduction to the concepts found in a variety of programming languages and to languages from a number of different paradigms. Topics to be covered are: Haskell, Prolog, scoping, parameter passing, types, polymorphism, exception handling, semantics.

Contents of this web page:

Learning Objectives

On completion of the course, students must demonstrate the ability to:

Prerequisites

I assume that students have the following background: If you don't recall these concepts, you should become familiar with them before the class starts.

Textbook

The textbook I recommend as backup reading material is:
Concepts in Programming Languages
By John C. Mitchell, published by Cambridge University Press 2003.

I will also provide access to my slides.

Haskell

Most programming will be done in Haskell, a modern functional programming language. In particular, we will use Haskell as a formal notation to explain concepts of programming languages. It is therefore absolutely essential that you acquire profound programming skills in Haskell! I will introduce Haskell with lots of examples during the first three weeks of the class. To become confident in writing Haskell programs, you should work on all the (non-graded) small programming assignments that I will give during class. A lot of information on Haskell (documentation, textbooks, compilers, examples, ...) can be found on the website
haskell.org
There you will also find links to several tutorials. You might start by looking at the short summary. In the class schedule I will refer to sections of the so-called A Gentle Introduction (which is actually not so gentle after all, but provides a concise and comprehensive summary). I have also put an introductory a textbook and the Haskell Report (the latter is not suited for beginners) on reserve in the library to provide additional information on Haskell:
Haskell: The Craft of Functional Programming
By Simon Thompson. Addison-Wesley, 1999.

Haskell 98 Language and Libraries: The Revised Report
Edited by Simon Peyton Jones. Cambridge University Press, 2003.

We will mainly use the ghci interpreter, which is available on many different platforms. It is already installed on the CS and ENGR machines, but only on Unix. Just enter ghci in the Unix shell. In ghci, enter :? for help on commands; enter :q to quit the interpreter.

Information about Prolog is also available on the Internet, see the links provided here. We will be using SWI-Prolog.

Class Schedule/Preparation

The following table shows the topics that are covered in each class. The "Prepare" column shows what you can read to prepare for the class if you like (plain numbers refer to chapters/sections of the textbook, "H" refers to the "A Gentle Introduction to Haskell", and file names refer to programs).

Week Date Topics Prepare/Rework
1 June 26 Introduction, Haskell: Values, Types, Expressions, Tuples H2, 5.4.1
June 27
 Haskell: Lists, Functions H2, H3, 3.4.3, 5.4.2 (Lists), 2.1.2, 3.4.5, 3.4.6, 4.2.1 (Functions)
June 28
 Haskell: Lists, Functions (cont) H2, H3, 3.4.3, 5.4.2 (Lists), 2.1.2, 3.4.5, 3.4.6, 4.2.1 (Functions)
June 29 Haskell: Definitions, (Lazy) Evaluation, Higher-Order Functions H3, 5.4.3, 3.4.7
2 July 5 (Lazy) Evaluation, Higher-Order Functions, Types H2.3, H3, 3.4.7
July 6 Types, Parametric Polymorphism
 H2.3, H3, 6.4
July 7
 Data Types, Pattern Matching
 H2.2, H4-H4.3, 5.4.4
3 July 10 Data Types, Pattern Matching
 H2.2, H4-H4.3, 5.4.4
July 11 Data Types, Pattern Matching
 H2.2, H4-H4.3, 5.4.4
July 12 Type Classes H5
July 13 Type Classes H5
4 July 17 Block Structure and Scope, Activation Records 7.1, 7.2, 7.3.1, 7.3.3
July 18 Block Structure and Scope, Activation Records  
July 19 Parameter Passing, Exceptions 7.3.2, Exercise 7.6, 5.1.1, 8.2, 13.3.4, TestFinally.java
July 20 Review for midterm  
5 July 24 Midterm  
July 25 Languages and Interpreters 4.1.2, Expr.hs, Expr2.hs, TypeCheck.hs
July 26 Languages and Interpreters  
July 27 Type Checking MILtc.hs
6 July 31 Type Checking MILtc.hs
Aug 1 Type System 6.1, 6.2
Aug 2 Type Checking 6.4, 13.3.5 MILtcN.hs
Aug 3 Semantics  
7 Aug 1 Semantics  
Aug 2 Denotational Semantics 4.2 Sem.hs
Aug 3 Operational Semantics  
Aug 4 Prolog: Predicates, Goals, and Rules 15
8 Aug 14 Prolog: Backtracking, Terms and Lists
Aug 15 Prolog: The Cut, Operational Semantics opsem.pl
Aug 16 Prolog examples examples.pl
Aug 17 FINAL EXAM

Slides

I will try to make the slides available online before each lecture, but be aware that there might be some last-minute changes.

1.Introduction [pdf]
2.Haskell [pdf]
3.Scope & Parameters [pdf]
4.Exceptions [pdf]
5.Languages and Interpreters [pdf]
6.Types [pdf]
7.Semantics [pdf]
8.Prolog [pdf]

Additional Explanations, Frequently Asked Questions

Here I collect definitions and explanations for some terms and topics that might be difficult to understand or to remember and for which there is no explicit definition given on the slides or in the textbook. I also try to add explanations for frequently asked questions by students. If somebody would like to have something added, please let me know (it would be great if you tried a definition yourself!). Also if you find errors or have other suggestions for improving this reference list, please send me an email.

Point-free definition
This means that a function definition avoids, as much as possible, variables for objects that are not functions (lists, numbers, ...) and defines new functions by application of higher order functions. In other words, point-free function definitions avoid unnecessary lambda-abstractions and also recursion in the definition.
Prolog Terms vs. Prolog Predicates
Terms look a lot like predicates. How are they related? Syntactically, any term can be used as a predicate. You can have terms like man(adam) in your program, and you can also use man as a unary predicate at the same time (although it is not recommended to do that unless you really understand the difference). For example, 
  man(adam).
  man(X) :- ...
defines a predicate man. Even in one goal you can use terms and predicates of the same name at the same time. For example, the following goal asks whether the predicate man is true for the term man(adam) and for the atom adam. 
  man(man(adam)), man(adam).
Notice that the first and third occurrence of man are as predicate names, whereas the second use of man is as a functor. Similarly, the first expression man(adam) is a term (as an argument of the predicate man), whereas the second expression man(adam) is a goal. Note that there are no declarations of functors, unlike in Haskell where constructors have to be declared in data type definitions.

A source of possible confusion is the fact that Prolog terms are used to represent two different things: (i) structured objects (terms) and (ii) programs (predicates), and there is no name space distinction between the two. Hence, if you use terms to represent structured objects or to just tag or mark objects (like var(x)), you usually won't have rules for these terms. Rather these terms are used in your program as patterns of other predicates.

Singleton Variables
If you get a warning about a "singleton variable" for one of your rule, you should check your rule carefully. Singleton variables are variables that are used only once, which often indicates a typo. If it is correct that the variable is used only once, you can always replace it with a wildcard (_), which is a Good Thing to do. Then the error message disappears.

Homework

  1. Haskell [pdf]. Due date: 07/07/06 (23:59:59pm)
    Type definitions to be used: HW1types.hs
    Sample solution: HW1.hs
  2. Haskell Data Types [pdf]. Due date: 07/18/04 (23:59:59pm)
    Type definitions to be used: HW2types.hs
    Sample solution: HW2.hs
  3. Higher-order functions [pdf]. Due date: 07/21/04 (23:59:59pm)
    Type definitions to be used: HW3types.hs
    Sample solution: HW3.hs
  4. Parameter Passing [pdf] Due date: 07/28/04 (23:59:59pm)
    Sample solutions: HW4.txt
  5. Type Checking and Semantics [pdf] Due date: 08/11/06 (23:59:59pm)
    Sample solutions: HW5.hs
  6. Prolog [pdf] Due date: 08/18/06 (23:59:59pm)
    Definitions to be used: hw6.pl

Grading (Homework)

Grading (General)

Grades will be roughly computed as follows: For 90% or more, you get an A; for less than 30% you get an F. The remaining grades in between are assigned linearly. I might lift individual grades if clustering of points achieved by students suggests so (but I won't assign grades worse than indicated by the above linear schema).

Grading Results

Results. The first column contains the last 4 digits of your OSU ID.

Academic Dishonesty

I will strictly enforce the departmental policies on academic dishonesty. Please read carefully. Do not take chance, you will be caught if you cheat.

Important Dates and Times

Class Time: Mon-Thur
 12:00pm - 1:00pm Rogers 230
Office hours: By Appointment
Midterm Exam: Mon, July 24th
 12:00pm-1:00pm Rogers 230
Final Exam: Thu, Aug 17th
 12:00pm-1:00pm
 Rogers 230