VLISP A Verfied Implementation of Scheme: A Special Issue of Lisp and Symbolic Computation, An International Journal Vol. 8, Nos. 1 & 2 March 1995

پروژه VLISP نشان داد که چگونه می توان یک پیاده سازی تأیید شده جامع برای یک زبان برنامه نویسی، یعنی Scheme [4، 15] تولید کرد. برخی از عناصر اصلی در این راستی آزمایی عبارتند از: • اثبات بر اساس معناشناسی دلالتی کلینگر-ریس طرح ارائه شده در [15] بود. هدف ما ایجاد یک راستی‌آزمایی «زگیل و همه» از یک زبان واقعی بود. با استثنائات بسیار کمی، ما خودمان را محدود کردیم تا از مشخصات se mantic همانطور که منتشر شده است استفاده کنیم. راستی‌آزمایی قرار بود دقیق باشد، اما. نه کاملاً رسمی، تقریباً به سبک گفتمان معمولی ریاضی. هدف ما تأیید الگوریتم‌ها و انواع داده‌های مورد استفاده در implementat.ion بود، نه تجسم آنها. در کد برای بحث کاملتر در مورد این مسائل به بخش 2 مراجعه کنید. تصمیم ما برای وفاداری به مشخصات معنایی منتشر شده منجر به سخت‌ترین بخش‌های اثبات شد. اینها در [13، بخش 2.3-2.4) مورد بحث قرار گرفته اند. • اجرای ما بر اساس اجرای Scheme48 از کلسی و ریس [17] بود. این پیاده سازی Scheme را به یک زبان سطح متوسط ​​\"بایت کد\" ترجمه می کند که توسط یک ماشین مجازی تفسیر می شود. ماشین مجازی در زیر مجموعه ای از Scheme به نام PreScheme نوشته شده است. Implementationissufficient.ly کامل و کارآمد است که به آن اجازه می دهد خود را بوت استرپ کند. ما معتقدیم که این اولین است. اجرای زبان را با این خصوصیات تأیید کرد.

The VLISP project showed how to produce a comprehensively verified implemen­ tation for a programming language, namely Scheme [4, 15). Some of the major elements in this verification were: • The proof was based on the Clinger-Rees denotational semantics of Scheme given in [15). Our goal was to produce a "warts-and-all" verification of a real language. With very few exceptions, we constrained ourselves to use the se­ mantic specification as published. The verification was intended to be rigorous, but. not. complet.ely formal, much in the style of ordinary mathematical discourse. Our goal was to verify the algorithms and data types used in the implementat.ion, not their embodiment. in code. See Section 2 for a more complete discussion ofthese issues. Our decision to be faithful to the published semantic specification led to the most difficult portions ofthe proofs; these are discussed in [13, Section 2.3-2.4). • Our implementation was based on the Scheme48 implementation of Kelsey and Rees [17). This implementation t.ranslates Scheme into an intermediate-level "byte code" language, which is interpreted by a virtual machine. The virtual machine is written in a subset of Scheme called PreScheme. The implementationissufficient.ly complete and efficient to allow it to bootstrap itself. We believe that this is the first. verified language implementation with these properties.