Three approaches
It is the purpose of this text to explain the concepts underlying programming languages and to examine the major language paradigms that use these concepts.
Programming languages can be understood in terms of a relatively small number of concepts. In particular, a programming language is syntactic realization of one or more computational models. The relationship between the syntax and the computational model is provided by a semantic description. Semantics provide meaning to programs. The computational model provides much of the intuition behind the construction of programs. When a programming language is faithful to the computational model, programs can be more easily written and understood.
The fundamental concepts are supported bindings, abstraction and generalization. Concepts so fundamental that they are included in virtually every programming language. These concepts support the human facility for simile and metaphor which are so necessary in problem solving and in managing complexity.
Programming languages are also shaped by pragmatic considerations. Formost among these considerations are safety, efficiency and applicability. In some languages these external forces have played a more important role in shaping the language than the computational model to the point of distorting the language and actually limiting the applicability of the language. There are several distinct computational models --- imperative, functional, and logic. While these models are equivalent (all computable functions may be defined in each model), there are pragmatic reasons for prefering one model over the another.
This text is designed to formalize and consolidate the knowledge of programming languages gained in the introductory courses a computer science curriculum and to provide a base for further studies in the semantics and translation of programming languages. It aims at covering the subject area PL: Programming Languages as described in the ``ACM/IEEE Computing Curricula 1991.''
Computer science is not a spectator sport. To gain maximum benefit from the text, the reader should construct programs in each of the paradigms, write semantic specifications; and implement a small programming language.
The first part of the text consists of chapters 1-3.
Chapter 1 is an overview of the text.
It introduces the themes of the text: models of computation, syntax, semantics,
abstraction, generalization and pragmatics.
It is a philosopy for the design and implementation of programming languages and a context for understanding programming languages.
Chapter 2 focuses on systax for the structural description of programming languages. It is an introductory treatment of context-free grammars, push-down automata, regular expressions,
and finite state machines.
Context-free grammars are utilized throughout the text and
the material is a prerequisite for Chapter ??
Chapter 3 introduces semantics: algebraic, axiomatic, denotational and operational. While the chapter is optional,
I introduce algebraic semantics in conjunction with abstract types and axiomatic semantics with imperative programming.
Chapter 4 is a formal treatment of abstraction and generalization as used in programming languages.
Chapter 5 deals with values, types, type constructors and type systems.
Chapter 6 deals with environments, block structure and scope rules.
Chapter 7 deals with the functional model of computation. It introduces the lambda calculus and examines Scheme and Haskell.
Chapter 8 deals with the logic model of computation. It introduces Horn clause logic, resolution and unification and examines Prolog.
Chapter 9 deals with the imperative model of computation. Features of several imperative programming languages are examined. Various parameter passing mechanisms should be discussed in conjunction with this chapter.
Chapter 10 deals with the concurrent model of programming. Its primary emphasis is from the imperative point of view.
Chapter 11 is a further elaboration of the concepts of abstraction and generalization in the module concept. It is preparatory for Chapter 12.
Chapter 12 deals with the object-oriented model of programming. Its primary emphasis is from the imperative point of view. Features of Smalltalk, C++ and Modula-3 provide examples.
Chapter 13 deals with pragmatic issues and implementation details. It may be read in conjunction with earlier chapters.
Chapter ?? deals with parsing, compiling and attribute grammars.
Chapter 14 deals with programming environments,
Chapter 15 deals with the evaluation of programming languages and a review of programming language design principles.
Chapter 16 contains a short history of programming languages.
The instructor's manual contains lecture outlines and illustrations from the text which may be transferred to transparencies. There is also a laboratory manual which provides short introductions to Lex, Yacc, Prolog, Haskell, Modula-3, and SR.
The text has been used as a semester course with a weekly two hour lab. Its approach reflects the core area of programming languages as described in the report {\bf Computing as a Discipline} in CACM January 1989 Volume 32 Number 1.
| Knowledge Unit | Chapter(s) |
|---|---|
| PL1: History | 6,7,8,9,11 |
| PL2: Virtual Machines | 2,6,7,8,13 |
| PL3: Data Types | 5,13 |
| PL4: Sequence Control | 9,10 |
| PL5: Data Control | 5,11,12 |
| PL6: Run-time | 2,13 |
| PL7: Regular Expressions | 2 |
| PL8: Context-free grammars | 2 |
| PL9: Translation | 2 |
| PL10: Semantics | 3 |
| PL11: Programming Paradigms | 1,7,8,9,10,12 |
| PL12: Parallel Constructs | 10 |
| SE3: Specifications | 3 |