• Non ci sono risultati.

Principles  of  Programming  Languages

N/A
N/A
Protected

Academic year: 2022

Condividi "Principles  of  Programming  Languages"

Copied!
39
0
0

Testo completo

(1)

Principles  of  Programming  Languages  

h"p://www.di.unipi.it/~andrea/Dida2ca/PLP-­‐14/  

Prof.  Andrea  Corradini  

Department  of  Computer  Science,  Pisa  

•  Sta:c  versus  Dynamic  Checking  

•  Type  checking  

•  Type  conversion  and  coercion    

 

Lesson 14!

(2)

Recap  (last  lecture)  

•  Intermediate  code  genera:on  for:  

–  Mul:-­‐dimensional  arrays  

•  Transla:on  scheme  for  compu:ng  type  and  width  

•  Genera:on  of  three  address  statement  for  addressing   array  elements  

–  Transla:ng  logical  and  rela:onal  expressions  

–  Transla:ng  short-­‐circuit  Boolean  expressions  and  

flow-­‐of-­‐control  statements  with  backpatching  lists  

(3)

3  

Revisited  Structure  of    

Typical  Compiler    Front  End  

Lexical  analyzer  

Syntax-­‐directed   sta>c  checker  

Character  

stream   Token  

stream  

Intermediate   code  

Yacc  specifica:on   Intermediate  

Representa:on   specifica:on   Lex  specifica:on  

Syntax-­‐directed   translator  

Type  

checking   Code   genera:on  

(4)

Sta:c  versus  Dynamic  Checking  

•  Sta$c  checking:  the  compiler  enforces  

programming  language’s  sta$c  seman$cs  

–  Program  proper:es  that  can  be  checked  at   compile  :me  

–  Usually  not  expressible  with  CFG  

•  Dynamic  seman$cs:  checked  at  run  :me  

–  Compiler  generates  verifica:on  code  to  enforce  

programming  language’s  dynamic  seman:cs  

(5)

5  

Sta:c  Checking  

•  Typical  examples  of  sta:c  checking  are  

–  Type  checks  

–  Flow-­‐of-­‐control  checks   –  Uniqueness  checks  

–  Name-­‐related  checks  

(6)

Type  Checking,  Overloading,  Coercion,   Polymorphism  

class X { virtual int m(); } *x;

int op(int), op(float);

int f(float);

int a, c[10], d;

d = c + d; // FAIL

*d = a; // FAIL

a = op(d); // OK: static overloading (C++) a = f(d); // OK: coercion of d to float a = x->m(); // OK: dynamic binding (C++) vector<int> v; // OK: template instantiation

(7)

Flow-­‐of-­‐Control  Checks  

myfunc() { …

break; // ERROR }

myfunc() { …

switch (a) { case 0:

break; // OK case 1:

}

} myfunc()

{ …

while (n) { …

if (i>10)

break; // OK }

}

(8)

Uniqueness  Checks  

myfunc()

{ int i, j, i; // ERROR

}

cnufym(int a, int a) // ERROR { …

}

struct myrec { int name;

};

struct myrec // ERROR { int id;

(9)

Name-­‐Related  Checks  

LoopA: for (int i = 0; i < n; i++) { …

if (a[i] == 0)

break LoopB; // Java labeled break

}

(10)

One-­‐Pass  versus  Mul:-­‐Pass     Sta:c  Checking  

•  One-­‐pass  compiler:  sta:c  checking  in  C,  Pascal,  

Fortran,  and  many  other  languages  is  performed  in   one  pass  while  intermediate  code  is  generated  

–  Influences  design  of  a  language:  placement  constraints  

•  Declara:ons  

•  Func:on  prototypes

 

•  Mul$-­‐pass  compiler:  sta:c  checking  in  Ada,  Java,  and  

C#  is  performed  in  a  separate  phase,  some:mes  by  

traversing  a  syntax  tree  mul:ple  :mes  

(11)

11  

Towards  Type  Checking:  

Type  Expressions  

•  Type  expressions  are  used  in  declara:ons  and  type   casts  to  define  or  refer  to  a  type  

Type  ::=    int  |  bool  |  …  |  X  |  Tname  |pointer-­‐to(Type)  |        array(num,  Type)  |  record(Fields)  |  class(…)  |        Type  à  Type  |  Type  x  Type  

   

–  Primi$ve  types,  such  as  int  and  bool  

–  Type  constructors,  such  as  pointer-­‐to,  array-­‐of,  records   and  classes,  and  func:ons  

–  Type  names,  such  as  typedefs  in  C  and  named  types  in   Pascal,  refer  to  type  expressions  

 

(12)

Graph  Representa:ons  for     Type  Expressions  

•  Internal  compiler  representa:on,  built  during   parsing  

•  Example:  

int *f(char*,char*)

fun

args pointer

char

int pointer

char pointer

Tree forms

fun

args pointer

char

int pointer

DAGs

(13)

Cyclic  Graph  Representa:ons  

struct Node { int val;

struct Node *next;

};

struct val

pointer int

Internal  compiler  representa:on   of  the  Node  type:  cyclic  graph  

next

Source  program  

(14)

Equivalence  of  Type  Expressions  

•  Important  for  type  checking,  e.g.  in  assignments  

•  Two  different  no:ons:  name  equivalence  and   structural  equivalence    

–  Two  types  are  structurally  equivalent  if  

1.  They  are  the  same  basic  types,  or  

2.  They  have  the  form  TC(T1,…,  Tn)  and  TC(S1,  …,  Sn),  where  TC   is  a  type  constructor  and  Ti  is  structurally  equivalent  to  Si  for   all  1  <=  i  <=  n,  or  

3.  One  is  a  type  name  that  denotes  the  other.  

–  Two  types  are  name  equivalent  if  they  sa:sfy  1.  and  2.  

 

(15)

On  Name  Equivalence  

•  Each  type  name  is  a  dis:nct  type,  even  when   the  type  expressions  that  the  names  refer  to   are  the  same  

•  Types  are  iden:cal  only  if  names  match  

•  Used  by  Pascal  (inconsistently)  

type link = ^node;

var next : link;

last : link;

p : ^node;

q, r : ^node;

With  name  equivalence  in  Pascal:

p := next FAIL last := p FAIL

q := r OK

next := last OK

p := q FAIL !!!

(16)

Structural  Equivalence  of     Type  Expressions  

•  Two  types  are  the  same  if  they  are  structurally   iden$cal  

•  Used  in  C/C++,  Java,  C#  

struct

val next

int

pointer

struct val

int

pointer

=

pointer

next

(17)

Structural  Equivalence  of  Type   Expressions  (cont’d)  

•  Two  structurally  equivalent  type  expressions  have   the  same  pointer  address  when  construc:ng  graphs   by  (maximally)  sharing  nodes

struct val

int

pointer s

struct Node p

{ int val;

struct Node *next;

};

struct Node s, *p;

p = &s; // OK

*p = s; // OK

p = s; // ERROR next

&s

*p

(18)

Type  Systems  

•  A  type  system  defines  a  set  of  types  and  rules   to  assign  types  to  programming  language  

constructs  

•  Informal  type  system  rules,  for  example  “if  

both  operands  of  addi$on  are  of  type  integer,   then  the  result  is  of  type  integer”  

•  Formal  type  system  rules:  Post  systems  

(19)

Type  Rules  in  Post  System  Nota:on  

ρ ⊥   e1 : integer ρ ⊥   e2 : integer

ρ ⊥   e1 + e2 : integer

Type judgments e : τ

where e is an expression and τ is a type

Environment ρ maps objects v to types τ:

ρ(v) = τ ρ(v) = τ

ρ ⊥   v : τ

ρ ⊥   e : τ

ρ ⊥   v := e : void

ρ(v) = τ

(20)

Type  System  Example  

ρ ⊥   y + 2 : integer

ρ ⊥   x := y + 2 : void

Environment ρ is a set of 〈name, type〉 pairs, for example:

ρ = { 〈x,integer〉, 〈y,integer〉, 〈z,char〉, 〈1,integer〉, 〈2,integer〉 }

From ρ and rules we can check the validity of typed expressions:

The proof that x := y + 2 is typed correctly:

ρ(y) = integer

ρ ⊥   y : integer

ρ(x) = integer

ρ(2) = integer

ρ ⊥   2 : integer

(21)

A Simple Language Example

P  →  D  ;  S   D  →  D  ;  D                ⎟  id  :  T   T  →    boolean                ⎟  char                ⎟  integer  

             ⎟  array  [  num  ]  of  T                ⎟  ^  T  

S  →    id  :=  E                ⎟  if  E  then  S                ⎟  while  E  do  S                ⎟  S  ;  S  

E  →  true              ⎟  false                ⎟  literal                ⎟  num                ⎟  id  

           ⎟  E  and  E              ⎟  E  +  E              ⎟  E  [  E  ]              ⎟  E  ^  

Pascal-like pointer dereference operator Pointer to T

(22)

Simple Language Example:

Declarations

D  →  id  :  T        {  addtype(id.entry,  T.type)  }   T  →  boolean      {  T.type  :=  boolean  }  

T  →  char        {  T.type  :=  char  }   T  →  integer      {  T.type  :=  integer  }  

T  →  array  [  num  ]  of  T1  {  T.type  :=  array(1..num.val,  T1.type)  }   T  →  ^  T1        {  T.type  :=  pointer(T1)  

Parametric types:

type constructor

(23)

Simple  Language  Example:    

Checking  Statements  

S  →  id  :=  E  {  S.type  :=  (if  id.type  =  E.type  then  void  else  type_error)  }  

ρ ⊥   e : τ

ρ ⊥   v := e : void

ρ(v) = τ

Note:  the  type  of  id  is  determined  by  scope’s  environment:  

id.type  =  lookup(id.entry)  

(24)

Simple  Language  Example:  Checking   Statements  (cont’d)  

S  →  if  E  then  S1  {  S.type  :=  (if  E.type  =  boolean  then  S1.type                        else  type_error)  }    

ρ s : τ

ρ ⊥   if e then s : τ

ρ e : boolean ⊥   ⊥  

(25)

Simple  Language  Example:  Statements   (cont’d)  

S  →  while  E  do  S1  {  S.type  :=  (if  E.type  =  boolean  then  S1.type                        else  type_error)  }    

ρ s : τ

ρ ⊥   while e do s : τ

ρ e : boolean ⊥   ⊥  

(26)

Simple  Language  Example:  Checking   Statements  (cont’d)  

S  →  S1  ;  S2  {  S.type  :=  (if  S1.type  =  void  and  S2.type  =  void                      then  void  else  type_error)  }    

ρ s2 : void

ρ ⊥   s1 ; s2 : void

ρ s⊥   1 : void ⊥  

(27)

Simple  Language  Example:  Checking   Expressions  

E  →  true    {  E.type  =  boolean  }   E  →  false      {  E.type  =  boolean  }   E  →  literal    {  E.type  =  char  }  

E  →  num    {  E.type  =  integer  }    

E  →  id      {  E.type  =  lookup(id.entry)  }  

…  

ρ(v) = τ

ρ ⊥   v : τ

(28)

Simple  Language  Example:  Checking   Expressions  (cont’d)  

E  →  E1  +  E2  {  E.type  :=  (if  E1.type  =  integer  and  E2.type  =  integer                          then  integer  else  type_error)  }    

ρ ⊥   e1 : integer ρ ⊥   e2 : integer

ρ ⊥   e1 + e2 : integer

(29)

Simple  Language  Example:  Checking   Expressions  (cont’d)  

E  →  E1  and  E2  {  E.type  :=  (if  E1.type  =  boolean  and  E2.type  =  boolean                            then  boolean  else  type_error)  }    

ρ ⊥   e1 : boolean ρ ⊥   e2 : boolean

ρ ⊥   e1 and e2 : boolean

(30)

Simple  Language  Example:  Checking   Expressions  (cont’d)  

E  →  E1  [  E2  ]    {  E.type  :=  (if  E1.type  =  array(s,  t)  and  E2.type  =  integer                          then  t  else  type_error)  }    

ρ ⊥   e1 ⊥   e2 : integer

ρ ⊥   e1[e2] : τ

Note:  parameter  t  is  set  with  the  unifica:on  of   E1.type  =  array(s,  t)    

(31)

Simple  Language  Example:  Checking   Expressions  (cont’d)  

E  →  E1  ^  {  E.type  :=  (if  E1.type  =  pointer(t)  then  t                        else  type_error)  }    

ρ ⊥   e : pointer(τ)

ρ ⊥   e ^ : τ

Note:  parameter  t  is  set  with  the  unifica:on  of   E1.type  =  pointer(t)  

(32)

A  Simple  Language  Example:  Func:ons  

T  →    T  ->  T   E  →  E  (  E  )  

Example:

v : integer;

odd : integer -> boolean;

if odd(3) then v := 1;

Func:on  type  declara:on   Func:on  call  

(33)

Simple  Language  Example:    

Func:on  Declara:ons  

T  →  T1  ->  T2  {  T.type  :=  func$on(T1.type,  T2.type)  }  

Parametric type:

type constructor

(34)

Simple  Language  Example:  Checking   Func:on  Invoca:ons  

E  →  E1  (  E2  )    {  E.type  :=  (if  E1.type  =  func$on(s,  t)  and  E2.type  =  s                          then  t  else  type_error)  }    

ρ ⊥   e1 : function(σ, τ) ρ ⊥   e2 : σ

ρ ⊥   e1(e2) : τ

(35)

35  

Type  Conversion  and  Coercion  

•  Type  conversion  is  explicit,  for  example  using   type  casts  

•  Type  coercion  is  implicitly  performed  by  the  

compiler  to  generate  code  that  converts  types   of  values  at  run:me  (typically  to  narrow  or  

widen  a  type)  

•  Both  require  a  type  system  to  check  and  infer  

types  from  (sub)expressions  

(36)

•  Coercion  (implicit,  widening)  

–  No  loss  of  informa:on  (almost…)  

•  Cast  (explicit,  narrowing)    

–  Some  informa:on  can  be  lost  

•  Explicit  cast  is  always  allowed   when  coercion  is  

36  

ªñɴ؛ Z]1 ؛Q ƩoÓ؛ +!˙

¨ºz™Á ¨ºz™‚Á

¨ò ¥Ð

ˆ¨vµÁ ‰¨vµÁ

Óò

™¨§ŠÁ ™¨§ŠÁ

¥Ð

Ž§µÁ §µÁ

ò æò ¹ ¥ º Ð

´Œ¨­µÁ }Œv­Á }Œv­Á "# ³Œ¨­µÁòó z¿µ‚Á

åò

z¿µ‚Á

sàm”{~®”®‹àw°®Í~¼Á”°®Áà uà Vs¼¼°Ð”®‹àw°®Í~¼Á”°®Áà

֍ೊஸᎯᅼ੎ᗮνȪ͍Υвᗮ Ԧအྲྀᐕ੎ᅼበ೔အྲྀበᗮऔ੎ዏᑌ੎੎ྲྀᗮႼᅼೊ༌೔ዏೊᐕ੎ᗮዏᒹႼ੎በᗮ೔ྲྀᗮـࡐᐕࡐᗮ

ࡐᅼ੎ᗮเೊ༌ೊዏ੎়ᗮೊྲྀᗮ༌ࡐྲྀᒹᗮเࡐྲྀஸᎯࡐஸ੎በᗮዏအᗮᑌ೔়੎ྲྀೊྲྀஸᗮहအྲྀᐕ੎ᅼበ೔အྲྀበȪᗮ Ԧအྲྀᐕ੎ᅼበೊအྲྀᗮ೔በᗮ በࡐೊ়ᗮ ዏအᗮ औ੎ᗮ1" ( ˙ೊ૤ᗮዏఀ੎ᗮႼᅼအஸᅼࡐ༌༌੎ᅼᗮ༌Ꭿበዏᗮᑌᅼೊዏ੎ᗮበအ༌੎ዏఀೊྲྀஸᗮዏအᗮहࡐᎯበ੎ᗮዏఀ੎ᗮहအྲྀᐕ੎ᅼበ೔အྲྀȪᗮ իᒏႼเ೔ह೔ዏᗮहအྲྀᐕ੎ᅼበೊအྲྀበᗮࡐᅼ੎ᗮࡐเበအᗮहࡐเเ੎়ᗮ(Ƿ˙

ݫఀ੎ᗮበ੎༌ࡐྲྀዏ೔हᗮࡐहዏ೔အྲྀᗮ૤အᅼᗮहఀ੎हฆ೔ྲྀஸᗮAÛ˙ïᗮAg˙Ꭿበ੎በᗮዏᑌအᗮ૤Ꭿྲྀहዏೊအྲྀበпᗮ

¨ ؛21˙µϏ˙g ˙ዏࡐฆ੎በᗮዏᑌအᗮዏᒹႼ੎በᗮķ˙ࡐྲ়ྀᗮg˙ࡐྲ়ྀᗮᅼ੎ዏᎯᅼྲྀበᗮዏఀ੎ᗮ༌ࡐᒏ೔༌Ꭿ༌ᗮ$အᅼᗮเ੎ࡐበዏᗮ

ᎯႼႼ੎ᅼᗮऔအᎯྲ়ྀအ૤ᗮዏఀ੎ᗮዏᑌအᗮዏᒹႼ੎በᗮ೔ྲྀᗮዏఀ੎ᗮᑌ೔়੎ྲྀೊྲྀஸᗮఀ೔੎ᅼࡐᅼहఀᒹȺᗮ רዏᗮ ়੎हเࡐᅼ੎በᗮࡐྲྀᗮ

੎ᅼᅼအᅼᗮ೔૤ᗮ੎ೊዏఀ੎ᅼᗮµϏအᅼᗮg˙ೊበᗮྲྀအዏᗮೊྲྀᗮዏఀ੎ᗮఀ೔੎ᅼࡐᅼहఀᒹҤᗮ੎ȩஸȪÿᗮೊ૤ᗮ੎೔ዏఀ੎ᅼᗮዏᒹႼ੎ᗮೊበᗮࡐྲྀᗮࡐᅼᅼࡐᒹᗮ အᅼᗮࡐᗮႼအ೔ྲྀዏ੎ᅼᗮዏᒹႼ੎ɫᗮ

͍Ȫᗮc ˙9̓˙ஸ੎ྲྀ੎ᅼࡐዏ੎በᗮ ዏᒹႼ੎ᗮहအྲྀᐕ੎ᅼበೊအྲྀበᗮ೔૤ᗮྲྀ੎੎়੎়ᗮዏအᗮᑌ೔়੎ྲྀᗮࡐྲྀᗮࡐ়়ᅼ੎በበᗮ

အ૤ᗮዏᒹႼ੎ᗮ೔ྲྀዏအᗮࡐᗮᐕࡐเᎯ੎ᗮအ૤ᗮዏᒹႼ੎ᗮ̚ҿ רዏᗮᅼ੎ዏᎯᅼྲྀበᗮೊዏበ੎เ૤ᗮೊ૤ᗮࡐྲ়ྀᗮᑐ ࡐᅼ੎ᗮዏఀ੎ᗮ በࡐ༌੎ᗮዏᒹႼ੎ȩᗮ ۖዏఀ੎ᅼᑌೊበ੎ċᗮ ೊዏᗮ ஸ੎ྲྀ੎ᅼࡐዏ੎በᗮࡐྲྀᗮ೔ྲྀበዏᅼᎯहዏ೔အྲྀᗮዏအᗮ়အᗮዏఀ੎ᗮहအྲྀᐕ੎ᅼበ೔အྲྀᗮ ࡐྲ়ྀᗮ Ⴜเࡐह੎ᗮዏఀ੎ᗮ ᅼ੎በᎯเዏᗮ ೔ྲྀᗮ ࡐᗮ ዏ੎༌Ⴜအᅼࡐᅼᒹᗮ˙ᑌఀೊहఀᗮ೔በᗮ ᅼ੎ዏᎯᅼྲྀ੎়ᗮ ࡐበᗮ ዏఀ੎ᗮᅼ੎በᎯเዏȪᗮ ۻበ੎Ꭿ়အहအ়੎ᗮ૤အᅼᗮc ˙ࡐበበᎯ༌ೊྲྀஸᗮዏఀࡐዏᗮዏఀ੎ᗮအྲྀเᒹᗮዏᒹႼ੎በᗮࡐᅼ੎ᗮ %˙ࡐྲ়ྀᗮƮ˙

ࡐႼႼ੎ࡐᅼበᗮ೔ྲྀᗮ֍೔ஸɋᗮνȪ͍νȪᗮ

_˙c _˙" . Š6"˙˙ Š6"˙

ɼ˙Ò˙ U)#Uɼij̓

؛

ɼɼ˙Ò˙ %˙ɼҿÒ˙Ʈ ˙ ÷˙

ŝ—õŜ̓ ҿ 'ɼŠ2"òģ˙

˜˚|Nŝ—õŜ̓eÒe˙H fœ )RHɼ) ȶ̓

U)#Uɼ̇—õŜȷ̓

؛ɼ UU ɠpɼ

Example:  Type  Coercion  and  Cast  in  Java     among  numerical  types  

64   32   64   32   16  

8  

(37)

Handling  coercion  during  transla:on  

Transla:on  of  sum  without  type  coercion:  

E  →  E1  +  E2    {    E.place  :=  newtemp();  

               gen(E.place  ‘:=’ E1.place  ‘+’ E2.place)  }    

With  type  coercion:  

E  →  E1  +  E2    {    E.  type  =  max(E1.type,E2.type);  

         a1  =  widen(E1.addr,  E1.type,  E.type)  ;              a2  =  widen(E2.addr,  E2.type,  E.type);  

         E.addr  =  new  Temp();    

         gen(E.addr  '='  a1  '+'  a2);  }     where:  

•  max(T1,T2)  returns  the  least  upper  bound  of  T1  and  T2  in  the   widening  hierarchy  

•  widen(addr,  T1,  T2)  generate  the  statement  that  copies  the  value  of   type  T1  in  addr  to  a  new  temporary,  cas:ng  it  to  T2    

37  

(38)

Pseudocode  for  widen  

Addr widen(Addr a, Type t, Type w){

temp = new Temp();

if(t = w) return a; //no coercion needed elseif(t = integer and w = float){

gen(temp '=' '(float)' a);

elseif(t = integer and w = double){

gen(temp '=' '(double)' a);

elseif ...

else error;

return temp; } }

(39)

Type  Inference  and     Polymorphic  Func:ons  

•  Languages  like  ML  are  strongly  typed,  but  declara:on  of  type   is  not  mandatory  

•  Type  checking  includes  a  Type  Inference  algorithm  to  assign   types  to  expressions  

•  Type  Inference  is  very  interes:ng  in  presence  of  polymorphic   types,  which  are  type  expressions  with  variables  

For  example,  consider  the  list  length  func:on  in  ML:  

 fun  length(x)  =  if  null(x)  then  0  else  length(tl(x))  +  1  

–  length(["sun",  "mon",  "tue"])  +  length([10,9,8,7])    returns  7  

•  What  is  its  type?  

 

Riferimenti

Documenti correlati

•  An NFA accepts an input string x (over Σ ) if and only if there is some path with edges labeled with symbols from x in sequence from the start state to some.. accepting state

–  Transla=ng short-circuit Boolean expressions and flow-of- control statements with backpatching lists.. How does the code

special end symbol # to make accepting states important: the new expression is r#. •  Construct a syntax tree

•  A backward analysis propagates informa@on in the opposite direc@on in which the program flows. •  A forward analysis propagates informa@on in the same direc@on in which

/* Returns a stream consisting of the results of replacing each element of this stream with the contents of a mapped stream produced by applying the provided mapping function to

•  LALR parsing (Look-Ahead LR) merges two or more LR(1) state into one state to reduce table size. •  Less powerful

§  The types of variables and parameters are not declared, and cannot be inferred by the Python compiler.. So run-time type checks are needed to detect

•  Each state is a mul=way branch based on the next input character.. Puxng the