CS 381: Programming Language Fundamentals (Summer 2005)

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 20 Introduction, Haskell: Values, Types, Expressions, Tuples H2, 5.4.1
June 21
 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 22
 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 23 Haskell: Definitions, (Lazy) Evaluation, Higher-Order Functions H3, 5.4.3, 3.4.7
2 June 27 (Lazy) Evaluation, Higher-Order Functions, Types H2.3, H3, 3.4.7
June 28 Types, Parametric Polymorphism
 H2.3, H3, 6.4
June 29
 Data Types, Pattern Matching
 H2.2, H4-H4.3, 5.4.4
June 30 Continued  
3 July 5 Data Types, Pattern Matching (continued)
 H2.2, H4-H4.3, 5.4.4
July 6 Type Classes H5
July 7 Type Classes H5
4 July 11 Block Structure and Scope, Activation Records 7.1, 7.2, 7.3.1, 7.3.3
July 12 continued  
July 13 Review of HW1  
July 14 Parameter Passing, Exceptions 7.3.2, Exercise 7.6, 5.1.1, 8.2, 13.3.4, TestFinally.java
5 July 18 Continued  
July 19 Languages and Interpreters 4.1.2, Expr.hs, Expr2.hs, TypeCheck.hs
July 20 Languages and Interpreters  
July 21 Midterm Sample solution
6 July 25 Type Checking MILtc.hs
July 26 Type System 6.1, 6.2
July 27 Type Checking MILtc.hs
July 28 Type Checking 6.4, 13.3.5 MILtcN.hs
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 8 Prolog: Backtracking, Terms and Lists
Aug 9 Prolog: The Cut, Operational Semantics opsem.pl
Aug 10 Prolog examples examples.pl
Aug 11 FINAL EXAM Solution

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: extended to 07/07/04 (23:59:59pm)
    Type definitions to be used: HW1types.hs
    Sample solution: HW1.hs Test cases and points: test1.pdf
  2. Haskell Data Types [pdf] Due date: Extended to 07/19/04 (23:59:59pm)
    Helpful files: Sample solution: HW2.hs Test cases and points: test2.pdf
  3. Scoping and Parameter Passing [pdf] Due date: 07/27/04 (12pm, before class!!!)
    Sample solutions: HW3.sol
  4. Semantics [pdf] Due date: 08/09/04 (12pm, before class!!!)
    Sample solutions: HW4.sol
  5. Prolog [pdf] Due date: 08/12/04 23:59:59
    Definitions to be used: hw5.pl
    Sample solutions and test cases: HW5.sol

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: Monday 1:00pm - 2:00pm
 Dear 115

Tuesday 11:00am - 12:00pm
 Dear 115

Wednesday 11:00am - 12:00pm Dear 115
Midterm Exam: Thursday, July 21st.
 12:00pm-1:00pm Rogers 230
Final Exam: Thursday, Aug 11th.
 12:00pm-1:00pm
 Rogers 230