4.5 Influence of Language Goals on Implementation
The goals of a language (e.g., speed of execution, ease of development, safety) influence its design choices (e.g., static or dynamic bindings). Historically, both of these factors have had an influence on language implementation (e.g., interpretation or compilation). For instance, Fortran and C programs are intended to execute fast and, therefore, are compiled. The speed of the executable produced by a compiler is a direct result of the efficient decoding of machine instructions (vis-à-vis high-level statements) at run-time coupled with few semantic checks at run-time. Static bindings also support fast program execution. It is natural to implement a language designed to support static bindings through compilation because establishing those bindings and performing semantic checks for them can occur at compile time so they do not occupy CPU cycles at run-time—yielding a fast executable. A compiler for a language supporting static bindings need not generate code for performing semantic checks at run-time in the target executable.7
UNIX shell scripts, by contrast, are intended to be quick and easy to develop and debug; thus, they are interpreted. It is natural and easier to interpret programs in a language with dynamic bindings (e.g., identifiers that can be bound to values of any type at run-time), including Scheme, since the necessary semantic checks cannot be performed before run-time. Compiling programs written in languages with dynamic bindings requires generating code in the target executable for performing semantic checks at run-time. Interpreted languages can also involve static bindings. Scheme, for example, uses static scoping. If a language is implemented with an interpreter, the static bindings in a program written in that language do not present an opportunity to improve the run-time speed of the interpreted program as a compiler would. Therefore, the use of static bindings in an interpreted language must be justified by reasons other than improving runtime performance.
However, there is nothing intrinsic in a programming language (i.e., in its definition) that precludes it from being implemented through interpretation or compilation. For instance, we can build an interpreter for C, which is traditionally a compiled language. An interpretive approach to implementing C is contrary to the design goals of C (i.e., efficiency) and provides no reasonable benefit to justify the degradation in performance. Similarly, compilers for Scheme are available. The programming language Clojure is a dialect of Lisp that is completely dynamic, yet is compiled to Java bytecode and runs on the JVM. The time required for these run-time checks is tolerated because of flexibility that dynamic bindings lend to program development.8 Binding is the topic of Chapter 6.
In cases where an implementation provides both an interpreter and a compiler (to object code) for a language (e.g., Scheme), the interpreter can be used for (speedy and flexible) program development, while the compiler can be reserved for producing the final (fast-executing) production version of software.
Programming Exercises for Chapter 4
Table 4.2 presents the interpretation programming exercises in this chapter annotated with the prior exercises on which they build. Table 4.3 presents the features of the parsers used in each subpart of the programming exercises in this chapter.
Table 4.2 Interpretation Programming Exercises in This Chapter Annotated with the Prior Exercises on Which They Build (Key: PE = programming exercise.)
Table 4.3 Features of the Parsers Used in Each Subpart of the Programming Exercises in This Chapter (Key: R-D = recursive-descent; S-R = shift-reduce.)
Exercise 4.1 Reconsider the following context-free grammar defined in EBNF from Programming Exercise 3.5:
where <eχpr> and <integer> are non-terminals and +, *, –, and 1, 2, 3, ..., 231 – 1 are terminals.
(a) Extend your program from Programming Exercise 3.5.a to interpret programs. Normal precedence rules hold: – has the highest, * has the second highest, and + has the lowest. Assume left-to-right associativity. The following is sample input and output for the expression evaluator (> is simply the prompt for input and will be the empty string in your system):
Do not build a parse tree to solve this problem. Factor your program into a recursive-descent parser (i.e., solution to Programming Exercise 3.5.a) and an interpreter as shown in Figure 4.1.
(b) Extend your program from Programming Exercise 3.5.b to interpret expressions as shown in Programming Exercise 4.1.a. Do not build a parse tree to solve this problem. Factor your program into a shift-reduce parser (solution to Programming Exercise 3.5.b) and an interpreter as shown in Figure 4.1.
(c) Complete Programming Exercise 4.1.a, but this time build a parse tree and traverse it to evaluate the expression.
(d) Complete Programming Exercise 4.1.b, but this time build a parse tree and traverse it to evaluate the expression.
(e) Extend your program from Programming Exercise 3.5.d to interpret expressions as shown here:
(f) Extend your program from Programming Exercise 3.5.e to interpret expressions as shown in Programming Exercise 4.1.e.
(g) Extend your program from Programming Exercise 3.5.f to interpret expressions as shown in Programming Exercise 4.1.e.
(h) Extend your program from Programming Exercise 3.5.g to interpret expressions as shown in Programming Exercise 4.1.e.
(i) Complete Programming Exercise 4.1.e, but this time, rather than diagramming the expression, decorate each expression with parentheses to indicate the order of operator application and interpret expressions as shown here:
(j) Complete Programming Exercise 4.1.f with the same addendum noted in part i.
(k) Complete Programming Exercise 4.1.g with the same addendum noted in part i.
(l) Complete Programming Exercise 4.1.h with the same addendum noted in part i.
Exercise 4.2 Reconsider the following context-free grammar defined in BNF (not EBNF) from Programming Exercise 3.7:
where t, f, |, &, and ∼ are terminals that represent true, false, or, and, and not, respectively. Thus, sentences in the language defined by this grammar represent logical expressions that evaluate to true or false.
Complete Programming Exercise 4.1 (parts a–l) using this grammar, subject to all of the requirements given in that exercise. Specifically, build a parser and an interpreter to evaluate and determine the order in which operators of a logical expression are evaluated. Normal precedence rules hold: ∼ has the highest, & has the second highest, and | has the lowest. Assume left-to-right associativity.
The following is a sample interactive session with the pure interpreter:
The following is a sample interactive session with the diagramming interpreter:
The following is a sample interactive session with the decorating (i.e., parentheses-for-operator-precedence) interpreter:
Exercise 4.3 Reconsider the following context-free grammar defined in BNF (not EBNF) from Programming Exercise 3.8:
where t, f, |, &, and ∼ are terminals that represent true, false, or, and, and not, respectively, and all lowercase letters except for f and t are terminals, each representing a variable. Each variable in the variable list is bound to true in the expression. Any variable used in any expression not contained in the variable list is assumed to be false. Thus, programs in the language defined by this grammar represent logical expressions, which can contain variables, that can evaluate to true or false.
Complete Programming Exercise 4.1 (parts a–d and i–l) using this grammar, subject to all of the requirements given in that exercise.
Specifically, build a parser and an interpreter to evaluate and determine the order in which operators of a logical expression with variables are evaluated. Normal precedence rules hold: ∼ has the highest, & has the second highest, and | has the lowest. Assume left-to-right associativity.
The following is a sample interactive session with the pure interpreter:
The following is a sample interactive session with the parentheses-for-operator-precedence interpreter:
Notice that this language is context-sensitive because variables must be declared before they are used. For example, 
is syntactically, but not semantically, valid.
7. Similarly, time spent optimizing object code at compile time results in a faster executable. This is a worthwhile trade-off because compilation is a “compile once, run repeatedly” proposition—once a program is stable, compilation is no longer performed.
8. The speed of compilation decreases with the generation of code for run-time checks as well.