(YDOXDWLRQ RI D 7\SH,QIHUHQFH )UDPHZRUN IRU -DYD $SSOLFDWLRQV$QWRQLR 0DJQDJKL 6KXLFKL 6DNDL DQG +LGHKLNR 7DQDND,QIRUPDWLRQ 6FLHQFH 'HSDUWPHQW 7KH 8QLYHUVLW\ RI 7RN\R +RQJR %XQN\RNX 7RN\R  -DSDQ^PDJQDJKLVDNDLWDQDND`#PWOWXWRN\RDFMS,QWURGXFWLRQ
7KH SRSXODULW\ RI -DYD KDV LQFUHDVHG UHPDUNDEO\ RYHU WKH ODVW IHZ \HDUV DQG WKH XWLOL]DWLRQ RI -DYD

SURJUDPPLQJ ODQJXDJH KDV IORXULVKHG ERWK LQ DFDGHPLF DQG LQGXVWULDO SURMHFWV 7KH GHPDQG IRU KLJKSHUIRUPDQFH-DYD

DSSOLFDWLRQVLVKRZHYHUVWUHVVLQJ

WKH

QHFHVVLW\RIDSSURSULDWHFRPSLODWLRQ

WHFKQLTXHV DQG DJJUHVVLYH RSWLPL]DWLRQ SURFHGXUHV >0+@,Q WKLV SDSHU ZH LQWURGXFH D IUDPHZRUN WR HQKDQFH VWDWLF DQDO\VLV RI -DYD DSSOLFDWLRQV E\ H[SORLWDWLRQ
RI W\SHLQIHUHQFH >$ &&= 0L@ $QG ZH H[SHULPHQWDOO\ HYDOXDWH KRZ VXFK D IUDPHZRUN FDQ
EH XWLOL]HG WR LPSURYH LQWHUSURFHGXUDO DQDO\VLV IRU VRXUFH FRGH OHYHO RSWLPL]DWLRQV
2XU DSSURDFK LV UHODWHG WR WKH ZRUN RI >&&=@ ,Q >&&=@ WKH DXWKRUV SURSRVH D W\SHLQIHUHQFH
DOJRULWKP IRU (LIIHO DQG PHQWLRQ WKH SRVVLELOLW\ RI DSSO\LQJ LW WR WKH -DYD ODQJXDJH %XW WKH\ GR QRW
LGHQWLI\ OLPLWDWLRQV WR WKHLU GHILQLWLRQ RI OLYLQJ FODVVHV WKDW DULVH LQ WKH FDVH RI -DYD SURJUDPV ,QVWHDGWKH IUDPHZRUN ZH GHYHORS FRQVLVWV RI QHZ RSHUDWLYH GHILQLWLRQV WKDW DGGUHVV -DYDVSHFLILF VHPDQWLFIHDWXUHV ,Q SDUWLFXODU $SSOLFDWLRQ 7D[RQRP\ $7 DQG DSSOLFDWLRQ /LYLQJ &ODVVHV 6HW /&6 DUH NH\
FRQFHSWV WKDW OHDG XV WR SURSRVH D SUDFWLFDO W\SHLQIHUHQFH DOJRULWKP IRU -DYD DSSOLFDWLRQV EDVHG RQ/LYLQJ &ODVVHV $QDO\VLV /&$  ,Q DGGLWLRQ ZH WDNH DGYDQWDJH RI WKH E\WHFRGH EDVHG H[HFXWLRQPRGHO WKDW DOORZV E\WHFRGH ILOHV WR EH GHFRPSLOHG >-D@ 7KLV HQDEOHV XV WR LQYHVWLJDWH D QHZSHUVSHFWLYH IRU SHUIRUPLQJ PRUH DJJUHVVLYH DQDO\VLV ZKLFK ZH H[WHQG DOVR E\ GHFRPSLODWLRQ WR WKRVHSURJUDPV DYDLODEOH RQO\ LQ E\WHFRGH IRUPDW IRU LQVWDQFH WKLUGSDUW\ FODVV OLEUDULHV  +HQFH ZH
DFKLHYH D PRUH FRPSOHWH DQG SUHFLVH SURJUDP UHSUHVHQWDWLRQ ,Q WKH W\SLFDO FDVH RI FRPSLOHGODQJXDJHV VRXUFH OHYHO RSWLPL]HUV KDYH WR DVVXPH WKH ZRUVW FDVH K\SRWKHVLV ZKHQ SHUIRUPLQJ
LQWHUSURFHGXUDO DQDO\VLV LQ WKH FRUUHVSRQGHQFH RI OLEUDU\ URXWLQH LQYRFDWLRQV EHFDXVH RI VRXUFH FRGHXQDYDLODELOLW\,Q DGGLWLRQ WKLV SDSHU HYDOXDWHV WKH LPSDFW RI RXU W\SHLQIHUHQFH IUDPHZRUN /&$ RQ D
EHQFKPDUN VXLWH RI ILYH SURJUDPV /&$ LV HPSOR\HG WR RSWLPL]H FDOOJUDSK FRQVWUXFWLRQ 0RVWFRQVROLGDWHG FDOOJUDSK FRQVWUXFWLRQ WHFKQLTXHV >*''@ XWLOL]H LQWHUSURFHGXUDO GDWDIORZ DQDO\VLV
EXW ZH LQVWHDG LQYHVWLJDWH WKH SRVVLELOLW\ DQG FRQYHQLHQFH RI /&$ W\SHLQIHUHQFH &RPSDUHG WR GDWDIORZ DQDO\VLV /&$ KDV WKH DGYDQWDJH RI VLPSOLFLW\ \HW LW KDV DQ HIIHFWLYH LPSDFW RQ FDOOJUDSKRSWLPL]DWLRQV 2EWDLQHG UHVXOWV VKRZ WKDW /&$ SURGXFHV D ZRUWKZKLOH UHGXFWLRQ XS WR  LQ WKH
QXPEHU RI PHWKRGV FRQVWUXFWRUV LQ DSSOLFDWLRQ FDOOJUDSKV :H DOVR HYDOXDWH WKH HIILFLHQF\ RI /&$IRU HOLPLQDWLQJ ODWH ELQGLQJ LQ FRUUHVSRQGHQFH RI FDOOJUDSK FDOOVLWHV 2XU UHVXOWV VHHP HQFRXUDJLQJ/&$ UHYHDOV WKDW  RI ODWH ELQGLQJ RFFXUUHQFHV FDQ EH UHSODFHG E\ VWDWLF ELQGLQJV ,I ZH FRPSDUHWKH YDOXH ZH REWDLQHG  ZLWK WKH GDWD UHSRUWHG LQ >&&=@   /&$ DSSHDUV WR EH D PRUH
HIILFLHQW W\SHLQIHUHQFH PHWKRG([SRVLWLRQ LV RUJDQL]HG DV IROORZV )LUVW VHFWLRQ  WKH FRQFHSW RI $SSOLFDWLRQ 7D[RQRP\ $7 LV
LQWURGXFHG WR FRQYHQLHQWO\ UHSUHVHQW -DYD DSSOLFDWLRQV 6HFRQG ZH SURYLGH WKH GHILQLWLRQ RI $7 OLYLQJ
FODVVHV DQG WKH DOJRULWKP WR FRPSXWH WKHP IRU D JLYHQ -DYD DSSOLFDWLRQ VHFWLRQ   ,Q VHFWLRQ  ZH
RXWOLQH WKH W\SHLQIHUHQFH DOJRULWKP EDVHG RQ /LYLQJ &ODVVHV $QDO\VLV /&$  7KURXJK /&$ ZH VKRZWKDW LW LV SRVVLEOH WR HIIHFWLYHO\ UHILQH W\SH LQIRUPDWLRQ DERXW SURJUDP H[SUHVVLRQV VHFWLRQ  RIIHUV D
TXDQWLWDWLYH HYDOXDWLRQ RI RXU WHFKQLTXHV IRU WKH VSHFLILF FDVH RI FDOOJUDSK FRQVWUXFWLRQ $7 DQG /&$DUH XVHG WR RSWLPL]H FDOOJUDSKV RI ILYH UHDO -DYD DSSOLFDWLRQV 7KH XWLOL]DWLRQ RI /&$ SURGXFHV DQDSSUHFLDEOH LPSURYHPHQW LQ WKH TXDOLW\ RI FRQVWUXFWHG FDOOJUDSKV FRPSDUHG WR WKH FDVH ZKHUH /&$ LV
QRW XWLOL]HG 2XU FRQFOXVLRQV DUH WKHQ SUHVHQWHG LQ VHFWLRQ 

3URJUDP 5HSUHVHQWDWLRQ WKH $SSOLFDWLRQ 7D[RQRP\

7KH SURJUDP WR DQDO\]H LV UHSUHVHQWHG WKURXJK WKH$SSOLFDWLRQ 7D[RQRP\ $7  $7 VWDWLFDOO\JURXSV DOO FODVVHV LQWHUIDFHV WKDW DUH LQYROYHG E\ DQ\ SRVVLEOH H[HFXWLRQ RI WKH DSSOLFDWLRQ %DVHG RQ
LQSXW GDWD WR WKH DSSOLFDWLRQ WKH H[HFXWLRQ SDWK FDQ XWLOL]H RU JHQHUDWH LQVWDQFHV RI GLIIHUHQW FODVVHV$7 FROOHFWV LQ D FRQWUROIORZ LQVHQVLWLYH

PDQQHU DOO SRVVLEOH UHIHUHQFH W\SHV QHHGHG

GXULQJDSSOLFDWLRQ H[HFXWLRQ $ SDUWLDO RUGHU UHODWLRQVKLS LV QDWXUDOO\ GHILQHG RQ $7 HOHPHQWV EDVHG RQ

extends DQG implements NH\ZRUGV  )RU LQVWDQFH LI FODVV % H[WHQGV FODVV $ WKHQ % LV D

LQKHULWDQFH
VRQ RI $

7KURXJKRXW WKH UHPDLQGHU RI WKH SDSHU WKH WHUP ¦UHIHUHQFH W\SH§ ZLOO LGHQWLI\ EDVHG RQ WKH FRQWH[W
HLWKHU D FODVV RU DQ LQWHUIDFH
/HW WKH $7

JHQHUDWRU EH WKH FODVV RI WKH DSSOLFDWLRQ SURJUDP IURP ZKLFK H[HFXWLRQ EHJLQVQDPHO\ WKH FODVV FRQWDLQLQJ WKH main PHWKRG 8SRQ $7 LQVWDQWLDWLRQ WKH JHQHUDWRU LV DGGHG WR WKH
WD[RQRP\,QVHUWLQJ D UHIHUHQFH W\SH W LQ $7 WULJJHUV WKH IROORZLQJ DFWLRQV•W LV SDUVHG

PHWKRGVDIWHU GHFRPSLODWLRQ LI QHFHVVDU\DQG IURP LWV PHPEHUVILHOGV FRQVWUXFWRUV DQG

LQIRUPDWLRQ LV FROOHFWHG DERXW XWLOL]HG UHIHUHQFH W\SHV 6RPH RI WKH SULQFLSDO UHIHUHQFH

W\SH DWWULEXWHV RI W DUH VXPPDUL]HG E\ WKH IROORZLQJ VHWV

H[WHQGHGBUBW UHIHUHQFH W\SHV RI ZKLFK W LV D GLUHFW GHVFHQGDQWLPSOHPHQWHGBUBW UHIHUHQFH W\SHV LPSOHPHQWHG E\ WWKURZQBUBW UHIHUHQFH W\SHV WKURZQ DV H[FHSWLRQV E\ PHPEHU FRQVWUXFWRUV RU PHWKRGV RI WUHWXUQHGBUBW UHIHUHQFH W\SHV UHWXUQHG E\ PHPEHU PHWKRGV RI W

ILHOGBUBW GHFODUDWLRQ UHIHUHQFH W\SHV RI PHPEHU ILHOGV RI W



GHFODUDWLRQBUBW GHFODUDWLRQ UHIHUHQFH W\SHV RI YDULDEOHV GHFODUHG LQVLGHPHWKRGRU

FRQVWUXFWRU ERGLHV RU UHIHUHQFH W\SHV XVHG LQ FDVW H[SUHVVLRQV•

IRUPDOBUBW GHFODUDWLRQ UHIHUHQFH W\SHV RI IRUPDO SDUDPHWHUVVWDWLFBUBW UHIHUHQFH W\SHV RI ZKLFK DW OHDVW RQH VWDWLF PHPEHU LV UHIHUHQFHG LQ W

OLYLQJBUBW FODVVHV LQVWDQWLDWHG

new NH\ZRUG LQ W

UHIHUHQFH W\SHV H[WUDFWHG IURP W SRLQWV  WKURXJK  DUH LQVHUWHG LQ $7 WKRXJK WKH VDPH SURFHVV
SRVVLEO\ OHDGLQJ WR WKH LGHQWLILFDWLRQ RI IXUWKHU $7 HOHPHQWV

$7 FRQVWUXFWLRQ HQGV ZKHQ QR DGGLWLRQDO UHIHUHQFH W\SHV DUH FROOHFWHG
$7 QRGHV DUH GLVWLQJXLVKHG LQ FODVVQRGHV DQG LQWHUIDFHQRGHV ZKLFK UHVSHFWLYHO\ FRUUHVSRQG WRFODVVHV RU LQWHUIDFHV,Q VHFWLRQ  GLVFXVVLRQ ZLOO IRFXV RQ VWDWLFBUBW OLYLQJBUBW DQG DOVR RQ UHWXUQHGBQDWLYHBUBW 7KLVODWWHU $7 QRGH DWWULEXWH LV D VXEVHW RI UHWXUQHGBUBW DQG JURXSV UHIHUHQFH W\SHV UHWXUQHG E\ QDWLYH
PHPEHU PHWKRGV RI DQ $7 QRGH
6RPH UHVWULFWLRQV DSSO\ WR WKH $7 PRGHO IRU SURJUDP UHSUHVHQWDWLRQ $7 LV GHVLJQHG IRU WKRVH
FDVHV ZKHUH FODVVHV DUH QRW JHQHUDWHG G\QDPLFDOO\ GXULQJ SURJUDP H[HFXWLRQIRU LQVWDQFH E\

H[WHQGLQJ WKH DEVWUDFW FODVV MDYDODQJ&ODVV/RDGHU  6XFK D FLUFXPVWDQFH SRWHQWLDOO\ ZRXOG QRW DOORZWKH DERYH $7 FRQVWUXFWLRQ DOJRULWKP WR VWDWLFDOO\ LGHQWLI\ DOO QHFHVVDU\ UHIHUHQFH W\SHV$WWHQWLRQ PXVW EH SDLG DOVR WR QDWLYH PHWKRGV ZKRVH EHKDYLRU FDQ QRW EH GHVFULEHG SUHFLVHO\ $QDWLYH PHWKRG PLJKW DFWXDOO\ UHWXUQ DQ REMHFW WKDW LV DQ LQVWDQFH RI D VXEFODVV RI WKH UHWXUQ UHIHUHQFH
W\SH GHFODUHG LQ LWV VLJQDWXUH SUHYHQWLQJ VWDWLF GHWHFWLRQ RI WKH DFWXDOO\ LQYROYHG UHIHUHQFH W\SHV :H
UHTXLUH WKDW VXFK D FLUFXPVWDQFH GRHV QRW RFFXU 7KHUHIRUH D QDWLYH PHWKRG LV DVVXPHG WR UHWXUQ DQ
LQVWDQFH RI WKH VLJQDWXUH UHWXUQ UHIHUHQFH W\SH ZKLFK LV QHFHVVDULO\ D FODVV EHFDXVH LQWHUIDFHV FDQ QRWEH LQVWDQWLDWHG



$SSOLFDWLRQ /LYLQJ &ODVVHV:H DLP DW LQIHUULQJ WKH FODVVHV DQ H[SUHVVLRQ FDQ EH DQ LQVWDQFH RI DW UXQWLPH EDVHG RQ WKHDQDO\VLVRI

REMHFWVLQVWDQWLDWHGDSSOLFDWLRQ /LYLQJ &ODVVHV 6HW

E\

WKH

DSSOLFDWLRQ

7KXV

WKLV

VHFWLRQSUHOLPLQDU\

GHILQHV

WKH

/&6 

/HW &6 EH WKH VHW FRPSULVLQJ DOO $7 FODVVQRGHV ,I & LV DQ HOHPHQW RI &6 &D GHQRWHV DWWULEXWH D
RI WD[RQRP\ FODVVQRGH & ,Q WKH SUHYLRXV VHFWLRQ DPRQJ WD[RQRP\ QRGH DWWULEXWHV ZH GHILQHG
&ILHOGBUBW &VWDWLFBUBW &OLYLQJBUBW DQG &UHWXUQHGBQDWLYHBUBW/HW nestedRefComp(.) EH D IXQFWLRQ IURP &6 WR WKH SRZHU VHW RI &6 DQG VXFK WKDW LW DVVRFLDWHVWR D FODVV & LQ &6 WKH XQLRQ RI  WKH VHW RI GHFODUDWLRQ FODVV W\SHV RI ILHOGV LQ & DQG  WKH VHW RI ILHOGGHFODUDWLRQ FODVV W\SHV HQFRXQWHUHG E\ UHFXUVLYHO\ LQVSHFWLQJ HDFK FODVV UHIHUHQFH W\SH LQ &ILHOGBUBW)RU H[DPSOH LI FODVV $ FRQWDLQV D UHIHUHQFH PHPEHU ILHOG ZKRVH GHFODUDWLRQ W\SH LV FODVV % DQG LIFODVV % FRQWDLQV RQO\ SULPLWLYH PHPEHU ILHOGV WKHQ nestedRefComp $

%

^ `

7KH SUHFLVH GHILQLWLRQ RI nestedRefComp  FDQ EH VSHFLILHG DV IROORZV

nestedRefComp & = auxNestedRefComp &  ∅ZKHUH

auxNestedRefComp 

LV DQ DX[LOLDU\ IXQFWLRQ GHDOLQJ ZLWK GHILQLWLRQV RI FLUFXODU GDWD

VWUXFWXUHV
auxNestedRefComp & 6 = (&ILHOGBUBW ∩ &6) ∪  ∈ ∉7KH ILUVW DUJXPHQW RI auxNestedRefComp 
auxNestedRefComp &  6 ∪ &ILHOGBUBW 
∩



&

&ILHOGBUB W

&

6

&6

LV WKH $7 FODVVQRGH WR LQVSHFW ZKHUHDV WKH VHFRQG

DUJXPHQW LV D VHW FROOHFWLQJ UHIHUHQFH W\SHV DOUHDG\ PHW ZKLFK WKHUHIRUH PXVW EH GLVFDUGHG
/&6 LV GHILQHG DV IROORZV $ FODVV




$ FODVVWKDW FDXVHV& EHORQJV WR /&6 LII DW OHDVW RQH RI WKHVH FRQGLWLRQV LV YHULILHG

& LV WKH $7 JHQHUDWRU∃&©∈/&6 &∈&©OLYLQJBUBW∃&©∈/&6 &∈&©VWDWLFBUBW∃&©∈/&6 ∃&©©∈&©UHWXUQHGBQDWLYHBUBW &∈nestedRefComp &©©
& LV H[FOXGHG IURP /&6 LI DQG RQO\ LI WKHUH FDQ EH QR H[HFXWLRQ SDWK LQ WKH DSSOLFDWLRQ& WR EH LQVWDQWLDWHG &RQGLWLRQ  VWDWHV WKDW WKH $7 JHQHUDWRU LV DOZD\V FRQVLGHUHG DOLYLQJ FODVV 7KH JHQHUDWRU FRQWDLQV WKH main PHWKRG DQG WKH -90 FODVV ORDGHU JHQHUDWHV DQ LQVWDQFH

 DQG   D FODVV & LV LQ /&6 LI DQ&© ZKLFK LV DOUHDG\ LQ /&6 RU LI &© FRGH UHIHUHQFHV RQH RI &RI LW ZKHQ WKH DSSOLFDWLRQ LV VWDUWHG %HFDXVH RI FRQGLWLRQV
H[HPSODU RI LW LV LQVWDQWLDWHG E\ FODVVVWDWLF PHPEHUV ILHOGV RU PHWKRGV &© LV D OLYLQJ FODVV&©© ZH
FRQVHUYDWLYHO\ DVVXPH WKDW VXFK D PHWKRG FDQ EH LQYRNHG UHWXUQLQJ DQ LQVWDQFH RI &©© $OO QHVWHG
UHIHUHQFH FRPSRQHQWV RI &©© SRWHQWLDOO\ DUH JHQHUDWHG E\ WKH QDWLYH PHWKRG XSRQ FUHDWLRQ RI WKHUHWXUQHG REMHFW &©© 7KHUHIRUH DOO QHVWHG UHIHUHQFH W\SHV RI UHWXUQHG W\SHV E\ QDWLYH PHWKRGV EHORQJ WR&RQGLWLRQ  GHDOV ZLWK QDWLYH PHWKRGV DFFRUGLQJ WR SUHYLRXV DVVXPSWLRQV ,I

IRU WKH DSSOLFDWLRQ/&6 FRQGLWLRQ  

LW LV LQ /&6  DQG LI LW FRQWDLQV D QDWLYH PHWKRG UHWXUQLQJ UHIHUHQFH W\SH

7\SH,QIHUHQFH YLD /LYLQJ &ODVVHV $QDO\VLV$7 DQG /&6 DUH XVHG WR SHUIRUP W\SHLQIHUHQFH DQG WKXV WR UHILQH W\SH LQIRUPDWLRQ DVVRFLDWHGZLWK SURJUDP H[SUHVVLRQV $W UXQWLPH EHFDXVH RI SRO\PRUSKLVP DQ H[SUHVVLRQ FDQ EH DQ LQVWDQFH RI
DQ\ VXEFODVV RI WKH FODVV LQWHUIDFH WKDW UHSUHVHQWV WKH H[SUHVVLRQ VWDWLF W\SH 7KHUHIRUH SURJUDP FDOOVLWHV FDQ DFWXDOO\ GLVSDWFK PHVVDJHV WR VHYHUDO GLIIHUHQW PHWKRGV OLPLWLQJ LQWHUSURFHGXUDO DQDO\VLVHIIHFWLYHQHVV/LYLQJ &ODVVHV $QDO\VLV /&$ HPSOR\V LQIRUPDWLRQ DERXW WKRVH $7 FODVVHV WKDW PD\ EH

LQVWDQWLDWHG E\ WKH DSSOLFDWLRQ LQ RUGHU WR LPSURYH VWDWLF DQDO\VLV/HW type(.) EH D IXQFWLRQ WKDW UHWXUQV WKH XQLTXH VWDWLF W\SH DVVRFLDWHG ZLWK D SURJUDP H[SUHVVLRQ
type(.) LV GHILQHG SURSHUO\ DV -DYD LV VWULFWO\ VWDWLFDOO\ W\SHG /HW subTreeClasses(.) EH D IXQFWLRQWKDW PDSV HYHU\ $7 QRGHWRRQHFRUUHVSRQGHQFH

Q WR WKH VHW RI FODVVQRGHV RI WKH $7 VXEWUHH URRWHG LQ Q 7KHUH H[LVWV D RQHσ EHWZHHQ UHIHUHQFH W\SHV

LQ

WKH

DSSOLFDWLRQ

DQG

$7

QRGHV

+HQFH

subTreeClasses(.) FDQ EH GHVFULEHG HTXLYDOHQWO\ DV D IXQFWLRQ WKDW PDSV HYHU\ UHIHUHQFH W\SH W LQ WKHDSSOLFDWLRQ WR WKH VHW V RI DOO DSSOLFDWLRQ FODVV W\SHV WKDW VXEFODVV W 7KHUHIRUH LI WKH H[SUHVVLRQ H[SUKDV

VWDWLFUHIHUHQFH

subTreeClasses σ

W\SH

W



W type H[SU 
7KLV

UHSUHVHQWV

WKHQ
D

DW

H[SU

UXQWLPH

FRQVHUYDWLYH

LV

DQ

DVVXPSWLRQLQVWDQFH
,Q

RUGHU

RI

FODVVHVWR

UHILQH

LQ

W\SH

LQIRUPDWLRQ WKH IXQFWLRQ typeInference(.) LV LQWURGXFHG )RU HYHU\ DSSOLFDWLRQ UHIHUHQFH W\SH W

typeInference W

subTreeClasses σ W ∩/&6

$V /&6 LV D VXSHUVHW RI WKH FODVVHV WKDW DUH DFWXDOO\ LQVWDQWLDWHG WKURXJK DQ\ SURJUDP H[HFXWLRQ
SDWK WKH DERYH GHILQLWLRQ HQDEOHV WKH UHPRYDO RI DOO WKRVH FODVVHV WKDW EHORQJ WR WKH WD[RQRP\ EXW WKDWWKH DSSOLFDWLRQ GRHV QRW JHQHUDWH 7KHUHIRUH WKH YDOXH typeInference(type(H[SU)) LV HYDOXDWHG WRSHUIRUP W\SHLQIHUHQFH RQ DQ\ H[SUHVVLRQ H[SU 7KLV UHSUHVHQWV DQ HVWLPDWLRQ RI WKH FODVVHV H[SU FDQ
EH DQ LQVWDQFH RI ZKHQ WKH DSSOLFDWLRQ LV UXQ DQG W\SH LQIRUPDWLRQ UHILQHPHQW LV REWDLQHG DV

typeInference(type(H[SU))⊆subTreeClasses(σ type(H[SU))).
,Q >0@ WKURXJK D ZRUNLQJ H[DPSOH ZH GLVFXVV WKH GHYHORSHG FRQFHSWV RI $7 DQG W\SHLQIHUHQFH E\ /&$ $GGLWLRQDOO\ >0@ XWLOL]HV /&$ IRU FDOOJUDSK FRQVWUXFWLRQ RSWLPL]DWLRQ 7KLV LV
WKH VXEMHFW RI QH[W VHFWLRQ 7KH H[DPSOH ZH SURSRVH LQ >0@ GHSLFWV WKH W\SLFDO VLWXDWLRQ PHW LQ WKH
LPSOHPHQWDWLRQ RI WKH 9LVLWRU 3DWWHUQ >*+-@ DQG VKRZV KRZ /&$ HIIHFWLYHO\ LPSURYHV SURJUDPDQDO\VLV LQ VXFK D FDVH

([SHULPHQWDO (YDOXDWLRQ RI /&$7\SHLQIHUHQFH DOJRULWKPV IRU WKH UHILQHPHQW RI W\SH LQIRUPDWLRQ ILQG VHYHUDO IUXLWIXO DUHDV RIDSSOLFDWLRQ LQ WKH GHVLJQ DQG GHYHORSPHQW RI RSWLPL]LQJ FRPSLOHUV IRU 22 SURJUDPPLQJ ODQJXDJHV ,Q
WKH UHPDLQGHU RI WKH H[SRVLWLRQ ZH ZLOO IRFXV RQ WKH DSSOLFDWLRQ RI /&$ WR FDOOJUDSK FRQVWUXFWLRQ
EHFDXVH RI WKH LPSRUWDQFH RI FDOOJUDSKV IRU LQWHUSURFHGXUDO RSWLPL]LQJ FRPSLOHUV6XEVWDQWLDO LPSURYHPHQWV LQ DSSOLFDWLRQ SHUIRUPDQFH FDQ EH DFKLHYHG E\ DOORZLQJ RSWLPL]LQJ
FRPSLOHUV WR PDNH OHVV FRQVHUYDWLYH DVVXPSWLRQV DFURVV PHWKRG LQYRFDWLRQ ERXQGDULHV *LYHQ D
SURJUDP FDOOJUDSK UHSUHVHQWLQJ WKH

SRVVLEOH

FDOOHHV DW

HDFK

FDOOVLWH

LQWHUSURFHGXUDODQDO\VLVVXPPDUL]HV WKH HIIHFWV RI FDOOHHV DW HDFK PHWKRG HQWU\ %HFDXVH RI WKH -DYD G\QDPLF GLVSDWFKLQJ
PHFKDQLVP WKH VHW RI SRVVLEOH FDOOHHV DW HDFK FDOOVLWH LV GLIILFXOW WR HYDOXDWH SUHFLVHO\ DQG
QHFHVVLWDWHV WKH FRPSXWDWLRQ RI WKH SRVVLEOH FODVVHV RI PHVVDJH UHFHLYHUV RU WKH SRVVLEOH YDOXHVUHWXUQHG E\ LQYRNHG PHWKRGV *HQHUDOO\ PRUH FRQVROLGDWHG FDOOJUDSK FRQVWUXFWLRQ WHFKQLTXHV UHO\ RQ
LQWHUSURFHGXUDO GDWDIORZ DQDO\VLV ,Q WKLV VHFWLRQ ZH LQYHVWLJDWH DQ DOWHUQDWLYH DSSURDFK W\SHLQIHUHQFH WKURXJK /&$ LV DSSOLHG WR HQKDQFH FDOOJUDSK FRQVWUXFWLRQ
7KH FKRLFH RI EHQFKPDUNV LV D GHOLFDWH WDVN EHFDXVH RI WKH ODFN RI VWDQGDUG SURJUDPV WKDW DUHZLGHO\ DFFHSWHG E\ WKH -DYD FRPPXQLW\ 7KLV LV GXH RQ RQH KDQG WR WKH EURDG YDULHW\ RI
SURJUDPPLQJ FRQWH[WV WKDW -DYD $3,V DGGUHVV DQG RQ WKH RWKHU KDQG WR WKH UHODWLYH QHZQHVV RI WKHODQJXDJH :H FKRVH D VHW RI ILYH -DYD EHQFKPDUNV EDVHG RQ GLYHUVLILFDWLRQ RI DSSOLFDWLRQ DUHD DQGKWWSVHUYHU LV D VLPSOH +773VHUYHU DSSOLFDWLRQ  SUR[\ LV D JHQHULF
FDVFDGLQJ SUR[\ VHUYHU VXSSRUWLQJ VLQJOH VRFNHW QHWZRUN DSSOLFDWLRQV  5QJ3DFN LPSOHPHQWV D
UDQGRP QXPEHU JHQHUDWRU  GHQW LV D IRUPDWWHU RI -DYD VRXUFH FRGH  -DVPLQH LV D -DYD E\WHFRGH
FRPSOH[LW\ DV ZHOO 

GHFRPSLOHU 7DEOH  VXPPDUL]HV VRPH IHDWXUHV RI WKHVH SURJUDPV

1XPEHU 2I &ODVVHV$SSOLFDWLRQ






KWWSVHUYHU
SUR[\
5QJ3DFNGHQW-DVPLQH

1XPEHU 2I &RGH /LQHV




















Table 17KH QXPEHU RI FODVVHV LQ WDEOH  UHIHUV WR FODVVHV LQWHUIDFHV FRQWDLQHG LQ WKH DSSOLFDWLRQGLVWULEXWLRQ SDFNDJH 7KH QXPEHU RI FRGH OLQHV UHIHUV WR WKH DSSOLFDWLRQ VRXUFH FRGH LI LW LV DYDLODEOH
RWKHUZLVH LW LV REWDLQHG WKURXJK E\WHFRGH GHFRPSLODWLRQ $OO EHQFKPDUNV DUH SXUH -DYD DSSOLFDWLRQV)RU FRQYHQLHQFH EHQFKPDUNV ZLOO EH LGHQWLILHG E\ WKH VHTXHQWLDO QXPEHUV WKH\ KDYH LQ WDEOH 
400

360
350

300

Classes (Interfaces)

260
250

200

198

206

197

AT
LCS

191

150

113

111

116

106

100

50

0
1

2

3

4

5

Benchmarks

Figure 1

7KH H[SHULPHQW ZH FRQGXFWHG FDQ EH GHVFULEHG DV IROORZV )LUVWO\ $7 LV FRQVWUXFWHG DQG /&6 LV
HYDOXDWHG )LJXUH  VKRZV IRU HDFK EHQFKPDUN KRUL]RQWDO D[LV WKH FDUGLQDOLW\ YHUWLFDO D[LV RI $7
OLJKW JUD\ EDUV DQG /&6 GDUN JUD\ EDUV  $ SUHOLPLQDU\ REVHUYDWLRQ LV WKDW LQ EHQFKPDUNV  WR  WKH
QXPEHU RI WD[RQRP\ FODVVHV GRHV QRW YDU\ PXFK DERXW  HOHPHQWV  7KH QXPEHU RI FODVVHV
LQWHUIDFHV WKDW FRQVWLWXWH WKH DSSOLFDWLRQV LV UHODWLYHO\ VPDOO VHH WDEOH   DQG WKHUHIRUH WKH PDMRULW\
RI $7 QRGHV DUH UHSUHVHQWHG E\ FODVVHV LQWHUIDFHV EHORQJLQJ WR MGN $3,V %HQFKPDUN  UHSUHVHQWV DQ
H[FHSWLRQ  RI $7 QRGHV DUH FODVVHV LQWHUIDFHV WKDW EHORQJ WR WKH DSSOLFDWLRQ  $7 QRGHVRXW RI  $GGLWLRQDOO\ LW LV LQWHUHVWLQJ WR REVHUYH WKDW IRU DSSOLFDWLRQV    DQG  WKH SHUFHQWDJH RI OLYLQJ
FODVVHV LQ WKH $7 LV FRQVLGHUDEO\ VWDEOH UHVSHFWLYHO\    DQG  HYHQ LI WKH VL]HRI WKH DSSOLFDWLRQV LQ WHUPV RI OLQHV RI FRGH YDULHV LQ D VLJQLILFDQW PDQQHU IURP EHQFKPDUN  WR
EHQFKPDUN  %XW WKH ILIWK EHQFKPDUN VKRZV D GLIIHUHQW EHKDYLRU  RI WD[RQRP\ FODVVHV DUH
OLYLQJ FODVVHV 6XFK D KLJK SHUFHQWDJH RI OLYLQJ FODVVHV DIIHFWV /&$ SUHFLVLRQ DV WKH IROORZLQJ
H[SHULPHQWDO VWHSV FOHDUO\ SURYH
6XFFHVVLYHO\ H[SHULPHQWDWLRQ FRQVLVWV LQ HYDOXDWLQJ WKH HIIHFWLYHQHVV RI /&$ IRU FDOOJUDSKRSWLPL]DWLRQ +HQFH WZR DSSURDFKHV DUH XVHG ZKHQ SURGXFLQJ WKH DSSOLFDWLRQ FDOOJUDSKV ,Q WKH ILUVWSODFH IRU HDFK EHQFKPDUN WKH FDOOJUDSK LV SURGXFHG ZLWKRXW WKH H[SORLWDWLRQ RI W\SHLQIHUHQFH E\/&$ 7KHUHIRUH RQO\ $7 ZDV WDNHQ LQWR FRQVLGHUDWLRQ ZKHQ DQDO\]LQJ FDOOVLWHV 7KHQ WKH FDOOJUDSKLV FRPSXWHG DJDLQ EXW /&$ LV SHUIRUPHG LQ RUGHU WR JDWKHU PRUH SUHFLVH LQIRUPDWLRQ )LJXUH  DQG 
VKRZ WKH DFKLHYHG UHVXOWV
20

17.3

18

19.9
20

18.7

19.4

Call-Sites Reduction Percentage (%)

Methods (Constructors) Reduction Percentage (%

25

18.5

15

9.2

10

5

16

14.8
13.6

14

11.6

12

10

8

6

4
4

2

0

0
1

2

3

4

1

5

2

3

Benchmarks

45

Benchmarks

Figure 2

Figure 3)LJXUH  FRPSDUHV WKH QXPEHU RI PHWKRGV FRQVWUXFWRUV LQFOXGHG LQ WKH FRQVWUXFWHG FDOOJUDSKVZKHQ /&$ LV QRW HPSOR\HG DJDLQVW WKH FDVH ZKHQ /&$ LV FDUULHG RXW ,W VKRZV IRU HDFK EHQFKPDUNKRUL]RQWDO D[LV WKH UHGXFWLRQ SHUFHQWDJH YHUWLFDO D[LV RI WKH QXPEHU RI FDOOJUDSK PHWKRGVFRQVWUXFWRUV  /&$ SHUIRUPV HIILFLHQWO\ RQ EHQFKPDUNV  DQG  LW LV SRVVLEOH WR REWDLQ E\ /&$ D UHGXFWLRQ RI PHWKRGV FRQVWUXFWRUV LQ WKH FDOOJUDSK FRPSDUHG WR WKH FDVH ZKHQ /&$ LV QRWHPSOR\HG ,QVWHDG LQ WKH FDVH RI WKH ILIWK EHQFKPDUN /&$ SURGXFHV D  UHGXFWLRQ $V SUHYLRXVO\
REVHUYHG VXFK D EHQFKPDUN VKRZV D KLJKHU SHUFHQWDJH RI OLYLQJ FODVVHV  FRPSDUHG WR WKH
RWKHU VHOHFWHG DSSOLFDWLRQV)LJXUH  HYDOXDWHV /&$ LPSDFW RQ FDOOJUDSK HQKDQFHPHQW E\ FRQVLGHULQJ WKH UHGXFWLRQ LQ WKH
QXPEHU RI RYHUDOO FDOOVLWHV LQ WKH FDVH ZKHUH /&$ LV HPSOR\HG LQ FRPSDULVRQ WR ZKHUH LW LV QRWXWLOL]HG WKH FDOOVLWH UHGXFWLRQ SHUFHQWDJH LV UHSRUWHG DORQJ WKH YHUWLFDO D[LV  )LJXUH  VKRZV WKDW/&$ DFKLHYHV WKH KLJKHVW UHGXFWLRQ SHUFHQWDJH RQ WKH WKLUG EHQFKPDUN  UHGXFWLRQ  DQG WKDW WKH
ORZHVW UHGXFWLRQ YDOXH  LV DWWDLQHG LQ FRUUHVSRQGHQFH RI WKH ILIWK EHQFKPDUN
100

92.8

94.6

94.8

94.4
86.8

90

No-Late-Binding Call-Sites (%)

80

70

60

50

40

30

20

10

0
1

2

3

4

5

Benchmarks

Figure 4,Q ILJXUH  ZH SURYLGH DGGLWLRQDO H[SHULPHQWDO GDWD DERXW /&$ FROOHFWHG IURP EHQFKPDUNV DQG  7KH DSSOLFDWLRQ FDOOJUDSKV DUH H[SRVHG WR /&$ RSWLPL]DWLRQ 7KH GLDJUDP LQGLFDWHV WKH
SHUFHQWDJH YHUWLFDO D[LV RI FDOOVLWHV IRU ZKLFK UXQWLPH PHWKRG GLVSDWFK UHTXLUHV RQO\ RQH PHWKRG2XU /&$EDVHG DSSURDFK HQDEOHV FRPSLOHUV WR ORFDWH D UHPDUNDEOH DPRXQW RI ODWH ELQGLQJ RFFXUUHQFHVWKDW FDQ EH UHSODFHG E\ VWDWLF ELQGLQJV RQ WKH DYHUDJH  

&RQFOXVLRQV

7KH FRQWULEXWLRQV RI WKLV SDSHU FDQ EH VXPPDUL]HG DV IROORZV :H SURSRVHG ERWK D FRQFHSWXDOIUDPHZRUN DQG DQ LPSOHPHQWDWLRQ WR FDUU\ RXW W\SHLQIHUHQFH RQ -DYD SURJUDPV 8VLQJ WKLVIUDPHZRUN ZH HPSLULFDOO\ DFFHVVHG D VHW RI EHQFKPDUNV ZKLFK YDU\ LQ FRPSOH[LW\ DQG DUHD RIDSSOLFDWLRQ :H DSSOLHG /&$ W\SHLQIHUHQFH WR WKHVH EHQFKPDUNV LQ RUGHU WR RSWLPL]H WKHLU FDOOJUDSKV 2EWDLQHG UHVXOWV VKRZHG WKDW /&$ HQDEOHG VXEVWDQWLDO LPSURYHPHQWV LQ FDOOJUDSKFRQVWUXFWLRQ )RU WKRVH EHQFKPDUNV ZKHUH WKH SHUFHQWDJH RI DSSOLFDWLRQ OLYLQJ FODVVHV ZDVDSSUR[LPDWHO\  /&$ W\SHLQIHUHQFH OHG XV WR D VLJQLILFDQW UHGXFWLRQ  LQ WKH QXPEHU RI FDOOJUDSK FRQVWUXFWRUVPHWKRGV   DQG  LQ WKH QXPEHU RI ODWH ELQGLQJ RFFXUUHQFHV RYHU  +RZHYHU LQ RQH FDVH EHQFKPDUN   WKH SHUFHQWDJH RI OLYLQJ FODVVHV ZDV UHPDUNDEO\ KLJKHU PRUH
WKDQ  WKDQ LQ WKH RWKHU EHQFKPDUNV DQG FDOOJUDSK RSWLPL]DWLRQ DFKLHYHG E\ /&$ ZDV OLPLWHG
:H DLP WR LPSURYH /&$ SHUIRUPDQFH DOVR LQ VXFK VLWXDWLRQV E\ DGRSWLQJ D FRQWUROIORZ VHQVLWLYH
DOJRULWKP IRU HYDOXDWLRQ RI DSSOLFDWLRQ OLYLQJ FODVVHV:H H[SHFW WKDW /&$ W\SHLQIHUHQFH FDQ EH EHQHILFLDO QRW RQO\ WR FDOOJUDSK FRQVWUXFWLRQ EXW DOVRWR RWKHU HVVHQWLDO WDVNV SHUIRUPHG E\ RSWLPL]LQJ FRPSLOHUV 6SHFLILFDOO\ LQ RXU UHVHDUFK SURMHFW DERXWDXWRPDWLF SDUDOOHOL]DWLRQ RI -DYD SURJUDPV >067 067@ /&$ LV DGRSWHG QRW RQO\ WR HQKDQFH
SURJUDP FDOOJUDSKV EXW DOVR WR GHYHORS DQ LQWHUSURFHGXUDO DQDO\VLV IUDPHZRUN ZKHUH DOLDVLQJ
FRQIOLFWV DUH LQYHVWLJDWHG YLD 7\SH%DVHG $OLDVLQJ $QDO\VLV 7%$$ >'00 067@

5HIHUHQFHV>$@2 $JHVHQ 7KH &DUWHVLDQ 3URGXFW $OJRULWKP 6LPSOH DQG 3UHFLVH 7\SH ,QIHUHQFH RI
3DUDPHWULF 3RO\PRUSKLVP ,Q

WK
3URFHHGLQJV RI WKH  (XURSHDQ &RQIHUHQFH RQ 2EMHFW2ULHQWHG 3URJUDPPLQJ SS  >$68@$ $KR 5 6HWKL - 8OOPDQ &RPSLOHUV 3ULQFLSOHV 7HFKQLTXHV DQG 7RROV $GGLVRQ:HVOH\ >$@>%11@$ $SSHO 0RGHUQ &RPSLOHU ,PSOHPHQWDWLRQ LQ -DYD &DPEULGJH 8QLYHUVLW\ 3UHVV &

%URZQKLOO

$

3DUDOOHOL]DWLRQ ,Q

1LFRODX

6

1RYDFN

3URFHHGLQJV R&3RO\FKURQRSRXORV$FKLHYLQJ0XOWLOHYHO

I ,6+3& ,QWHUQDWLRQDO 6\PSRVLXP /HFWXUH 1RWHV LQ&RPSXWHU 6FLHQFH 6SULQJHU9HUODJ SS  >&&=@6 &ROOLQ' &ROQHW&RPSLOHU,Q

2

=HQGUD 7\SH

,QIHUHQFH

IRU

/DWH

%LQGLQJWKH

6PDOO(LIIHO

3URFHHGLQJV RI WKH -RLQW 0RGXODU /DQJXDJHV &RQIHUHQFH-0/&© 

/HFWXUH 1RWHV LQ &RPSXWHU 6FLHQFH 6SULQJHU9HUODJ SS  >'00@$ 'LZDQ . 0F.LQOH\ ( 0RVV 7\SH%DVHG $OLDV $QDO\VLV ,Q 3URFHHGLQJV RI WKH$&0 6,*3/$1 &RQIHUHQFH RQ 3URJUDPPLQJ /DQJXDJH 'HVLJQ DQG ,PSOHPHQWDWLRQ
SS  >*+-@( *DPPD 5 +HOP 5 -RKQVRQ - 9OLVVLGHV 'HVLJQ 3DWWHUQV $GGLVRQ:HVOH\ >*-@- *UDYHU 5 -RKQVRQ $ 7\SH 6\VWHP IRU 6PDOWDON ,Q 3URFHHGLQJV RI 323/ SS  

>*''@' *URYH*'H)RXZ-'HDQ& &KDPEHUV &DOO

*UDSK

&RQVWUXFWLRQ

LQ

2EMHFW

2ULHQWHG /DQJXDJHV ,Q 3URFHHGLQJV RI WKH $&0 2236/$ &RQIHUHQFH SS 

>+@

:

+ZX

,6&$,PSOHPHQWDWLRQV

DQG

7XWRULDO

-DYD

$SSOLFDWLRQV

90

WK

$UFKLWHFWXUH,QWHUQDWLRQDO

6RIWZDUH

6\PSRVLXP$UFKLWHFWXUHRQ&RPSXWHU$UFKLWHFWXUH 

-DVPLQH -DYD 'HFRPSLOHU

>-D@

¦

>0@

$ 0DJQDJKL§ KWWSPHPEHUVWULSRGFRPa6RXUFH7HFMDVPLQHKWP-DYD 1DWLYH7KUHDG 6XSSRUW RQ 6XQ (QWHUSULVH 6HUYHUV ,QWHUQDO 5HSRUW7KH 8QLYHUVLW\ RI 7RN\R -XQH 

>0@$ 0DJQDJKL

7KH 9LVLWRU 3DWWHUQ DQ $SSOLFDELOLW\ ([DPSOH RI /&$

HW DO,QWHUQDO

5HSRUW 7KH 8QLYHUVLW\ RI 7RN\R )HEUXDU\ >067@$ 0DJQDJKL 6 6DNDL + 7DQDND $Q ,QWHUSURFHGXUDO $SSURDFK IRU 2SWLPL]DWLRQV RI-DYD 3URJUDPV ,Q 3URFHHGLQJV RI ,QIRUPDWLRQ 3URFHVVLQJ 6RFLHW\ RI -DSDQ >067@

$ 0DJQDJKL 6 6DNDL + 7DQDND ,QWHUSURFHGXUDO $QDO\VLV IRU 3DUDOOHOL]DWLRQ RI-DYD

3URJUDPV&RPSXWDWLRQ

3URFHHGLQJV

,Q

RI

WKH

WK


 
>0+@,QWHUQDWLRQDO&RQIHUHQFH$ 0F0DQXV - +XQW 7KH 1HHG IRU 6SHHG ,Q

3DUDOOHO

6,*6 -DYD 5HSRUW

 9RO  1R  SS0D\ >0L@

RQ$&3&  /HFWXUH 1RWHV LQ &RPSXWHU 6FLHQFH 6SULQJHU9HUODJ SS 5 0LOQHU $ 7KHRU\ RI 7\SH 3RO\PRUSKLVP LQ 3URJUDPPLQJ ,Q

DQG 6\VWHPV 6FLHQFHV-RXUQDO RI &RPSXWHU SS  >5'@0

5LQDUG

3

'LQL]&RPPXWDWLYLW\

3DUDOOHOL]LQJ &RPSLOHUV ,Q$QDO\VLV$1HZ$QDO\VLV

9RO  1R  SS  1RYHPEHU >9@7HFKQLTXH

IRU$&0 7UDQVDFWLRQV RQ 3URJUDPPLQJ /DQJXDJHV DQG 6\VWHPV

% 9HQQHUV ,QVLGH WKH -DYD 9LUWXDO 0DFKLQH 0F*UDZ+LOO 