%!PS-Adobe-2.0 %%Creator: dvips 5.528 Copyright 1986, 1994 Radical Eye Software %%Title: noss.dvi %%Pages: 24 %%PageOrder: Ascend %%BoundingBox: 0 0 612 792 %%EndComments %DVIPSCommandLine: dvips noss.dvi -o noss.ps %DVIPSParameters: dpi=300, comments removed %DVIPSSource: TeX output 1994.07.21:1329 %%BeginProcSet: tex.pro /TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N /X{S N}B /TR{translate}N /isls false N /vsize 11 72 mul N /hsize 8.5 72 mul N /landplus90{false}def /@rigin{isls{[0 landplus90{1 -1}{-1 1} ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR matrix currentmatrix dup dup 4 get round 4 exch put dup dup 5 get round 5 exch put setmatrix}N /@landscape{/isls true N}B /@manualfeed{ statusdict /manualfeed true put}B /@copies{/#copies X}B /FMat[1 0 0 -1 0 0]N /FBB[0 0 0 0]N /nn 0 N /IE 0 N /ctr 0 N /df-tail{/nn 8 dict N nn begin /FontType 3 N /FontMatrix fntrx N /FontBBox FBB N string /base X array /BitMaps X /BuildChar{CharBuilder}N /Encoding IE N end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /df{/sf 1 N /fntrx FMat N df-tail}B /dfs{div /sf X /fntrx[sf 0 0 sf neg 0 0]N df-tail}B /E{ pop nn dup definefont setfont}B /ch-width{ch-data dup length 5 sub get} B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup type /stringtype ne{ctr get /ctr ctr 1 add N}if}B /id 0 N /rw 0 N /rc 0 N /gp 0 N /cp 0 N /G 0 N /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 add]{ ch-image}imagemask restore}B /D{/cc X dup type /stringtype ne{]}if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1 sub dup 2 index S get sf div put}if put /ctr ctr 1 add N}B /I{cc 1 add D }B /bop{userdict /bop-hook known{bop-hook}if /SI save N @rigin 0 0 moveto /V matrix currentmatrix dup 1 get dup mul exch 0 get dup mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N /eop{SI restore showpage userdict /eop-hook known{eop-hook}if}N /@start{userdict /start-hook known{start-hook}if pop /VResolution X /Resolution X 1000 div /DVImag X /IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for 65781.76 div /vsize X 65781.76 div /hsize X}N /p{show}N /RMat[1 0 0 -1 0 0]N /BDot 260 string N /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V {}B /RV statusdict begin /product where{pop product dup length 7 ge{0 7 getinterval dup(Display)eq exch 0 4 getinterval(NeXT)eq or}{pop false} ifelse}{false}ifelse end{{gsave TR -.1 -.1 TR 1 1 scale rulex ruley false RMat{BDot}imagemask grestore}}{{gsave TR -.1 -.1 TR rulex ruley scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave transform round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail{dup /delta X 0 rmoveto}B /M{S p delta add tail}B /b{S p tail} B /c{-4 M}B /d{-3 M}B /e{-2 M}B /f{-1 M}B /g{0 M}B /h{1 M}B /i{2 M}B /j{ 3 M}B /k{4 M}B /w{0 rmoveto}B /l{p -4 w}B /m{p -3 w}B /n{p -2 w}B /o{p -1 w}B /q{p 1 w}B /r{p 2 w}B /s{p 3 w}B /t{p 4 w}B /x{0 S rmoveto}B /y{ 3 2 roll p a}B /bos{/SS save N}B /eos{SS restore}B end %%EndProcSet TeXDict begin 40258431 52099146 1095 300 300 (/home/anarres/g/users/bh/papers/noss.dvi) @start /Fa 1 111 df<383C004CC7004F03004E03009C07001C07001C07001C0E00380E00380E4038 1C40381C80700C80300700120E7E8D16>110 D E /Fb 4 52 df<0FC018603030703860 186018E01CE01CE01CE01CE01CE01CE01CE01CE01CE01C60187038303018600FC00E157F 9412>48 D<03000700FF0007000700070007000700070007000700070007000700070007 0007000700070007007FF00C157E9412>I<1F0021C040E080E0C070E070407000F000E0 00E001C001800300060004000810101020303FE07FE0FFE00C157E9412>I<0FC0306060 707078703800780070007000E007C0006000780038003C003CE03CE03CC038407830600F C00E157F9412>I E /Fc 12 121 df<70F8F8F87005057C840D>58 D<70F8FCFC74040404080810102040060E7C840D>I62 D<00000200000006000000 0E0000000E0000001E0000001F0000002F0000002F0000004F0000008F0000008F000001 0F0000010F0000020F0000040F0000040F0000080F800008078000100780002007800020 0780007FFF800040078000800780018007800100078002000780020007C0040003C00C00 03C01E0007C0FF807FFC1E207E9F22>65 D<00FFFFE0000F0078000F003C000F001C000F 001E001E001E001E001E001E001E001E001E003C003C003C003C003C0078003C00F00078 03C0007FFF80007803C0007801E000F000F000F000F000F000F000F0007001E000F001E0 00F001E000F001E000E003C001E003C003C003C0038003C00F0007801E00FFFFF0001F1F 7E9E22>I<0000FE0200078186001C004C0038003C0060003C00C0001C01C00018038000 18070000180F0000181E0000101E0000103C0000003C0000007800000078000000780000 0078000000F0000000F0000000F0000000F0000000F00000807000008070000080700001 003800010038000200180004000C001800060020000381C00000FE00001F217E9F21>I< 00F1800389C00707800E03801C03803C0380380700780700780700780700F00E00F00E00 F00E00F00E10F01C20F01C20703C20705C40308C400F078014147E9318>97 D<07803F8007000700070007000E000E000E000E001C001C001CF01D0C3A0E3C0E380F38 0F700F700F700F700FE01EE01EE01EE01CE03CE038607060E031C01F0010207E9F14>I< 00007C0000CE00019E00039E00030C000700000700000700000700000E00000E00000E00 00FFF0000E00000E00001C00001C00001C00001C00001C00003800003800003800003800 00380000700000700000700000700000700000E00000E00000E00000E00000C00001C000 318000798000F300006200003C000017297E9F16>102 D<001E3000713800E0F001C070 0380700780700700E00F00E00F00E00F00E01E01C01E01C01E01C01E01C01E03801E0380 0E07800E0B8006170001E700000700000700000E00000E00300E00781C00F03800607000 3FC000151D809316>I<1E07802318C023A06043C0704380704380708700E00700E00700 E00700E00E01C00E01C00E01C00E03821C03841C07041C07081C03083803101801E01714 7E931B>110 D<03C1C00C62201034701038F02038F02038604070000070000070000070 0000E00000E00000E00000E02061C040F1C040F1C080E2C080446300383C0014147E931A >120 D E /Fd 72 121 df<70F8F8F8F8F8F8F8F8F8F8F8F8F8F8F8F870000000000070 F8F8F870051C779B18>33 D<4010E038F078E038E038E038E038E038E038E038E038E038 E03860300D0E7B9C18>I<030600078F00078F00078F00078F00078F00078F007FFFC0FF FFE0FFFFE07FFFC00F1E000F1E000F1E000F1E000F1E000F1E007FFFC0FFFFE0FFFFE07F FFC01E3C001E3C001E3C001E3C001E3C001E3C000C1800131C7E9B18>I<387C7C7E3E0E 0E0E1C1C38F8F0C0070E789B18>39 D<007000F001E003C007800F001E001C0038003800 7000700070007000E000E000E000E000E000E000E000E000700070007000700038003800 1C001E000F00078003C001F000F000700C24799F18>I<6000F00078003C001E000F0007 80038001C001C000E000E000E000E00070007000700070007000700070007000E000E000 E000E001C001C0038007800F001E003C007800F00060000C247C9F18>I<01C00001C000 01C00001C000C1C180F1C780F9CF807FFF001FFC0007F00007F0001FFC007FFF00F9CF80 F1C780C1C18001C00001C00001C00001C00011147D9718>I<00600000F00000F00000F0 0000F00000F00000F00000F0007FFFC0FFFFE0FFFFE07FFFC000F00000F00000F00000F0 0000F00000F00000F00000600013147E9718>I<1C3E7E7F3F1F070E1E7CF860080C7885 18>I<7FFF00FFFF80FFFF807FFF0011047D8F18>I<3078FCFC78300606778518>I<0003 00000780000780000F80000F00001F00001E00001E00003E00003C00007C000078000078 0000F80000F00001F00001E00003E00003C00003C00007C0000780000F80000F00000F00 001F00001E00003E00003C00003C00007C0000780000F80000F00000F000006000001124 7D9F18>I<01F00007FC000FFE001F1F001C07003803807803C07001C07001C0E000E0E0 00E0E000E0E000E0E000E0E000E0E000E0E000E0E000E0F001E07001C07001C07803C038 03801C07001F1F000FFE0007FC0001F000131C7E9B18>I<01800380038007800F803F80 FF80FB804380038003800380038003800380038003800380038003800380038003800380 03807FFCFFFE7FFC0F1C7B9B18>I<03F0000FFE003FFF007C0F807003C0E001C0F000E0 F000E06000E00000E00000E00001C00001C00003C0000780000F00001E00003C00007800 00F00001E00007C0000F80001E00E03C00E07FFFE0FFFFE07FFFE0131C7E9B18>I<07F8 001FFE003FFF007807807803C07801C03001C00001C00003C0000380000F0003FF0003FE 0003FF000007800003C00001C00000E00000E00000E0F000E0F000E0F001C0F003C07C07 803FFF001FFE0003F800131C7E9B18>I<001F00003F0000770000770000E70001E70001 C7000387000787000707000E07001E07003C0700380700780700F00700FFFFF8FFFFF8FF FFF8000700000700000700000700000700000700007FF000FFF8007FF0151C7F9B18>I< 1FFF803FFF803FFF803800003800003800003800003800003800003800003800003BF800 3FFE003FFF003C07801803C00001C00000E00000E06000E0F000E0F000E0E001C07003C0 7C0F803FFF001FFC0003F000131C7E9B18>I<007E0001FF0007FF800F83C01E03C01C03 C0380180380000700000700000E1F800E7FE00FFFF00FE0780F803C0F001C0F000E0E000 E0F000E07000E07000E07000E03801C03C03C01E07800FFF0007FE0001F800131C7E9B18 >II<03F8000FFE001FFF003E0F80 3803807001C07001C07001C07001C03803803C07801FFF0007FC000FFE001F1F003C0780 7001C0F001E0E000E0E000E0E000E0E000E07001C07803C03E0F801FFF000FFE0003F800 131C7E9B18>I<03F0000FFC001FFE003C0F00780780700380E001C0E001C0E001C0E001 E0E001E07001E07803E03C0FE01FFFE00FFEE003F0E00000E00001C00001C00001C03003 80780780780F00783E003FFC001FF00007C000131C7E9B18>I<3078FCFC783000000000 000000003078FCFC78300614779318>I<183C7E7E3C180000000000000000183C7E7E3E 1E0E1C3C78F060071A789318>I<000300000780001F80003F00007E0001FC0003F00007 E0001FC0003F00007E0000FC0000FC00007E00003F00001FC00007E00003F00001FC0000 7E00003F00001F8000078000030011187D9918>I<7FFFC0FFFFE0FFFFE0FFFFE0000000 000000000000000000FFFFE0FFFFE0FFFFE07FFFC0130C7E9318>I<0FF0003FFC007FFF 00700F00F00380F00380600780000F00003E00007C0001F00001E00003C00003C00003C0 0003C00003C00003800000000000000000000000000000000003800007C00007C00007C0 00038000111C7D9B18>63 D<00700000F80000F80000D80000D80001DC0001DC0001DC00 018C00038E00038E00038E00038E000306000707000707000707000707000FFF800FFF80 0FFF800E03800E03801C01C01C01C07F07F0FF8FF87F07F0151C7F9B18>65 DI<00F8E003FEE007FFE00F07E01E03E03C 01E03800E07000E07000E0700000E00000E00000E00000E00000E00000E00000E00000E0 00007000007000E07000E03800E03C00E01E01C00F07C007FF8003FE0000F800131C7E9B 18>I<7FF800FFFE007FFF001C0F801C03C01C03C01C01E01C00E01C00E01C00F01C0070 1C00701C00701C00701C00701C00701C00701C00701C00F01C00E01C00E01C01E01C01C0 1C03C01C0F807FFF00FFFE007FF800141C7F9B18>III<01F1C003FDC00FFFC01F0FC0 1C03C03803C03801C07001C07001C0700000E00000E00000E00000E00000E00000E00FF0 E01FF0E00FF07001C07001C07003C03803C03803C01C07C01F0FC00FFFC003FDC001F1C0 141C7E9B18>I<7F07F0FF8FF87F07F01C01C01C01C01C01C01C01C01C01C01C01C01C01 C01C01C01C01C01FFFC01FFFC01FFFC01C01C01C01C01C01C01C01C01C01C01C01C01C01 C01C01C01C01C01C01C07F07F0FF8FF87F07F0151C7F9B18>I<7FFF00FFFF807FFF0001 C00001C00001C00001C00001C00001C00001C00001C00001C00001C00001C00001C00001 C00001C00001C00001C00001C00001C00001C00001C00001C00001C0007FFF00FFFF807F FF00111C7D9B18>I<01FFC003FFC001FFC0000E00000E00000E00000E00000E00000E00 000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00 000E00F00E00F00E00F03C007FFC003FF0000FC000121C7D9B18>I<7F07F0FF87F87F07 F01C03C01C07801C07001C0E001C1E001C3C001C38001C70001CF0001DF0001DF0001FB8 001FB8001F1C001E1C001C0E001C0E001C07001C07001C03801C03801C01C07F03F0FF87 F87F03F0151C7F9B18>I<7FE000FFE0007FE0000E00000E00000E00000E00000E00000E 00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E 00700E00700E00700E00700E00707FFFF0FFFFF07FFFF0141C7F9B18>II<7E07F0FF0FF87F07F01D81C01D81C01D81C01DC1C01CC1 C01CC1C01CE1C01CE1C01CE1C01C61C01C71C01C71C01C31C01C39C01C39C01C39C01C19 C01C19C01C1DC01C0DC01C0DC01C0DC07F07C0FF87C07F03C0151C7F9B18>I<0FF8003F FE007FFF00780F00700700F00780E00380E00380E00380E00380E00380E00380E00380E0 0380E00380E00380E00380E00380E00380E00380E00380E00380F00780700700780F007F FF003FFE000FF800111C7D9B18>II<0FF8 003FFE007FFF00780F00700700F00780E00380E00380E00380E00380E00380E00380E003 80E00380E00380E00380E00380E00380E00380E00380E1E380E1E380F0E78070F700787F 007FFF003FFE000FFC00001C00001E00000E00000F0000070000070011227D9B18>I<7F F800FFFE007FFF001C0F801C03801C03C01C01C01C01C01C01C01C03C01C03801C0F801F FF001FFE001FFE001C0F001C07001C03801C03801C03801C03801C03801C039C1C039C1C 039C7F01F8FF81F87F00F0161C7F9B18>I<03F3801FFF803FFF807C0F80700780E00380 E00380E00380E000007000007800003F00001FF00007FE0000FF00000F800003C00001C0 0000E00000E06000E0E000E0E001E0F001C0F80780FFFF80FFFE00E7F800131C7E9B18> I<7FFFF8FFFFF8FFFFF8E07038E07038E07038E070380070000070000070000070000070 000070000070000070000070000070000070000070000070000070000070000070000070 0000700007FF0007FF0007FF00151C7F9B18>IIII<7F8FE07F9FE07F8FE00E07000F0700070E00078E00039C0003DC0001F80001 F80000F00000F00000700000F00000F80001F80001DC00039E00038E00070F000707000E 07800E03801E03C07F07F0FF8FF87F07F0151C7F9B18>II91 D93 D<1FE0003FF8007FFC00781E0030 0E0000070000070000FF0007FF001FFF007F0700780700E00700E00700E00700F00F0078 1F003FFFF01FFBF007E1F014147D9318>97 D<7E0000FE00007E00000E00000E00000E00 000E00000E00000E3E000EFF800FFFC00FC1E00F80E00F00700E00700E00380E00380E00 380E00380E00380E00380F00700F00700F80E00FC1E00FFFC00EFF80063E00151C809B18 >I<01FE0007FF001FFF803E0780380300700000700000E00000E00000E00000E00000E0 0000E000007000007001C03801C03E03C01FFF8007FF0001FC0012147D9318>I<001F80 003F80001F8000038000038000038000038000038003E3800FFB801FFF803C1F80380F80 700780700380E00380E00380E00380E00380E00380E00380700780700780380F803C1F80 1FFFF00FFBF803E3F0151C7E9B18>I<01F00007FC001FFE003E0F003807807003807003 80E001C0E001C0FFFFC0FFFFC0FFFFC0E000007000007001C03801C03E03C01FFF8007FF 0001FC0012147D9318>I<7E0000FE00007E00000E00000E00000E00000E00000E00000E 3E000EFF800FFFC00FC1C00F80E00F00E00E00E00E00E00E00E00E00E00E00E00E00E00E 00E00E00E00E00E00E00E00E00E07FC3FCFFE7FE7FC3FC171C809B18>104 D<03800007C00007C00007C0000380000000000000000000000000007FC000FFC0007FC0 0001C00001C00001C00001C00001C00001C00001C00001C00001C00001C00001C00001C0 0001C00001C000FFFF00FFFF80FFFF00111D7C9C18>I<7FE000FFE0007FE00000E00000 E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000 E00000E00000E00000E00000E00000E00000E00000E00000E0007FFFC0FFFFE07FFFC013 1C7E9B18>108 D<7CE0E000FFFBF8007FFFF8001F1F1C001E1E1C001E1E1C001C1C1C00 1C1C1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C001C1C1C00 1C1C1C007F1F1F00FFBFBF807F1F1F001914819318>I<7E3E00FEFF807FFFC00FC1C00F 80E00F00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E00E 00E07FC3FCFFE7FE7FC3FC1714809318>I<01F0000FFE001FFF003E0F803803807001C0 7001C0E000E0E000E0E000E0E000E0E000E0F001E07001C07803C03C07803E0F801FFF00 0FFE0001F00013147E9318>I<7E3E00FEFF807FFFC00FC1E00F80E00F00700E00700E00 380E00380E00380E00380E00380E00380F00700F00700F80E00FC1E00FFFC00EFF800E3E 000E00000E00000E00000E00000E00000E00000E00007FC000FFE0007FC000151E809318 >I<7F87E0FF9FF07FBFF803F87803F03003E00003C00003C00003800003800003800003 80000380000380000380000380000380007FFE00FFFF007FFE0015147F9318>114 D<07F7003FFF007FFF00780F00E00700E00700E007007C00007FE0001FFC0003FE00001F 00600780E00380E00380F00380F80F00FFFF00FFFC00E7F00011147D9318>I<01800003 80000380000380000380007FFFC0FFFFC0FFFFC003800003800003800003800003800003 80000380000380000380000380400380E00380E00380E001C1C001FFC000FF80003E0013 197F9818>I<7E07E0FE0FE07E07E00E00E00E00E00E00E00E00E00E00E00E00E00E00E0 0E00E00E00E00E00E00E00E00E00E00E01E00F03E007FFFC03FFFE01FCFC1714809318> I119 D<7F8FF07F9FF07F8FF0070700078E00039E0001DC0001F80000F80000700000F00000F8 0001DC00039E00038E000707000F07807F8FF0FF8FF87F8FF015147F9318>I E /Fe 2 3 df0 D<400004C0000C6000183000301800 600C00C006018003030001860000CC0000780000300000300000780000CC000186000303 000601800C00C0180060300030600018C0000C40000416187A9623>2 D E /Ff 3 27 df<00000C0000180000300000600000C00001C000038000070000060000 0E00001C00001C0000380000700000700000E00000E00001E00001C00003C00003800003 80000780000700000700000F00000E00000E00001E00001E00001C00003C00003C00003C 00003C0000380000780000780000780000780000780000780000780000700000F00000F0 0000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F00000F0 0000F00000F00000F00000F00000F00000F0000070000078000078000078000078000078 00007800007800003800003C00003C00003C00003C00001C00001E00001E00000E00000E 00000F000007000007000007800003800003800003C00001C00001E00000E00000E00000 7000007000003800001C00001C00000E000006000007000003800001C00000C000006000 003000001800000C166C778121>18 DI<0000380000780001F00003C000 0780000F00001E00001E00003C00003C0000780000780000780000780000780000780000 780000780000780000780000780000780000780000780000780000780000780000780000 780000780000780000780000780000780000780000780000780000780000780000780000 780000780000780000780000F00000F00001E00001E00003C0000780000F00001E000078 0000F00000F000007800001E00000F000007800003C00001E00001E00000F00000F00000 780000780000780000780000780000780000780000780000780000780000780000780000 780000780000780000780000780000780000780000780000780000780000780000780000 7800007800007800007800007800007800007800007800007800007800003C00003C0000 1E00001E00000F000007800003C00001F0000078000038156C7A8122>26 D E /Fg 41 122 df<00003FE00000E01000018038000380780003007800070030000700 000007000000070000000E0000000E0000000E000000FFFFE0000E00E0001C01C0001C01 C0001C01C0001C01C0001C03800038038000380380003803800038070000380700007007 000070071000700E2000700E2000700E2000E00E2000E0064000E0038000E0000000C000 0001C0000001C000003180000079800000F3000000620000003C0000001D29829F1A>12 D<1C3C3C3C3C040408081020204080060E7D840E>44 D<7FF0FFE07FE00C037D8A10>I< 0007C0001C200030200060E000C1E00181E00380C00700000F00000E00001E00001E7800 1D84003E06003E07003C07007C0780780780780780780780700F00700F00F00F00F00E00 F01E00701C00601C0070380030700010C0000F8000131F7B9D17>54 D<001F000061800080C00100600300600600600600600600600E00C00F00800F818007C3 0007E40003F80001F80003FC00047E00183F00300F00200700600700C00300C00300C003 00800600800600C00C00C008004030003060001F8000131F7B9D17>56 D<00000200000006000000060000000E0000001E0000001E0000003F0000002F0000004F 0000004F0000008F0000010F0000010F0000020F0000020F0000040F00000C0F0000080F 0000100F0000100F0000200F80003FFF800040078000C007800080078001000780010007 800200078002000780060007801E000F80FF807FF81D207E9F22>65 D<0000FE0200078186001C004C0038003C0060003C00C0001C01C0001803800018070000 180F0000181E0000101E0000103C0000003C000000780000007800000078000000780000 00F0000000F0000000F0000000F0000000F0000080700000807000008070000100380001 0038000200180004000C001800060020000381C00000FE00001F217A9F21>67 D<01FFFFFE001E001C001E000C001E0004001E0004003C0004003C0004003C0004003C00 040078080800780800007808000078180000F0300000FFF00000F0300000F0300001E020 0001E0200001E0200001E0001003C0002003C0002003C0004003C0004007800080078001 8007800100078007000F001F00FFFFFE001F1F7D9E1F>69 D<01FFF0001F00001E00001E 00001E00003C00003C00003C00003C0000780000780000780000780000F00000F00000F0 0000F00001E00001E00001E00001E00003C00003C00003C00003C0000780000780000780 000780000F8000FFF800141F7D9E12>73 D<01FFF800001F0000001E0000001E0000001E 0000003C0000003C0000003C0000003C00000078000000780000007800000078000000F0 000000F0000000F0000000F0000001E0000001E0000001E0000001E0008003C0010003C0 010003C0030003C00200078006000780060007800C0007801C000F007800FFFFF800191F 7D9E1D>76 D<01FE00007FC0001E0000FC00001E0000F800001700017800001700017800 00270002F00000270004F00000270004F00000270008F00000470009E00000470011E000 00470021E00000470021E00000870043C00000838043C00000838083C00000838083C000 0103810780000103820780000103820780000103840780000203840F00000203880F0000 0203900F00000203900F00000401E01E00000401E01E00000401C01E00000C01801E0000 1C01803E0000FF8103FFC0002A1F7D9E29>I<01FFFF80001E00E0001E0070001E003800 1E003C003C003C003C003C003C003C003C003C0078007800780078007800F0007800E000 F003C000F00F0000FFFC0000F0000001E0000001E0000001E0000001E0000003C0000003 C0000003C0000003C00000078000000780000007800000078000000F800000FFF000001E 1F7D9E1F>80 D<0007E040001C18C0003005800060038000C0038001C001800180010003 80010003800100038001000380000003C0000003C0000003F8000001FF800001FFE00000 7FF000001FF0000001F80000007800000078000000380000003800200038002000380020 00300060007000600060006000E0007000C000E8038000C606000081F800001A217D9F1A >83 D<0FFFFFF01E0780E0180780201007802020078020200F0020600F0020400F002040 0F0020801E0040001E0000001E0000001E0000003C0000003C0000003C0000003C000000 78000000780000007800000078000000F0000000F0000000F0000000F0000001E0000001 E0000001E0000001E0000003E00000FFFF00001C1F789E21>I<001FC0001FC000180000 180000300000300000300000300000600000600000600000600000C00000C00000C00000 C00001800001800001800001800003000003000003000003000006000006000006000006 00000C00000C00000C00000C000018000018000018000018000030000030000030000030 00006000006000006000007F0000FE0000122D7EA10E>91 D<001FC0001FC00000C00000 C00001800001800001800001800003000003000003000003000006000006000006000006 00000C00000C00000C00000C000018000018000018000018000030000030000030000030 0000600000600000600000600000C00000C00000C00000C0000180000180000180000180 000300000300000300007F0000FE0000122D82A10E>93 D<00F1800389C00707800E0380 1C03803C0380380700780700780700780700F00E00F00E00F00E00F00E20F01C40F01C40 703C40705C40308C800F070013147C9317>97 D<07803F8007000700070007000E000E00 0E000E001C001C001CF01D0C3A0E3C0E380F380F700F700F700F700FE01EE01EE01EE01C E03CE038607060E031C01F0010207B9F15>I<007E0001C1000300800E07801E07801C07 003C0200780000780000780000F00000F00000F00000F00000F000007001007002003004 0018380007C00011147C9315>I<0000780003F80000700000700000700000700000E000 00E00000E00000E00001C00001C000F1C00389C00707800E03801C03803C038038070078 0700780700780700F00E00F00E00F00E00F00E20F01C40F01C40703C40705C40308C800F 070015207C9F17>I<007C01C207010E011C013C013802780C7BF07C00F000F000F000F0 007000700170023804183807C010147C9315>I<00007800019C00033C00033C00071800 0700000700000E00000E00000E00000E00000E0001FFE0001C00001C00001C00001C0000 380000380000380000380000380000700000700000700000700000700000700000E00000 E00000E00000E00000C00001C00001C0000180003180007B0000F300006600003C000016 29829F0E>I<003C6000E27001C1E00380E00700E00F00E00E01C01E01C01E01C01E01C0 3C03803C03803C03803C03803C07003C07001C0F001C17000C2E0003CE00000E00000E00 001C00001C00301C00783800F0700060E0003F8000141D7E9315>I<01E0000FE00001C0 0001C00001C00001C000038000038000038000038000070000070000071E000763000E81 800F01C00E01C00E01C01C03801C03801C03801C0380380700380700380700380E10700E 20700C20701C20700C40E00CC060070014207D9F17>I<00C001E001E001C00000000000 0000000000000000000E003300230043804300470087000E000E000E001C001C001C0038 40388030807080310033001C000B1F7C9E0E>I<0001800003C00003C000038000000000 0000000000000000000000000000000000003C0000460000870000870001070001070002 0E00000E00000E00000E00001C00001C00001C00001C0000380000380000380000380000 700000700000700000700000E00000E00030E00079C000F180006300003C00001228829E 0E>I<01E0000FE00001C00001C00001C00001C000038000038000038000038000070000 0700000703C00704200E08E00E11E00E21E00E40C01C80001D00001E00001FC00038E000 387000387000383840707080707080707080703100E03100601E0013207D9F15>I<03C0 1FC0038003800380038007000700070007000E000E000E000E001C001C001C001C003800 3800380038007000700070007100E200E200E200E200640038000A207C9F0C>I<1C0F80 F0002630C318004740640C004780680E004700700E004700700E008E00E01C000E00E01C 000E00E01C000E00E01C001C01C038001C01C038001C01C038001C01C070803803807100 3803806100380380E10038038062007007006600300300380021147C9325>I<1C0F8026 30C04740604780604700704700708E00E00E00E00E00E00E00E01C01C01C01C01C01C01C 03843803883803083807083803107003303001C016147C931A>I<007C0001C300030180 0E01C01E01C01C01E03C01E07801E07801E07801E0F003C0F003C0F003C0F00780F00700 700F00700E0030180018700007C00013147C9317>I<01C1E002621804741C04781C0470 1E04701E08E01E00E01E00E01E00E01E01C03C01C03C01C03C01C0380380780380700380 E003C1C0072380071E000700000700000E00000E00000E00000E00001C00001C0000FFC0 00171D809317>I<00F0400388C00705800E03801C03803C038038070078070078070078 0700F00E00F00E00F00E00F00E00F01C00F01C00703C00705C0030B8000F380000380000 380000700000700000700000700000E00000E0000FFE00121D7C9315>I<1C1E00266100 4783804787804707804703008E00000E00000E00000E00001C00001C00001C00001C0000 38000038000038000038000070000030000011147C9313>I<00FC030206010C030C070C 060C000F800FF007F803FC003E000E700EF00CF00CE008401020601F8010147D9313>I< 018001C0038003800380038007000700FFF007000E000E000E000E001C001C001C001C00 3800380038003820704070407080708031001E000C1C7C9B0F>I<0E00C03300E02301C0 4381C04301C04701C08703800E03800E03800E03801C07001C07001C07001C07101C0E20 180E20180E201C1E200C264007C38014147C9318>I<0E03803307802307C04383C04301 C04700C08700800E00800E00800E00801C01001C01001C01001C02001C02001C04001C04 001C08000E300003C00012147C9315>I<0E00C1C03300E3C02301C3E04381C1E04301C0 E04701C060870380400E0380400E0380400E0380401C0700801C0700801C0700801C0701 001C0701001C0602001C0F02000C0F04000E13080003E1F0001B147C931E>I<0383800C C4401068E01071E02071E02070C040E00000E00000E00000E00001C00001C00001C00001 C040638080F38080F38100E5810084C60078780013147D9315>I<0E00C03300E02301C0 4381C04301C04701C08703800E03800E03800E03801C07001C07001C07001C07001C0E00 180E00180E001C1E000C3C0007DC00001C00001C00003800F03800F07000E06000C0C000 4380003E0000131D7C9316>I E /Fh 80 124 df<001F83E000F06E3001C078780380F8 780300F03007007000070070000700700007007000070070000700700007007000FFFFFF 800700700007007000070070000700700007007000070070000700700007007000070070 000700700007007000070070000700700007007000070070000700700007007000070070 007FE3FF001D20809F1B>11 D<003F0000E0C001C0C00381E00701E00701E00700000700 00070000070000070000070000FFFFE00700E00700E00700E00700E00700E00700E00700 E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E00700E07FC3 FE1720809F19>I<003FE000E0E001C1E00381E00700E00700E00700E00700E00700E007 00E00700E00700E0FFFFE00700E00700E00700E00700E00700E00700E00700E00700E007 00E00700E00700E00700E00700E00700E00700E00700E00700E00700E07FE7FE1720809F 19>I<001F81F80000F04F040001C07C06000380F80F000300F00F000700F00F00070070 000007007000000700700000070070000007007000000700700000FFFFFFFF0007007007 000700700700070070070007007007000700700700070070070007007007000700700700 070070070007007007000700700700070070070007007007000700700700070070070007 00700700070070070007007007007FE3FE3FF02420809F26>I<70F8F8F8F8F8F8F87070 70707070707070702020202020000000000070F8F8F87005217CA00D>33 D<7038F87CFC7EFC7E743A0402040204020804080410081008201040200F0E7E9F17>I< 70F8FCFC74040404080810102040060E7C9F0D>39 D<0020004000800100020006000C00 0C00180018003000300030007000600060006000E000E000E000E000E000E000E000E000 E000E000E000E0006000600060007000300030003000180018000C000C00060002000100 0080004000200B2E7DA112>I<800040002000100008000C000600060003000300018001 80018001C000C000C000C000E000E000E000E000E000E000E000E000E000E000E000E000 C000C000C001C001800180018003000300060006000C00080010002000400080000B2E7D A112>I<0006000000060000000600000006000000060000000600000006000000060000 00060000000600000006000000060000000600000006000000060000FFFFFFF0FFFFFFF0 000600000006000000060000000600000006000000060000000600000006000000060000 0006000000060000000600000006000000060000000600001C207D9A23>43 D<70F8FCFC74040404080810102040060E7C840D>II<70F8F8F8 7005057C840D>I<03F0000E1C001C0E00180600380700700380700380700380700380F0 03C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0F003C0F0 03C07003807003807003807807803807001806001C0E000E1C0003F000121F7E9D17>48 D<018003800F80F380038003800380038003800380038003800380038003800380038003 80038003800380038003800380038003800380038007C0FFFE0F1E7C9D17>I<03F0000C 1C00100E00200700400780800780F007C0F803C0F803C0F803C02007C00007C000078000 0780000F00000E00001C0000380000700000600000C0000180000300000600400C004018 00401000803FFF807FFF80FFFF80121E7E9D17>I<03F0000C1C00100E00200F00780F80 780780780780380F80000F80000F00000F00000E00001C0000380003F000003C00000E00 000F000007800007800007C02007C0F807C0F807C0F807C0F00780400780400F00200E00 1C3C0003F000121F7E9D17>I<000600000600000E00000E00001E00002E00002E00004E 00008E00008E00010E00020E00020E00040E00080E00080E00100E00200E00200E00400E 00C00E00FFFFF0000E00000E00000E00000E00000E00000E00000E0000FFE0141E7F9D17 >I<1803001FFE001FFC001FF8001FE00010000010000010000010000010000010000011 F000161C00180E001007001007800003800003800003C00003C00003C07003C0F003C0F0 03C0E00380400380400700200600100E000C380003E000121F7E9D17>I<007C00018200 0701000E03800C07801C0780380300380000780000700000700000F1F000F21C00F40600 F80700F80380F80380F003C0F003C0F003C0F003C0F003C07003C07003C0700380380380 3807001807000C0E00061C0001F000121F7E9D17>I<4000007FFFC07FFF807FFF804001 0080020080020080040000080000080000100000200000200000400000400000C00000C0 0001C0000180000380000380000380000380000780000780000780000780000780000780 00078000030000121F7D9D17>I<03F0000C0C0010060030030020018060018060018060 01807001807803003E03003F06001FC8000FF00003F80007FC000C7E00103F00300F8060 03804001C0C001C0C000C0C000C0C000C0C000806001802001001002000C0C0003F00012 1F7E9D17>I<03F0000E18001C0C00380600380700700700700380F00380F00380F003C0 F003C0F003C0F003C0F003C07007C07007C03807C0180BC00E13C003E3C0000380000380 000380000700300700780600780E00700C002018001070000FC000121F7E9D17>I<70F8 F8F8700000000000000000000070F8F8F87005147C930D>I<70F8F8F870000000000000 0000000070F0F8F878080808101010202040051D7C930D>I<7FFFFFE0FFFFFFF0000000 0000000000000000000000000000000000000000000000000000000000FFFFFFF07FFFFF E01C0C7D9023>61 D<0FC0307040384038E03CF03CF03C603C0038007000E000C0018001 80010003000200020002000200020002000000000000000000000007000F800F800F8007 000E207D9F15>63 D<000100000003800000038000000380000007C0000007C0000007C0 000009E0000009E0000009E0000010F0000010F0000010F0000020780000207800002078 0000403C0000403C0000403C0000801E0000801E0000FFFE0001000F0001000F0001000F 00020007800200078002000780040003C00E0003C01F0007E0FFC03FFE1F207F9F22>65 DI<000FC040007030C001C009C0 038005C0070003C00E0001C01E0000C01C0000C03C0000C07C0000407C00004078000040 F8000000F8000000F8000000F8000000F8000000F8000000F8000000F8000000F8000000 780000007C0000407C0000403C0000401C0000401E0000800E0000800700010003800200 01C0040000703800000FC0001A217D9F21>IIII<000FE0200078186000E004E0038002E0070001E0 0F0000E01E0000601E0000603C0000603C0000207C00002078000020F8000000F8000000 F8000000F8000000F8000000F8000000F8000000F8007FFCF80003E0780001E07C0001E0 3C0001E03C0001E01E0001E01E0001E00F0001E0070001E0038002E000E0046000781820 000FE0001E217D9F24>III<0FFFC0007C 00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C00003C 00003C00003C00003C00003C00003C00003C00003C00003C00003C00203C00F83C00F83C 00F83C00F0380040780040700030E0000F800012207E9E17>I76 D II<001F800000F0F00001C03800 07801E000F000F000E0007001E0007803C0003C03C0003C07C0003E0780001E0780001E0 F80001F0F80001F0F80001F0F80001F0F80001F0F80001F0F80001F0F80001F0F80001F0 780001E07C0003E07C0003E03C0003C03C0003C01E0007800E0007000F000F0007801E00 01C0380000F0F000001F80001C217D9F23>II82 D<07E0800C1980100780300380600180600180E00180E00080E00080E00080F00000F000 007800007F00003FF0001FFC000FFE0003FF00001F800007800003C00003C00001C08001 C08001C08001C08001C0C00180C00380E00300F00600CE0C0081F80012217D9F19>I<7F FFFFE0780F01E0600F0060400F0020400F0020C00F0030800F0010800F0010800F001080 0F0010000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F000000 0F0000000F0000000F0000000F0000000F0000000F0000000F0000000F0000000F000000 0F0000000F0000001F800007FFFE001C1F7E9E21>IIII89 D91 D<080410082010201040204020804080408040B85CFC7EFC7E7C3E381C0F0E7B9F17>I< FEFE06060606060606060606060606060606060606060606060606060606060606060606 06060606060606FEFE072D7FA10D>I<081020204040808080B8FCFC7C38060E7D9F0D> 96 D<1FE000303000781800781C00300E00000E00000E00000E0000FE00078E001E0E00 380E00780E00F00E10F00E10F00E10F01E10781E103867200F83C014147E9317>I<0E00 00FE00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E00000E3E 000EC3800F01C00F00E00E00E00E00700E00700E00780E00780E00780E00780E00780E00 780E00700E00700E00E00F00E00D01C00CC300083E0015207F9F19>I<03F80E0C1C1E38 1E380C70007000F000F000F000F000F000F00070007000380138011C020E0C03F010147E 9314>I<000380003F800003800003800003800003800003800003800003800003800003 8000038003E380061B801C0780380380380380700380700380F00380F00380F00380F003 80F00380F003807003807003803803803807801C07800E1B8003E3F815207E9F19>I<03 F0000E1C001C0E00380700380700700700700380F00380F00380FFFF80F00000F00000F0 00007000007000003800801800800C010007060001F80011147F9314>I<007C00C6018F 038F07060700070007000700070007000700FFF007000700070007000700070007000700 07000700070007000700070007000700070007007FF01020809F0E>I<0000E003E3300E 3C301C1C30380E00780F00780F00780F00780F00780F00380E001C1C001E380033E00020 00002000003000003000003FFE001FFF800FFFC03001E0600070C00030C00030C00030C0 00306000603000C01C038003FC00141F7F9417>I<0E0000FE00000E00000E00000E0000 0E00000E00000E00000E00000E00000E00000E00000E3E000E43000E81800F01C00F01C0 0E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0 0E01C00E01C0FFE7FC16207F9F19>I<1C001E003E001E001C0000000000000000000000 00000E007E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E00 0E000E00FFC00A1F809E0C>I<00E001F001F001F000E000000000000000000000000000 7007F000F000700070007000700070007000700070007000700070007000700070007000 70007000700070007000706070F060F0C061803F000C28829E0E>I<0E0000FE00000E00 000E00000E00000E00000E00000E00000E00000E00000E00000E00000E0FF00E03C00E03 000E02000E04000E08000E10000E30000E70000EF8000F38000E1C000E1E000E0E000E07 000E07800E03800E03C00E03E0FFCFF815207F9F18>I<0E00FE000E000E000E000E000E 000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E000E 000E000E000E000E000E000E00FFE00B20809F0C>I<0E1F01F000FE618618000E81C81C 000F00F00E000F00F00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E00 0E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E00E00E000E 00E00E000E00E00E00FFE7FE7FE023147F9326>I<0E3E00FE43000E81800F01C00F01C0 0E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C0 0E01C00E01C0FFE7FC16147F9319>I<01F800070E001C03803801C03801C07000E07000 E0F000F0F000F0F000F0F000F0F000F0F000F07000E07000E03801C03801C01C0380070E 0001F80014147F9317>I<0E3E00FEC3800F01C00F00E00E00E00E00F00E00700E00780E 00780E00780E00780E00780E00780E00700E00F00E00E00F01E00F01C00EC3000E3E000E 00000E00000E00000E00000E00000E00000E00000E0000FFE000151D7F9319>I<03E080 0619801C05803C0780380380780380700380F00380F00380F00380F00380F00380F00380 7003807803803803803807801C0B800E138003E380000380000380000380000380000380 000380000380000380003FF8151D7E9318>I<0E78FE8C0F1E0F1E0F0C0E000E000E000E 000E000E000E000E000E000E000E000E000E000E00FFE00F147F9312>I<1F9030704030 C010C010C010E00078007F803FE00FF00070803880188018C018C018E030D0608F800D14 7E9312>I<020002000200060006000E000E003E00FFF80E000E000E000E000E000E000E 000E000E000E000E000E080E080E080E080E080610031001E00D1C7F9B12>I<0E01C0FE 1FC00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E01C00E 01C00E01C00E01C00E03C00603C0030DC001F1FC16147F9319>II I<7FC3FC0F01E00701C007018003810001C20000E40000EC00007800003800003C00007C 00004E000087000107000303800201C00601E01E01E0FF07FE1714809318>II<3FFF380E200E201C40384078407000E001E0 01C00380078007010E011E011C0338027006700EFFFE10147F9314>II E /Fi 43 122 df<387CFEFFFF7F3B030306060E0C18702008107C860F>44 DI<387CFEFEFE7C38000000000000387CFEFEFE7C38 07147C930F>58 D<07F8001FFE00381F80780F80FC0FC0FC0FC0FC0FC0780FC0301F8000 1F00003E00007C0000700000E00000E00000C00000C00000C00000C00000C00000C00000 000000000000000000000001C00003E00007F00007F00007F00003E00001C00012207D9F 19>63 D<0000E000000000E000000001F000000001F000000001F000000003F800000003 F800000006FC00000006FC0000000EFE0000000C7E0000000C7E000000183F000000183F 000000303F800000301F800000701FC00000600FC00000600FC00000C007E00000FFFFE0 0001FFFFF000018003F000018003F000030001F800030001F800060001FC00060000FC00 0E0000FE00FFE00FFFE0FFE00FFFE0231F7E9E28>65 DI<0007FC02003FFF0E00FE03DE03F000FE07E0003E0FC0001E1F80 001E3F00000E3F00000E7F0000067E0000067E000006FE000000FE000000FE000000FE00 0000FE000000FE000000FE0000007E0000007E0000067F0000063F0000063F00000C1F80 000C0FC0001807E0003803F0007000FE01C0003FFF800007FC001F1F7D9E26>IIII72 DI76 DI 80 D82 D<03FC080FFF381E03F83800F87000 78700038F00038F00018F00018F80000FC00007FC0007FFE003FFF801FFFE00FFFF007FF F000FFF80007F80000FC00007C00003CC0003CC0003CC0003CE00038E00078F80070FE01 E0E7FFC081FF00161F7D9E1D>I<7FFFFFFC7FFFFFFC7C07E07C7007E01C6007E00C6007 E00CE007E00EC007E006C007E006C007E006C007E0060007E0000007E0000007E0000007 E0000007E0000007E0000007E0000007E0000007E0000007E0000007E0000007E0000007 E0000007E0000007E0000007E0000007E00003FFFFC003FFFFC01F1E7E9D24>II87 D<07FC001FFF003F0F803F07C0 3F03E03F03E00C03E00003E0007FE007FBE01F03E03C03E07C03E0F803E0F803E0F803E0 FC05E07E0DE03FF8FE0FE07E17147F9319>97 DI<01FE0007FF801F0FC03E0FC03E0FC07C0FC07C0300 FC0000FC0000FC0000FC0000FC0000FC00007C00007E00003E00603F00C01F81C007FF00 01FC0013147E9317>I<0007F80007F80000F80000F80000F80000F80000F80000F80000 F80000F80000F80000F801F8F80FFEF81F83F83E01F87E00F87C00F87C00F8FC00F8FC00 F8FC00F8FC00F8FC00F8FC00F87C00F87C00F87E00F83E01F81F07F80FFEFF03F8FF1820 7E9F1D>I<01FE0007FF800F83C01E01E03E00F07C00F07C00F8FC00F8FFFFF8FFFFF8FC 0000FC0000FC00007C00007C00003E00181E00180F807007FFE000FF8015147F9318>I< 001F8000FFC001F3E003E7E003C7E007C7E007C3C007C00007C00007C00007C00007C000 FFFC00FFFC0007C00007C00007C00007C00007C00007C00007C00007C00007C00007C000 07C00007C00007C00007C00007C00007C0003FFC003FFC0013207F9F10>I<01FC3C07FF FE0F079E1E03DE3E03E03E03E03E03E03E03E03E03E01E03C00F07800FFF0009FC001800 001800001C00001FFF800FFFF007FFF81FFFFC3C007C70003EF0001EF0001EF0001E7800 3C78003C3F01F80FFFE001FF00171E7F931A>II<1C003E007F007F007F003E001C0000000000000000 0000000000FF00FF001F001F001F001F001F001F001F001F001F001F001F001F001F001F 001F001F00FFE0FFE00B217EA00E>I107 DIII<01FF0007FFC01F83F03E00F83E00F87C007C7C007CFC007EFC007EFC007E FC007EFC007EFC007E7C007C7C007C3E00F83E00F81F83F007FFC001FF0017147F931A> II<01F81807FE381F87783F01F83E 01F87E00F87C00F8FC00F8FC00F8FC00F8FC00F8FC00F8FC00F87C00F87E00F87E00F83F 01F81F87F80FFEF803F8F80000F80000F80000F80000F80000F80000F80000F80007FF00 07FF181D7E931C>II<0FE63FFE701E600EE006E006F800FFC07FF83FFC1FFE03FE001FC007C007E007 F006F81EFFFCC7F010147E9315>I<01800180018003800380038007800F803F80FFFCFF FC0F800F800F800F800F800F800F800F800F800F800F860F860F860F860F8607CC03F801 F00F1D7F9C14>III120 DI E /Fj 13 119 df<00003FC0000000003FC00000 00003FC0000000007FE0000000007FE0000000007FE000000000FBF000000000FBF00000 0000FBF000000001F3F800000001F1F800000001F1F800000003F1FC00000003E1FC0000 0003E0FC00000007E0FE00000007C0FE00000007C07E0000000FC07F0000000FC07F0000 000F807F0000001F803F8000001F803F8000001F003F8000003F001FC000003F001FC000 003E001FC000007E000FE000007E000FE000007C000FE00000FC0007F00000FC0007F000 00F80007F00001F80003F80001F80003F80001FFFFFFF80003FFFFFFFC0003FFFFFFFC00 03FFFFFFFC0007FFFFFFFE0007E00000FE0007E00000FE000FC00000FF000FC000007F00 0FC000007F001F8000003F801F8000003F801F8000003F803F0000001FC03F0000001FC0 3F0000001FC07E0000000FE07E0000000FE07C0000000FE0FC00000007F02C377EB631> 65 D82 D<000FF800007FFF0001FFFFC003FFFFE007FFFFE00FF00FE01FC001C01F8000C03F0000 003F0000007E0000007E0000007E000000FC000000FC000000FC000000FC000000FC0000 00FC000000FC000000FC0000007E0000007E0000007E0000003F0000003F0000201F8000 E01FC003E00FF00FE007FFFFE003FFFFE001FFFFC0007FFE00000FF0001B227DA121>99 D<000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001 F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001F8000001 F8000001F8000001F8000001F8003F81F801FFE1F803FFF9F807FFFFF80FFFFFF81FF81F F81FE007F83F8003F83F0001F87F0001F87E0001F87E0001F8FE0001F8FC0001F8FC0001 F8FC0001F8FC0001F8FC0001F8FC0001F8FC0001F8FC0001F8FE0001F87E0001F87E0001 F87F0001F83F0003F83F8007F81FC00FF81FF03FF80FFFFFF807FFFDF803FFF9F801FFE1 F8007F01F81D377DB626>I<001FE000007FF80001FFFE0003FFFF0007FFFF800FF03F80 1FC01FC01F8007C03F0007E03F0003E07E0003E07E0001F07FFFFFF0FFFFFFF0FFFFFFF0 FFFFFFF0FFFFFFF0FC000000FC000000FC000000FC0000007C0000007E0000007E000000 3F0000003F8000001FC000101FE000F00FF807F007FFFFF003FFFFF000FFFFE0007FFF00 000FF8001C227EA121>I<001F801F0000FFF1FF0001FFFFFF8003FFFFFF8007FFFFFF80 0FE07F00001FC03F80001F801F80001F801F80003F000FC0003F000FC0003F000FC0003F 000FC0003F000FC0003F000FC0001F801F80001F801F80001FC03F80000FE07F00000FFF FE00000FFFFC00001FFFF800001EFFF000001E1F8000003E000000003E000000003E0000 00001F000000001FFFFE00001FFFFFC0000FFFFFF0000FFFFFF8001FFFFFFC003FFFFFFC 007F0003FE007E0000FE00FE00007F00FC00003F00FC00003F00FC00003F00FC00003F00 FE00007F007F0000FE007F8001FE003FF00FFC001FFFFFF8000FFFFFF00003FFFFC00000 FFFF0000001FF8000021327EA125>103 D105 D110 D<000FF000007FFE0000FFFF0003FFFFC007FFFFE00FF81FF01FE007 F81F8001F83F0000FC3F0000FC7E00007E7E00007E7C00003EFC00003FFC00003FFC0000 3FFC00003FFC00003FFC00003FFC00003FFC00003F7E00007E7E00007E7E00007E3F0000 FC3F8001FC1FC003F81FE007F80FF81FF007FFFFE003FFFFC000FFFF00007FFE00000FF0 0020227EA125>I114 D<01FF8007FFF01FFFFC3FFFFC3FFFFC7F00F87E0018FC0000FC 0000FC0000FC0000FE00007F00007FF0003FFF001FFFC00FFFF007FFF801FFFC001FFE00 01FE00007F00003F00003F00003F40003F60003F78007EFF01FEFFFFFCFFFFFC7FFFF00F FFE001FF0018227EA11C>I117 DI E end %%EndProlog %%BeginSetup %%Feature: *Resolution 300dpi TeXDict begin %%EndSetup %%Page: 1 1 1 0 bop 680 55 a Fj(Avoiding)26 b(Recursion)820 141 y Fi(Brian)18 b(Harv)o(ey)590 199 y(Univ)o(ersit)o(y)f(of)g(California,)i (Berk)o(eley)91 317 y Fh(It)11 b(is)h(traditional)f(to)g(understand)g (a)g(computer)g(program)f(as)h(a)g Fg(se)n(quenc)n(e)i Fh(of)d(instructions.)20 b(The)11 b(computer)0 375 y(carries)h(out)g (these)h(instructions)g(one)f(after)f(another.)19 b(V)l(arious)12 b Fg(c)n(ontr)n(ol)h(structur)n(es)j Fh(allo)o(w)c(the)h(programmer)e (to)0 433 y(c)o(hange)16 b(the)g(order)g(in)g(whic)o(h)h(these)f (instructions)h(are)f(carried)g(out;)g(there)g(are)f(conditional)j (structures)e(that)0 491 y(allo)o(w)c(a)g(c)o(hoice)h(b)q(et)o(w)o(een) f(subsequences,)i(and)f(lo)q(oping)g(structures)f(that)f(allo)o(w)h (the)g(rep)q(etition)i(of)d(a)h(sequence.)91 553 y(In)f(con)o(trast)e (to)h(this)h(idea)h(of)e(sequen)o(tial)i(programming)e(there)h(is)g(a)f (more)g(recen)o(t)h(mo)q(del)g(called)i Fg(functional)0 611 y(pr)n(o)n(gr)n(amming)18 b Fh([Bac)o(kus,)c(1978;)f(Allen,)j (1984;)d(Ab)q(elson,)i(1985].)k(In)14 b(this)h(approac)o(h,)f(a)g (program)f(is)i(view)o(ed)g(as)0 669 y(a)c(collection)j(of)d (mathematical)g(functions,)i(whic)o(h)f(can)g(b)q(e)g(applied)h(to)e (argumen)o(ts)g(and)h(comp)q(osed)f(with)h(other)0 727 y(functions)17 b(to)f(create)g(more)g(complicated)h(functions.)24 b(The)17 b(emphasis)g(is)g(on)f(the)g(input-output)i(b)q(eha)o(vior)e (of)0 785 y(a)i(function,)h(rather)e(than)h(on)g(the)g(sequence)i(of)d (ev)o(en)o(ts)h(b)o(y)g(whic)o(h)h(the)f(computer)g(determines)h(the)f (output)0 843 y(v)m(alue.)i(Programming)10 b(languages)i(suc)o(h)g(as)f (LISP)l(,)h(Logo,)g(and)g(APL)g(emphasize)g(the)g(functional)h(mo)q (del,)f(while)0 901 y(BASIC,)k(P)o(ascal,)e(and)i(C)f(emphasize)h(the)f (sequen)o(tial)i(view.)j(\(This)15 b(division)j(is)d(not)g(absolute;)g (an)o(y)g(program)0 960 y(can)f(b)q(e)h(written)f(in)h(an)o(y)e (language,)h(more)g(or)f(less.)20 b(But)15 b(eac)o(h)f(language)g (encourages)g(a)f(certain)i(natural)f(st)o(yle)0 1018 y(of)h(programming.\))91 1080 y(In)23 b(this)g(pap)q(er)g(I)g(b)q(egin) h(b)o(y)e(arguing)h(that)f(functional)h(programming)f(is)h(not)f(only)i (more)e(p)q(o)o(w)o(erful)0 1138 y(tec)o(hnically)d(but)e(also)g(more)g (sensible)h(p)q(edagogically)l(,)h(esp)q(ecially)h(when)d(computer)g (programming)g(is)g(to)f(b)q(e)0 1196 y(used)j(as)e(a)h(v)o(ehicle)h (for)f(teac)o(hing)g(mathematical)g(ideas.)29 b(Wh)o(y)l(,)18 b(then,)h(is)f(secondary)g(sc)o(ho)q(ol)h(programming)0 1254 y(done)14 b(almost)f(exclusiv)o(ely)j(in)e(BASIC)g(and)g(P)o (ascal?)20 b(Wh)o(y)13 b(not)g(Logo?)19 b(Although)14 b(there)g(are)f(sev)o(eral)h(answ)o(ers)0 1312 y(to)h(this)h(question,) f(I)h(w)o(an)o(t)f(to)f(fo)q(cus)i(atten)o(tion)f(on)g(one)h(tec)o (hnical)h(reason:)j(T)l(eac)o(hers)15 b(are)g(put)h(o\013)e(b)o(y)i (Logo's)0 1370 y(hea)o(vy)j(reliance)j(on)d(recursion)i(as)e(the)g (principal)j(con)o(trol)e(mec)o(hanism.)33 b(I)20 b(shall)h(discuss)g (the)e(relationship)0 1428 y(b)q(et)o(w)o(een)e(functional)g (programming)f(and)h(recursion,)g(sho)o(w)f(ho)o(w)g(the)h(t)o(w)o(o)e (can)i(b)q(e)g(separated,)f(and)h(suggest)0 1486 y(sp)q(eci\014c)g (approac)o(hes)e(to)g(sample)g(mathematical)h(programming)e(problems.) 91 1548 y(Recursion)19 b(is)f(itself)g(an)g(in)o(teresting)g (mathematical)g(idea,)g(b)q(ecause)h(of)e(its)g(connection)i(with)f (pro)q(of)f(b)o(y)0 1606 y(induction.)30 b(I)19 b(don't)e(mean)h(to)f (suggest)h(that)f(mathematics)h(teac)o(hers)g(should)h(wish)f(to)g(a)o (v)o(oid)f(recursion)i(in)0 1664 y(ev)o(ery)12 b(situation.)19 b(Indeed,)14 b(later)f(w)o(e'll)g(consider)g(examples)g(\(e.g.,)e (computing)i(the)f(determinan)o(t)h(of)f(a)g(matrix\))0 1723 y(for)i(whic)o(h)h(the)g(use)f(of)g(recursion)h(is)g(naturally)g (connected)h(with)f(the)f(task.)19 b(Logo)14 b(is,)h(of)f(course,)g(an) g(excellen)o(t)0 1781 y(v)o(ehicle)j(for)d(the)h(study)f(of)h (recursion)g(when)h(that)e(is)h(desired.)21 b(But)15 b(not)f(ev)o(ery)h(topic)g(is)g(inheren)o(tly)i(recursiv)o(e,)0 1839 y(and)c(the)g(v)m(alue)h(of)e(functional)i(programming)f(will)h(b) q(e)g(enhanced)g(if)f(the)g(issue)h(of)e(recursion)i(can)f(b)q(e)g (separated)0 1897 y(from)h(that)h(of)g(functions.)0 2013 y Fi(Sequen)o(tial)j(and)g(F)l(unctional)i(Programming)91 2130 y Fh(Consider)c(the)f(problem)h(of)f(adding)h(t)o(w)o(o)d (matrices:)666 2199 y Ff(\022)707 2236 y Fh(2)45 b(3)g(4)707 2291 y(5)g(6)g(7)873 2199 y Ff(\023)917 2263 y Fh(+)962 2199 y Ff(\022)1010 2236 y Fh(87)62 b(0)57 b(14)1003 2291 y Fe(\000)p Fh(6)46 b(28)56 b(9)1251 2199 y Ff(\023)0 2380 y Fh(The)12 b(result)g(is)h(a)e(matrix)h(with)g(the)g(same)g(shap) q(e)g(as)g(the)g(t)o(w)o(o)e(addends.)20 b(Eac)o(h)11 b(elemen)o(t)i(of)f(the)g(result)g(is)g(formed)0 2438 y(b)o(y)j(adding)i(the)e(corresp)q(onding)h(elemen)o(ts)h(of)e(the)g (addends;)h(in)g(sequen)o(tial)h(programming)e(this)h(leads)g(to)e(six) 0 2496 y(assignmen)o(t)h(instructions,)h(whic)o(h)g(can)f(b)q(e)h (arranged)f(in)h(t)o(w)o(o)e(nested)i(lo)q(ops)g(to)e(re\015ect)i(the)f (t)o(w)o(o-dimensional)0 2554 y(structure)h(of)g(the)h(matrix.)24 b(F)l(or)16 b(no)o(w)g(let's)g(ignore)h(the)g(matter)e(of)h(reading)h (these)g(particular)g(n)o(um)o(b)q(ers)g(in)o(to)0 2612 y(the)c(computer,)h(and)f(supp)q(ose)h(w)o(e)f(ha)o(v)o(e)g(t)o(w)o(o)f (arra)o(ys)g Fd(A)h Fh(and)g Fd(B)g Fh(con)o(taining)h(the)g(addends.) 20 b(A)13 b(BASIC)h(program)0 2670 y(to)h(add)g(these)g(matrices)h (migh)o(t)f(b)q(e)g(written)h(as)e(follo)o(ws.)964 2779 y(1)p eop %%Page: 2 2 2 1 bop 0 45 a Fd(10)24 b(DIMENSION)e(A\(2,3\),)h(B\(2,3\),)g(C\(2,3\)) 0 104 y(20)h(FOR)f(I)h(=)f(1)h(TO)g(2)0 162 y(30)71 b(FOR)24 b(J)f(=)h(1)g(TO)g(3)0 220 y(40)119 b(C\(I,J\))23 b(=)h(A\(I,J\))f(+)h (B\(I,J\))0 278 y(50)71 b(NEXT)24 b(J)0 336 y(60)g(NEXT)f(I)0 394 y(70)h(END)0 474 y Fh(This)c(is)g(a)f(simple)i(enough)e(program.)32 b(It)19 b(has)g(t)o(w)o(o)f(main)i(w)o(eaknesses.)32 b(One)20 b(has)g(to)e(do)i(with)f(the)h(use)f(of)0 532 y(arra)o(ys)h(to)g(represen)o(t)h(the)h(matrices.)37 b(The)22 b(problem)f(is)h(that)e(the)i(particular)f(dimensions,)j(t)o (w)o(o)c(ro)o(ws)g(b)o(y)0 590 y(three)d(columns,)h(m)o(ust)e(b)q(e)i (built)g(in)o(to)f(the)g(program,)f(b)q(oth)h(in)g(the)g(arra)o(y)f (declarations)h(and)h(in)f(the)g(con)o(trol)0 648 y(structures)f(\(the) g Fd(FOR)g Fh(statemen)o(ts\))f(that)g(con)o(trol)i(the)f(sequence)h (of)f(ev)o(en)o(ts.)23 b(The)17 b(second)g(w)o(eakness)f(is)h(that)0 706 y(this)h(program)f(exp)q(ects)i(to)e(\014nd)i(its)f(data)f(in)i (\014xed)g(places,)g(the)f(arra)o(ys)f Fd(A)h Fh(and)g Fd(B)p Fh(,)f(and)h(lea)o(v)o(es)h(its)f(result)g(in)0 765 y(a)f(third)g(predetermined)i(lo)q(cation)e Fd(C)p Fh(.)g(This)g(is)h(\014ne)f(if)h(w)o(e)e(only)i(w)o(an)o(t)d(to)i (compute)g Fc(A)11 b Fh(+)h Fc(B)r Fh(,)17 b(but)g(what)g(if)g(w)o(e)0 823 y(w)o(an)o(t)f(to)h(solv)o(e)h(a)f(sligh)o(tly)h(di\013eren)o(t)g (problem,)g(lik)o(e)h Fc(A)12 b Fh(+)g(2)p Fc(B)r Fh(?)27 b(What)17 b(if)h(w)o(e)f(w)o(an)o(t)g(to)f(c)o(hec)o(k)i(that)f (addition)0 881 y(of)g(matrices)h(is)g(truly)f(comm)o(utativ)o(e,)g(b)o (y)h(adding)g(\014rst)f Fc(A)12 b Fh(+)g Fc(B)20 b Fh(and)e(then)g Fc(B)c Fh(+)e Fc(A)p Fh(?)28 b(Or,)18 b(ha)o(ving)g(computed)0 939 y Fc(C)g Fh(as)d(the)g(sum)h(of)f Fc(A)g Fh(and)h Fc(B)r Fh(,)f(what)g(if)h(w)o(e)f(w)o(an)o(t)f(to)h(use)h(that)e (result)i(as)f(part)g(of)g(a)g(larger)g(computation,)g(lik)o(e)0 997 y Fc(C)e Fh(+)d Fc(B)r Fh(?)22 b(In)16 b(eac)o(h)f(case)g(w)o(e)g (ha)o(v)o(e)g(to)f(rewrite)i(the)f(program.)91 1063 y(A)j(b)q(etter)g (in)o(teractiv)o(e)g(system)f(for)g(studen)o(ts)h(to)f(use)h(in)h (exploring)g(matrix)e(arithmetic)i(w)o(ould)f(supply)0 1121 y(functions)e(whose)f(domain)h(and)f(range)g(are)g(matrices.)20 b(W)l(e)15 b(should)h(b)q(e)g(able)g(to)f(en)o(ter)g(instructions)h (lik)o(e)0 1198 y Fd(PRINT)23 b(ADD\(A,B\))0 1256 y(PRINT)g(ADD\(A,)g (ADD\(B,B\)\))0 1314 y(LET)g(C)h(=)g(ADD\(A,B\))0 1372 y(PRINT)f(ADD\(C,B\))0 1430 y(IF)h(ADD\(A,B\))e(=)i(ADD\(B,A\))f(THEN)g (PRINT)g("IT'S)h(COMMUTATIVE.")0 1510 y Fh(\(In)18 b(this)g(fanciful)h (example)g(I)f(am)g(using)g(the)g(syn)o(tax)f(of)g(BASIC,)h(but)g (asking)g(for)g(computations)f(that)g(are)0 1568 y(b)q(ey)o(ond)22 b(the)g(p)q(o)o(w)o(ers)f(of)g(most)g(v)o(ersions)h(of)f(BASIC.)h(Man)o (y)f(v)o(ersions)h(do)g(allo)o(w)g(this)g(sort)f(of)g(functional)0 1626 y(notation,)14 b(but)i(only)g(for)e(certain)i(functions)g(of)e (single)j(n)o(um)o(b)q(ers,)e(not)g(arra)o(y-v)m(alued)g(functions.\)) 91 1692 y(Although)k(functions)g(are)e(one)i(of)e(the)i(cen)o(tral)f (ideas)h(of)e(mathematics,)i(they)f(are)g(not)f(limited)j(to)e(the)0 1750 y(narro)o(w)c(sc)o(ho)q(ol)i(v)o(ersion)f(of)g(mathematics)g(as)g (\\stu\013)f(ab)q(out)h(n)o(um)o(b)q(ers.")20 b(Consider)c(the)f (functions)0 1827 y(plural\(b)q(o)o(x\))h(=)f(b)q(o)o(xes)0 1885 y(F)l(renc)o(h\(b)q(o)q(ok\))g(=)h(livre)0 1943 y(capital\(England\))g(=)g(London)0 2001 y(A)o(tomicW)l(eigh)o(t\(silv) o(er\))g(=)f(107.87)0 2081 y(I)i(shall)i(resist)e(the)g(temptation)g (to)f(explore)i(p)q(ossible)h(p)q(edagogic)e(uses)h(of)e(functional)j (programming)d(in)i(the)0 2139 y(areas)g(suggested)h(b)o(y)g(these)g (simple)h(functions.)32 b(A)18 b(serious)i(e\013ort)d(to)i(translate)f (English)i(in)o(to)f(F)l(renc)o(h,)h(for)0 2198 y(example,)d(w)o(ould)g (need)g(m)o(uc)o(h)g(more)f(sophistication)h(than)g(the)f(w)o (ord-for-w)o(ord)f(translation)i(function)g(illus-)0 2256 y(trated)i(ab)q(o)o(v)o(e.)35 b(The)20 b(p)q(oin)o(t)g(is)h(that)e (no)h(matter)f(what)h(a)g(computation)g(is)g(ab)q(out,)h(the)f(abilit)o (y)i(to)d(de\014ne,)0 2314 y(in)o(v)o(ok)o(e,)c(and)g(comp)q(ose)g (functions)h(is)g(a)f(natural)g(and)h(con)o(v)o(enien)o(t)f(to)q(ol.)91 2380 y(Computer)h(scien)o(tists)i(are)e(excited)i(ab)q(out)e (functional)i(programming)e(for)g(reasons)g(unconnected)j(with)0 2438 y(p)q(edagogy)l(.)43 b(T)l(o)23 b(a)f(computer)h(scien)o(tist,)i (what)e(distinguishes)i(this)e(metho)q(dology)g(from)f(traditional)i (ap-)0 2496 y(proac)o(hes)14 b(is)h(that)e(a)h(function)h(has)f(no)g (\\side)g(e\013ects.")19 b(That)14 b(is,)g(when)h(a)f(programmer)f (asks)g(for)h(the)g(v)m(alue)h(of)0 2554 y Fc(f)5 b Fh(\(7\))14 b(the)h(v)m(alue)h(returned)f(is)g(alw)o(a)o(ys)f(the)h(same.)20 b(This)15 b(computation)g(do)q(es)g(not)f(cause)h(a)g(p)q(ermanen)o(t)g (c)o(hange)0 2612 y(in)f(the)f(computer's)g(memory)f(that)h(migh)o(t)g (a\013ect)f(later)h(computations.)19 b(\(F)l(or)13 b(example,)h(there)f (are)g(no)g(assign-)0 2670 y(men)o(ts)h(to)f(global)i(v)m(ariables.\)) 21 b(This)14 b(is)h(imp)q(ortan)o(t)f(for)f(t)o(w)o(o)g(reasons.)19 b(First,)14 b(it)g(is)h(easier)f(to)g(carry)g(out)f(formal)964 2779 y(2)p eop %%Page: 3 3 3 2 bop 0 45 a Fh(reasoning)14 b(ab)q(out)g(a)g(program)e(without)i (side)h(e\013ects.)k(One)c(branc)o(h)f(of)g(computer)g(science)h(is)g (concerned)g(with)0 104 y(program)g Fg(veri\014c)n(ation)s Fh(:)h(the)h(attempt)e(to)h(pro)o(vide)h(formal)f(pro)q(of)g(of)g(the)h (correctness)f(of)g(a)h(program.)22 b(F)l(unc-)0 162 y(tional)14 b(programs)f(lend)i(themselv)o(es)g(to)e(this)h(attempt)f (more)h(readily)h(than)f(traditional)g(sequen)o(tial)h(programs)0 220 y(that)20 b(are)g(hea)o(vily)i(dep)q(enden)o(t)g(on)e(long-term)h (v)m(ariable)h(assignmen)o(t.)36 b(Second,)22 b(if)f(the)g(computation) f(of)g(a)0 278 y(function)15 b(has)g(no)f(side)i(e\013ects,)e(then)h (it)f(mak)o(es)g(no)h(di\013erence)h(whic)o(h)f(of)f(t)o(w)o(o)f (desired)j(computations)f(is)g(done)0 336 y(\014rst;)i(eac)o(h)g(is)g (guaran)o(teed)f(to)g(b)q(e)i(indep)q(enden)o(t)h(of)d(the)h(other.)25 b(Recen)o(t)17 b(dev)o(elopmen)o(ts)g(in)h(computer)f(hard-)0 394 y(w)o(are)f(include)k Fg(p)n(ar)n(al)r(lel)h Fh(pro)q(cessors,)c (in)h(whic)o(h)g(the)f(t)o(w)o(o)f(computations)h(migh)o(t)g(actually)h (tak)o(e)e(place)i(at)f(the)0 452 y(same)c(time.)19 b(F)l(unctional)14 b(programs)e(can)h(easily)h(tak)o(e)e(adv)m(an)o(tage)g(of)h(this)g (parallelism;)j(traditional)d(programs)0 510 y(require)j(detailed)h (analysis)f(b)q(efore)f(an)o(y)g(subtask)g(can)g(b)q(e)h(split)g(o\013) f(for)f(parallel)j(computation.)91 576 y(F)l(or)c(our)g(p)q(edagogic)h (purp)q(oses,)h(ho)o(w)o(ev)o(er,)d(the)i(imp)q(ortan)o(t)f(p)q(oin)o (ts)h(ab)q(out)g(functional)g(programming)f(are)0 634 y(di\013eren)o(t.)22 b(A)15 b(studen)o(t)h(who)f(w)o(an)o(ted)g(to)g (use)h(the)g(BASIC)h(instructions)f(sho)o(wn)f(ab)q(o)o(v)o(e)h(to)f (add)h(t)o(w)o(o)e(matrices)0 693 y(in)i(a)f(larger)f(program)g(w)o (ould)i(ha)o(v)o(e)e(to)h(remem)o(b)q(er)g(that)f(the)h(result)h(is)f (in)h(the)f(arra)o(y)f Fd(C)g Fh(and)i(write)f(the)g(rest)f(of)0 751 y(the)k(program)e(accordingly)l(.)29 b(Tw)o(o)16 b(suc)o(h)i(addition)h(problems)f(with)g(di\013eren)o(t)g(matrices)g(w) o(ould)g(require)g(t)o(w)o(o)0 809 y(copies)g(of)f(the)g(instructions)h (or)f(reuse)g(of)g(the)g(same)g(arra)o(ys)f(for)g(di\013eren)o(t)i (purp)q(oses.)26 b(A)17 b(function)h(that)f(can)0 867 y(b)q(e)f(applied)h(to)e(an)o(y)g(t)o(w)o(o)f(matrices,)h(and)g(whose)g (return)h(v)m(alue)g(can)g(b)q(e)g(used)f(as)g(part)g(of)g(a)g(larger)g (expression)0 925 y(instead)h(of)g(b)q(eing)h(tied)f(to)f(a)h(sp)q (eci\014c)h(result)f(arra)o(y)l(,)f(allo)o(ws)h(the)g(studen)o(t)f(to)g (think)i(ab)q(out)e(the)h(mathematics)0 983 y(instead)g(of)f(tripping)h (o)o(v)o(er)e(the)i(programming)e(language.)0 1104 y Fi(First-Class)k(Data)g(Aggregates)91 1224 y Fh(Consider)i(no)o(w)f (the)h(problem)g(of)f(en)o(tering)i(the)e(actual)h(matrix)f(v)m(alues)i (in)o(to)f(the)f(program.)33 b(In)20 b(most)0 1283 y(programming)14 b(languages,)g(the)g(facilities)i(for)e(dealing)h(with)g(individual)i (n)o(um)o(b)q(ers)e(\(scalars\))e(are)h(m)o(uc)o(h)g(more)0 1341 y(\015exible)23 b(than)f(the)f(facilities)i(for)e(arra)o(ys.)37 b(It)21 b(is)h(as)f(if)h(n)o(um)o(b)q(ers)g(are)f(\\real)g(things")g (while)i(collections)g(of)0 1399 y(n)o(um)o(b)q(ers)15 b(are)g(less)h(real.)k(F)l(or)14 b(example,)i(in)f(BASIC)h(or)f(P)o (ascal)f(a)h(scalar)g(constan)o(t)f(can)h(b)q(e)h(directly)g(assigned)0 1457 y(to)f(a)f(v)m(ariable)j(\()p Fd(X)23 b(=)h(3)p Fh(\))15 b(or)g(can)g(b)q(e)h(part)e(of)h(a)g(larger)g(expression)h(\() p Fd(X)23 b(=)h(Y+3)p Fh(\),)14 b(but)i(y)o(ou)e(can't)h(sa)o(y)0 1534 y Fd(A)24 b(=)f(2,3,4,5,6,7)0 1614 y Fh(to)c(assign)h(a)f(v)m (alue)i(to)e(an)g(en)o(tire)h(arra)o(y)e(at)h(once.)34 b(Instead,)20 b(getting)g(this)g(v)m(alue)h(in)o(to)e(the)h(computer)f (is)h(a)0 1672 y(sequence)c(of)f(ev)o(en)o(ts)g(in)h(itself:)0 1749 y Fd(10)24 b(DIMENSION)e(A\(2,3\))0 1807 y(20)i(FOR)f(I)h(=)f(1)h (TO)g(2)0 1865 y(30)71 b(FOR)24 b(J)f(=)h(1)g(TO)g(3)0 1924 y(40)119 b(READ)23 b(A\(I,J\))0 1982 y(50)71 b(NEXT)24 b(J)0 2040 y(60)g(NEXT)f(I)0 2098 y(70)h(DATA)f(2,3,4,5,6,7)0 2156 y(80)h(END)91 2236 y Fh(Logo's)16 b(list)h(pro)q(cessing)h(mak)o (es)e(matrix)h(manipulation)h(m)o(uc)o(h)f(more)f(con)o(v)o(enien)o(t.) 25 b(F)l(or)17 b(one)g(thing,)g(the)0 2295 y(size)e(of)f(a)g(list)h (need)g(not)e(b)q(e)i(declared)g(in)g(adv)m(ance;)g(w)o(e)f(can)g (write)h(matrix)e(functions)i(that)f(w)o(ork)f(on)h(matrices)0 2353 y(of)i(an)o(y)f(size)i(or)e(shap)q(e.)23 b(Also,)16 b(a)g(list)h(is)f(a)g(\\\014rst-class")f(en)o(tit)o(y:)21 b(Lik)o(e)c(a)f(n)o(um)o(b)q(er,)g(it)g(can)g(b)q(e)h(used)f(as)g(part) f(of)0 2411 y(an)h(expression,)g(as)g(an)g(input)h(to)e(or)h(output)f (from)g(a)h(function,)h(as)e(the)h(v)m(alue)h(assigned)g(to)e(a)h(v)m (ariable,)h(or)e(as)0 2469 y(something)g(to)g(b)q(e)h(read)f(or)g(prin) o(ted.)91 2535 y(W)l(e'll)i(represen)o(t)g(a)f(matrix)g(as)h(a)f(list)h (of)f(lists.)25 b(Eac)o(h)17 b(of)f(the)g(sublists)i(will)g(b)q(e)g (one)e(ro)o(w)g(of)g(the)h(matrix.)0 2593 y(W)l(e)e(can)h(solv)o(e)f (the)g(addition)i(problem)e(p)q(osed)h(ab)q(o)o(v)o(e)f(b)o(y)g (assigning)h(matrix)f(v)m(alues)h(to)f(v)m(ariables:)0 2670 y Fd(MAKE)23 b("A)h([[2)f(3)h(4])g([5)f(6)h(7]])964 2779 y Fh(3)p eop %%Page: 4 4 4 3 bop 0 45 a Fd(MAKE)23 b("B)h([[87)f(0)h(14])f([-6)h(28)f(9]])0 104 y(SHOW)g(ADD)h(:A)f(:B)0 177 y Fh(or)15 b(w)o(e)g(can)g(use)g(the)h (matrix)f(v)m(alues)h(directly)g(as)f(inputs)h(to)f(the)g(addition)i (function:)0 254 y Fd(SHOW)23 b(ADD)h([[2)f(3)h(4])g([5)f(6)h(7]])47 b([[87)23 b(0)h(14])g([-6)f(28)h(9]])0 327 y Fh(The)13 b(brac)o(k)o(ets)f(that)g(delimit)i(the)f(sublists)h(mak)o(e)e(the)h(t) o(w)o(o-b)o(y-three)f(shap)q(e)h(of)f(the)h(matrix)f(immediately)i (clear)0 385 y(to)h(a)f(h)o(uman)i(reader)f(as)g(w)o(ell)h(as)f(to)f (the)h(computer)h(program.)0 500 y Fi(Adding)i(Matrices)f(in)h(Logo)91 614 y Fh(I)12 b(ha)o(v)o(e)g(indicated)h(some)f(of)f(the)h(reasons)f (wh)o(y)h(Logo)f(is)i(a)e(go)q(o)q(d)h(language)g(in)h(whic)o(h)f(to)g (add)g(matrices,)g(but)0 672 y(I)h(ha)o(v)o(e)g(not)f(y)o(et)h(gotten)f (around)h(to)f(writing)h(the)g(actual)g(program.)18 b(I)c(shall)g(no)o (w)e(do)h(so,)g(in)g(a)g(traditional)g(Logo)0 730 y(st)o(yle.)25 b(The)17 b(t)o(w)o(o-dimensional)h(nature)f(of)f(a)h(matrix)f(is)h (re\015ected)h(in)g(a)e(t)o(w)o(o-pro)q(cedure)h(program)f(structure.)0 788 y(The)g(top-lev)o(el)h(pro)q(cedure)g(go)q(es)f(through)g(the)g(t)o (w)o(o)f(input)i(matrices)f(ro)o(w)f(b)o(y)h(ro)o(w,)f(adding)i(pairs)f (of)g(ro)o(ws)f(to)0 846 y(pro)q(duce)h(a)g(ro)o(w)e(of)h(the)h (result.)21 b(The)16 b(subpro)q(cedure)h(that)e(adds)g(a)h(ro)o(w)e (has)i(the)f(same)h(general)g(structure;)f(it)0 904 y(go)q(es)i (through)h(t)o(w)o(o)e(v)o(ectors)h(\(that's)f(what)h(a)h(ro)o(w)e(of)i (a)f(matrix)g(is\))h(elemen)o(t)h(b)o(y)e(elemen)o(t,)i(adding)f(pairs) g(of)0 962 y(n)o(um)o(b)q(ers.)0 1039 y Fd(TO)24 b(MATRIX.ADD)e(:M1)i (:M2)24 1097 y(IF)f(EMPTYP)g(:M1)h([OUTPUT)f([]])24 1155 y(OUTPUT)g(FPUT)g(\(VECTOR.ADD)g(FIRST)g(:M1)g(FIRST)g(:M2\))310 1213 y(\(MATRIX.ADD)g(BUTFIRST)f(:M1)i(BUTFIRST)f(:M2\))0 1271 y(END)0 1387 y(TO)h(VECTOR.ADD)e(:V1)i(:V2)24 1446 y(IF)f(EMPTYP)g(:V1)h([OUTPUT)f([]])24 1504 y(OUTPUT)g(FPUT)g(\(SUM)h (FIRST)f(:V1)g(FIRST)g(:V2\))310 1562 y(\(VECTOR.ADD)g(BUTFIRST)f(:V1)i (BUTFIRST)f(:V2\))0 1620 y(END)0 1693 y Fh(I'v)o(e)f(called)i(the)f (top-lev)o(el)g(pro)q(cedure)g Fd(MATRIX.ADD)e Fh(rather)h(than)g(just) g Fd(ADD)g Fh(to)g(mak)o(e)f(sure)i(there)f(is)h(no)0 1751 y(confusion)17 b(ab)q(out)g(whic)o(h)g(is)g(whic)o(h.)24 b(The)17 b(pro)q(cedure)g Fd(SUM)f Fh(that's)g(used)h(b)o(y)f Fd(VECTOR.ADD)f Fh(is)i(Logo's)f(built-in)0 1810 y(addition)g(function) g(for)f(scalars.)0 1886 y Fd(?)24 b(SHOW)f(MATRIX.ADD)g([[2)g(3)h(4])f ([5)h(6)g(7]])47 b([[87)23 b(0)h(14])f([-6)h(28)f(9]])0 1944 y([[89)g(3)h(18])f([-1)h(34)g(16]])91 2018 y Fh(These)d(pro)q (cedures)g(are)g Fg(r)n(e)n(cursive)p Fh(.)35 b(That)20 b(is,)i(eac)o(h)e(of)h(them)f(includes)j(an)d(in)o(v)o(o)q(cation)h(of) g(the)f(same)0 2076 y(function)h(applied)g(to)f(di\013eren)o(t)g (inputs.)35 b(De\014ning)21 b(a)e(function)i(in)g(terms)e(of)g(itself)i (is)f(a)g(familiar)h(tric)o(k)f(to)0 2134 y(mathematicians:)678 2265 y Fc(n)p Fh(!)12 b(=)778 2200 y Ff(\032)820 2236 y Fh(1)259 b(if)15 b Fc(n)e Fh(=)g(0;)820 2291 y Fc(n)d Fe(\002)h Fh(\()p Fc(n)f Fe(\000)g Fh(1\)!)45 b(if)15 b Fc(n)e(>)g Fh(0.)0 2378 y(But)i(mathematicians)h(also)f(kno)o(w)f (that)g(it's)h(hard)g(to)g(get)f(studen)o(ts)h(to)g(understand)g(these) g(inductiv)o(e)i(de\014ni-)0 2436 y(tions)e(at)g(\014rst.)91 2496 y(There)k(are)f(man)o(y)h(reasons)f(wh)o(y)g(Logo)h(is)g(not)f (widely)j(used)e(in)g(teac)o(hing)h(mathematical)f(topics)g(suc)o(h)0 2554 y(as)i(matrix)f(arithmetic.)38 b(BASIC)22 b(is)g(p)q(opular)f(b)q (ecause)h(it)g(often)e(comes)h(free)g(with)h(p)q(ersonal)f(computers.)0 2612 y(P)o(ascal)d(is)g(p)q(opular,)h(in)g(the)f(United)h(States,)e(b)q (ecause)i(of)f(the)g(Adv)m(anced)h(Placemen)o(t)f(Exam)g(in)g(Computer) 0 2670 y(Science.)24 b(Logo,)16 b(b)q(ecause)h(of)e(its)i(widespread)g (use)f(in)h(elemen)o(tary)f(sc)o(ho)q(ols,)g(has)g(an)g(undeserv)o(ed)h (but)f(nearly)964 2779 y(4)p eop %%Page: 5 5 5 4 bop 0 45 a Fh(univ)o(ersal)20 b(reputation)f(as)f(a)g(language)h (suitable)h Fg(only)i Fh(for)c(v)o(ery)h(y)o(oung)f(studen)o(ts)h (doing)g(trivial)h(problems.)0 104 y(Man)o(y)12 b(p)q(eople)h(b)q (eliev)o(e)h(that)e(Logo)g(can)g(only)h(do)f(graphics,)h(lik)o(e)g(a)f (pain)o(t)g(program.)18 b(But)12 b(ev)o(en)h(p)q(eople)h(who)e(see)0 162 y(past)17 b(these)g(misunderstandings)i(often)e(consider)h(Logo)e (list)i(pro)q(cessing)g(di\016cult)h(b)q(ecause)f(of)f(the)g(frequen)o (t)0 220 y(use)f(of)e(recursion.)91 280 y(Wh)o(y)20 b(is)h(a)f (recursiv)o(e)i(de\014nition)g(needed)g(here?)37 b(Later)20 b(I)h(shall)h(suggest)e(that)g(the)g(use)h(of)f(recursion)0 338 y(is)i Fg(not)j Fh(truly)d(necessary;)i(b)o(y)d(pro)o(viding)i(a)e (larger)g(functional)h(programming)f(\\to)q(olkit")g(w)o(e)g(can)h (express)0 396 y(the)e(desired)h(computation)f(without)g(writing)h (self-referen)o(tial)h(pro)q(cedures.)35 b(Still,)22 b(there)f(is)f(a)g(connection)0 455 y(b)q(et)o(w)o(een)14 b(the)f(functional)i(approac)o(h)e(and)g(the)h(use)g(of)f(recursion.)20 b(T)l(o)13 b(simplify)i(the)f(discussion,)h(let's)e(consider)0 513 y(the)j(subpro)q(cedure)i Fd(VECTOR.ADD)p Fh(.)c(The)i(sequen)o (tial)h(view)g(of)f(programming)f(w)o(ould)i(express)f(the)g(job)g(of)g (this)0 571 y(pro)q(cedure)g(as)f(a)g(sequence)h(of)f(ev)o(en)o(ts,)f (one)i(for)e(eac)o(h)i(elemen)o(t)g(of)e(the)i(result)f(v)o(ector:)0 647 y Fd(LET)23 b(C\(1\))h(=)f(A\(1\))h(+)g(B\(1\))0 705 y(LET)f(C\(2\))h(=)f(A\(2\))h(+)g(B\(2\))0 763 y(LET)f(C\(3\))h(=)f (A\(3\))h(+)g(B\(3\))0 838 y Fh(In)15 b(this)f(illustration)h(I)g(am)e (supp)q(osing)i(that)f(w)o(e)f(are)h(adding)h(v)o(ectors)e(of)g(length) i(three.)k(Sequen)o(tial)d(program-)0 896 y(ming)j(languages)g (generally)h(pro)o(vide)f(a)f(lo)q(oping)i(mec)o(hanism)f(so)f(that)g (a)h(string)f(of)g(similar)i(ev)o(en)o(ts)f(can)f(b)q(e)0 954 y(enco)q(ded)f(without)e(explicit)i(rep)q(etition:)0 1030 y Fd(FOR)23 b(I=1)h(TO)f(3)0 1088 y(LET)g(C\(I\))h(=)f(A\(I\))h(+) g(B\(I\))0 1147 y(NEXT)f(I)0 1221 y Fh(In)18 b(the)g(functional)h (programming)e(mo)q(del,)i(w)o(e)e(are)h(trying)g(to)f(get)g(a)o(w)o(a) o(y)f(from)h(this)h(idea)h(of)e(a)g(sequence)i(of)0 1279 y(ev)o(en)o(ts.)k(F)l(or)15 b(one)i(thing,)f(w)o(e)g(ha)o(v)o(e)g(no)g (predetermined)i(place,)f(lik)o(e)g(the)f(arra)o(y)f Fd(C)h Fh(in)h(the)g(sequen)o(tial)g(v)o(ersion,)0 1337 y(to)d(put)h(the)f(result.)21 b(Still,)16 b(it's)e(p)q(ossible)i(to)e (express)h(the)g(output)f(v)m(alue)i(in)g(terms)e(of)g(comp)q(osition)h (of)g(built-in)0 1395 y(functions.)20 b(W)l(e)12 b(m)o(ust)f(use)i(the) f(addition)h(function)g Fd(SUM)p Fh(,)e(but)h(also)g(functions)h(that)f (select)h(particular)f(elemen)o(ts)0 1453 y(from)i(a)h(v)o(ector)g(or)g (com)o(bine)h(elemen)o(ts)f(in)o(to)h(a)e(new)i(v)o(ector:)0 1530 y Fd(TO)24 b(VECTOR.ADD)e(:V1)i(:V2)24 1588 y(OUTPUT)f(\(LIST)g (\(SUM)g(ITEM)h(1)f(:V1)h(ITEM)f(1)h(:V2\))334 1646 y(\(SUM)f(ITEM)h(2) f(:V1)h(ITEM)f(2)h(:V2\))334 1704 y(\(SUM)f(ITEM)h(3)f(:V1)h(ITEM)f(3)h (:V2\)\))0 1762 y(END)0 1837 y Fh(Again,)13 b(in)g(this)g(illustration) h(I)f(am)f(assuming)h(three-elemen)o(t)h(v)o(ectors.)k(I'v)o(e)12 b(used)i(the)e(built-in)j(function)f Fd(ITEM)0 1895 y Fh(to)k(select)h(one)g(elemen)o(t)g(from)f(a)g(v)o(ector)g(and)g(the)h (function)g Fd(LIST)f Fh(to)g(com)o(bine)h(sev)o(eral)g(elemen)o(ts)g (in)o(to)g(one)0 1953 y(v)o(ector.)f(\(I'v)o(e)13 b(formatted)f(this)i (pro)q(cedure)g(to)e(indicate)j(the)e(groupings)h(clearly)g(but)f(in)h (most)f(micro)q(computer)0 2011 y(v)o(ersions)i(of)g(Logo)g(the)g Fd(OUTPUT)f Fh(instruction)j(m)o(ust)d(b)q(e)i(en)o(tered)g(as)e(a)h (single,)h(long)g(line.\))91 2071 y(The)f(di\016cult)o(y)g(comes)g(in)g (generalizing)h(this)f(de\014nition)h(to)e(w)o(ork)g(with)g(v)o(ectors) g(of)g(an)o(y)g(length.)20 b(F)l(ormal)0 2129 y(mathematical)15 b(notation)g(has)g(no)g(trouble)h(with)467 2249 y(\()p Fc(a)509 2256 y Fb(1)529 2249 y Fc(;)8 b(a)574 2256 y Fb(2)594 2249 y Fc(;)g(a)639 2256 y Fb(3)658 2249 y Fh(\))i(+)h(\()p Fc(b)770 2256 y Fb(1)789 2249 y Fc(;)d(b)830 2256 y Fb(2)849 2249 y Fc(;)g(b)890 2256 y Fb(3)909 2249 y Fh(\))13 b(=)g(\()p Fc(a)1030 2256 y Fb(1)1060 2249 y Fh(+)d Fc(b)1125 2256 y Fb(1)1145 2249 y Fc(;)e(a)1190 2256 y Fb(2)1220 2249 y Fh(+)i Fc(b)1285 2256 y Fb(2)1305 2249 y Fc(;)e(a)1350 2256 y Fb(3)1380 2249 y Fh(+)i Fc(b)1445 2256 y Fb(3)1465 2249 y Fh(\))0 2342 y(but)15 b(when)h(w)o(e)f(w)o(an)o(t)f(to)h (generalize)h(w)o(e)f(m)o(ust)g(resort)f(to)h(ellipses:)479 2461 y(\()p Fc(a)521 2468 y Fb(1)542 2461 y Fc(;)8 b(:)g(:)g(:)t(;)g(a) 667 2468 y Fa(n)691 2461 y Fh(\))i(+)h(\()p Fc(b)803 2468 y Fb(1)822 2461 y Fc(;)d(:)g(:)g(:)d(;)j(b)944 2468 y Fa(n)967 2461 y Fh(\))13 b(=)g(\()p Fc(a)1088 2468 y Fb(1)1118 2461 y Fh(+)d Fc(b)1183 2468 y Fb(1)1203 2461 y Fc(;)e(:)g(:)g(:)d(;)j(a)1329 2468 y Fa(n)1363 2461 y Fh(+)j Fc(b)1429 2468 y Fa(n)1453 2461 y Fh(\))0 2554 y(This)16 b(notation)g(is)g(ok)m(a)o(y)f(on)h(pap)q(er)g(but)g (not)g(quite)g(what)f(w)o(e)h(w)o(an)o(t)e(for)i(a)f(computer)h (program.)k(The)c(mathe-)0 2612 y(matician's)e(solution)g(is)g(an)f (inductiv)o(e)j(de\014nition:)21 b(Imagine)14 b(that)f(w)o(e)g(kno)o(w) g(ho)o(w)g(to)g(add)g Fc(n)p Fh(-elemen)o(t)i(v)o(ectors,)0 2670 y(and)20 b(use)g(that)f(to)g(de\014ne)i(addition)g(of)e(v)o (ectors)g(with)h Fc(n)13 b Fh(+)h(1)19 b(elemen)o(ts.)34 b(T)l(o)20 b(do)g(this)g(w)o(e)f(need)i(a)e(function)964 2779 y(5)p eop %%Page: 6 6 6 5 bop 0 45 a Fh(\\adjoin")16 b(that)g(tak)o(es)f(a)h(n)o(um)o(b)q(er) h(and)g(a)f(v)o(ector)f(as)h(inputs,)i(giving)f(as)f(its)g(output)g(a)h (sligh)o(tly)g(longer)g(v)o(ector)0 104 y(including)h(the)d(new)h(n)o (um)o(b)q(er.)k(Then)c(w)o(e)f(can)g(sa)o(y)456 226 y(adjoin\()p Fc(a)620 233 y Fb(0)640 226 y Fc(;)8 b Fi(a)p Fh(\))i(+)g(adjoin\()p Fc(b)919 233 y Fb(0)939 226 y Fc(;)e Fi(b)p Fh(\))k(=)h(adjoin\()p Fc(a)1231 233 y Fb(0)1261 226 y Fh(+)e Fc(b)1327 233 y Fb(0)1347 226 y Fc(;)d Fi(a)h Fh(+)i Fi(b)p Fh(\))0 323 y(The)16 b(Logo)f(equiv)m(alen)o(t)i(of)e(adjoin)h(is)g(called)h Fd(FPUT)p Fh(,)e(for)f(\\\014rst)h(put.")21 b(It)15 b(tak)o(es)g(t)o(w) o(o)f(inputs.)22 b(The)16 b(\014rst)f(can)g(b)q(e)0 381 y(an)o(ything,)f(but)g(the)h(second)f(m)o(ust)g(b)q(e)h(a)e(list.)21 b(The)14 b(output)g(is)h(a)f(new)g(list)h(consisting)g(of)f(the)g(old)g (list)h(with)g(the)0 439 y(new)f(thing)h(put)f(in)h(fron)o(t.)j(T)l (aking)c(apart)f(a)h(v)o(ector)f(is)i(accomplished)h(with)e(the)g (functions)h Fd(FIRST)p Fh(,)d(to)i(extract)0 497 y(the)k(\014rst)g (elemen)o(t)i(of)e(a)g(list,)h(and)g Fd(BUTFIRST)p Fh(,)e(whose)h (output)g(is)h(a)f(list)h(equal)g(to)f(its)h(input)g(with)g(the)f (\014rst)0 555 y(elemen)o(t)e(remo)o(v)o(ed.)91 618 y(The)g(recursiv)o (e)h(de\014nition)h(of)e Fd(VECTOR.ADD)p Fh(,)e(then,)i(expresses)h (the)f(sum)g(of)g(its)g(input)h(v)o(ectors)f(in)h(terms)0 676 y(of)i(the)g(sum)g(of)g(t)o(w)o(o)f(smaller)i(v)o(ectors,)f(namely) g(the)h Fd(BUTFIRST)p Fh(s)e(of)g(the)i(inputs,)g(with)g(one)f(extra)g (n)o(um)o(b)q(er)0 734 y(adjoined,)12 b(namely)g(the)f(ordinary)g(n)o (umeric)h(sum)f(of)f(the)h Fd(FIRST)g Fh(elemen)o(ts)g(of)g(eac)o(h)g (v)o(ector.)18 b(Lik)o(e)12 b(an)o(y)e(inductiv)o(e)0 792 y(de\014nition,)18 b(it)f(needs)g(a)f(base)h(case.)24 b(This)17 b(one)f(sa)o(ys)g(that)g(the)g(sum)h(of)f(t)o(w)o(o)f (zero-length)i(\(empt)o(y\))f(v)o(ectors)f(is)0 850 y(the)i(empt)o(y)f (v)o(ector.)22 b(The)17 b(analysis)g(of)f Fd(MATRIX.ADD)f Fh(is)i(similar,)h(except)f(that)e(a)h(matrix)g(is)h(a)g(list)g(of)f(v) o(ectors)0 909 y(rather)f(than)g(a)g(list)h(of)e(n)o(um)o(b)q(ers.)0 1026 y Fi(Wh)o(y)j(Is)g(Recursion)g(Hard?)91 1144 y Fh(There)12 b(are)g(sev)o(eral)h(asp)q(ects)f(to)g(the)g(di\016cult)o(y)i(that)d (studen)o(ts)h(ha)o(v)o(e)g(in)h(coming)g(to)e(understand)i(recursiv)o (e)0 1202 y(programming)i(st)o(yle.)23 b(One)17 b(of)e(these)h(is)h (also)f(found)g(in)h(learning)g(to)f(accept)g(inductiv)o(e)i(pro)q (ofs:)d(the)h(sense)g(of)0 1260 y(unfairness)d(in)h(an)o(y)e (self-referen)o(tial)i(de\014nition.)21 b(\\Y)l(ou're)12 b(assuming)h(what)f(y)o(ou're)g(supp)q(osed)h(to)f(b)q(e)i(pro)o (ving!")0 1318 y(But)h(in)h(some)f(w)o(a)o(ys)f(the)i(di\016cult)o(y)g (is)g(greater)e(in)i(the)f(case)h(of)e(programming.)91 1382 y(An)19 b(inductiv)o(e)i(pro)q(of)e(can)h(b)q(e)g(presen)o(ted)f (\\ground)g(up.")33 b(W)l(e)19 b(sho)o(w)g(explicitly)j(that)c(the)h (theorem)g(is)0 1440 y(true)d(for)g Fc(n)e Fh(=)h(1.)23 b(Then,)16 b(b)o(y)h(the)f(inductiv)o(e)i(step,)e(w)o(e)g(can)g(see)h (that)f(it)g(m)o(ust)g(b)q(e)h(true)f(for)f Fc(n)g Fh(=)g(2.)22 b(Then,)17 b(b)o(y)0 1498 y(induction)f(again,)e(it)g(m)o(ust)f(also)h (b)q(e)h(true)f(for)f Fc(n)g Fh(=)g(3.)19 b(The)14 b(adv)m(an)o(tage)g (of)f(this)i(p)q(ersp)q(ectiv)o(e)g(is)g(that)e(eac)o(h)h(step)0 1556 y(is)h(tak)o(en)f(from)g(a)g(\014rm)h(fo)q(oting,)f(with)h (nothing)g(hanging)g(in)h(the)e(air.)20 b(That)14 b(is,)h(b)o(y)f(the)h (time)g(w)o(e)f(consider)i(the)0 1614 y(case)f Fc(n)e Fh(=)g(3)i(w)o(e)g(are)g(completely)h(satis\014ed)g(that)f(the)g (theorem)g(has)g(b)q(een)h(demonstrated)f(for)f Fc(n)f Fh(=)g(2.)91 1677 y(By)19 b(con)o(trast,)f(in)i(the)f(programming)f (con)o(text)h(the)g(more)f(usual)i(situation)g(is)f(that)f(w)o(e)h(ha)o (v)o(e)g(to)f(w)o(ork)0 1735 y(bac)o(kw)o(ards.)h(F)l(or)13 b(example,)h(w)o(e)g(are)f(presen)o(ted)i(with)f(a)f(pair)i(of)e (three-elemen)o(t)i(v)o(ectors)e(to)g(add.)20 b(That)13 b(is)h(our)0 1793 y(starting)i(p)q(oin)o(t.)23 b(W)l(e)16 b(then)h(sa)o(y)l(,)e(\\w)o(e)h(could)h(do)f(this)h(if)f(w)o(e)g(knew)h (ho)o(w)e(to)h(add)g(t)o(w)o(o-elemen)o(t)g(v)o(ectors.")22 b(The)0 1852 y(initial)16 b(problem)e(m)o(ust)f(b)q(e)i(susp)q(ended)g (while)h(w)o(e)d(consider)i(this)f(subproblem.)21 b(By)13 b(the)h(time)g(w)o(e)g(get)f(do)o(wn)h(to)0 1910 y(the)g(base)h(case)f (there)g(are)g(three)h(suc)o(h)f(susp)q(ended)i(problems.)k(This)15 b(state)f(of)f(a\013airs)h(is)h(a)f(c)o(hallenge)i(not)d(only)0 1968 y(to)g(our)h(faith)f(but)h(to)f(our)h(memory)l(.)19 b(It)14 b(is)g(v)o(ery)f(easy)h(to)f(lose)h(the)g(thread)f(of)h(con)o (texts)f(in)h(whic)o(h)h(subproblems)0 2026 y(arose.)27 b(The)18 b(di\013erence)h(b)q(et)o(w)o(een)f(the)g(pro)q(of)f(and)h (the)g(program)f(arises)h(b)q(ecause)h(in)f(the)g(pro)q(of)f(w)o(e)h (are)f(not)0 2084 y(sp)q(eci\014cally)f(concerned)e(with)g(an)o(y)f (concrete)g(example;)i(the)e(goal)g(is)h(a)f(general)h(truth,)e(and)i (it)f(mak)o(es)g(as)g(m)o(uc)o(h)0 2142 y(sense)19 b(to)f(start)f (small)i(as)f(not.)29 b(But)18 b(w)o(e)g(wrote)g(the)g(program)g(b)q (ecause)h(w)o(e)f(w)o(an)o(ted)g(to)g(solv)o(e)g(a)g(particular)0 2200 y(problem,)e(and)f(most)f(often)h(not)g(a)g(trivial)h(base-case)g (problem.)91 2263 y(F)l(or)21 b(teac)o(hing)i(purp)q(oses,)h(it)e(is)g (p)q(ossible)i(to)e(in)o(tro)q(duce)h(recursion)f(from)g(the)g(ground)g (up.)41 b(W)l(e)22 b(can)0 2321 y(in)o(tro)q(duce)15 b(a)f(general)h(problem,)g(then)g(decide)h(to)e(start)f(b)o(y)h (solving)h(the)g(simplest)g(p)q(ossible)h(case.)k(This)15 b(is)g(the)0 2380 y(metho)q(d)e(I)f(prefer)h(in)g(m)o(y)f(o)o(wn)g (teac)o(hing.)20 b(The)12 b(adv)m(an)o(tage)g(is)h(that)f(it)h(a)o(v)o (oids)f(the)g(sense)h(of)f(hanging)h(in)g(midair,)0 2438 y(but)i(there)g(are)g(t)o(w)o(o)f(costs.)19 b(First,)14 b(it)i(means)f(that)f(the)h(use)h(of)e(recursion)i(can't)f(b)q(e)g (motiv)m(ated)h(b)o(y)f(a)f(problem)0 2496 y(that)h(really)i(arises)f (in)h(class;)f(suc)o(h)g(problems)g(w)o(on't)f(b)q(e)i(so)e(simple.)23 b(Second,)17 b(although)f(the)g(studen)o(ts)f(don't)0 2554 y(feel)e(strained,)g(they)f(do)g(feel)h(fo)q(olish)g(during)g(the) f(b)q(eginning)i(stages)d(of)h(the)g(explanation.)20 b(The)12 b(recursiv)o(e)h(st)o(yle)0 2612 y(seems)k(lik)o(e)i(an)e(o)o (v)o(erly)g(complicated)i(approac)o(h)e(to)f(suc)o(h)i(simple)h (problems.)27 b(Then)17 b(the)h(more)f(complicated)0 2670 y(cases)e(can)g(feel)i(lik)o(e)f(rabbits)f(suddenly)i(pulled)h (from)c(a)h(hat.)964 2779 y(6)p eop %%Page: 7 7 7 6 bop 91 45 a Fh(Another)12 b(problem)g(in)h(learning)g(recursion)g (is)f(faced)h(b)o(y)e(studen)o(ts)h(who)g(ha)o(v)o(e)f(previous)i(exp)q (erience)h(in)f(the)0 104 y(sequen)o(tial)k(programming)f(st)o(yle.)22 b(They)17 b(are)e(strongly)h(tempted)g(to)g(in)o(terpret)g(the)g (recursiv)o(e)h(in)o(v)o(o)q(cation)f(as)0 162 y(a)e(lo)q(op,)g(an)g (instruction)h(to)f(\\do)f(it)i(again.")k(That)14 b(in)o(terpretation)g (can)g(sometimes)g(w)o(ork)f(for)h(recursiv)o(e)g(Logo)0 220 y(commands)j(\(programs)g(with)h(side-e\013ect)g(instructions\),)h (but)e(is)i(almost)e(nev)o(er)h(appropriate)f(for)g(recursiv)o(e)0 278 y(op)q(erations)h(\(functions)h(that)e(return)h(v)m(alues,)i(lik)o (e)f Fd(VECTOR.ADD)p Fh(\).)d(The)i(actual)g(sequence)i(of)d(ev)o(en)o (ts)h(in)h(the)0 336 y(computer)14 b(is)g(not)f(what)g(these)h(studen)o (ts)f(w)o(ould)h(predict,)h(in)f(whic)o(h)h(the)f(\014rst)f(in)o(v)o(o) q(cation)h(computes)g(the)f(\014rst)0 394 y(elemen)o(t,)19 b(then)f(the)g(second)g(tak)o(es)f(o)o(v)o(er.)27 b(It)18 b(w)o(ould)g(b)q(e)h(more)e(nearly)i(accurate)e(to)h(sa)o(y)f(that)g (the)h(sequence)0 452 y(happ)q(ens)h(bac)o(kw)o(ards;)e(the)h(\014rst)f (in)o(v)o(o)q(cation)i(can't)e(do)g(its)h(job)g(un)o(til)g(the)g (second)g(is)h(complete,)f(and)g(so)f(on.)0 510 y(So)e(it)h(is)f(the)h Fg(last)j Fh(in)o(v)o(o)q(cation,)c(the)g(one)h(for)e(the)h(base)h (case,)e(that)h(really)h(happ)q(ens)g(\014rst!)91 591 y(A)c(problem)g(related)h(to)e(the)h(\\do)f(it)h(again")g (misunderstanding)i(concerns)e(the)g(nature)g(of)f(lo)q(cal)i(v)m (ariables.)0 649 y(In)h(a)g(lo)q(op,)g(suc)o(h)g(as)g(the)f Fd(FOR)p Fh({)p Fd(NEXT)g Fh(examples)h(seen)h(earlier,)f(there)g(is)h (one)e(single)j(lo)q(op)e(v)m(ariable)h(whose)f(v)m(alue)0 707 y(k)o(eeps)j(c)o(hanging.)25 b(In)18 b(a)e(recursiv)o(e)i(pro)q (cedure,)f(the)g(relev)m(an)o(t)h(v)m(ariable)g(names)f(\(the)f(pro)q (cedure)i(inputs,)g(lik)o(e)0 765 y Fd(V1)d Fh(and)g Fd(V2)p Fh(\))g(do)g(not)g(corresp)q(ond)g(to)g(a)g(single)h(b)q(o)o(x) g(in)o(to)f(whic)o(h)h(c)o(hanging)g(v)m(alues)g(are)f(placed.)21 b(Rather,)15 b(eac)o(h)0 823 y(in)o(v)o(o)q(cation)i(of)f(the)g(pro)q (cedure)h(creates)f(a)g(new)h(set)f(of)g(v)m(ariables.)24 b(Sev)o(eral)17 b(suc)o(h)g(v)m(ariables)g(can)g(exist)f(at)g(the)0 881 y(same)g(time.)24 b(Studen)o(ts)16 b(ha)o(v)o(e)g(to)g(w)o(ork)g (out)g(ho)o(w)g(the)g(program)f(decides)j(whic)o(h)f(v)m(ariable)h(to)e (use)h(when)g(suc)o(h)0 939 y(a)e(name)g(app)q(ears)g(in)h(an)g (instruction.)0 1074 y Fi(F)l(unctional)j(Programming)e(Without)i (Recursion)91 1209 y Fh(One)g(language)f(sp)q(eci\014cally)j(designed)e (for)e(matrix)h(manipulation)h(is)g(APL.)f(T)l(o)f(add)i(t)o(w)o(o)d (matrices)i(in)0 1267 y(APL,)e(w)o(e)g(can)g(simply)i(use)e(the)h (built-in)h Fd(+)e Fh(op)q(eration.)23 b(Addition)18 b(in)f(APL)g(is)f(de\014ned)i(to)e(w)o(ork)f(for)g(scalars,)0 1325 y(v)o(ectors,)k(matrices,)g(or)f(higher-dimensional)k(arra)o(ys.) 30 b(The)19 b(APL)g(programmer)f(a)o(v)o(oids)h(b)q(oth)g(lo)q(oping)h (and)0 1383 y(recursion.)37 b(\(Of)21 b(course)g(there)g(is)g(some)g (kind)g(of)g(rep)q(etition)h(going)f(on)f(b)q(ehind)j(the)e(scenes,)h (if)g(the)f(APL)0 1441 y(program)13 b(is)i(running)g(on)f(a)g(con)o(v)o (en)o(tional)h(computer)f(that)g(can)g(only)h(p)q(erform)f(one)g (arithmetic)h(op)q(eration)g(at)0 1499 y(a)j(time.)28 b(But)18 b(this)h(rep)q(etition)g(is)f(in)o(visible)j(to)d(the)g (programmer,)f(just)g(as)h(ev)o(ery)g(language)g(mak)o(es)g(certain)0 1557 y(details)e(in)o(visible.\))91 1638 y(APL)h(encourages)f(a)h (functional)g(programming)f(st)o(yle.)24 b(The)17 b(addition)g(op)q (erator)f(is)h(a)f(function;)i(it)f(can)0 1696 y(b)q(e)i(comp)q(osed)g (with)f(other)g(functions)h(to)f(build)i(new,)f(more)e(complex)j (functions.)29 b(Because)19 b(the)g(primitiv)o(e)0 1754 y(functions)g(all)h(w)o(ork)d(on)h(arra)o(ys)f(as)h(w)o(ell)i(as)e (scalars,)h(man)o(y)f(problems)h(can)f(b)q(e)h(solv)o(ed)g(using)g (\\one-liners,")0 1812 y(programs)e(with)h(no)g(visible)j(con)o(trol)c (structures)h(at)f(all.)30 b(There)18 b(is)h(no)f(lo)q(oping)h (construct)f(in)h(APL.)f(When)0 1870 y(a)d(con)o(trol)g(mec)o(hanism)g (is)h(needed,)g(the)f(APL)g(programmer)f(can)h(c)o(ho)q(ose)g(b)q(et)o (w)o(een)h(t)o(w)o(o)e(extremes,)g(Logo-lik)o(e)0 1928 y(recursion)i(and)g(an)f(unstructured)h(\\goto")e(op)q(eration.)21 b(But)16 b(man)o(y)f(mathematical)h(problems)g(can)f(b)q(e)i(solv)o(ed) 0 1986 y(without)e(raising)h(the)f(issue)h(of)f(con)o(trol,)g(whic)o(h) h(is)f(adv)m(an)o(tageous)g(for)g(a)f(math)h(teac)o(her.)91 2067 y(Unfortunately)l(,)20 b(APL)g(is)g(not)f(widely)i(a)o(v)m (ailable.)34 b(The)20 b(largest)f(obstacle)g(is)h(that)f(it)h(uses)f(a) g(notation)0 2125 y(v)o(ery)14 b(close)i(to)e(that)g(of)g(ordinary)h (mathematics,)f(full)j(of)d(Greek)g(letters)h(and)g(other)g(strange)f (sym)o(b)q(ols.)20 b(These)0 2183 y(are)d(not)h(part)f(of)g(the)h (standard)f(computer)g(c)o(haracter)g(set,)h(and)g(sp)q(ecial)h(hardw)o (are)e(is)h(required)h(to)e(displa)o(y)0 2241 y(them.)29 b(\(Indeed,)20 b(there)f(aren't)e(enough)i(k)o(eys)f(ev)o(en)h(on)f (the)g(APL)h(k)o(eyb)q(oard.)29 b(Some)19 b(sym)o(b)q(ols)f(are)g (formed)0 2299 y(b)o(y)d(o)o(v)o(erprin)o(ting)g(t)o(w)o(o)f(other)g (sym)o(b)q(ols.)20 b(This)c(approac)o(h)f(w)o(as)f(designed)i(for)f (hardcop)o(y)g(computer)g(terminals,)0 2357 y(whic)o(h)i(bac)o(kspace)g (and)f(o)o(v)o(erprin)o(t)g(naturally)l(.)25 b(It)16 b(isn't)h(suitable)g(for)f(most)g(curren)o(t)g(displa)o(y)h(devices,)h (whic)o(h)0 2415 y(allo)o(w)d(only)h(one)g(c)o(haracter)e(in)i(an)o(y)f (screen)h(p)q(osition.\))91 2496 y(Can)h(w)o(e)h(use,)g(in)h(Logo,)e (the)h(APL)g(idea)g(of)g(op)q(erating)g(on)f(a)h(v)o(ector)f(or)g (matrix)g(\\all)h(at)g(once,")g(rather)0 2554 y(than)12 b(explicitly)j(manipulating)e(eac)o(h)g(elemen)o(t)f(individual)q(ly?) 23 b(T)l(o)q(ols)12 b(for)g(this)g(programming)g(metaphor)f(ha)o(v)o(e) 0 2612 y(long)17 b(b)q(een)h(part)e(of)h(LISP)l(,)h(Logo's)e(paren)o(t) g(language.)25 b(It)17 b(is)h(an)e(easy)h(matter)f(to)g(extend)i(Logo)e (\(b)o(y)g(writing)0 2670 y(pro)q(cedures)g(in)g(Logo)f(and)g(loading)h (them)f(for)g(studen)o(ts\))g(with)g(suc)o(h)h(to)q(ols.)964 2779 y(7)p eop %%Page: 8 8 8 7 bop 0 45 a Fi(Av)o(oiding)17 b(Recursion)h(in)g(Logo)91 176 y Fh(Let)d(me)h(b)q(egin)g(b)o(y)f(de\014ning)i(a)e(few)g(simple)i (arithmetic)e(pro)q(cedures.)0 254 y Fd(TO)24 b(SQUARE)f(:X)24 312 y(OUTPUT)g(:X)g(*)h(:X)0 370 y(END)0 486 y(TO)g(NEXT)f(:X)24 544 y(OUTPUT)g(:X)g(+)h(1)0 602 y(END)0 718 y(TO)g(DOUBLE)f(:X)24 777 y(OUTPUT)g(:X)g(*)h(2)0 835 y(END)0 926 y Fh(No)o(w)15 b(consider)h(these)f(in)o(teractions)h(with)f(Logo:)0 1003 y Fd(?)24 b(SHOW)f(MAP)g("SQUARE)g([2)h(3)g(4)f(5])0 1062 y([4)h(9)f(16)h(25])0 1120 y(?)g(SHOW)f(MAP)g("NEXT)h([7)f(8)h(9]) 0 1178 y([8)g(9)f(10])0 1236 y(?)h(SHOW)f(MAP)g("DOUBLE)g([5)h(3)g(20)f (6)h(1])0 1294 y([10)f(6)h(40)g(12)f(2])0 1385 y Fh(The)18 b(pro)q(cedures)g Fd(SQUARE)f Fh(and)g(so)g(on)h(are)f(de\014ned)h(to)f (op)q(erate)h(on)f(scalars.)26 b(The)18 b(general)g(to)q(ol)f(called)i Fd(MAP)0 1443 y Fh(allo)o(ws)c(these)h(functions)g(to)e(w)o(ork)h(on)g (v)o(ectors,)f(b)o(y)h(arranging)g(to)f(apply)i(a)f(function)h(to)f (eac)o(h)g(elemen)o(t)h(of)f(the)0 1501 y(v)o(ector.)k(The)c(output)f (from)g Fd(MAP)g Fh(is)i(another)e(v)o(ector)g(with)h(the)f(same)h(n)o (um)o(b)q(er)g(of)f(elemen)o(ts,)h(but)g(with)g(v)m(alues)0 1559 y(computed)h(b)o(y)f(the)g(function)h(b)q(eing)h(mapp)q(ed.)91 1635 y(Logo)c(is)g(an)g(extensible)i(language.)k(This)14 b(means)f(that)f(a)h(user-de\014ned)i(pro)q(cedure)f(is)f(in)o(v)o(ok)o (ed)h(in)g(exactly)0 1693 y(the)22 b(same)f(w)o(a)o(y)f(as)h(a)h (primitiv)o(e)g(pro)q(cedure.)40 b Fd(MAP)21 b Fh(happ)q(ens)i(not)e (to)g(b)q(e)h(a)f(Logo)g(primitiv)o(e,)j(but)e(if)g(it)f(is)0 1751 y(included)d(in)e(a)f(startup)g(\014le)h(it)g(can)f(b)q(e)h (presen)o(ted)g(to)f(studen)o(ts)g(just)g(as)g(if)h(it)f(w)o(ere)g(a)g (primitiv)o(e.)22 b(Its)15 b(purp)q(ose)0 1809 y(is)i(immediately)h (clear,)f(and)g(should)h(presen)o(t)e(no)h(conceptual)g(problems)h(to)e (studen)o(ts.)23 b(The)17 b(same)f(idea)i(can)0 1868 y(b)q(e)e(extended)g(to)f(functions)h(of)e(t)o(w)o(o)g(inputs:)0 1945 y Fd(?)24 b(SHOW)f(MAP.2)g("SUM)h([1)f(2)h(3])f([40)h(50)f(60])0 2003 y([41)g(52)h(63])0 2062 y(?)g(SHOW)f(MAP.2)g("PRODUCT)g([5)h(6])f ([7)h(8])0 2120 y([35)f(48])0 2178 y(?)h(SHOW)f(MAP.2)g("EQUALP)g([1)h (4)f(6)h(7])g([30)f(4)h(5)g(9])0 2236 y([FALSE)f(TRUE)g(FALSE)h(FALSE]) 0 2327 y(MAP.2)18 b Fh(requires)h(three)f(inputs,)h(a)f(function)h(and) g(t)o(w)o(o)e(lists.)29 b(The)19 b(t)o(w)o(o)e(lists)i(m)o(ust)f(ha)o (v)o(e)f(the)i(same)f(length,)0 2385 y(and)d(the)h(output)f(will)i(ha)o (v)o(e)d(that)h(length)h(also.)91 2461 y(W)l(e)f(are)g(no)o(w)g(in)h(a) f(p)q(osition)h(to)e(return)i(to)e(the)h(problem)h(of)f(matrix)g (addition)h(with)g(whic)o(h)g(w)o(e)f(b)q(egan:)0 2539 y Fd(TO)24 b(MATRIX.ADD)e(:M1)i(:M2)24 2597 y(OUTPUT)f(MAP.2)g ("VECTOR.ADD)f(:M1)i(:M2)0 2655 y(END)964 2779 y Fh(8)p eop %%Page: 9 9 9 8 bop 0 45 a Fd(TO)24 b(VECTOR.ADD)e(:V1)i(:V2)24 104 y(OUTPUT)f(MAP.2)g("SUM)g(:V1)h(:V2)0 162 y(END)0 240 y Fh(That's)19 b(it!)35 b(I)21 b(\014nd)f(this)h(v)o(ersion)f(simpler)i (than)e(the)g(original)h(BASIC)g(program)e(with)i(nested)f Fd(FOR)g Fh(lo)q(ops.)0 298 y(There)14 b(are)g(no)g(auxiliary)h(v)m (ariables)g Fd(I)f Fh(and)g Fd(J)p Fh(;)f(there)h(is)h(no)f(need)g(to)g (build)i(the)e(size)h(or)e(shap)q(e)h(of)g(the)g(matrices)0 356 y(in)o(to)h(the)h(pro)q(cedures.)21 b(Once)16 b(the)f(general)h (idea)g(of)f Fd(MAP)g Fh(is)g(understo)q(o)q(d,)h(its)f(application)i (to)e(this)g(problem)h(is)0 414 y(straigh)o(tforw)o(ard.)91 478 y(The)f Fd(MAP)g Fh(and)g Fd(MAP.2)f Fh(pro)q(cedures)i(themselv)o (es)f(are,)g(naturally)l(,)g(a)g(little)h(more)f(complicated.)21 b(They)15 b(are)0 536 y(de\014ned)g(recursiv)o(ely)l(,)f(using)g(some)f (of)g(the)g(more)g(adv)m(anced)h(capabilities)i(of)c(Logo.)19 b(If)14 b(studen)o(ts)f(\(or)f(teac)o(hers!\))0 594 y(w)o(an)o(t)j(to)g (understand)h(the)g(inner)g(w)o(orkings)g(of)f(these)h(to)q(ols,)f (they)h(m)o(ust)f(face)g(the)h(c)o(hallenge)h(of)f(recursion.)22 b(I)0 652 y(think)13 b(this)f(is)g(\014ne;)i(p)q(eople)f(who)e(are)h (in)o(terested)g(in)h(programming)e(m)o(ust,)h(ev)o(en)o(tually)l(,)h (understand)g(recursion.)0 711 y(The)h(p)q(oin)o(t)h(is)f(that)g(that)f (understanding)i(no)f(longer)g(has)g(to)g(come)g(\014rst.)19 b(The)14 b(mathematics)g(can)g(b)q(e)h(studied)0 769 y(and)h(the)f(programming)g(issues)h(can)g(b)q(e)g(p)q(ostp)q(oned.)22 b(\(The)15 b(Logo)g(de\014nitions)j(of)d(all)h(the)g(to)q(ols)f(presen) o(ted)h(in)0 827 y(this)g(pap)q(er)f(are)g(collected)i(in)f(an)f(app)q (endix.\))0 945 y Fi(T)l(emplates)91 1064 y Fh(One)j(problem)h(with)e (the)h(mapping)g(to)q(ols)g(as)f(I'v)o(e)h(presen)o(ted)g(them)f(ab)q (o)o(v)o(e)g(is)h(that)f(w)o(e)h(m)o(ust)f(de\014ne)h(a)0 1122 y(named)i(scalar)f(function)h(in)g(order)f(to)g(use)g(that)g(name) g(as)g(an)g(input)h(to)f Fd(MAP)p Fh(.)g(F)l(or)f(example,)j(when)f(I)f (\014rst)0 1180 y(in)o(tro)q(duced)e Fd(MAP)p Fh(,)d(I)i(had)f(to)g (detour)g(through)g(de\014nitions)i(of)e Fd(SQUARE)p Fh(,)f Fd(NEXT)p Fh(,)g(and)i Fd(DOUBLE)e Fh(in)j(order)e(to)f(ha)o(v)o (e)0 1238 y(something)22 b(to)f(map)h(o)o(v)o(er)f(the)h(v)o(ectors)f (in)h(the)g(examples.)41 b(It's)21 b(not)h(so)f(bad)h(to)f(ha)o(v)o(e)h (names)g(for)f(these)0 1296 y(functions,)16 b(since)h(the)f(functions)g (are)f(useful)i(in)g(themselv)o(es)f(and)g(the)f(names)h(are)f (sensible.)23 b(But)16 b(sometimes)0 1354 y(w)o(e)g(need)i(an)f Fg(ad)h(ho)n(c)h Fh(function)f(just)e(for)g(one)h(particular)g(mapping) h(op)q(eration.)25 b(The)16 b(problem)i(will)g(b)q(ecome)0 1413 y(clearer)e(if)f(w)o(e)g(consider)h(an)g(example.)91 1477 y(W)l(e)f(w)o(ould)h(lik)o(e)g(to)e(b)q(e)i(able)g(to)e(m)o (ultiply)j(a)e(matrix)g(b)o(y)g(a)g(scalar.)k(That)c(is,)g(w)o(e)g(w)o (an)o(t)f(to)g(b)q(e)i(able)g(to)f(sa)o(y)0 1553 y Fd(?)24 b(SHOW)f(MATRIX.SCALE)f(3)i([[1)f(2)h(3])g([4)f(5)h(6]])0 1612 y([[3)f(6)h(9])g([12)f(15)h(18]])0 1690 y Fh(The)19 b(function)g Fd(MATRIX.SCALE)e Fh(\(I'm)h(sa)o(ving)h(the)g(name)f Fd(MULTIPLY)g Fh(for)g(m)o(ultiplication)j(of)d(a)g(matrix)h(b)o(y)f(a) 0 1748 y(matrix\))e(tak)o(es)f(t)o(w)o(o)g(inputs,)i(a)g(n)o(um)o(b)q (er)f(and)h(a)f(matrix.)23 b(Its)16 b(output)g(is)h(a)f(matrix)g(with)h (the)f(same)g(shap)q(e)h(as)0 1806 y(the)e(input,)h(but)f(with)h(eac)o (h)f(elemen)o(t)h(m)o(ultiplied)i(b)o(y)d(the)h(n)o(um)o(b)q(er.)91 1870 y(It)f(ma)o(y)g(b)q(e)h(tempting)f(to)g(write)g Fd(MATRIX.SCALE)e Fh(as)i(follo)o(ws:)0 1947 y Fd(TO)24 b(MATRIX.SCALE)e(:NUM)h(:MAT)477 b(;)24 b(incorrect!)24 2005 y(OUTPUT)f(MAP.2)g("VECTOR.SCALE)f(:NUM)h(:MAT)0 2063 y(END)0 2179 y(TO)h(VECTOR.SCALE)e(:NUM)h(:VEC)24 2237 y(OUTPUT)g(MAP.2)g("PRODUCT)g(:NUM)g(:VEC)0 2295 y(END)0 2374 y Fh(This)d(lo)q(oks)f(lik)o(e)h(a)f(straigh)o(tforw)o (ard)e(application)k(of)e(the)g(same)g(ideas)h(w)o(e)f(used)g(in)h Fd(MATRIX.ADD)p Fh(,)e(but)h(the)0 2432 y(parallel)f(do)q(esn't)e(w)o (ork.)22 b(The)17 b(problem)g(is)f(that)g Fd(MAP.2)f Fh(requires)i(t)o(w)o(o)e Fg(lists)k Fh(of)d(equal)h(length)g(so)f (that)f(it)i(can)0 2490 y(inductiv)o(ely)e(step)e(through)f(them,)h (applying)h(the)e(function)i(input)g(to)e(pairs)g(of)h(elemen)o(ts.)19 b(Here)13 b(w)o(e)g(are)f(trying)0 2548 y(to)j(use)g(a)g(single)h(n)o (um)o(b)q(er)g Fd(:NUM)f Fh(rep)q(eatedly)l(.)91 2612 y(There)e(is)h(really)g(only)g(one)f(matrix)g(input)h(in)g(this)f (problem,)h(not)f(t)o(w)o(o,)f(and)h(so)g(w)o(e)g(need)h(a)e(solution)i (using)0 2670 y Fd(MAP)p Fh(,)g(not)h Fd(MAP.2)p Fh(.)k(It)d(w)o(ould)f (b)q(e)h(easy)f(enough)h(to)e(do)h(this)h(for)e(an)o(y)h(sp)q(eci\014c) i(scale)f(factor:)964 2779 y(9)p eop %%Page: 10 10 10 9 bop 0 45 a Fd(TO)24 b(TIMES3)f(:X)24 104 y(OUTPUT)g(3)h(*)f(:X)0 162 y(END)0 278 y(TO)h(MATRIX.SCALE3)e(:MAT)24 336 y(OUTPUT)h(MAP)g ("VECTOR.SCALE3)f(:MAT)0 394 y(END)0 510 y(TO)i(VECTOR.SCALE3)e(:VEC)24 568 y(OUTPUT)h(MAP)g("TIMES3)g(:VEC)0 626 y(END)0 713 y Fh(But)16 b(it's)f(not)g(ob)o(vious)h(ho)o(w)f(to)g(generalize)i (this)f(in)o(to)g(the)f(desired)i Fd(MATRIX.SCALE)d Fh(function.)22 b(W)l(e'd)15 b(ha)o(v)o(e)h(to)0 771 y(b)q(e)g(able)g(to)e(in)o(v)o(en) o(t)i(the)f(functions)h(lik)o(e)g Fd(TIMES3)f Fh(\\on)g(the)g(\015y)l (.")91 842 y(The)f(problem)h(w)o(e)f(are)g(exp)q(eriencing)j(here)e (turns)f(out)g(to)g(b)q(e)h(similar)g(to)f(the)g(problem)h(that)f (encouraged)0 900 y(us)h(to)f(switc)o(h)g(from)g(BASIC)h(to)f(Logo)g (as)h(the)f(medium)i(for)e(matrix)g(manipulation.)21 b(In)15 b(BASIC,)g(w)o(e)f(couldn't)0 958 y(compute)22 b(the)g(sum)h(of)e(t)o(w)o(o)g(matrices)h(without)g(putting)h(the)f (result)g(in)h(a)f(sp)q(eci\014c)i(named)e(arra)o(y)f Fd(C)p Fh(.)h(An)0 1016 y(arra)o(y)e(couldn't)h(exist)h(as)f(a)f(real)i (ob)s(ject)e(on)h(its)h(o)o(wn,)f(without)g(a)g(name.)38 b(Logo)20 b(lists,)j(b)o(y)e(con)o(trast,)g(are)0 1074 y(\014rst-class)16 b(ob)s(jects)f(that)f(can)i(b)q(e)g(en)o(tered)g (directly)h(as)e(argumen)o(ts)g(to)g(functions)h(lik)o(e)h Fd(MATRIX.ADD)d Fh(without)0 1133 y(the)k(in)o(termediate)g(step)g(of)f (assigning)i(them)e(as)h(the)f(v)m(alue)i(of)e(a)h(named)g(v)m (ariable.)28 b(What)17 b(w)o(e)h(need)g(no)o(w)f(is)0 1191 y Fg(\014rst-class)e(functions)p Fh(.)k(W)l(e)c(w)o(an)o(t)f(to)h (b)q(e)h(able)g(to)e(sa)o(y)h(\\the)g(function)h(3)f(times)g Fc(x)p Fh(")g(as)g(an)g(input)h(to)f Fd(MAP)p Fh(.)91 1262 y(First-class)i(functions)h(are)e(one)i(of)e(the)h(cen)o(tral)g (ideas)h(of)e(LISP)l(,)i(the)f(language)g(from)f(whic)o(h)i(Logo)f(w)o (as)0 1320 y(dev)o(elop)q(ed.)33 b(Logo)19 b(itself)h(do)q(es)g(not)f (include)i(LISP's)f(mec)o(hanism)g(for)e(this)i(purp)q(ose,)g(but)g(it) f(do)q(es)h(include)0 1378 y(other)13 b(mec)o(hanisms)i(that)e(allo)o (w)h(us)g(to)f(implemen)o(t)i(\014rst-class)f(functions)g(within)h (Logo.)k(W)l(e)14 b(can)g(put)g(a)f(Logo)0 1436 y(expression)j(in)g(a)f (list,)h(lik)o(e)0 1514 y Fd([3)24 b(*)f(:X])0 1600 y Fh(and)16 b(then)g(w)o(e)f(can)h(ask)f(Logo)g(to)g Fd(RUN)g Fh(the)h(list.)21 b(That)15 b(is,)h(the)g(function)g Fd(RUN)f Fh(tak)o(es)g(an)h(expression)g(list)h(as)e(its)0 1658 y(input,)h(and)f(giv)o(es)h(the)f(v)m(alue)h(of)f(the)g (expression)h(as)f(its)h(output.)91 1729 y(It)f(ma)o(y)g(seem)g(that)f (this)i(is)g(all)g(w)o(e)f(need.)21 b(W)l(e)15 b(could)h(write)0 1807 y Fd(OUTPUT)23 b(MAP)g([3)h(*)g(:X])f(:VEC)0 1893 y Fh(instead)16 b(of)0 1970 y Fd(OUTPUT)23 b(MAP)g("TIMES3)g(:VEC)0 2056 y Fh(and)14 b(just)g(design)h(the)f Fd(MAP)f Fh(pro)q(cedure)i(so) f(that)f(it)h(runs)h(the)f(expression)g(list)h(for)f(eac)o(h)g(elemen)o (t)g(of)g(the)g(v)o(ector.)0 2115 y(This)f(is)h(almost)e(the)h(righ)o (t)g(thing,)g(but)g(there)g(is)g(a)g(mathematical)g(confusion)g(in)o(v) o(olv)o(ed.)20 b(An)13 b(expression)h(is)f(not)0 2173 y(the)g(same)g(thing)g(as)f(a)h(function.)20 b(In)13 b(mathematical)g(notation,)g(w)o(e)f(don't)h(sa)o(y)f Fc(f)18 b Fh(=)13 b(3)p Fc(x)p Fh(;)g(w)o(e)f(sa)o(y)g Fc(f)5 b Fh(\()p Fc(x)p Fh(\))13 b(=)g(3)p Fc(x)p Fh(.)18 b(In)0 2231 y(this)12 b(particular)g(example)g(the)g(di\013erence)h(ma) o(y)d(not)h(seem)h(imp)q(ortan)o(t;)g Fc(x)f Fh(is)h(the)g(only)g(v)m (ariable)h(around,)f(and)f(so)0 2289 y(it's)h(ob)o(vious)g(what)g(is)g (mean)o(t.)19 b(But)12 b(consider)h(the)f(di\013erence)i(b)q(et)o(w)o (een)e Fc(f)5 b Fh(\()p Fc(a;)j(b)p Fh(\))j(=)i(2)p Fc(a)t Fh(+)t Fc(b)f Fh(and)g Fc(g)r Fh(\()p Fc(b;)c(a)p Fh(\))i(=)j(2)p Fc(a)t Fh(+)t Fc(b)p Fh(.)0 2347 y(These)g(t)o(w)o(o)e(functions)i(are) g(not)f(equiv)m(alen)o(t,)i(ev)o(en)f(though)g(they)f(are)g(de\014ned)i (b)o(y)f(the)f(same)h(expression)g(2)p Fc(a)5 b Fh(+)g Fc(b)p Fh(.)91 2418 y(A)15 b(similar)g(naming)g(problem)h(arises)f(in)g (the)g Fd(SCALE)f Fh(problem.)20 b(If)15 b(w)o(e)f(just)h(w)o(an)o(t)e (to)h(scale)i(b)o(y)e(3,)g(then)h(w)o(e)0 2476 y(could)h(sa)o(y)f(that) f(there's)h(only)h(one)f(v)m(ariable)i(around.)j(But)15 b(w)o(e)g(are)g(going)g(to)f(w)o(an)o(t)h(to)f(write)h(something)h(lik) o(e)0 2554 y Fd(TO)24 b(VECTOR.SCALE)e(:NUM)h(:VEC)24 2612 y(OUTPUT)g(MAP)g([:NUM)h(*)f(:X])h(:VEC)0 2670 y(END)952 2779 y Fh(10)p eop %%Page: 11 11 11 10 bop 0 45 a Fh(In)15 b(this)g(situation)f(it's)g(not)g(ob)o(vious) h(ho)o(w)f Fd(MAP)f Fh(should)j(kno)o(w)d(that)h(the)g(v)m(ariable)i Fd(NUM)e Fh(has)g(a)g(particular)h(v)m(alue)0 104 y(assigned)i(to)f(it) g(externally)l(,)i(while)g(the)e(v)m(ariable)i Fd(X)e Fh(is)h(the)f(one)g(in)o(to)h(whic)o(h)g(it)g(should)g(plug)g(the)f (elemen)o(ts)h(of)0 162 y(the)h(v)o(ector.)27 b(The)18 b(traditional)h(LISP)g(solution)g(is)f(to)f(represen)o(t)h(a)g (function)h(as)e(a)h Fg(lamb)n(da)g(expr)n(ession)j Fh(that)0 220 y(con)o(tains)11 b(the)h(names)f(of)g(the)g(input)h(v)m(ariables)h (as)e(w)o(ell)h(as)f(the)g(de\014ning)i(expression.)19 b(So)11 b(in)h(LISP)h(w)o(e)e(migh)o(t)g(sa)o(y)0 295 y Fd(\(DEFINE)23 b(F)h(\(LAMBDA)f(\(A)g(B\))h(\(+)f(\(*)h(2)g(A\))f (B\)\)\))0 353 y(\(DEFINE)g(G)h(\(LAMBDA)f(\(B)g(A\))h(\(+)f(\(*)h(2)g (A\))f(B\)\)\))0 424 y Fh(\(LISP)14 b(uses)g(pre\014x)g(form)e Fd(\(*)24 b(2)g(A\))13 b Fh(rather)g(than)g(in\014x)i(form)d Fd(\(2)24 b(*)g(A\))13 b Fh(to)g(represen)o(t)g(arithmetic)h(op)q (erations.)0 482 y(But)i(the)g(imp)q(ortan)o(t)g(p)q(oin)o(t)h(for)e (our)h(purp)q(oses)h(is)g(to)e(notice)i(the)f(di\013erence)i(b)q(et)o (w)o(een)e Fd(F)g Fh(and)g Fd(G)p Fh(,)g(namely)h(the)0 541 y(list)f(of)f(parameter)f(names)h(follo)o(wing)h(the)g(w)o(ord)e Fd(LAMBDA)p Fh(.\))91 599 y(It)h(w)o(ould)h(b)q(e)g(p)q(ossible)h(to)d (in)o(v)o(en)o(t)h(this)h(precise)g(mec)o(hanism)g(for)f(Logo.)k(Then)d (w)o(e)f(could)h(sa)o(y)0 674 y Fd(TO)24 b(VECTOR.SCALE)e(:NUM)h(:VEC) 24 732 y(OUTPUT)g(MAP)g([LAMBDA)g([X])h([3)f(*)h(:X]])f(:VEC)0 790 y(END)0 861 y Fh(The)17 b(trouble)g(is)h(that)e(this)h(notation)f (seems)h(needlessly)i(obtrusiv)o(e.)25 b(If)17 b(w)o(e)g(presen)o(t)f (this)i(to)e(studen)o(ts,)g(their)0 919 y(atten)o(tion)k(will)i(b)q(e)f (fo)q(cused)g(on)f(the)h(meaning)g(of)f(the)g(notation,)h(rather)f (than)g(on)h(matrix)f(arithmetic.)36 b(I)0 978 y(w)o(an)o(ted)13 b(to)g(\014nd)i(a)e(b)q(etter)h(alternativ)o(e.)20 b(A)14 b(quic)o(k-and-dirt)o(y)h(solution)g(w)o(ould)f(b)q(e)g(to)g(sa)o(y)f (that)g(the)h(parameter)0 1036 y(to)i(ev)o(ery)g(function)h(m)o(ust)f (b)q(e)h(called)g Fd(X)p Fh(;)f(for)g(t)o(w)o(o-input)g(functions)h(w)o (e)f(could)h(reserv)o(e)g Fd(X)f Fh(and)g Fd(Y)p Fh(.)g(That)g(w)o (ould)0 1094 y(w)o(ork,)g(but)g(it)h(seems)g(ugly)g(to)f(me.)24 b(It)17 b(w)o(ould)g(prev)o(en)o(t)f(the)h(use)g(of)f(those)g(names)h (for)f(other)g(purp)q(oses.)25 b(\(F)l(or)0 1152 y(example,)16 b(what)e(if)i(I'd)f(w)o(an)o(ted)g(to)g(call)h(the)f(scale)h(factor)e Fd(X)h Fh(instead)h(of)f Fd(NUM)p Fh(?\))91 1210 y(I)k(to)q(ok)f(m)o(y) h(inspiration)h(from)e(an)h(earlier)h(problem)f(in)h(mathematics)f (education)h(that)e(seems)h(closely)0 1268 y(related.)h(Some)14 b(of)f(the)h(early)g(New)g(Math)g(exp)q(erimen)o(ters)g(w)o(an)o(ted)g (to)f(use)h(algebraic)h(ideas)f(with)h(elemen)o(tary)0 1326 y(sc)o(ho)q(ol)h(studen)o(ts,)e(presen)o(ting)i(v)o(ery)f(simple)i (equations)e(lik)o(e)881 1442 y Fc(x)10 b Fh(+)h(3)h(=)h(7)0 1529 y(They)f(found)h(that)e(the)h(underlying)i(idea)f(of)f(\\what)f (plus)i(three)f(is)h(sev)o(en?")f(w)o(asn't)f(to)q(o)h(di\016cult,)h (but)g(that)e(the)0 1587 y Fc(x)i Fh(notation)f(w)o(as)g(a)g(problem)h (for)f(some)h(studen)o(ts.)19 b(Their)13 b(solution)g(w)o(as)f(to)g (presen)o(t)h(the)f(equation)i(in)f(the)g(form)p 855 1656 79 2 v 855 1729 2 73 v 932 1729 V 855 1731 79 2 v 944 1704 a(+)d(3)j(=)g(7)0 1796 y(P)o(edagogically)l(,)k(the)f(b)q(o) o(x)h(seems)f(to)f(suggest)h(\\this)g(is)h(a)f(slot)g(to)g(b)q(e)h (\014lled")g(without)g(raising)f(the)h(di\016culties)0 1854 y(ab)q(out)e(names)h(and)f(v)m(alues)i(that)d(studen)o(ts)h (\014nd)i(with)e Fc(x)p Fh(.)21 b(Unfortunately)15 b(there)h(is)f(no)h (b)q(o)o(x)f(c)o(haracter)g(in)h(the)0 1912 y(ASCI)q(I)j(sequence,)h (but)e(I)g(w)o(an)o(ted)f(to)h(come)g(as)f(close)i(as)e(p)q(ossible)j (to)d(this)i(ideal)g(of)f(a)f(graphically)j(ob)o(vious)0 1970 y(slot)15 b(indication.)22 b(My)15 b(solution)h(w)o(as)e(to)h(use) g(a)g(question)h(mark:)0 2046 y Fd(?)24 b(SHOW)f(MAP)g([3)h(*)g(?])f ([2)h(3)g(4])0 2104 y([6)g(9)f(12])0 2162 y(?)h(SHOW)f(MAP)g([?)h(*)g (?])f([2)h(3)g(4)f(5])0 2220 y([4)h(9)f(16)h(25])0 2278 y(?)g(SHOW)f(MAP)g([IFELSE)g(\(?)h(<)g(0\))f([-?])h([?]])f([2)h(-3)f (12)h(0)f(-14])0 2336 y([2)h(3)f(12)h(0)g(14])0 2407 y Fh(An)15 b(expression)i(list)f(with)f(a)g(question)h(mark)e(slot)h (to)g(b)q(e)h(\014lled)h(is)f(called)g(an)g(expression)g Fg(template)p Fh(.)91 2465 y(W)l(e)f(can)h(no)o(w)e(solv)o(e)i(the)f Fd(SCALE)f Fh(problem:)0 2541 y Fd(TO)24 b(MATRIX.SCALE)e(:NUM)h(:MAT) 24 2599 y(OUTPUT)g(MAP)g([VECTOR.SCALE)f(:NUM)i(?])f(:MAT)0 2657 y(END)952 2779 y Fh(11)p eop %%Page: 12 12 12 11 bop 0 45 a Fd(TO)24 b(VECTOR.SCALE)e(:NUM)h(:VEC)24 104 y(OUTPUT)g(MAP)g([:NUM)h(*)f(?])h(:VEC)0 162 y(END)91 240 y Fh(W)l(e)15 b(ha)o(v)o(e)f(redesigned)i Fd(MAP)f Fh(to)f(accept)h(templates)g(instead)g(of)g(named)g(functions.)20 b(What)15 b(ab)q(out)f Fd(MAP.2)p Fh(?)0 298 y(W)l(e)h(need)h(a)f(w)o (a)o(y)f(to)h(express)g(templates)h(with)f(t)o(w)o(o)f(slots.)20 b(My)15 b(solution)h(is)f(to)g(name)g(the)g(slots)g Fd(?1)g Fh(and)h Fd(?2)p Fh(.)0 375 y Fd(?)24 b(SHOW)f(MAP.2)g([?2)h(-)f(?1])h ([1)f(2)h(3])g([15)f(20)h(30])0 433 y([14)f(18)h(27])0 511 y Fh(This)12 b(do)q(esn't)g(seem)g(quite)g(so)g(comp)q(elling)i(as) d(the)h(unadorned)g(question)h(mark,)e(just)g(as)h(New)g(Math)f (equations)0 569 y(with)j(b)q(o)o(xes)f(and)g(triangles)h(seem)f(more)g (cluttered)h(and)f(less)h(ob)o(vious)g(than)f(the)g(ones)g(with)h(only) f(b)q(o)o(xes.)20 b(Still,)0 627 y(the)15 b(notation)g(clearly)h (indicates)h(whic)o(h)f(slot)f(is)h(whic)o(h.)91 691 y(By)f(the)g(w)o(a)o(y)l(,)f(are)h(y)o(ou)g(tired)h(of)e(ha)o(ving)i (to)e(write)h Fd(MATRIX)g Fh(and)g Fd(VECTOR)f Fh(v)o(ersions)i(of)e (ev)o(erything,)h(when)0 749 y(y)o(ou)i(really)h(only)g(care)g(ab)q (out)f(the)g(matrix)g(v)o(ersion?)28 b(Y)l(ou)18 b(can)f(in)o(v)o(en)o (t)h(t)o(w)o(o-lev)o(el)f(mapping)h(to)q(ols)g(that)e(will)0 807 y(allo)o(w)f(direct)h(de\014nition)h(of)e(the)g(matrix)g (functions.)0 884 y Fd(TO)24 b(MMAP)f(:FN)g(:MAT)358 b(;)23 b(matrix)h(map)24 942 y(OUTPUT)f(MAP)g([MAP)h(:FN)f(?])h(:MAT)0 1000 y(END)0 1116 y(TO)g(MMAP.2)f(:FN)g(:M1)h(:M2)24 1174 y(OUTPUT)f(MAP.2)g([MAP.2)g(:FN)h(?1)f(?2])h(:M1)f(:M2)0 1232 y(END)0 1349 y(TO)h(ADD)f(:M1)g(:M2)24 1407 y(OUTPUT)g(MMAP.2)g ([?1)g(+)h(?2])g(:M1)f(:M2)0 1465 y(END)0 1581 y(TO)h(SCALE)f(:NUM)g (:MAT)24 1639 y(OUTPUT)g(MMAP)g([:NUM)g(*)h(?])g(:MAT)0 1697 y(END)0 1775 y Fh(The)19 b(de\014nitions)i(of)d Fd(ADD)h Fh(and)g Fd(SCALE)f Fh(no)o(w)h(em)o(b)q(o)q(dy)g(the)g (mathematical)h(ideas)f(quite)h(directly)l(,)h(with)e(v)o(ery)0 1833 y(little)c(programming)e(language)h(noise.)20 b(Y)l(ou)14 b(ma)o(y)f(\014nd)i(the)f(de\014nitions)h(of)f Fd(MMAP)f Fh(and)h Fd(MMAP.2)f Fh(a)g(little)i(tric)o(ky)l(,)0 1891 y(but)i(the)f(structure)g(of)g(nested)h Fd(MAP)p Fh(s)f(is)h(exactly)g(analogous)f(to)g(the)g(nested)h Fd(FOR)p Fh(s)f(in)i(the)e(sequen)o(tial)i(v)o(ersion)0 1950 y(of)d(matrix)g(programming.)0 2068 y Fi(More)i(F)l(unctional)i (Programming)e(T)l(o)q(ols)91 2187 y Fh(I)h(w)o(ould)g(lik)o(e)h(to)e (de\014ne)i(an)f(exp)q(onen)o(tiation)h(function.)28 b(That)17 b(is,)i(I)f(w)o(an)o(t)f(to)g(tak)o(e)g(a)g(giv)o(en)h(base)g (to)f(a)0 2245 y(giv)o(en)d(p)q(o)o(w)o(er,)f(using)i(rep)q(eated)f(m)o (ultiplication.)21 b(\(The)14 b(p)q(o)o(w)o(er)f(m)o(ust,)g(of)g (course,)h(b)q(e)g(a)g(nonnegativ)o(e)f(in)o(teger.\))0 2303 y(This)21 b(is)h(an)f(example)g(of)g(comp)q(osition)g(of)g (functions,)h(in)g(whic)o(h)g(the)e(function)i Fd([?)i(*)f(:BASE])d Fh(is)i(in)o(v)o(ok)o(ed)0 2361 y Fd(:EXP)16 b Fh(times,)g(with)h(the)f (result)g(from)g(one)g(in)o(v)o(o)q(cation)h(\014lling)h(the)f(slot)f (for)f(the)i(next)f(in)o(v)o(o)q(cation.)23 b(\(The)16 b(\014rst)0 2419 y(in)o(v)o(o)q(cation)g(is)f(done)h(with)g(1)e(in)i (the)g(slot.\))0 2496 y Fd(TO)24 b(POWER)f(:BASE)g(:EXP)24 2554 y(OUTPUT)g(CASCADE)g(:EXP)g([?)h(*)f(:BASE])g(1)0 2612 y(END)952 2779 y Fh(12)p eop %%Page: 13 13 13 12 bop 0 45 a Fd(?)24 b(SHOW)f(POWER)g(2)h(5)0 104 y(32)91 186 y(CASCADE)18 b Fh(is)j(a)e(to)q(ol)g(for)g(rep)q(eated)h (comp)q(osition)h(of)e(a)g(function)i(with)e(itself.)34 b(It)20 b(tak)o(es)f(three)g(inputs.)0 244 y(First)13 b(is)g(a)g(n)o(um)o(b)q(er)g(sa)o(ying)g(ho)o(w)f(man)o(y)h(times)g(w)o (e)g(w)o(an)o(t)e(to)i(in)o(v)o(ok)o(e)g(the)g(function.)20 b(Second)13 b(comes)g(a)g(template)0 302 y(indicating)i(what)e(the)h (function)g(is.)20 b(Third)15 b(is)f(the)f(initial)j(v)m(alue)f(used)f (to)f(\014ll)i(the)e(slot)h(in)g(the)g(\014rst)f(in)o(v)o(o)q(cation.)0 361 y(As)f(another)g(example)g(of)g(its)g(use,)h(here)f(is)h(Newton's)e (metho)q(d)h(to)g(appro)o(ximate)f(the)h(square)g(ro)q(ot)f(of)h(a)g(n) o(um)o(b)q(er)0 419 y(b)o(y)j(rep)q(eated)h(comp)q(osition)g(of)f(a)g (function:)0 496 y Fd(TO)24 b(NSQRT)f(:X)24 554 y(OUTPUT)g(CASCADE)g (10)g([\(?)h(+)g(\(:X/?\)\)/2])e(1)0 612 y(END)0 695 y Fh(Newton's)13 b(appro)o(ximation)g(function)h(tak)o(es)e(the)h(a)o (v)o(erage)g(of)f(the)i(previous)g(guess)f(and)g(the)h(quotien)o(t)f (of)g Fc(x)g Fh(and)0 753 y(the)18 b(guess.)27 b(In)19 b(this)f(pro)q(cedure)h(w)o(e)e(start)g(with)h(an)g(initial)i(guess)d (of)h(1)f(and)h(w)o(e)g(apply)g(the)g(appro)o(ximation)0 811 y(function)f(10)e(times.)23 b(This)17 b(constan)o(t)e(n)o(um)o(b)q (er)h(of)g(in)o(v)o(o)q(cations)g(is)h(to)q(o)e(simple;)j(few)o(er)d (in)o(v)o(o)q(cations)i(w)o(ould)f(do)0 869 y(for)i(small)h(v)m(alues)g (of)f Fc(x)p Fh(,)h(while)g(more)f(are)g(needed)i(to)d(get)h(a)g(go)q (o)q(d)g(appro)o(ximation)h(for)e(large)i(v)m(alues.)30 b(\(F)l(or)0 927 y(example,)18 b(try)f Fd(NSQRT)f Fh(of)h(a)f (million.\))28 b(T)l(o)17 b(\014x)g(this)g(problem,)h Fd(CASCADE)e Fh(accepts)i(as)e(its)i(\014rst)e(input)i(either)g(a)0 985 y(n)o(um)o(b)q(er)d(or)f(a)g Fg(pr)n(e)n(dic)n(ate)h(template)p Fh(,)g(that)e(is,)i(an)g(expression)g(template)g(whose)f(v)m(alue)i(is) f Fd(TRUE)e Fh(or)h Fd(FALSE)p Fh(.)g(The)0 1043 y(rep)q(eated)i(comp)q (osition)g(con)o(tin)o(ues)g(un)o(til)g(the)f(v)m(alue)i(of)d(the)i (predicate)g(template)f(is)h Fd(TRUE)p Fh(.)0 1120 y Fd(TO)24 b(NSQRT)f(:X)24 1178 y(OUTPUT)g(CASCADE)g([LESSP)g(ABS)g(\(:X) h(-)f(?*?\))h(0.00000001])e([\(?)i(+)f(\(:X/?\)\)/2])g(1)0 1236 y(END)0 1353 y(TO)h(ABS)f(:X)24 1411 y(OUTPUT)g(IFELSE)g(:X<0)g ([-:X])g([:X])0 1469 y(END)91 1552 y Fh(It)15 b(is)h(sometimes)f(con)o (v)o(enien)o(t)h(for)e(the)h(function)h(b)q(eing)h(cascaded)e(to)g(kno) o(w)f(ho)o(w)h(man)o(y)g(times)g(it's)g(b)q(een)0 1610 y(in)o(v)o(ok)o(ed)g(so)g(far.)k(F)l(or)14 b(example,)h(the)g (factorial)g(function)h(is)f(lik)o(e)h(the)f(p)q(o)o(w)o(er)g(function) g(except)h(that)e(eac)o(h)h(new)0 1668 y(m)o(ultiplication)22 b(is)e(b)o(y)f(a)h(larger)f(n)o(um)o(b)q(er,)h(instead)h(of)e(alw)o(a)o (ys)f(b)o(y)i(the)f(same)h Fd(:BASE)p Fh(.)e(Therefore,)i Fd(CASCADE)0 1726 y Fh(templates)15 b(can)h(include)h(another)e(sp)q (ecial)i(sym)o(b)q(ol,)e Fd(#)p Fh(,)g(indicating)i(the)e(n)o(um)o(b)q (er)h(of)f(in)o(v)o(o)q(cations.)0 1803 y Fd(TO)24 b(FACTORIAL)e(:N)24 1861 y(OUTPUT)h(CASCADE)g(:N)g([?)h(*)g(#])f(1)0 1919 y(END)0 2002 y Fh(The)14 b(template)h(is)g(\014rst)e(in)o(v)o(ok)o(ed)i (with)f(1)g(in)h(the)g(question)f(mark)g(slot)g(\(b)q(ecause)h(the)f (third)h(input)g(to)f Fd(CASCADE)0 2060 y Fh(is)h(1\))f(and)h(also)g(1) f(in)i(the)e(n)o(um)o(b)q(er)h(sign)g(slot)g(\(b)q(ecause)g(this)g(is)h (the)e(\014rst)h(in)o(v)o(o)q(cation\).)k(The)c(result)g(is)h(1.)j (Next)0 2118 y(time,)c Fd(?)20 b Fh(is)c(1)f(b)q(ecause)h(that's)e(the) h(result)h(of)f(the)g(\014rst)g(in)o(v)o(o)q(cation,)g(but)g Fd(#)g Fh(is)h(2.)k(The)15 b(third)h(time,)f Fd(?)20 b Fh(is)c(2)f(and)0 2176 y Fd(#)g Fh(is)h(3.)91 2244 y(The)22 b(function)g(b)q(eing)h(cascaded)e(is)h(not)g(limited)h(to)e (a)g(scalar)g(domain)h(or)f(range.)38 b(W)l(e)22 b(can)f(use)h(list)0 2302 y(pro)q(cessing)16 b(op)q(erations)f(to)g(generate)g(the)g(v)o (ector)g(of)f(all)j(the)e(in)o(tegers)g(from)g(1)f(to)h Fc(n)p Fh(:)0 2380 y Fd(TO)24 b(FROM1TO)e(:N)24 2438 y(OUTPUT)h(CASCADE)g(:N)g([LPUT)h(#)f(?])h([])0 2496 y(END)0 2612 y(?)g(SHOW)f(FROM1TO)g(5)0 2670 y([1)h(2)f(3)h(4)g(5])952 2779 y Fh(13)p eop %%Page: 14 14 14 13 bop 0 45 a Fh(Here)18 b(the)g(initial)i(v)m(alue)g(is)e(an)g (empt)o(y)g(v)o(ector,)f(and)h(eac)o(h)g(in)o(v)o(o)q(cation)h(of)f (the)g(template)g(app)q(ends)h(the)f(next)0 104 y(in)o(teger)c(in)h (sequence.)21 b(\()p Fd(LPUT)13 b Fh(means)g(\\last)h(put";)g(it's)g (lik)o(e)h Fd(FPUT)e Fh(except)i(that)e(the)h(new)g(elemen)o(t)h(is)f (adjoined)0 162 y(on)h(the)g(righ)o(t)g(instead)h(of)f(on)g(the)g (left.\))91 224 y(Just)g(as)g(there)g(is)h(a)f Fd(MAP.2)f Fh(for)h(t)o(w)o(o-input)g(functions,)g(w)o(e)g(sometimes)h(need)g Fd(CASCADE.2)e Fh(for)g(t)o(w)o(o-input)0 282 y(functions.)25 b(The)17 b(parallel)h(is)f(not)f(exact,)g(ho)o(w)o(ev)o(er.)24 b(In)17 b(this)g(con)o(text)f(w)o(e)g(need)i(not)e(only)h(t)o(w)o(o)e (initial)k(inputs)0 340 y(but)f(also)f(t)o(w)o(o)f(functions,)j(one)f (to)f(sp)q(ecify)i(the)e(next)h(v)m(alue)h(of)e Fd(?1)g Fh(and)h(one)g(to)f(giv)o(e)g(the)h(next)g(v)m(alue)g(of)g Fd(?2)p Fh(.)0 398 y Fd(CASCADE.2)c Fh(therefore)h(tak)o(es)f(\014v)o (e)i(inputs:)0 475 y Fd(CASCADE.2)23 b(end.test)f(template.1)h (initial.1)g(template.2)f(initial.2)0 551 y Fh(F)l(or)15 b(example,)g(here)h(is)g(ho)o(w)e(to)h(compute)g(the)g Fc(n)p Fh(th)h(Fib)q(onacci)g(n)o(um)o(b)q(er:)0 628 y Fd(TO)24 b(FIB)f(:N)24 686 y(OUTPUT)g(CASCADE.2)g(:N-1)g([?1)g(+)h (?2])f(1)h([?1])g(0)0 744 y(END)0 820 y Fh(The)15 b(\014nal)h(output)f (from)g Fd(CASCADE.2)f Fh(is)i(the)f(\014nal)h(v)m(alue)g(of)f Fd(?1)p Fh(.)91 882 y(Because)i(I'm)f(presen)o(ting)h(so)f(man)o(y)g (examples)h(so)f(brie\015y)l(,)h(I'm)f(afraid)h(the)f(o)o(v)o(erall)g (p)q(oin)o(t)h(is)g(in)g(danger)0 940 y(of)e(b)q(eing)h(lost,)f(so)g (let)h(me)f(tak)o(e)g(a)g(momen)o(t)f(to)h(review)h(where)f(w)o(e)g (are.)20 b(I)15 b(started)g(b)o(y)g(presen)o(ting)h(the)f(idea)h(of)0 998 y(functional)g(programming,)f(in)h(whic)o(h)g(the)f(fo)q(cus)h(is)f (on)g(the)h(input-output)g(b)q(eha)o(vior)g(of)e(a)h(pro)q(cedure)i (rather)0 1057 y(than)i(on)g(the)g(exact)f(sequence)i(of)f(ev)o(en)o (ts)f(through)h(whic)o(h)h(the)f(computer)g(pro)q(duces)g(the)g (desired)i(output.)0 1115 y(I)i(suggested)g(that)f(functional)h (programming)f(is)i(m)o(uc)o(h)e(b)q(etter)h(suited)h(to)e(mathematics) g(teac)o(hing)h(than)0 1173 y(traditional,)c(sequen)o(tial)g (programming.)27 b(If)18 b(this)g(is)g(true,)g(teac)o(hers)g(should)g (prefer)g(a)g(functional)h(language)0 1231 y(lik)o(e)13 b(Logo)e(rather)g(than)g(a)g(sequen)o(tial)i(one)f(lik)o(e)g(BASIC)h (or)e(P)o(ascal.)18 b(One)13 b(stum)o(bling)f(blo)q(c)o(k)g(has)g(b)q (een)g(the)g(need)0 1289 y(to)h(teac)o(h)h(recursion)h(in)g(order)f(to) g(program)f(ev)o(en)h(the)g(simplest)i(mathematical)e(ideas,)h(but)f (this)g(obstacle)h(can)0 1347 y(b)q(e)g(a)o(v)o(oided)g(b)o(y)g(pro)o (viding)h(to)q(ols)e(that)g(are)h(the)g(functional)h(analog)e(to)g(the) h(lo)q(oping)h(construct)e(in)i(sequen)o(tial)0 1405 y(programming.)91 1467 y(So)c(far)g(I)h(ha)o(v)o(e)f(in)o(tro)q(duced)h (t)o(w)o(o)e(suc)o(h)i(to)q(ols,)g Fd(MAP)f Fh(and)g Fd(CASCADE)p Fh(,)f(in)j(one-input)f(and)g(t)o(w)o(o-input)f(v)o (ersions.)0 1525 y(With)g(this)h(small)f(to)q(olkit)h(I)f(ha)o(v)o(e)g (b)q(een)h(able)f(to)g(write)g(pro)q(cedures)h(that)e(are)h(not)f (self-referen)o(tial)j(for)d(a)h(v)m(ariet)o(y)0 1584 y(of)18 b(mathematical)h(functions.)32 b(In)20 b(m)o(y)e(exp)q (erience,)k(studen)o(ts)c(quic)o(kly)j(understand)e Fd(MAP)g Fh(with)g(hardly)g(an)o(y)0 1642 y(explanation,)e(and)f(can)h(use)f(it) h(correctly)f(themselv)o(es.)24 b Fd(CASCADE)15 b Fh(is)i(a)f(little)h (harder,)f(p)q(erhaps)h(just)f(b)q(ecause)0 1700 y(it)h(has)f(more)g (inputs)h(and)g(the)g(pro)q(cedures)g(are)f(therefore)g(harder)h(to)f (read.)23 b(But)17 b(the)f(e\013ort)g(to)f(understand)0 1758 y(the)f(metaphor)f(b)q(ehind)i Fd(CASCADE)e Fh(\(comp)q(osing)g(a) g(function)i(with)e(itself)t(\))h(pa)o(ys)f(o\013)g(in)h(more)f (expressiv)o(e)h(p)q(o)o(w)o(er)0 1816 y(than)j(studen)o(ts)g(of)g (traditional)g(languages)g(get)g(from)f(similar)j(e\013ort)d(put)h(in)o (to)g Fd(FOR)p Fh(,)f Fd(WHILE)p Fh(,)g Fd(UNTIL)p Fh(,)g(and)h(so)0 1874 y(on.)j(I)15 b(no)o(w)g(w)o(an)o(t)f(to)h(in)o(tro)q(duce)h(t)o(w) o(o)e(more)h(functional)h(programming)e(to)q(ols.)91 1936 y(W)l(e)22 b(w)o(an)o(t)f(to)h(tak)o(e)f(the)i(dot)f(pro)q(duct)g (of)g(t)o(w)o(o)f(v)o(ectors.)40 b(T)l(o)22 b(do)g(this,)i(w)o(e)e(m)o (ust)g(m)o(ultiply)i(pairs)e(of)0 1994 y(corresp)q(onding)15 b(elemen)o(ts,)f(and)h(then)f(add)g(up)h(all)f(the)h(pro)q(ducts.)k (The)c(\014rst)e(part)h(of)f(this)i(is)f(clearly)h(a)f(job)g(for)0 2052 y Fd(MAP.2)p Fh(,)g(but)h(w)o(e)g(need)h(a)f(to)q(ol)g(for)g(the)g (second)h(part.)0 2129 y Fd(?)24 b(SHOW)f(REDUCE)g("SUM)g([2)h(3)g(4])0 2187 y(9)0 2245 y(?)g(SHOW)f(REDUCE)g("PRODUCT)g([2)g(3)h(4])0 2303 y(24)0 2419 y(TO)g(DOTPROD)e(:V1)i(:V2)24 2478 y(OUTPUT)f(REDUCE)g ("SUM)g(\(MAP.2)g("PRODUCT)g(:V1)h(:V2\))0 2536 y(END)0 2612 y Fh(Because)12 b(the)f(function)h(I)g(w)o(an)o(t)e(to)h(map)g(o)o (v)o(er)g(the)g(t)o(w)o(o)f(v)o(ectors)g(happ)q(ens)j(to)d(b)q(e)i (included)i(as)d(a)g(Logo)g(primitiv)o(e,)0 2670 y(I'v)o(e)i(just)f (giv)o(en)h Fd(MAP.2)f Fh(its)h(name,)g(as)f(I)h(did)h(in)f(the)g (earliest)g(examples,)h(instead)f(of)f(a)h(template)f(with)h(question) 952 2779 y(14)p eop %%Page: 15 15 15 14 bop 0 45 a Fh(marks.)19 b(W)l(e'll)14 b(write)f(these)h(to)q(ols) f(so)g(that)f(either)i(form)f(is)h(allo)o(w)o(ed.)19 b Fd(REDUCE)p Fh(,)12 b(the)i(new)f(to)q(ol)h(in)g(this)f(example,)0 104 y(tak)o(es)i(a)h(t)o(w)o(o-input)g(asso)q(ciativ)o(e)g(function)h (and)f(applies)i(it)e(to)f(all)i(the)f(elemen)o(ts)h(of)e(the)h (indicated)i(list.)23 b(\(W)l(e)0 162 y(insist)14 b(that)e(the)h (function)h(b)q(e)f(asso)q(ciativ)o(e)h(to)e(a)o(v)o(oid)g(questions)i (ab)q(out)f(the)g(precise)h(grouping)f(of)f(the)h(elemen)o(ts)0 220 y(of)i(the)g(list.\))91 298 y(It)c(ma)o(y)f(b)q(e)i(time)f(for)g(a) g(reminder)h(that)e(functional)i(programming)f(to)q(ols)f(can)i(b)q(e)f (applied)i(to)e(non-n)o(umeric)0 356 y(computation)k(as)g(w)o(ell:)0 434 y Fd(TO)24 b(ACRONYM)e(:NAME)24 492 y(OUTPUT)h(REDUCE)g("WORD)g (MAP)h("FIRST)f(:NAME)0 550 y(END)0 666 y(?)h(SHOW)f(ACRONYM)g ([AMERICAN)g(CIVIL)g(LIBERTIES)f(UNION])0 724 y(ACLU)0 840 y(TO)i(PIGLATIN)e(:WORD)24 898 y(OUTPUT)h(WORD)g(\(CASCADE)g ([MEMBERP)g(FIRST)g(?)h("AEIOU])525 956 y([WORD)f(BUTFIRST)g(?)h(FIRST) f(?])525 1015 y(:WORD\))310 1073 y("AY)0 1131 y(END)0 1247 y(?)h(SHOW)f(PIGLATIN)g("SPAGHETTI)0 1305 y(AGHETTISPAY)91 1398 y Fh(The)14 b(last)f(to)q(ol)h(is)g(used)g(to)f(select)h(a)f (subset)h(of)f(the)h(mem)o(b)q(ers)f(of)h(a)f(list,)h(based)g(on)f(a)h (predicate)g(template:)0 1476 y Fd(?)24 b(SHOW)f(FILTER)g([EQUALP)g (\(REMAINDER)f(?)i(2\))g(0])f([1)h(2)g(3)f(4)h(5])0 1534 y([2)g(4])0 1592 y(?)g(SHOW)f(FILTER)g([EQUALP)g(\(SQRT)g(?\))h(\(INT)f (SQRT)g(?\)])h([1)f(2)h(3)g(4)g(5])0 1650 y([1)g(4])0 1744 y Fh(Supp)q(ose)17 b(w)o(e)e(w)o(an)o(t)g(to)g(kno)o(w)g(if)i(a)e (n)o(um)o(b)q(er)h Fc(n)g Fh(is)g(p)q(erfect.)22 b(W)l(e)16 b(need)h(to)e(\014nd)h(all)h(the)f(factors)f(of)g Fc(n)p Fh(,)h(then)g(add)0 1802 y(them)f(up:)0 1880 y Fd(TO)24 b(PERFECT?)e(:N)24 1938 y(OUTPUT)h(EQUALP)g(:N)358 1996 y(REDUCE)g("SUM)525 2054 y(FILTER)g([EQUALP)g(\(REMAINDER)f(:N)i(?\))g (0])692 2112 y(FROM1TO)f(:N-1)0 2170 y(END)0 2286 y(?)h(SHOW)f (PERFECT?)g(6)0 2344 y(TRUE)0 2403 y(?)h(SHOW)f(PERFECT?)g(7)0 2461 y(FALSE)0 2554 y Fh(In)18 b(this)g(pro)q(cedure,)g Fd(FROM1TO)f Fh(giv)o(es)g(us)h(a)f(list)h(of)f(all)i(the)e(n)o(um)o(b) q(ers)h(that)e(migh)o(t)i(b)q(e)g(factors)e(of)h Fc(n)p Fh(.)27 b Fd(FILTER)0 2612 y Fh(selects)12 b(the)g(ones)f(that)g (actually)h(are)g(factors,)e(b)o(y)i(c)o(hec)o(king)g(the)g(remainder)g (of)f(dividing)j Fc(n)d Fh(b)o(y)h(eac)o(h)f(candidate.)0 2670 y Fd(REDUCE)j Fh(adds)i(all)g(the)f(factors,)f(and)h Fd(EQUALP)g Fh(c)o(hec)o(ks)g(whether)g(the)h(sum)f(is)g(equal)h(to)f Fc(n)p Fh(.)952 2779 y(15)p eop %%Page: 16 16 16 15 bop 91 45 a Fh(Y)l(ou)15 b(ma)o(y)g(b)q(e)h(w)o(ondering)g(if)f (there)h(will)h(b)q(e)f Fd(REDUCE.2)e Fh(and)h Fd(FILTER.2)f Fh(pro)q(cedures.)21 b(It)16 b(turns)f(out)g(that)0 104 y(these)e(w)o(ould)h(not)e(b)q(e)i(meaningful.)20 b(F)l(unctions)14 b(can)f(ha)o(v)o(e)g(more)f(than)h(one)g(input,)h(but)f(they)g(are)g (only)h(allo)o(w)o(ed)0 162 y(one)19 b(output.)31 b(If)19 b(w)o(e)f(tried)i(to)e(select)h(elemen)o(ts)h(from)e(t)o(w)o(o)f(lists) j(in)g(parallel,)h(w)o(e)d(w)o(ould)h(end)h(up)f(with)g(t)o(w)o(o)0 220 y(sublists.)i(Whic)o(h)16 b(w)o(ould)g(w)o(e)e(output?)0 347 y Fi(Some)j(Problems)g(Really)h(Are)f(Recursiv)o(e)91 475 y Fh(Supp)q(ose)23 b(w)o(e)f(w)o(an)o(t)f(to)g(\014nd)i(the)f (determinan)o(t)g(of)f(a)h(square)g(matrix.)40 b(The)22 b(w)o(ell-kno)o(wn)h(algorithm)0 533 y(requires)c(us)g(to)f(select)h(a) f(single)i(ro)o(w)d(or)h(column)i(of)e(the)g(matrix,)h(then)g(for)e (eac)o(h)i(elemen)o(t)g(of)f(that)g(ro)o(w)f(or)0 591 y(column)d(w)o(e)f(m)o(ust)f(compute)h Fg(the)i(determinant)f(of)23 b Fh(a)13 b(submatrix)g(formed)g(b)o(y)g(remo)o(ving)g(the)g(ro)o(w)f (and)h(column)0 649 y(con)o(taining)19 b(that)f(elemen)o(t.)29 b(\(Then)19 b(w)o(e)f(m)o(ultiply)h(b)o(y)g(plus)g(or)f(min)o(us)g(the) h(elemen)o(t,)g(and)g(then)f(w)o(e)g(add)g(up)0 707 y(all)f(the)f (results,)g(but)g(those)f(are)h(the)g(easy)f(parts.\))21 b(The)16 b(w)o(ords)f(in)i(italics)g(are)e(a)h(self-referen)o(tial)h (part)e(of)h(the)0 765 y(de\014nition)g(of)d(the)h(determinan)o(t.)19 b(The)14 b(use)h(of)e(recursion)h(to)g(solv)o(e)f(this)i(problem)f(is)g (not)g(an)g(acciden)o(tal)h(result)0 823 y(of)g(missing)h(features)f (in)h(the)f(programming)g(language.)20 b(It's)14 b(a)h(naturally)h (recursiv)o(e)g(problem.)91 896 y(It)e(will)h(turn)e(out)g(to)g(b)q(e)i (easiest)e(if)h(w)o(e)g(c)o(ho)q(ose)f(the)h(leftmost)f(column)h(of)g (the)f(matrix)g(as)h(the)f(one)h(to)f(treat)0 954 y(sp)q(ecially)l(.)23 b(If)16 b(w)o(e)f(c)o(hose)h(the)f(top)h(ro)o(w,)e(whic)o(h)i(w)o(ould) g(b)q(e)g(more)f(traditional,)h(then)g(for)f(eac)o(h)g(elemen)o(t)i(of) e(that)0 1012 y(ro)o(w)f(w)o(e)h(m)o(ust)g(extract)f(a)h(submatrix)h (in)g(whic)o(h)g(its)f(column)i(is)e(remo)o(v)o(ed.)20 b(If)15 b(w)o(e)g(start)f(with)i(a)f(column,)h(then)0 1070 y(for)f(eac)o(h)i(of)e(its)h(elemen)o(ts)h(the)f(submatrix)g(is)h (found)f(b)o(y)g(remo)o(ving)g(a)g(ro)o(w.)21 b(The)16 b(latter)g(op)q(eration)g(is)h(easier,)0 1128 y(since)f(w)o(e)f(store)g (matrices)g(as)g(lists)h(of)e(ro)o(ws.)19 b(The)d(left)f(column)h(of)f (a)g(matrix)g(is)h(found)f(with)h(the)f(expression)0 1206 y Fd(MAP)23 b("FIRST)g(:MATRIX)0 1294 y Fh(whic)o(h)16 b(selects)g(the)f(\014rst)g(elemen)o(t)h(of)f(eac)o(h)g(ro)o(w.)k (Similarly)l(,)e(the)e(expression)0 1371 y Fd(MAP)23 b("BUTFIRST)g(:MATRIX)0 1459 y Fh(returns)15 b(a)g(\(non-square\))f (matrix)h(with)g(the)h(\014rst)e(column)i(eliminated.)22 b(This)16 b(latter)f(matrix)f(will)j(b)q(e)f(used)f(as)0 1517 y(the)g(basis)h(from)e(whic)o(h)i(ro)o(ws)f(will)h(b)q(e)g (eliminated)i(to)c(form)h(eac)o(h)g(submatrix.)0 1595 y Fd(TO)24 b(DET)f(:MATRIX)24 1653 y(IF)g(EMPTYP)g(BUTFIRST)g(:MATRIX)g ([OUTPUT)g(FIRST)g(FIRST)g(:MATRIX])71 b(;)24 b(base)f(case,)g(1x1)24 1711 y(LOCAL)g("RIGHTPART)24 1769 y(MAKE)g("RIGHTPART)g(MAP)g ("BUTFIRST)g(:MATRIX)500 b(;)24 b(all)f(but)h(1st)f(col)24 1827 y(OUTPUT)g(REDUCE)g("SUM)358 1885 y(MAP)g([\(PRODUCT)g(?)h(\(SIGN) f(#\))h(\(DET)f(ALLBUT)g(#)h(:RIGHTPART\)\)])453 1943 y(MAP)g("FIRST)f(:MATRIX)0 2001 y(END)0 2117 y(TO)h(ALLBUT)f(:N)g(:MAT) 1002 b(;)24 b(all)f(but)h(nth)f(row)24 2176 y(OUTPUT)g(FILTER)g([NOT)g (EQUALP)g(#)h(:N])f(:MAT)0 2234 y(END)0 2350 y(TO)h(SIGN)f(:N)24 2408 y(OUTPUT)g(IFELSE)g(\(EQUALP)g(REMAINDER)f(:N)i(2)g(0\))f([-1])h ([1])0 2466 y(END)0 2554 y Fh(Ev)o(en)17 b(though)g(recursion)g(is)h (necessary)f(in)g(this)h(problem,)f(I'v)o(e)g(con)o(tin)o(ued)h(to)e (use)h(the)g(non-recursiv)o(e)h(func-)0 2612 y(tional)h(to)q(ols)f (wherev)o(er)g(p)q(ossible.)30 b(T)l(o)18 b(mak)o(e)f(this)i(w)o(ork,)e (I)h(had)h(to)e(extend)i(the)f Fd(#)g Fh(notation)f(in)i(templates,)0 2670 y(whic)o(h)d(I)g(originally)h(in)o(tended)f(only)g(for)e Fd(CASCADE)p Fh(,)g(to)h(w)o(ork)f(in)i Fd(MAP)f Fh(and)g Fd(FILTER)g Fh(also.)952 2779 y(16)p eop %%Page: 17 17 17 16 bop 91 45 a Fh(Since)20 b Fd(DET)d Fh(is)i(de\014ned)h(recursiv)o (ely)l(,)g(it)e(m)o(ust)g(ha)o(v)o(e)g(a)g(base)g(case.)29 b(In)19 b(this)f(problem,)i(the)e(base)g(case)g(is)0 104 y(that)13 b(the)i(determinan)o(t)f(of)g(a)g(matrix)g(with)g(one)g (ro)o(w)g(and)g(one)g(column)h(is)g(the)f(single)i(n)o(um)o(b)q(er)e (in)h(the)g(matrix.)0 162 y(W)l(e)20 b(sa)o(y)e Fd(FIRST)24 b(FIRST)18 b Fh(b)q(ecause)j(the)e(n)o(um)o(b)q(er)h(is)g(the)g (\014rst)f(elemen)o(t)h(of)f(the)h(\014rst)f(ro)o(w.)31 b(F)l(or)19 b(other)g(cases,)0 220 y(the)d(program)f(is)i(more)e (complicated.)24 b(First)16 b(w)o(e)g(create)f(a)h(lo)q(cal)h(v)m (ariable)h Fd(RIGHTPART)d Fh(and)h(assign)g(to)g(it)g(the)0 278 y(non-square)e(matrix)f(with)h(the)g(\014rst)f(column)h(of)f(the)h (original)h(matrix)e(remo)o(v)o(ed.)19 b(The)14 b(reason)f(for)g(this)h (step)f(is)0 336 y(to)f(a)o(v)o(oid)h(rep)q(etitiv)o(e)g(computation)g (of)f(the)h(same)g(matrix)f(for)g(ev)o(ery)h(ro)o(w,)f(whic)o(h)h(w)o (ould)g(result)g(if)h(w)o(e)e(just)g(said)24 413 y Fd(OUTPUT)23 b(REDUCE)g("SUM)358 471 y(MAP)g([\(PRODUCT)g(?)h(\(SIGN)f(#\))h(\(DET)f (ALLBUT)g(#)h(MAP)f("BUTFIRST)g(:MATRIX\)\)])453 529 y(MAP)h("FIRST)f(:MATRIX)0 612 y Fh(without)14 b(using)i(the)e(extra)g (v)m(ariable.)21 b(No)o(w)14 b(w)o(e)g(can)g(pic)o(k)i(apart)d(the)i (long)f Fd(OUTPUT)g Fh(instruction)h(to)f(see)h(ho)o(w)f(it)0 670 y(em)o(b)q(o)q(dies)j(the)e(de\014nition.)22 b(W)l(e)15 b(kno)o(w)g(from)f(the)i(use)f(of)g Fd(REDUCE)g Fh(that)f(w)o(e)h(are)g (going)h(to)e(compute)i(a)f(list)h(full)0 728 y(of)f(n)o(um)o(b)q(ers)g (and)h(then)f(add)h(up)f(the)g(n)o(um)o(b)q(ers.)21 b(What)14 b(is)i(the)f(list?)22 b(W)l(ell,)16 b(it's)f(computed)g(b)o(y)0 805 y Fd(MAP)23 b([...])h(MAP)f("FIRST)g(:MATRIX)0 888 y Fh(whic)o(h)18 b(means)e(\\compute)h(some)f(function)i(of)e(eac)o(h)h (elemen)o(t)h(of)e(the)h(\014rst)f(column)i(of)e(the)h(matrix.")24 b(So)17 b(far,)0 946 y(so)h(go)q(o)q(d.)30 b(What)18 b(function)i(do)e(w)o(e)g(compute)h(for)f(eac)o(h)h(elemen)o(t)g(of)f (the)h(\014rst)f(column?)32 b(It's)18 b(a)g(pro)q(duct)h(of)0 1004 y(three)14 b(factors:)e(the)i(elemen)o(t)g(itself,)h(either)g(p)q (ositiv)o(e)f(or)f(negativ)o(e)h(1)g(dep)q(ending)i(on)d(whic)o(h)i (elemen)o(t)g(it)f(is,)g(and)0 1062 y(the)h(determinan)o(t)g(of)f(a)g (submatrix.)20 b(That)14 b(submatrix)h(is)g(computed)g(b)o(y)g (selecting)h(all)f(but)g(a)g(particular)g(ro)o(w)0 1120 y(from)f(the)i(matrix)f Fd(:RIGHTPART)p Fh(.)91 1189 y(This)k(is)f(a)g(complicated)i(problem,)f(and)f(the)g(complexit)o(y)h (of)f(the)g(pro)q(cedure)h(re\015ects)g(that.)28 b(Still,)20 b(the)0 1247 y(use)d(of)f(functional)i(programming)d(has)i(allo)o(w)o (ed)g(us)f(to)g(solv)o(e)h(the)f(problem)h(without)g(in)o(tro)q(ducing) h(auxiliary)0 1305 y(index)e(v)m(ariables.)22 b(The)15 b(pro)q(cedure)h(exactly)g(re\015ects)f(the)g(structure)g(of)g(the)g (de\014nition)i(of)e(determinan)o(t.)91 1373 y(Since)21 b(w)o(e)f(can't)f(a)o(v)o(oid)g(recursion)i(in)f(the)g(de\014nition)i (of)d Fd(DET)p Fh(,)g(it)h(migh)o(t)g(b)q(e)g(w)o(orth)o(while)g(to)f (compare)0 1431 y(this)e(v)o(ersion)g(with)g(the)g(w)o(a)o(y)e(it)i(w)o (ould)g(traditionally)h(b)q(e)g(written)e(in)i(Logo,)e(relying)i(ev)o (en)f(more)f(hea)o(vily)i(on)0 1489 y(recursion:)0 1566 y Fd(TO)24 b(DET)f(:MATRIX)24 1624 y(IF)g(EMPTYP)g(BUTFIRST)g(:MATRIX)g ([OUTPUT)g(FIRST)g(FIRST)g(:MATRIX])24 1682 y(OUTPUT)g(DET1)g(\(FIRSTS) g(:MATRIX\))g(\(BUTFIRSTS)f(:MATRIX\))h(1)h(1)0 1741 y(END)0 1857 y(TO)g(DET1)f(:COL)g(:REST)g(:N)h(:SIGN)24 1915 y(IF)f(EMPTYP)g(:COL)h([OUTPUT)f(0])24 1973 y(OUTPUT)g(SUM)g (\(PRODUCT)g(\(FIRST)g(:COL\))g(:SIGN)h(\(DET)f(ALLBUT)g(:N)g (:REST\)\))286 2031 y(\(DET1)h(\(BUTFIRST)e(:COL\))h(:REST)h(:N+1)f (-:SIGN\))0 2089 y(END)0 2205 y(TO)h(FIRSTS)f(:LIST)24 2263 y(IF)g(EMPTYP)g(:LIST)h([OUTPUT)f([]])24 2321 y(OUTPUT)g(FPUT)g (\(FIRST)g(FIRST)g(:LIST\))g(\(FIRSTS)g(BUTFIRST)g(:LIST\))0 2380 y(END)0 2496 y(TO)h(BUTFIRSTS)e(:LIST)24 2554 y(IF)h(EMPTYP)g (:LIST)h([OUTPUT)f([]])24 2612 y(OUTPUT)g(FPUT)g(\(BUTFIRST)g(FIRST)g (:LIST\))g(\(BUTFIRSTS)g(BUTFIRST)f(:LIST\))0 2670 y(END)952 2779 y Fh(17)p eop %%Page: 18 18 18 17 bop 0 104 a Fd(TO)24 b(ALLBUT)f(:N)g(:LIST)24 162 y(IF)g(:N=1)h([OUTPUT)f(BUTFIRST)f(:LIST])24 220 y(OUTPUT)h(FPUT)g (\(FIRST)g(:LIST\))g(\(ALLBUT)g(:N-1)h(BUTFIRST)e(:LIST\))0 278 y(END)0 352 y Fh(T)l(o)c(someone)h(familiar)h(with)f(recursion,)h (the)f(pro)q(cedures)g Fd(DET)g Fh(and)f Fd(DET1)h Fh(in)g(this)g(v)o (ersion)g(ma)o(y)f(seem)h(less)0 410 y(in)o(timidating)f(than)f(the)g (earlier)h(v)o(ersion.)24 b(It)17 b(w)o(ould)g(b)q(e)h(p)q(ossible)g (to)e(compromise,)h(using)h Fd(MAP)e Fh(and)h Fd(FILTER)0 468 y Fh(to)d(de\014ne)i Fd(FIRSTS)p Fh(,)e Fd(BUTFIRSTS)p Fh(,)g(and)h Fd(ALLBUT)f Fh(as)g(in)i(the)f(\014rst)g(v)o(ersion,)g (but)g(using)h Fd(DET)e Fh(and)h Fd(DET1)g Fh(from)f(the)0 526 y(second)i(v)o(ersion.)91 587 y(On)22 b(the)g(other)f(hand,)j(to)d (a)g(reader)h(who)f(is)h(not)g(in)o(timidated)h(b)o(y)f(the)f(\014rst)h (v)o(ersion,)h(it)f(mak)o(es)f(the)0 645 y(structure)16 b(of)h Fd(DET)f Fh(more)g(plainly)i(apparen)o(t.)24 b(In)17 b(the)g(second)g(v)o(ersion,)g(the)g(fact)f(that)g(the)g(determinan)o (t)h(is)g(a)0 703 y(sum)g(of)g(pro)q(ducts)h(is)g(buried)h(inside)g Fd(DET1)p Fh(,)e(and)g(y)o(ou)g(ha)o(v)o(e)g(to)g(notice)h(that)f(one)g (of)g(the)g(inputs)i(to)d Fd(SUM)h Fh(is)h(a)0 761 y(recursiv)o(e)e (call)g(in)g(order)f(to)g(see)g(that)g(sev)o(eral)g(pro)q(ducts)h(will) g(b)q(e)g(added.)21 b(The)15 b(\014rst)g(v)o(ersion)h(sa)o(ys)0 837 y Fd(OUTPUT)23 b(REDUCE)g("SUM)g(MAP)h([\(PRODUCT)e(...)0 912 y Fh(righ)o(t)15 b(up)h(fron)o(t.)91 972 y(Computing)i(the)g (determinan)o(t)g(is)g(a)f(hard)h(problem,)h(and)f(the)f(program)g (will)i(b)q(e)g(complex)f(no)g(matter)0 1030 y(ho)o(w)13 b(it's)h(written.)20 b(Here)14 b(is)h(an)e(easier)i(problem)g(that)e (is)h(still)i(most)d(con)o(v)o(enien)o(t)h(in)h(recursiv)o(e)g(form:)e (compute)0 1088 y(the)i(transp)q(ose)g(of)f(a)h(matrix.)k(That)c(is,)g (in)o(terc)o(hange)g(the)g(ro)o(ws)f(and)h(the)g(columns.)21 b(The)15 b(tric)o(k)g(is)g(to)f(see)i(that)0 1146 y(the)h(\014rst)g(ro) o(w)g(of)f(the)i(output)f(will)i(b)q(e)f(the)f(\014rst)g(column)h(of)f (the)g(input,)h(while)h(the)f(remaining)g(ro)o(ws)e(of)h(the)0 1204 y(output)e(will)i(b)q(e)f(the)f Fg(tr)n(ansp)n(ose)g(of)25 b Fh(the)15 b(remaining)i(columns.)0 1281 y Fd(TO)24 b(TRANSPOSE)e(:MAT)24 1339 y(IF)h(EMPTYP)g(FIRST)h(:MAT)f([OUTPUT)g ([]])24 1397 y(OUTPUT)g(FPUT)g(\(MAP)h("FIRST)f(:MAT\))g(\(TRANSPOSE)f (MAP)i("BUTFIRST)e(:MAT\))0 1455 y(END)0 1571 y(?)i(SHOW)f(TRANSPOSE)g ([[1)g(2)h(3])f([4)h(5)g(6]])0 1629 y([[1)f(4])h([2)g(5])f([3)h(6]])91 1704 y Fh(As)17 b(a)h(third)g(example)g(in)g(whic)o(h)h(recursion)f(is) g(helpful,)i(let's)d(return)h(to)f(the)g(question)h(of)f Fd(MATRIX.ADD)0 1762 y Fh(and)h Fd(VECTOR.ADD)p Fh(.)d(My)j(\014rst)f (implemen)o(tation)i(de\014nes)f(one)g(in)g(terms)f(of)g(the)h(other.) 26 b(Later,)18 b(b)o(y)f(in)o(v)o(en)o(ting)0 1820 y(a)g(sp)q(ecial)h (to)q(ol)f(for)g(t)o(w)o(o-dimensional)g(mapping,)h(I)f(w)o(as)f(able)i (to)e(de\014ne)i(the)g(matrix)e(v)o(ersion)h(directly)l(.)27 b(But)0 1878 y(no)o(w)16 b(supp)q(ose)i(that)e(I)i(w)o(an)o(t)e(to)g(b) q(e)i(able)f(to)g(add)g(v)o(ectors,)f(matrices,)h(and)g(ev)o(en)h(m)o (ulti-dimensional)i(arra)o(ys.)0 1936 y(I)e(don't)f(w)o(an)o(t)f(to)h (ha)o(v)o(e)h(to)e(de\014ne)j(a)e(separate)g Fd(ADD)h Fh(pro)q(cedure)g(for)f(ev)o(ery)g(p)q(ossible)j(dimension.)28 b(Instead,)19 b(I)0 1994 y(w)o(an)o(t)14 b(one)h Fd(ADD)g Fh(pro)q(cedure)h(that)f(will)i(w)o(ork)d(on)h(scalars,)g(v)o(ectors,)f (matrices,)h(or)f(an)o(y)h(other)g(arra)o(y)l(.)0 2071 y Fd(TO)24 b(ADD)f(:A)h(:B)24 2129 y(IF)f(NUMBERP)g(:A)h([OUTPUT)f(:A)g (+)h(:B])24 2187 y(OUTPUT)f(MAP.2)g("ADD)g(:A)h(:B)0 2245 y(END)0 2319 y Fh(This)15 b(pro)q(cedure)g(extends)g(the)f (pattern)g(of)g(v)o(ector)f(and)i(matrix)f(addition)h(to)f(an)o(y)g(n)o (um)o(b)q(er)g(of)g(dimensions)i(b)o(y)0 2377 y(mapping)g Fg(itself)24 b Fh(o)o(v)o(er)14 b(its)h(inputs!)91 2438 y(P)o(erhaps)d(it's)h(time)g(for)f(another)h(review)g(of)f(our)h (journey)g(so)f(far.)19 b(In)13 b(principle,)j(there)d(is)g(no)g(need)g (for)f(an)o(y)0 2496 y(con)o(trol)17 b(mec)o(hanism)g(other)f(than)h (recursion)h(in)f(a)g(programming)f(language.)25 b(An)o(y)17 b(problem)g(can)g(b)q(e)h(solv)o(ed)0 2554 y(using)d(recursiv)o(e)h (pro)q(cedures,)f(without)f(explicit)j(lo)q(oping)f(mec)o(hanisms.)k (Ho)o(w)o(ev)o(er,)13 b(the)i(idea)g(of)f(recursion)h(is)0 2612 y(hard)h(for)f(b)q(eginning)j(studen)o(ts,)e(so)f(in)i(order)f(to) f(mak)o(e)g(functional)i(programming)e(practical,)i(it's)f(helpful)i (to)0 2670 y(pro)o(vide)g(to)q(ols)f(that)f(are)h(analogous)f(to)h(lo)q (oping)h(constructs)f(but)g(consisten)o(t)g(with)h(the)f(functional)h (st)o(yle.)26 b(I)952 2779 y(18)p eop %%Page: 19 19 19 18 bop 0 45 a Fh(ha)o(v)o(e)13 b(sho)o(wn)g(four)g(suc)o(h)h(to)q (ols:)f Fd(MAP)p Fh(,)g Fd(CASCADE)p Fh(,)f Fd(REDUCE)p Fh(,)g(and)i Fd(FILTER)p Fh(.)e(These)i(to)q(ols)f(are)g(adequate)h (for)e(man)o(y)0 104 y(problems,)j(but)g(not)f(for)f(all)j(problems.)k (If)15 b(a)f(problem)h(is)g(fundamen)o(tally)h(self-referen)o(tial,)g (then)e(the)h(studen)o(t)0 162 y(m)o(ust)g(understand)g(recursiv)o(e)h (programming)f(to)f(solv)o(e)i(it.)0 279 y Fi(Con)o(tin)o(uing)i(Dev)o (elopmen)o(t)91 397 y Fh(Un)o(til)f(the)e(writing)i(of)e(this)h(pap)q (er)g(I)g(had)g(nev)o(er)g(written)g(a)g(determinan)o(t)f(pro)q (cedure.)23 b(This)16 b(is)h(the)e(\014rst)0 455 y(example)i(I'v)o(e)f (found)g(in)h(whic)o(h)g Fd(MAP)f Fh(and)g Fd(FILTER)f Fh(templates)h(need)h(the)f Fd(#)g Fh(mec)o(hanism)h(to)e(let)i(the)f (function)0 513 y(kno)o(w)g(the)g(p)q(osition)i(of)e(its)g(argumen)o(t) g(in)h(the)g(original)g(input)h(list.)24 b(The)17 b(pro)q(cedure)g (de\014nitions)h(at)e(the)g(end)0 571 y(of)d(the)h(pap)q(er,)g (therefore,)f(are)h(somewhat)f(di\013eren)o(t)g(from)g(earlier)i (published)h(v)o(ersions.)k(Because)14 b(these)g(to)q(ols)0 629 y(are)j(language)h(extensions)g(written)g(in)g(Logo)f(itself,)i(I)f (can)g(mak)o(e)f(this)h(c)o(hange)g(without)f(ha)o(ving)h(to)f(rewrite) 0 688 y(the)g(Logo)g(in)o(terpreter.)27 b(Other)18 b(teac)o(hers)f(can) g(also)h(in)o(v)o(en)o(t)f(their)h(o)o(wn)f(to)q(ols,)h(so)f(that)f (their)i(studen)o(ts)f(ha)o(v)o(e)0 746 y(exactly)i(the)g(necessary)f (to)q(ols)h(for)f(whatev)o(er)g(pro)s(jects)g(are)g(relev)m(an)o(t)h (to)f(their)h(topic.)30 b(F)l(or)18 b(example,)i(for)e(a)0 804 y(computer-based)j(linguistics)j(course)c([Golden)o(b)q(erg,)j (1987])c(P)o(aul)i(Golden)o(b)q(erg)h(in)o(v)o(en)o(ted)f(a)f(to)q(ol)h (to)f(mak)o(e)0 862 y(systematic)15 b(c)o(hanges)g(in)h(the)f(sp)q (elling)j(of)d(a)g(w)o(ord:)0 939 y Fd(?)24 b(SHOW)f(REPLACE)g([M)h(O]) f([P)h(A])f("MOMMY)0 997 y(PAPPY)0 1074 y Fh(The)14 b(\014rst)g(input)h (is)g(a)f(list)h(of)f(letters)g(to)g(lo)q(ok)g(for)g(in)h(the)f(w)o (ord,)f(and)i(the)f(second)h(input)g(is)f(a)g(same-length)h(list)0 1132 y(of)g(replacemen)o(ts.)91 1195 y(Recen)o(tly)21 b(I)f(ha)o(v)o(e)g(found)g(m)o(yself,)h(in)g(certain)g(situations,)g(w) o(an)o(ting)e(something)h(more)g(lik)o(e)h(the)f(LISP)0 1253 y(lam)o(b)q(da)14 b(notation,)g(with)g(explicit)i(names)d(for)h (the)g(slots)f(in)i(the)f(template.)19 b(F)l(or)13 b(example,)i(here)f (is)h(a)e(program)0 1311 y(to)i(m)o(ultiply)h(t)o(w)o(o)e(matrices:)0 1388 y Fd(TO)24 b(MULTIPLY)e(:A)i(:B)24 1446 y(LOCAL)f("TB)24 1504 y(MAKE)g("TB)h(TRANSPOSE)e(:B)24 1562 y(OUTPUT)h(MAP)g([MULROW)g (?)h(:TB])f(:A)0 1620 y(END)0 1737 y(TO)h(MULROW)f(:ROWA)g(:TB)24 1795 y(OUTPUT)g(MAP)g([DOTPROD)g(:ROWA)g(?])h(:TB)0 1853 y(END)0 1930 y Fh(Eac)o(h)16 b(elemen)o(t)g(of)f(the)h(pro)q(duct)g(is) h(the)e(dot)h(pro)q(duct)g(of)f(a)h(ro)o(w)e(of)i Fd(:A)f Fh(and)h(a)f(column)i(of)e Fd(:B)p Fh(.)g(\(The)h(program)0 1988 y(uses)g Fd(TRANSPOSE)e Fh(b)q(ecause)j(w)o(e)e(store)g(matrices)h (b)o(y)g(ro)o(ws,)e(and)i(a)f(ro)o(w)g(of)g(the)h(transp)q(ose)f(is)i (a)e(column)i(of)e(the)0 2046 y(original)g(matrix.\))k(The)14 b(subpro)q(cedure)h Fd(MULROW)e Fh(computes)h(a)f(single)j(ro)o(w)d(of) g(the)h(answ)o(er;)f(the)h(en)o(tire)h(answ)o(er)0 2104 y(is)h(found)f(b)o(y)g(mapping)h Fd(MULROW)f Fh(o)o(v)o(er)f(the)h(ro)o (ws)f(of)h(the)g(\014rst)g(input)h(matrix.)91 2167 y(I)f(don't)g(lik)o (e)h(ha)o(ving)g(to)e(ha)o(v)o(e)h(the)g(auxiliary)h(pro)q(cedure)h Fd(MULROW)p Fh(.)c(I'd)j(rather)e(use)i(t)o(w)o(o)e(nested)h Fd(MAP)p Fh(s,)f(as)0 2226 y(in)i(the)f Fd(MMAP)g Fh(to)q(ol.)20 b(But)15 b(if)h(I)f(try)g(that,)f(I)i(end)f(up)h(with)g(the)f (instruction)0 2302 y Fd(OUTPUT)23 b(MAP)g([MAP)h([DOTPROD)f(?)g(?])h (:TB])f(:A)0 2380 y Fh(One)17 b(of)f(those)f(question)i(marks)f(refers) g(to)f(the)h(slot)g(in)h(the)f(inner)i(template,)e(while)h(the)g(other) e(refers)h(to)g(the)0 2438 y(slot)d(in)i(the)e(outer)g(one.)20 b(This)14 b(can't)f(w)o(ork.)18 b(\(Nor)13 b(w)o(ould)g(it)h(help)h(to) e(use)h Fd(?1)f Fh(and)g Fd(?2)p Fh(.)19 b(W)l(e)14 b(aren't)e(using)j Fd(MAP.2)0 2496 y Fh(to)h(map)h(o)o(v)o(er)f(t)o(w)o(o)f(lists)j(in)f (parallel;)i(w)o(e're)d(using)i(the)f(single-slot)h Fd(MAP)e Fh(t)o(wice.\))25 b(T)l(o)16 b(disam)o(biguate)h(the)g(t)o(w)o(o)0 2554 y(slots,)g(I)g(ha)o(v)o(e)g(to)f(b)q(e)i(able)g(to)e(giv)o(e)h (eac)o(h)g(one)h(a)e(name)h(explicitly)l(.)29 b(The)17 b(notation)f(do)q(esn't)h(actually)h(require)0 2612 y(the)d(w)o(ord)f Fd(LAMBDA)p Fh(,)g(whic)o(h)i(LISP)g(uses)f(for)g(historical)h (reasons;)e(if)h(the)g(\014rst)g(thing)g(in)h(a)f(template)g(is)h(a)e (list)i(in)0 2670 y(square)f(brac)o(k)o(ets,)f(I)i(w)o(an)o(t)e(to)g (tak)o(e)h(that)f(as)h(a)g(list)h(of)f(names)g(of)g(slots.)k(Then)d(I)g (can)f(sa)o(y)952 2779 y(19)p eop %%Page: 20 20 20 19 bop 0 45 a Fd(OUTPUT)23 b(MAP)g([[ROWA])g(MAP)h([[COLB])f (DOTPROD)g(:ROWA)g(:COLB])g(:TB])g(:A)0 118 y Fh(I)16 b(ha)o(v)o(e)e(written)i(to)q(ols)f(that)f(accept)i(this)f(format,)f (but)h(I)h(ha)o(v)o(en't)e(y)o(et)h(tried)g(teac)o(hing)h(it)f(to)g(an) o(y)o(one.)91 176 y(Another)j(anno)o(y)o(ance)g(I'd)g(lik)o(e)h(to)e (eliminate)j(is)f(the)f(need)h(for)e(separate)g(pro)q(cedures)i Fd(MAP)f Fh(and)g Fd(MAP.2)p Fh(.)0 235 y(What)d(if)i(I)f(w)o(an)o(t)f (to)g(map)h(a)g(three-input)h(function)g(o)o(v)o(er)e(three)h(lists)h (of)e(inputs?)24 b(I'd)16 b(lik)o(e)h(a)f(single)h Fd(MAP)f Fh(that)0 293 y(can)d(tak)o(e)g(an)o(y)g(n)o(um)o(b)q(er)h(of)e (inputs,)j(just)e(as)g(certain)g(Logo)g(primitiv)o(es)i(do,)e(inside)i (paren)o(theses.)k(This)14 b(c)o(hange,)0 351 y(unfortunately)l(,)k(do) q(es)f(require)h(mo)q(di\014cations)g(to)f(the)g(Logo)g(in)o (terpreter.)26 b(One)18 b(published)h(v)o(ersion)f(of)e(Logo)0 409 y(\(Ob)s(ject)h(Logo,)h(for)f(the)h(Macin)o(tosh,)g(dev)o(elop)q (ed)h(b)o(y)f(Coral)f(Soft)o(w)o(are)f(and)i(no)o(w)g(o)o(wned)f(b)o(y) h(Apple\))h(allo)o(ws)0 467 y(user-de\014ned)j(pro)q(cedures)g(with)f (v)m(ariable)h(n)o(um)o(b)q(ers)f(of)f(inputs.)38 b(I)21 b(hop)q(e)g(the)g(idea)g(is)h(extended)f(to)f(other)0 525 y(dialects.)0 638 y Fi(T)l(eac)o(hing)e(Exp)q(erience)91 751 y Fh(When)13 b(I)f(published)j(the)d(\014rst)g(v)o(olume)h(of)f Fg(Computer)i(Scienc)n(e)e(L)n(o)n(go)h(Style)h Fh([Harv)o(ey)l(,)e (1985],)f(I)i(in)o(tro)q(duced)0 809 y(mapping)j(to)q(ols)g(near)f(the) h(end)h(of)e(the)h(b)q(o)q(ok,)f Fg(after)21 b Fh(the)16 b(reader)f(w)o(as)g(familiar)i(with)f(recursion,)g(b)q(ecause)g(m)o(y)0 868 y(emphasis)k(w)o(as)f(on)g(the)h(implemen)o(tation)g(of)f(the)h(to) q(ols.)33 b(I)19 b(w)o(an)o(ted)g(to)g(mak)o(e)g(the)g(p)q(oin)o(t)h (that)f(Logo)g(is)h(an)0 926 y(extensible)g(language)e(b)o(y)f(sho)o (wing)h(ho)o(w)g(to)f(extend)h(it.)28 b(I)18 b(had)g(considered)i(in)o (tro)q(ducing)f(the)f(to)q(ols)f(earlier,)0 984 y(without)f(sho)o(wing) g(their)h(de\014nitions,)g(to)f(allo)o(w)g(readers)g(to)f(write)h(in)o (teresting)h(functional)g(programs)e(in)i(the)0 1042 y(early)f(c)o(hapters.)23 b(What)15 b(dissuaded)j(me,)e(at)g(that)f (time,)h(w)o(as)g(that)f(I)i(w)o(as)e(trying)h(to)g(mak)o(e)f(the)i(b)q (o)q(ok)f(usable)0 1100 y(without)g(a)f(teac)o(her)h(b)o(y)g(readers)f (who)h(migh)o(t)f(ha)o(v)o(e)h(an)o(y)f(of)h(half)g(a)f(dozen)i(v)o (ersions)f(of)f(Logo)g(at)g(home.)22 b(Eac)o(h)0 1158 y(dialect)h(is)e(sligh)o(tly)i(di\013eren)o(t)e(from)g(the)g(others.)38 b(I)22 b(felt)g(that)e(I)i(couldn't)g(use)g(to)q(ol)f(pro)q(cedures)h (unless)h(I)0 1216 y(pro)o(vided)16 b(the)f(de\014nitions)i(on)e(disk)o (ette,)g(and)h(that)e(seemed)i(lik)o(e)g(to)q(o)f(m)o(uc)o(h)g (trouble.)91 1275 y(As)20 b(it)h(turned)g(out,)g(the)g(biggest)g (complain)o(t)g(I)g(heard)g(from)f(p)q(eople)i(who)e(taugh)o(t)g (courses)g(based)h(on)0 1333 y(that)13 b(b)q(o)q(ok)h(w)o(as)f(ab)q (out)h(the)g(di\016cult)o(y)h(their)f(studen)o(ts)g(had)g(in)h(the)f(c) o(hapter)f(on)h(recursiv)o(e)h(op)q(erations.)k(Their)0 1391 y(confusion)13 b(w)o(as)d(not)i(only)g(ab)q(out)f(recursion,)i (but)f(ab)q(out)g(the)f(more)h(fundamen)o(tal)g(issue)g(of)g(writing)g (op)q(erations)0 1449 y(at)17 b(all.)28 b(They)17 b(w)o(ere)g (uncomfortable)h(with)g Fd(OUTPUT)f Fh(and)g(with)h(list)g (manipulation.)29 b(The)17 b(reason)h(for)e(this,)j(I)0 1507 y(decided,)j(w)o(as)d(that)f(un)o(til)j(that)e(c)o(hapter)g(they)h (had)f(had)h(v)o(ery)f(little)i(practice)f(writing)g(op)q(erations)g (at)e(all.)0 1565 y(Without)f(recursion,)i(the)e(n)o(um)o(b)q(er)h(of)f (in)o(teresting)h(functions)g(y)o(ou)f(can)g(compute)h(is)g(small.)27 b(By)17 b(presen)o(ting)0 1623 y(to)q(ols)22 b(lik)o(e)i Fd(MAP)e Fh(earlier,)j(it)d(w)o(ould)h(b)q(e)g(p)q(ossible)h(to)e (presen)o(t)h(more)f(and)g(b)q(etter)h(examples)g(of)f(functional)0 1681 y(programming)15 b(in)h(the)f(early)g(c)o(hapters.)91 1740 y(In)g(the)g(fall)h(semester)f(of)f(1988)g(I)h(taugh)o(t)f(a)h (Logo)f(programming)h(course)f(to)h(a)f(small)i(group)f(of)f(Berk)o (eley)0 1798 y(undergraduates)19 b(using)g(this)g(approac)o(h.)30 b(I)19 b(ha)o(v)o(e)f(not)h(revised)g(the)g(b)q(o)q(ok,)g(but)g(in)g (the)g(early)g(w)o(eeks)g(of)f(the)0 1856 y(course)c(I)g(supplemen)o (ted)i(it)e(with)h(handouts)f(and)g(class)g(discussion)i(sho)o(wing)e (the)g(mapping)h(to)q(ols.)k(\(The)14 b(to)q(ol)0 1914 y(pro)q(cedures)f(I)g(used)g(w)o(ere)f(the)h(v)o(ersions)g(in)g([Harv)o (ey)l(,)f(1987],)f(sligh)o(tly)j(di\013eren)o(t)e(from)g(the)g(ones)h (in)g(this)g(pap)q(er.\))0 1972 y(My)e(exp)q(erience)i(w)o(as)e(that)f (the)h(studen)o(ts)g(w)o(ere,)h(as)f(exp)q(ected,)h(easily)h(able)f(to) e(apply)i(functional)h(programming)0 2030 y(ideas)k(to)e(problems)h (that)g(could)h(b)q(e)f(solv)o(ed)g(without)g(recursion.)23 b(Their)17 b(early)f(e\013orts)f(could)i(fo)q(cus)f(on)g(what)0 2089 y(it)k(means)g(for)f(a)h(pro)q(cedure)h(to)e(output)h(a)g(v)m (alue,)i(without)d(b)q(eing)j(confused)e(b)o(y)g(the)g(additional)i (issues)e(of)0 2147 y(self-reference.)h(On)15 b(the)g(other)f(hand,)h (I)g(had)f(hop)q(ed)i(that)d(with)i(this)g(basis)g(they)g(w)o(ould)g (\014nd)g(recursion)g(itself)0 2205 y(easy)i(when)h(w)o(e)f(got)f(to)h (it;)h(in)g(that)f(resp)q(ect)g(I)h(w)o(as)e(disapp)q(oin)o(ted.)28 b(Recursion)19 b(w)o(as)d(still)j(a)e(big)h(h)o(urdle.)27 b(By)0 2263 y(the)19 b(end)h(of)e(the)h(semester)g(almost)g(all)h(of)e (the)h(studen)o(ts)g(could)h(understand)g(recursiv)o(e)f(pro)q(cedures) h(that)f(I)0 2321 y(presen)o(ted,)c(but)h(not)e(all)j(could)f(reliably) h(write)e(their)h(o)o(wn)e(recursiv)o(e)i(pro)q(cedures.)91 2380 y(One)i(mistak)o(e)g(that)f(I)h(made)g(w)o(as)f(to)g(try)g(to)h (motiv)m(ate)f(the)h(use)g(of)g(recursion)g(b)o(y)g(starting)f(with)h (quite)0 2438 y(complicated)e(examples)g(that)e(couldn't)i(b)q(e)g (done)f(using)h(the)f(iterativ)o(e)g(to)q(ols)g(the)g(studen)o(ts)g (already)h(knew.)k(I)0 2496 y(w)o(as)12 b(o)o(v)o(erreacting)h(to)g (the)g(an)o(ticipated)h(question,)g(\\wh)o(y)f(don't)g(w)o(e)g(just)f (use)i Fd(MAP)p Fh(?")f(I)h(w)o(ould)f(no)o(w)g(b)q(egin)i(with)0 2554 y(simpler)g(examples)g(and)g(announce)g(b)o(y)f(\014at)f(that)h (the)g(iterativ)o(e)g(to)q(ols)g(ma)o(y)g(not)g(b)q(e)g(used)h(this)g (w)o(eek.)k(I)c(w)o(ould)0 2612 y(explain)g(that)f(they)f(are)h(going)g (to)f(learn)h(ho)o(w)g(things)g(lik)o(e)h Fd(MAP)e Fh(can)h(b)q(e)h (written)e(in)i(Logo,)e(and)h(to)f(understand)0 2670 y(that,)i(they)h(ha)o(v)o(e)f(to)g(pretend)i(that)e Fd(MAP)g Fh(isn't)h(a)o(v)m(ailable.)23 b(\(By)16 b(the)g(w)o(a)o(y)l(,)f(I)h (ha)o(v)o(e)f(of)h(course)g(done)g(something)952 2779 y(20)p eop %%Page: 21 21 21 20 bop 0 45 a Fh(similar)16 b(in)g(this)f(pap)q(er,)g(in)g(the)g (section)h(that)e(explains)i(wh)o(y)f(recursion)g(is)h(still)g (sometimes)f(necessary)l(.)20 b(But)15 b(I)0 104 y(trust)f(that)h(the)g (reader)g(is)h(not)f(new)g(to)g(Logo)g(and)g(has)g(already)h(seen)f (simpler)i(examples)f(of)f(recursion.\))91 162 y(Man)o(y)10 b(Logo)h(teac)o(hers)g(ha)o(v)o(e)g(noticed)h(that)f(studen)o(ts)g (\014nd)h(recursiv)o(e)g(op)q(erations)f(more)g(di\016cult)i(than)e (the)0 220 y(command-hea)o(vy)16 b(st)o(yle)h(of)e(programming)h(used)h (in)g(turtle)f(graphics)h(applications.)25 b(Some)16 b(ha)o(v)o(e)g(resp)q(onded)0 278 y(b)o(y)h(restricting)h(their)f(Logo) g(teac)o(hing)g(to)g(graphics.)26 b(Others,)17 b(w)o(an)o(ting)g(to)f (preserv)o(e)h(the)g(abilit)o(y)i(to)d(explore)0 336 y(natural)21 b(language)g(issues,)h(ha)o(v)o(e)e(in)o(tro)q(duced)i(w)o (ord)e(pro)q(cessing)i(commands)e(in)o(to)h(Logo)f(so)h(that)f(English) 0 394 y(text)c(can)g(b)q(e)h(pro)q(cessed)g(in)g(the)f(easier)h (command-hea)o(vy)f(st)o(yle.)23 b(\(See,)16 b(for)g(example,)h([T)l (emp)q(el,)g(1986])e(for)g(a)0 452 y(description)f(of)f(this)g(approac) o(h)f(in)i(LogoW)l(riter.\))k(I)13 b(am)g(un)o(willing)i(to)d(withhold) i(from)e(studen)o(ts)h(the)g(p)q(o)o(w)o(erful)0 510 y(idea)k(of)f(functional)h(programming;)f(the)g(w)o(ork)f(describ)q(ed) j(here)f(is)f(an)h(attempt)e(to)g(preserv)o(e)i(the)f(functional)0 568 y(st)o(yle)g(while)h(allo)o(wing)g(studen)o(ts)f(to)f(tak)o(e)g (smaller)i(steps)f(than)f(the)h(enormous)g(in)o(tellectual)i(leap)f (that)e(seems)0 626 y(to)g(b)q(e)g(required)i(in)f(mo)o(ving)f(from)f (commands)h(directly)i(in)o(to)e(recursiv)o(e)h(op)q(erations.)0 848 y Fi(App)q(endix:)23 b(The)18 b(Implemen)o(tation)91 961 y Fh(Resist)f(the)g(temptation)f(to)g(use)g(shorter)g(v)m(ariable)i (names)e(in)i(these)e(pro)q(cedures.)25 b(It's)16 b(imp)q(ortan)o(t)g (that)0 1019 y(these)g(names)f(b)q(e)h(di\013eren)o(t)g(from)f(an)o(y)g (v)m(ariable)i(names)e(used)h(in)g(other)g(parts)e(of)h(the)h(program)e (that)h(in)o(v)o(ok)o(es)0 1077 y(these)g(to)q(ols.)0 1180 y Fd(TO)24 b(MAP)f(:MAP.TEMPLATE)f(:TEMPLATE.LIST)24 1239 y(OUTPUT)h(MAP1)g(PREPARE.TEMPLATE)f(:MAP.TEMPLATE)g (:TEMPLATE.LIST)g(1)0 1297 y(END)0 1413 y(TO)i(MAP1)f(:MAP.TEMPLATE)f (:TEMPLATE.LIST)g(:TEMPLATE.NUMBER)24 1471 y(IF)h(EMPTYP)g (:TEMPLATE.LIST)f([OUTPUT)h([]])24 1529 y(LOCAL)g("TEMPLATE.VAR)24 1587 y(MAKE)g("TEMPLATE.VAR)f(FIRST)h(:TEMPLATE.LIST)24 1645 y(OUTPUT)g(FPUT)g(\(RUN)h(:MAP.TEMPLATE\))310 1703 y(\(MAP1)f(:MAP.TEMPLATE)f(\(BF)i(:TEMPLATE.LIST\))e (1+:TEMPLATE.NUMBER\))0 1761 y(END)0 1878 y(TO)i(PREPARE.TEMPLATE)d (:TEMPLATE)24 1936 y(IF)i(LISTP)h(:TEMPLATE)e([OUTPUT)h(:TEMPLATE])24 1994 y(OUTPUT)g(SENTENCE)g(:TEMPLATE)f("?)0 2052 y(END)0 2168 y(TO)i(?)24 2226 y(OUTPUT)f(:TEMPLATE.VAR)0 2284 y(END)0 2400 y(TO)h(#)24 2458 y(OUTPUT)f(:TEMPLATE.NUMBER)0 2517 y(END)952 2779 y Fh(21)p eop %%Page: 22 22 22 21 bop 0 45 a Fd(TO)24 b(MAP.2)f(:MAP.TEMPLATE)f(:TEMPLATE.LIST1)g (:TEMPLATE.LIST2)24 104 y(OUTPUT)h(MAP.21)g(PREPARE.TEMPLATE.2)e (:MAP.TEMPLATE)358 162 y(:TEMPLATE.LIST1)h(:TEMPLATE.LIST2)g(1)0 220 y(END)0 336 y(TO)i(MAP.21)f(:MAP.TEMPLATE)f(:TEMPLATE.LIST1)g (:TEMPLATE.LIST2)f(:TEMPLATE.NUMBER)24 394 y(IF)i(EMPTYP)g (:TEMPLATE.LIST1)f([OUTPUT)h([]])24 452 y(LOCAL)g([TEMPLATE.VAR1)f (TEMPLATE.VAR2])24 510 y(MAKE)h("TEMPLATE.VAR1)f(FIRST)h (:TEMPLATE.LIST1)24 568 y(MAKE)g("TEMPLATE.VAR2)f(FIRST)h (:TEMPLATE.LIST2)24 626 y(OUTPUT)g(FPUT)g(\(RUN)h(:MAP.TEMPLATE\))310 684 y(\(MAP.21)f(:MAP.TEMPLATE)f(\(BF)i(:TEMPLATE.LIST1\))501 743 y(\(BF)g(:TEMPLATE.LIST2\))d(1+:TEMPLATE.NUMBER\))0 801 y(END)0 917 y(TO)j(PREPARE.TEMPLATE.2)d(:TEMPLATE)24 975 y(IF)i(LISTP)h(:TEMPLATE)e([OUTPUT)h(:TEMPLATE])24 1033 y(OUTPUT)g(SENTENCE)g(:TEMPLATE)f([?1)i(?2])0 1091 y(END)0 1207 y(TO)g(?1)24 1265 y(OUTPUT)f(:TEMPLATE.VAR1)0 1323 y(END)0 1440 y(TO)h(?2)24 1498 y(OUTPUT)f(:TEMPLATE.VAR2)0 1556 y(END)0 1672 y(TO)h(CASCADE)e(:CASCADE.LIMIT)g(:CASCADE.TEMPLATE)g (:TEMPLATE.VAR)24 1730 y(OUTPUT)h(CASCADE1)g(PREPARE.LIMIT)f (:CASCADE.LIMIT)406 1788 y(PREPARE.TEMPLATE)f(:CASCADE.TEMPLATE)406 1846 y(:TEMPLATE.VAR)h(1)0 1904 y(END)0 2021 y(TO)i(CASCADE1)e (:CASCADE.LIMIT)g(:CASCADE.TEMPLATE)g(:TEMPLATE.VAR)g(:TEMPLATE.NUMBER) 24 2079 y(IF)h(\(RUN)h(:CASCADE.LIMIT\))e([OUTPUT)g(:TEMPLATE.VAR])24 2137 y(OUTPUT)h(CASCADE1)g(:CASCADE.LIMIT)f(:CASCADE.TEMPLATE)406 2195 y(\(RUN)h(:CASCADE.TEMPLATE\))e(1+:TEMPLATE.NUMBER)0 2253 y(END)0 2369 y(TO)j(PREPARE.LIMIT)e(:LIMIT)24 2427 y(IF)h(NUMBERP)g(:LIMIT)g([OUTPUT)g(SENTENCE)g([GREATERP)g (:TEMPLATE.NUMBER])e(:LIMIT])24 2485 y(OUTPUT)i(PREPARE.TEMPLATE)f (:LIMIT)0 2543 y(END)952 2779 y Fh(22)p eop %%Page: 23 23 23 22 bop 0 46 a Fd(TO)24 b(CASCADE.2)e(:CASCADE.LIMIT)g (:CASCADE.TEMPLATE1)g(:TEMPLATE.VAR1)668 104 y(:CASCADE.TEMPLATE2)g (:TEMPLATE.VAR2)24 162 y(OUTPUT)h(CASCADE.21)f(PREPARE.LIMIT.2)g (:CASCADE.LIMIT)453 220 y(PREPARE.TEMPLATE.2)g(:CASCADE.TEMPLATE1)f (:TEMPLATE.VAR1)453 278 y(PREPARE.TEMPLATE.2)h(:CASCADE.TEMPLATE2)f (:TEMPLATE.VAR2)h(1)0 336 y(END)0 444 y(TO)i(CASCADE.21)e (:CASCADE.LIMIT)g(:CASCADE.TEMPLATE1)f(:TEMPLATE.VAR1)692 502 y(:CASCADE.TEMPLATE2)g(:TEMPLATE.VAR2)h(:TEMPLATE.NUMBER)24 560 y(IF)h(\(RUN)h(:CASCADE.LIMIT\))e([OUTPUT)g(:TEMPLATE.VAR1])24 618 y(OUTPUT)h(CASCADE.21)f(:CASCADE.LIMIT)453 676 y (:CASCADE.TEMPLATE1)g(\(RUN)h(:CASCADE.TEMPLATE1\))453 734 y(:CASCADE.TEMPLATE2)f(\(RUN)h(:CASCADE.TEMPLATE2\))453 792 y(1+:TEMPLATE.NUMBER)0 850 y(END)0 957 y(TO)h(PREPARE.LIMIT.2)d (:LIMIT)24 1015 y(IF)i(NUMBERP)g(:LIMIT)g([OUTPUT)g(SENTENCE)g ([GREATERP)g(:TEMPLATE.NUMBER])e(:LIMIT])24 1073 y(OUTPUT)i (PREPARE.TEMPLATE.2)e(:LIMIT)0 1132 y(END)0 1239 y(TO)j(REDUCE)f (:REDUCE.TEMPLATE)e(:TEMPLATE.LIST)24 1297 y(OUTPUT)i(REDUCE1)g (PREPARE.TEMPLATE.2)e(:REDUCE.TEMPLATE)h(:TEMPLATE.LIST)0 1355 y(END)0 1462 y(TO)i(REDUCE1)e(:REDUCE.TEMPLATE)g(:TEMPLATE.LIST)24 1520 y(IF)h(EMPTYP)g(BUTFIRST)g(:TEMPLATE.LIST)f([OUTPUT)h(FIRST)g (:TEMPLATE.LIST])24 1578 y(LOCAL)g([TEMPLATE.VAR1)f(TEMPLATE.VAR2])24 1636 y(MAKE)h("TEMPLATE.VAR1)f(FIRST)h(:TEMPLATE.LIST)24 1694 y(MAKE)g("TEMPLATE.VAR2)f(REDUCE1)h(:REDUCE.TEMPLATE)f(BUTFIRST)g (:TEMPLATE.LIST)24 1752 y(OUTPUT)h(RUN)g(:REDUCE.TEMPLATE)0 1810 y(END)0 1918 y(TO)h(FILTER)f(:FILTER.TEMPLATE)e(:TEMPLATE.LIST)24 1976 y(OUTPUT)i(FILTER1)g(PREPARE.TEMPLATE)e(:FILTER.TEMPLATE)h (:TEMPLATE.LIST)g(1)0 2034 y(END)0 2141 y(TO)i(FILTER1)e (:FILTER.TEMPLATE)g(:TEMPLATE.LIST)g(:TEMPLATE.NUMBER)24 2199 y(IF)h(EMPTYP)g(:TEMPLATE.LIST)f([OUTPUT)h([]])24 2257 y(LOCAL)g("TEMPLATE.VAR)24 2315 y(MAKE)g("TEMPLATE.VAR)f(FIRST)h (:TEMPLATE.LIST)24 2373 y(IF)g(\(RUN)h(:FILTER.TEMPLATE\))95 2431 y([OUTPUT)f(FPUT)h(:TEMPLATE.VAR)406 2489 y(FILTER1)f (:FILTER.TEMPLATE)e(BF)j(:TEMPLATE.LIST)597 2547 y(1+:TEMPLATE.NUMBER]) 24 2606 y(OUTPUT)f(FILTER1)g(:FILTER.TEMPLATE)e(BF)j(:TEMPLATE.LIST)e (1+:TEMPLATE.NUMBER)0 2664 y(END)952 2779 y Fh(23)p eop %%Page: 24 24 24 23 bop 0 45 a Fi(References)0 190 y Fh(Ab)q(elson)16 b(H.)e(and)g(Sussman)g(G.)g(1985:)f Fg(Structur)n(e)j(and)f(interpr)n (etation)g(of)h(c)n(omputer)g(pr)n(o)n(gr)n(ams)p Fh(.)j(Cam)o(bridge:) 91 248 y(MIT)c(Press.)0 338 y(Allen)k(J.,)f(Da)o(vis)f(R.,)h(and)g (Johnson)g(J.)f(1984:)f Fg(Thinking)h(ab)n(out)i([TLC])e(L)n(o)n(go)p Fh(.)26 b(New)17 b(Y)l(ork:)g(Holt,)h(Rinehart)91 396 y(and)d(Winston.)0 486 y(Bac)o(kus)i(J.)g(1978:)f(`Can)g(programming)h (b)q(e)h(lib)q(erated)g(from)f(the)g(v)o(on)g(Neumann)h(st)o(yle?')26 b Fg(Communic)n(ations)91 544 y(of)16 b(the)h(A)o(CM)p Fh(,)d(21,)g(613{641.)0 634 y(Golden)o(b)q(erg)i(E.)f(P)l(.)g(and)g(F)l (eurzeig)h(W.)e(1987:)g Fg(Exploring)i(language)g(with)h(L)n(o)n(go)p Fh(.)i(Cam)o(bridge:)c(MIT)g(Press.)0 724 y(Harv)o(ey)g(B.)g Fg(Computer)i(scienc)n(e)d(L)n(o)n(go)i(style)p Fh(.)j(Cam)o(bridge:)c (MIT)g(Press.)91 782 y(1985:)k(V)l(olume)d(1:)j Fg(Interme)n(diate)d (pr)n(o)n(gr)n(amming)p Fh(.)91 840 y(1986:)j(V)l(olume)d(2:)j Fg(Pr)n(oje)n(cts,)d(styles,)f(and)h(te)n(chniques)p Fh(.)91 898 y(1987:)j(V)l(olume)d(3:)j Fg(A)n(dvanc)n(e)n(d)c(topics)p Fh(.)0 988 y(T)l(emp)q(el)i(M.)f(and)g(Mic)o(haud)g(N.)g(1986:)e(`Bey)o (ond)i(T)l(urtle)h(Graphics?')23 b Fg(L)n(o)n(go)16 b(86)h(Pr)n(o)n(c)n (e)n(e)n(dings)p Fh(,)c(Massac)o(h)o(usetts)91 1046 y(Institute)j(of)f (T)l(ec)o(hnology)l(.)952 2779 y(24)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF