PROGRAM TITLE

Programming Language Theory and Practice

INSTRUCTORS

Nelson, Neal (nealn@evergreen.edu),

Shulman, Sherri (sherrishulman@gmail.com), (sherri@evergreen.edu),

SUBJECT AREA

Computer Science, Logic, Math

PROGRAM TIMES

Mon 10am-3pm

Tues 10pm-3pm

Wed 10am-12pm

Thu 10am-5pm

Announcements

1. Winter Quarter Class Page
2. Logic Programming Dec 6 will meet at 10 am instead of 1 pm.
3. Evaluations:
   1. Neal's eval group
   2. Sherri's eval group
   3. Neal's eval schedule
   4. Sherri's eval schedule
4. Winter Quarter Textbooks
5. Please fill in this credit agreement form. Find your login name and indicate which threads you are taking for credit, and indicate the total number of credits you are attempting. If your login name is missing, please add it to the end. Each thread is 4 credits.
6. This master page and the syllabi are still in draft format. Details may change, but the schedule, the topics, and the textbooks are committed.
7. No class Sep 24, 25 and Oct 2 (Jewish Holidays). The first day of class will be Wed Sep 26 because of the Jewish Holidays. We will post readings for you to get started and send out email.
8. This program is planned for 16 credits in the fall, 12 in the winter, and 12 in the spring with an add-on 4 credits in winter and spring for Machine Learning and Data Mining with Richard Weiss.
9. Tutorial for cnc_submit which is used for submitting assignments on the computer science server ada. You'll need to change the "csf" to "cnc" when you read this tutorial.
10. This page is still in draft format.
11. First day of class: Wed Sep 26.
12. This page and the syllabus links are still in draft form, but the schedule (below) and books (below) are correct.
13. The syllabus pages are password protected. We will provide the password on the first day of class.

PROGRAM DESCRIPTION

Programming Language Theory and Practice is an advanced Computer Science program. We will concentrate on:

1. The Lambda Calculus (and Haskell in Winter and Spring)
2. Types and Programming Languages
3. Formal Languages and automata theory
4. Parsing
5. Computability
6. Prolog and Logic Programming
7. Machine Learning and Data Mining (an associated winter and spring module with Richard Weiss)

REQUIRED TEXTBOOKS

1. Types and Programming Languages, by Benjamin Pierce.
2. Lecture Notes on the Lambda Calculus, by Peter Selinger.
3. Lambda Calculus and Types, by Andrew D Ker.
4. Introduction to Lambda Calculus, by Henk Barendregt and Erik Barendsen.
5. Languages & Machines 3d edition, Sudkamp ISBN 978-0-321-32221-0 (This book recently went out of print. It is available from a variety of sources such as Amazon, Valore books, alibris, abebooks, textbooks.com. The author does not have a pdf of the book, but also thought used copies would be available from the above sources..)
6. Learn Prolog Now!
7. An Introduction to Prolog Programming
8. From Logic Programming to Prolog

SCHEDULE

Room assignments are still under negotiation.

SYLLABI

1. Foundations of Programming Languages (Lambda Calculus)
2. Types and Programming Languages
3. Formal Languages
4. Logic Programming

CREDIT POLICY

You cannot get partial credit for any thread: either you get credit for Lambda Calculus or you don't, either you get credit for Formal Languages or you don't, etc. In order to get credit for any thread you must:

1. Complete all exams
2. Complete homework assignments and labs
3. Attend and participate in class

If you do the work, you will get credit. The quality of your work will determine the nature of your evaluation. Don't confuse credit with quality. A narrative evaluation allows the faculty to include aspects of your performance that would not ordinarily be reflected in a grade. That works both ways. If you do great work, you get credit AND you get an evaluation that reflects that work. If you work hard but have some areas that you don't understand, we can emphasize your efforts while also commenting on the areas that you still have to work on. If you don't work hard, and there are many areas that you don't understand well, we can also include that in the evaluation.

HOMEWORK POLICY

1. All textbook reading should be completed prior to class. This allows you to participate more meaningfully in the class discussion and ask appropriate questions.
2. All homework assigned in a week are due the following week (unless otherwise specified). So if you are given an assignment in Formal Languages during week 1, it is due week 2. In general, you should aim at completing your work for the first meeting of the week (so work for Formal Languages should be competed by Monday; work for Haskell should be completed by Tuesday, etc.) This allows us to review the work, and start on the next weekly topic.
3. There are no (explicit) penalties for late work. However, we will discuss answers to problems and review sample solutions to programs. If you turn in your work after solutions have been posted or discussed, and this is a regular habit, then this may be reflected in your evaluation. Additionally, if you are consistently late with your work, you will have trouble keeping up with the class topics.
4. Concept assignments (those that do not require you to write or complete a program) should be turned in on paper.
5. All assignments should be turned in using a submit program. Directions on using submit will be posted on the webpage when available (and before you need it!)
6. Working in groups for homeworks and labs is fine, but all members of the group should be identified on any group work. Turning in work without acknowledging all contributors is considered academic dishonesty. Please cite all outside references used as well, including websites and other sources. Please limit the size of your group to 3 people.
7. All work on exams should be your OWN WORK. No collaboration is allowed.

CREDIT ALLOCATION

Yearly Credit

PROGRAM DESCRIPTION

Fall Quarter

Lambda Calculus                                    

We will study mathematical foundations of programming languages as developed through the untyped and typed lambda calculus, including syntax, types, semantics, model theory, and the correspondence with logic and proofs (fall).

There are two class periods per week with lectures and lab time. We will have weekly assigned readings and assignments from the readings. There will be two exams.

Credit Equivalency: Foundations of Programming Languages (4cr upper division science))

Formal Languages 1                                   

During the fall and winter the class studied formal languages using the textbook Languages and Machines by Thomas Sudkamp. In the fall we covered the definition of regular sets, grammars, and languages and their properties, context free grammars, normal forms for context free grammars, and finite automata and their properties. Students were evaluated on weekly chapter assignments and two exams.

Types and Programming Languages         

This course focuses on the the mathematical foundations for types in programming languages. The approach starts with the development of types for the Lambda Calculus. The fall quarter emphasizes the core type theory and the winter quarter leans toward type extensions and implementations.

There are two class periods per week with lectures and lab time. We will have weekly assigned readings and assignments from the readings. There will be two exams.

Credit Equivalency: Types and Programming Languages (4cr upper division science))

Logic Programming

Prolog(PROgrammation et LOGique) is a logic programming language widely used in Artificial Intelligence. It is a high-level programming language which enables the user to build programs by stating what they want the program to do rather than how it should do it. Due to Prolog's grounding in first-order predicate logic it is intended to be more analogous with human deductive reasoning than other programming languages.

This course will provide students with the technical skills needed to implement Artificial Intelligence techniques in compact and efficient Prolog programs. By the end of the module students will be able to construct Prolog programs of all sizes and complexity that implement a range of AI techniques. The students will be able to utilise the skills learnt during this course in many areas:

1. Natural Language Processing and Generation,
2. Knowledge Representation and Reasoning,
3. Database Search,
4. Problem Solving,
5. Planning,
6. Cognitive Modelling,
7. Logic and Theorem Proving,
8. General computational skills

Winter Quarter

Haskell Programming 1                                   

In the fall, students studied the advanced functional programming concepts and techniques using the Haskell programming language. Weekly topics included higher-order functions, programming with lazy evaluation, modules, abstract data types, algebraic data types, type classes, overloading, polymorphism, and an introduction to monads. Students were evaluated based on 8 programming assignments and a final exam.

Types                           

In development.

Lambda Calculus and Types

In development.

Machine Learning and Data Mining 1

Machine Learning associated module with Richard Weiss

Spring Quarter

Computability

In development.

Compiler Project

In development.

Haskell Programming 2                                   

During the winter the students studied higher order functional combinators and applicative functors, monoids, monads (including the state monad) and polymorphic type inference. Students were evaluated based on their programming portfolio of weekly assigned work and one exam.

Machine Learning and Data Mining 2

Machine Learning associated module with Richard Weiss