Característiques generals dels llenguatges de programació: enllaç i temps d'enllaç

Enllaç i temps d'enllaç

Tema IV. Caracteristiques generals dels
llenguatges de programació:
Part 1. Enllaç i temps d'enllaç
21721 - Llenguatges de Programació
UIB
M
Universitat
de les Illes Balears
Antoni OliverContingut

1. Enllaç i temps d'enllaç
2. Tipus de dades
3. Control de sequencia
4. Gestió de memòria

2Enllaç i temps d'enllaç

1. Enllaç i temps d'enllaç
2. Noms i entorns

Pratt, Terrence W., Zelkowitz, Marvin V. (2000). Programming languages:
design and implementation. Pearson (4th ed). Capítol 2.2.3.
3Enllaç i temps d'enllaç
·Podem definir l'enllaç (binding) d'un element d'un
programa a una característica particular o
propietat simplement com l'elecció de la propietat
d'entre un conjunt de possibilitats.
·El temps en el que aquesta elecció es fa
s'anomena temps d'enllaç (binding time)
d'aquesta propietat per aquest element.
4Classes de temps d'enllaç
Temps d'execució (run time):
A l'entrada en un subprograma o bloc (parametres)
En punts arbitraris (assignació)
Temps de compilació o traducció (compile time)
Escollits pel programador (noms i tipus de variables)
Escollits pel traductor (representació en memoria)
Temps d'implementació del llenguatge:
Representació de nombres i operacions aritmètiques
Temps de definició del llenguatge:
Estructures del llenguatge
5Temps d'enllaç del conjunt de tipus possibles
i := i + 10;
Conjunt de possibles tipus (en general):
Dreal, enter, booleà, etc.
·Temps d'enllaç:
Temps d'execució x
•
–
Temps de compilació o traducció V
· Podem haver definit més tipus, així que pot ser un d'aquests.
Temps d'implementació del llenguatge x
•
–
Temps de definicio del llenguatge
· El llenguatge pot no suportar la creació de nous tipus.
6Temps d'enllaç del tipus d'una variable
i := i + 10;
Tipus de la variable i:
Di: real;
Olet i;
·Temps d'enllaç:
Temps d'execució V
· Llenguatges amb tipat dinàmic.
Temps de compilació o traducció
· Llenguatges amb tipat estàtic.
Temps d'implementació del llenguatge x
. -
Temps de definició del llenguatge x
.-
7Temps d'enllaç del conjunt de possibles valors
i := i + 10;
Conjunt de possibles valors del tipus real:
Rang de nombres reals que es poden representar i
manipular a l'ordinador virtual.
·Temps d'enllaç:
Temps d'execució x
•
–
Temps de compilació o traducció x
•
–
Temps d'implementacio del llenguatge
Cada implementacio pot tenir rangs diferents.
•
Temps de definició del llenguatge x
•
–
8Temps d'enllaç del valor d'una variable
i := i + 10;
Valor de la variable i
"10 més que el que valia abans"
·Temps d'enllaç:
Temps d'execució V
· Fa falta executar el programa.
Temps de compilació o traducció x
. -
Temps d'implementació del llenguatge x
•
–
Temps de definició del llenguatge x
. -
9Temps d'enllaç de la representació de "10"
i := i + 10;
Representació de la constant 10:
1. En el text del programa (caracters 1 i 0).
2. En memoria (seqüència de bits).
·Temps d'enllaç:
Temps d'execució x
•
–
Temps de compilació o traducció x
•
–
Temps d'implementacio del llenguatge
· Com es representa un nombre en memòria (2).
Temps de definicio del llenguatge
· De quines maneres es poden representar els nombres (1).
10Temps d'enllaç de les propietats de "+"
i := i + 10;
Propietats de l'operador +:
1.
Ús de + per representar la "suma" de valors.
2. Definició dels diferents tipus de "suma" (entera, real, etc).
3. Quina "suma" utilitzar.
4. Resultat d'aplicar la "suma" als operands.
·Temps d'enllaç:
Temps d'execució V
· Resultat (4), quina "suma" utilitzar (tipat dinamic) (3).
Temps de compilació o traducció
Quina "suma" utilitzar (tipat estàtic) (3).
Temps d'implementacio del llenguatge
•
· Definició dels diferents tipus de "suma" (2).
Temps de definició del llenguatge
· Ús de + per representar la "suma" (1).
11Importancia del temps d'enllaç
"Es fa en temps de compilació o en temps
d'execució?"
Si la majoria dels enllaços es fan en temps
d'execució (implementacions interpretades):
Major temps d'execució (menor eficiencia).
Mes flexibilitat.
Si la majoria dels enllaços es fan en temps de
compilació (implementacions compilades):
Menor temps d'execució (major eficiencia).
Menys flexibilitat.
12Enllaç i temps d'enllaç

1. Enllaç i temps d'enllaç
2. Noms i entorns

Pratt, Terrence W., Zelkowitz, Marvin V. (2000). Programming languages:
design and implementation. Pearson (4th ed). Capítol 9.2.
Gabbrielli, M, Martini, S. (2023). Programming Languages: Principles and
Paradigms (2nd ed.). Springer. Capítol 4.
13Noms i entorns
Objectes denotables
Nom:
Objecte en el sentit ample de la
paraula, no només Orientat a Objecte
Seqüència de caracters per representar (denotar) un
objecte.
· Identificadors, en la majoria de llenguatges.
·Objecte denotable:
Aquells objectes als quals podem donar nom.
· Objectes definits pel programador: variables, parametres
formals, subprogrames, etc.
· Objectes definits pel llenguatge: tipus primitius, operacions
primitives, constants predefinides, etc.
Nom = objecte denotat:
La variable "x". La variable amb nom "x".
14Noms i entorns
Entorns i blocs
· Entorn (environment):
Conjunt d'associacions, en un instant de l'execució, entre noms i
objectes denotables.
Un mateix objecte pot ser denotat per mes d'un nom en entorns
diferents (pas per referencia): alias.
· Apuntadors (referencies) ens permeten fer una cosa semblant.
Un mateix nom pot denotar objectes diferents segons el flux del
programa: visibilitat (àmbit).
Bloc:
Regió del programa que conté declaracions locals.
· begin ... end, { ... }, ( ... ), etc.
Associats a un procediment o no (en línia, in-line).
15Noms i entorns
Entorns i blocs
·Blocs encastats: regla de visibilitat (àmbit):
Un nom local en un bloc és visible en aquell bloc i els
inclosos en ell, fins que s'introdueix una declaració que
l'amagui.
Tipus d'entorns:
Entorn local: noms locals.
Entorn no-local: noms visibles però no locals.
Entorn global: noms usables a qualsevol lloc.
Limitacions:
No podem encastar subprogrames en C o Java: es
defineixen a l'entorn global.
· Se simplifiquen els àmbits dins subprogrames: només podem
accedir a variables locals o globals.
16Noms i entorns
Entorns i blocs
Canvis d'entorn:
> Entrada en un bloc.
•
Creació de l'associació entre
ocals i objectes
denotats.
· Desactivació de les
associacions dels noms
redefinits.
O Sortida d'un bloc.
· Destrucció de l'associació
entre noms locals i objectes
denotats.
· Reactivació de les associacions
dels noms redefinits.
{
let x = 0;
{
let x = 1;
{
let x = 2;
}
print (x);
}
print (x);
}
17Noms i entorns
Àmbit lèxic (estàtic) i àmbit dinàmic
· Àmbit lèxic (estàtic):
Segons l'estructura sintàctica,
l'encastat més proper.
· Més facil d'entendre pel programador.
· Més facil d'implementar en un
compilador.
Àmbit dinàmic:
L'associació mes recent en el temps.
· Més facil d'implementar en un
interpret.
Entorn no-local a f1:
Quina és l'associació activa?
· L'activa quan es declara f1.
▪
Àmbit lèxic (estàtic).
· L'activa quan es crida f1.
· Àmbit dinàmic.
{
let x = 0
function f1() {
X = X + 1;
}
{
let x = 5;
f1();
print("x1="+x);
}
print("x2="+x);
}
Àmbit lèxic (estàtic)
x1=5
x2=1
Àmbit dinàmic
x1=6
×2=0
18Noms i entorns
Àmbit lèxic (estàtic) i àmbit dinàmic
LISP
; àmbit lèxic
(setq × 0)
Fa servir la
x segons
l'estructura
sintàctica
Fa servir la
x segons
l'associació
més recent
; àmbit dinàmic
(defvar x 0)
(defun px
(print x) )
(defun px ()
(print x) )
(defun fx (x)
(px)
t)
defun fx (x)
(px)
t)
Les x locals
no es fan
servir
Les x són
l'enllaç
actiu.
(defun fx2 (x)
(fx (+ x 1))
(px)
t)
(defun fx2 (x)
(fx (+ x 1))
(px)
t)
(px)
(fx 5)
(fx2 5)
0
0
00
(px)
(fx 5)
(fx2 5)
0
5
6 5
19Noms i entorns
Començament de l'àmbit
Cridam primer
fi després g ...
No es pot fer
servir la x local
quan encara
no té valor!
·C, Java, etc:
Des de la
declaració
Fins al final
del bloc
Python
Des de l'inici
del bloc
Fins al final
del bloc
Per això, a ANSI C, hem
de declarar les funcions
abans de fer-les servir
(p.e., recursivament).
int x = 1;
C
X = 1
Python
def f() :
global
X
y = X
X = 2 # global
print(y) # 1
}
def g() :
y = X
X = 2 # local
printf(y)
}
void f() {
int y = x;
x = 2; // global
printf(y); // 1
}
void g() {
int y = x;
// local
int x = 3;
printf(y); // 2
}
20Noms i entorns
Registres d'activació
Implementació dels entorns
Noms -> variables
Informació per fer-los i desfer-los
Current Environment Pointer:
Indica el registre d'activació que està actiu.
Dos casos:
Blocs en línia
Crides de subprogrames
·Gestió: gestió de memoria
Estàtica
Dinamica
· Pila
· Monticle
Informació
del sistema
Ad. retorn
Ad. resultat
Paràmetres
Variables
locals
Resultats
intermedis
Ja veurem les tècniques de gestió de memoria.
De moment, suposarem que feim servir una pila.
21Noms i entorns - Registres d'activació
Blocs en línia
Apuntador cadena
dinàmica:
A: {
Apuntador
cadena
dinàmica
A l'anterior registre
d'activació.
(El seu “pare”).
•
B: {
Variables
locals
Nom, tipus, valor.
Arrays dinàmics?
}
b = a + 2;
}
Da + a
O Resultats que no
tenen nom
int a = 1;
int b = 2;
Variables locals:
int b = 3;
int c = a + a;
Resultats
intermedis
Resultats
intermedis:
22Noms i entorns - Registres d'activació
Blocs en línia
ACD: nil
ACD: nil
1
int a = 1
int b = 2
2
int a = 1
int b = 2
t = a + 2
B: {
2
int b = 3;
int c = a + a;
}
3
b = a + 2;
}
(La pila creix cap a baix)
Current Environment Pointer: R.A. actiu
A: {
1
int a = 1;
int b = 2;
t = a + 2
ACD: A
int b = 3
int c = t
ACD: nil
t = a + a
3
int a = 1
int b = t
t = a + 2
23Noms i entorns - Registres d'activació
Subprogrames
Semblant als blocs en linia V,
però més informació:
Apuntador cadena dinamica V
· RA on es crida el subprograma
· Àmbit dinamic de variables no-locals
Apuntador cadena estàtica
· RA on es defineix el subprograma
· Àmbit lèxic de variables no-locals
Adreça de retorn: adreça crida + 1
Adreça del resultat: dins el RA on es crida
Parametres: semblant a variables locals
Variables locals
Resultats intermedis
V
Subprogrames =
procediments i funcions
Ap. cadena
dinàmica
Ap. cadena
estàtica
Ad. retorn
Ad. resultat
Paràmetres
Variables
locals
Resultats
intermedis
24Noms i entorns - Registres d'activació
Subprogrames
·Crida subprograma:
Modificació del Current Instruction
Pointer
· A l'inici del subprograma
Ap. cadena
dinàmica
Creació de l'RA
· Es reserva espai a la pila
R.A. actiu
Ap. cadena
estàtica
· S'actualitza cim pila
· S'actualitza RA actiu
Ad. retorn
Pas de parametres
Ad. resultat
· Segons l'RA des d'on es crida
Cim piļa
R.A. actiu
Parametres
· Adreça del resultat a l'RA on es crida
R. A.
Variables
locals
Informació del sistema
· Ap. cadena dinamica
· Adreça de retorn (CIP anterior)
Resultats
intermedis
Inicialització
· Ap. cadena estàtica
· Variables locals
· Resultats intermedis
Inici pila
R. A.
...
R. A.
Cim pila
Memòria
lliure a la
pila
25