Com S 541 - Programming Languages 1, Fall 2002

About Com S 541

This page provides general information about the Fall 2002 offering of Computer Science 541 at Iowa State University. 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

Meetings

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

Lectures
Tuesdays, Thursdays
12:40-2:00pm, 1219 Coover (note room change)

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, 3126 Coover

Return to top

Course Textbooks

There are two required texts for the course,

• Haskell: The Craft of Functional Programming, Second Edition by Simon Thompson (Addison-Wesley Longman, 1996, ISBN 0-201-34275-8).
• Adele Goldberg and David Robson's Smalltalk-80: The Language (Addison Wesley, 1989, ISBN 0201136880).

The texts, plus some additional resources, will be on reserve at the Parks library.

We will supplement the text 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.

Due to the vast amounts of spam from networked email providers like hotmail, yahoo, etc., if you send email from one of these providers, we can't guarantee that we'll read it quickly or notice it. For fast responses, please send email directly from an Iowa State computer.

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 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 Java, C++, C, Pascal, 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 an integer 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 of the course we will try to investigate aspect-oriented programming (AOP). AOP seems to be an evolutionary advance on object-oriented programming (OOP), in that it builds on OOP by adding new ways of thinking, and new features (especially for for naming and control). The basic plan is to try to design aspect-oriented extensions to Smalltalk, and to notate their semantics using either Haskell or lambda Prolog.

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 design a refinement calculus for a small programming language, to examine its quality using mathematical techniques, and to use it to design and prove correct small implementations of abstract specifications. We will focus on sequential programs, but allow nondeterminism. In more detail the essential objectives for this course are that you will be able to:

• Evaluate programming language features and designs based on their use in building aspect-oriented languages or in doing metaprogramming.
• Solve problems using the object-oriented, functional, and declarative paradigms.
• Describe the strengths and limitations of the object-oriented, functional, and logic 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 textbook and course notes for tasks involving specification, verification, and programming, but some exams may limit your access to such resources.

Justification

The dawn of aspect-oriented programming languages provides a unique opportunity for showing you how research in the design and semantics of programming languages takes place. We will learn by doing. Aspect-oriented programming techniques seem to have some promise for those dealing with very large OO programs and for software product lines.

Knowing how to solve problems using the 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 the twenty-first century you will not necessarily be programming in FORTRAN or C; if you can program in a language such as Smalltalk, C++, or Ada, or other new languages you 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. Similar comments hold true of 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).

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.

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

Return to top

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.

• 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.

• 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.

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 at Iowa State for his initial work on the HTML for these web pages, which I have adapted from another course.

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 Monday, September 16, 2002.