ëǕŏȀȀȩʶ C4ëɯ ŏȘƇ °ųǲƚżɾࡷ°ɟǞƚȘɾƚƇ ÚɟȩǃɟŏȒȒǞȘǃ
$ƚʿȩȘƇ ëǞȒɔȀƚ +ȩȒɔȩɯǞɾǞȩȘŏȀǞɾʿ

8FJYJO ;IBOHB BOE #SVOP $ E 4 0MJWFJSBBB 5IF 6OJWFSTJUZ PG )POH ,POH )POH ,POH $IJOBųɯɾɟŏżɾ $POUFYU &NCFEEFE %PNBJO4QFDJɯD -BOHVBHFT &%4-T BSF B DPNNPO BOE XJEFMZ VTFE BQQSPBDI
UP %4-T JO WBSJPVT MBOHVBHFT JODMVEJOH )BTLFMM BOE 4DBMB 5IFSF BSF UXP NBJO JNQMFNFOUBUJPO UFDIOJRVFT
GPS &%4-T TIBMMPX FNCFEEJOHT BOE EFFQ FNCFEEJOHT*ORVJSZ 4IBMMPX FNCFEEJOHT BSF RVJUF TJNQMF CVU UIFZ IBWF CFFO DSJUJDJ[FE JO UIF QBTU GPS CFJOH RVJUF
MJNJUFE JO UFSNT PG NPEVMBSJUZ BOE SFVTF *O QBSUJDVMBS JU JT PGUFO BSHVFE UIBU TVQQPSUJOH NVMUJQMF %4- JOUFSQSFUBUJPOT JO TIBMMPX FNCFEEJOHT JT EJɱDVMU"QQSPBDI 5IJT QBQFS BSHVFT UIBU TIBMMPX &%4-T BOE 0CKFDU0SJFOUFE 1SPHSBNNJOH 001 BSF DMPTFMZ SFMBUFE (JCCPOT BOE 8V BMSFBEZ EJTDVTTFE UIF SFMBUJPOTIJQ CFUXFFO TIBMMPX &%4-T BOE QSPDFEVSBM BCTUSBDUJPOXIJMF $PPL EJTDVTTFE UIF DPOOFDUJPO CFUXFFO QSPDFEVSBM BCTUSBDUJPO BOE 001 8F NBLF UIF USBOTJUJWF TUFQJO UIJT QBQFS CZ DPOOFDUJOH TIBMMPX &%4-T EJSFDUMZ UP 001 WJB QSPDFEVSBM BCTUSBDUJPO 5IF LOPXMFEHF BCPVUUIJT SFMBUJPOTIJQ FOBCMFT VT UP JNQSPWF PO JNQMFNFOUBUJPO UFDIOJRVFT GPS &%4-T
,OPXMFEHF 5IJT QBQFS BSHVFT UIBU DPNNPO 001 NFDIBOJTNT JODMVEJOH JOIFSJUBODF TVCUZQJOH BOE UZQF
SFȸOFNFOU JODSFBTF UIF NPEVMBSJUZ BOE SFVTF PG TIBMMPX &%4-T XIFO DPNQBSFE UP DMBTTJDBM QSPDFEVSBM BC
TUSBDUJPO CZ FOBCMJOH B TJNQMF XBZ UP FYQSFTT NVMUJQMF QPTTJCMZ EFQFOEFOU JOUFSQSFUBUJPOT(SPVOEJOH 8F NBLF PVS BSHVNFOUT CZ VTJOH (JCCPOT BOE 8VƫT FYBNQMFT XIFSF QSPDFEVSBM BCTUSBDUJPOJT VTFE JO )BTLFMM UP NPEFM B TJNQMF TIBMMPX &%4- 8F SFDPEF UIBU &%4- JO 4DBMB BOE XJUI BO JNQSPWFE
00JOTQJSFE )BTLFMM FODPEJOH 8F GVSUIFS JMMVTUSBUF PVS BQQSPBDI XJUI B DBTF TUVEZ PO SFGBDUPSJOH B EFFQFYUFSOBM 42- RVFSZ QSPDFTTPS UP NBLF JU NPSF NPEVMBS TIBMMPX BOE FNCFEEFE*NQPSUBODF 5IJT XPSL JT JNQPSUBOU GPS UXP SFBTPOT 'JSTUMZ GSPN BO JOUFMMFDUVBM QPJOU PG WJFX UIJT XPSLFTUBCMJTIFT UIF DPOOFDUJPO CFUXFFO TIBMMPX FNCFEEJOHT BOE 001 XIJDI FOBCMFT B CFUUFS VOEFSTUBOEJOH
PG CPUI DPODFQUT 4FDPOEMZ UIJT XPSL JMMVTUSBUFT QSPHSBNNJOH UFDIOJRVFT UIBU DBO CF VTFE UP JNQSPWF UIFNPEVMBSJUZ BOE SFVTF PG TIBMMPX &%4-T+ ++ë ߨߦߧߨëȩǀɾʶŏɟƚ ŏȘƇ Ǟɾɯ ƚȘǃǞȘƚƚɟǞȘǃ म ŏȘǃʕŏǃƚ ǀƚŏɾʕɟƚɯࡔ 4ȩȒŏǞȘ ɯɔƚżǞ˙ż ȀŏȘǃʕŏǃƚɯࡔƚʿʶȩɟƇɯ ƚȒųƚƇƇƚƇ ƇȩȒŏǞȘࡷɯɔƚżǞ˙ż ȀŏȘǃʕŏǃƚɯࡈ ɯǕŏȀȀȩʶ ƚȒųƚƇƇǞȘǃࡈ ȩųǲƚżɾࡷȩɟǞƚȘɾƚƇ ɔɟȩǃɟŏȒȒǞȘǃ

5IF "SU 4DJFODF BOE &OHJOFFSJOH PG 1SPHSBNNJOH
ëʕųȒǞɾɾƚƇëƚɔɾƚȒųƚɟ ߨ߯ࡈ ߨߦߧ߮ÚʕųȀǞɯǕƚƇ_ƚųɟʕŏɟʿ ߧࡈ ߨߦߧ̙߯Ύ͖ߧߦࡏߨߨߧ߫ߨࡕɔɟȩǃɟŏȒȒǞȘǃࡷǲȩʕɟȘŏȀࡏȩɟǃࡕߨߦߧ߯ࡕߩࡕߧߦ
h 8FJYJO ;IBOH BOE #SVOP $ E 4 0MJWFJSB
5IJT XPSL JT MJDFOTFE VOEFS B ƭ$$ #: ɌɈƮ MJDFOTF
*O 5IF "SU 4DJFODF BOE &OHJOFFSJOH PG 1SPHSBNNJOH WPM ɋ OP ɋ ɊɈɉɑ BSUJDMF ɉɈ Ɋɍ QBHFTëǕŏȀȀȩʶ C4ëɯ ŏȘƇ °ųǲƚżɾࡷ°ɟǞƚȘɾƚƇ ÚɟȩǃɟŏȒȒǞȘǃ

ߧvȘɾɟȩƇʕżɾǞȩȘ

4JODF )VEBLƫT TFNJOBM QBQFS <ɉɈ> PO FNCFEEFE EPNBJOTQFDJɯD MBOHVBHFT &%4-T
FYJTUJOH MBOHVBHFT IBWF CFFO VTFE UP EJSFDUMZ FODPEF %4-T 5XP DPNNPO BQQSPBDIFT
UP &%4-T BSF UIF TPDBMMFE TIBMMPX BOE EFFQ FNCFEEJOHT %FFQ FNCFEEJOHT FNQIBTJ[FB TZOUBYɯSTU BQQSPBDI UIF BCTUSBDU TZOUBY JT EFɯOFE ɯSTU VTJOH B EBUB UZQF BOEUIFO JOUFSQSFUBUJPOT PG UIF BCTUSBDU TZOUBY GPMMPX 5IF SPMF PG JOUFSQSFUBUJPOT JO EFFQFNCFEEJOHT JT UP NBQ TZOUBDUJD WBMVFT JOUP TFNBOUJD WBMVFT JO B TFNBOUJD EPNBJO
4IBMMPX FNCFEEJOHT FNQIBTJ[F B TFNBOUJDTɯSTU BQQSPBDI XIFSF B TFNBOUJD EPNBJOJT EFɯOFE ɯSTU *O UIF TIBMMPX BQQSPBDI UIF PQFSBUJPOT PG UIF &%4-T BSF JOUFSQSFUFEEJSFDUMZ JOUP UIF TFNBOUJD EPNBJO 5IFSFGPSF UIFSF JT OP EBUB UZQF SFQSFTFOUJOHVOJOUFSQSFUFE BCTUSBDU TZOUBY
5IF USBEFPɮT CFUXFFO TIBMMPX BOE EFFQ FNCFEEJOHT IBWF CFFO XJEFMZ EJTDVTTFE<ɊɈ ɉɉ> %FFQ FNCFEEJOHT FOBCMF USBOTGPSNBUJPOT PO UIF BCTUSBDU TZOUBY USFF "45
BOE NVMUJQMF JOUFSQSFUBUJPOT BSF FBTZ UP JNQMFNFOU 4IBMMPX FNCFEEJOHT FOGPSDFUIF QSPQFSUZ PG DPNQPTJUJPOBMJUZ CZ DPOTUSVDUJPO BOE BSF FBTJMZ FYUFOEFE XJUI OFX&%4- PQFSBUJPOT 4VDI EJTDVTTJPOT MFBE UP B HFOFSBMMZ BDDFQUFE CFMJFG UIBU JU JT IBSE UP
TVQQPSU NVMUJQMF JOUFSQSFUBUJPOT <ɊɈ> BOE "45 USBOTGPSNBUJPOT JO TIBMMPX FNCFEEJOHT$PNQPTJUJPOBMJUZ JT DPOTJEFSFE B TJHO PG HPPE MBOHVBHF EFTJHO BOE JU JT POF PG UIFIBMMNBSLT PG EFOPUBUJPOBM TFNBOUJDT $PNQPTJUJPOBMJUZ NFBOT UIBU B EFOPUBUJPO PSJOUFSQSFUBUJPO PG B MBOHVBHF JT DPOTUSVDUFE GSPN UIF EFOPUBUJPO PG JUT QBSUT $PNQPTJUJPOBMJUZ MFBET UP B NPEVMBS TFNBOUJDT XIFSF BEEJOH OFX MBOHVBHF DPOTUSVDUT EPFTOPU SFRVJSF DIBOHFT JO UIF TFNBOUJDT PG FYJTUJOH DPOTUSVDUT #FDBVTF DPNQPTJUJPOBMJUZPɮFST B HVJEFMJOF GPS HPPE MBOHVBHF EFTJHO &SXJH BOE 8BMLJOHTIBX <Ɏ> BSHVF UIBU B
TFNBOUJDTɯSTU BQQSPBDI UP &%4-T JT TVQFSJPS UP B TZOUBYɯSTU BQQSPBDI 4IBMMPX FNCFEEJOHT ɯU XFMM XJUI TVDI B TFNBOUJDTESJWFO BQQSPBDI /FWFSUIFMFTT UIF MJNJUBUJPOTPG TIBMMPX FNCFEEJOHT DPNQBSFE UP EFFQ FNCFEEJOHT DBO EFUFS UIFJS VTF5IJT QSPHSBNNJOH QFBSM TIPXT UIBU HJWFO BEFRVBUF MBOHVBHF TVQQPSU IBWJOH
NVMUJQMF NPEVMBS JOUFSQSFUBUJPOT JO TIBMMPX %4-T JT OPU POMZ QPTTJCMF CVU TJNQMF
5IFSFGPSF XF BJN UP EFCVOL UIF CFMJFG UIBU NVMUJQMF JOUFSQSFUBUJPOT BSF IBSE UP NPEFM
XJUI TIBMMPX FNCFEEJOHT 4FWFSBM QSFWJPVT BVUIPST <ɏ Ɏ> BMSFBEZ PCTFSWFE UIBU CZVTJOH QSPEVDUT BOE QSPKFDUJPOT NVMUJQMF JOUFSQSFUBUJPOT DBO CF TVQQPSUFE XJUI B
DVNCFSTPNF BOE PGUFO OPONPEVMBS FODPEJOH .PSFPWFS JU JT BMTP LOPXO UIBU NVMUJQMF JOUFSQSFUBUJPOT XJUIPVU EFQFOEFODJFT PO PUIFS JOUFSQSFUBUJPOT BSF NPEVMBSJ[FEFBTJMZ VTJOH WBSJBOUT $IVSDI FODPEJOHT <ɏ Ɋ ɉɍ> 8F TIPX UIBU B TPMVUJPO GPS NVMUJQMF JOUFSQSFUBUJPOT JODMVEJOH EFQFOEFODJFT JT FODPEBCMF OBUVSBMMZ XIFO UIF IPTUMBOHVBHF DPNCJOFT GVODUJPOBM GFBUVSFT XJUI DPNNPO 00 GFBUVSFT TVDI BT TVCUZQJOHJOIFSJUBODF BOE UZQFSFȸOFNFOU"U UIF DFOUFS PG UIJT QFBSM JT 3FZOPMETƫ <ɉɏ> JEFB PG QSPDFEVSBM BCTUSBDUJPO XIJDI
FOBCMFT VT UP SFMBUF TIBMMPX FNCFEEJOHT BOE 001 EJSFDUMZ 8JUI QSPDFEVSBM BCTUSBDUJPOEBUB JT DIBSBDUFSJ[FE CZ UIF PQFSBUJPOT UIBU BSF QFSGPSNFE PWFS JU 5IJT QFBSM CVJMETPO UXP JOEFQFOEFOUMZ PCTFSWFE DPOOFDUJPOT UP QSPDFEVSBM BCTUSBDUJPO(JCCPOT BOE 8V <ɏ>/ 1SPDFEVSBM "CTUSBDUJPO o
4IBMMPX &NCFEEJOHT oߧߦࡇ ߨ$PPL <Ɍ>/ 001ĦƚǞʾǞȘ ĻǕŏȘǃ ŏȘƇ $ɟʕȘȩ +ࡏ Ƈࡏ ëࡏ °ȀǞʲƚǞɟŏ

5IF ɯSTU DPOOFDUJPO JT CFUXFFO QSPDFEVSBM BCTUSBDUJPO BOE TIBMMPX FNCFEEJOHT "T(JCCPOT BOE 8V <ɏ> TUBUF ƭJU XBT QSPCBCMZ LOPXO UP 3FZOPMET XIP DPOUSBTUFE EFFQ FNCFEEJOHT ƪVTFS EFȸOFE UZQFTƫ BOE TIBMMPX ƪQSPDFEVSBM EBUB TUSVDUVSFTƫ Ʈ (JCCPOT BOE
8V OPUFE UIF DPOOFDUJPO CFUXFFO TIBMMPX FNCFEEJOHT BOE QSPDFEVSBM BCTUSBDUJPOTBMUIPVHI UIFZ EJE OPU HP JOUP NVDI EFUBJM 5IF TFDPOE DPOOFDUJPO JT UIF DPOOFDUJPOCFUXFFO 001 BOE QSPDFEVSBM BCTUSBDUJPO XIJDI XBT EJTDVTTFE JO EFQUI CZ $PPL <Ɍ>8F NBLF PVS BSHVNFOUT DPODSFUF VTJOH (JCCPOT BOE 8V <ɏ>ƫT FYBNQMFT XIFSF
QSPDFEVSBM BCTUSBDUJPO JT VTFE JO )BTLFMM UP NPEFM B TJNQMF TIBMMPX &%4- 8F SFDPEFUIBU &%4- JO 4DBMB VTJOH 8BOH BOE 0MJWFJSBƫT <Ɋɋ> FYUFOTJCMF JOUFSQSFUFS QBUUFSO XIJDIQSPWJEFT B TJNQMF TPMVUJPO UP UIF &YQSFTTJPO 1SPCMFN <ɊɊ> 5IF SFTVMUJOH 4DBMB WFSTJPOIBT NPEVMBSJUZ BEWBOUBHFT PWFS UIF )BTLFMM WFSTJPO EVF UP UIF VTF PG TVCUZQJOHJOIFSJUBODF BOE UZQFSFɯOFNFOU *O QBSUJDVMBS UIF 4DBMB DPEF DBO FBTJMZ FYQSFTTNPEVMBS JOUFSQSFUBUJPOT UIBU NBZ OPU POMZ EFQFOE PO UIFNTFMWFT CVU BMTP EFQFOE POPUIFS NPEVMBS JOUFSQSFUBUJPOT MFBEJOH UP PVS NPUUP CFZPOE TJNQMF DPNQPTJUJPOBMJUZ
8IJMF )BTLFMM EPFT OPU OBUJWFMZ TVQQPSU TVCUZQJOH JOIFSJUBODF BOE UZQFSFɯOFNFOUJUT QPXFSGVM BOE FYQSFTTJWF UZQF TZTUFN JT TVɱDJFOU UP FODPEF TJNJMBS GFBUVSFT 5IFSF
GPSF XF DBO QPSU CBDL UP )BTLFMM TPNF PG UIF JEFBT VTFE JO UIF 4DBMB TPMVUJPO VTJOHBO JNQSPWFE )BTLFMM FODPEJOH UIBU IBT TJNJMBS BOE TPNFUJNFT FWFO CFUUFS CFOF
ɯUT JO UFSNT PG NPEVMBSJUZ *O FTTFODF JO UIF )BTLFMM TPMVUJPO XF FODPEF B GPSN PG
TVCUZQJOH PO QBJST VTJOH UZQF DMBTTFT 5IJT JT VTFGVM UP BWPJE FYQMJDJU QSPKFDUJPOT UIBUDMVUUFS UIF PSJHJOBM )BTLFMM TPMVUJPO *OIFSJUBODF JT FODPEFE CZ FYQMJDJUMZ EFMFHBUJOHJOUFSQSFUBUJPOT VTJOH )BTLFMM TVQFSDMBTTFT 'JOBMMZ UZQFSFɯOFNFOU JT TJNVMBUFE VTJOHUIF TVCUZQJOH UZQFDMBTT UP JOUSPEVDF TVCUZQJOH DPOTUSBJOUT
8IJMF UIF UFDIOJRVFT BSF TUJMM DVNCFSTPNF GPS USBOTGPSNBUJPOT ZJFMEJOH FɱDJFOU
TIBMMPX &%4-T JT TUJMM QPTTJCMF WJB TUBHJOH <ɉɑ Ɋ> #Z SFNPWJOH UIF MJNJUBUJPO PG NVMUJQMF JOUFSQSFUBUJPOT XF FOMBSHF UIF BQQMJDBCJMJUZ PG TIBMMPX FNCFEEJOHT " DPODSFUF
FYBNQMF JT PVS DBTF TUVEZ XIJDI SFGBDUPST BO FYUFSOBM 42- RVFSZ QSPDFTTPS UIBUFNQMPZT EFFQ FNCFEEJOH UFDIOJRVFT <ɉɐ> JOUP B TIBMMPX &%4- 5IF SFGBDUPSFE JNQMF
NFOUBUJPO BMMPXT CPUI OFX QPTTJCMZ EFQFOEFOU JOUFSQSFUBUJPOT BOE OFX DPOTUSVDUT
UP CF JOUSPEVDFE NPEVMBSMZ XJUIPVU TBDSJɯDJOH QFSGPSNBODF 5IF DPNQMFUF DPEF GPS
BMM FYBNQMFT BOE DBTF TUVEZ JT BWBJMBCMF BU ǕɾɾɔɯࡇࡕࡕǃǞɾǕʕųࡏżȩȒࡕʶʾˌǕࡕɯǕŏȀȀȩʶࡷƇɯȀߨëǕŏȀȀȩʶ ȩųǲƚżɾࡷȩɟǞƚȘɾƚƇ ɔɟȩǃɟŏȒȒǞȘǃ

5IJT TFDUJPO TIPXT IPX 001 BOE TIBMMPX FNCFEEJOHT BSF SFMBUFE WJB QSPDFEVSBM
BCTUSBDUJPO 8F VTF UIF TBNF %4- QSFTFOUFE CZ (JCCPOT BOE 8V <ɏ> BT B SVOOJOHFYBNQMF 8F ɯSTU HJWF UIF PSJHJOBM TIBMMPX FNCFEEFE JNQMFNFOUBUJPO JO )BTLFMM BOE
SFXSJUF JU UPXBSET BO ƭ001 TUZMFƮ 5IFO USBOTMBUJOH UIF QSPHSBN JOUP B GVODUJPOBM
001 MBOHVBHF MJLF 4DBMB CFDPNFT TUSBJHIUGPSXBSEߨࡏߧ ë̐˨;χࡇ  4ë ǀȩɟ ɔŏɟŏȀȀƚȀ ɔɟƚ˙ʾ żǞɟżʕǞɾɯ

4ɵɳʀʅ <ɐ> JT B %4- GPS EFTDSJCJOH QBSBMMFM QSFɯY DJSDVJUT (JWFO BO BTTPDJBUJWF CJOBSZPQFSBUPS • UIF QSFɯY TVN PG B OPOFNQUZ TFRVFODF x1 , x2 , ..., xn JT x1 , x1 • x2 , ..., x1 •ߧߦࡇ ߩëǕŏȀȀȩʶ C4ëɯ ŏȘƇ °ųǲƚżɾࡷ°ɟǞƚȘɾƚƇ ÚɟȩǃɟŏȒȒǞȘǃhDJSDVJUi ::= ƪǞƇƫ hQPTJUJWFOVNCFSi] ƪǀŏȘƫ hQPTJUJWFOVNCFSi] hDJSDVJUi ƪųƚɯǞƇƚƫ hDJSDVJUi] hDJSDVJUi ƪŏųȩʲƚƫ hDJSDVJUi] ƪɯɾɟƚɾżǕƫ hQPTJUJWFOVNCFSTi hDJSDVJUi] ƪ࡫ƫ hDJSDVJUi ƪ࡬ƫ_Ǟǃʕɟƚ ߧ

5IF HSBNNBS PG 4ɵɳʀʅ

(ǀŏȘ 2 ųƚɯǞƇƚ ǀŏȘ 2) ŏųȩʲƚ(ɯɾɟƚɾżǕ 2 2 ǀŏȘ 2) ŏųȩʲƚ(ǞƇ 1 ųƚɯǞƇƚ ǀŏȘ 2 ųƚɯǞƇƚ ǞƇ 1)_Ǟǃʕɟƚ ߨ

5IF #SFOU,VOH DJSDVJU PG XJEUI Ɍ

x2 • ... • xn  4VDI DPNQVUBUJPO DBO CF QFSGPSNFE JO QBSBMMFM GPS B QBSBMMFM QSFɯY DJSDVJU
1BSBMMFM QSFɯY DJSDVJUT IBWF NBOZ BQQMJDBUJPOT JODMVEJOH CJOBSZ BEEJUJPO BOE TPSUJOHBMHPSJUINT 5IF HSBNNBS PG 4ɵɳʀʅ JT HJWFO JO 'JHVSF ɉ 4ɵɳʀʅ IBT ɯWF DPOTUSVDUTUXP QSJNJUJWFT id BOE fan BOE UISFF DPNCJOBUPST beside above BOE stretch  5IFJSNFBOJOHT BSF id n DPOUBJOT n QBSBMMFM XJSFT fan n IBT n QBSBMMFM XJSFT XJUI UIFMFGUNPTU XJSF DPOOFDUFE UP BMM PUIFS XJSFT GSPN UPQ UP CPUUPN c1 beside c2 KPJOT UXPDJSDVJUT c1 BOE c2 IPSJ[POUBMMZ c1 above c2 DPNCJOFT UXP DJSDVJUT PG UIF TBNF XJEUIWFSUJDBMMZ stretch ns c JOTFSUT XJSFT JOUP UIF DJSDVJU c TP UIBU UIF i th XJSF PG c JT TUSFUDIFE
UP B QPTJUJPO PG ns1 + ... + nsi SFTVMUJOH JO B OFX DJSDVJU PG XJEUI CZ TVNNJOH VQ ns
'JHVSF Ɋ WJTVBMJ[FT B DJSDVJU DPOTUSVDUFE VTJOH BMM UIFTF ɯWF DPOTUSVDUT 5IF TUSVDUVSFPG UIJT DJSDVJU JT FYQMBJOFE BT GPMMPXT 5IF XIPMF DJSDVJU JT WFSUJDBMMZ DPNQPTFE CZ UISFF
TVCDJSDVJUT UIF UPQ TVCDJSDVJU JT B UXP ɊfanT QVU TJEF CZ TJEF UIF NJEEMF TVCDJSDVJUJT B Ɋfan TUSFUDIFE CZ JOTFSUJOH B XJSF PO UIF MFGUIBOE TJEF PG JUT ɯSTU BOE TFDPOEXJSF UIF CPUUPN TVCDJSDVJU JT B Ɋfan JO UIF NJEEMF PG UXP ɉidTߨࡏߨ ëǕŏȀȀȩʶ ƚȒųƚƇƇǞȘǃɯ ŏȘƇ °°Ú

4IBMMPX FNCFEEJOHT EFɯOF B MBOHVBHF EJSFDUMZ CZ FODPEJOH JUT TFNBOUJDT VTJOHQSPDFEVSBM BCTUSBDUJPO *O UIF DBTF PG 4ɵɳʀʅ B TIBMMPX FNCFEEFE JNQMFNFOUBUJPO JO)BTLFMM DPOGPSNT UP UIF GPMMPXJOH UZQFT
type Circuit = ... Ʀ UIF PQFSBUJPOT XF XJTI UP TVQQPSU GPS DJSDVJUT
id:: Int ! Circuit
fan:: Int ! Circuit
beside:: Circuit ! Circuit ! Circuit
above:: Circuit ! Circuit ! Circuit
stretch:: [Int] ! Circuit ! Circuitߧߦࡇ ߪĦƚǞʾǞȘ ĻǕŏȘǃ ŏȘƇ $ɟʕȘȩ +ࡏ Ƈࡏ ëࡏ °ȀǞʲƚǞɟŏ

5IF UZQF Circuit SFQSFTFOUJOH UIF TFNBOUJD EPNBJO JT UP CF ɯMMFE XJUI B DPODSFUF UZQF
BDDPSEJOH UP UIF TFNBOUJDT &BDI DPOTUSVDU JT EFDMBSFE BT B GVODUJPO UIBU QSPEVDFTB Circuit 4VQQPTF UIBU UIF TFNBOUJDT PG 4ɵɳʀʅ DBMDVMBUFT UIF XJEUI PG B DJSDVJU 5IF
EFɯOJUJPOT BSFtype Circuit = Int
id n
=n
fan n
=n
beside c1 c2 = c1 + c2
above c1 c2 = c1
stretch ns c = sum ns'PS UIJT JOUFSQSFUBUJPO UIF )BTLFMM EPNBJO JT TJNQMZ Int 5IJT NFBOT UIBU XF XJMM HFU
UIF XJEUI JNNFEJBUFMZ BGUFS UIF DPOTUSVDUJPO PG B DJSDVJU /PUF UIBU UIF Int EPNBJO
GPS width JT B EFHFOFSBUF DBTF PG QSPDFEVSBM BCTUSBDUJPO Int DBO CF WJFXFE BT B OP
BSHVNFOU GVODUJPO *O )BTLFMM EVF UP MB[JOFTT Int JT B HPPE SFQSFTFOUBUJPO *O B
DBMMCZWBMVF MBOHVBHF B OPBSHVNFOU GVODUJPO () ! Int JT NPSF BQQSPQSJBUF UP EFBMDPSSFDUMZ XJUI QPUFOUJBM DPOUSPMɰPX MBOHVBHF DPOTUSVDUT/PX XF BSF BCMF UP DPOTUSVDU UIF DJSDVJU JO 'JHVSF Ɋ VTJOH UIFTF EFɯOJUJPOT> (fan 2 ‘beside‘ fan 2) ‘above‘ stretch [2, 2] (fan 2) ‘above‘ (id 1 ‘beside‘ fan 2 ‘beside‘ id 1)4÷ȩʶŏɟƇɯ °°Ú

"O JTPNPSQIJD FODPEJOH PG width JT HJWFO CFMPX XIFSF B SFDPSE XJUIPOF ɯFME DBQUVSFT UIF EPNBJO BOE JT EFDMBSFE BT B newtype
newtype Circuit1 = Circuit1 {width1 :: Int}id1 n
= Circuit1 {width1 = n}fan1 n= Circuit1 {width1 = n}beside1 c1 c2= Circuit1 {width1 = width1 c1 + width1 c2 }above1 c1 c2= Circuit1 {width1 = width1 c1 }stretch1 ns c
= Circuit1 {width1 = sum ns}

5IF JNQMFNFOUBUJPO JT TUJMM TIBMMPX CFDBVTF )BTLFMMƫT newtype EPFT OPU BEE BOZ
PQFSBUJPOBM CFIBWJPS UP UIF QSPHSBN )FODF UIF UXP QSPHSBNT BSF FɮFDUJWFMZ UIFTBNF )PXFWFS IBWJOH ɯFMET NBLFT UIF QSPHSBN MPPL NPSF MJLF BO 00 QSPHSBNÚȩɟɾǞȘǃ ɾȩ ëżŏȀŏ

*OEFFE XF DBO FBTJMZ USBOTMBUF UIF QSPHSBN GSPN )BTLFMM UP 4DBMBBT TIPXO JO 'JHVSF ɋ 5IF JEFB JT UP NBQ )BTLFMMƫT SFDPSE UZQFT JOUP BO PCKFDU JOUFSGBDF NPEFMFE BT B trait JO 4DBMB Circuit1 BOE )BTLFMMƫT ɯFME EFDMBSBUJPOT CFDPNF
NFUIPE EFDMBSBUJPOT 0CKFDU JOUFSGBDFT NBLF UIF DPOOFDUJPO UP QSPDFEVSBM BCTUSBDUJPODMFBS EBUB JT NPEFMFE CZ UIF PQFSBUJPOT UIBU DBO CF QFSGPSNFE PWFS JU &BDI DBTF JO
UIF TFNBOUJD GVODUJPO DPSSFTQPOET UP B DPODSFUF JNQMFNFOUBUJPO PG Circuit1 XIFSF
GVODUJPO QBSBNFUFST BSF DBQUVSFE BT JNNVUBCMF ɯFMET
5IJT JNQMFNFOUBUJPO JT FTTFOUJBMMZ IPX XF XPVME NPEFM 4ɵɳʀʅ XJUI BO 001 MBOHVBHF JO UIF ɯSTU QMBDF " NJOPS EJɮFSFODF JT UIF VTF PG USBJUT JOTUFBE PG DMBTTFT JO
JNQMFNFOUJOH Circuit1  "MUIPVHI B DMBTT EFɯOJUJPO MJLFߧߦࡇ ߫ëǕŏȀȀȩʶ C4ëɯ ŏȘƇ °ųǲƚżɾࡷ°ɟǞƚȘɾƚƇ ÚɟȩǃɟŏȒȒǞȘǃ

 PCKFDU JOUFSGBDF
trait Circuit1 {def width : Int} DPODSFUF JNQMFNFOUBUJPOT
trait Id1 extends Circuit1 {val n : Int
def width = n}
trait Fan1 extends Circuit1 {val n : Int
def width = n}

trait Beside1 extends Circuit1 {val c1 , c2 : Circuit1
def width = c1 .width + c2 .width}trait Above1 extends Circuit1 {val c1 , c2 : Circuit1
def width = c1 .width}trait Stretch1 extends Circuit1 {val ns : List[Int]; val c : Circuit1
def width = ns.sum}_Ǟǃʕɟƚ ߩ $JSDVJU JOUFSQSFUBUJPO JO 4DBMB

class Id1 (n : Int) extends Circuit1 {def width = n}

JT NPSF DPNNPO TPNF NPEVMBSJUZ PɮFSFE CZ UIF USBJU WFSTJPO FH NJYJO DPNQPTJUJPO JT MPTU 5P VTF UIJT 4DBMB JNQMFNFOUBUJPO JO B NBOOFS TJNJMBS UP UIF )BTLFMM
JNQMFNFOUBUJPO XF OFFE TPNF TNBSU DPOTUSVDUPST GPS DSFBUJOH PCKFDUT DPOWFOJFOUMZ
def id(x : Int)= new Id1
{val n = x}
def fan(x : Int)= new Fan1
{val n = x}
def beside(x : Circuit1 , y : Circuit1 ) = new Beside1 {val c1 = x; val c2 = y}def above(x : Circuit1 , y : Circuit1 ) = new Above1 {val c1 = x; val c2 = y}def stretch(x : Circuit1 , xs : Int⇤) = new Stretch1 {val ns = xs.toList; val c = x}

/PX XF BSF BCMF UP DPOTUSVDU UIF DJSDVJU TIPXO JO 'JHVSF Ɋ JO 4DBMB
val circuit = above(beside(fan(2), fan(2)),
above(stretch(fan(2), 2, 2),
beside(beside(id(1), fan(2)), id(1))))'JOBMMZ DBMMJOH circuit.width XJMM SFUVSO Ɍ BT FYQFDUFE"T UIJT FYBNQMF JMMVTUSBUFT TIBMMPX FNCFEEJOHT BOE TUSBJHIUGPSXBSE 00 QSPHSBNNJOH BSF DMPTFMZ SFMBUFE 5IF TZOUBY PG UIF 4DBMB DPEF JT OPU BT DPODJTF BT UIF )BTLFMMWFSTJPO EVF UP TPNF FYUSB WFSCPTJUZ DBVTFE CZ USBJU EFDMBSBUJPOT BOE TNBSU DPOTUSVDUPST/FWFSUIFMFTT UIF DPEF JT TUJMM RVJUF DPNQBDU BOE FMFHBOU BOE UIF 4DBMB JNQMFNFOUBUJPOIBT BEWBOUBHFT JO UFSNT PG NPEVMBSJUZ BT XF TIBMM TFF OFYUߩʕȀɾǞɔȀƚ ǞȘɾƚɟɔɟƚɾŏɾǞȩȘɯ ǞȘ ɯǕŏȀȀȩʶ ƚȒųƚƇƇǞȘǃɯ"O PGUFO TUBUFE MJNJUBUJPO PG TIBMMPX FNCFEEJOHT JT UIBU NVMUJQMF JOUFSQSFUBUJPOT BSF
EJɱDVMU (JCCPOT BOE 8V <ɏ> XPSL BSPVOE UIJT QSPCMFN CZ VTJOH UVQMFT )PXFWFSߧߦࡇ ߬ĦƚǞʾǞȘ ĻǕŏȘǃ ŏȘƇ $ɟʕȘȩ +ࡏ Ƈࡏ ëࡏ °ȀǞʲƚǞɟŏUIFJS FODPEJOH OFFET UP NPEJGZ UIF PSJHJOBM DPEF BOE UIVT JT OPONPEVMBS 5IJTTFDUJPO JMMVTUSBUFT IPX WBSJPVT UZQFT PG JOUFSQSFUBUJPOT DBO CF NPEVMBSMZ EFɯOFE VTJOH
TUBOEBSE 001 NFDIBOJTNT BOE DPNQBSFT UIF SFTVMU XJUI (JCCPOT BOE 8VƫT )BTLFMM
JNQMFNFOUBUJPOTߩࡏߧ ëǞȒɔȀƚ ȒʕȀɾǞɔȀƚ ǞȘɾƚɟɔɟƚɾŏɾǞȩȘɯ" TJOHMF JOUFSQSFUBUJPO NBZ OPU CF FOPVHI GPS SFBMJTUJD %4-T 'PS FYBNQMF CFTJEFT
width XF NBZ XBOU UP IBWF BOPUIFS JOUFSQSFUBUJPO UIBU DBMDVMBUFT UIF EFQUI PG B
DJSDVJU JO 4ɵɳʀʅ
ʕȀɾǞɔȀƚ ǞȘɾƚɟɔɟƚɾŏɾǞȩȘɯ ǞȘ mŏɯǺƚȀȀ)FSF JT (JCCPOT BOE 8V <ɏ>ƫT TPMVUJPO

type Circuit2 = (Int, Int)
id2 n
= (n, 0)fan2 n= (n, 1)
above2 c1 c2 = (width c1 , depth c1 + depth c2 )beside2 c1 c2 = (width c1 + width c2 , depth c1 ‘max‘ depth c2 )stretch2 ns c = (sum ns, depth c)width = fst
depth = snd" UVQMF JT VTFE UP BDDPNNPEBUF NVMUJQMF JOUFSQSFUBUJPOT BOE FBDI JOUFSQSFUBUJPO JT
EFɯOFE BT B QSPKFDUJPO PO UIF UVQMF )PXFWFS UIJT TPMVUJPO JT OPU NPEVMBS CFDBVTF
JU SFMJFT PO EFɯOJOH UIF UXP JOUFSQSFUBUJPOT width BOE depth TJNVMUBOFPVTMZ *U JT
OPU QPTTJCMF UP SFVTF UIF JOEFQFOEFOUMZ EFɯOFE width JOUFSQSFUBUJPO JO 4FDUJPO ɊɊ8IFOFWFS B OFX JOUFSQSFUBUJPO JT OFFEFE FH depth UIF PSJHJOBM DPEF IBT UP CFSFWJTFE UIF BSJUZ PG UIF UVQMF NVTU CF JODSFNFOUFE BOE UIF OFX JOUFSQSFUBUJPO IBT UP
CF BQQFOEFE UP FBDI DBTFʕȀɾǞɔȀƚ ǞȘɾƚɟɔɟƚɾŏɾǞȩȘɯ ǞȘ ëżŏȀŏ*O DPOUSBTU B 4DBMB TPMVUJPO BMMPXT OFX JOUFSQSFUBUJPOT UP CF JOUSPEVDFE JO B NPEVMBS XBZtrait Circuit2 extends Circuit1 {def depth : Int}  TVCUZQJOH
trait Id2 extends Id1 with Circuit2 {def depth = 0}
trait Fan2 extends Fan1 with Circuit2 {def depth = 1}
trait Above2 extends Above1 with Circuit2 { JOIFSJUBODF
override val c1 , c2 : Circuit2
 DPWBSJBOU UZQFSFɯOFNFOU
def depth = c1 .depth + c2 .depth}
trait Beside2 extends Beside1 with Circuit2 {override val c1 , c2 : Circuit2
def depth = Math.max (c1 .depth, c2 .depth)}
trait Stretch2 extends Stretch1 with Circuit2 {override val c : Circuit2ߧߦࡇ ߭ëǕŏȀȀȩʶ C4ëɯ ŏȘƇ °ųǲƚżɾࡷ°ɟǞƚȘɾƚƇ ÚɟȩǃɟŏȒȒǞȘǃ

}def depth = c.depth

5IF FODPEJOH SFMJFT PO UISFF 001 BCTUSBDUJPO NFDIBOJTNT JOIFSJUBODF TVCUZQJOHBOE UZQFSFȸOFNFOU 4QFDJɯDBMMZ Circuit2 JT B TVCUZQF PG Circuit1 XIJDI FYUFOET UIFTFNBOUJD EPNBJO XJUI B depth NFUIPE $PODSFUF DBTFT GPS JOTUBODF Above2 JNQMFNFOU
Circuit2 CZ JOIFSJUJOH Above1 BOE JNQMFNFOUJOH depth "MTP ɯFMET PG UZQF Circuit1
BSF DPWBSJBOUMZ SFɯOFE BT UZQF Circuit2 UP BMMPX depth JOWPDBUJPOT *NQPSUBOUMZ BMMEFɯOJUJPOT GPS width JO 4FDUJPO ɊɊ BSF NPEVMBSMZ SFVTFE IFSF
ߩࡏߨ 4ƚɔƚȘƇƚȘɾ ǞȘɾƚɟɔɟƚɾŏɾǞȩȘɯ%FQFOEFOU JOUFSQSFUBUJPOT BSF B HFOFSBMJ[BUJPO PG NVMUJQMF JOUFSQSFUBUJPOT " EFQFO
EFOU JOUFSQSFUBUJPO EPFT OPU POMZ EFQFOE PO JUTFMG CVU BMTP PO PUIFS JOUFSQSFUBUJPOTXIJDI HPFT CFZPOE TJNQMF DPNQPTJUJPOBM JOUFSQSFUBUJPOT "O JOTUBODF PG EFQFOEFOUJOUFSQSFUBUJPO JT wellSized XIJDI DIFDLT XIFUIFS B DJSDVJU JT DPOTUSVDUFE DPSSFDUMZ
5IF JOUFSQSFUBUJPO PG wellSized JT EFQFOEFOU CFDBVTF DPNCJOBUPST MJLF above VTF width
JO UIFJS EFɯOJUJPOT
4ƚɔƚȘƇƚȘɾ ǞȘɾƚɟɔɟƚɾŏɾǞȩȘɯ ǞȘ mŏɯǺƚȀȀ*O (JCCPOT BOE 8V )BTLFMMƫT TPMVUJPO EFQFO
EFOU JOUFSQSFUBUJPOT BSF BHBJO EFɯOFE XJUI UVQMFT JO B OPONPEVMBS XBZtype Circuit3 = (Int, Bool)id3 n= (n, True)
fan3 n= (n, True)
above3 c1 c2 = (width c1 , wellSized c1 ^ wellSized c2 ^ width c1 ⌘ width c2 )beside3 c1 c2 = (width c1 + width c2 , wellSized c1 ^ wellSized c2 )stretch3 ns c = (sum ns, wellSized c ^ length ns ⌘ width c)
wellSized = snd

XIFSF width JT DBMMFE JO UIF EFɯOJUJPO PG wellSized GPS above3 BOE stretch3 
4ƚɔƚȘƇƚȘɾ ǞȘɾƚɟɔɟƚɾŏɾǞȩȘɯ ǞȘ ëżŏȀŏ

0ODF BHBJO JU JT FBTZ UP NPEFM EFQFOEFOU JOUFSQSFUBUJPO XJUI B TJNQMF 00 BQQSPBDI
trait Circuit3 extends Circuit1 {def wellSized : Boolean}  EFQFOEFODZ EFDMBSBUJPO
trait Id3 extends Id1 with Circuit3 {def wellSized = true}
trait Fan3 extends Fan1 with Circuit3 {def wellSized = true}
trait Above3 extends Above1 with Circuit3 {override val c1 , c2 : Circuit3
def wellSized =c1 .wellSized ^ c2 .wellSized ^ c1 .width ⌘ c2 .width  EFQFOEFODZ VTBHF}
trait Beside3 extends Beside1 with Circuit3 {override val c1 , c2 : Circuit3
def wellSized = c1 .wellSized ^ c2 .wellSizedߧߦࡇ ߮ĦƚǞʾǞȘ ĻǕŏȘǃ ŏȘƇ $ɟʕȘȩ +ࡏ Ƈࡏ ëࡏ °ȀǞʲƚǞɟŏ

}trait Stretch3 extends Stretch1 with Circuit3 {override val c : Circuit3
def wellSized = c.wellSized ^ ns.length ⌘ c.width} EFQFOEFODZ VTBHF/PUF UIBU width BOE wellSized BSF EFɯOFE TFQBSBUFMZ &TTFOUJBMMZ JU JT TVɱDJFOU UPEFɯOF wellSized XIJMF LOPXJOH POMZ UIF TJHOBUVSF PG width JO UIF PCKFDU JOUFSGBDF *O
UIF EFɯOJUJPO PG Above3 GPS FYBNQMF JU JT QPTTJCMF OPU POMZ UP DBMM wellSized CVU BMTP
width
ߩࡏߩ +ȩȘɾƚʾɾࡷɯƚȘɯǞɾǞʲƚ ǞȘɾƚɟɔɟƚɾŏɾǞȩȘɯ*OUFSQSFUBUJPOT NBZ SFMZ PO TPNF DPOUFYU $POTJEFS BO JOUFSQSFUBUJPO UIBU TJNQMJɯFTUIF SFQSFTFOUBUJPO PG B DJSDVJU " DJSDVJU DBO CF EJWJEFE IPSJ[POUBMMZ JOUP MBZFST &BDIMBZFS DBO CF SFQSFTFOUFE BT B TFRVFODF PG QBJST (i, j) EFOPUJOH UIF DPOOFDUJPO GSPNXJSF i UP XJSF j  'PS JOTUBODF UIF DJSDVJU TIPXO JO 'JHVSF Ɋ IBT UIF GPMMPXJOH MBZPVU
[[(0, 1), (2, 3)], [(1, 3)], [(1, 2)]]

5IF DPNCJOBUPS stretch BOE beside XJMM DIBOHF UIF MBZPVU PG B DJSDVJU 'PS FYBNQMF JG
UXP DJSDVJUT BSF QVU TJEF CZ TJEF BMM UIF JOEJDFT PG UIF SJHIU DJSDVJU XJMM CF JODSFBTFE CZUIF XJEUI PG UIF MFGU DJSDVJU )FODF UIF JOUFSQSFUBUJPO layout JT BMTP EFQFOEFOU SFMZJOHPO JUTFMG BT XFMM BT width "O JOUVJUJWF JNQMFNFOUBUJPO PG layout QFSGPSNT UIFTF DIBOHFT
JNNFEJBUFMZ UP UIF BɮFDUFE DJSDVJU " NPSF FɱDJFOU JNQMFNFOUBUJPO BDDVNVMBUFTUIFTF DIBOHFT BOE BQQMJFT UIFN BMM BU PODF 5IFSFGPSF BO BDDVNVMBUJOH QBSBNFUFS JT
VTFE UP BDIJFWF UIJT HPBM XIJDI NBLFT layout DPOUFYUTFOTJUJWF+ȩȘɾƚʾɾࡷɯƚȘɯǞɾǞʲƚ ǞȘɾƚɟɔɟƚɾŏɾǞȩȘɯ ǞȘ mŏɯǺƚȀȀ

5IF GPMMPXJOH )BTLFMM DPEF JNQMFNFOUT

OPONPEVMBS layout
type Circuit4 = (Int, (Int ! Int) ! [[(Int, Int)]])id4 n= (n, f ! [ ])fan4 n= (n, f ! [[(f 0, f j) | j [1 . . n 1]]])
above4 c1 c2 = (width c1 , f ! layout c1 f ++ layout c2 f )beside4 c1 c2 = (width c1 + width c2 ,f ! lzw (++) (layout c1 f ) (layout c2 (f (width c1 +))))
stretch4 ns c = (sum ns, f ! layout c (f pred (scanl1 (+) ns!!)))lzw:: (a ! a ! a) ! [a] ! [a] ! [a]lzw f [ ] ys
= ys
lzw f xs [ ]= xs
lzw f (x : xs) (y : ys) = f x y : lzw f xs ys
layout = snd

5IF EPNBJO PG layout JT B GVODUJPO UZQF (Int ! Int) ! [[(Int, Int)]] XIJDI UBLFT B
USBOTGPSNBUJPO PO XJSFT BOE QSPEVDFT B MBZPVU "O BOPOZNPVT GVODUJPO JT IFODF EFɯOFE GPS FBDI DBTF XIFSF f JT UIF BDDVNVMBUJOH QBSBNFUFS /PUF UIBU f JT BDDVNVMBUFEߧߦࡇ ߯ëǕŏȀȀȩʶ C4ëɯ ŏȘƇ °ųǲƚżɾࡷ°ɟǞƚȘɾƚƇ ÚɟȩǃɟŏȒȒǞȘǃ

JO beside4 BOE stretch4 UISPVHI GVODUJPO DPNQPTJUJPO QSPQBHBUFE JO above4 BOE ɯOBMMZ
BQQMJFE UP XJSF DPOOFDUJPOT JO fan4  "O BVYJMJBSZ EFɯOJUJPO lzw TUBOET GPS ƭMPOH [JQXJUIƮ [JQT UXP MJTUT CZ BQQMZJOH UIF CJOBSZ PQFSBUPS UP FMFNFOUT PG UIF TBNF JOEFY
BOE BQQFOEJOH UIF SFNBJOJOH FMFNFOUT GSPN UIF MPOHFS MJTU UP UIF SFTVMUJOH MJTU #Z
DBMMJOH layout PO B DJSDVJU BOE TVQQMZJOH BO JEFOUJUZ GVODUJPO BT UIF JOJUJBM WBMVF PG UIFBDDVNVMBUJOH QBSBNFUFS XF XJMM HFU UIF MBZPVU+ȩȘɾƚʾɾࡷɯƚȘɯǞɾǞʲƚ ǞȘɾƚɟɔɟƚɾŏɾǞȩȘɯ ǞȘ ëżŏȀŏ

$POUFYUTFOTJUJWF JOUFSQSFUBUJPOT JO 4DBMB

BSF VOQSPCMFNBUJD BT XFMM
trait Circuit4 extends Circuit1 {def layout(f : Int ) Int) : List[List[(Int, Int)]]}trait Id4 extends Id1 with Circuit4 {def layout(f : Int ) Int) = List()}trait Fan4 extends Fan1 with Circuit4 {def layout(f : Int ) Int) = List(for(i List.range(1, n)) yield(f (0), f (i)))}
trait Above4 extends Above1 with Circuit4 {override val c1 , c2 : Circuit4
def layout(f : Int ) Int) = c1 .layout(f ) ++ c2 .layout(f )}trait Beside4 extends Beside1 with Circuit4 {override val c1 , c2 : Circuit4
def layout(f : Int ) Int) =lzw(c1 .layout(f ), c2 .layout(f .compose(c1 .width + )))( ++ )}trait Stretch4 extends Stretch1 with Circuit4 {override val c : Circuit4
def layout(f : Int ) Int) = {val vs = ns.scanLeft(0)( + ).tailc.layout(f .compose(vs( ) 1))}}
def lzw[A](xs : List[A], ys : List[A])(f :(A, A) ) A) : List[A] =(xs, ys) match {case(Nil, )) yscase( , Nil)) xscase(x :: xs, y :: ys) ) f (x, y) :: lzw(xs, ys)(f )}5IF 4DBMB WFSTJPO DBQUVSFT DPOUFYUT BT NFUIPE BSHVNFOUT BOE UIF JNQMFNFOUBUJPOPG layout JT B EJSFDU USBOTMBUJPO GSPN UIF )BTLFMM WFSTJPO 5IFSF BSF TPNF NJOPSTZOUBY EJɮFSFODFT UIBU OFFE FYQMBOBUJPOT 'JSTUMZ JO Fan4 B for comprehension JT VTFEGPS QSPEVDJOH B MJTU PG DPOOFDUJPOT 4FDPOEMZ GPS TJNQMJDJUZ BOPOZNPVT GVODUJPOTBSF DSFBUFE XJUIPVU B QBSBNFUFS MJTU 'PS FYBNQMF JOTJEF Beside4 c1 .width + JT B
TIPSUIBOE GPS i ) c1 .width + i XIFSF UIF QMBDFIPMEFS QMBZT UIF SPMF PG UIF OBNFEQBSBNFUFS i 5IJSEMZ GVODUJPO DPNQPTJUJPO JT BDIJFWFE UISPVHI UIF compose NFUIPE
EFɯOFE PO GVODUJPO WBMVFT XIJDI IBT B SFWFSTF DPNQPTJUJPO PSEFS BT PQQPTFE UP JO)BTLFMM 'PVSUIMZ lzw JT JNQMFNFOUFE BT B curried function XIFSF UIF CJOBSZ PQFSBUPSf JT NPWFE UP UIF FOE BT B TFQBSBUF QBSBNFUFS MJTU GPS GBDJMJUBUJOH UZQF JOGFSFODFߧߦࡇ ߧߦ

ĦƚǞʾǞȘ ĻǕŏȘǃ ŏȘƇ $ɟʕȘȩ +ࡏ Ƈࡏ ëࡏ °ȀǞʲƚǞɟŏߩࡏߪ Ș ŏȀɾƚɟȘŏɾǞʲƚ ƚȘżȩƇǞȘǃ ȩǀ ȒȩƇʕȀŏɟ ǞȘɾƚɟɔɟƚɾŏɾǞȩȘɯ

5IFSF JT BO BMUFSOBUJWF FODPEJOH PG NPEVMBS JOUFSQSFUBUJPOT JO 4DBMB 'PS FYBNQMF UIF
wellSized JOUFSQSFUBUJPO DBO CF SFEFɯOFE MJLF UIJT
trait Circuit3 extends Circuit1 {def wellSized : Boolean}
trait Id3 extends Circuit3 {def wellSized = true}...
trait Stretch3 extends Circuit3 {val c : Circuit3 ; val ns : List[Int]def wellSized = c.wellSized ^ ns.length ⌘ c.width}

XIFSF B DPODSFUF DBTF MJLF Id3 EPFT OPU JOIFSJU Id1 BOE MFBWFT UIF width NFUIPE
VOJNQMFNFOUFE 5IFO BO FYUSB TUFQ UP DPNCJOF wellSized BOE width JT OFFEFE
trait Id13 extends Id1 with Id3...
trait Stretch13 extends Stretch1 with Stretch3$PNQBSFE UP UIF QSFWJPVT FODPEJOH UIJT FODPEJOH JT NPSF NPEVMBS CFDBVTF JU
EFDPVQMFT wellSized XJUI B QBSUJDVMBS JNQMFNFOUBUJPO PG width )PXFWFS NPSF CPJMFSQMBUF JT OFFEFE GPS DPNCJOJOH JOUFSQSFUBUJPOT .PSFPWFS JU SFRVJSFT TPNF TVQQPSU GPS
NVMUJQMFJOIFSJUBODF XIJDI SFTUSJDUT UIF FODPEJOH JUTFMG GSPN CFJOH BQQMJFE UP B XJEFSSBOHF PG 00 MBOHVBHFTߩࡏ߫ ȩƇʕȀŏɟ ȀŏȘǃʕŏǃƚ żȩȘɯɾɟʕżɾɯ

#FTJEFT OFX JOUFSQSFUBUJPOT OFX MBOHVBHF DPOTUSVDUT NBZ CF OFFEFE XIFO B %4FWPMWFT 'PS FYBNQMF JO UIF DBTF PG 4ɵɳʀʅ XF NBZ XBOU B rstretch SJHIU TUSFUDIDPNCJOBUPS XIJDI JT TJNJMBS UP UIF stretch DPNCJOBUPS CVU TUSFUDIFT B DJSDVJU PQQPTJUFMZƚʶ żȩȘɯɾɟʕżɾɯ ǞȘ mŏɯǺƚȀȀ

4IBMMPX FNCFEEJOHT NBLF UIF BEEJUJPO PG rstretch FBTZ CZEFɯOJOH B OFX GVODUJPO
rstretch:: [Int] ! Circuit4 ! Circuit4
rstretch ns c = stretch4 (1 : init ns) c ‘beside4 ‘ id4 (last ns

1)

rstretch IBQQFOT UP CF TZOUBDUJD TVHBS PWFS FYJTUJOH DPOTUSVDUT 'PS OPOTVHBS DPOTUSVDUTB OFX GVODUJPO UIBU JNQMFNFOUT BMM TVQQPSUFE JOUFSQSFUBUJPOT JT OFFEFEƚʶ żȩȘɯɾɟʕżɾɯ ǞȘ ëżŏȀŏ

4VDI TJNQMJDJUZ PG BEEJOH OFX DPOTUSVDUT JT SFUBJOFE JO 4DBMB%JɮFSFOUMZ GSPN UIF )BTLFMM BQQSPBDI UIFSF JT B DMFBS EJTUJODUJPO CFUXFFO TZOUBDUJD
TVHBS BOE PSEJOBSZ DPOTUSVDUT JO 4DBMB
*O 4DBMB TZOUBDUJD TVHBS JT EFɯOFE BT B TNBSU DPOTUSVDUPS VQPO PUIFS TNBSU DPOTUSVDUPST
def rstretch(ns : List[Int], c : Circuit4 ) = stretch(1 :: ns.init, beside(c, id(ns.lastߧߦࡇ ߧߧ

1)))ëǕŏȀȀȩʶ C4ëɯ ŏȘƇ °ųǲƚżɾࡷ°ɟǞƚȘɾƚƇ ÚɟȩǃɟŏȒȒǞȘǃ

0O UIF PUIFS IBOE BEEJOH PSEJOBSZ DPOTUSVDUT JT EPOF CZ EFɯOJOH B OFX USBJU UIBUJNQMFNFOUT Circuit4  *G XF USFBUFE rstretch BT BO PSEJOBSZ DPOTUSVDU JUT EFɯOJUJPOXPVME CFtrait RStretch extends Stretch4 {override def layout(f : Int ) Int) = {val vs = ns.scanLeft(ns.last 1)( + ).initc.layout(f .compose(vs( )))}}

4VDI BO JNQMFNFOUBUJPO PG RStretch JMMVTUSBUFT BOPUIFS TUSFOHUI PG UIF 4DBMB BQQSPBDI SFHBSEJOH NPEVMBSJUZ /PUF UIBU RStretch EPFT OPU JNQMFNFOU Circuit4 EJSFDUMZ*OTUFBE JU JOIFSJUT Stretch4 BOE PWFSSJEFT UIF layout EFɯOJUJPO TP BT UP SFVTF PUIFSJOUFSQSFUBUJPOT BT XFMM BT ɯFME EFDMBSBUJPOT GSPN Stretch4  *OIFSJUBODF BOE NFUIPE
PWFSSJEJOH FOBCMF QBSUJBM SFVTF PG BO FYJTUJOH MBOHVBHF DPOTUSVDU JNQMFNFOUBUJPOXIJDI JT QBSUJDVMBSMZ VTFGVM GPS EFɯOJOH TQFDJBMJ[FE DPOTUSVDUTߩࡏ߬ 4ǞɯżʕɯɯǞȩȘ(JCCPOT BOE 8V DMBJN UIBU JO TIBMMPX FNCFEEJOHT OFX MBOHVBHF DPOTUSVDUT BSF FBTZUP BEE CVU OFX JOUFSQSFUBUJPOT BSF IBSE *U JT QPTTJCMF UP EFɯOF NVMUJQMF JOUFSQSFUBUJPOT WJB UVQMFT ƭCVU UIJT JT TUJMM B CJU DMVNTZ JU FOUBJMT SFWJTJOH FYJTUJOH DPEF FBDI UJNF B
OFX JOUFSQSFUBUJPO JT BEEFE BOE XJEF UVQMFT HFOFSBMMZ MBDL HPPE MBOHVBHF TVQQPSUƮ <ɏ>*O PUIFS XPSET )BTLFMMƫT BQQSPBDI CBTFE PO UVQMFT JT FTTFOUJBMMZ OPONPEVMBS )PXFWFS BT PVS 4DBMB DPEF TIPXT VTJOH 001 NFDIBOJTNT CPUI MBOHVBHF DPOTUSVDUTBOE JOUFSQSFUBUJPOT BSF FBTZ UP BEE JO TIBMMPX FNCFEEJOHT .PSFPWFS EFQFOEFOUJOUFSQSFUBUJPOT BSF QPTTJCMF UPP XIJDI FOBCMFT JOUFSQSFUBUJPOT UIBU NBZ EFQFOE POPUIFS NPEVMBS JOUFSQSFUBUJPOT BOE HP CFZPOE TJNQMF DPNQPTJUJPOBMJUZ 5IF LFZ QPJOUJT UIBU QSPDFEVSBM BCTUSBDUJPO DPNCJOFE XJUI 001 GFBUVSFT TVCUZQJOH JOIFSJUBODFBOE UZQFSFɯOFNFOU BEET FYQSFTTJWFOFTT PWFS USBEJUJPOBM QSPDFEVSBM BCTUSBDUJPO
0OF XPSUIZ QPJOU BCPVU UIF 4DBMB TPMVUJPO QSFTFOUFE TP GBS JT UIBU JU JT TUSBJHIUGPSXBSE VTJOH 001 NFDIBOJTNT JU VTFT POMZ TJNQMF UZQFT BOE EFQFOEFOU JOUFSQSFUBUJPOTBSF OPU B QSPCMFN (JCCPOT BOE 8V EP EJTDVTT B OVNCFS PG NPSF BEWBODFE UFDIOJRVFT <Ɋ Ɋɉ> UIBU DBO TPMWF TPNF PG UIF NPEVMBSJUZ QSPCMFNT *O UIFJS QBQFS UIFZTIPX IPX UP TVQQPSU NPEVMBS depth BOE width DPSSFTQPOEJOH UP 4FDUJPO ɋɉ VT
JOH UIF 'JOBMMZ 5BHMFTT <Ɋ> BQQSPBDI 5IJT JT QPTTJCMF CFDBVTF depth BOE width BSF
OPOEFQFOEFOU )PXFWFS UIFZ EP OPU TIPX IPX UP NPEVMBSJ[F wellSized OPS layout
DPSSFTQPOEJOH UP 4FDUJPO ɋɊ BOE ɋɋ SFTQFDUJWFMZ  *O 4FDUJPO Ɍ XF SFWJTJU TVDI
'JOBMMZ 5BHMFTT FODPEJOH BOE JNQSPWF JU UP BMMPX EFQFOEFOU JOUFSQSFUBUJPOT JOTQJSFECZ UIF 00 TPMVUJPO QSFTFOUFE JO UIJT TFDUJPOߪȩƇʕȀŏɟ ǞȘɾƚɟɔɟƚɾŏɾǞȩȘɯ ǞȘ mŏɯǺƚȀȀ.PEVMBS JOUFSQSFUBUJPOT BSF BMTP QPTTJCMF JO )BTLFMM WJB B WBSJBOU PG $IVSDI FODPEJOHTUIBU VTFT UZQF DMBTTFT 5IF PSJHJOBM UFDIOJRVF JT EVF UP )JO[F <ɑ> BOE XBT TIPXO UP CFߧߦࡇ ߧߨ

ĦƚǞʾǞȘ ĻǕŏȘǃ ŏȘƇ $ɟʕȘȩ +ࡏ Ƈࡏ ëࡏ °ȀǞʲƚǞɟŏ

NPEVMBS BOE FYUFOTJCMF CZ 0MJWFJSB )JO[F BOE -´I <ɉɎ> *U IBT TJODF CFFO QPQVMBSJ[FEVOEFS UIF OBNF 'JOBMMZ 5BHMFTT <Ɋ> JO UIF DPOUFYU PG FNCFEEFE %4-T 5IF JEFB JT UP
VTF B UZQF DMBTT UP BCTUSBDU PWFS UIF TJHOBUVSFT PG DPOTUSVDUT BOE EFɯOF JOUFSQSFUBUJPOTBT JOTUBODFT PG UIBU UZQF DMBTT 5IJT TFDUJPO SFDPEFT UIF 4ɵɳʀʅ FYBNQMF BOE DPNQBSFTUIF UXP NPEVMBS JNQMFNFOUBUJPOT JO )BTLFMM BOE 4DBMBߪࡏߧ áƚʲǞɯǞɾǞȘǃ ë̐˨;χ

)FSF JT UIF UZQF DMBTT EFɯOFE GPS 4ɵɳʀʅ
class Circuit c whereid:: Int ! cfan:: Int ! c
above :: c ! c ! cbeside :: c ! c ! cstretch :: [Int] ! c ! c

5IF TJHOBUVSFT BSF UIF TBNF BT XIBU 4FDUJPO ɊɊ TIPXT FYDFQU UIBU UIF TFNBOUJDEPNBJO JT DBQUVSFE CZ B UZQF QBSBNFUFS c *OUFSQSFUBUJPOT TVDI BT width BSF UIFO
EFɯOFE BT JOTUBODFT PG Circuit
newtype Width = Width {width :: Int}instance Circuit Width where
id n= Width n
fan n= Width nabove c1 c2 = Width (width c1 )beside c1 c2 = Width (width c1 + width c2 )stretch ns c = Width (sum ns)

XIFSF c JT JOTUBOUJBUFE BT B SFDPSE UZQF Width *OTUBOUJBUJOH UIF UZQF QBSBNFUFS BT
Width SBUIFS UIBO Int BWPJET UIF DPOɰJDU XJUI UIF depth JOUFSQSFUBUJPO XIJDI BMTPQSPEVDFT JOUFHFSTʕȀɾǞɔȀƚ ǞȘɾƚɟɔɟƚɾŏɾǞȩȘɯ

"EEJOH UIF depth JOUFSQSFUBUJPO DBO OPX CF EPOF JO B NPEVMBS NBOOFS TJNJMBS UP width
newtype Depth = Depth {depth :: Int}instance Circuit Depth whereid n= Depth 0
fan n= Depth 1
above c1 c2 = Depth (depth c1 + depth c2 )beside c1 c2 = Depth (depth c1 ‘max‘ depth c2 )stretch ns c = Depth (depth c)ߧߦࡇ ߧߩ

ëǕŏȀȀȩʶ C4ëɯ ŏȘƇ °ųǲƚżɾࡷ°ɟǞƚȘɾƚƇ ÚɟȩǃɟŏȒȒǞȘǃߪࡏߨ ȩƇʕȀŏɟ ƇƚɔƚȘƇƚȘɾ ǞȘɾƚɟɔɟƚɾŏɾǞȩȘɯ

"EEJOH B NPEVMBS EFQFOEFOU JOUFSQSFUBUJPO MJLF wellSized JT NPSF DIBMMFOHJOH JO UIF'JOBMMZ 5BHMFTT BQQSPBDI )PXFWFS JOTQJSFE CZ UIF 00 BQQSPBDI XF DBO USZ UP NJNJDUIF 00 NFDIBOJTNT JO )BTLFMM UP PCUBJO TJNJMBS CFOFɯUT JO )BTLFMM *O XIBU GPMMPXTXF FYQMBJO IPX UP FODPEF TVCUZQJOH JOIFSJUBODF BOE UZQFSFɯOFNFOU JO )BTLFMM BOE
IPX UIBU FODPEJOH FOBCMFT BEEJUJPOBM NPEVMBSJUZ CFOFɯUT JO )BTLFMMëʕųɾʿɔǞȘǃ*O UIF 4DBMB TPMVUJPO TVCUZQJOH BWPJET UIF FYQMJDJU QSPKFDUJPOT UIBU BSF
OFFEFE JO UIF )BTLFMM TPMVUJPO QSFTFOUFE JO 4FDUJPO ɋ 8F DBO PCUBJO B TJNJMBS CFOFɯUJO )BTLFMM CZ FODPEJOH B TVCUZQJOH SFMBUJPO PO UVQMFT JO )BTLFMM 8F VTF UIF GPMMPXJOHUZQF DMBTT XIJDI XBT JOUSPEVDFE CZ #BIS BOE )WJUWFE <ɉ> UP FYQSFTT B TVCUZQJOHSFMBUJPO PO UVQMFT
class a b where
prj :: a ! b

instance a
prj x = xa whereinstance (a, b)
prj = fsta whereinstance (b c) ) (a, b)
prj = prj snd

c where*O FTTFODF B UZQF a JT B TVCUZQF PG B UZQF b FYQSFTTFE BT a b JG a IBT UIF TBNF PS
NPSF UVQMF DPNQPOFOUT BT UIF UZQF b 5IJT TVCUZQJOH SFMBUJPO JT DMPTFMZ SFMBUFE UPUIF FMBCPSBUJPO JOUFSQSFUBUJPO PG JOUFSTFDUJPO UZQFT QSPQPTFE CZ %VOɯFME <ɍ> XIFSF%VOɯFMEƫT NFSHF PQFSBUPS DPSSFTQPOET WJB FMBCPSBUJPO UP UIF UVQMF DPOTUSVDUPS BOEQSPKFDUJPOT BSF JNQMJDJU BOE UZQFESJWFO 5IF GVODUJPO prj TJNVMBUFT VQDBTUJOH XIJDIDPOWFSUT B WBMVF PG UZQF a UP B WBMVF PG UZQF b 5IF UISFF PWFSMBQQJOH JOTUBODFT EFɯOFUIF CFIBWJPS PG UIF QSPKFDUJPO GVODUJPO CZ TFBSDIJOH GPS UIF UZQF CFJOH QSPKFDUFE JO B
DPNQPVOE UZQF
ȩƇʕȀŏɟ wellSized ŏȘƇ ƚȘżȩƇǞȘǃɯ ȩǀ ǞȘǕƚɟǞɾŏȘżƚ ŏȘƇ ɾʿɔƚࡷɟƚ˙ȘƚȒƚȘɾ/PX EFɯOJOH

wellSized NPEVMBSMZ CFDPNFT QPTTJCMF
newtype WellSized = WellSized {wellSized :: Bool}

instance (Circuit c, c Width) ) Circuit (WellSized, c) where
id n= (WellSized True, id n)
fan n= (WellSized True, fan n)
above c1 c2 = (WellSized (gwellSized c1 ^ gwellSized c2 ^ gwidth c1 ⌘ gwidth c2 ), above (prj c1 ) (prj c2 ))beside c1 c2 = (WellSized (gwellSized c1 ^ gwellSized c2 ), beside (prj c1 ) (prj c2 ))stretch ns c = (WellSized (gwellSized c ^ length ns ⌘ gwidth c), stretch ns (prj c))
gwidth :: (c Width) ) c ! Int
gwidth = width prjߧߦࡇ ߧߪ

ĦƚǞʾǞȘ ĻǕŏȘǃ ŏȘƇ $ɟʕȘȩ +ࡏ Ƈࡏ ëࡏ °ȀǞʲƚǞɟŏgwellSized :: (c WellSized) ) c ! BoolgwellSized = wellSized prj&TTFOUJBMMZ EFQFOEFOU JOUFSQSFUBUJPOT BSF TUJMM EFɯOFE VTJOH UVQMFT 5IF EFQFOEFODZ
PO width JT FYQSFTTFE CZ DPOTUSBJOJOH UIF UZQF QBSBNFUFS BT c Width 4VDI DPOTUSBJOUBMMPXT VT UP TJNVMBUF UIF UZQFSFɯOFNFOU PG ɯFMET JO UIF 4DBMB TPMVUJPO "MUIPVHI UIFJNQMFNFOUBUJPO JT NPEVMBS JU SFRVJSFT TPNF CPJMFSQMBUF 5IF SFVTF PG width JOUFSQSFUBUJPO JT BDIJFWFE WJB EFMFHBUJPO XIFSF prj OFFET UP CF DBMMFE PO FBDI TVCDJSDVJU 4VDI
FYQMJDJU EFMFHBUJPO TJNVMBUFT UIF JOIFSJUBODF FNQMPZFE JO UIF 4DBMB TPMVUJPO "MTPBVYJMJBSZ EFɯOJUJPOT gwidth BOE gwellSized BSF OFDFTTBSZ GPS QSPKFDUJOH UIF EFTJSFEJOUFSQSFUBUJPOT GSPN UIF DPOTUSBJOFE UZQF QBSBNFUFSߪࡏߩ ȩƇʕȀŏɟ ɾƚɟȒɯ

"T OFX JOUFSQSFUBUJPOT NBZ CF BEEFE MBUFS B QSPCMFN JT IPX UP DPOTUSVDU UIF UFSNUIBU DBO CF JOUFSQSFUFE CZ UIPTF OFX JOUFSQSFUBUJPOT XJUIPVU SFDPOTUSVDUJPO 8F TIPXIPX UP EP UIJT GPS UIF DJSDVJU TIPXO JO 'JHVSF Ɋ
circuit :: Circuit c ) ccircuit = (fan 2 ‘beside‘ fan 2) ‘above‘
stretch [2, 2] (fan 2) ‘above‘(id 1 ‘beside‘ fan 2 ‘beside‘ id 1))FSF circuit JT B HFOFSJD DJSDVJU UIBU JT OPU UJFE UP BOZ JOUFSQSFUBUJPO 8IFO JOUFSQSFUJOH
circuit JUT UZQF NVTU CF JOTUBOUJBUFE> width (circuit :: Width)4> depth (circuit :: Depth)
3> gwellSized (circuit :: (WellSized, Width))
True"U VTFSTJUF circuit NVTU CF BOOPUBUFE XJUI UIF UBSHFU TFNBOUJD EPNBJO TP UIBU BO
BQQSPQSJBUF UZQF DMBTT JOTUBODF GPS JOUFSQSFUBUJPO DBO CF DIPTFOëʿȘɾŏʾ ƚʾɾƚȘɯǞȩȘɯ

5IJT TPMVUJPO BMTP BMMPXT VT UP NPEVMBSMZ FYUFOE <ɉɎ> 4ɵɳʀʅ XJUINPSF MBOHVBHF DPOTUSVDUT TVDI BT rstretchclass Circuit c ) ExtendedCircuit c where
rstretch :: [Int] ! c ! c&YJTUJOH JOUFSQSFUBUJPOT DBO CF NPEVMBSMZ FYUFOEFE UP IBOEMF rstretch
instance ExtendedCircuit Width where
rstretch = stretch&YJTUJOH DJSDVJUT DBO BMTP CF SFVTFE GPS DPOTUSVDUJOH DJSDVJUT JO FYUFOEFE 4ɵɳʀʅ
circuit2 :: ExtendedCircuit c ) ccircuit2 = rstretch [2, 2, 2, 2] circuitߧߦࡇ ߧ߫

ëǕŏȀȀȩʶ C4ëɯ ŏȘƇ °ųǲƚżɾࡷ°ɟǞƚȘɾƚƇ ÚɟȩǃɟŏȒȒǞȘǃ
÷ŏųȀƚ ߧ -BOHVBHF GFBUVSFT OFFEFE GPS NPEVMBS JOUFSQSFUBUJPOT 4DBMB WT )BTLFMM(PBM.VMUJQMF JOUFSQSFUBUJPO*OUFSQSFUBUJPO SFVTF%FQFOEFODZ EFDMBSBUJPO

4DBMB)BTLFMM

5SBJU  5ZQFSFɯOFNFOU*OIFSJUBODF
4VCUZQJOH

5ZQF DMBTT%FMFHBUJPO
5VQMFT  5ZQF DPOTUSBJOUT

ߪࡏߪ +ȩȒɔŏɟǞȘǃ ȒȩƇʕȀŏɟ ǞȒɔȀƚȒƚȘɾŏɾǞȩȘɯ ʕɯǞȘǃ ëżŏȀŏ ŏȘƇ mŏɯǺƚȀȀ"MUIPVHI CPUI UIF 4DBMB BOE )BTLFMM TPMVUJPOT BSF BCMF UP NPEFM NPEVMBS EFQFO
EFOU JOUFSQSFUBUJPOT UIFZ VTF B EJɮFSFOU TFU PG MBOHVBHF GFBUVSFT 5BCMF ɉ DPNQBSFTUIF MBOHVBHF GFBUVSFT OFFEFE CZ 4DBMB BOE )BTLFMM 5IF 4DBMB BQQSPBDI SFMJFT PO
CVJMUJO GFBUVSFT *O QBSUJDVMBS TVCUZQJOH JOIFSJUBODF NJYJO DPNQPTJUJPO BOE UZQF
SFɯOFNFOU BSF BMM CVJMUJO 5IJT NBLFT JU RVJUF OBUVSBM UP QSPHSBN UIF TPMVUJPOT JO
4DBMB XJUIPVU FWFO OFFEJOH BOZ GPSN PG QBSBNFUSJD QPMZNPSQIJTN *O DPOUSBTU UIF)BTLFMM TPMVUJPO EPFT OPU IBWF TVDI CVJMUJO TVQQPSU GPS 00 GFBUVSFT 4VCUZQJOH BOE
UZQFSFɯOFNFOU OFFE UP CF FODPEFETJNVMBUFE VTJOH QBSBNFUSJD QPMZNPSQIJTN BOE
UZQF DMBTTFT *OIFSJUBODF JT TJNVMBUFE CZ FYQMJDJU EFMFHBUJPOT 5IF )BTLFMM FODPEJOH JT
BSHVBCMZ DPODFQUVBMMZ NPSF EJɱDVMU UP VOEFSTUBOE BOE VTF CVU JU JT TUJMM RVJUF TJNQMF
0OF JOUFSFTUJOH GFBUVSF UIBU JT TVQQPSUFE JO )BTLFMM JT UIF BCJMJUZ UP FODPEF NPEVMBSUFSNT 5IJT SFMJFT PO UIF GBDU UIBU UIF DPOTUSVDUPST BSF PWFSMPBEFE 5IF 4DBMB TPMVUJPOQSFTFOUFE TP GBS EPFT OPU BMMPX TVDI PWFSMPBEJOH TP DPEF VTJOH DPOTUSVDUPST JT UJFEXJUI B TQFDJɯD JOUFSQSFUBUJPO *O UIF OFYU TFDUJPO XF XJMM TFF B ɯOBM SFɯOFNFOU PG UIF
4DBMB TPMVUJPO UIBU FOBCMFT NPEVMBS UFSNT BMTP CZ VTJOH PWFSMPBEFE DPOTUSVDUPST߫ȩƇʕȀŏɟ ɾƚɟȒɯ ǞȘ ëżŏȀŏ

0OF BEWBOUBHF PG UIF 'JOBMMZ 5BHMFTT BQQSPBDI PWFS PVS 4DBMB BQQSPBDI QSFTFOUFE
TP GBS JT UIBU UFSNT DBO CF DPOTUSVDUFE NPEVMBSMZ XJUIPVU UZJOH UIPTF UFSNT UP BOZ
JOUFSQSFUBUJPO .PEVMBS UFSNT BSF BMTP QPTTJCMF CZ DPNCJOJOH PVS 4DBMB BQQSPBDIXJUI 0CKFDU "MHFCSBT <ɉɍ> XIJDI FNQMPZ B UFDIOJRVF TJNJMBS UP 'JOBMMZ 5BHMFTT JO UIFDPOUFYU PG 001 %JɮFSFOUMZ GSPN UIF )BTLFMM TPMVUJPO QSFTFOUFE JO 4FDUJPO Ɍ UIF 4DBMBBQQSPBDI POMZ FNQMPZT QBSBNFUSJD QPMZNPSQIJTN UP PWFSMPBE UIF DPOTUSVDUPST #PUIJOIFSJUBODF BOE UZQFSFɯOFNFOU EP OPU OFFE UP CF TJNVMBUFE PS FODPEFE°ųǲƚżɾ Ȁǃƚųɟŏ ǞȘɾƚɟǀŏżƚ

5P DBQUVSF UIF HFOFSJD JOUFSGBDF PG UIF DPOTUSVDUPST XF EFɯOFBO BCTUSBDU GBDUPSZ PS 0CKFDU "MHFCSB JOUFSGBDF GPS DJSDVJUT TJNJMBS UP UIF UZQF DMBTTWFSTJPO TIPXO JO 4FDUJPO Ɍɉtrait Circuit[C] {def id(x : Int) : C
def fan(x : Int) : C
def above(x : C, y : C) : C
def beside(x : C, y : C) : Cߧߦࡇ ߧ߬

ĦƚǞʾǞȘ ĻǕŏȘǃ ŏȘƇ $ɟʕȘȩ +ࡏ Ƈࡏ ëࡏ °ȀǞʲƚǞɟŏ

def stretch(x : C, xs : Int⇤) : C}

XIJDI FYQPTFT GBDUPSZ NFUIPET GPS FBDI DJSDVJU DPOTUSVDU TVQQPSUFE CZ 4ɵɳʀʅ
ųɯɾɟŏżɾ ɾƚɟȒɯ

.PEVMBS UFSNT DBO CF DPOTUSVDUFE WJB UIF BCTUSBDU GBDUPSZ 'PS FYBNQMF UIF DJSDVJU TIPXO JO 'JHVSF Ɋ JT CVJMU BT
def circuit[C](f : Circuit[C]) =f .above(f .beside(f .fan(2), f .fan(2)),
f .above(f .stretch(f .fan(2), 2, 2),
f .beside(f .beside(f .id(1), f .fan(2)), f .id(1))))4JNJMBSMZ circuit JT B HFOFSJD NFUIPE UIBU UBLFT B Circuit JOTUBODF BOE CVJMET B DJSDVJUUISPVHI UIBU JOTUBODF 8JUI 4DBMB UIF EFɯOJUJPO PG circuit DBO CF FWFO TJNQMFS XF DBO
BWPJE QSFɯYJOH ƭf .Ʈ FWFSZXIFSF CZ JNQPSUJOH f  /FWFSUIFMFTT UIF EFɯOJUJPO TIPXOIFSF JT NPSF MBOHVBHFJOEFQFOEFOU
°ųǲƚżɾ Ȁǃƚųɟŏɯ

8F OFFE DPODSFUF GBDUPSJFT 0CKFDU "MHFCSBT UIBU JNQMFNFOU Circuit
UP BDUVBMMZ JOWPLF circuit )FSF JT B DPODSFUF GBDUPSZ UIBU QSPEVDFT Circuit1 trait Factory1 extends Circuit[Circuit1 ] {...}XIFSF UIF PNJUUFE DPEF JT JEFOUJDBM UP UIF TNBSU DPOTUSVDUPST QSFTFOUFE JO 4FDUJPO ɊɊ$PODSFUF GBDUPSJFT GPS PUIFS DJSDVJU JNQMFNFOUBUJPOT DBO CF EFɯOFE JO B TJNJMBS XBZCZ JOTUBOUJBUJOH UIF UZQF QBSBNFUFS Circuit BDDPSEJOHMZ
trait Factory4 extends Circuit[Circuit4 ] {...}+ȩȘżɟƚɾƚ ɾƚɟȒɯ

#Z TVQQMZJOH DPODSFUF GBDUPSJFT UP BCTUSBDU UFSNT XF PCUBJO DPODSFUF
UFSNT UIBU DBO CF JOUFSQSFUFE EJɮFSFOUMZ
circuit(new Factory1 { }).widthɌcircuit(new Factory4 { }).layout {x ) x}-JTU -JTU Ɉ ɉɊɋ-JTU ɉ ɋ-JTU ɉ ɊȩƇʕȀŏɟ ƚʾɾƚȘɯǞȩȘɯ

#PUI GBDUPSJFT BOE UFSNT DBO CF NPEVMBSMZ SFVTFE XIFO UIF %4JT FYUFOEFE XJUI OFX MBOHVBHF DPOTUSVDUT 5P TVQQPSU SJHIU TUSFUDI GPS 4ɵɳʀʅ XF ɯSTU
FYUFOE UIF BCTUSBDU GBDUPSZ XJUI OFX GBDUPSZ NFUIPET
trait ExtendedCircuit[C] extends Circuit[C] {def rstretch(x : C, xs : Int⇤) : C}

8F DBO BMTP CVJME FYUFOEFE DPODSFUF GBDUPSJFT VQPO FYJTUJOH DPODSFUF GBDUPSJFT
trait ExtendedFactory4 extends ExtendedCircuit[Circuit4 ] with Factory4 {def rstretch(x : Circuit4 , xs : Int⇤) = new RStretch {val c = x; val ns = xs.toList}}'VSUIFSNPSF QSFWJPVTMZ EFɯOFE UFSNT DBO CF SFVTFE JO DPOTUSVDUJOH FYUFOEFE UFSNTdef circuit2 [C](f : ExtendedCircuit[C]) = f .rstretch(circuit(f ), 2, 2, 2, 2)ߧߦࡇ ߧ߭

ëǕŏȀȀȩʶ C4ëɯ ŏȘƇ °ųǲƚżɾࡷ°ɟǞƚȘɾƚƇ ÚɟȩǃɟŏȒȒǞȘǃ

߬+ŏɯƚ ɯɾʕƇʿࡇ ŏ ɯǕŏȀȀȩʶ C4ë ǀȩɟ ëß ɛʕƚɟǞƚɯ

" DPNNPO NPUJWBUJPO GPS VTJOH EFFQ FNCFEEJOHT JT QFSGPSNBODF %FFQ FNCFEEJOHT
FOBCMF DPNQMFY "45 USBOTGPSNBUJPOT XIJDI JT VTFGVM UP JNQMFNFOU PQUJNJ[BUJPOTUIBU JNQSPWF UIF QFSGPSNBODF "O BMUFSOBUJWF XBZ UP PCUBJO QFSGPSNBODF JT UP VTF
TUBHJOH GSBNFXPSLT TVDI BT -JHIUXFJHIU .PEVMBS 4UBHJOH -.4 <ɉɑ> "T JMMVTUSBUFECZ 3PNQG BOE "NJO <ɉɐ> TUBHJOH DBO QSFDMVEF UIF OFFE GPS "45 USBOTGPSNBUJPOT GPS B
SFBMJTUJD RVFSZ %4- 5P GVSUIFS JMMVTUSBUF UIF BQQMJDBCJMJUZ PG TIBMMPX 00 FNCFEEJOHTXF SFGBDUPSFE 3PNQG BOE "NJOƫT EFFQ FYUFSOBM %4- JNQMFNFOUBUJPO UP NBLF JU NPSF
NPEVMBS TIBMMPX BOE FNCFEEFE 5IF TIBMMPX %4- SFUBJOT UIF QFSGPSNBODF PG UIFPSJHJOBM EFFQ %4- CZ HFOFSBUJOH UIF TBNF DPEF
߬ࡏߧ °ʲƚɟʲǞƚʶ

42- JT UIF CFTULOPXO %4- GPS EBUB RVFSJFT 3PNQG BOE "NJO <ɉɐ> QSFTFOU B 42- RVFSZQSPDFTTPS JNQMFNFOUBUJPO JO 4DBMB 5IFJS JNQMFNFOUBUJPO JT BO FYUFSOBM %4- XIJDIɯSTU QBSTFT B 42- RVFSZ JOUP B SFMBUJPOBM BMHFCSB "45 BOE UIFO FYFDVUFT UIF RVFSZ JOUFSNT PG UIBU "45 #BTFE PO UIF -.4 GSBNFXPSL <ɉɑ> UIF 42- DPNQJMFST BSF OFBSMZ
BT TJNQMF BT BO JOUFSQSFUFS XIJMF IBWJOH QFSGPSNBODF DPNQBSBCMF UP IBOEXSJUUFO
DPEF 5IF JNQMFNFOUBUJPO VTFT EFFQ FNCFEEJOH UFDIOJRVFT TVDI BT BMHFCSBJD EBUBUZQFT DBTF DMBTTFT JO 4DBMB BOE QBUUFSO NBUDIJOH GPS SFQSFTFOUJOH BOE JOUFSQSFUJOH"45T 5IFTF UFDIOJRVFT BSF B OBUVSBM DIPJDF BT NVMUJQMF JOUFSQSFUBUJPOT BSF OFFEFE GPS
TVQQPSUJOH EJɮFSFOU CBDLFOET #VU QSPCMFNT BSJTF XIFO UIF JNQMFNFOUBUJPO FWPMWFTXJUI OFX MBOHVBHF DPOTUSVDUT "MM FYJTUJOH JOUFSQSFUBUJPOT IBWF UP CF NPEJɯFE GPS
EFBMJOH XJUI UIFTF OFX DBTFT TVɮFSJOH GSPN UIF &YQSFTTJPO 1SPCMFN
8F SFGBDUPSFE 3PNQG BOE "NJO <ɉɐ>ƫT JNQMFNFOUBUJPO JOUP B TIBMMPX &%4- GPS UIFGPMMPXJOH SFBTPOT 'JSTUMZ NVMUJQMF JOUFSQSFUBUJPOT BSF OP MPOHFS B QSPCMFN GPS PVSTIBMMPX FNCFEEJOH UFDIOJRVF 4FDPOEMZ UIF PSJHJOBM JNQMFNFOUBUJPO DPOUBJOT OP
IBOEDPEFE "45 USBOTGPSNBUJPOT 5IJSEMZ JU JT DPNNPO UP FNCFE 42- JOUP B HFOFSBMQVSQPTF MBOHVBHF
5P JMMVTUSBUF PVS TIBMMPX &%4- TVQQPTF UIFSF JT B EBUB ɯMF talks.csv UIBU DPOUBJOT B
MJTU PG UBMLT XJUI UJNF UJUMF BOE SPPN 8F DBO XSJUF TFWFSBM TBNQMF RVFSJFT PO UIJT ɯMF
XJUI PVS &%4- " TJNQMF RVFSZ UIBU MJTUT BMM JUFNT JO talks.csv JT
def q0 = FROM (ࢆɾŏȀǺɯࡏżɯʲࢆ)"OPUIFS RVFSZ UIBU ɯOET BMM UBMLT BU ɑ BN XJUI UIFJS SPPN BOE UJUMF TFMFDUFE JT
def q1 = q0 WHERE ‘time === ࢆߦ߯ࡇߦߦ ࢆ SELECT (‘room, ‘title):FU BOPUIFS SFMBUJWFMZ DPNQMFY RVFSZ UP ɯOE BMM DPOɰJDUJOH UBMLT UIBU IBQQFO BU UIFTBNF UJNF JO UIF TBNF SPPN XJUI EJɮFSFOU UJUMFT JT
def q2 = q0 SELECT (‘time, ‘room, ‘title AS ‘title1 ) JOIN
(q0 SELECT (‘time, ‘room, ‘title AS ‘title2 )) WHERE‘title1 <> ‘title2ߧߦࡇ ߧ߮

ĦƚǞʾǞȘ ĻǕŏȘǃ ŏȘƇ $ɟʕȘȩ +ࡏ Ƈࡏ ëࡏ °ȀǞʲƚǞɟŏ$PNQBSFE UP BO FYUFSOBM JNQMFNFOUBUJPO PVS FNCFEEFE JNQMFNFOUBUJPO IBT UIF
CFOFɯU PG SFVTJOH UIF NFDIBOJTNT QSPWJEFE CZ UIF IPTU MBOHVBHF GPS GSFF "T JMMVTUSBUFECZ UIF TBNQMF RVFSJFT BCPWF XF BSF BCMF UP SFVTF DPNNPO TVCRVFSJFT q0 JO CVJMEJOH
DPNQMFY RVFSJFT q1 BOE q2  5IJT JNQSPWFT UIF SFBEBCJMJUZ BOE NPEVMBSJUZ PG UIFFNCFEEFE QSPHSBNT߬ࡏߨ CȒųƚƇƇƚƇ ɯʿȘɾŏʾ

5IBOLT UP UIF HPPE TVQQPSU GPS &%4-T JO 4DBMB XF DBO QSFDJTFMZ NPEFM UIF TZOUBY PG
42- 5IF TZOUBY PG PVS &%4- JT DMPTF UP UIBU PG -*/2 <ɉɋ> XIFSF select JT BO PQUJPOBMUFSNJOBUJOH DMBVTF PG B RVFSZ 8F FNQMPZ XFMMFTUBCMJTIFE 00 BOE 4DBMB UFDIOJRVFT UP
TJNVMBUF UIF TZOUBY PG 42- RVFSJFT JO PVS TIBMMPX &%4- JNQMFNFOUBUJPO 4QFDJɯDBMMZ
XF VTF UIF 1JNQ .Z -JCSBSZ QBUUFSO <ɉɌ> GPS MJGUJOH ɯFME OBNFT BOE MJUFSBMT JNQMJDJUMZ'PS UIF TZOUBY PG DPNCJOBUPST TVDI BT where BOE join XF BEPQU B ɰVFOU JOUFSGBDF TUZMF
'MVFOU JOUFSGBDFT FOBCMF XSJUJOH TPNFUIJOH MJLF ƭFROM (...).WHERE (...).SELECT (...)Ʈ
4DBMBƫT JOɯY OPUBUJPO GVSUIFS PNJUT ƭ.Ʈ JO NFUIPE DIBJOT 0UIFS GBNPVT FNCFEEFE 42JNQMFNFOUBUJPOT JO 001 TVDI BT -*/2 <ɉɋ> BMTP BEPQU TJNJMBS UFDIOJRVFT JO EFTJHOJOHUIFJS TZOUBY 5IF TZOUBY JT JNQMFNFOUFE JO B QMVHHBCMF XBZ JO UIF TFOTF UIBU UIFTFNBOUJDT JT EFDPVQMFE GSPN UIF TZOUBY %FUBJMT PG UIF TZOUBY JNQMFNFOUBUJPO BSF
CFZPOE UIF TDPQF PG UIJT QFBSM 5IF JOUFSFTUFE SFBEFS DBO DPOTVMU UIF DPNQBOJPO DPEF
#FOFBUI UIF TVSGBDF TZOUBY B SFMBUJPOBM BMHFCSB PQFSBUPS TUSVDUVSF JT DPOTUSVDUFE'PS FYBNQMF XF XJMM HFU UIF GPMMPXJOH PQFSBUPS TUSVDUVSF GPS q1 
Project(Schema(ࢆɟȩȩȒࢆ, ࢆɾǞɾȀƚࢆ),
Filter(Eq(Field(ࢆɾǞȒƚࢆ), Value(ࢆߦ߯ࡇߦߦ ࢆ)),Scan(ࢆɾŏȀǺɯࡏżɯʲࢆ)))߬ࡏߩ  ɟƚȀŏɾǞȩȘŏȀ ŏȀǃƚųɟŏ żȩȒɔǞȀƚɟ" 42- RVFSZ DBO CF SFQSFTFOUFE CZ B SFMBUJPOBM BMHFCSB FYQSFTTJPO 5IF CBTJD JOUFSGBDF
PG PQFSBUPST JT NPEFMFE BT GPMMPXT
trait Operator {def resultSchema : Schema
def execOp(yld : Record ) Unit) : Unit}

5XP JOUFSQSFUBUJPOT resultSchema BOE execOp OFFE UP CF JNQMFNFOUFE GPS FBDI DPODSFUF PQFSBUPS UIF GPSNFS DPMMFDUT B TDIFNB GPS QSPKFDUJPO UIF MBUUFS FYFDVUFT BDUJPOTUP UIF SFDPSET PG UIF UBCMF 7FSZ NVDI MJLF UIF JOUFSQSFUBUJPO layout EJTDVTTFE JO 4FDUJPO ɋɋ execOp JT CPUI DPOUFYUTFOTJUJWF BOE EFQFOEFOU JU UBLFT B DBMMCBDL yld BOE
BDDVNVMBUFT XIBU UIF PQFSBUPS EPFT UP SFDPSET JOUP yld BOE VTFT resultSchema JO
EJTQMBZJOH FYFDVUJPO SFTVMUT *O PVS JNQMFNFOUBUJPO execOp JT JOEFFE JOUSPEVDFE BT
BO FYUFOTJPO KVTU MJLF layout )FSF XF NFSHF UIF UXP JOUFSQSFUBUJPOT GPS DPODJTFOFTTPG QSFTFOUBUJPO 4PNF DPSF DPODSFUF SFMBUJPOBM BMHFCSB PQFSBUPST BSF HJWFO CFMPXߧߦࡇ ߧ߯

ëǕŏȀȀȩʶ C4ëɯ ŏȘƇ °ųǲƚżɾࡷ°ɟǞƚȘɾƚƇ ÚɟȩǃɟŏȒȒǞȘǃ

trait Project extends Operator {val out, in : Schema; val op : Operator
def resultSchema = out
def execOp(yld : Record ) Unit) = op.execOp {rec ) yld(Record(rec(in ), out))}}
trait Join extends Operator {val op1 , op2 : Operator
def resultSchema = op1 .resultSchema ++ op2 .resultSchema
def execOp(yld : Record ) Unit) =op1 .execOp {rec1 )op2 .execOp {rec2 )val keys = rec1 .schema intersect rec2 .schema
if(rec1 (keys) ⌘ rec2 (keys))yld(Record(rec1 .fields ++ rec2 .fields, rec1 .schema ++ rec2 .schema))}}}trait Filter extends Operator {val pred : Predicate; val op : Operator
def resultSchema = op.resultSchema
def execOp(yld : Record ) Unit) = op.execOp {rec ) if(pred.eval(rec)) yld(rec)}}Project SFBSSBOHFT UIF ɯFMET PG B SFDPSE Join NBUDIFT B SFDPSE BHBJOTU BOPUIFS BOE
DPNCJOFT UIF UXP SFDPSET JG UIFJS DPNNPO ɯFMET TIBSF UIF TBNF WBMVFT Filter LFFQT B
SFDPSE POMZ XIFO JU NFFUT B DFSUBJO QSFEJDBUF 5IFSF BSF BMTP UXP VUJMJUZ PQFSBUPST
Print BOE Scan GPS QSPDFTTJOH JOQVUT BOE PVUQVUT XIPTF EFɯOJUJPOT BSF PNJUUFE GPSTQBDF SFBTPOT_ɟȩȒ ŏȘ ǞȘɾƚɟɔɟƚɾƚɟ ɾȩ ŏ żȩȒɔǞȀƚɟ

5IF RVFSZ QSPDFTTPS QSFTFOUFE TP GBS JT FMFHBOU CVUVOGPSUVOBUFMZ TMPX 5P BDIJFWF CFUUFS QFSGPSNBODF 3PNQG BOE "NJO FYUFOE UIF 42QSPDFTTPS JO WBSJPVT XBZT 0OF EJSFDUJPO JT UP UVSO UIF TMPX RVFSZ JOUFSQSFUFS JOUP B
GBTU RVFSZ DPNQJMFS CZ HFOFSBUJOH TQFDJBMJ[FE MPXMFWFM DPEF GPS B HJWFO RVFSZ 8JUIUIF IFMQ PG UIF -.4 GSBNFXPSL UIJT UBTL CFDPNFT SBUIFS FBTZ -.4 QSPWJEFT B UZQF
DPOTUSVDUPS Rep GPS BOOPUBUJOH DPNQVUBUJPOT UIBU BSF UP CF QFSGPSNFE JO UIF OFYU
TUBHF 5IF TJHOBUVSF PG UIF TUBHFE execOp JT
def execOp(yld : Record ) Rep[Unit]) : Rep[Unit]

XIFSF Unit JT MJGUFE BT Rep [Unit] GPS EFMBZJOH UIF BDUJPOT PO SFDPSET UP UIF HFOFSBUFE DPEF 5XP TUBHFE WFSTJPOT PG execOp BSF JOUSPEVDFE GPS HFOFSBUJOH 4DBMB BOE$ DPEF SFTQFDUJWFMZ #Z VTJOH UIF UFDIOJRVF QSFTFOUFE JO 4FDUJPO ɋ UIFZ BSF BEEFENPEVMBSMZ XJUI FYJTUJOH JOUFSQSFUBUJPOT TVDI BT resultSchema SFVTFE 5IF JNQMFNFOUBUJPO PG TUBHFE execOp JT TJNJMBS UP UIF VOTUBHFE DPVOUFSQBSU FYDFQU GPS NJOPS "1*
EJɮFSFODFT CFUXFFO TUBHFE BOE VOTUBHFE UZQFT )FODF UIF TJNQMJDJUZ PG UIF JNQMF
NFOUBUJPO SFNBJOT "U UIF TBNF UJNF ESBNBUJD TQFFEVQT BSF PCUBJOFE CZ TXJUDIJOH
GSPN JOUFSQSFUBUJPO UP DPNQJMBUJPOߧߦࡇ ߨߦ

ĦƚǞʾǞȘ ĻǕŏȘǃ ŏȘƇ $ɟʕȘȩ +ࡏ Ƈࡏ ëࡏ °ȀǞʲƚǞɟŏ÷ŏųȀƚ ߨ 4-0$ GPS PSJHJOBM %FFQ BOE SFGBDUPSFE 4IBMMPX WFSTJPOT4PVSDFRVFSZ@VOTUBHFERVFSZ@TUBHFERVFSZ@PQUD'VODUJPOBMJUZ%FFQ

4IBMMPX

42- JOUFSQSFUFS
42- UP 4DBMB DPNQJMFS
42- UP $ DPNQJMFS

ɐɋ
ɉɏɑ
ɊɌɍ

ɑɐ
ɉɑɌ
ɊɎɊ

ŏȘǃʕŏǃƚ ƚʾɾƚȘɯǞȩȘɯ

3PNQG BOE "NJO BMTP FYUFOE UIF RVFSZ QSPDFTTPS XJUI UXP OFXMBOHVBHF DPOTUSVDUT IBTI KPJOT BOE BHHSFHBUFT 5IF JOUSPEVDUJPO PG UIFTF DPOTUSVDUT
JT EPOF JO B NPEVMBS NBOOFS XJUI PVS BQQSPBDI
trait Group extends Operator {val keys, agg : Schema; val op : Operator
def resultSchema = keys ++ agg
def execOp(yld : Record ) Unit) {...}}
trait HashJoin extends Join {override def execOp(yld : Record ) Unit) = {val keys = op1 .resultSchema intersect op2 .resultSchema
val hm = new HashMapBuffer(keys, op1 .resultSchema)
op1 .execOp {rec1 )hm(rec1 (keys)) += rec1 .fields}
op2 .execOp {rec2 )hm(rec2 (keys)) foreach {rec1 )yld(Record(rec1 .fields ++ rec2 .fields, rec1 .schema ++ rec2 .schema))}}}}

Group TVQQPSUT 42-ƫT group by DMBVTF XIJDI QBSUJUJPOT SFDPSET BOE TVNT VQ TQFDJɯFEɯFMET GSPN UIF DPNQPTFE PQFSBUPS HashJoin JT B SFQMBDFNFOU GPS Join XIJDI VTFTB IBTICBTFE JNQMFNFOUBUJPO JOTUFBE PG OBJWF OFTUFE MPPQT 8JUI JOIFSJUBODF BOE
NFUIPE PWFSSJEJOH XF BSF BCMF UP SFVTF UIF ɯFME EFDMBSBUJPOT BOE PUIFS JOUFSQSFUBUJPOTGSPN Join
߬ࡏߪ CʲŏȀʕŏɾǞȩȘ

8F FWBMVBUF PVS SFGBDUPSFE TIBMMPX JNQMFNFOUBUJPO XJUI SFTQFDU UP UIF PSJHJOBM EFFQJNQMFNFOUBUJPO #PUI JNQMFNFOUBUJPOT PG UIF %4- UIF PSJHJOBM BOE PVS SFGBDUPSFEWFSTJPO HFOFSBUF UIF TBNF DPEF UIVT UIF QFSGPSNBODF PG UIF UXP JNQMFNFOUBUJPOTJT TJNJMBS )FODF XF DPNQBSF UIF UXP JNQMFNFOUBUJPOT POMZ JO UFSNT PG UIF TPVSDFMJOFT PG DPEF 4-0$  8F FYDMVEF UIF DPEF SFMBUFE UP TVSGBDF TZOUBY GPS UIF GBJSOFTTPG DPNQBSJTPO CFDBVTF PVS SFGBDUPSFE WFSTJPO VTFT FNCFEEFE TZOUBY XIFSFBT UIFPSJHJOBM VTFT B QBSTFS "T TFFO JO 5BCMF Ɋ PVS TIBMMPX BQQSPBDI UBLFT B EP[FO NPSF
MJOFT PG DPEF UIBO UIF PSJHJOBM EFFQ BQQSPBDI GPS FBDI WFSTJPO PG 42- QSPDFTTPS 5IF
4-0$ FYQBOTJPO JT BUUSJCVUFE UP UIF GBDU UIBU GVODUJPOBM EFDPNQPTJUJPO DBTF DMBTTFT JT
NPSF DPNQBDU UIBO PCKFDUPSJFOUFE EFDPNQPTJUJPO JO 4DBMB /FWFSUIFMFTT PVS TIBMMPXBQQSPBDI NBLFT JU FBTJFS UP BEE OFX MBOHVBHF DPOTUSVDUTߧߦࡇ ߨߧ

ëǕŏȀȀȩʶ C4ëɯ ŏȘƇ °ųǲƚżɾࡷ°ɟǞƚȘɾƚƇ ÚɟȩǃɟŏȒȒǞȘǃ

߭+ȩȘżȀʕɯǞȩȘ

5IJT QSPHSBNNJOH QFBSM SFWFBMT UIF DMPTF DPSSFTQPOEFODF CFUXFFO 001 BOE TIBMMPXFNCFEEJOHT UIF FTTFODF PG CPUI JT QSPDFEVSBM BCTUSBDUJPO *U BMTP TIPXFE IPX 001
JODSFBTFT UIF NPEVMBSJUZ PG TIBMMPX &%4-T 001 BCTUSBDUJPOT JODMVEJOH TVCUZQJOHJOIFSJUBODF BOE UZQFSFɯOFNFOU CSJOH FYUSB NPEVMBSJUZ UP USBEJUJPOBM QSPDFEVSBM
BCTUSBDUJPO "T B SFTVMU NVMUJQMF JOUFSQSFUBUJPOT BSF BMMPXFE UP DPFYJTU JO TIBMMPXFNCFEEJOHT .PSFPWFS UIF NVMUJQMF JOUFSQSFUBUJPOT DBO CF EFQFOEFOU BO JOUFSQSFUBUJPO DBO EFQFOE OPU POMZ PO JUTFMG CVU BMTP PO PUIFS NPEVMBS JOUFSQSFUBUJPOT 5IVTUIF BQQSPBDI QSFTFOUFE IFSF BMMPXT VT UP HP CFZPOE TJNQMF DPNQPTJUJPOBMJUZ XIFSFJOUFSQSFUBUJPOT DBO POMZ EFQFOE PO UIFNTFMWFT
*U IBT BMXBZT CFFO B IBSE DIPJDF CFUXFFO TIBMMPX BOE EFFQ FNCFEEJOHT XIFOEFTJHOJOH BO &%4- UIFSF BSF TPNF USBEFPɮT CFUXFFO UIF UXP TUZMFT %FFQ FNCFEEJOHT
USBEF TPNF TJNQMJDJUZ BOE UIF BCJMJUZ UP BEE OFX MBOHVBHF DPOTUSVDUT GPS TPNF FYUSBQPXFS 5IJT FYUSB QPXFS FOBCMFT NVMUJQMF JOUFSQSFUBUJPOT BT XFMM BT DPNQMFY "45
USBOTGPSNBUJPOT "T UIJT QFBSM TIPXT JO MBOHVBHFT XJUI 001 NFDIBOJTNT NVMUJQMF
QPTTJCMZ EFQFOEFOU JOUFSQSFUBUJPOT BSF TUJMM FBTZ UP EP XJUI TIBMMPX FNCFEEJOHT
BOE UIF GVMM CFOFɯUT PG BO FYUFOEFE GPSN PG DPNQPTJUJPOBMJUZ TUJMM BQQMZ 5IFSFGPSFUIF NPUJWBUJPO UP FNQMPZ EFFQ FNCFEEJOHT CFDPNFT XFBLFS UIBO CFGPSF BOE NPTUMZSFEVDFE UP UIF OFFE GPS "45 USBOTGPSNBUJPOT 1SJPS XPSL PO UIF 'JOBMMZ 5BHMFTT <ɉɊ>
BOE 0CKFDU "MHFCSBT <ɊɌ> BQQSPBDIFT BMSFBEZ TIPX UIBU "45 USBOTGPSNBUJPOT BSF TUJMM
QPTTJCMF JO UIPTF TUZMFT )PXFWFS UIJT SFRVJSFT TPNF FYUSB NBDIJOFSZ BOE UIF MJOF
CFUXFFO TIBMMPX BOE EFFQ FNCFEEJOHT CFDPNFT RVJUF CMVSSZ BU UIBU QPJOU'JOBMMZ UIJT XPSL TIPXT B DPNCJOBUJPO PG UXP QSFWJPVTMZ TUVEJFE TPMVUJPOT UP UIF&YQSFTTJPO 1SPCMFN JO 00 UIF FYUFOTJCMF JOUFSQSFUFS QBUUFSO QSPQPTFE CZ 8BOH BOE
0MJWFJSB <Ɋɋ> BOE 0CKFDU "MHFCSBT <ɉɍ> 5IF DPNCJOBUJPO FYQMPJUT UIF BEWBOUBHFT PG
FBDI PG UIF BQQSPBDIFT UP PWFSDPNF UIF MJNJUBUJPOT PG FBDI BQQSPBDI JOEJWJEVBMMZ *O
UIF PSJHJOBM BQQSPBDI CZ 8BOH BOE 0MJWFJSB NPEVMBS UFSNT BSF IBSE UP NPEFM XIFSFBTXJUI 0CKFDU "MHFCSBT B EJɱDVMUZ JT NPEFMJOH NPEVMBS EFQFOEFOU PQFSBUJPOT " DMPTFMZSFMBUFE UFDIOJRVF JT FNQMPZFE CZ $B[[PMB BOE 7BDDIJ <ɋ> BMUIPVHI JO UIF DPOUFYUPG FYUFSOBM %4-T 5IFJS UFDIOJRVF JT TMJHIUMZ EJɮFSFOU XJUI SFTQFDU UP UIF FYUFOTJCMF
JOUFSQSFUFS QBUUFSO &TTFOUJBMMZ XIJMF PVS BQQSPBDI JT QVSFMZ CBTFE PO TVCUZQJOH BOE
UZQFSFɯOFNFOU UIFZ VTF HFOFSJD UZQFT JOTUFBE UP TJNVMBUF UIF UZQFSFɯOFNFOU 8IJMF
UIF GPDVT PG PVS XPSL JT FNCFEEFE %4-T UIF UFDIOJRVFT EJTDVTTFE IFSF BSF VTFGVM GPS
PUIFS BQQMJDBUJPOT JODMVEJOH FYUFSOBM %4-T BT $B[[PMB BOE 7BDDIJ TIPX
żǺȘȩʶȀƚƇǃƚȒƚȘɾɯ

8F UIBOL 8JMMBN 3 $PPL +FSFNZ (JCCPOT 3BMG )JO[F .BSUJO&SXJH BOE UIF BOPOZNPVT SFWJFXFST PG (1$& *$'1 +'1 BOE 1SPHSBNNJOH GPS UIFJSWBMVBCMF DPNNFOUT UIBU TJHOJɯDBOUMZ JNQSPWFE UIJT XPSL 5IJT XPSL JT CBTFE PO UIFɯSTU BVUIPSƫT NBTUFS UIFTJT <Ɋɍ> BOE IBT CFFO GVOEFE CZ )POH ,POH 3FTFBSDI (SBOU$PVODJM QSPKFDUT OVNCFS ɉɏɊɉɈɎɉɏ BOE ɉɏɊɍɐɐɉɎߧߦࡇ ߨߨ

ĦƚǞʾǞȘ ĻǕŏȘǃ ŏȘƇ $ɟʕȘȩ +ࡏ Ƈࡏ ëࡏ °ȀǞʲƚǞɟŏáƚǀƚɟƚȘżƚɯ<ɉ> 1BUSJDL #BIS BOE 5PN )WJUWFE $PNQPTJUJPOBM %BUB 5ZQFT *O 1SPDFFEJOHT PG UIF
4FWFOUI "$. 4*(1-"/ 8PSLTIPQ PO (FOFSJD 1SPHSBNNJOH 8(1 ƫɉɉ QBHFT ɐɋƦɑɌɊɈɉɉ ƇȩǞࡇߝߜࡏߝߝߠߡࡕߞߜߟߢߥߝߤࡏߞߜߟߢߥߟߜ
<Ɋ> +BDRVFT $BSFUUF 0MFH ,JTFMZPW BOE $IVOHDIJFI 4IBO 'JOBMMZ 5BHMFTT 1BSUJBMMZ&WBMVBUFE 5BHMFTT 4UBHFE *OUFSQSFUFST GPS 4JNQMFS 5ZQFE -BOHVBHFT +PVSOBM PG'VODUJPOBM 1SPHSBNNJOH ɉɑ Ɉɍ ɍɈɑƦɍɌɋ ɊɈɈɑ ƇȩǞࡇߝߜࡏߝߜߝߣࡕëߜߥߡߢߣߥߢߤߜߥߜߜߣߞߜߡ
<ɋ> 8BMUFS $B[[PMB BOE &EPBSEP 7BDDIJ -BOHVBHF $PNQPOFOUT GPS .PEVMBS %4-T
6TJOH 5SBJUT $PNQVUFS -BOHVBHFT 4ZTUFNT  4USVDUVSFT ɌɍɉɎƦɋɌ ɊɈɉɎ ƇȩǞࡇߝߜࡏߝߜߝߢࡕǲࡏżȀࡏߞߜߝߡࡏߝߞࡏߜߜߝ
<Ɍ> 8JMMJBN 3 $PPL 0O 6OEFSTUBOEJOH %BUB "CTUSBDUJPO 3FWJTJUFE *O 1SPDFFEJOHTPG UIF ȘȚUI "$. 4*(1-"/ $POGFSFODF PO 0CKFDU 0SJFOUFE 1SPHSBNNJOH 4ZTUFNT-BOHVBHFT BOE "QQMJDBUJPOT 0014-" ƫɈɑ QBHFT ɍɍɏƦɍɏɊ ɊɈɈɑ ƇȩǞࡇߝߜࡏߝߝߠߡࡕ
ߝߢߟߥߥߠߥࡏߝߢߠߜߝߟߟ
<ɍ> +PTIVB %VOɯFME &MBCPSBUJOH *OUFSTFDUJPO BOE 6OJPO 5ZQFT +PVSOBM PG 'VODUJPOBM
1SPHSBNNJOH ɊɌ Ɋɋ ɉɋɋƦɉɎɍ ɊɈɉɌ ƇȩǞࡇߝߜࡏߝߜߝߣࡕëߜߥߡߢߣߥߢߤߝߟߜߜߜߞߣߜ
<Ɏ> .BSUJO &SXJH BOE &SJD 8BMLJOHTIBX 4FNBOUJDT%SJWFO %4- %FTJHO *O 'PSNBM
BOE 1SBDUJDBM "TQFDUT PG %PNBJO4QFDJȸD -BOHVBHFT 3FDFOU %FWFMPQNFOUT QBHFTɍɎƦɐɈ ɊɈɉɊ ƇȩǞࡇߝߜࡏߠߜߝߤࡕߥߣߤࡷߝࡷߠߢߢߢࡷߞߜߥߞࡷߢࡏżǕߜߜߟ<ɏ> +FSFNZ (JCCPOT BOE /JDPMBT 8V 'PMEJOH %PNBJO4QFDJɯD -BOHVBHFT %FFQ BOE
4IBMMPX &NCFEEJOHT 'VODUJPOBM 1FBSM  *O 1SPDFFEJOHT PG UIF ȗʁUI "$. 4*(1-"/*OUFSOBUJPOBM $POGFSFODF PO 'VODUJPOBM 1SPHSBNNJOH *$'1 ƫɉɌ QBHFT ɋɋɑƦɋɌɏɊɈɉɌ ƇȩǞࡇߝߜࡏߝߝߠߡࡕߞߢߞߤߝߟߢࡏߞߢߞߤߝߟߤ
<ɐ> 3BMG )JO[F "O "MHFCSB PG 4DBOT *O .BUIFNBUJDT PG 1SPHSBN $POTUSVDUJPO QBHFTɉɐɎƦɊɉɈ ɊɈɈɌ ƇȩǞࡇߝߜࡏߝߜߜߣࡕߥߣߤࡷߟࡷߡߠߜࡷߞߣߣߢߠࡷߠ࡙ߝߝ
<ɑ> 3BMG )JO[F (FOFSJDT GPS UIF .BTTFT +PVSOBM PG 'VODUJPOBM 1SPHSBNNJOH ɉɎ Ɍɍ ɌɍɉƦɌɐɋ ɊɈɈɎ ƇȩǞࡇߝߜࡏߝߜߝߣࡕëߜߥߡߢߣߥߢߤߜߢߜߜߢߜߞߞ
<ɉɈ> 1BVM )VEBL .PEVMBS %PNBJO 4QFDJɯD -BOHVBHFT BOE 5PPMT *O 1SPDFFEJOHT'JGUI *OUFSOBUJPOBM $POGFSFODF PO 4PGUXBSF 3FVTF QBHFT ɉɋɌƦɉɌɊ ɉɑɑɐ ƇȩǞࡇߝߜࡏߝߝߜߥࡕv+ëáࡏߝߥߥߤࡏߢߤߡߣߟߤ
<ɉɉ> 7PKJO +PWBOPWJD "NJS 4IBJLIIB 4BOESP 4UVDLJ 7MBEJNJS /JLPMBFW $ISJTUPQI,PDI BOE .BSUJO 0EFSTLZ :JO:BOH $PODFBMJOH UIF %FFQ &NCFEEJOH PG %4-T
*O 1SPDFFEJOHT PG UIF ȘȖȗȚ *OUFSOBUJPOBM $POGFSFODF PO (FOFSBUJWF 1SPHSBNNJOH
$PODFQUT BOE &YQFSJFODFT (1$& ɊɈɉɌ QBHFT ɏɋƦɐɊ ɊɈɉɌ ƇȩǞࡇߝߜࡏߝߝߠߡࡕߞߢߡߤߣߢߝࡏ
ߞߢߡߤߣߣߝ
<ɉɊ> 0MFH ,JTFMZPW 5ZQFE 5BHMFTT 'JOBM *OUFSQSFUFST *O (FOFSJD BOE *OEFYFE 1SPHSBNNJOH QBHFT ɉɋɈƦɉɏɌ ɊɈɉɊ ƇȩǞࡇߝߜࡏߝߜߜߣࡕߥߣߤࡷߟࡷߢߠߞࡷߟߞߞߜߞࡷߜ࡙ߟ
<ɉɋ> &SJL .FJKFS #SJBO #FDLNBO BOE (BWJO #JFSNBO -*/2 3FDPODJMJOH 0CKFDU3FMBUJPOT BOE 9.- JO UIF /&5 'SBNFXPSL *O 1SPDFFEJOHT PG UIF ȘȖȖɾ "$.
4*(.0% *OUFSOBUJPOBM $POGFSFODF PO .BOBHFNFOU PG %BUB 4*(.0% ƫɈɎ QBHFTɏɈɎƦɏɈɎ ɊɈɈɎ ƇȩǞࡇߝߜࡏߝߝߠߡࡕߝߝߠߞߠߣߟࡏߝߝߠߞߡߡߞߧߦࡇ ߨߩ

ëǕŏȀȀȩʶ C4ëɯ ŏȘƇ °ųǲƚżɾࡷ°ɟǞƚȘɾƚƇ ÚɟȩǃɟŏȒȒǞȘǃ

<ɉɌ> .BSUJO 0EFSTLZ 1JNQ .Z -JCSBSZ ɊɈɈɎ -BTU BDDFTTFE PO ɊɈɉɑɈɉɊɑ 63-ǕɾɾɔࡇࡕࡕʶʶʶࡏŏɟɾǞȒŏࡏżȩȒࡕʶƚųȀȩǃɯࡕʲǞƚʶɔȩɯɾࡏǲɯɔࡐɾǕɟƚŏƇ࣌ߝߣߥߣߢߢ
<ɉɍ> #SVOP $ E 4 0MJWFJSB BOE 8JMMJBN 3 $PPL &YUFOTJCJMJUZ GPS UIF .BTTFT1SBDUJDBM &YUFOTJCJMJUZ XJUI 0CKFDU "MHFCSBT *O 1SPDFFEJOHT PG UIF ȘɾUI &VSPQFBO$POGFSFODF PO 0CKFDU0SJFOUFE 1SPHSBNNJOH &$001 ƫɉɊ QBHFT ɊƦɊɏ ɊɈɉɊ ƇȩǞࡇߝߜࡏߝߜߜߣࡕߥߣߤࡷߟࡷߢߠߞࡷߟߝߜߡߣࡷߣ࡙ߞ
<ɉɎ> #SVOP $ E 4 0MJWFJSB 3BMG )JO[F BOE "OESFT -´I &YUFOTJCMF BOE .PEVMBS(FOFSJDT GPS UIF .BTTFT *O 5SFOET JO 'VODUJPOBM 1SPHSBNNJOH QBHFT ɉɑɑƦɊɉɎɊɈɈɎ<ɉɏ> +PIO $ 3FZOPMET 6TFSEFȸOFE 5ZQFT BOE 1SPDFEVSBM %BUB 4USVDUVSFT BT $PNQMF
NFOUBSZ "QQSPBDIFT UP 5ZQF "CTUSBDUJPO QBHFT ɋɈɑƦɋɉɏ ɉɑɏɐ ƇȩǞࡇߝߜࡏߝߜߜߣࡕߥߣߤࡷߝࡷ
ߠߢߝߞࡷߢߟߝߡࡷߥ࡙ߞߞ
<ɉɐ> 5JBSL 3PNQG BOE /BEB "NJO 'VODUJPOBM 1FBSM " 42- UP $ $PNQJMFS JO ɍɈɈ -JOFT
PG $PEF *O 1SPDFFEJOHT PG UIF ȘȖUI "$. 4*(1-"/ *OUFSOBUJPOBM $POGFSFODF PO'VODUJPOBM 1SPHSBNNJOH *$'1 ɊɈɉɍ QBHFT ɊƦɑ ɊɈɉɍ ƇȩǞࡇߝߜࡏߝߝߠߡࡕߞߣߤߠߣߟߝࡏߞߣߤߠߣߢߜ
<ɉɑ> 5JBSL 3PNQG BOE .BSUJO 0EFSTLZ -JHIUXFJHIU .PEVMBS 4UBHJOH " 1SBHNBUJD"QQSPBDI UP 3VOUJNF $PEF (FOFSBUJPO BOE $PNQJMFE %4-T *O 1SPDFFEJOHT PG
UIF /JOUI *OUFSOBUJPOBM $POGFSFODF PO (FOFSBUJWF 1SPHSBNNJOH BOE $PNQPOFOU&OHJOFFSJOH (1$& ƫɉɈ QBHFT ɉɊɏƦɉɋɎ ɊɈɉɈ ƇȩǞࡇߝߜࡏߝߝߠߡࡕߝߤߢߤߞߥߠࡏߝߤߢߤߟߝߠ
<ɊɈ> +PTFG 4WFOOJOHTTPO BOE &NJM "YFMTTPO $PNCJOJOH %FFQ BOE 4IBMMPX &NCFEEJOH
GPS &%4- *O 5SFOET JO 'VODUJPOBM 1SPHSBNNJOH QBHFT ɊɉƦɋɎ ɊɈɉɊ ƇȩǞࡇߝߜࡏߝߜߜߣࡕߥߣߤࡷ
ߟࡷߢߠߞࡷߠߜߠߠߣࡷߠ࡙ߞ
<Ɋɉ> 8PVUFS 4XJFSTUSB %BUB 5ZQFT  MB $BSUF +PVSOBM PG 'VODUJPOBM 1SPHSBNNJOH
ɉɐ ɈɌ ɌɊɋƦɌɋɎ ɊɈɈɐ ƇȩǞࡇߝߜࡏߝߜߝߣࡕëߜߥߡߢߣߥߢߤߜߤߜߜߢߣߡߤ
<ɊɊ> 1IJMJQ 8BEMFS 5IF &YQSFTTJPO 1SPCMFN /PUF UP +BWB (FOFSJDJUZ NBJMJOH MJTU /PWɉɑɑɐ
<Ɋɋ> :BOMJO 8BOH BOE #SVOP $ E 4 0MJWFJSB 5IF &YQSFTTJPO 1SPCMFN 5SJWJBMMZ *O
1SPDFFEJOHT PG UIF ȗɽUI *OUFSOBUJPOBM $POGFSFODF PO .PEVMBSJUZ .0%6-"3*5:ɊɈɉɎ QBHFT ɋɏƦɌɉ ɊɈɉɎ ƇȩǞࡇߝߜࡏߝߝߠߡࡕߞߤߤߥߠߠߟࡏߞߤߤߥߠߠߤ
<ɊɌ> )BPZVBO ;IBOH ;FXFJ $IV #SVOP $ E 4 0MJWFJSB BOE 5JKT WBO EFS 4UPSN 4DSBQ:PVS #PJMFSQMBUF XJUI 0CKFDU "MHFCSBT *O 1SPDFFEJOHT PG UIF ȘȖȗɽ "$. 4*(1-"/*OUFSOBUJPOBM $POGFSFODF PO 0CKFDU0SJFOUFE 1SPHSBNNJOH 4ZTUFNT -BOHVBHFT
BOE "QQMJDBUJPOT 0014-" ɊɈɉɍ QBHFT ɉɊɏƦɉɌɎ ɊɈɉɍ ƇȩǞࡇߝߜࡏߝߝߠߡࡕߞߤߝߠߞߣߜࡏߞߤߝߠߞߣߥ
<Ɋɍ> 8FJYJO ;IBOH &YUFOTJCMF %PNBJO4QFDJɯD -BOHVBHFT JO 0CKFDU0SJFOUFE 1SPHSBNNJOH ),6 5IFTFT 0OMJOF ),650 ɊɈɉɏߧߦࡇ ߨߪ

ĦƚǞʾǞȘ ĻǕŏȘǃ ŏȘƇ $ɟʕȘȩ +ࡏ Ƈࡏ ëࡏ °ȀǞʲƚǞɟŏųȩʕɾ ɾǕƚ ŏʕɾǕȩɟɯ

8FJYJO ;IBOH JT B 1I% DBOEJEBUF BU UIF 6OJWFSTJUZ PG )POH ,POH
)JT DVSSFOU SFTFBSDI JOUFSFTUT BSF DFOUFSFE BSPVOE NPEVMBSJUZEPNBJOTQFDJɯD MBOHVBHFT BOE HFOFSBUJWF QSPHSBNNJOH :PV DBO
DPOUBDU IJN BU ʶʾˌǕŏȘǃߞॅżɯࡏǕǺʕࡏǕǺ BOE ɯOE GVSUIFS JOGPSNBUJPOBU ǕɾɾɔɯࡇࡕࡕʶʾˌǕࡏǃǞɾǕʕųࡏǞȩ

#SVOP $ E 4 0MJWFJSB JT BO BTTJTUBOU QSPGFTTPS PG UIF BU UIF
6OJWFSTJUZ PG )POH ,POH )JT SFTFBSDI JOUFSFTUT BSF DFOUFSFEBSPVOE QSPHSBNNJOH MBOHVBHFT )JT FYJTUJOH SFTFBSDI JT NBJOMZGPDVTFE PO UZQF TZTUFNT GPS NPEVMBSJUZ BOE UIF DPNCJOBUJPOPG 0CKFDU0SJFOUFE BOE 'VODUJPOBM 1BSBEJHNT :PV DBO DPOUBDUIJN BU ųɟʕȘȩॅżɯࡏǕǺʕࡏǕǺ BOE ɯOE GVSUIFS JOGPSNBUJPO BU Ǖɾɾɔɯࡇ
ࡕࡕǞࡏżɯࡏǕǺʕࡏǕǺࡕࣂųɟʕȘȩߧߦࡇ ߨ߫