E2011: Theoretical fundamentals of computer science
Introduction to programming languages
Vlad Popovici, Ph.D.
Fac. of Science - RECETOX
Outline
1 Programming languages
Imperative languages
Functional languages
Logic predicate languages
Object-oriented languages
2 Executing programs
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag2 / 30
Physics: electrons
Transistors, diodes -
devices
Analog circuits:
amplifiers, filters
Logic: adders,
memory
Digital circuits: gates
Microarchitecture:
data paths,
controllers
Architecture:
instructions,
registers
Operating system:
device drivers,
kernels
Application software:
programs
Abstraction
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Basic concepts about operating systems3 / 16Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag3 / 30
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag4 / 30
0100010001
1101010001

0010010000
1001000101Assembly
language
Pseudocode
Algorithm
design
…… …
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag5 / 30
Programming languages
”How we communicate influences how we
think and vice versa.”
”Similarly, how we program computers
influences how we think about computation,
and vice versa.”
LibraryPirate
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag6 / 30
Programming languages
it is a formal computation specification means
it has a strict syntax specified by a grammar
clear semantics for each syntactic construct
various practical implementations:
▶ real vs virtual machine
▶ translation vs. compilation vs. interpretation
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag7 / 30
Levels of abstraction
algebraic notation and floating point numebers: FORTRAN
structured abstractions and machine independence Algol, Pascal
architecture independence (λ−calculus, Lisp)
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag8 / 30
Levels of data abstraction
basic: variables, data types, declarations
structured abstractions: data structures, arrays
unit abstractions: abstract data types (ADTs), classes, packages,
namespaces
information hiding, modularity, reusability, interoperability
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag9 / 30
Main programming paradigms
imperative/procedural (e.g., C, C++): variables, assignment, other
operators
functional (e.g., Lisp, Scheme, ML, Haskell): abstract notion of a
function, based on λ−calculus
logic (e.g., Prolog): symbolic logic (e.g., predicate calculus)
object–oriented (e.g., Java, Python, C++): encapsulation of data
and control together
generic (e.g., C++ and especially its standard library - STL): type
abstraction and enforcement mechanisms
several paradigms may be implemented in the same language
(multi-paradigm languages)
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag10 / 30
Imperative languages
variables and assignments
sequential execution
conditionals (if-then-else) and loops (for-do, while-do, and do-while)
are the building blocks
subroutines/functions/procedures for procedural abstraction
efficiency and low-level control
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag11 / 30
Imperative languages - sum of odd elements in C
#include <s t d i o . h>
i n t main () {
i n t v e c t o r [ ] = {1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9}; // some data
i n t s i z e = s i z e o f ( v e c t o r ) / s i z e o f ( v e c t o r [ 0 ] ) ;
i n t sum = 0;
for ( i n t i = 0; i < s i z e ; i++) {
i f ( v e c t o r [ i ] & 1) { // use bit −wise AND
sum += v e c t o r [ i ] ; // Add odd element to the sum
}
}
p r i n t f ( ”Sum of odd elements i n the v e c t o r : %d\n” , sum ) ;
return 0;
}
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag12 / 30
Imperative languages - example in Fortran 95
program sum odd elements vectorized
i m p l i c i t none
integer , parameter : : n = 9
integer : : v e c t o r ( n ) = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9]
integer : : sum
sum = sum( v e c t o r (mod( vector , 2) /= 0))
p r i n t ∗ , ’Sum of odd elements i n the v e c t o r : ’ , sum
end program sum odd elements vectorized
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag13 / 30
Functional programming
λ−calculus
Alonzo Church, 1930s
formal basis of all functional languages
infix notation
syntax:
expression → constant
|variable
|(expressionexpression)
|(λvariable.expression)
example
(λx. + 1 x) 2 ⇒ (+1 2) ⇒ 3
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag14 / 30
Examples
Examples of FL: Haskell, JavaScript, Scala, Erlang, Lisp, ML, Clojure,
OCaml, Lisp, etc. etc.
Lisp
( defun sum−odd−elements ( l s t )
( i f ( n u l l l s t )
0
( i f ( oddp ( car l s t ))
(+ ( car l s t ) (sum−odd−elements ( cdr l s t ) ) )
(sum−odd−elements ( cdr l s t ) ) ) ) )
( l e t (( v e c t o r ’(1 2 3 4 5 6 7 8 9 ) ))
( format t ” Result : ˜a” (sum−odd−elements v e c t o r ) ) )
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag15 / 30
OCaml
l e t rec sum odd elements l s t =
match l s t with
| [ ] −> 0
| hd : : t l −>
i f hd mod 2 <> 0 then
hd + sum odd elements t l
e l s e
sum odd elements t l
l e t () =
l e t v e c t o r = [ 1 ; 2; 3; 4; 5; 6; 7; 8; 9] in
l e t r e s u l t = sum odd elements v e c t o r in
P r i n t f . p r i n t f ”Sum of odd elements i n the l i s t : %d\n” r e s u l t
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag16 / 30
Logic programming
based on logical statements
uses first order predicate calculus; ingredients
▶ variables: e.g. x, y, z
▶ constants: e.g. 1, 2, a, b
▶ predicates: e.g. P(x), Q(y), properties or relationships that can be true
or false for objects or values
▶ quantifiers: universal quantifier ∀, e.g.∀ x P(x), and existential
quantifier ∃, e.g. ∃ x P(x)
▶ connectives: AND (∧), OR (∨), NOT (¬), and IMPLIES (→)
example: ∀ x (P(x) → Q(x)) means ”for all values of x, if P(x) is
true, then Q(x) is also true”
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag17 / 30
Prolog
Example 1: family relations
male ( harry ) .
female ( l i z ) .
parent ( p h i l , chas ) .
parent ( l i z , chas ) .
parent ( chas , harry ) .
parent ( chas , w i l l s ) .
grandmother (GM, C):−
mother (GM, P) ,
parent (P, C ) .
mother (M,C):−
female (M) ,
parent (M, C ) .
% Run : grandmother ( l i z , Who) .
% Result : Who=harry and Who=w i l l s
Example 2 (recursion): sum of
elements from a list
s u m l i s t ( [ ] , 0 ) .
s s u m l i s t ( [H|T] ,N) :−
s u m l i s t (T, N1) ,
N i s N1+H.
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag18 / 30
Example 3: sum of odd elements
sum odd elements ( [ ] , 0 ) .
sum odd elements ( [ Head | T a i l ] , Sum) :−
0 i s Head mod 2 , % I f Head i s even ,
sum odd elements ( Tail , Sum ) . % s k i p Head
sum odd elements ( [ Head | T a i l ] , Sum) :−
1 i s Head mod 2 , % I f Head i s odd ,
sum odd elements ( Tail , TailSum ) , % sum of odd elem . i n Tail ,
Sum i s Head + TailSum . % and add Head to the sum .
% Example usage :
% sum odd elements ( [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9] , Result ) .
% Result w i l l contain the sum of odd elements : 25
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag19 / 30
Object-Oriented Programming
satistifes three important needs:
▶ reusability
▶ minimal changes for
modifying behaviour
▶ independence of components
extension of data and/or
operations
redefinition of operations
abstraction
polymorphism
realPart printOn: aStream.
aStream nextPut : $+.
imaginaryPart printOn: aStream.
aStream nextPut : $i
5.2.3 The Collection Hierarchy
Collections are containers whose elements are organized in a specific manner. The different types
of organization include linear, sorted, hierarchical, graph, and unordered. Linear collections include
the familiar examples of strings, arrays, lists, stacks, and queues. Unordered collections include bags,
sets, and dictionaries (also known as map collections in Java). Graphs and trees are also collections, as
are sorted collections, whose elements have a natural ordering (each element is less than or equal to its
successor).
Built-in collections in imperative languages, such as FORTRAN, C, Pascal, and Ada, have historically
been limited to arrays and, if the application programmer is lucky, strings. The programmer must
build the other types of collections using the array data structure or by defining linked nodes. Functional
languages like Lisp include the list, which is essentially a linked structure, as the basic collection type.
Smalltalk provides the standard for object-oriented languages by including a large set of collection
types. They are organized, for maximum code reuse, in a collection class hierarchy. Figure 5.4 shows a
class diagram of the most important Smalltalk collection classes.
Object
Col lect ion
Bag IndexedCol lect ion Set
FixedSizeCol lect ion
Array String
OrderedCol lect ion Dict ionary
SortedCol lect ion
Figure 5.4 The Smalltalk collection class hierarchy
C7729_ch05.indd 157C7729_ch05.indd 157 03/01/11 9:31 AM03/01/11 9:31 AM
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag20 / 30
Java
public c l a s s SumOddElements {
public s t a t i c void main ( S t r i n g [ ] args ) {
i n t [ ] v e c t o r = {1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9};
i n t sum = 0;
for ( i n t element : v e c t o r ) {
i f ( element % 2 != 0) { // Check i f the element i s odd
sum += element ; // Add odd element to the sum
}
}
System . out . p r i n t l n ( ” Result : ” + sum ) ;
}
}
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag21 / 30
Python - while OOP, does not impose it
v e c t o r = [1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9]
sum = 0
for element in v e c t o r :
i f element % 2 != 0:
sum += element
p r i n t ( ”Sum of odd elements i n the l i s t : ” , sum)
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag22 / 30
Programs: from code to execution
the source code is not directly runnable on the CPU
means to run a program
▶ compilation - ahead-of-time compilation for compiled languages (e.g.
C/C++/Fortran...)
▶ interpretation - a special software interprets and executes the
instructions in a program - for interpreted languages (e.g. Lisp, Prolog,
Python)
▶ just-in-time compilation for programs running on virtual machines (e.g.
Java, Python (CPython))
compilation allows code optimization
sometimes several techniques are used for a single language: e.g.
Java is compiled to bytecode, runs on VM and has a JIT
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag23 / 30
AOT vs JIT vs interpretation
from https://attractivechaos.github.io/plb/
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag24 / 30
AOT compilation
Program
in high-level
language
Program
in assembly
language
Program
in machine
code
0100010001
1101010001
0010010000
1001000101
mov ax,'00'
mov di,counter
mov cx,digits+cntDigits/2
cld
rep stosw
inc ax
mov [num1 + digits - 1],al
mov [num2 + digits - 1],al
mov [counter + cntDigits - 1],al
# let rec sort = function
| [] -> []
| x :: l -> insert x (sort l)
and insert elem = function
| [] -> [elem]
| x :: l -> if elem < x then elem :: x :: l
else x :: insert elem l;;
Source code Object code
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag25 / 30
Advantages:
▶ efficiency
▶ privacy
▶ offline execution: no need for the original source code
Disadvantages:
▶ low portability
▶ build complexity and time
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag26 / 30
Source code
Assembly code
Libraries
Executable
COMPILER
LINKER
ASSEMBLER
Object code
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag27 / 30
Interpretation
there is an interpreter software that reads and executes the program
instruction-by-instruction
supports ”write-once-execute-everywhere” idea
Advantages:
▶ portability
▶ dynamic features
▶ ease of debugging
Disadvantages:
▶ low performance
▶ dependency on interpreter
examples: Python, R
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag28 / 30
Virtual machines and JIT
VM: an abstract machine (program) that runs the bytecode
represenation of the program
the program is compiled to bytecode either by AOT compiler or by a
just-in-time (JIT) compiler
JIT may operate at various time points and different granularity to
optimize the (byte)code
Advantages: portability and good performance
Disadvantages: overhead and dependency on VM
example: Java Virtual Machine (JVM) contains bothseveral an
interpreter for bytcode, a compiler from code to bytecode and from
an optimizing JIT
there are also JITs for other interpreted languages (e.g. Python)
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag29 / 30
If you’re curious about other programming languages, check out
http://helloworldcollection.de
Questions?
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to programming languag30 / 30