I denna funktionella pärla undersöker vi användningen av definitionstolkar som en grund för abstrakt tolkning av högre ordinära programmeringsspråk. Som det visar sig kan definitionstolkar, särskilt de som är skrivna i monadisk stil, utgöra en bra grund för ett brett utbud av semantik, abstrakta tolkningar, symboliska avrättningar och deras intermixing. Men den verkliga insikten i denna berättelse är en replaying av en insikt från Reynolds landmärke papper, Definitional tolkar för högre-Order programmeringsspråk, där han observerar definitionstolkar gör det möjligt för de definierade språk att ärva egenskaper definitionsspråket. Vi visar samma sak för definitionsmässiga abstrakta tolkar. Anmärkningsvärt är att abstrakta definitionstolkar kan ärva den så kallade "pushdown control flow" egenskapen, där funktionssamtal och returer exakt matchas i den abstrakta semantiken, helt enkelt på grund av funktionen anropsmekanism för det definierande språket. De första tillvägagångssätten för att uppnå denna egenskap för högre ordning språk dök upp under de senaste tio åren, och har sedan dess varit föremål för många papper. Dessa tillvägagångssätt börjar från en state-machine semantics och innebär enhetligt betydande teknisk konstruktion för att återvinna precisionen av pushdown kontrollflödet. Med utgångspunkt från en definitionstolk är däremot den nedpressade kontrollflödet en naturlig del av metaspråket och kräver ingen ytterligare teknisk mekanism för att uppnå detta. Den uppsättning av nåbara stater är okomplicerad. Kärnan i den statsmaskinbaserade metoden destillerades av Van Horn och Might i deras "abstrakta abstrakta maskiner" (AAM) teknik, som ger en systematisk metod för att konstruera abstrakta tolkar från standard abstrakta maskiner som CEK-eller Krivine-maskiner [Van Horn och Might 2010]. Språkdesigners som vill bygga abstrakta tolkar och programanalysverktyg för sitt språk kan nu, åtminstone i princip, först bygga en statsmaskinstolk och sedan vrida veven för att konstruera den approximerande abstrakta motsvarigheten. En naturlig fråga som uppstår ur detta tidigare arbete är att undra: kan en systematisk abstraktionsteknik liknande AAM utföras för tolkar skrivna, inte som statsmaskiner, utan istället som högt definierade tolkar, d.v.s. Rekursiva, kompositionsutvärderare? Denna funktionella pärla svarar jakande och visar några av de intressanta konsekvenserna av att göra det. För det första visar vi att AAM receptet kan tillämpas på definitionstolkar med endast en liten anpassning av den ursprungliga metoden. Den främsta tekniska utmaningen i denna nya miljö är att hantera tolk fasta punkter på ett sätt som är både sunt och alltid avslutar-en naiv abstraktion av fasta punkter kommer att vara bra men är inte alltid avslutande, och en naiv användning av caching för fasta punkter kommer att garantera uppsägning men är i sig osund. Vi tar itu med denna tekniska utmaning med en caching fast-punkt-finding algoritm som är både bra och garanterat att avsluta när abstraktion godtycklig definition tolkar. För det andra hävdar vi att det abstrakta definitionstolkperspektivet är fruktbart i två avseenden. Den första är föga förvånande: abstrakta tolkar på hög nivå erbjuder de vanliga goda egenskaperna hos sina konkreta motsvarigheter när det gäller att vara återanvändbar och extensibel. I synnerhet visar vi att abstrakta tolkar kan struktureras med monadtransformatorer till god effekt. Den andra synpunkten är mer förvånande, och vi anser att dess iakttagelse är det viktigaste bidraget från denna pärla. Definitionstolkar, i motsats till abstrakta maskiner, kan lämna aspekter av beräkning implicit, förlita sig på semantik av definitionsspråket för att definiera semantik av det definierade språket, en observation som gjorts av Reynolds [1972] i hans landmärke papper, Definitional tolkar för högre ordning programmeringsspråk. Till exempel visade Reynolds att det är möjligt att skriva en definitionstolk så att den definierar ett call-by- value-språk när metaspråket är call-by- value, och definierar ett call-by-name-språk när metaspråket är call-by-name. Inspirerade av Reynolds visar vi att abstrakta definitionstolkar också kan ärva metaspråkets egenskaper. I synnerhet konstruerar vi en abstrakt definitionstolk där det inte finns någon explicit representation av fortsättningar eller en samtalstack. I stället är tolken skriven i en enkel rekursiv stil, och call stacken hanteras implicit av metalanguge. Vad som framträder ur denna konstruktion är en total abstrakt utvärderingsfunktion som på ett sunt sätt approximerar alla möjliga konkreta utföranden av ett givet program. Men anmärkningsvärt, eftersom den abstrakta utvärderaren förlitar sig på metaspråket för att hantera samtalstacken implicit, är det lätt att konstatera att det inte introducerar någon approximation i matchningen av samtal och returer, och därför genomför en "pushdown" analys [Earl et al. 2010; Vardoulakis och Shivers 2011], alla utan behov av någon explicit maskiner för att göra det.
Definitionstolkar har föreslagits som en teknik för att bygga sammansättning abstrakt tolkar REF.
Abstracting definitional interpreters (functional pearl)
{'venue': 'PACMPL', 'journal': None, 'mag_field_of_study': ['Computer Science']}