Com S 541 - Programming Languages 1 Fall 2006

About Computer Science 541

This page provides general information about the Fall 2006 offering of Computer Science 541 at Iowa State University. The course's home page is http://www.cs.iastate.edu/~cs541/.

This page 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.

I also maintain information about previous offerings of this course.

Meetings

Lecture attendance is required. The meeting time and location is as follows:

Lectures: Tuesdays and Thursdays, at 12:40PM-2:00PM, 1120 Sweeney.

Discussion sections will be used for makeup lectures, and for help with homeworks and material in the class. The meeting time and location is as follows:

Discussions: Wednesdays 5:10PM-6:00PM, 1120 Sweeney. (Note the change of place.)

Return to top

Course Textbooks

There is one required text for the course.

• Concepts, Techniques, and Models of Computer Programming, by Peter Van Roy and Seif Haridi (MIT Press, 2004).

These text, will be on reserve at the Parks library.

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

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 Catalog: " Survey of the goals and problems of language design. Formal and informal studies of a wide array of programming language features including type systems, naming, state, and control. Creative use of functional and declarative programming paradigms."

Some Explanation

A programming language can be defined as a language capable of expressing anything that can be computed. Examples include general purpose languages, such as AspectJ, Java, Smalltalk, C, Pascal, Haskell, ML, and LISP, and FORTRAN, as well as special purpose languages like the Unix Shell, Perl, and even Lotus 1-2-3's macro language.

A formal study of a language feature is a study that is mathematically precise; descriptions that do not give mathematical precision are said to be informal. Formal studies, also known as semantics, have many uses. One traditional use is as an aid to reasoning about the correctness of programs. Another use is in helping to design a language; the idea being that a language is well-designed if it has a simple and elegant semantics. Finally, one can use semantics to guide the construction of compilers and interpreters, or to prove that optimizations and program transformations are correctness-preserving.

A language's type system fundamentally checks for consistency between names and their uses. For example, it would be a type error in Java to use a Boolean variable where a Stack variable is required. Declarations introduce names for semantically meaningful entities (classes, methods, procedures, variables, types, etc.) and often give other information for them, such as their types. Ways of naming such entities in various contexts can be surprisingly subtle. Some entities have time-varying state, which is of paramount importance in the imperative paradigm and its descendants, such as object-oriented programming. Besides state, the other thing manipulated by programs is control flow, which can be changed by things like jumps, conditionals, loops, and various kinds of procedure calls.

These features play out in different ways across many different languages, and learning about them helps you learn new languages more quickly.

Slant of this offering

In this offering we will study the (relatively) new textbook Concepts, Techniques, and Models of Computer Programming, by Peter Van Roy and Seif Haridi (MIT Press, 2004). This book has an interesting approach to presenting a wide variety of different programming models. Such programming models, or ways of programming, are also known as paradigms. The set of models discussed in the book includes a declarative model, a declarative concurrent model, a message passing concurrency model, an explicit state model, an object-oriented model, a shared-state concurrency model, and a relational model. Several variants are considered. The book not only describes these paradigms, it also describes how to program in them. In particular, it has an especially rich discussion of concurrent lanugage features.

All of the paradigms are presented in terms of the Oz language. Oz forms a kernel on which all the other paradigms are built as extensions. This lends itself naturally to a discussion of semantic models, in particular to operational semantics. Programming in Oz is supported by the Mozart/Oz system.

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. The essential objectives will be helpful for your career as a computer scientist or software engineer; 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 be able to understand, use, and critically evaluate features of programming paradigms and programming languages. In more detail the essential objectives for this course are that you will be able to:

• Solve problems using the different programming paradigms.
• Describe the strengths and limitations of these paradigms for solving different kinds of problems (or in different application domains), especially in relation to each other.
• Explain and answer questions about specific languages that illustrate different paradigms including questions about relevant concepts and major features.
• Design, define, and evaluate parts of programming languages or similar systems and justify your design decisions. Justifications can be by:
  • referring to known programming language concepts,
  • referring to the semantics of the features,
  • making analogies to features in specific languages that illustrate the different paradigms and their success or limitations, or
  • making some more direct argument or proof.
• Explain the tradeoffs and issues involved in the design of various language features.
• Find and critically write about research in programming languages. Evaluations of research should be based on an understanding of:
  • the goals and problems of language design,
  • the successes and limitations of previous approaches, and
  • current research directions.

You will be permitted to use the textbooks and course notes for all exams.

Justification

Knowing how to solve problems using different paradigms is important for several reasons. You can find solutions to problems more surely if you have many different ways to approach problems. In your career you will not necessarily be programming in C, C++, C#, or Java; those who can quickly learn how to program well in new languages will be much in demand.

As parallel programming becomes more important, the use of functional (and declarative) languages may increase. The large telephone company Ericsson uses the functional language Erlang to write all of its software. Functional programming is also a key technology for supporting domain-specific languages. See also Why Functional Programming Matters by John Hughes.

Even if you do not become a programmer, the ideas of the functional paradigm (function abstraction, infinite data structures, continuations, referential transparency) have important applications in all areas of computer science and in many other contexts such as mathematics and engineering.

The ideas of the logic programming paradigm (also known as the relational paradigm) are important in formal methods, especially for specification, and in program analysis and tool building, such as model checking. The key concept of unification is also important for type inference. Moreover, the basic ideas of logic programming are closely related to operational semantics, which is arguably the most important semantic technique for programming languages.

Similar comments hold for the object-oriented paradigm. For example, the idea of data abstraction is certainly a key concept in software engineering and even in contemporary mathematics (category theory).

The new aspect-oriented paradigm may have similar applications and may unveil yet other ideas about programming and programming languges. For example, it seems to provide new ideas about modularity. It certainly provides new insight into the challenges of very large programs, and the demands of software product lines.

Understanding the strengths and weaknesses of the various paradigms is important in applying them to solve problems. Problems in the real world are not labeled with the paradigm that ``should'' be used to solve them, so the choice of paradigm will be important. In programming language and software engineering research, understanding the strengths and weaknesses of the existing paradigms is important for designing better ways to program.

Finally, future languages will probably try to support some blend of these paradigms. Hence it will be useful to understand the different paradigms, as that will help in using. Such understanding will also benefit the design of such languages and accompanying tools (such as IDEs).

Language design is fundamental to mathematics and science because a crucial step in solving a problem is designing an adequate notation for stating the problem (the specification) and expressing the solution. Because computers are general purpose tools, computer scientists, unlike mathematicians and traditional scientists, tend to look at widely different problems. Problems from different application domains often come without a familiar or ready-made notation; thus as computer scientists we often find it convenient to develop a special-purpose notation. These special-purpose notations, when generalized, are specification languages or programming languages. In developing and defining such a language it is helpful to draw on the results of programming language research. These results help you generate plausible designs, avoid errors, evaluate alternative designs, and precisely define the details of the design. Such justification of a design is a necessary step in debugging your design and in ultimately convincing yourself and others that your (final) design is good.

Notations that are similar to programming languages are found in every area of computer science. Besides specification languages, other similar notation systems include: user-interfaces, program libraries, formal models of computation, database query languages, operating system command languages and system call interfaces, mathematical logics, computer instruction sets, expert system shells, network protocols, and many others.

In addition, language design is challenging. Since it is one step removed from programming (you design notations that are used by programmers to write many different programs), the opportunities for good or ill are multiplied. Because of that, it is great fun!

Understanding the tradeoffs and issues involved in language design, and the semantics of various features is useful in language design itself. But it also helps one more easily understand and learn new languages and new language features. It also helps one choose a language for a programming project, and to write compilers or interpreters.

Understanding the concepts and semantics of programming languages is also necessary to make full use of them in new languages. For example, if you want to program in an object-oriented language you need to understand inheritance and message passing. A better understanding of such features, may help you to better program, reason about, and debug your programs. You will become better able to discuss advanced programming ideas with others.

Formal methods (specification and verification) are becoming increasingly important at many companies, and a deep understanding of the semantics of programming languages is also a great help in using formal methods.

Since computer science is a rapidly-changing field, it is important to be able to find and evaluate relevant papers from the research literature, even if you do not usually do research in that area. As a first step, you need to know where to find various kinds of information. It is important to distinguish peer-reviewed research literature, most of which is only found in the library, from drafts available on the web, and from trade publications.

Understanding the ``state of the art'' in programming language research is important for our goal of designing the next programming langauge. It is also important for the following reasons. First, in the business world, it helps predict promising technology for programming. Knowing the goals and problems of language design helps you categorize problems that may arise; this gives you a start towards looking for existing solutions. Knowing about previous approaches to solving such problems will help you avoid mistakes and can point out fruitful approaches to solving design problems. Knowing the current research directions in language design also helps you when you are designing a non-research language, by helping you avoid features that are not well-understood. Conversely, if you are a programming languages researcher, this knowledge tells you places to spend effort.

Enrichment Objectives

Enrichment objectives could be multiplied without limit, but the following seem most important or most likely to be taught.

Several of these relate to my research work on Java and JML. I think it will be interesting and exciting to have you involved in my research work.

• Understand how different approaches to parallel or distributed processing can be reflected in programming languages.

  If you are a programmer, you will probably be programming on a parallel computer or writing distributed programs during your career. If you are a theoretician, you will surely spend much of your efforts thinking about parallel processing.

• Read and write formal descriptions of type systems for small programming languages.

  Type declarations are a simple form of formal specification, and type checking is a simple, automatic form of program verification. Type checking is believed to be of great help in programming, because it catches errors before a program is run, and type information is used heavily in optimizing compilers to improve generated code. The techniques of type checking can also be applied by hand in dynamically typed languages (like Smalltalk, LISP, or Scheme), and can be used for other purposes (other kinds of static analysis). These techniques are a hot topic of research, and have been so for years. Type systems of programming languages have a deep connection to logic (the Curry-Howard isomorphism). Studying type systems and paying attention to type issues in language design seems to help organize and regularize a language design.

• Prototype type systems and language designs by using semantic interpreters.

  The study of semantic interpreters and formal semantic description techniques reinforce each other and, we believe, help solidify your understanding of major programming language features. Such techniques are also a valuable tool for language designers. They add precision to descriptions and can be used to help prevent ambiguity. Formal techniques can also be used to reason about properties of a design, such as whether the design is secure, or whether parts of the language are not useful. More important, careful study can reveal new and interesting possibilities for language features, or the simplification of features. Primitives such as procedure closures, monitors, and continuations first emerged as the result of semantic descriptions. Finally, one can use such techniques to aid in judging language designs, by revealing hidden interactions between features, and by giving you a sense of how simple or complex the design is. Writing semantics-based interpreters in an operational or denotational style is a valuable tool for animating language descriptions that helps in debugging and refining language designs.

• Apply the techniques and results of language design in other areas of computer science.

  This goal may be important for doing successful research in other areas of computer science. Certainly much fruitful research in computer science happens at the boundaries between different areas of computer science. A few examples of interaction between programming languages and other areas: object-oriented databases, capability based operating systems, formal language theory, reduced instruction set computers, data flow computers, type theory, knowledge representation languages.

• Design a domain-specific language or evaluate parts of such a design.

  The argument for the study of domain-specific languages is as follows. Programming languages are the main technology that makes it possible for humans to instruct computers; however current programming languages are too hard to use. They take years of study to master, and there are not enough people with the necessary training. It also seems that there won't be enough people with this training anytime soon. As language designers, we should respond to this need by creating tools to create languages that help others without specialized training in programming to do their work.

Return to top

Prerequisites

The formal prerequisites in the Iowa State University catalog are Com S 342 or Com S 440.

The formal prerequisite in the Iowa State catalog is successful completion of either Com S 440 (Principles of Compiling) or Com S 342 (Principles of Programming Languages); that is, successful completion of either an undergraduate course in compiler construction or programming languages.

See the professor if you have questions about the prerequisites.

The skills taught in Com S 440 relevant to Com S 541 include the ability to:

• read and write context free grammars,
• estimate the run-time costs of various language features, such as parameter passing mechanisms,
• modularize, document, and manage a large and evolving piece of software.

The skills of Com S 342 relevant to Com S 541 include the ability to:

• Modify interpreters to change or enhance their behavior so as to implement various features of programming languages such as: control flow, variables, recursion, scoping, syntactic sugars, arrays, parameter passing mechanisms, objects, and inheritance.
• Write programs using such features, and explain (using appropriate terminology) and answer questions about the user-visible behavior of such programs.
• Explain (using appropriate terminology) and answer questions about the data structures and algorithms used in interpreters to implement such features.
• Compare alternatives in the design and implementation of such features.
• Solve problems using the functional paradigm.

If you do not have this background, especially if you are interested in research in programming languages, you should take Com S 342 or Com S 440 (preferably both if you want to do research in this area). Mere reading of texts on these subjects is not enough.

Return to top

Acknowledgments

Many thanks to Curtis Clifton (now at Rose-Hulman) for his initial work on the HTML for these web pages, which I have adapted from another course, and his style sheets, which I have also adapted. Thanks to Steve Shaner for getting me to use an RSS feed for these web pages, and thanks to Evagoras Charalambous for the XSL style sheet and style sheet for showing such RSS feeds as a web page.

I thank the many people I have talked to over the years about programming languages, especially Barbara Liskov, David Gifford, Kelvin Nilsen, Markus Lumpe, David Schmidt, Dan Friedman, and the people mentioned in the overview and history of this course, including the authors of the various textbooks I have used.

Return to top

Last modified Wednesday, August 23, 2006.

This web page is for the Fall 2006 offering of Com S 541 at Iowa State University. The details of this course are subject to change as experience dictates. You will be informed of any changes. Please direct any comments or questions to Gary T. Leavens.