• Non ci sono risultati.

NAMES, SCOPES AND BINDING A REVIEW OF THE CONCEPTS Name Binding and Binding Time

N/A
N/A
Protected

Academic year: 2022

Condividi "NAMES, SCOPES AND BINDING A REVIEW OF THE CONCEPTS Name Binding and Binding Time"

Copied!
44
0
0

Testo completo

(1)

NAMES,  SCOPES  AND  BINDING   A  REVIEW  OF  THE  CONCEPTS  

Name  Binding  and  Binding  Time  

  Name  binding  is  the  associa1on  of  objects  (data  and/or  code)   with  names  (iden1fiers)  

  Shape  S  =  new  Shape();  

  The  binding  of  a  program  element  to  a  par1cular  property  is   the  choice  of  the  property  from  a  set  of  possible  proper1es  

  binding  and  binding  1mes  are  the  proper1es  of  program  elements  that   are  determined  by  the  defini1on  of  the  language  or  its  implementa1on  

  The  1me  during  program  formula1on  or  processing  when   this  choice  is  made  is  the  binding  +me  

  There  are  many  classes  of  bindings  in  programming   languages  as  well  as  many  different  binding  1mes  

(2)

Binding  Time  

Binding  1mes:  

  Run  1me  (execu1on  1me):  

 On  entry  to  a  subprogram  or  block  

 Binding  of  formal  to  actual  parameters  

 Binding  of  formal  parameters  to  storage  loca1ons  

 At  arbitrary  points  during  execu1on  

 binding  of  variables  to  values  

 Dynamic  binding  

Binding  Time  

 Compile  1me  (Sta1c  Time)  

 Declara1ons  (programmer  ac1on)  

 Variable  names  

 variable  types  

 program  statement  structure  

 Compiler  ac1on  

 Rela1ve  loca1on  of  data  objects  

 Linker  ac1ons  

 Rela1ve  loca1on  of  different  object  modules  

(3)

Binding  Time  

Binding  Time  

(4)

Binding  Time  

o  The  sum  operator  (+)  

 At  compila1on  1me  (depending  on  the  type  of  the  operands   because  of  overloading)  

o  If  x  is  declared  integer  +  means  one  thing   o  if  x  is  declared  real  means  something  else   o  +  can  also  be  overloaded  by  the  programmer.  

o  Example  (C++):  it  is  possible  to  specify  that  +  operates  on  strings:  

  string operator +(string& a, string& b) {   return a.append(b);

  }

Binding  Time  

Shape s= new Shape();

s.getArea();

// The compiler can resolve this method call statically.

(5)

Binding  Time  

public void MakeSomeFoo(object a) { // Things happen...

((Shape) a).getArea();

// You won't know if this works until runtime!}

Binding  Time:  discussion  

•  Many  of  the  most  important  and  subtle  differences  between   programming  languages  involve  differences  in  binding  1me  

•  The  trade  off  is  between  sta1c  analysis,  efficient  execu1on  and   flexibility  

•  The  language  comes  with  a  type  system.  The  compiler  assigns  a   type  expression  to  parts  of  the  source  program.  The  compiler   checks  that  the  type  usage  in  the  program  conforms  to  the  type   system  for  the  language.  

•  When  efficiency  is  a  considera1on  (Fortran,  C)  languages  are   designed  so  that  as  many  bindings  as  possible  are  performed   during  transla1on  

•  Where  flexibility  is  the  prime  determiner,  bindings  are  delayed   un1l  execu1on  1me  so  that  they  may  be  made  data  dependent  

(6)

Dynamic  Dispatch  

"   Dynamic  dispatch  allows  the  code  executed  when  a   message  is  sent  to  an  object    (o.m(x))  to  be  determined   by  run-­‐1me  values.    

"   interface  Shape  {  ...  void  draw()  {  ...  }  }    

class  Circle  extends  Shape  {  ...  void  draw()  {  ...  }  }     class  Square  extends  Shape  {  ...  void  draw()  {  ...  }  }  ...    

Shape  s  =  ...;  //could  be  a  circle  a  square,  or  something   else.    

s.draw();    

"   Invoking  s.draw()  could  run  the  code  for  any  of  the   methods  shown  in  the  program  (or  for  any  other  class   that  extends  Shape).    

"   Java,  all  methods  (except  for  sta1c  methods)  are   dispatched  dynamically.  In    

"   C++,  only  virtual  members  are  dispatched   dynamically.    

"   Note  that  dynamic  dispatch  is  not  the  same  as   overloading,  which  is  usually  resolved  using  the   sta1c  types  of  the  arguments  to  the  func1on   being  called.    

(7)

Objects  life1me  

Creation of an object

Destruction of an object Creation of a binding

Destruction of a binding Dangling reference

if these two times are interchanged

Program execution time Object lifetime Binding lifetime

Dangling  References  

Int * p = new int;

Int * q = new int;

// things happen on p and q delete p;

//Other things happens Use(q)

(8)

Dangling  references  

#include<stdio.h>

int *call();

void main(){

int*ptr;

ptr=call();

fflush(stdin);

printf("%d",*ptr);

}

int * call(){

int x=25;

++x;

return &x;

}

(9)

Storage  Management  

  Programming  languages  provide  three  storage   alloca1on  mechanisms  

o  Sta1c  

 Absolute  address  retained  troughout  program’s   execu1on  

o  Stack    

 Dynamic  alloca1on  with  calls&returns  

o  Heap    

 Allocated  and  de-­‐allocated  at  arbitrary  1me  

Sta1c  Alloca1on  

  Global  variables  

  Constants  

o  manifest,  declared  (parameter  variables  in  Fortran)  or   iden1fied  by  the  compiler  

  Variables  iden1fied  as  const  in  C  can  be  a  func1on   of  non  constants  and  therefore  cannot  be  sta1cally   allocated  

  Constant  tables  generated  by  the  compiler  for   debugging  and  other  purposes  

(10)

Sta1c  Alloca1on    

  In  the  absence  of  recursion,  all  variables  can  be   sta1cally  allocated  

  Also,  can  be  sta1cally  allocated:  

o  Arguments  and  return  values  (or  their  addresses).  

Alloca1on  can  be  in  processor  registers  rather  than  in   memory  

o  Temporaries    

o  Bookkeeping  informa1on  

 return  address  

 saved  registers  

 debugging  informa1on  

Sta1c  Alloca1on  

(11)

Stack-­‐based  Alloca1on  

  Needed  when  language  permits  recursion  

  Useful  in  languages  without  recursion  because  it  can  save   space  

  Each  subrou1ne  invoca1on  creates  a  frame  or  ac1va1on   record  

o  arguments  

o  return  address  

o  local  variables  

o  temporaries  

o  bookkeeping  informa1on  

  Stack  maintained  by  

o  calling  sequence  

o  prologue  

o  epilogue  

Stack-­‐based  Alloca1on  (Cont.)  

(12)

Una  funzione  ricorsiva  

int    Func      (    /*  in  */    int      a,      /*  in  */    int      b  )       {  

                       int    result;  

       if    (  b  ==  0  )                                            //    base  case                    result  =  0;    

   else        if    (  b  >  0  )                            //    first    general    case                    result  =  a  +    Func  (  a  ,  b  -­‐  1  )  )  ;      

   return    result;  

}      

23

         Run-­‐Time  Stack  Ac1va1on  Records

   

                                                                   x = Func(5, 2);// original call at instruction 100

24

FCTVAL ? result ? b 2 a 5 Return Address 100

original call at instruction 100 pushes on this record for Func(5,2)

(13)

         Run-­‐Time  Stack  Ac1va1on  Records

   

                                                                   x = Func(5, 2);// original call at instruction 100

25

FCTVAL ? result ? b 1 a 5 Return Address 50 FCTVAL ?

result 5+Func(5,1) = ? b 2

a 5 Return Address 100

record for Func(5,2) call in Func(5,2) code at instruction 50 pushes on this record for Func(5,1)

         Run-­‐Time  Stack  Ac1va1on  Records

   

                                                                   x = Func(5, 2);// original call at instruction 100

26

FCTVAL ? result ? b 0 a 5 Return Address 50 FCTVAL ?

result 5+Func(5,0) = ? b 1

a 5 Return Address 50 FCTVAL ?

result 5+Func(5,1) = ? b 2

a 5 Return Address 100

record for Func(5,2) record for Func(5,1) call in Func(5,1) code at instruction 50 pushes on this record for Func(5,0)

(14)

         Run-­‐Time  Stack  Ac1va1on  Records

   

                                                                   x = Func(5, 2);// original call at instruction 100

27

FCTVAL 0

result 0

b 0

a 5

Return Address 50

FCTVAL ? result 5+Func(5,0) = ? b 1

a 5

Return Address 50

FCTVAL ? result 5+Func(5,1) = ? b 2

a 5

Return Address 100

record for Func(5,0) is popped first with its FCTVAL record for Func(5,2) record for Func(5,1)

         Run-­‐Time  Stack  Ac1va1on  Records

                                                                       x = Func(5, 2);// original call at instruction 100

28 record for Func(5,2) record for Func(5,1) is popped next with its FCTVAL FCTVAL 5

result 5+Func(5,0) = 5+ 0 b 1

a 5

Return Address 50

FCTVAL ? result 5+Func(5,1) = ? b 2

a 5

Return Address 100

(15)

         Run-­‐Time  Stack  Ac1va1on  Records

   

                                                                   x = Func(5, 2);// original call at instruction 100

29

FCTVAL 10

result 5+Func(5,1) = 5+5 b 2

a 5 Return Address 100

record for Func(5,2) is popped last with its FCTVAL

Heap-­‐based  Alloca1on  

  Region  of  storage  in  which  blocks  of  memory  can  be   allocated  and  de-­‐allocated  at  arbitrary  1mes  

  Because  they  are  not  allocated  in  the  stack,  the   life1me  of  objects  allocated  in  the  heap  is  not   confined  to  the  subrou1ne  where  they  are  created  

o  They  can  be  assigned  to  parameters  (or  to  components  of   objects  accessed  via  pointers  by  parameters)  

o  They  can  be  returned  as  value  of  the  subrou1ne/func1on/

method  

(16)

Find  the  errors  in  this  code  

Heap-­‐based  Alloca1on  

  Several  strategies  to  manage  space  in  the  heap  

  Fragmenta1on  

o  Internal  fragmenta+on  when  space  allocated  is  larger   than  needed  

o  External  fragmenta+on  when  allocated  blocks  are   scahered  through  the  heap.  Total  space  available  might   be  more  than  requested,  but  no  block  has  the  needed   size  

(17)

Heap-­‐based  Alloca1on  

  One  approach  to  maintain  the  free  memory  space  is   to  use  a  free  list  

  Two  strategies  to  find  a  block  for  a  give  request  

o  First  fit:  use  first  block  in  the  list  large  enough  to  sa1sfy  the   request  

o  Best  fit:  search  the  list  to  find  the  smallest  block  that   sa1sfy  the  request  

  The  free  list  could  be  organized  as  an  array  of  free   lists  where  each  list  in  the  array  contain  blocks  of   the  same  size  

Cells  and  Liveness  

"   Cell  =  data  item  in  the  heap  

o  Cells  are  “pointed  to”  by  pointers  held  in  registers,   stack,  global/sta1c  memory,  or  in  other  heap  cells  

"   Roots:  registers,  stack  loca1ons,  global/sta1c   variables  

"   A  cell  is  live  if  its  address  is  held  in  a  root  or  held   by  another  live  cell  in  the  heap  

(18)

slide 35

Garbage  

"   Garbage  is  a  block  of  heap  memory  that  cannot   be  accessed  by  the  program  

o  An  allocated  block  of  heap  memory  does  not  have  a   reference  to  it  (cell  is  no  longer  “live”)  

"   Garbage  collec1on  (GC)  -­‐  automa1c  management   of  dynamically  allocated  storage  

o  Reclaim  unused  heap  blocks  for  later  use  by  program  

slide 36

Example  of  Garbage  

class  node  {    int  value;  

 node  next;  

}  

node  p,  q;  

p = new node();

q = new node();

q = p;

delete p;

(19)

slide 37

The  Perfect  Garbage  Collector  

"   No  visible  impact  on  program  execu1on  

"   Works  with  any  program  and  its  data  structures  

o  For  example,  handles  cyclic  data  structures  

"   Collects  garbage  (and  only  garbage)  cells  quickly  

o  Incremental;  can  meet  real-­‐1me  constraints  

"   Has  excellent  spa1al  locality  of  reference  

o  No  excessive  paging,  no  nega1ve  cache  effects  

"   Manages  the  heap  efficiently  

o  Always  sa1sfies  an  alloca1on  request  and  does  not   fragment  

slide 38

Reference  Coun1ng:  Example  

1 root

set

Heap space

2

1 1

1

1 2 1

(20)

slide 39

Reference  Coun1ng:  Cycles  

1 root

set

Heap space

1

1 1

1

1 2 1

Memory leak

slide 40

root set

Heap space

Mark-­‐Sweep  Example  (1)  

(21)

slide 41

root set

Heap space

Mark-­‐Sweep  Example  (2)  

slide 42

root set

Heap space

Mark-­‐Sweep  Example  (3)  

(22)

slide 43

root set

Heap space

Mark-­‐Sweep  Example  (4)  

Reset mark bit of marked cells

Free unmarked cells

slide 44

Genera1onal  Garbage  Collec1on  

"   Observa1on:  most  cells  that  die,  die  young  

o  Nested  scopes  are  entered  and  exited  more  

frequently,  so  temporary  objects  in  a  nested  scope   are  born  and  die  close  together  in  1me    

"   Divide  the  heap  into  genera1ons,  and  GC  the   younger  cells  more  frequently  

o  Amor1ze  the  cost  across  genera1ons  

(23)

slide 45

Young

Old root

set A

B

C D

E

F

G

Example  with  Immediate  “Aging”  (1)  

slide 46

Young

Old root

set

A

B

D

E

F

G

C

Example  with  Immediate  “Aging”  (2)  

(24)

slide 47

Youngest

Oldest To-space

From-space From-space

To-space root

set . . .

Middle generation(s)

Genera1ons  with  Semi-­‐Spaces  

SCOPE  

(25)

Variable  

  A  variable  is  a  loca+on  (AKA    reference)  that  can   be  associated  with  a  value.  

  Obtaining  the  value  associated  with  a  variable  is   called  dereferencing,  and  crea1ng  or  changing   the  associa1on  is  called  assignment.    

Seman1cs  of    

Programming  Languages  

(26)

Formal  Model  Graphical  

x y z 3.14

“abc”

s fun

Names Env

123 43.21

Store x

y z x s

fun “abc”

Scope  and  extent  

(27)

Typed  Variables  

  In  sta1cally-­‐typed  languages,  a  variable  also  has   a  type,  meaning  that  only  values  of  a  given  type   can  be  stored  in  it  

  In  dynamically-­‐typed  languages,  values,  not   variables,  have  types  

Scope  rules  

  The  region  of  the  program  in  which  a  binding  is   ac1ve  is  its  scope  

  Most  languages  today  are  lexically  scoped  

  Some  languages  (e.g.  Perl)  have  both  lexical  and   dynamic  scoping  

(28)

Sta1c  Scope  -­‐  Nested  Subrou1nes  

  In  most  languages  any  constant,  type,  variables   or  subrou1nes  declared  within  a  subrou1ne  are   not  visible  outside  the  subrou1ne  

  Closest  nested  scope  rule:  

 a  name  is  known  in  the  scope  in  which  it  is  declared   unless  it  is  hidden  by  another  declara1on  of  the   same  name  

Sta1c  Scope  -­‐  Nested  Subrou1nes  (2)  

procedure P1(A1: T1);

var X: real;

procedure P2(A2: T2);

procedure P3(A3: T3);

begin

(*body of P3 *) end;

begin

(* body of P2 *) end;

procedure P4(A4: T4);

function F1(A5: T5) : T6;

var X: integer;

begin

(* body of F1 *) end;

begin

(* body of P4 *) end;

begin

(* body of P1 *)

end;

(29)

Sta1c  Scope  -­‐  Nested  Subrou1nes  (3)  

  To  find  the  frames  of  surrounding  scopes  where   the  desired  data  is  a  sta1c  link  could  be  used  

func1on  A()    {  int  I;      

   func1on  B()  {    int  J;    

         func1on  C()  {    int  K;  

                 K=I+J;  B();  }            C();  }      //  body  of  B.  

   B();  }            //  body  of  A.  

A  calls  B  calls  C  calls            B  calls  C.  

(30)

Sta1c  Scope  -­‐  Nested  Subrou1nes  (4)  

Sta1c  Scope  -­‐  Nested  Subrou1nes  (5)  

ARB4

ARB1 ARB2 ARB3 { /* B1 */!

{ /* B2 */!

{ /* B3 */!

{ /* B4 */!

}!

}!

}!

}!

(31)

class  Outer  {    final  int  x;  

 class  Inner  {      //int  x;  

   void  foo()  {  x;  }    }  

 void  bar()  {  Inner  i  =  new  Inner();  

   int  x;  

   i.foo();  

 }   }  

GNU  MIPS  

(32)

gcc  MIPS  

gcc  x386  

sp fp

arg1 arg2 ...

argn

return addr old fp local m local m-1

...

local 1

(33)

Example  

Example:  invoca1on  

(34)

Example  

int  baz(int  x,  int  y)   {  

   char  buf[256];  

   {  

       int  z  =  y  +  1;  

       x  +=  z;  

   }  

   return  x  +  y;      

}  

(35)

Modules  

  Modulariza1on  depends  on  informa1on  hiding  

  Func1ons  and  subrou1nes  can  be  used  to  hide   informa1on.  However,  this  is  not  flexible  enough.  

  One  reason  is  that  persistent  data  is  usually   needed  to  create  abstrac1on.  This  can  be   addressed  in  some  cases  using  sta1cally   allocated  values  

Sta1c  Scope  -­‐  Modules  (Cont.)  

(36)

Sta1c  Scope  -­‐  Modules  (Cont.)  

  But  modulariza1on  oten  requires  a  variety  of   opera1ons  on  persistent  data.  

Sta1c  Scope  -­‐  Modules  (Cont.)    

  Objects  inside  a  module  are  visible  to  each  other  

  Objects  inside  can  be  hidden  explicitly  (using  a   keyword  like  private)  or  implicitly  (objects  are   only  visible  outside  if  they  are  exported)  

  In  some  language  objects  outside  need  to  be   imported  to  be  visible  within  the  module  

(37)

Sta1c  Scope  -­‐  Modules   Modula-­‐2  examples  

VAR a,b: CARDINAL;!

MODULE M;!

!IMPORT a; EXPORT w,x;!

!VAR u,v,w; CARDINAL;!

!MODULE N;!

! !IMPORT u; EXPORT x,y;!

! !VAR x,y,z: CARDINAL;!

! !(* x,u,y,z visible here *)!

!END N;!

!(* a,u,v,w,x,y visible here *)!

END M;!

(* a,b,w,x visible here *)!

(38)

Modules  as  types  

Dynamic  scope  

  In  early  Lisp  systems  variables  were  bound   dynamically  rather  than  sta1cally  

  In  a  language  with  dynamic  binding,  free  

variables  in  a  procedure  get  their  values  from  the   environment  in  which  the  procedure  is  called   rather  than  the  environment  in  which  the   procedure  is  defined  

(39)

Symbol  Tables  

  Symbol  tables  are  used  to  keep  track  of  scope  and   binding  informa1on  about  names.  

  The  symbol  table  is  searched  every  1me  a  name  is   encountered  in  the  source  text  

  Changes  occur  when  a  new  name  or  new   informa1on  about  a  name  is  discovered  

  The  abstract  syntax  tree  will  contain  pointers  to  the   symbol  table  rather  than  the  actual  names  used  for   objects  in  the  source  text  

Symbol  Tables  (Cont.)  

  Each  symbol  table  entry  contains    

o  the  symbol  name  

o  its  category  (scalar  variable,  array,  constant,  type,   procedure,  field  name,  parameter,  etc.)  

o  scope  number  

o  type  (a  pointer  to  another  symbol  table  entry)  

o  and  addi1onal,  category  specific  fields  (e.g.  rank  and  shape   for  arrays)  

  To  keep  symbol  table  records  uniform,  it  may  be   convenient  for  some  of  the  informa1on  about  a   name  to  be  kept  outside  the  table  entry,  with  only  a   pointer  to  this  informa1on  stored  in  the  entry  

(40)

Symbol  Tables  (Cont.)  

  The  symbol  table  may  contain  the  keywords  at   the  beginning  if  the  lexical  scanner  searches  the   symbol  table  for  each  name  

  Alterna1vely,  the  lexical  scanner  can  iden1fy   keywords  using  a  separate  table  or  by  crea1ng  a   separate  final  state  for  each  keyword  

Symbol  Tables  (Cont.)  

  One  of  the  important  issues  is  handling  sta1c  scope  

  A  simple  solu1on  is  to  create  a  symbol  table  for  each   scope  and  ahach  it  to  the  node  in  the  abstract  

syntax  tree  corresponding  to  the  scope  

  An  alter  na1ve  is  to  use  a  addi+onal  data  structure   to  keep  track  of  the  scope.  This  structure  would   resemble  a  stack:  

(41)

A C A

B additional

0 2

scope_marker

4 top

2 LL

symbol table

Symbol  Tables  (Cont.)  

  A  hash  table  can  be  added  to  the  previous  data   structure  to  accelerate  the  search.  

  Elements  with  the  same  name  are  linked  from  top   to  bohom.  

  Search  start  at  the  entry  of  the  hash  table  and   proceeds  through  the  linked  list  un1l  the  end  of  the   list  is  reached  (old_id)  or  un1l  the  link  list  refers   to  an  element  below  scope_marker(LL - 1) (new_id)  

(42)

Symbol  Tables  (Cont.)  

Symbol  Tables  

(43)

Symbol  Tables  (Cont.)  

Associa1on  Lists  and  Central  Reference  

Tables  

(44)

The  binding  of  referencing  environments  

ARP1 ARB1 ARB2 ARB3 ARP2 ARP3 P1()!

{ REAL X!

{ /* B1 */!

{ /* B2 */!

{ /* B3 */!

P2(P3)!

}!

! P3()!

! {!

!x!

! } ! }!

P2(PX)!

{ ! PX()!

}!

}!

}!

PX

Riferimenti

Documenti correlati

The catalyst used with the HTL-AP showed a serious deactivation: the conversion of the glycolic acid in the liquid phase decreased from 91% to 20%.. On the other hand, the test

ENHANCING THE TANNINS BIODEGRADATION WITH ASPERGILLUS TUBINGENSIS AND CHAETOMIUM SP.: COSUBSTRATES BATCH TESTS.. of Environmental and Civil Engineering, University or

Infatti, in FINUDA, si puoÁ ottenere una misura diretta della vita media degli ipernuclei dalla differenza tra l'istante in cui il  emesso all'atto della formazione colpisce il

In the present paper, we study the limiting behaviour of the number of new species to be observed from further sampling, conditional on observed data, assuming the observations

study, neonatal antibiotic exposure was associated with reduced weight and height gain in boys whilst antibiotic use later in infancy and childhood was associated with increased

In Native American literary production, Pine Ridge holds a very deep cultural importance as emblem of the Indians’ resistance, and paradoxically, as a representative image of

del Presidente della Repubblica 8 giugno 2001, n. 327, il progetto di fattibilità tecnica ed economica sostituisce il progetto preliminare di cui al comma 2 del

La proposta della Commissione nel quadro della Conferenza di Maastricht: l’idea di una protezione del cittadino da parte dell’Unione.. La tutela diplomatica