ÿWPCú H!ã‡:Üeóu!Ú¾§Õ­î‰ïócâÕ<Üüðž5îv,ž#ž]{é¶àÁ÷«“©#(à [&ä.ñ¡sL”(xµR׬oZÞ†¾Äà`ã¯þ²5¥€†-§÷_øÍS·Ú~:"¸ÍTúþ ¯ÆuÆü¹‚€¨átÁ¤ö1¥¸ÐÔxWQ†y¨\לޟÌ;šë,·$ý±ErËU†šy¸ç¤^lqõ³ ¨§iQûˆbcªp¨ßÌO# "ÁÆA”4@°ÓÞ¼*•†‚D'RâÛr€,ìòµ°?Bk7ËùuQeþ²„ ¡WÚ&s^iHŠL2wñÜPêßÄbtîGçÁŸh5âW9·("2¡ñ¯™9Aî€m"X¯nÏi›2N؇2í%¬‡û•­æ )Xè+5ÛhÄÈ[+¶Ã „Ý…  „àu&Oó14ªå®+·ÇqEm¨ÛÏUöócÏ,£-#XÄOƒgæ¡#àžN.ùÚ¯A_nfåE—^Yó#Ì %Y×ã”à!,÷bòŸ!Dì‡*?Ê÷›ßH& É…BïuÖ®Fù÷‚ŠÌ_D×&[sÁ¦õ‰¨yüWö êFY’}dþut¶{$ßr;Áë·¿MÉëj`mºÌ ¶#!ÆUNç %5 0(;NcUFe^ «w·4Íá mã#|x˜HP LaserJet 5/5M PostScriptÈÚØÚÚØÈÚ0(ÖÃ9 Z‹6Times New Roman RegularX($¡¡<4šÛ 9Z+‹.Courier New Regular-…Ä*á¿D ›Ã*—)ç€M157ÿU‹ÿÀÀÀÝ ƒ!ÝÝ  ÝÔ_ÔññÔ€X eXXXÔÔ€ôúËõXX eÔññÌ€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€€J3/01-232ÌÌDate:€€€€June€2,€2001ÌTo:€€€€€€J3ÌFrom:€€€€Ô_ÔAleksandarÔ_Ô€Ô_ÔDonevÔ_Ô€ÌSubject:€The€need€for€C-like€array€pointers€in€FortranÌññÌññÌIn€my€extensive€work€in€Fortran€95€on€algorithms€using€graphÌand€tree-like€dynamic€data-structures€I€have€found€a€very€strong€need€forÌC-like€array€pointers,€and€have€recently€concluded€that€Ô_ÔexitstingÔ_ÔÌÔ_ÔworkaroundsÔ_Ô€in€F95€are€unsatisfactory€and€will€further€deter€the€usage€ofÌFortran€in€certain€areas€of€computer€science.ÌÌI€wish€to€document€my€need€with€an€example€and€propose€a€possible€additionÌto€Ô_ÔaccomodateÔ_Ô€for€this€need:ÌÌAssume€we€wish€to€represent€a€graph€(an€object€that€is€a€collection€ofÌvertices,€or€points,€and€a€collection€of€edges,€or€lines,€connecting€theÌvertices)€with€adjacency€lists.€This€means€that€for€each€vertex€we€want€toÌhave€a€list€of€the€edges€that€are€incident€upon€it.ÌOne€standard€representation€is€to€make€two€integer€arrays,€one€which€I€willÌcall€Ô_ÔNEIGHBOURSÔ_Ô,€and€another€which€I€will€call€Ô_ÔMY_NEIGHBOURSÔ_Ô.€Assuming€weÌnumber€the€nodes€from€1€to€N,€then€the€elements:ÌÔ_ÔNEIGHBOURSÔ_Ô(Ô_ÔMY_NEIGHBOURSÔ_Ô(I):Ô_ÔMY_NEIGHBOURSÔ_Ô(I+1)-1)Ìgive€the€indices€of€the€nodes€that€Ô_ÔneighbourÔ_Ô€node€I.€In€a€sense,€weÌrepresent€the€list€of€Ô_ÔneighboursÔ_Ô€using€an€array,€and€concatenate€all€ofÌthese€small€arrays€into€one€big€array€Ô_ÔNEIGHBOURSÔ_Ô,€and€we€use€the€arrayÌÔ_ÔMY_NEIGHBOURSÔ_Ô€to€chop€the€large€array€into€pieces.ÌÌThis€representation€is€efficient€and€can€be€used€in€FORTRAN€77.€HoweverÌit€suffers€from€a€lack€of€modularity€and€dynamic€character,€which€I€feel€isÌnot€necessary€to€describe€in€detail,€since€they€are€relatively€obvious.ÌA€much€more€dynamic€and€easier€to€useÌin€a€modular€fashion€is€an€approach€in€which€each€node€is€a€user-definedÌdata-type€that€contains€its€list€of€nodes.€Depending€on€the€kind€of€dynamicÌcharacter€needed,€many€schemes€are€possible,€but€I€will€use€a€very€simpleÌone€sufficient€to€illustrate€my€point:ÌÌTYPE€vertexÌ€€€INTEGER,€DIMENSION(:),€POINTER€::€neighbors€!€The€list€of€neighborsÌEND€TYPE€vertexÌÌNow,€one€has€freedom€of€where€the€neighbors€are€stored€and€how€they€areÌallocated,€and€can€simply€use€pointer€assignment€on€neighbors€to€changeÌthis.€For€efficiency€reasons,€one€would€almost€always€allocate€a€large€arrayÌÔ_ÔNEIGHBOURSÔ_Ô€when€initializing€the€graph,€and€then€chop€this€array€into€smallÌpieces,€this€time€using€the€array€pointer€Ô_ÔneighboursÔ_Ô€instead€of€the€globalÌindex€array€Ô_ÔMY_NEIGHBOURSÔ_Ô.€An€example€code€segment€might€be:ÌÌTYPE(vertex),€DIMENSION(N)€::€V€!€Vertex€setÌINTEGER,€DIMENSION(N*d)€::€N€!€Ô_ÔNeighbourÔ_Ô€set,€d€is€maximal€degreeÌINTEGER€::€vertex,€counter,€degreeÌÌcounter=1ÌDO€vertex=1,€NÌ€€degree=...€!€Assign€valueÌ€€V(vertex)%neighbors=>N(Ô_Ôcounter:counterÔ_Ô+degree)€!€Pointer€assignmentÌ€€counter=counter+degreeÌEND€DOÐ ¶-); ЇThis€approach€is€nice€to€use€and€allows€one€to€have€freedom€in€how€theÌÔ_ÔneighbourÔ_Ô€lists€are€allocated,€for€example.ÌÌThe€above€code€has€a€big€efficiency€problem€though,€which€is€very€importantÌin€practice.€The€array€pointer€Ô_ÔneighboursÔ_Ô€in€the€type€vertex€usually€takes€aÌlot€of€memory,€since€the€array€pointer€concept€of€Fortran€90€requires€thatÌÔ_ÔadressÔ_Ô,€stride€and€bound€information€be€stored.€The€compilers€I€have€usedÌusually€pad€this€to€some€large€value€such€as€16€or€32€bytes.€This€storageÌrequirement€is€excessive€and€in€many€cases€not€necessary.€For€example,Ìstride€information€is€often€not€needed€since€the€user€knows€that€he€willÌonly€use€memory€Ô_ÔcontigousÔ_Ô€blocks,€and€in€some€cases,€such€as€skip€linkedÌsearch€lists,€the€size€(bound)€information€is€also€not€needed.ÌÌIn€my€opinion,€if€one€had€a€C-like€array€pointers€in€Fortran€90,€similar€toÌassumed-size€array€arguments,€that€is,€deferred-shape€arrays€which€rely€onÌsequence€association€and€do€not€store€an€array€descriptor,€but€rather€just€aÌmemory€address€(C-pointer),€then€efficient€implementations€of€veryÌsophisticated€dynamic€data-structures€are€possible.ÌÌOne€possible€syntax€for€this€is€to€add€a€Ô_ÔdefferedÔ_Ô-shape€dimensionÌdeclaration€that€has€a€*€in€the€last€dimension,€just€like€assumed-sizeÌarray€arguments.€For€example,€here€is€a€possible€declaration€of€the€typeÌvertex€with€this€approach:ÌÌTYPE€vertexÌ€€€INTEGER€::€degree=0Ì€€€INTEGER,€DIMENSION(*),€POINTER€::€Ô_ÔneighboursÔ_ÔÌEND€TYPE€vertexÌÌthen€the€assignment€of€the€Ô_ÔneighbourÔ_Ô€list€in€the€above€code€would€beÌsubstituted€with:ÌÌV(vertex)%degree=degreeÌV(vertex)%neighbors=>N(counter)€!€Or€maybe€N(counter:)Ì€€€!€Or€maybe€N(Ô_Ôcounter:counterÔ_Ô+degree)ÌÌI€can€not€say€with€certainty€how€such€a€syntax€would€fit€into€the€standard,Ìand€would€greatly€appreciate€suggestions€from€J3.€However,€I€stronglyÌbelieve€in€the€need€for€this€kind€of€contiguous€deferred-shape€arrays,€andÌhave€strong€Fortran€95€experience€to€support€this€claim.€I€have€advocated,Ìtaught€and€used€Fortran€95€extensively,€and€believe€this€change€will€makeÌthe€language€much€more€attractive€to€computer€scientists.€ApplicationsÌinclude€better€interfacing€with€C€(think€of€buffer€creation€for€Ô_ÔMPIÔ_ÔÌapplications,€interfacing€with€external€C-based€memory€allocators,€betterÌinterfacing€with€FORTRAN€77€procedures€accepting€assumed-size€arguments,Ìetc.)ÌÌAlso,€since€we€have€assumed-size€arrays€in€Fortran,€the€same€restrictionsÌthat€apply€to€these€inside€procedures€(such€as€the€fact€that€they€can€not€beÌused€in€array€Ô_ÔstatmentsÔ_Ô€without€explicit€bounds,€or€can€not€be€used€inÌcertain€array€inquiry€functions,€etc.),€can€be€applied€in€this€case.€So€IÌexpect€this€will€not€require€a€big€change€of€the€standard.€I€may€be€wrong€ofÌcourse.ÌÌThere€are€other€changes€that€I€would€like€to€see€in€F2k,€particularlyÌpertaining€to€adding€features€for€restricting€Ô_ÔaliasingÔ_Ô€of€pointers€in€theÌform€of€programmer€guarantees€for€non-Ô_ÔalisingÔ_Ô,€but€the€above€addition€isÌbecoming€increasingly€important€as€I€program€more€dynamic€data-structuresÌand€use€C€graph€libraries€(which€are€abundant).€So€I€am€very€interested€inÌseeing€this€considered€carefully€by€committee€members.Ð ¶-); ЇññThank€you€for€your€time,ÌÔ_ÔAleksandarÔ_ÔÌ______________ÌPhysics€and€Astronomy€Department,€Michigan€State€UniversityÌhttp://www.pa.msu.edu/~donevÌññ