Introduction
to CSE 3341/5341
Corresponds to Chapter 1
of M. Scott's textbook
Outline
• A brief history of programming languages
• A brief overview of programming languages
• Why? and Objectives
• Questions addressed in this course
2
Programming in Machine Code
• Too labor-intensive and error-prone
• Euclid’s GCD algorithm in MIPS machine code
• Assembly language
– Mnemonics
– Translated by
an assembler
3
Evolution of Programming Languages
• Hardware
• Machine code
• Assembly language
• Macro assembly language
• FORTRAN, 1954: first machine-independent,
high-level programming language
– The IBM Mathematical FORmula TRANslating System
• LISP, 1958 (LISt Processing)
• ALGOL, 1958 (ALGOrithmic Language)
• Many hundreds of languages since then
4
Incomplete History
5
Why So Many Programming Languages?
• Evolution of language features and user needs
– Control flow: goto vs. if-then, switch-case, while-do
– Procedures (Fortran, C) vs. classes/objects (C++, Java)
– Weak types (C) vs. strong types (Java)
– Memory management: programmer (C, C++) vs.
language (Java through garbage collection)
– Error conditions: error codes (C) vs. exceptions and
exception handling (C++, Java)
6
Why So Many Programming Languages?
• Different application domains require different
specialized languages
– Scientific computing (Fortran, C, Matlab)
– Business applications (Cobol)
– Artificial intelligence (Lisp)
– Systems programming (C, C++)
– Enterprise computing (Java, C#)
– Web programming (PHP, JavaScript)
– String processing (AWK, Perl)
7
Outline
• A brief history of programming languages
• A brief overview of programming languages
• Why? and Objectives
• Questions addressed in this course
8
Programming Languages Spectrum
• Imperative languages
– What are the steps the computer should follow in order
to achieve the programmer’s goals?
– “Prescriptive” attitude
– Traditional (non-object-oriented) imperative; object-
oriented
• Declarative languages
– What are the properties of the desired?
– “Descriptive” attitude – higher level of abstraction
– Often, lower performance than imperative languages
– Functional; logic
• The lines are blurred – e.g., F#
9
Programming Languages Paradigms
• (Non-OO) Imperative (Fortran, C, Pascal)
– Underlying model: von Neumann machine
– Primary abstraction: procedure
• Object-oriented (Smalltalk, C++, Java, C#)
– Underlying model: object calculus
– Primary abstraction: class or object
• Functional (Lisp, Scheme, ML, Haskell)
– Underlying model: lambda calculus
– Primary abstraction: mathematical function
• Logic (Prolog)
– Underlying model: first-order logic
10
Im
pe
ra
tiv
e
D
ec
la
ra
tiv
e
Example: Euclid’s GCD Algorithm
11
int gcd(int a, int b) {
while (a != b) {
if (a > b) a = a – b;
else b = b – a;
}
return a;
} /* C procedure */
(define gcd (a b)
(cond ( (= a b) a )
( (> a b) (gcd (– a b) b) )
( else (gcd (– b a) a) )
)) ; Scheme function
C: First, compare a and b. If they
are equal, stop. Otherwise, …
assign to a … assign to b …
Scheme: same as a math definition
a if a=b
gcd(a,b) = gcd(b,a-b) if a>b
gcd(a,b-a)
otherwise
Implementation Methods
• Compilation (C, C++, ML)
• Interpretation (Lisp)
• Hybrid systems (Java)
12
The Entire Compiler Toolchain (1/2)
• Preprocessor: source to source translation
– E.g. GNU C/C++ macro preprocessor cpp
• Inlines #include, evaluates #ifdef, expands #define
• Produces valid C or C++ source code
• Compiler: source to assembly code
– E.g. GNU C/C++/… compuler gcc
– Produces assembly language for the target
processor
– Assembler: assembly to object code
• E.g. GNU assembler as
• Translates mnemonics (e.g. ADD) to opcodes; resolves
symbolic names for memory locations 13
The Entire Compiler Toolchain (2/2)
• Linker: object code from several modules
(including libraries) to single executable
– E.g. GNU linker ld
– Resolves inter-module symbol references; relocates
the code (recomputes addresses)
• Example: gcc from Unix command line is a driver
program that invokes the entire toolchain
– gcc –E test.c: preprocessor
– gcc –S test.c: preprocessor+compiler
– gcc –c test.c: preprocessor+compiler+assembler
– gcc test.c: preprocessor+compiler+assembler+linker 14
Overview of Compilation
15
Source Code for Euclid’s GCD Algorithm
16
Parse Tree
17
Parse Tree (Continued)
18
Abstract Syntax Tree and Symbol Table
19
Assembly
20
Interpreter Overview
21
Another way to implement a language:
Intermediate Languages for Portability
• Java: the translator produces Java bytecode
– Executed on the Java Virtual Machine (JVM)
– Inside the JVM, there is a bytecode interpreter and a
just-in-time (JIT) compiler (triggered for “hot” code)
– Android: Java bytecode → Dalvik bytecode, for
execution on the Dalvik Virtual Machine
• C can be used as an intermediate language: a C
compiler is available on pretty much any machine
22
Outline
• A brief history of programming languages
• A brief overview of programming languages
• Why? and Objectives
• Questions addressed in this course
23
Why Study Programming Languages?
• Choose the right language for the job
– They all have strengths and weaknesses
• Learn new languages faster
– This is a course on common principles of PL
• Understand your tools better
– Compilers, interpreters, virtual machines, debuggers,
assemblers, linkers
• Write your own languages
– Happens more often than you’d think!
• To fix bugs & make programs fast, often you need to
understand what’s happening “under the hood”
24
Objectives
• 3341: Principles of Programming Languages
• Master important concepts for PLs
• Master several different language paradigms
– Imperative, object-oriented, functional
• Master some implementation issues
– You will have some idea how to implement
compilers and interpreters for PLs
• Other related courses
– 6341: Foundations of Programming Languages
– 5343: Compiler Design and Implementation
25
Outline
• A brief history of programming languages
• A brief overview of programming languages
• Why? and Objectives
• Questions addressed in this course
26
Questions Addressed in This Course
How do language implementations understand and
transform program code? How do they get machine
code or else interpret the program code?
27
Questions Addressed in This Course
How do compilers generate code for object-
oriented and non-OO method calls?
Does Java avoid most memory errors? Why? How?
28
Questions Addressed in This Course
Why does a Java program
• run out of memory with 1 GB heap,
• run slow with 2 GB heap,
• run fast with 3-7 GB heap,
• and run slow with ≥8 GB heap?
How does GC work?
29
Questions Addressed in This Course
A language that doesn't support writing/storing to
variables?!
30
Questions Addressed in This Course
What can this program do?
31
Thread 1:
data = 42;
flag = true;
Thread 2:
if (flag) {
print(data);
}
Initially:
int data = 0;
boolean flag = false;