Implementation methods and the evolution of languages
Compilation, pure interpretation and hybrid implementation; compiler phases, linker and preprocessor, JIT; programming environments and the milestones in the evolution of languages from Fortran to Java that are asked on exams.
Writing a language is one thing; running it on a computer is another. This page covers two topics: how languages are implemented (compilation, interpretation, hybrid) and the milestones from the evolution of languages that are asked on exams. On the midterm it appears as short-answer and matching questions; points won with little effort.
Golden rules:
- Compilation: slow translation, fast execution. Interpretation: no translation, slow execution.
- Hybrid = compile to an intermediate language + interpret. JIT speeds this up.
- The preprocessor does textual replacement; it does not compute.
- Know the “firsts” in history: Fortran the first compiled language, ALGOL 60 the first BNF, SIMULA 67 the first class, LISP the first functional.
Implementation methods
A computer’s hardware runs only machine language. A high-level language can be run in three ways.
Compilation
The source program is translated to machine language once, then runs directly. Translation is slow, execution is fast. C, C++, COBOL, Ada.
source program
│ lexical analyzer characters → lexical units (lexemes)
▼
lexical units
│ syntax analyzer → parse trees
▼
parse trees
│ intermediate code generator and semantic analyzer
▼
intermediate code ──(optimization, optional)
│ code generator
▼
machine language ── linker (+ library and system code) ──► load module ──► runs
symbol table: provides all phases with the types and attributes of user-defined names- Lexical analyzer: gathers characters into units such as identifiers, special words, operators and punctuation; skips comments.
- Syntax analyzer: builds a parse tree from these units.
- Semantic analyzer: checks errors that syntax cannot catch, such as type errors; produces intermediate code.
- Optimization: makes the program smaller or faster (usually on the intermediate code).
- Code generator: produces the machine code.
- Linker: connects the user program with system and library programs; the output is a load module (executable image).
While a program runs, instructions move from memory to the processor; this connection is usually slower than the processor and limits the speed (the von Neumann bottleneck).
Pure interpretation
No translation. An interpreter program reads and runs the source program statement by statement; like a virtual machine simulated in software.
- Pro: an error message points directly to the source line and variable; easy debugging.
- Con: 10 to 100 times slower. The bottleneck is that every statement is decoded again each time it runs. Also, the source program and the symbol table stay in memory while running.
- Examples: early JavaScript and PHP, early versions of LISP, APL. It came back with web scripting languages.
Hybrid implementation
The source program is compiled to an intermediate language that is easy to interpret; the intermediate language is interpreted. Faster than pure interpretation, because source statements are decoded only once.
- Perl: first partially compiled to catch errors.
- Java: source → bytecode → interpreted by the JVM (Java Virtual Machine). Bytecode is portable: it runs on any machine that has a JVM.
Just-in-time
A JIT compiler translates a subprogram’s intermediate code to machine code when it is called for the first time and saves it; later calls use the machine code. Java and .NET languages (C#) work this way. The result: portable intermediate code + the speed of compiled code.
| Method | Translation | Execution speed | Example |
|---|---|---|---|
| Compilation | Once, slow | Fastest | C, C++, COBOL |
| Pure interpretation | None | 10-100x slower | Early JavaScript, PHP |
| Hybrid | To an intermediate language | In between | Perl, early Java |
| JIT | Intermediate language + to machine code at run time | Close to compiled | Java, C# |
Preprocessor
A program that processes the program just before compilation. It includes other files (#include) and expands macros (#define). Replacement is textual; the expression is not evaluated, and precedence rules apply after the expansion.
#define SQ(x) x*x
#define SQP(x) ((x)*(x))
#define DOUBLE(x) x+x
SQ(2+3) /* 2+3*2+3 */
SQP(2+3) /* ((2+3)*(2+3)) */
10 * DOUBLE(3) /* 10 * 3+3 */11
25
33PITFALL · a macro is not a function.
SQ(2+3)gives 11, not 25, because the argument is pasted as text without being evaluated. Put the parameters and the whole body in parentheses.
Programming environments
The collection of tools used in software development: file system, editor, linker, compiler, debugger. UNIX is an old environment; Eclipse, NetBeans, Microsoft Visual Studio .NET are integrated (IDE) examples.
Evolution of languages: what is asked on exams
| Year | Language | Why it matters |
|---|---|---|
| 1945 | Plankalkül (Zuse) | First high-level language design; not implemented |
| 1957 | Fortran I (Backus, IBM) | First widely used compiled high-level language; showed compiled code could be efficient |
| 1958 | LISP (McCarthy) | First functional language; list processing, garbage collection; artificial intelligence |
| 1958-60 | ALGOL 58 / ALGOL 60 | Machine independent; the first language described with BNF; block structure, recursion, pass-by-value and pass-by-name |
| 1960 | COBOL | Business applications; records, decimal arithmetic, readable English-like syntax |
| 1964 | BASIC | Time-shared, easy to learn |
| 1964 | PL/I | Scientific + business; first attempts at exception handling and concurrency; very complex |
| 1967 | SIMULA 67 | Classes and objects; the basis of data abstraction |
| 1971 | Pascal (Wirth) | For teaching; structured programming |
| 1972 | C | Systems programming (UNIX); powerful operators, weak type checking |
| 1972 | Prolog | Logic programming |
| 1980 | Smalltalk-80 | First fully OOP: everything is an object, message passing; graphical interface |
| 1983 | Ada | U.S. Department of Defense; packages, exception handling, generics, tasks |
| 1985 | C++ | C + classes, multiple inheritance, operator overloading, templates |
| 1995 | Java | Based on C++, simpler and safer: no pointers, garbage collection, applets, bytecode |
| 2000 | C# | .NET; ideas from Java and C++, delegates, properties |
Scripting languages: Perl (1987, text processing), JavaScript (1995, browser), PHP (1995, server), Python (1991), Ruby (1996, everything is an object). Functional: Scheme (1975, a small dialect of LISP), ML (static typing, type inference), Haskell (pure and lazy).
TIP · the “first” questions. First compiled: Fortran. First BNF: ALGOL 60. First class: SIMULA 67. First fully OOP: Smalltalk. First functional and garbage collection: LISP. Logic: Prolog. Business: COBOL. These seven pairings bring most of the points in this section.
Common mistakes
| Wrong | Correct |
|---|---|
| Interpretation is slow because machine instructions are slow | Every statement is decoded each time |
| Java is purely interpreted | Bytecode + JVM (hybrid), today with JIT |
| JIT compiles the whole program at the start | It compiles a subprogram on its first call and saves it |
| Optimization is a mandatory phase | It is optional |
| The linker compiles source code | It connects compiled pieces with libraries |
SQ(2+3) = 25 | With the x*x macro it is 11 |
| The first BNF was in Fortran | ALGOL 60 (BNF was used for ALGOL 58) |
| The first OOP language is Smalltalk | Classes are in SIMULA 67; the first fully OOP is Smalltalk |
Test yourself
Exam-style questions. Solve them on paper first, then reveal the answer.
Put the phases of a compiler in order: code generation, syntax analysis, lexical analysis, semantic analysis / intermediate code generation, optimization (optional).
Show answer
The lexer gathers characters into lexemes. The parser builds a parse tree from them. The semantic analyzer checks type errors and produces intermediate code. The optional optimization makes the program smaller or faster. The code generator produces the machine code. The symbol table serves all the phases.
Which compiler phase turns the characters of the source program into lexical units, and which builds parse trees?
Show answer
Lexical units: identifiers, special words, operators, punctuation. The lexer skips comments and whitespace. The syntax analyzer (parser) builds, from the lexical units, parse trees that show the syntactic structure of the program.
Why is pure interpretation typically 10 to 100 times slower than running compiled code?
Show answer
The interpreter has to re-decode a source statement every time it runs it; in a loop the same line is decoded thousands of times. The bottleneck is decoding the statement, not the machine instructions themselves. Also, the source program and the symbol table stay in memory while running. The upside: error messages point to the source line, and debugging is easy.
Classify the implementation method: (a) C and COBOL; (b) early JavaScript and PHP; (c) Perl and early Java.
Show answer
Compilation: the source is translated to machine language once, and execution is fast. Pure interpretation: no translation, the interpreter runs the source directly. Hybrid: the source is translated to an intermediate language that is easy to interpret (Java bytecode), and then this intermediate language is interpreted (the JVM).
What does a just-in-time (JIT) compiler do?
Show answer
JIT removes the slowness of the hybrid system: the program is compiled to the intermediate language; when a subprogram is called for the first time, its intermediate code is translated to machine code and saved, and later calls run the machine code directly. Java and .NET languages work this way. So JIT is really a delayed compiler.
With the C macro #define SQ(x) x*x, what is the value of SQ(2+3)? How should the macro be written?
Show answer
The preprocessor does textual replacement before compilation; it does not evaluate the expression. SQ(2+3) → 2+3*2+3; multiplication first: 2 + 6 + 3 = 11. With the parenthesized definition it becomes ((2+3)*(2+3)) = 25.
With #define DOUBLE(x) x+x, what is the value of 10 * DOUBLE(3)?
Show answer
Expansion: 10 * 3+3. Multiplication first: 30 + 3 = 33 (not the expected 60). The whole body of the macro must also be in parentheses: #define DOUBLE(x) ((x)+(x)).
What does a linker do?
Show answer
A user program usually needs other programs (operating system routines, library functions). The linker connects them and produces a single executable file (load module). That is why the binding of a library call to the function's code happens at link time.
Name the language: (a) the first widely used compiled high-level language (1957); (b) the first language described with BNF; (c) the language that introduced classes (1967); (d) designed for business data processing.
Show answer
Fortran (John Backus, IBM 704) proved that compiled code could be fast. ALGOL 60 was described with BNF and brought block structure, recursion, pass-by-value/name. SIMULA 67 brought classes and objects for simulation. COBOL (1960) brought records and decimal numbers for business applications.
Which language introduced list processing and garbage collection, and which was the first purely object-oriented language?
Show answer
LISP (1958, John McCarthy) was designed for artificial intelligence: the only data structure is the list, computation is function application, and unused memory is collected automatically. Smalltalk (Xerox PARC, Smalltalk-80) was the first fully OOP language, where everything is an object and computation is done by sending messages; it also introduced the graphical windowing interface.
Order these chronologically: Java, Prolog, Fortran I, SIMULA 67, Smalltalk-80.
Show answer
Fortran I 1957, SIMULA 67 1967, Prolog 1972, Smalltalk-80 1980, Java 1995. The exam asks for the order and "which idea first appeared where?", not memorized years.
Which language was designed for the U.S. Department of Defense and is known for packages, exception handling, generic units and tasks (concurrency)?
Show answer
Ada (1983) is the product of a very large design process: data abstraction with packages, detailed exception handling, generic program units, concurrency with tasks. Ada 95 added OOP support. Its complexity and compiler cost limited its spread.
Verification: The preprocessor macro questions were verified by expanding the macro body textually and evaluating the resulting expression with node (verify/SEN2001/01.mjs); the real cpp was not run because no C compiler is installed. The phase orders and years are conceptual/historical knowledge; they were compared with the textbook's standard account.