Scalas typsystem förenar aspekter av ML-moduler, objektorienterad och funktionell programmering. Den beroende objekttyper (DOT) familjen av calculi har föreslagits som en ny teoretisk grund för Scala och liknande expressiva språk. Tyvärr är det inte klart hur DOT relaterar till välstuderade typsystem från litteraturen, och typ ljudstyrka har bara fastställts för mycket begränsade undergrupper. I själva verket har det visat sig att viktiga Scala-egenskaper såsom typförfining eller undertypningsförhållande med latticestruktur bryter minst en viktig metateoretisk egenskap, såsom miljöförträngning eller subtypering av transitivitet, som vanligen krävs för en typ av ljudstyrka. Det första huvudsakliga bidraget i detta dokument är att visa hur, kanske förvånande, även om dessa egenskaper går förlorade i sin fulla generalitet, en rik DOT-kalkyl som inkluderar både typförfining och en undertypning lattice med skärningstyper kan fortfarande bevisas ljud. Den viktigaste insikten är att förträngning och subtyping transitivitet bara behöver hålla för runtime objekt, men inte för kod som aldrig utförs. Ack, den dominerande metoden för att bevisa typ ljud, Wright och Felleisen syntaktik, bygger på termen omskrivning, som inte a priori gör en åtskillnad mellan runtime och typ tilldelningstid. Det andra huvudsakliga bidraget i detta dokument är att visa hur typ ljudstyrka bevis för avancerade, polymorfa, typsystem kan utföras med en operativ semantik baserad på hög nivå, definition tolkar, implementeras i Coq. Vi presenterar den första mekaniserade ljudstyrka bevis i denna stil för System F <: och flera förlängningar, inklusive muterbara referenser. Våra bevis använder endast enkel induktion, vilket är en annan överraskande resultat, eftersom kombinationen av stora steg semantik, muterbara referenser, och polymorfism allmänt anses kräva co-induktiva bevistekniker. Det tredje huvudsakliga bidraget i detta dokument är att visa hur DOT-like calculi uppstår ur enkla generaliseringar av de operativa aspekterna av F <:, att exponera en rik design utrymme av kalkyl med vägberoende typer mellan System F och DOT, som vi kollektivt kallar System D. Beväpnad med insikter från definitionstolk semantik, visar vi också hur likvärdiga små steg semantik och ljudstyrka bevis i stil med Wright och Felleisen kan härledas för dessa system.
Ljudstyrka resultat med mekaniserade bevis för versioner av System D <: och DOT liknande dem som presenteras här (men fortfarande baserat på big-step semantics) var först nyligen etablerat REF.
From F to DOT: Type Soundness Proofs with Definitional Interpreters
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}