Language Design and Language Implementation
Copyright (c) 2000, Morgan Kaufmann Publishers
Throughout this text we have had occasion to remark on the many connections
between language design and language implementation. This appendix lists
many such connections, with pointers to sections of the text in which they
are discussed.
Language features that most designers now believe were mistakes,
at least in part because of implementation difficulties:
- by-name parameters in Algol 60:
Section 8.3.1 (Call By Name)
- dangling
else in Pascal:
Sections 2.2.5 (Writing an LL(1) Grammar), 2.4, and 6.4;
Exercise 2.22
- dot-dot token of Pascal:
Section 2.2.1
- labels as parameters:
Secton 8.3.1 (Label Parameters)
- lexical complexity in Fortran:
Sections 2.2.1 and 2.4
- non-local
gotos:
Sections 6.2 and 8.5.4
-
ON conditions in PL/I:
Section 8.5
- real bounds on
do loops in Fortran 77:
Section 6.5.1
- separate compilation mechanisms in (early) C:
Section 3.6.2
Potentially useful features omitted from some languages because of
concern that they might be too difficult or slow to implement:
- array slice operations:
Section 7.4.1 (Slices and Array Operations)
- closures, first-class subroutines, and unlimited extent:
Sections 3.4.1, 3.4.2, 7.7.3, 8.2, 8.2.2, 8.3.1 (Closures as
Parameters), 8.3.3, 8.5.4, 8.6, 10.4.4, and 12.3.3 (Fork/Join);
Exercise 8.6
- comparing records with holes for equality:
Section 7.3.2
- conditional critical regions:
Section 12.3.3 (Conditional Critical Regions)
- continuations:
Sections 6.2, 6.8, and 8.5.4
- coroutines:
Section 8.6
- dynamic arrays and variable-length strings:
Sections 7.4.2 and 7.5
- early reply:
Section 12.2.3 (Early Reply)
- exception handling:
Sections 8.5 and 8.5.4
- garbage collection:
Sections 7.7, 7.7.3, 7.11, 10.3.4, 10.6, and 11.2; Exercise 7.24
- higher-order functions:
Section 11.2.3
- iterators:
Sections 6.5.3, 8.6.3, and 6.8
- lazy evaluation:
Sections 6.6.2 and 11.2.2
- multiple inheritance:
Section 10.5
- non-determinacy (with fairness):
Sections 6.7, 6.8, and 12.4.3
- recursion in Fortran:
Section 3.2
- side-effect freedom:
Sections 6.1.2, 6.3, 6.6, 6.8, 11.2.2, and 12.3.4
- type checked separate compilation:
Section 9.6.2
- type inference by unification:
Section 7.2.5
- type-checked I/O:
Section 7.9.3
- homoiconography:
Sections 7.8, 11.2.1 (Programs as Lists), and 11.3.1 (Database
Manipulation)
Language limitations adopted at least in part out of concern for
implementation complexity or cost:
- column-major order for arrays in Fortran:
Section 7.4.3
- dynamic scope (to allow the use of an A-list):
Sections 3.3.2 and 3.3.4
- fixed size for opaque exports in Modula-2:
Section 10.2.1
-
in reverse, downto, and constant step for
Sections 6.5.1 (Empty Bounds) and 6.8
- lack of nested threads (to avoid cactus stacks):
Sections 8.6.1 and 12.2.3 (Early Reply)
- lack of ranges in
case statement labels:
Sections 6.4.2 and 6.8
- limit on nesting level of subroutines (for displays):
Section 8.1
- limited character sets:
Sections 7.4.1 and 7.4.1 (Slices and Array Operations)
- limited length of identifiers:
Section 2.1.1
- limited length of lines:
Section 2.1.1
- limits on the size and member types of sets:
Section 7.6
- mix-in inheritance (as in Java):
Section 10.5.4
- non-virtual member functions in C:
Section 10.4.1
- prohibition against forward references:
Sections 3.3.3 and 3.6.1
- restricted bodies for
co..oc statements in SR:
Sections 12.2.3 (Co-Begin) and 12.2.3 (Early Reply)
Language features introduced at least in part to facilitate efficient
or elegant implementations:
-
access all and aliased types in Ada 95:
Sections 7.7 and 7.7.2; Exercises 7.22 and 7.23
- Ada parameter modes (to cover rendezvous):
Sections 8.3.1 (Parameter Modes in Ada) and 12.4.4 (Semantics)
-
case statements:
Section 6.4.2
- decimal arithmetic:
Section 7.1.2
- explicit deletion of dynamic objects in Pascal, C, etc.:
Section 7.7 (see also garbage collection above)
- imperative features in functional languages:
Sections 6.3, 7.7.1 (Value Model), and 11.2.1 (Control Flow and
Assignment)
-
inline keyword for subroutines in C++:
Sections 6.6.2, 6.8, and 8.2.3
- local scope for
for loop index:
Sections 6.5.1 (Access to the Index Outside the Loop) and 6.8
- mixed integer sizes in C (and to some extent subranges in Pascal):
Sections 7.1.2 and 7.1.2 (Subrange Types)
- packed types:
Section 7.3.2
- parameter modes (two reasons, e.g., to pass by reference):
Section 8.3.1 (Variations on Value and Reference Parameters)
- pointer arithmetic in C:
Sections 5.6.2 (The Impact of Subroutine Calls), 6.1.2
(Combination Assignment Operators), and 7.7.1 (Pointers and
Arrays in C)
- private parts of a module specification:
Sections 3.3.1 (Modules) and 10.1; Exercise 3.8
- pseudoenumeration (
for) loop in C:
Section 6.5.2
- short-circuit Boolean evaluation:
Sections 6.1.4, 6.4.1, and 6.8
- variant parts at end of record; allocation of constrained
records in Pascal and Ada:
Sections 7.3.4 and 7.3.4 (Variants in Ada)
- the cut,
assert, fail, etc. in Prolog:
Sections 11.3.1 (Imperative Control Flow) and 11.3.1 (Database
Manipulation)
-
with statements:
Section 7.3.
Tradeoffs in which implementation plays a significant role:
- blocking semantics in monitors:
Section 12.3.3 (Monitors)
- coercions and conversions:
Sections 3.5 and 7.2.3
- compilation vs. interpretation:
Section 1.4
- cost of various semantic checks:
Sections 6.1.2 (Initialization), 6.1.3, 6.8, 7.2.4 (Subranges),
7.2.4 (Composite Types), 7.4.3 (Address Calculations), and
7.7.2; Exercises 1.9 and 4.2
- error reporting and buffering for no-wait send:
Section 12.4.2
- fragile base class problem in Java
(nice semantics despite the cost):
Section 10.4.3
- initialization vs. assignment in C++:
Section 6.1.2 (Initialization)
- late vs. early binding:
Section 3.1
- message screening (by content?):
Section 12.4.3
- normal and applicative order evaluation:
Sections 6.6.2 and 11.2.2
- overflow and arithmetic reordering:
Sections 6.1.3 and 6.8
- pointers to non-heap objects:
Section 7.7.2; Exercises 7.22 and 7.23
- pointers, aliases, and optimization:
Section 2.2.1 (Significant Comments), 3.3.1 (Modules), 7.3.3,
13.3, and 13.4.2
- reordering of record fields:
Section 7.3.2
- row-pointer vs. contiguous layout for arrays:
Section 7.4.3
- shared memory vs. message passing:
SEction 12.2.1
- small subroutines (and big register sets, inlining,
and interprocedural optimization):
Sections 5.6.2 (The Impact of Subroutine Calls), 8.2, 8.2.3,
10.4, and 10.7
- static and dynamic scope:
Sections 3.3.3, 3.3.4, 3.4, 7.1, and 8.1
- static vs. dynamic typing:
Section 7.1
- strict numeric semantics in Java:
Sections 6.1.3 and 6.8
- trivial update problem:
Section 11.2.5
- type inference:
Sections 7.2.4 and 7.2.5
- variables as values and references:
Sections 6.1.2 (What Is a Variable?), 7.7, 10.1, 10.3.2, and
10.3.3
- vtable implementation:
Section 10.10; Exercises 10.18 and 10.20
Cases in which ease/difficulty of implementation significantly
affected the success of a language:
- Ada (negatively):
Section 1.1
- Common Lisp (with respect to quality of environment):
Sections 1.1 and 1.5
- Forth:
Section 1.1
- Fortran (esp.~with respect to quality of compilers):
Section 1.1
- Java (web):
Sections 1.1 and 9.2
- Pascal (P-code):
Sections 1.1, 1.4, and 9.2
- Smalltalk (with respect to quality of environment):
Sections 1.5 and 10.6.1
Cases in which a machine architecture makes reasonable features
unreasonably expensive:
- recursion in Fortran on the IBM 704:
Section 3.2
- threads on a Sparc:
Section 5.6.2 (The Impact of Subroutine Calls)
- shared memory on a multicomputer or network:
Section 12.2.1
Miscellany:
- choosing to count with doubles:
Exercise 5.4
- etymology of
car and cdr in Lisp:
Section 7.8
- C porting bugs:
Exercise 7.4
Back to the book home page
