Introduction
Chapter 1
Programming languages – ubiquitous
2
Computer evolution
§ENIAC
§ 18,000 sq feet
§ 25 tones = 25,000 Kg § 5,000 instr/s
§iPhone 6
§ 4.55 ounces = 0.13 Kg § 25,000,000,000 instr/s
§ 20,000 x smaller, 5,000,000 x faster = 100,000,000,000 x more efficient
3
Introduction
Why are there so many languages?
§ Evolution
§ Special purposes
§ Personal preference
§ Features
§ Availability
§ Standardization
§ Open source
§ Good compilers
§ Socio-economic factors
4
object-oriented programming scripted programming
structured programming
Introduction
5
Evolution
§Machine language
5589e553 83ec0483 e4f0e831 00000089 c3e82a00 000039c3 74108db6 00000000 39c37e13 29c339c3 75f6891c 24e86e00 00008b5d fcc9c329 d8ebeb90
§Assembly
pushl %ebp
movl %esp, %ebp
pushl %ebx
subl $4, %esp
andl $−16, %esp
call getint
jle D
§ Fortran FUNCTION GCD(A, B)
movl
call
cmpl
je
A: cmpl
%eax, %ebx
getint
%eax, %ebx
C
%eax, %ebx
movl
leave
ret
D: subl jmp
−4(%ebp), %ebx
%ebx, %eax B
subl B: cmpl
jne C: movl
%eax, %ebx
%eax, %ebx
A
%ebx, (%esp)
1
IA = A
IB = B
IF (IB.NE.0) THEN
ITEMP = IA
IA = IB
IB = MOD(ITEMP, IB) GOTO 1
END IF
GCD = IA
RETURN END
call putint
6
Evolution
§ C++
int gcd(int a, int b) { while (a != b) {
if (a > b) a = a – b;
else b = b – a; }
return a; }
§ Python
def gcd(x, y): while (y):
x, y = y, x % y return x
def gcd2(a,b):
return a if (b==0) else gcd2(b, a%b)
int gcd2(int a, int b) {
return (b==0) ? a : gcd2(b, a%b);
}
7
Evolution
§ Scheme
(define gcd (lambda (a b)
(cond ((zero? b) a)
(else (gcd b (modulo a b))))))
§ Prolog
gcd(X,Y,G) :- X=Y, G=X.
gcd(X,Y,G) :- X
8
Introduction
What are programming languages for? § way of thinking – expressing algorithms
§ abstraction of virtual machine – way of specifying what you want the hardware to do without getting down into the bits
§ implementor’s point of view vs. programmer’s point of view §speed vs. expressivepower
“Programming is the art of telling another human being what one wants the computer to do.”
Donald Knuth
9
Introduction
What makes a language successful? § easy to learn:
§ BASIC, Pascal, LOGO, Scheme
§ easy to express things, easy to use once fluent, powerful:
§ C, Common Lisp, APL, Algol-68, Perl, Scheme § easy to implement
§ BASIC, Forth
§ possible to compile to very good (fast/small) code
§ Fortran, C
§ backing of a powerful sponsor
§ COBOL, PL/1, Ada, Visual Basic
§ wide dissemination at minimal cost § Pascal, Turing, Java
10
Why study programming languages?
§ Help you choose a language:
§ systems programming: C, C++, C#
§ numerical computations: Fortran, C, Matlab
§ web-based applications: PHP, Ruby
§ embedded systems: Ada, C
§ symbolic data manipulation: Scheme, ML, Common Lisp § networked PC programs: Java, .NET
§ logical relationships: Prolog
§ Make it easier to learn new languages:
§ many concepts are common to many languages: syntax, semantics,
iteration, recursion, abstraction, etc.
§ Make better use of the language you are using:
§ understand various features
§ understand implementation cost
§ find ways to do things that are not explicitly supported
11
Programming languages spectrum
§imperative – how the computer should do it?
§ von Neumann
§ object-oriented
§ scripting languages
– C, Fortran, Pascal, Basic
– C++, Smalltalk, Eiffel
– Python, Perl, JavaScript, PHP
§declarative – what the computer is to do? § functional – Scheme, ML, Lisp, FP
§ logic – Prolog, VisiCalc, RPG §imperative languages predominate
§ better performance
§declarative languages are higher level
§ farther from implementation details
§ safer; imperative languages started importing features
12
Compilation vs. Interpretation
§Compilation vs. interpretation § not opposites
§ not a clear-cut distinction
§Pure Compilation
§ The compiler translates the high-level source program into an equivalent target program (typically in machine language), and then goes away:
13
Compilation vs. Interpretation
§Pure Interpretation
§ Interpreter stays around for the execution of the program § Interpreter is the locus of control during execution
14
Compilation vs. Interpretation
§Interpretation:
§ Greater flexibility
§ Example: Lisp, Prolog programs can write new pieces and execute them on the fly
§ Better diagnostics – error messages § Source-level debugger
§Compilation
§ Better performance
§ Early decisions can save time
§ Example: a variable’s address can be fixed at compile time
15
Compilation vs. Interpretation
§Common: compilation, then interpretation
§ Distinction not very clear; compiled if:
§ Translator analyzes the program thoroughly
§ Intermediate program very different from source
§ Python – interpreted: dynamic semantic error checking § C, Fortran – compiled: static semantic error checking
16
Compilation vs. Interpretation
§Compilation
§ Compilation is translation from one language into
another, with full analysis of the meaning of the input
§ Compilation entails semantic understanding of what is being processed; pre-processing does not
§ A pre-processor will often let errors through. A compiler hides further steps; a pre-processor does not
17
Compilation vs. Interpretation
§Many compiled languages have interpreted pieces: § Fortran: format
§ C: printf
§Most use “virtual instructions”: § set operations in Pascal
§ string manipulation in Basic
§Some compilers produce only virtual instructions: § Pascal P-code
§ Java byte code
18
Implementation strategies
§Preprocessor
§ Used by many interpreted languages
§ Removes comments and white space
§ Groups characters into tokens (keywords, identifiers,
numbers, symbols)
§ Expands abbreviations in the style of a macro assembler
§ Identifies higher-level syntactic structures (loops, subroutines)
19
Implementation strategies
§Library of Routines and Linking
§ Compiler uses a linker program to merge the appropriate library of subroutines (e.g., math functions such as sin, cos, log, etc.) into the final program:
20
Implementation strategies
§Post-compilation Assembly
§ Facilitates debugging (assembly is easier for people to
read)
§ Isolates the compiler from changes in the format of machine language files (only assembler must be changed, is shared by many compilers)
21
Implementation strategies
§The C Preprocessor (conditional compilation)
§ Preprocessor deletes comments and expands macros
§ Preprocessor deletes portions of code, which allows several versions of a program be built from same source
§ Example: #ifdef directive
22
Implementation strategies
§Source-to-Source Translation (C++)
§ C++ implementations based on the early AT&T compiler generated an intermediate program in C, instead of assembly language:
23
Implementation strategies
§ Many compilers are self-hosting: written in the same language: C compiler is written in C
§ Who compiles the compiler?
§ Example: Pascal distribution contained
§ Pascal compiler, written in Pascal, that generates P-code
§ The same compiler, translated into P-code § P-code interpreter, written in Pascal
§ To get Pascal running:
§ translate the P-code interpreter (by hand) in machine language
§ by running the P-code version of the compiler on top of the P-code interpreter, one could compile any Pascal program into P-code, which can be run by the interpreter
§ Bootstrapping: faster implementation
§ modify the Pascal version of compiler to machine language (instead of P-code) § run it through itself to produce machine-code version of the compiler
24
Implementation strategies
§Compilation of Interpreted Languages
§ Lisp, Prolog, Smalltalk
§ The compiler generates code that makes assumptions about decisions that won’t be finalized until runtime.
§ If these assumptions are valid, the code runs very fast.
§ If not, a dynamic check will revert to the interpreter.
25
Implementation strategies
§Dynamic and Just-in-Time Compilation
§ Deliberately delay compilation until the last possible moment
§ Lisp, Prolog: invoke the compiler on the fly, to translate newly created source into machine language
§ Java: machine-independent intermediate form – bytecode
§ bytecode is the standard format for distribution of Java programs
§ C# compiler produces Common Intermediate Language (CIL), which is translated into machine code immediately prior to execution.
26
Implementation strategies
§Unconventional compilers
§ text formatters may compile high-level document description into commands for a printer
§,
§ query language processors translate into primitive
operations on files § SQL
27
Programming Environment Tools
§Tools
§ Assemblers, debuggers, preprocessors, linkers (see above)
§ Editors – can have cross referencing
§ Version management – keep track of separately compiled
modules
§ Profilers – performance analysis
§ IDEs – help with everything
§ knowledge of syntax
§ maintain partially compiled internal representation § Eclipse, NetBeans, Visual Studio, XCode
28
An Overview of Compilation
§Phases of Compilation
29
An Overview of Interpretation
§Phases of Interpretation
30
An Overview of Compilation
§Scanning (Lexical Analysis)
§ divide program into “tokens”
§ smallest meaningful units
§ this saves time, since character-by-character processing is slow
§ scanning is recognition of a regular language § via a DFA (Deterministic Finite Automaton)
31
An Overview of Compilation
§Scanning: Example
§ C Program (computes GCD):
int main() {
int i = getint(), j = getint();
while (i != j) {
if (i > j) i = i – j;
else j = j – i; }
putint(i); }
§ Input – sequence of characters:
§ ‘i’, ‘n’, ‘t’, ‘ ’, ‘m’, ‘a’, ‘i’, ‘n’, ‘(’, ‘)’, …
§ Output – tokens:
§ int, main, (, ), {, int, i, =, getint, (, ), j, =, getint, (, ), ;, while, (, i, !=, j, ), {, if, (, i, >, j, ), i, =, i, -, j, ;, else, j, =, j, -, i, ;, }, putint, (, i, ), ;, }
32
An Overview of Compilation
§Parsing (Syntax Analysis)
§ discovers the “context free” structure of the program
§ parsing is recognition of a context-free language § via a Push-Down Automaton (PDA)
§ organize tokens into a parse tree
§ higher-level constructs in terms of their constituents
§ as defined by a context-free grammar
33
An Overview of Compilation
§Parsing: Example – while loop in C § Context-free grammar (part of):
iteration-statement → while ( expression ) statement statement → { block-item-list-opt } block-item-list-opt → block-item-list | ε block-item-list → block-item
block-item-list → block-item-list block-item
block-item → declaration block-item → statement
§ Parse tree for GCD program
§ based on full context-free grammar § see next slides
34
An Overview of Compilation
35
An Overview of Compilation
§Context-Free Grammar and Parsing (continued)
36
An Overview of Compilation
§Semantic Analysis
§ the discovery of meaning in the program
§ detects multiple occurrences of the same identifier § tracks the types of identifiers and expressions
§ verify consistent usage and guide code generation
§ builds and maintains a symbol table:
§ maps each identifier to its information: type, scope, structure, etc. § used to check many things
§ Examples in C:
§ identifiers declared before used
§ identifiers used in the appropriate context
§ correct number and type of arguments for subroutines § return correct type
§ switch arms have distinct constant labels
37
An Overview of Compilation
§Semantic Analysis
§ compiler does static semantic analysis
§ dynamic semantics – for what must be checked at run time § Dynamic checks – trade off: safety vs. speed
§ C has very few dynamic checks § Examples in other languages:
§ array indexes within bounds
§ variables initialized before used
§ pointers are dereferenced only when referring to valid object § arithmetic operations do not overflow
§ Run time checks fail – abort or throw exception
38
An Overview of Compilation
§Syntax Tree
§ Parse tree = concrete syntax tree
§ it shows how the tokens are derived from CFG
§ after that, much information in the parse tree is not relevant
§ Semantic analyzer: parse tree changed into syntax tree
§ syntax tree = abstract syntax tree
§ removes the “useless” internal nodes
§ annotates the remaining nodes with useful information
39
An Overview of Compilation
§Syntax Tree Example: GCD program Parse Tree
40
An Overview of Compilation
§Intermediate form
§ annotated syntax tree
§ done after semantic analysis if program passes all checks
§ chosen for machine independence, ease of optimization,
or compactness
§Code generation
§ produces assembly language
§ Example for GCD program – next slide § naïve code
§ good code is difficult to produce
41
An Overview of Compilation
42
An Overview of Compilation
§Optimization (code improvement)
§ takes an intermediate-code program and produces another
one that does the same thing faster, or in less space § The code on the previous slide becomes:
pushl %ebp
movl %esp, %ebp
pushl %ebx
subl $4, %esp
andl $−16, %esp
call getint
movl %eax, %ebx
call getint
cmpl %eax, %ebx
je C
jle D
subl %eax, %ebx
B: cmpl %eax, %ebx
jne A
C: movl %ebx, (%esp)
call putint
movl −4(%ebp), %ebx
leave
ret
D: subl %ebx, %eax
jmp B
A: cmpl
%eax, %ebx
43