Programmerare resonerar om sina program med hjälp av en mängd olika formella och informella metoder. Programmerare i otypade språk som Scheme eller Erlang kan använda någon sådan metod för att resonera om typbeteendet hos sina program. Vårt typsystem för schemat rymmer vanliga resonerande metoder genom att tilldela variabla händelser en subtyp av deras deklarerade typ baserat på predikat före händelsen, en disciplin dubbade händelseskrivning. Det gör det möjligt för programmerare att berika den befintliga systemkoden med olika typer, samtidigt som det krävs få ändringar av själva koden. Tre års praktisk erfarenhet har avslöjat allvarliga brister i vårt typsystem. Den förlitade sig särskilt på ett system med ad hoc-regler för att relatera kombinationer av predikat, den kunde inte resonera om delkomponenter av datastrukturer, och den kunde inte följa ett sofistikerat resonemang om förhållandet mellan predikattester, som alla används i befintlig kod. I det här dokumentet omformulerar vi skrivningen av händelser för att undanröja dessa brister. Den nya formuleringen härleder förslagslogiska formler som håller när ett uttryck utvärderar till sant eller falskt, respektive. Ett enkelt bevissystem används sedan för att bestämma typer av variabla händelser från dessa påståenden. Vårt genomförande av detta reviderade system av händelsetyp klarar därmed av många fler otypade programmeringsimdiomer än det ursprungliga systemet.  Nyckelord Typsystem, Otypade språk, Logic Utvecklingsprogram på ett maskinskrivet språk hjälper programmerare att undvika misstag. Det tvingar dem också att tillhandahålla viss dokumentation, och det etablerar några skyddande abstraktionsbarriärer. Som sådan innebär typsystemet en disciplin för programplaneringsprocessen. Ändå fortsätter många programmerare att välja otypade skriptspråk för sitt arbete, däribland många som arbetar i funktionell stil. När någon så småningom beslutar att uttryckligen angiven typ information minskar underhållskostnader, de står inför en * Denna forskning fick delvis stöd av bidrag från den amerikanska NSF och en donation från Mozilla Foundation. Tillstånd att göra digitala eller papperskopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift, förutsatt att kopiorna inte görs eller distribueras för vinst eller kommersiella fördelar och att kopiorna är försedda med detta meddelande och den fullständiga hänvisningen 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. ICFP'10 september 27-29, 2010, Baltimore, Maryland, USA. Upphovsrätt c 2010 ACM 978-1-60558-794-3/10/09. .... 10.00 dilemma. För att ta itu med denna situation måste vi utveckla maskinskrivna systerspråk för otypade språk. Med dessa kan programmerare berika befintliga program med typdeklarationer vid behov och samtidigt upprätthålla smidig driftskompatibilitet. Ett typsystem för ett befintligt otypat språk måste ta hänsyn till de befintliga idiomen för att hålla kostnaden för typberikning låg. I annat fall kräver typberikning ändringar av koden, vilket kan medföra nya misstag. Det idealiska systerspråket kräver inget annat än tillägg av typspecifikationer till funktionshuvuden, strukturdefinitioner etc. Vår erfarenhet visar att programmeringsidom i otypade funktionella språk vilar på en kombination av traditionella typbaserade resonemang med resonemang om kontrollflöde. I synnerhet används villkor och predikat av datatyp för att fastställa egenskaperna hos variablernas värden, och på grundval av detta flödeskänsliga resonemang använder programmerare variabler vid mer specifika typer än förväntat. Med andra ord bestämmer programmeraren vilken typ av variabel händelse som är baserad på de predikat som flow-dominerar den. Flera forskare under årtiondena har upptäckt denna insikt. I sitt dokument om den statiska analysen av otypade program konstaterar Reynolds [1968] att ett sådant resonemang är nödvändigt och säger att "i framtida system bör en viss hänsyn tas till lokalerna i villkorliga uttryck". I sitt arbete med TYPD LISP beskriver Cartwright [1976, §5] att man måste överge policyn att avvisa typinkorrekta program eftersom variablerna i villkor hade alltför breda typer. På samma sätt anger Henglein och Rehof [1995] i sitt dokument om översättning av Scheme to ML "typtestning predikerar förlusten av statisk typinformation eftersom de vanligtvis används för att styra kontrollflödet i ett program på ett sådant sätt att utförandet beror på vilken typ tagg ett objekt har vid körtid." Vi utnyttjade denna insikt för utvecklingen av Typed Scheme, ett skrivbart systerspråk för Racket (tidigare PLT Scheme) [TobinHochstadt och Felleisen 2008]. Dess typsystem kombinerar flera redan existerande element-"sanna" rekursiva union typer, subtyping, polymorfism-med den nya idén om förekomst maskinskrivning, 1 en typ disciplin för att utnyttja användningen av data-typ predikat i testuttrycket av villkor. Således, om ett test använder (antal? x), typsystemet använder typnumret för x i den dåvarande grenen och den deklarerade typen av x, minus Nummer, annars. Tre års omfattande användning har avslöjat flera brister i vår ursprungliga design. Ett betydande problem gäller kontrollflödet som styrs av logiska kombinationer (t.ex. och, eller inte) av predikattester. En annan är att typsystemet inte kan spåra användning av predikat som tillämpas på strukturväljare såsom bil. Denna brist på uttrycksförmåga i typsystemet beror på grundläggande begränsningar. För det första, vårt ursprungliga system inte betraktar asymmetrier mellan då och andra grenar av villkor. Till exempel när uttrycket (och (antal? x) (> x 100)) är sant, typsystemet bör veta att x är ett tal, men x kan eller 1 Komondoor et al. [2005] myntade självständigt termen "tillfällig maskinskrivning" i samband med att man tillhandahåller ett avancerat typsystem för COBOL. kanske inte är ett tal när uttrycket är falskt, eftersom det kan vara 97 eller "Hej". För det andra skiljer inte typsystemet på lämpligt sätt mellan väljarens uttryck såsom (car x) och predikatera uttryck som (nummer? x)..................................................................................................... För det tredje bygger behandlingen av kombinationer av tester på en ad hoc-samling av regler. I detta dokument presenterar vi en ny och enkel ram för händelseskrivning som eliminerar alla tre problemen genom en ökning av uttryckskraft. Den viktigaste innovationen är att omvandla kontrollflödet till formler i propositionslogiken för resonemang om typerna av variabler. Atomförslagen innehåller påståenden om att en viss variabel har en viss typ, som ersätter den tidigare samlingen av specialfall med läroboksregler för logisk slutledning. Denna nya design gör det möjligt för typsystemet att resonera om kombinationer av predikat: (cond [och (antal? (node-vänster x)) (sträng? (node-höger y) ;; känd: (node-höger y) är en sträng, (node-vänster x) är ett nummer. Nu bestämmer programmeraren och det reviderade typsystemet det sedan dess (antal? (node-vänster x) är sant i den andra klausulen, (sträng? (node-right y) måste vara falskt, och därför (node-right y) är inte en sträng. Genom att använda förslagslogik för att resonera om predikat hanterar detta och många andra liknande situationer. Utöver det nya typsystemet bidrar detta dokument till: • En fullfjädrad implementering av kalkylen, nu kallad Typed Racket, som tar upp hela komplexiteten i den funktionella kärnan i Racket, såsom muterbara data och flera argument, • en empirisk studie av användbarheten av våra förlängningar, och • en ny modell-teoretisk bevisteknik för typ ljud. Papperet börjar med en kort genomgång av essensen av händelseskrivning med tonvikt på programmering idiomer som vårt ursprungliga system inte kan typkontroll. Vi beskriver sedan det nya systemet på ett semiformellt sätt. I de tre följande avsnitten beskriver vi systemet formellt: först kärnsystemet för händelseskrivning, sedan flera förlängningar som visar hur uttrycksfullt systemet är, och tredje beviset för sundhet. Dessa avsnitt följs av en beskrivning av vår genomförandestrategi och empiriska mått på dess användbarhet på befintlig kod. Slutligen diskuterar vi relaterat arbete och avslutar.
Skrivet Racket händelse skriva smalar typ av fackföreningar baserat på kontroll dominerar typ tester, och dess latenta predikat lyfta resultaten av tester över högre ordning funktioner REF.
Logical types for untyped languages
{'venue': "ICFP '10", 'journal': None, 'mag_field_of_study': ['Computer Science']}