Detta dokument visar hur supersammanställning kan omarbetas för att uttryckligen baseras på en utvärderare, i motsats till standardpresentationer som specificeras som algoritmer som blandar utvärderingsregler med minskningar som är unika för supersammanställning. Genom att bygga på standardoperativ-semantik teknik för call-by-need språk visar vi hur man utökar superkompileringsalgoritmen för att hantera rekursiva låtuttryck. Trots sin anmärkningsvärda kraft är omvandlingen enkel, principiell och helt automatisk. Superkompilering är nära relaterat till partiell utvärdering, men kan uppnå strikt mer optimerade omvandlingar [6]. De viktigaste bidragen i detta dokument är följande: • Inspirerad av Mitchells lovande resultat [7], kastar vi supersammanställning i ett nytt ljus, visar hur man utformar en modulär superkompilator som är direkt baserad på den operativa semantik av språket (avsnitt 3). Att se superkompilering på detta sätt är värdefullt, eftersom det gör det lättare att få fram en superkompilator på ett systematiskt sätt från språket, och att anpassa den till nya språkfunktioner. Tidigare arbete kombinerar utvärdering och specialisering på ett mycket mer komplext och ad hoc-mässigt sätt. • Som ett exempel på denna flexibilitet visar vi hur man superkompilerar ett nödspråk med obegränsade rekursiva uthyrningsbindningar, genom att använda en standardutvärderare för call-by-need (avsnitt 4). Detta har två fördelar: Tillstånd att göra digitala eller hårda kopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift under förutsättning att kopior inte görs eller distribueras för vinst eller kommersiell fördel och att kopior bär detta meddelande och den fullständiga hänvisning på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. , tidigare supercompilers för lata språk har endast behandlat icke-rekursiva låtbindningar. HOSC kan också avskoga detta exempel, men till priset av ibland duplicera arbete något som vi är noga med att undvika. Eftersom rekursion inte är speciell, behöver vi inte ge programmet toppnivå speciell status, eller λ-lyft inmatningsprogrammet. • Vi utför en empirisk utvärdering av vår superkompilator (avsnitt 5), särskilt genom att jämföra den med Mitchells superkompilator [7]. Källkoden för genomförandet, Cambridge Haskell Supercompiler (CHSC), är tillgänglig online 1. Vår superkompilator minskar körtiden med upp till 95%, med en genomsnittlig minskning på 26%. Det bästa sättet att förstå hur superkompilering fungerar är genom exempel. Låt oss börja med ett enkelt exempel på hur standard superkompilering kan specialisera funktioner på deras högre ordning argument: En supercompiler utvärderar öppna termer, så att minskningar som annars skulle göras vid körtiden utförs vid kompileringstid. Därför är det första steget i algoritmen att minska termen så mycket som möjligt, enligt standard utvärderingsregler: Vid denna punkt, vi fastnar på den fria variabeln zs. Det viktigaste beslutet när man utformar en superkompilator är hur man ska gå till väga i en sådan situation, och vi kommer att ägna avsevärd tid senare åt att förklara hur detta val görs när vi täcker splittern i avsnitt 3.5. I just detta exempel fortsätter vi med rekursivt superkompilera två underuttryck. Vi avser att senare reombera de två underuttryck till en output term där fallet zs förblir i utdataprogrammet, men där båda grenarna av fallet har optimerats ytterligare genom superkompilering.
Som visades i REF, kan supersammanställning baseras på en utvärderare som försöker minska en öppen term till huvud normal form.
Supercompilation by evaluation
{'venue': "Haskell '10", 'journal': None, 'mag_field_of_study': ['Computer Science']}