This page gives access to information about the course offering of ``Programming Languages 1'' by Gary T. Leavens for the Department of Computer Science at Iowa State University as taught in Fall 1997.
The Fall 1997 offering was different from my previous offerings in 1990-92, 1993, 1994-95, 1996, and Spring 1997, although it is somewhat similar to the 1994-95 offerings.
This is an old offering of the course. Information about the latest offering and other offerings is also available.
Information is available under the following headings.
Also available (some only locally) are the following.
When I teach this course, I like to change what (and even how) I teach to some extent each semester. I started teaching (in 1990-92) based on readings, notes, and projects from Dave Gifford's 6.821 course at MIT (for which I was a TA). I gradually found that the students at Iowa State needed more programming experience, and so taught various languages as part of the course (usually towards the end of the semester). At various times these have included: OBJ3, Prolog, lambda-Prolog, Scheme, Standard ML, Haskell, Smalltalk, C++, and SR. (I have also tried to find the right balance between this course and the undergraduate programming languages course, which was been teaching programming and paradigms until Fall 1995, but now teaches some functional programming in Scheme and essential semantic ideas using interpreters.)
Continuing the development of 541, I taught the course in 1993 based on Watt's Programming Languages: Concepts and Paradigms, with a supplement of Watt's Programming Languages: Syntax and Semantics; the focus was on language design, not semantics. In 1994 and 1995, I reversed the use of these books, and taught a course centered around semantics, especially for object-oriented programming languages; this version of the course also did a considerable amount of operational semantics, using lambda-Prolog to animate these semantics. I carried this trend to perhaps its conclusion by using David Schmidt's new book The Structure of Typed Programming Languages in 1996. Although I'm struck by how this book uses denotational semantic techniques to explain things (as opposed to teaching the semantic techniques as an end in themselves), the balance between theory and practice was a bit too much on the theory side for 541.
In the Spring semester 1997 we went back to something more like the 1994 and 1995 offerings of the course. Although we used Haskell instead of ML, as in 1994-95 we centered the course around semantics of object-oriented programming languages. We used the generic-function language BeCecil, which is described in ISU CS TR#96-17a, as a jumping off point for several projects. The treatment was much less theoretical than in 1996, did more programming, a bit of language design, and some prototyping of BeCecil's type system. Finally, we continued previously successful aspects of the course, such as group work for mini-projects, and exercises to help students learn to read and evaluate relevant research literature.
Computer Science 541 studies modern programming languages, with an emphasis on design and semantics. This document specifies the course's general and specific objectives.
The study of programming languages is primarily concerned with the following questions:
The catalog description of the course is as follows:
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, object-oriented, declarative, concurrent and other programming paradigms. (3 credits).
Com S 541 is distinguished from Com S 342 (Principles of Programming Languages) is that Com S 342 concentrates on essential semantic concepts, studied with the use of interpreters (coded in a functional style). Com S 342 avoids mathematical formalisms, while in Com S 541, we will not shy away from them. In this version of Com S 541, we concentrate on semantic ideas; that is, the key concepts needed to use, design, and specify a programming language. In Com S 541 we aim to study modern logic and functional and object-oriented languages, and assume that the graduate students are capable of dealing with the realistic versions of such languages. In Com S 541, we use mathematical tools to draw design lessons from our study of semantics, as opposed to simply understanding the features of modern languages.
Com S 541 is distinguished from Com S 641 (Semantics of Programming Languages) in that Com S 641 discusses particular formal semantic description techniques in depth, whereas a broader and less mathematically deep use of semantic description techniques is made in Com S 541; furthermore, an attempt is made in Com S 541 to show how to use the concepts behind these techniques, not so much their details, in language design.
Com S 541, ``Programming Languages 1,'' is usually taken by first year graduate students (if they have sufficient background). The class has a ``lecture'' that meets 2 times a week, for 75 minutes a time. It also has a discussion section that meets once a week (for 50 minutes) with a teaching assistant. There are usually 29 or 30 lecture meetings in a semester. The course carries 3 credit hours.
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.
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.
The following are the objectives for Fall 1997.
The general objectives for Com S 541 are divided into two parts: a set of essential of objectives and a set of enrichment objectives. The essential objectives were negotiated with the students in the class (thanks!).
In all cases, we allow the use of reference material to complete the tasks implied by the objectives.
In general terms the essential objectives for Com S 541 are that you be able to:
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 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 specify 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 concepts behind programming languages, their 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.
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. Already the use of functional languages is increasing, and the large telephone company Ericsson uses the functional language Erlang to write all of its software. 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 labelled 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.
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 endlessly. Listed here are general statements of those that I tend to teach or that you may wish to investigate. The justification for each objective is included in this list.
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.
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.
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.
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.
I've made the following three texts available as recommendations. Details will be decided as the course goes on.
We will also pass out some readings. Other related books are on reserve at the Parks Library.
The syllabus below was developed in negotiation with the stuents in the class. The ``when'' is specified by class meeting numbers (a count of the ``lectures,'' which are 75 minutes each). The readings from ``Discovering Smalltalk'' by Wilf LaLonde (Benjamin-Cummings, 1994) are marked ``DS''. The readings from ``Design Patterns'' by Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides (Addison-Wesley, 1995) are marked ``DP''. The readings from ``Haskell The Craft of Functional Programming'' by Simon Thompson (Addison Wesley, 1996) are marked ``H''.
Essential
Meetings Topic Readings Other Readings
-----------------------------------------------------------------------
1,4 Introduction, Survey, Goals handouts (see reserve list)
2-3,5-12 OO and Smalltalk DS2-3,5,6-7,9 DS1,4,8 DP1-2
handouts (other reserve books)
13-15 Java case study Gosling et al
20 test on OO languages
16-19,21-27 Functional and Haskell H1-2,4,6-10, H3,5,11-12,15
H13-14 (other reserve books)
28-29 Logic and Lambda Prolog handouts Miller & other reserve
30 Course Summary & Evaluation
---------------------------------------------------------------------------