About Com S 541
Homework & Grades
Q & A
Iowa State U. Homepage
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:
Lecture attendance is required. The Meeting time and location is as follows:
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:
There are two required texts for the course,
We will supplement the text with other material as described in the syllabus's bibliography.
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.
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.
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."
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.
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.
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:
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.
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.
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.
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:
The skills of Com S 342 relevant to Com S 541 include the ability to:
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.
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.
Last modified Monday, September 16, 2002.
This web page is for the Fall 2002 offering of Com S 541 at Iowa State University. The details of this course are subject to change as experience dictates and are still in draft form. Once the semester starts, students will be informed of any changes. Please direct any comments or questions to Gary T. Leavens at leavens@cs-DOT-iastate-DOT-edu.