Programming Languages, Technologies and Paradigms

Introduction

Objectives

To understand why we need to know different programming paradigms To list the most important programming paradigms out there To define formally a new programming language To understand some basic concepts about the implementation of programming languages: compilation vs interpretation

Contents

Motivation Programming paradigms

Imperative Declarative Object oriented ormal description !synta" # semantics$ Translation

Programming languages

Motivation
% story beginning in &'() ***

()+s

Programmer time was cheap, machines were e"pensive keep the machine busy -ometimes programs were directy written in machine code* .and/made compilations were also fre0uent in order to get the best performance for a given hardware direct connection language 1 hardware

Today

Programmer time is e"pensive, the machines are cheap keep the programmer busy Programs are designed to be efficient2 and they are automatically compiled to generate portable and efficient code direct connection between the program design and the language: object2 concurrency2 etc*
4

Motivation
3earning Programming languages

-o today we can forget about the hardware and just focus on the programming language Three approaches to learn new programming languages:
&* Programming as a job 4* Programming as a branch of mathematics 5* Programming through concepts

Motivation
&* Programming as a job

It involves studying just one paradigm with just one language It is counterproductive !it has a boomerang effect$: having a bad e"perience2 for e"ample2 handling lists in some languages can lead to the wrong conclusion that manipulating lists is always complicated and costly

Motivation
&* Programming as a job

6"ample: 7ip a list in 8ava vs .askell

8ava .askell

Motivation
4* Programming as a branch of mathematics

It involves either studying an +ideal+2 restricted language !Dijkstra$ or it is too theoretical2 unpractical2 out from the real world 6"ample: formal verification !of a single line !9$ program$

Motivation
5* Programming through concepts

It involves studying a set of semantic concepts and implementation structures leading to a natural description of the languages and their implementations
+kernel+ 3anguage Data %bstractions :ecursion ***

3ogic language ;on/determinism 3ogic variables <nification

unctional language Polymorphism -trategies .igher Order

Imperative language 6"plicit states Modularity =omponents

OO language =lasses Inheritance

+dataflow+ language =oncurrency

Motivation
5* Programming through concepts

Once the main concepts are known2 translating into a particular implementation is seamless !very easy$*
=## = =obol Pascal

8ava

=lips

Prolog 8ava-cript =>

.askell

10

Motivation
5* Programming through concepts

?e will focus on this third approach ?e will study the main concepts of some of the most popular programming paradigms Then we will apply them to particular programming language implementations

11

Motivation
5* Programming through concepts

<nderstanding the main concepts of several programming paradigms has a number of advantages:

@roaden our perspective as software engineers2 and get abstracted from the particular programming language2 just focusing on the characteristics re0uired from the programming language for solving a problem Aiven a problem2 choose the most appropriate paradigm !and programming language$ for building a solution -imulate some techni0ues re0uired for building a solution that are not present in a particular programming language

12

Motivation
5* Programming through concepts

Take the right pill ***

13

Motivation
5* Programming through concepts

If you take the blue pill B you will continue working with just one language *** at most !though sometimes +ignorance is bliss+$

14

Motivation
5* Programming through concepts

If you take the red pill B you will potentially master do7ens of languages just by taking a 0uick look at the synta" !+you stay in ?onderland and I show you how deep the rabbit hole goes+$

15

Programming paradigms

% programming paradigm is a fundamental style of programming* Definition: basic model for designing and developing programs which provides methods and techni0ues for producing programs according to specific guidelines !style and approach for solving a problem$ our main paradigms:

Imperative unctional !declarative$ 3ogic !declarative$ Object/oriented

Others: aspect/oriented2 event/driven2 natural computing2 0uantum computing2 etc*

16

Imperative paradigm

% program is a se0uence of commands that changes the state of a machine It establishes how to proceed C %lgorithm !recipe$ The main concept is the machine state2 given by the values of the variables stored in memory Instructions are se0uentially processed and the program builds a se0uence of machine states leading to the solution This model strongly follows Don ;eumann+s machine Programs are structured in blocks and modules 6fficient2 difficult to modify and verify2 with side effects
17

Imperative paradigm
Don ;eumann+s machine

18

Imperative paradigm
6"ample: string length in =
int length(char v[]) { int i = 0; while(v[i] != '\0') i++; return i; }

19

Imperative paradigm
-ide effects: two calls to the same function with the same arguments return different results
Alobal variable

int flag = 0;
int length(char v[]) { int i = 0; if (flag == 0) { while(v[i] != '\0') i++; flag = 1; } else flag = 1; return i; }
20

6"ample of e"ecution: E length!FholaG$, HH I E length!FholaG$, HH )

Declarative paradigm

% program contains a set of properties describing the desired solution* ;othing is said about how to obtain it* % declarative program J e"ecutable specification %ccording to :* Kowalski&: P:OA:%M J 3OAI= # =O;T:O3

3OAI=: related with the establishment of ?.%T =O;T:O3: related with the establishment of .O?

The main concerns of the programmer are the logic aspects of the solution* =ontrol aspects are left to the compilerHsystem* 6asy to verify and modify2 concise and clear
&

%lgorithm J logic # control* Kowalski2 :obert* =ommun* %=M* I4I/I5L* &'M'* ;ew Nork

21

Declarative paradigm
6"ample: fibonacci numbers

Mathematical definition
fib(0) = 1 fib(1) = 1 fib(n) = fib(n-1) + fib(n-2)

Declarative program !functional$

fib(0) = 1 fib(1) = 1 fib(n) = fib(n-1) + fib(n-2)

22

Declarative paradigm
6"ample: fibonacci numbers

Mathematical definition
fib(0) = 1 fib(1) = 1 fib(n) = fib(n-1) + fib(n-2)

Declarative program !functional$

fib(0) = 1 of the declarative program using 6fficient version fib(1) = 1
an accumulator parameter fib(0) = fib(n) = 1fib(n-1) + fib(n-2)

fib(1) = 1 fib(n) = fib_aux(1,1,n) fib_aux(x,y,0) = x fib_aux(x,y,n) = fib_aux(y,x+y,n-1)

23

Declarative paradigm
Two main declarative sub/paradigms:

unctional paradigm

unction definition by using e0uations !sJt$ Polymorphism .igher order :elationships definition by using rules FIf = then %G: !% O =&2 ***2 =n$ 3ogic variables ;on/determinism
24

3ogic paradigm

Declarative paradigm
6"ample: function length
unctional paradigm !.askell$
length [] = 0 length (x:xs) = (length xs) + 1

3ogic paradigm !Prolog$

length([ ],0). length([X|Xs],N) :- length(Xs,M), N is M+1.

25

Imperative vs Declarative paradigm

Imperative

More comple" that it seems Distracts programmer+s attention from the functional aspect of the solution in order to focus on the machine control Difficult to paralleli7e More efficient .igher level programming language 1 higher e"pressive power 1 less code 1 higher productivity 1 better maintenance -impler semantic %utomatic control 6asier to paralleli7e
26

Declarative

Object oriented paradigm

@ased on the idea of encapsulating state and operations within objects Object: state # operations Objects react to messages by e"ecuting its operations
Object &
op& op4 op5 message op&
state& state4 state5 state& state4 state5

Object 4

op4 op5

%dvanced concepts: polymorphism2 inheritance2 etc*

27

Object oriented paradigm

6"ample: list search !8ava$
public class List { private int[] list = new int[100]; public int search(int elem) { for (int i = 0; i < [Link]; i++) if (list[i] == elem) return i; return -1; } } 3ist
search intP Q

28

Programming Languages
ormal description of a programming language

.ow can we define a programming language without ambiguities or misconceptionsR ormally999

-ynta"

-emantics

Programming 3anguage

29

Programming Languages
ormal description of a programming language

-ynta":

which se0uence of characters make up a FlegalG program* which are the main Fbuilding blocksG of the language which is the meaning of each building block which is the meaning of the a concrete legal program

-emantics:

30

Programming Languages
-ynta"

Defines the FappearanceG of the program Determines which programs are legal or comply with a language specification Different approaches

Aenerative grammars !=homsky &24252I$ %utomata @; notation !@ackus/;aur orm$ Araphical representation

31

Programming Languages
-ynta" / 6"tended @; ;otation

inite set of rules: SwE ::J S"E T % SyE T @ T B SwE is used for indicating a symbol not predefined in the language !au"iliar$ that must be rewrittenHreplaced The symbol T means +or+ -0uare brackets P Q surrounding optional items =urly brackets U V !or symbol W$ for indicating a se0uence of ) or more items -ymbol # for indicating a se0uence of & or more items

32

Programming Languages
-ynta" / 6"tended @; ;otation
6"ample !8ava synta"$
@;

<while_statement> ::= while ( <expression> ) <statement> <expression> ::= <statement> ::=

Araphical

33

Programming Languages
-ynta" / 6"tended @; ;otation
6"ample !Modula/4 synta"$
@;

<while_statement> ::= WHILE <expression> DO <statement> {; <statement>} END <expression> ::= <statement> ::=
Araphical

34

Programming Languages
-ynta" / 6"tended @; ;otation
6"ample ! ull 8ava language$
[Link] [Link] [Link]

35

Programming Languages
-emantics

Defines the meaning of a language

3anguage -emantics

-tatic -emantics

Dynamic -emantics

36

Programming Languages
-tatic semantics

Defines restrictions on the structure of valid programs that are hard or impossible to e"press in standard syntactic formalism !@; $ 6"ample: % :J @ # =

-yntactically it is a correct e"pression It may not be legal2 if %2 @ or = have not been previously declared !we do not know their data type$ It may not be legal if %2 @ and = belong to incompatible data types !e*g* integer vs string vs array$

37

Programming Languages
Dynamic semantics

Defines the behavior of the programming language constructs

;atural language is often used to specify the dyanmic semantics of a language* %mbiguities and misunderstandings are usual Dynamic semantics should be defined in a mathematically rigorous way % formal definition provides a mathematical model that describes the possible computations described by the language There are several ways: operational2 a"iomatic2 delcarative semantics ***
38

Programming Languages
Dynamic semantics

In dynamic semantics we typically need a formal way of specifying the computation of a particular program step by step C1 C2 .. Cn 6ach step is called a configuration Ci 6ach configuration is a pair: <P, e>2 where P is a set of instructions !program$ that must be e"ecuted and e is the state of the machine !the variables+ values$ at that point in time ?e use configurations Ci and logic for specifying the behavior !meaning$ of each language construct

39

Programming Languages
Dynamic semantics

6"ample* @oolean constants evaluation

<true, e> true <false, e> false

40

Programming Languages
Dynamic semantics

6"ample* @oolean constants evaluation

<true, e> true <false, e> false

Means that the constant true gets always evaluated to true2 regardless of the current state e

41

Programming Languages
Dynamic semantics

6"ample* =omparison evaluation

Two rules

&

<a0,e>

n0

<a1,e>

n1

n0 n1 true

< a0 a1, e>

4

<a0,e>

n0

<a1,e>

n1

n0 > n1

< a0 a1, e>

false
42

Programming Languages
Dynamic semantics

6"ample* =omparison evaluation

Two rules

Premises* If FthisG gets evaluated to true

&

<a0,e>

n0

<a1,e>

n1

n0 n1 true
=onclusion

< a0 a1, e>

4

Then

<a0,e>

n0

<a1,e>

n1

n0 > n1

< a0 a1, e>

false
43

Programming Languages
Dynamic semantics

6"ample* =omparison evaluation

Two rules

%nd

&

<a0,e>

n0

<a1,e>

n1

n0 n1 true

< a0 a1, e>

4

<a0,e>

n0

<a1,e>

n1

n0 > n1

< a0 a1, e>

false
44

Programming Languages
Dynamic semantics

6"ample* -e0uence

<i0, e> <i0, e> <(i0;i1), e> <(i0;i1), e> <(;i), e> <i,e>

45

Programming Languages
Dynamic semantics

6"ample* -e0uence
=onfiguration transition

<i0, e> <i0, e> <(i0;i1), e> <(i0;i1), e> <(;i), e> <i,e>
6mpty instruction

46

Programming Languages
Dynamic semantics

6"ample* ?hile

Two rules for describing the behavior

&

<b,e> false < while b do i, e> <,e>

<b,e> true

<while b do i, e> < (i;while b do i), e>

47

Programming Languages
3anguage translators

% program written in a high level language can not be understood by the machine The machine does only understand binary code % translation process is re0uired
Program XXXXXXXX XXXXXXXX XXXXXXXX XXXXXXXX XXXXXXXX Translator =omputer ))&)&&)&))&) )&)&))

48

Programming Languages
3anguage translators

Two types !can be complemented2 not e"clusive$

=ompiler Interpreter

49

Programming Languages
=ompiler

% program that transforms !in a single action$ source code written in a source !high/level$ programming language into another target !low/level$ computer language If the target language is binary !e"ecutable$2 it is called native compiler
Program XXXXXXXX XXXXXXXX XXXXXXXX XXXXXXXX XXXXXXXX ;ative compiler @inary object code &)&))&)& ))))&)&& =omputer

50

Programming Languages
=ompiler

Phases
Object code

-ource program

XXXXX XXXXX XXXXX

3e"ical %nalysis

-yntactic %nalysis

-emantic %nalysis

=ode Aeneration

&)&))&)& ))))&)&&

51

Programming Languages
=ompiler

3e"ical %nalysis
Object code

-ource program

XXXXX XXXXX XXXXX

3e"ical %nalysis

-yntactic %nalysis

-emantic %nalysis

=ode Aeneration

&)&))&)& ))))&)&&

The program splits into a se0uence of primitive syntactic components or words !identifiers2 numbers2 reserved words2 etc*$ This se0uence of words is the input of the ne"t phase
52

Programming Languages
=ompiler

3e"ical %nalysis* 6"ample

Object code

-ource program

XXXXX XXXXX XXXXX

3e"ical %nalysis

-yntactic %nalysis

-emantic %nalysis

=ode Aeneration

&)&))&)& ))))&)&&

-ource program

fun {Fact N} if N==0 then 1 else N*{Fact N-1} endif end B is a vector of chars **

[f,u,n,{,F,a,c,t, ,N,},\n, ,i,f, ,N,=,=,0, , t,h,e,n, ,1,\n, ,e,l,s,e, ,N,*,{,F,a, c,t, ,N, -,1,}, ,e,n,d,i,f,\n,e,n,d] = string
53

Programming Languages
=ompiler

3e"ical %nalysis* 6"ample

Object code

-ource program

XXXXX XXXXX XXXXX

3e"ical %nalysis

-yntactic %nalysis

-emantic %nalysis

=ode Aeneration

&)&))&)& ))))&)&&

[f,u,n,{,F,a,c,t, ,N,},\n, ,i,f, ,N,=,=,0, , t,h,e,n, ,1,\n, ,e,l,s,e, ,N,*,{,F,a, c,t, ,N, -,1,}, ,e,n,d,i,f,\n,e,n,d] = string B splits into ** [fun,{,Fact,N,},if,N,= =,0,then,1,else,N,*,{,Fact,N, -,1,},endif,end ]

= sequence of words
54

Programming Languages
=ompiler

-yntactic %nalysis
Object code

-ource program

XXXXX XXXXX XXXXX

3e"ical %nalysis

-yntactic %nalysis

-emantic %nalysis

=ode Aeneration

&)&))&)& ))))&)&&

The instructions that conform to a particular @; are recogni7ed and a parse tree is built The parse tree is the input of the ne"t phase

55

Programming Languages
=ompiler

-yntactic %nalysis
Object code

-ource program

XXXXX XXXXX XXXXX

3e"ical %nalysis

-yntactic %nalysis

-emantic %nalysis

=ode Aeneration

&)&))&)& ))))&)&&

[fun,{,Fact,N,},if,N,= =,0,then,1,else,N,*,{,Fact,N, -,1,},endif,end ]

= sequence of words
B are recogni7ed as instructions **

fun {Fact N} if N = = 0 then 1 else N* {Fact N-1} endif end = instruction

56

Programming Languages
=ompiler

-yntactic %nalysis
Object code

-ource program

XXXXX XXXXX XXXXX

3e"ical %nalysis

-yntactic %nalysis

-emantic %nalysis

=ode Aeneration

&)&))&)& ))))&)&&

B a parse tree is built ***

57

Programming Languages
=ompiler

-emantic %nalysis
Object code

-ource program

XXXXX XXXXX XXXXX

3e"ical %nalysis

-yntactic %nalysis

-emantic %nalysis

=ode Aeneration

&)&))&)& ))))&)&&

-tatic semantics are checked %ppropriate measures are taken for checking dynamic semantics at runtime !this can only be done by generating e"tra code$
58

Programming Languages
=ompiler

-emantic %nalysis* 6"ample

Object code

-ource program

XXXXX XXXXX XXXXX

3e"ical %nalysis

-yntactic %nalysis

-emantic %nalysis

=ode Aeneration

&)&))&)& ))))&)&&

-ome restrictions are checked:

Declaration of variables prior to its use =ompatobility ad type conversion unction signature !the parameters of a call must match the formal parameters$
59

Programming Languages
=ompiler

=ode Aeneration
Object code

-ource program

XXXXX XXXXX XXXXX

3e"ical %nalysis

-yntactic %nalysis

-emantic %nalysis

=ode Aeneration

&)&))&)& ))))&)&&

=ode is generated and optimi7ed The code includes instructions for checking dynamic semantics !e*g* checking that inde"es belong to an array range2 B$

Y J ZHN Y J DPNQ

error if it is e"ecuted with a value of N J ) error if N has a valur out of the vector range
60

Programming Languages
=ompiler
The big picture

61

Programming Languages
Interpreter

% program that e"ecutes source code !line/per/line$ written in a source !high/level$ programming language on a particular machine It is actively translating each high/level instruction into a binary instruction that the underlying machine understands
Program XXXXXXXX XXXXXXXX XXXXXXXX XXXXXXXX XXXXXXXX Interpreter =omputer

62

Programming Languages
=ompiled vs Interpreted programming languages

% compiled program e"ecutes very fast %n interpreted program re0uires an on/line translator % program is compiled for a particular platform !it must be compiled n times to be deployed on n platforms$ %n interpreted program can be e"ecuted on any platform that has an appropriate interpreter % compiled program detects errors !either syntactic or semantic$ prior to the program translation and e"ecution %n interpreter detects all errors in the course of the program e"ecution
63

Programming Languages
Mi"ed languages !why don+t we get the best of both worldsR$

The source program is first compiled into another low/level program that is easily interpreted and e"ecuted by an interpreter* The source program is writen in a high/level programming language The target program+s low/level language is called intermediateHbytecodeHpseudocode This intermediate code is very close to the machine language2 but it is abstract enough for being portable This is the approach of the most modern programming languages !8ava2 *;6T2 etc*$
64

Programming Languages
Mi"ed languages !why don+t we get the best of both worldsR$
Program =ompiler

XXXXXXXX XXXXXXXX XXXXXXXX XXXXXXXX XXXXXXXX

Intermediate code

Interpreter

=omputer

The interpreter may be considered some kind of virtual machine

%pp& %pp4 Interpreter %pp5

65

Programming Languages
Mi"ed languages !why don+t we get the best of both worldsR$

6"ample* 8ava

=ompile once2 run anywhere99

66