Com S 342 - Principles of Programming Langauges Spring 2005

About Computer Science 342

This page provides general information about the Spring 2005 offering of Computer Science 342 at Iowa State University. The course's home page is http://www.cs.iastate.edu/~cs342/. This page, which descibes the course is organized as follows:

1. Meetings
2. Course Textbooks
3. Computer Accounts
4. Accommodations for Disabilities
5. Course Description
6. Objectives
7. Prerequisites
8. Acknowledgments

The course grading policy and syllabus are on separate web pages.

Information about previous offerings of this course is also available.

• Spring 2004
• Fall 2001
• Earlier versions of the course with different texts

Meetings

Lectures

Lecture attendance is required. The lecture meets on Tuesdays and Thursdays at 2:10-3:30pm in 1115 Pearson.

Discussions

Attendance at discussion sections is strongly recommended. Meeting times and locations are as follows:

• Section A, Wednesdays 9:00-9:50am, in Atanasoff B29
• Section B, Wednesdays 4:10-5:00pm, in Marston 209

Return to top

Course Textbooks

There are two required texts for the course.

• Essentials of Programming Languages (second edition) by Daniel P. Friedman, Mitchell Wand, and Christopher T. Haynes MIT Press, 2001, ISBN 0-262-06217-8.
• The Little Schemer (Fourth Edition) by Daniel P. Friedman and Matthias Felleisen, MIT Press, 1996, ISBN 0-262-56099-2.

There are two optional (but recommended) texts for the course.

• Structure and Interpretation of Computer Programs (second edition), by Abelson, Harold, and Gerald J. Sussman with Julie Sussman. MIT Press, Cambridge, 1996.
• Revised⁵ Report on the Algorithmic Programming Language Scheme, Richard Kelsey, William Clinger, and Jonathan Rees, editors, 1998. You can get this report on-line from our resources page.

All the texts are on reserve at the Parks library.

We will supplement the texts with other material as described in the syllabus.

Return to top

Computer Accounts

You must have an account on the department Unix machines. You should either read your email there, or have it forwarded to where you read it.

Return to top

Accommodations for Disabilities

We would like to hear from you if you have a disability that may require some modification of seating, testing, or other class requirements. If so, please request that the Disability Resources staff send a SAAR (Student Academic Accommodation Request) form verifying your disability and specifying the accommodation you will need. Then bring the SAAR form along and talk to Gary Leavens as soon as possible so appropriate arrangements may be made.

Return to top

Course Description

From the Iowa State University Bulletin: "Organization of programming languages emphasizing language design concepts and semantics. Study of language features and major programming paradigms, especially functional programming. Programming projects."

Explanation

The currently popular computer language is constantly changing. Fifteen years ago it might have been Pascal or C; 10 years ago it was probably C++; today it is probably Java (or C#). Now it seems time for another change. There are a host of other languages (Perl, PHP, Visual Basic, JavaScript, Python, Ruby, Haskell, etc...) that are popular for their own classes of problems and programming styles. Therefore, to have a career in computer science means having to learn new programming languages.

To meet your need to learn new programming langauges quickly, and to help you work better with the languages you do use, this course seeks to provide a forum where you can develop an understanding of the basic design decisions that are part of every programming language. Things like:

• How does one divide programs into manageable pieces?
• What conceptual models can be used for translating a real world problems into programs?
• What are good ways to express programming idioms?
• What features must a programming language provide?
• What additional features will help simplify things for users?
• How does one precisely describe a programming language?
• How should a language be implemented?

Our technique for studying these questions will be two-fold. First we will learn the functional programming language Scheme. Functional programming is much different from the imperative programming that most of us are used to from languages like C++, Visual Basic, or Java. Learning functional programming helps one to develop a more thorough understanding of the various ways of organizing programs.

After we have developed some experience with Scheme we will develop a series of interpreters for various small programming languages. These interpreters allow us to experiment with various design decisions, how those decisions interact, and how different language features are implemented.

Return to top

Objectives

The general objectives for this course are divided into two parts: a set of essential objectives, and a set of enrichment objectives. These objectives are linked to the course's learning outcomes (in references that look like this: [B3]). The essential objectives will be helpful for your career as a computer scientist; hence we want to help you to master them. You are encouraged to explore the enrichment objectives both for their own sake and because learning more about those will help deepen your understanding of the essential objectives.

Essential Objectives

In one sentence, the main objective is that you will have a deep, working knowledge of the functional paradigm [A1] [A3] [B1] [C1] and the key ideas used in modern programming languages [A1] [A3] [B1] [B2] [C1]. In more detail the essential objectives for this course are that you will be able to:

• Write and modify programs using a mostly-functional style [A1] [A3] [B1] [C1]. This means programming that makes effective use of the abstraction mechanisms of functional languages, such as higher-order functions (functions that take functions as arguments and return functions as results) to achieve generality and abstraction.
• Write and modify programs that make effective use of data abstraction [A1] [A3] [B1].
• Modify interpreters to change or enhance their behavior so as to implement various features of programming languages [A1] [A3] [B1] [B2] [C1] such as: control flow, variables, recursion, scoping, syntactic sugars, arrays, parameter passing mechanisms, type checking, objects, classes, and inheritance.
• Write programs using such features, and explain, using appropriate terminology, the user-visible behavior and performance of such programs [A1] [A3] [B1] [B2] [C1].
• Explain, using appropriate terminology, the data structures and algorithms used in interpreters to implement such features [A3] [B2].
• Compare alternatives in the design and implementation of such features [A3] [B2].

Conditions

You will be permitted to use the textbook and course notes for tasks involving programming, but not during tests. On tests you may be permitted a small amount of reference material.

Justification

The functional style is one answer to the question: "What are good ways to program?" It also represents one major way to organize a programming language for parallel processing. Even if you do not become a programmer, the ideas of functional programming (function abstraction, referential transparency, etc.) have important applications in all areas of Computer Science (such as software specification, algorithm design, and of course in manipulation and specification of programming languages). These ideas also have application in many other contexts such as mathematics and engineering.

Data abstraction is a key idea for allowing programs to be easily modifiable. It forms the basis for the object-oriented style of programming.

Understanding the key ideas used in modern programming languages will help you learn new languages quickly, by mapping key ideas and concepts from this class into the new language's syntax and semantics. For example, Java and other object-oriented languages (such as Smalltalk-80) use the "indirect model" of storage, which will be unfamiliar to you if you've programmed only in C++, C, Pascal, or Ada (all of which use the "direct model"). We will study the indirect model in detail, and you will gain practical programming experience with it, using Scheme. Learning this and other key ideas will also help you read (or write!) a new language's reference manual.

More importantly, understanding of fundamental concepts and run time implementation ideas will help you to better understand whatever language you program in; this will help you program more effectively. Being able to program better will also give you increased job satisfaction.

Enrichment Objectives

Enrichment objectives could be multiplied without limit, but the following seem most important or most easily taught using the course text. Following each of the enrichment objectives is a brief justification.

• Design or critically evaluate design alternatives for languages and language features by careful consideration of their semantics [A3] [B2] [C1].
  
  In designing software you will often be confronted with decisions about features that resemble those found in programming languages. This is particularly true for the design of user-interfaces and abstract data types. For example, a database management system has to deal with names for (say) relations, and thus must have scope rules; it will also have (difficult) type-checking problems, its query language will have control-flow issues, there will be demands for sweeter syntax, etc. The basic principles taught in this course can help with such design decisions, and can provide guidance for overall designs. Such skills are also important in judging whole languages, for example if you need to decide on a new language for new programming project, or if you become a manager of a group of programmers.
  
  
• Be able to write the types of functions and use them in writing software [A3] [B1].
  
  Types are an important way to summarize the behavior of functions, and a key way to check the basic sanity of software. Although types are best checked automatically by software tools, an understanding of them is important for writing such tools, and for aiding the quick construction of correct software.
  
  
• Use algebraic techniques to modify, derive, and prove programs correct [A1] [A3] [B1].
  
  Such techniques are a powerful aid in writing sophisticated programs and in reasoning about them. They represent the future of software engineering, which lies in design to specification (as opposed to debugging).
  
  
• Explain and answer questions about the features found in widely-used programming languages, such as Perl, C, C++, Java, Visual Basic, etc [C1].
  
  This is a good way to deepen your understanding of such features. It also helps in informal or technical discussions.
  
  
• Explain and answer questions about design principles such as regularity, the zero-one-many principle, orthogonality, etc. [A3] [B2] [C1].
  
  These principles form good rules-of-thumb that you can use in designing programs or languages.

Return to top

Prerequisites

The formal prerequisites in the Iowa State catalog are successful completion of Com S 321, English 104, Com S 330 or Cpr E 310, and either Com S 309, 362 or 363.

Return to top

Acknowledgements

My original ideas for this course at Iowa State were developed with the help of Kelvin Nilsen. Final exams for similar courses at other universities were provided by Kim Bruce (Williams College), Sam Kamin (University of Illinois), Dan Friedman and J. Michael Ashley (Indiana), and John Mitchell (Stanford); these helped provide perspective on what is important for such a course. Thanks also to Simanta Mitra and Markus Lumpe for discussions about variations of this course taught at Iowa State. For this version of the course, I owe a great deal of thanks to Clyde Ruby, who was my TA and then an instructor for the course and who provided much of the infrastructure for the course. I also owe many thanks to Curtis Clifton at Iowa State for collaboration much work on these web pages, for collaborative discussions about the course, and for collaboration on the Scheme type checker we sometimes use. Thanks also to Brian Dorn for further work on the type checker. Further thanks are due to authors of the textbooks we have used. Thanks all!

Return to top

Last modified Tuesday, February 8, 2005.

This web page is for the Spring 2005 offering of Com S 342 at Iowa State University. The details of this course are subject to change as experience dictates. You will be informed of any changes. Thanks to Curtis Clifton for help with these web pages. Please direct any comments or questions to Gary T. Leavens.