page8.scm

(group "Compiler Technology/Implementation Techniques and Optimization")

(group "Basic Techniques")

(id steele1978rabbit)
(type techreport)
(title "Rabbit: A compiler for Scheme")
(author "Steele Jr, Guy L")
(year 1978)
(month 5)
(number "AITR-474")
(institution "Massachusetts Institute of Technology")
(pdf-sha1 "77e89aa6508d00e505dfb7ca98c141357d8caccb")
(pdf "https://archive.org/download/bitsavers_mitaiaimAI_11751904/AITR-474.pdf")
(abstract "We have developed a compiler for the lexically-scoped dialect of LISP known as SCHEME. The compiler knows relatively little about specific data manipulation primitives such as arithmetic operators, but concentrates on general issues of environment and control. Rather than having specialized knowledge about a large variety of control and environment constructs, the compiler handles only a small basis set which reflects the semantics of lambda-calculus. All of the traditional imperative constructs, such as sequencing, assignment, looping, GO TO, as well as many standard LISP constructs such as AND, OR and COND, are expressed as macros in terms of the applicative basis set. A small number of optimization techniques, coupled with the treatment of function calls as GO TO statements, serves to produce code as good as that produced by more traditional compilers.")

(id adams1986orbit)
(type article)
(title "Orbit: An optimizing compiler for Scheme")
(author "Adams, Norman")
(author "Kranz, David")
(author "Kelsey, Richard")
(author "Rees, Jonathan")
(author "Hudak, Paul")
(author "Philbin, James")
(journal "ACM SIGPLAN Notices")
(volume "21")
(number "7")
(pages "219--233")
(year 1986)
(month 6)
(publisher "ACM New York, NY, USA")
(pdf-sha1 "7eaea33f91c32ca3bd13888eefcf7879d68c33ba")
(pdf "https://people.csail.mit.edu/riastradh/t/adams86orbit.pdf")
(pdf "https://www.academia.edu/download/49363232/adams86orbit.pdf")
(abstract "In this paper we describe an optimizing compiler for Scheme (3, 13] called Orbit that incorporates our experience with an earlier Scheme compiler called TC (10, 11], together with some ideas from Steele's Rabbit compiler. The three main design goals have been correctness, gencrating very efficient compiled code, and portability." "In spirit, Orbit is similar to the Rabbit compiler in that it depends on a translation of source code into \"continuation-passing style\" (CPS), a convenient intermediate form that makes control-flow explicit. After CPS conversion, procedures take an extra argument called a continuation (another procedure) that represents the next logical execution point after execution of the procedure body. Thus procedures do not \"return,\" but rather \"continue into\" the code represented by the continuation. This permits, for example, a general but simple way to optimize tail-recursions into loops." "Steele's seminal work on Rabbit demonstrated the general benefits of this approach to compiler design. However, his work was primarily research oriented, and Rabbit was essentially a prototype compiler (consider, for example, that it generated MACLISP code). TC, on the other hand, was one of the first practical compilers for a Scheme dialect, and much was learned through its design and construction.\" Orbit now represents a culmination of that learning process, in which CPS conversion has been implemented thoroughly, extended in critical ways, and set in a framework of other important compiler innovations to yield a practical compiler that generates production-quality code competitive with the best compilers for Lisp as well as non-Lisp languages.")

;; Also: YALEU/DCS/TR632
(id kranz1988orbit)
(type phdthesis)
(title "Orbit: An Optimizing Compiler for Scheme")
(author "Kranz, David")
(year 1988)
(month 6)
(school "Department of Computer Science, Yale University")
(pdf-sha1 "514a5c2deb540cebeb879d396ab027aca9b2731c")
(pdf "https://cpsc.yale.edu/sites/default/files/files/tr632.pdf")
(abstract "It has often been assumed that the performance of languages with rst-class procedures is necessarily inferior to that of more traditional languages. Both experience and benchmarks appear to support this assumption. This work shows that the performance penalty is only a result of applying conventional compiler technologies to the compilation of higher order languages. These technologies do not adapt well to the situation in which closures of unlimited extent can be created dynamically." "The ORBIT compiler is based on a continuation-passing model instead of the traditional procedure call/return. The problem of reducing heap storage is solved using new algorithms for closure analysis, allowing many objects to be allocated on a stack or, better still, in machine registers. Closure packing and hoisting allow more than one procedure to share an environment without introducing indirection. Move instructions and memory references are reduced by passing arguments in registers and using a dynamic register allocation strategy. Register allocation and code generation are accomplished at the same time, with environment pointers being treated as variables. Environment pointers are kept in a lazy display, being brought into registers and cached when needed. The interaction of this strategy with the closure analysis also allows many optimizations based on type information to be performed." "Benchmarks are presented to show that, using these new techniques, the performance of programs written in higher order languages almost equals that of programs written in Pascal in both space and time. Thus the greater expressive power of higher order languages and debugging ease of traditional LISP systems need not be sacri ced to attain good performance.")

(id feeley1986deux)
(type mastersthesis)
(title "Deux approches à l'implantation du langage Scheme")
(author "Feeley, Marc")
(year 1986)
(school "Université de Montréal")
(pdf-sha1 "22e0485c3cbda78fef823ca52d30821b296173ed")
(pdf "https://www-labs.iro.umontreal.ca/~feeley/papers/FeeleyMSc.pdf")
(ps "http://www.iro.umontreal.ca/~feeley/papers/msc.ps.gz")
(abstract "Le langage Scheme est un dialecte de Lisp simple et homogène qui gagne de la popularité. Ce mémoire porte sur l'implantation efficace de deux aspects importants d'un système Scheme, c'est-à-dire les fermetures et la génération de code. Pour chacun de ces aspects, nous proposons une nouvelle approche d'implantation et la comparons à d'autres méthodes connues." "Notre approche d'implantation de fermetures est fondée sur le principe de β-conversion du λ-calcul. Nous raffinons une méthode simple basée sur cette dernière ce qui nous amène à concevoir les fermetures comme étant un bout de code. Les avantages de cette approche sont discutés et, à l'aide d'une batterie de tests, nous en analysons la performance. Les résultats obtenus indiquent que dans plusieurs situations notre approche est supérieure à l'approche classique." "Nous montrons qu'il est possible d'utiliser les fermetures pour représenter le code généré par un compilateur. Cette approche permet d'écrire un compilateur Scheme totalement en Scheme et de remplacer avantageusement les interpréteurs. De plus, cette approche peut être étendue à d'autres langages tel que les langages orienté-objet. L'intégration de cette approche dans un compilateur optimisant nous a permis d'en mesurer l'efficacité par rapport à d'autres méthodes d'évaluation." "L'implantation d'un système Scheme combinant nos deux approches a été réalisée. À l'aide de tests comparant celui-ci à d'autres systèmes couramment disponibles sur le marché, nous montrons la viabilité d'un système basé sur nos deux approches.")

(id dybvig1987three)
(type phdthesis)
(title "Three implementation models for Scheme")
(author "Dybvig, R Kent")
(year 1987)
(school "University of North Carolina at Chapel Hill")
(pdf-sha1 "bc896e5336120b0f4ad00feb500cd7ce70134836")
(pdf "https://mazdaywik.github.io/direct-link/dybvig-disser.pdf")
(pdf "https://legacy.cs.indiana.edu/~dyb/papers/3imp.pdf")
(abstract "This dissertation presents three implementation models for the Scheme Programming Language. The first is a heap-based model used in some form in most Scheme implementations to date; the second is a new stack-based model that is considerably more efficient than the heap-based model at executing most programs; and the third is a new string-based model intended for use in a multiple-processor implementation of Scheme. The heap-based model allocates several important data structures in a heap, including actual parameter lists, binding environments, and call frames. The stack-based model allocates these same structures on a stack whenever possible. This results in less heap allocation, fewer memory references, shorter instruction sequences, less garbage collection, and more efficient use of memory. The string-based model allocates versions of these structures right in the program text, which is represented as a string of symbols. In the string-based model, Scheme programs are translated into an FFP language designed specifically to support Scheme. Programs in this language are directly executed by the FFP machine, a multiple-processor string-reduction computer. The stack-based model is of immediate practical benefit; it is the model used by the author's Chez Scheme system, a high-performance implementation of Scheme. The string-based model will be useful for providing Scheme as a high-level alternative to FFP on the FFP machine once the machine is realized.")

(id clinger1984scheme)
(type inproceedings)
(title "The Scheme 311 compiler: an exercise in denotational semantics")
(author "Clinger, William")
(booktitle "Proceedings of the 1984 ACM Symposium on LISP and functional programming")
(pages "356--364")
(year 1984)
(pdf-sha1 "e3daa2373e23694144fae2f8ec99b2bd503abfcb")
(abstract "Many authors have offered much good advice on structuring compilers and proving them correct [3, 12, 13, 27, 28]. The correctness proof described here demonstrates that their advice can be applied to a useful compiler for a real programming language. This paper describes and proves the correctness of a simple compiler algorithm for Scheme, a statically scoped dialect of Lisp. The algorithm has been used as the basis for an interactive compiler generating interpreted byte code in an implementation comparable to those available for Pascal, Smalltalk, and Basic [1, 7, 9]." "Most of the correctness proof consists of trivial calculations. This is possible because the meanings of target code instructions are expressed in the same language used to express source meanings, and that language can be wielded as a calculus. The proof is complicated by what amounts to a static type distinction needed to compile primitive operators in line. Previous compiler correctness proofs using static type information (eg [179 have assumed that separate presentations of static and dynamic semantics are available a priori, but the proof in this paper works from a single standard semantics." "The proof is similar in spirit to that of, though the algorithm was designed and a compiler built before any thought was given to a formal correctness proof. The algorithm is superior to that in in that it directly produces linear and properly tail-recursive object code of reasonable quality.")

(id bartley1986implementation)
(type inproceedings)
(title "The implementation of PC Scheme")
(author "Bartley, David H")
(author "Jensen, John C")
(booktitle "Proceedings of the 1986 ACM conference on LISP and functional programming")
(pages "86--93")
(year 1986)
(pdf-sha1 "d68ebbed3f12e295e18f39dad48cf53afbd6ef40")
(abstract "PC Scheme is a compiler-based implementation of Scheme for PC-class machines. The compiler generates code for an idealized virtual machine which is emulated with threaded code techniques. The design has traded off the requirements of space sad speed effectively, resulting in one of the fastest PC-class LISP systems known to the authors.")

(id serrano2000vers)
(type phdthesis)
(title "Vers une programmation fonctionnelle praticable")
(author "Serrano, Manuel")
(year 2000)
(month 9)
(school "Université de Nice Sophia-Antipolis")
(pdf-sha1 "acf4864d29801d22720bdda8b800e9f1c5187bc2")
(ps-sha1 "6aed4169480c4fbe385d5e4fc0483ea1c4cc0653")
(ps "https://www-sop.inria.fr/members/Manuel.Serrano/publi/serrano-hdr00.ps.gz")
(abstract "A programmation est une activité terriblement difficile. Elle est tellement complexe et laborieuse qu'on finit méme par accepter la piétre qualité de la plupart des réalisations informatiques. L'industrie du logiciel est la seule (avec peut-étre les compagnies on aériennes qui sont incapables de respecter les horaires des avions) qui soit parvenue a établir le commerce de produits aussi instables et hasardeux que sont la plupart des logiciels actuels. Personne ne sait trés bien ce que les dits logiciels font ; les éditeurs informatiques se dé- gageant, pour leur part, de toute responsabilité en cas de dysfonctionnement. La notion méme de garantie est inopérante car personne n'aurait |'« audace» de spécifier ce qu'un logiciel est supposé faire. Les déficiences de l'informatique ont des impacts de plus en plus nombreux dans notre vie quotidienne a tel point que méme les journaux d'informations générales les relatent. Ainsi, dans le quotidien Le Monde, daté du Dimanche 26/Lundi 27 Décembre 1999, on a pu lire")

(id serrano1995bigloo)
(type inproceedings)
(title "Bigloo: a portable and optimizing compiler for strict functional languages")
(author "Serrano, Manuel")
(author "Weis, Pierre")
(booktitle "International Static Analysis Symposium")
(pages "366--381")
(year 1995)
(month 9)
(organization "Springer")
(pdf-sha1 "e9f6988ba5a9cc8f6cd9a9437968580215981eeb")
(pdf "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.50.8424&rep=rep1&type=pdf")
(ps "https://www-sop.inria.fr/members/Manuel.Serrano/publi/sw-sas95.ps.gz")
(abstract "We present Bigloo, a highly portable and optimizing compiler. Bigloo is the rst compiler for strict functional languages that can efficiently compile several languages: Bigloo is the rst compiler for full Scheme and full ML, and for these two languages, Bigloo is one of the most efficient compiler now available (Bigloo is available by anonymous ftp on ftp.inria.fr [192.93.2.54])." "This high level of performance is achieved by numerous high-level optimizations. Some of those are classical optimizations adapted to higherorder functional languages (e.g. inlining), other optimization schemes are speci c to Bigloo (e.g. a new re ned closure analysis, an original optimization of imperative variables, and intensive use of higher-order control ow analysis). All these optimizations share the same design guideline: the reduction of heap allocation.")

(id rees1995security)
(type phdthesis)
(title "A security kernel based on the lambda-calculus")
(author "Rees, Jonathan A")
(year 1995)
(school "Massachusetts Institute of Technology")
(pdf-sha1 "93c25e5faa0bb20c56202dc135c20c621e313187")
(pdf "https://dspace.mit.edu/bitstream/handle/1721.1/36956/32890570-MIT.pdf;sequence=2")
(ps "https://groups.csail.mit.edu/mac/ftpdir/users/jar/archive/whole.ps")
(abstract "Cooperation between independent agents depends upon establishing a degree of security. Each of the cooperating agents needs assurance that the cooperation will not endanger resources of value to that agent. In a computer system, a computational mechanism can assure safe cooperation among the system's users by mediating resource access according to desired security policy. Such a mechanism, which is called a security kernel, lies at the heart of many operating systems and programming environments." "The dissertation describes Scheme 48, a programming environment whose design is guided by established principles of operating system security. Scheme 48's security kernel is small, consisting of the call-by-value A-calculus with a few simple extensions to support abstract data types, object mutation, and access to hardware resources. Each agent (user or subsystem) has a separate evaluation environment that holds objects representing privileges granted to that agent. Because environments ultimately determine availability of object references, protection and sharing can be controlled largely by the way in which environments are constructed." "I will describe experience with Scheme 48 that shows how it serves as a robust and flexible experimental platform. Two successful applications of Scheme 48 are the programming environment for the Cornell mobile robots, where Scheme 48 runs with no (other) operating system support; and a secure multi-user environment that runs on workstations.")

(id kelsey1994tractable)
(type article)
(title "A tractable Scheme implementation")
(author "Kelsey, Richard A")
(author "Rees, Jonathan A")
(journal "Lisp and Symbolic Computation")
(volume "7")
(number "4")
(pages "315--335")
(year 1994)
(publisher "Springer")
(scheme-id scheme48)
(pdf-sha1 "3acd9fb69ef052223814ba75dcb6b1308e576be2")
(pdf "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.459.8113&rep=rep1&type=pdf")
(abstract "Scheme 48 is an implementation of the Scheme programming language constructed with tractability and reliability as its primary design goals. It has the structural properties of large, compiler-based Lisp implementations: it is written entirely in Scheme, is bootstrapped via its compiler, and provides numerous language extensions. It controls the complexity that ordinarily attends such large Lisp implementations through clear articulation of internal modularity and by the exclusion of features, optimizations, and generalizations that are of only marginal value.")

(id clinger1994lambda)
(type article)
(title "Lambda, the ultimate label or a simple optimizing compiler for Scheme")
(author "Clinger, William D")
(author "Hansen, Lars Thomas")
(journal "ACM SIGPLAN Lisp Pointers")
(volume "7")
(number "3")
(pages "128--139")
(year 1994)
(publisher "ACM New York, NY, USA")
(pdf-sha1 "1ddcec59325b6932e7d5d6a9facf2451bf0d4d76")
(abstract "Optimizing compilers for higher-order languages need not be terribly complex. The problems created bv non-local, non-global variables can be eliminated by allocating all such variables in the heap. Lambda lifting makes this practical by eliminating all non-local variables except for those that would have to be allocated in the heap anyway. The eliminated non-local variables become local variables that can be allocated in registers. Since calls to known procedures are just gotos that pass arguments, lifted lambda expressions are just assembly language labels that have been augmented by a list of symbolic names for the registers that are live at that label.")

(id clinger1988implementation)
(type inproceedings)
(title "Implementation strategies for continuations")
(author "Clinger, Will")
(author "Hartheimer, Anne")
(author "Ost, Eric")
(booktitle "Proceedings of the 1988 ACM conference on LISP and functional programming")
(pages "124--131")
(year 1988)
(month 7)
(pdf-sha1 "d995e99d9179e671f6543ef2f22f4743718a1955")
(abstract "Scheme and Smalltalk continuations may have unlimited extent. This means that a purely stack-based implementation of continuations, as suffices for most languages, is inadequate. Several implementation strategies have been described in the literature. Determining which is best requires knowledge of the kinds of programs that will commonly be run." "Danvy, for example, has conjectured that continuation captures occur in clusters. That is, the same continuation, once captured, is likely to be captured again. As evidence, Danvy cited the use of continuations in a research setting. We report that Danvy's conjecture is somewhat true in the commercial setting of MacScheme+Toolsmith, which provides tools for developing Macintosh user interfaces in Scheme. These include an interrupt-driven event system and multitasking, both implemented by liberal use of continuations." "We describe several implementation strategies for continuations and compare four of them using benchmarks. We conclude that the most popular strategy may have a slight edge when continuations are not used at all, but that other strategies perform better when continuations are used and Danvy's conjecture holds.")

(id clinger2006rapid)
(type inproceedings)
(title "Rapid Case Dispatch in Scheme")
(author "Clinger, William D")
(booktitle "2006 Workshop on Scheme and Functional Programming")
(year 2006)
(month 9)
(pdf-sha1 "69e43684e7d12cbf368fcea9f28330c6c426699c")
(pdf "https://www.ccs.neu.edu/home/will/Research/SW2006/casedispatch.pdf")
(abstract "The case expressions of Scheme can and should be implemented efficiently. A three-level dispatch performs well, even when dispatching on symbols, and scales to large case expressions.")

(id bruggeman1996representing)
(type inproceedings)
(title "Representing control in the presence of one-shot continuations")
(author "Bruggeman, Carl")
(author "Waddell, Oscar")
(author "Dybvig, R Kent")
(booktitle "Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation")
(pages "99--107")
(year 1996)
(month 6)
(pdf-sha1 "573a255da8c25555f231863717d20f3a91825649")
(ps-sha1 "b254497626a05ea27e186b22a8c59031258227de")
(ps "https://legacy.cs.indiana.edu/~dyb/papers/Call-1cc-PLDI96.ps.gz")
(abstract "Traditional first-class continuation mechanisms allow a captured continuation to be invoked multiple times. Many continuations, however, are invoked only once. This paper introduces one-shot continuations, shows how they interact with traditional multi-shot continuations, and describes a stack-based implementation of control that handles both one-shot and multi-shot continuations. The implementation eliminates the copying overhead for one-shot continuations that is inherent in multi-shot continuations.")

(id hilsdale1995compiler)
(type inproceedings)
(title "Compiler construction using scheme")
(author "Hilsdale, Erik")
(author "Ashley, J Michael")
(author "Dybvig, R Kent")
(author "Friedman, Daniel P")
(booktitle "International Symposium on Functional Programming Languages in Education")
(pages "251--267")
(year 1995)
(organization "Springer")
(pdf-sha1 "857a8441c017c3f1ce678506e003397e8e3d09a1")
(pdf-sha1 "068ceb1e9066fe36f336b815c0cb4cceac48d3f4")
(pdf "https://legacy.cs.indiana.edu/~dyb/pubs/fple95.pdf")
(pdf "https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.8685&rep=rep1&type=pdf")
(abstract "This paper describes a course in compiler design that focuses on the Scheme implementation of a Scheme compiler that generates native assembly code for a real architecture. The course is suitable for advanced undergraduate and beginning graduate students. It is intended both to provide a general knowledge about compiler design and implementation and to serve as a springboard to more advanced courses. Although this paper concentrates on the implementation of a compiler, an outline for an advanced topics course that builds upon the compiler is also presented.")

(id ashley1994efficient)
(type inproceedings)
(title "An efficient implementation of multiple return values in Scheme")
(author "Ashley, J Michael")
(author "Dybvig, R Kent")
(booktitle "Proceedings of the 1994 ACM Conference on LISP and Functional Programming")
(pages "140--149")
(year 1994)
(month 6)
(pdf-sha1 "bf54700a2b96de14a2a86411f8d20969f423f25c")
(abstract "This paper describes an implementation of the new Scheme multiple values interface. The implementation handles multiple values efficiently, with no run-time overhead for normal calls and returns. Error checks are performed where necessary to insure that the expected number of values is returned in all situations. The implementation fits cleanly with our direct-style compiler and stack-based representation of control, but is equally well suited to continuation-passing style compilers and to heap-based run-time architectures.")

(id hieb1990representing)
(type article)
(title "Representing control in the presence of first-class continuations")
(author "Hieb, Robert")
(author "Dybvig, R Kent")
(author "Bruggeman, Carl")
(journal "ACM SIGPLAN Notices")
(volume "25")
(number "6")
(pages "66--77")
(year 1990)
(month 6)
(publisher "ACM New York, NY, USA")
(pdf-sha1 "8e24b81541ab6310e6882d57dfd3f26fdbe3e204")
(ps-sha1 "b1ed86fef928546f79ee1bf3c297db986757783b")
(ps "https://legacy.cs.indiana.edu/~dyb/papers/stack.ps")
(abstract "Languages such as Scheme and Smalltalk that provide continuations as first-class data objects present a challenge to efficient implementation. Allocating activation records in a heap has proven unsatisfactory because of increased frame linkage costs, increased garbage collection overhead, and decreased locality of reference. However, simply allocating activation records on a stack and copying them when a continuation is created results in unbounded copying overhead. This paper describes a new approach based on stack allocation that does not require the stack to be copied when a continuation is created and that allows us to place a small upper bound on the amount copied when a continuation is reinstated. This new approach is faster than the naive stack allocation approach, and it does not suffer from the problems associated with unbounded copying. For continuationintensive programs, our approach is at worst a constant factor slower than the heap allocation approach, and for typical programs, it is significantly faster. An important additional benefit is that recovery from stack overflow is handled gracefully and efficiently.")

(id flanagan1993essence)
(type inproceedings)
(title "The essence of compiling with continuations")
(author "Flanagan, Cormac")
(author "Sabry, Amr")
(author "Duba, Bruce F")
(author "Felleisen, Matthias")
(booktitle "Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation")
(pages "237--247")
(year 1993)
(pdf-sha1 "227d2f191ca8b87aae66497a9015448ce64d7312")
(ps-sha1 "222729baf3f0e29ba31186f67bf8d198a7c1e742")
(ps "https://www.ccs.neu.edu/scheme/pubs/pldi93-fsdf.ps.gz")
(abstract "In order to simplify the compilation process, many compilers for higher-order languages use the continuation-passing style (CPS) transformation in a first phase to generate an intermediate representation of the source program. The salient aspect of this intermediate form is that all procedures take an argument that represents the rest of the computation (the \"continuation\"). Since the naive CPS transformation considerably increases the size of programs, CPS compilers perform reductions to produce a more compact intermediate representation. Although often implemented as a part of the CPS transformation, this step is conceptually a second phase. Finally, code generators for typical CPS compilers treat continuations specially in order to optimize the interpretation of continuation parameters." "A thorough analysis of the abstract machine for CPS terms shows that the actions of the code generator invert the naive CPS translation step. Put differently, the combined effect of the three phases is equivalent to a source-to-source transformation that simulates the compaction phase. Thus, fully developed CPS compilers do not need to employ the CPS transformation but can achieve the same results with a simple source-level transformation.")

(id sabry1995formal)
(type phdthesis)
(title "The formal relationship between direct and continuation-passing style optimizing compilers: a synthesis of two paradigms")
(author "Sabry, Amr Afaf")
(year 1995)
(school "Rice University")
(pdf-sha1 "161933785d6ad0d040f8e18beef829624cd72cf9")
(ps-sha1 "48b300524261740d870d6d292b23557b734a1737")
(pdf "https://scholarship.rice.edu/bitstream/handle/1911/16878/9610702.PDF?sequence=1")
(ps "https://www.ccs.neu.edu/scheme/pubs/thesis-sabry.ps.gz")
(abstract "Compilers for higher-order programming languages like Scheme, ML, and Lisp can be broadly characterized as either \"direct compilers\" or \"continuation-passing style (CPS) compilers\", depending on their main intermediate representation. Our central result is a precise correspondence between the two compilation strategies." "Starting from the theoretical foundations of direct and CPS compilers, we develop relationships between the main components of each compilation strategy: generation of the intermediate representation, simplification of the intermediate representation, code generation, and data flow analysis. For each component, our results pinpoint the superior compilation strategy, the reason for which it dominates the other strategy, and ways to improve the inferior strategy. Furthermore, our work suggests a synthesis of the direct and CPS compilation strategies that combines the best aspects of each." "The contributions of this thesis include a comprehensive analysis of the properties of the CPS iniermediate representation, a new optimal CPS transformation and its inverse, a new intermediate representation for direct compilers, an equivalence between the canonical equational theories for reasoning about continuations and general computational effects, a sound and complete equational axiomatization of the semantics of call-by-value control operators, a methodology for deriving equational logics for imperative languages, and formal relationships between code generators and data flow analyzers for direct and CPS compilers. These contributions unify concepts in two distinct compilation strategies, and can be used to compare specific compilers.")

(id queinnec1993continuation)
(type article)
(title "Continuation conscious compilation")
(author "Queinnec, Christian")
(journal "ACM SIGPLAN Lisp Pointers")
(volume "6")
(number "1")
(pages "2--14")
(year 1993)
(month 1)
(publisher "ACM New York, NY, USA")
(pdf-sha1 "40de0e38059b23aec4f68345f386ebd1992dbf72")
(pdf-sha1 "be66e6574ed18e5f8d014dc422c6e43aa8a236ac")
(pdf "https://christian.queinnec.org/PDF/ccc.pdf")
(pdf "https://pages.lip6.fr/Christian.Queinnec/PDF/ccc.pdf")
(abstract "This paper proposes some (unimplemented) ideas for the compilation of Scheme-like languages where functions may be specialized with respect to some of the continuations with which they are invoked. This allows for some optimizations, for instance, when a frame to be pushed and the frame on top of the continuation can be combined into a single and simplified frame. Among possible improvements are: intermediate data structure elimination and removal of useless calculations. Functions can therefore be compiled with respect to their near future and reorganize it when appropriate." "The compilation technique is based on a program transformation named Abstract Continuation Passing Style that makes continuation (i.e. stack) frames explicit. Shape of continuations is approximated to determine which frames would gain by being combined together then partial evaluation is used to determine the behavior of combined frames. Our main results cover local deforestation-like effect as well as iterative compilation of associatively wrapped recursions converting, for example, a recursive unary factorial into an iterative binary one.")

(id queinnec1992continuation)
(type techreport)
(title "Continuation sensitive compilation")
(author "Queinnec, Christian")
(year 1992)
(month 11)
(institution "Research Report LIX RR 92/14, Laboratoire d'Informatique de l'Ecole~...")
(pdf-sha1 "8d9998d8bac52074fe47d29310340980ce9baf32")
(pdf "https://pages.lip6.fr/Christian.Queinnec/PDF/csc.pdf")
(pdf "https://christian.queinnec.org/PDF/csc.pdf")
(abstract "This paper presents a compilation technique for Scheme-like languages where functions may look at their continuation before pushing frames onto it. This allows for some optimizations when the frame to be pushed and the frame on top of the continuation can be combined into a single and simplified frame. Among possible simplifications are: intermediate data structure elimination and removal of redundant calculations. Functions can therefore be compiled with respect to their near future and reorganize it when appropriate." "The compilation technique is based on an improved CPS-like transformation that makes continuation (i.e. stack) frames explicit. Shape of continuations is approximated to determine which frames would gain by being combined together then partial evaluation is used to determine the behavior of combined frames. Our main results cover local deforestation-like effect as well as iterative compilation of associatively wrapped recursions.")

(id thiemann1999higher)
(type inproceedings)
(title "Higher-order code splicing")
(author "Thiemann, Peter")
(booktitle "European Symposium on Programming")
(pages "243--257")
(year 1999)
(month 3)
(organization "Springer")
(pdf-sha1 "84c9be0fb04f75c1c240c5a5f21a3b49b486d18c")
(ps-sha1 "28937d21f4b2249cac4563462e5d00d24ec526a5")
(pdf "https://link.springer.com/content/pdf/10.1007/3-540-49099-X_16.pdf")
(ps "http://www.informatik.uni-freiburg.de/~thiemann/papers/esop99.ps.gz")
(abstract "Run-time code generation (RTCG) and just-in-time compilation (JIT) are features of modern programming systems to strike the balance between generality and efficiency. Since RTCG and JIT techniques are not portable and notoriously hard to implement, we propose code splicing as an alternative for dynamically-typed higher-order programming languages. Code splicing combines precompiled pieces of code using higher-order functions. While this approach cannot achieve the performance of compiled code, it can support some intriguing features:" "– very fast \"compilation\" times;" "– satisfactory run times, compared with interpretation;" "– simple interfacing with compiled code;" "– portability." "Starting from implementation models for functional languages we develop and evaluate several approaches to code splicing. This leads to some new insights into compilation techniques for functional programming languages, among them a compositional compilation schema to SKI-combinators. The progression of different techniques sheds some light on their relationship, specifically between combinator-based implementations and closure-based implementations." "All techniques have been implemented and evaluated in Scheme.")

(id steele1977debunking)
(type inproceedings)
(title "Debunking the \"expensive procedure call\" myth or, procedure call implementations considered harmful or, LAMBDA: The Ultimate GOTO")
(author "Steele Jr, Guy Lewis")
(booktitle "Proceedings of the 1977 annual ACM conference")
(pages "153--162")
(year 1977)
(pdf-sha1 "bdc7b4eda3995fe20320ddde753b3630612b05c5")
(abstract "Folklore states that GOTO statements are \"cheap\", while procedure calls are \"expensive\". This myth is largely a result of poorly designed language implementations. The historical growth of this myth is considered. Both theoretical ideas and an existing implementation are discussed which debunk this myth. It is shown that the unrestricted use of procedure calls permits great stylistic freedom. In particular, any flowchart can be written as a \"structured\" program without introducing extra variables. The difficulty with the GOTO statement and the procedure call is characterized as a conflict between abstract programming concepts and concrete language constructs.")

;; S. B. Thesis.
(id rozas1984liar)
(type article)
(title "Liar, an Algol-like compiler for Scheme")
(author "Rozas, Guillermo J")
(school "Massachusetts Institute of Technology")
(year 1984)
(month 1)

;; MIT LCS Memo TM-267
(id schooler1984proposal)
(type techreport)
(title "Proposal for a Small Scheme Implementation")
(author "Schooler, Richard")
(author "Stamos, James W")
(year 1984)
(month 10)
(institution "Massachusetts Institute of Technology LCS")
(pdf-sha1 "661be241bd585d54c0ad1a81c47ea4257dac096e")
(pdf-sha1 "b5912b7fc31dc43b80adfa1a71c181d1fe101939")
(pdf "https://apps.dtic.mil/dtic/tr/fulltext/u2/a148707.pdf")
(pdf "http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TM-267.pdf")
(abstract "Scheme is a lexically scoped dialect of LISP developed at MIT. In this report we determine the feasibility of implementing a Scheme-based programming/application environment on a contemporary personal computer such as the Apple Macintosh. The absence of virtual memory, coupled with a limitation on the maximum amount of physical memory, means that space is at a premium. We suggest the use of bytecodes and sketch a possible instruction set." "Because of space constraints, tail-recursion optimization and an efficient mechanism for the reclamation of inaccessible contexts are also examined. Using the built-in operating system and user interface of the Macintosh realizes speed, functionality, and friendliness but raises a number of interesting issues. For example, the Pascal! and assembler routines make many assumptions about data representation, type checking, and parameter passing. Since an implementation of Scheme is likely to have radically different conventions, the two environments must be interfaced smoothly and efficiently." "In addition to the bytecoded instruction set, we specify the virtual machine informally, discuss the implementation of basic and advanced features, estimate the performance of such an implementation, and finally evaluate the proposed design.")

(id wand1986interpreter)
(type incollection)
(title "From interpreter to compiler: a representational derivation")
(author "Wand, Mitchell")
(booktitle "Programs as Data Objects")
(pages "306--324")
(year 1986)
(publisher "Springer")

(id wand1978compiling)
(type article)
(title "Compiling lambda-expressions using continuations and factorizations")
(author "Wand, Mitchell")
(author "Friedman, Daniel P")
(journal "Computer Languages")
(volume "3")
(number "4")
(pages "241--263")
(year 1978)
(publisher "Pergamon Press, Inc.")

(id steele1980compiler)
(type misc)
(title "Compiler optimization based on viewing LAMBDA as RENAME + GOTO")
(author "Steele Jr, Guy Lewis")
(year 1980)
(book "Artificial Intelligence: An MIT Perspective")
(publisher "MIT Press")

(id steele1980dream)
(type inproceedings)
(title "The dream of a lifetime: A lazy variable extent mechanism")
(author "Steele Jr, Guy Lewis")
(author "Sussman, Gerald Jay")
(booktitle "Proceedings of the 1980 ACM conference on LISP and functional programming")
(pages "163--172")
(year 1980)
(pdf-sha1 "31de1ed42e183a99d6645e316cfb0cd716364f0b")
(pdf-sha1 "3cb34b298d5aba1f5fd07a6a4adbc9b024ffa0a3")
(abstract "We define a \"rack\", a data abstraction hybrid of a register and a stack. It is used for encapsulating the behavior of the kind of register whose contents may have an extent which requires that it be saved during the execution of an unknown piece of code. A rack can be implemented cleverly to achieve performance benefits over the usual implementation of a stack discipline. The basic idea is that we interpose a state machine controller between the rack abstraction and its stack/registers. This controller can act as an on-the-fly run-time peephole optimizer, eliding unnecessary stack operations." "We demonstrate the sorts of savings one might expect by using cleverly implemented racks in the context of a particular caller-saves implementation of an interpreter for the SCHEME dialect of LISP. For sample problems we can expect that only one out of every four pushes that would be done by a conventional machine will be done by the clever version.")

(id mcdermott1980efficient)
(type inproceedings)
(title "An efficient environment allocation scheme in an interpreter for a lexically-scoped LISP")
(author "McDermott, Drew")
(booktitle "Proceedings of the 1980 ACM conference on LISP and functional programming")
(pages "154--162")
(year 1980)
(pdf-sha1 "bab51c0c347c304ce902dd3478366a0300d21e45")
(abstract "Lexically-scoped LISP dialects offer great flexibility and expressive power. Unfortunately, they tend to be inefficiently implemented, because many interpreter structures such as variable binding environments must be allocated in the heap rather than on the stack. One solution to this problem is to allocate them on the stack, then move them to the heap if necessary. This means moving the environment of a function only if it passes an environment pointer to the last function it calls, returns an environment pointer as a value, sets a global variable to one, or CONSes one into a list structures. To make this work, the interpreter must be able to tell which current environments a function call is the last function call of, and must know exactly what parts of the stack can be moved. This approach saves dramatically on garbage collections, at the price of increasing function application time a bit. It is worth doing if free storage is not abundant, or if it is important to avoid garbage collections.")

(id vegdahl1989runtime)
(type article)
(title "The runtime environment for Scheme, a Scheme implementation on the 88000")
(author "Vegdahl, Steven R")
(author "Pleban, Uwe F")
(journal "ACM SIGARCH Computer Architecture News")
(volume "17")
(number "2")
(pages "172--182")
(year 1989)
(month 4)
(publisher "ACM New York, NY, USA")
(pdf-sha1 "88cd472a48afba3c8e0e639646491dc01d1c376a")
(abstract "We are implementing a Scheme development system for the Motorola 88000. The core of the implementation is an optimizing native code compiler, together with a carefully designed runtime system. This paper describes our experiences with the 88000 as a target architecture. We focus on the design decisions concerning the runtime system, particularly with respect to data type representations, tag checking, procedure calling protocol, generic arithmetic, and the handling of continuations. We also discuss rejected design alternatives, and evaluate the strengths and weaknesses of the instruction set with respect to our constraints.")

(id pearlmutter1991implementation)
(type misc)
(title "The implementation of Oaklisp")
(author "Pearlmutter, Barak A")
(author "Lang, Kevin J")
(journal "Topics in Advanced Language Implementation")
(pages "189--215")
(year 1991)
(publisher "MIT Press")
(pdf "http://www.bcl.hamilton.ie/~barak/papers/Oaklisp-TALI-Chapter-1991.pdf")
(pdf-sha1 "a92f23d93bf58b7c3300469125dceabde435ac60")

(id pleban1991compilation)
(type article)
(title "Compilation Issues in the Screme Implementation for the 88000")
(author "Pleban, Uwe F.")
(journal "Topics in Advanced Language Implementation")
(pages "157--188")
(year 1991)
(publisher "MIT Press Cambridge, MA")

(id teodosiu1991hare)
(type article)
(title "HARE: An optimizing portable compiler for Scheme")
(author "Teodosiu, Dan")
(journal "ACM SIGPLAN Notices")
(volume "26")
(number "1")
(pages "109--120")
(year 1991)
(month 1)
(publisher "ACM New York, NY, USA")
(pdf-sha1 "67a9b5106ef0967ff4352cab37ec559f26b708f6")
(pdf "https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55.6693&rep=rep1&type=pdf")
(abstract "The paper presents the design of a highly optimizing Scheme compiler called HARE. A combination of several optimization techniques allows the generation of very efficient code. Easy portability of the compiler has been achieved through the use of a virtual machine as a target for code generation.")

;; Nitsan Seniak. "Compilation de Scheme par specialisation explicite". _BIGRE Bulletin_. 65. July 1989.

(id hanson1990efficient)
(type inproceedings)
(title "Efficient Stack Allocation for Tail-Recursive Languages")
(author "Hanson, Chris")
(booktitle "Proceedings of the 1990 ACM conference on LISP and functional programming")
(pages "106--118")
(year 1990)
(month 6)
(pdf-sha1 "d08ee33852d0372d9563794f798e59402adaa6f7")
(pdf "https://www.cs.purdue.edu/homes/suresh/502-Fall2008/papers/tail-recursion.pdf")
(abstract "The Scheme dialect of Lisp is properly tail-recursive --- it relies entirely on procedure calls to express iteration. In Scheme, a tail-recursive procedure call (that is, a call in which the calling procedure does not do any further processing of the returned value) is essentially a goto that passes arguments, as was first pointed out by Steele. In a properly tail-recursive language, there is no need for any explicit iteration constructs such as do or while; these can all be defined in terms of ordinary procedure calls." "As elegant as tail-recursion may be from the perspective of the programmer or the theoretician, it poses challenges for the compiler designer. One of the crucial decisions in the design of a compiler is the formation of a strategy for memory allocation and deallocation. An important aspect of this strategy is the treatment of memory locations used to hold the bindings of local variables. Because local variables play a significant role in most computer languages, their treatment can have a noticeable impact on a program's execution speed and run-time space requirements. Compilers for many block-structured languages use a simple strategy when allocating local variables: stack allocation. This strategy is supported by hardware on many computers, and by software mechanisms such as the access link and the display. However, the standard methods for implementing stack allocation assume that the language is not tail-recursive, and a straightforward application of these methods to a tail-recursive language can result in non-tail-recursive compiled code." "This paper describes stack-allocation techniques for compiling tail-recursive languages. We do not claim that these are the only techniques that can be used to solve the problem, nor do we compare them to other techniques. Instead, we use our techniques as a concrete example to demonstrate that it is possible to implement stack allocation of local variables without sacrificing tail recursion, which to our knowledge has not previously been shown.")

;; Dan Teodosiu. "HARE: A Compiler for Scheme". Masters Thesis. Master's Thesis. June 1990.
;; Also in International Conference on Functional Programming (ICFP'2002)

(id gasbichler2002final)
(type article)
(title "Final shift for call/cc: direct implementation of shift and reset")
(author "Gasbichler, Martin")
(author "Sperber, Michael")
(journal "ACM SIGPLAN Notices")
(volume "37")
(number "9")
(pages "271--282")
(year 2002)
(publisher "ACM New York, NY, USA")
(pdf-sha1 "11fd1a726ec27a1c523166975b30d3228cec1258")
(pdf "https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11.3425&rep=rep1&type=pdf")
(abstract "We present a direct implementation of the shift and reset control operators in the Scheme 48 system. The new implementation improves upon the traditional technique of simulating shift and reset via call/cc. Typical applications of these operators exhibit space savings and a significant overall performance gain. Our technique is based upon the popular incremental stack/heap strategy for representing continuations. We present implementation details as well as some benchmark measurements for typical applications.")

;; Martin Gasbichler, Michael Sperber. "A Direct Implementation of Shift/Reset". _IFL 2001_. 2001.

;; Also presented at 2009 Workshop on Scheme and Functional Programming
(id ghuloum2009fixing)
(type article)
(title "Fixing letrec (reloaded)")
(author "Ghuloum, Abdulaziz")
(author "Dybvig, R Kent")
(journal "Technical Report CPSLO-CSC-09-03")
(pages "57")
(year 2009)
;; SHA of this paper only:
(pdf-sha1 "59356469b851e620bc88404ed45758be8f8d9546")
;; SHA of full proceedings PDF:
(pdf-sha1 "271c513ef5adef8ccf91da2fcf39a6d543af5555")
(pdf "http://schemeworkshop.org/2009/scheme2009.pdf#page=57")
(abstract "The Revised6 Report on Scheme introduces three fundamental changes involving Scheme's recursive variable binding constructs. First, it standardizes the sequential recursive binding construct, letrec*, which evaluates its initialization expressions in a strict leftto-right order. Second, it specifies that internal and library definitions have letrec* semantics. Third, it prohibits programs from invoking the continuation of a letrec or letrec* init expression more than once. The first two changes increase the incentive for handling letrec* efficiently, while the third change gives the compiler more options for transforming letrec and letrec* expressions." "This paper extends an earlier effort of Waddell, Sarkar, and Dybvig to handle the Revised5 Report letrec and the (then nonstandard) letrec* efficiently. It presents more aggressive transformations for letrec and letrec* that take advantage of the new prohibition on invoking the continuations of initialization expressions multiple times. The implementation employs Tarjan's algorithm for finding strongly connected components in a graph that encodes the dependencies among the bindings.")

(id ghuloum2006incremental)
(type inproceedings)
(title "An incremental approach to compiler construction")
(author "Ghuloum, Abdulaziz")
(booktitle "Proceedings of the 2006 Scheme and Functional Programming Workshop")
(year 2006)
(organization "Citeseer")
(pdf-sha1 "297dd192274fdebcbfec7a5b8a22154de9792311")
(pdf "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.170&rep=rep1&type=pdf")
(abstract "Compilers are perceived to be magical artifacts, carefully crafted by the wizards, and unfathomable by the mere mortals. Books on compilers are better described as wizard-talk: written by and for a clique of all-knowing practitioners. Real-life compilers are too complex to serve as an educational tool. And the gap between real-life compilers and the educational toy compilers is too wide. The novice compiler writer stands puzzled facing an impenetrable barrier, \"better write an interpreter instead.\"" "The goal of this paper is to break that barrier. We show that building a compiler can be as easy as building an interpreter. The compiler we construct accepts a large subset of the Scheme programming language and produces assembly code for the Intel-x86 architecture, the dominant architecture of personal computing. The development of the compiler is broken into many small incremental steps. Every step yields a fully working compiler for a progressively expanding subset of Scheme. Every compiler step produces real assembly code that can be assembled then executed directly by the hardware. We assume that the reader is familiar with the basic computer architecture: its components and execution model. Detailed knowledge of the Intel-x86 architecture is not required." "The development of the compiler is described in detail in an extended tutorial. Supporting material for the tutorial such as an automated testing facility coupled with a comprehensive test suite are provided with the tutorial. It is our hope that current and future implementors of Scheme find in this paper the motivation for developing high-performance compilers and the means for achieving that goal.")

;; Also presented at International Conference on Functional Programming 2004
(id sarkar2004nanopass)
(type article)
(title "A nanopass infrastructure for compiler education")
(author "Sarkar, Dipanwita")
(author "Waddell, Oscar")
(author "Dybvig, R Kent")
(journal "ACM SIGPLAN Notices")
(volume "39")
(number "9")
(pages "201--212")
(year 2004)
(publisher "ACM New York, NY, USA")
(pdf-sha1 "ef63ccac82166f1062b05c79c00e8930c191307a")
(pdf "https://guenchi.github.io/Scheme/doc/A%20Nanopass%20Framework%20for%20Compiler%20Education.pdf")
(abstract "A compiler structured as a small number of monolithic passes is difficult to understand and difficult to maintain. The steep learning curve is daunting, and even experienced developers find that modifying existing passes is difficult and often introduces subtle and tenacious bugs. These problems are especially frustrating when the developer is a student in a compiler class. An attractive alternative is to structure a compiler as a collection of many fine-grained passes, each of which performs a single task. This structure aligns the implementation of a compiler with its logical organization, simplifying development, testing, and debugging. This paper describes the methodology and tools comprising a framework for constructing such compilers.")

;; Also presented at _International Conference on Functional Programming, ICFP 2005_
(id pettyjohn2005continuations)
(type article)
(title "Continuations from generalized stack inspection")
(author "Pettyjohn, Greg")
(author "Clements, John")
(author "Marshall, Joe")
(author "Krishnamurthi, Shriram")
(author "Felleisen, Matthias")
(journal "ACM SIGPLAN Notices")
(volume "40")
(number "9")
(pages "216--227")
(year 2005)
(publisher "ACM New York, NY, USA")
(pdf-sha1 "2d764abd03633c63cf2b011165e24fb0f2d1444a")
(pdf-sha1 "6378b7d960465c09c49e7108143e0d88575352ff")
(pdf "http://cs.brown.edu/~sk/Publications/Papers/Published/pcmkf-cont-from-gen-stack-insp/paper.pdf")
(pdf "https://digitalcommons.calpoly.edu/cgi/viewcontent.cgi?article=1048&context=csse_fac")
(abstract "Implementing first-class continuations can pose a challenge if the target machine makes no provisions for accessing and re-installing the run-time stack. In this paper, we present a novel translation that overcomes this problem. In the first half of the paper, we introduce a theoretical model that shows how to eliminate the capture and the use of first-class continuations in the presence of a generalized stack inspection mechanism. The second half of the paper explains how to translate this model into practice in two different contexts. First, we reformulate the servlet interaction language in the PLT Web server, which heavily relies on first-class continuations. Using our technique, servlet programs can be run directly under the control of non-cooperative web servers such as Apache. Second, we show how to use our new technique to copy and reconstitute the stack on MSIL.Net using exception handlers. This establishes that Scheme's first-class continuations can exist on non-cooperative virtual machines.")

(id flatt2009keyword)
(type article)
(title "Keyword and optional arguments in PLT Scheme")
(author "Flatt, Matthew")
(author "Barzilay, Eli")
(journal "Proceedings of the 2009 Scheme and Functional Programming Workshop")
(pages "94--102")
(year 2009)
;; This paper only:
(pdf-sha1 "88714450b5b5b5724333ce1d1917feb50818ce0b")
;; Full proceedings:
(pdf "http://schemeworkshop.org/2009/scheme2009.pdf#page=94")
(abstract "The lambda and procedure-application forms in PLT Scheme support arguments that are tagged with keywords, instead of identified by position, as well as optional arguments with default values. Unlike previous keyword-argument systems for Scheme, a keyword is not self-quoting as an expression, and keyword arguments use a different calling convention than non-keyword arguments. Consequently, a keyword serves more reliably (e.g., in terms of error reporting) as a lightweight syntactic delimiter on procedure arguments. Our design requires no changes to the PLT Scheme core compiler, because lambda and application forms that support keywords are implemented by macros over conventional core forms that lack keyword support.")

(id ghuloum2007generation)
(type inproceedings)
(title "Generation-friendly eq hash tables")
(author "Ghuloum, Abdulaziz")
(author "Dybvig, R Kent")
(booktitle "2007 Workshop on Scheme and Functional Programming")
(pages "27--35")
(year 2007)
(organization "Citeseer")
(pdf-sha1 "326dbd886d8f532af40026c65c134967ec737f3a")
(pdf "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.308.8410&rep=rep1&type=pdf")
(abstract "Eq hash tables, which support arbitrary objects as keys, distinguish keys via pointer comparison and often employ hash functions that utilize the address of the object. When compacting garbage collectors move garbage collected objects, the addresses of such objects may change, thus invalidating the hash function computation. A common solution is to rehash all of the entries in an eq hash table on the first access to the table after a collection. For a simple stop-and-copy garbage collector, which moves every element of a hash table, the rehashing overhead is proportional to the amount of work done by the collector and so the cost of rehashing adds only constant overhead. Generational copying collectors, however, may move a few or none of the entries, so rehashing a large table may cost considerably more than the garbage collection run that caused the rehash. In other words, such rehashing is not \"generation friendly.\"" "In this paper, we describe an efficient, generation-friendly mechanism for implementing eq hash tables. The amount of work required for rehashing is proportional to the work performed by the collector as only objects that actually move during a collection are rehashed. The collector supports eq hash tables and their variants via a simple new type of object, a transport link cell, the handling of which by the collector is nearly trivial.")

(end-group)

(group "Implementing Scheme in Java, .NET, and JavaScript")

;; Presented at 2009 Workshop on Scheme and Functional Programming
(id basar9world)
(type article)
(title "World With Web: A compiler from world applications to JavaScript")
(author "Başar, R Emre")
(author "Derici, Caner")
(author "Şenol, Çağdaş")
(year 2009)
(journal "Technical Report CPSLO-CSC-09-03")
(pages "121")
(pdf-sha1 "fe60c3d5a407a53f25eddaf75a6170c0b214a25f")
(pdf "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.308.9976&rep=rep1&type=pdf")
(abstract "Our methods for interacting with computers have changed drastically over the last 10 years. As web based technologies improve, online applications are starting to replace their offline counterparts. In the world of online interaction, our educational tools also need to be adapted for this environment. This paper presents WorldWithWeb, a compiler and run-time libraries for mapping programs written in Beginning Student Language of PLT Scheme with World teachpack to JavaScript. This tool is intended to exploit the sharingenabled nature of the web to support the learning process of students. Although it is designed as an extension to DrScheme, it is also possible to use it in various settings to enable different methods of user interaction and collaboration.")

(id nagata2002scheme)
(type inproceedings)
(title "A Scheme-to-Java translator with soft typing")
(author "Nagata, Akihito")
(author "Sumii, Eijiro")
(author "Yonezawa, Akinori")
(booktitle "Poster at JSSST Workshop on Systems for Programming and Applications")
(year 2002)
(month 5)
(organization "Citeseer")
(ps-sha1 "f226a33ec9596836e625b4ceeaa5a2110b288bfa")
(ps "http://www.yl.is.s.u-tokyo.ac.jp/~sumii/pub/scm2java.ps.gz")
(pdf-sha1 "17c7c17ca1f55542191b0c56b9ea68c29236ab65")
(pdf "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12.5571&rep=rep1&type=pdf")
(abstract "This paper presents a compiler that translates Scheme code into the Java language. The programming language Scheme is known to be highly expressive and safe. By translating Scheme into Java, one can benefit from such features of Scheme as well as the portability of Java. Our compiler implements dynamic type checking in Scheme via down-casting in Java by mapping each Scheme value to a Java Object. However, naively doing so requires dynamic class checking in Java for every primitive operation in Scheme and thereby incurs much overhead. We reduce this overhead of runtime type checking by exploiting partial static type information obtained through soft typing. This method achieves about 200–700% speedup in micro benchmarks and 67% for a ray tracing program. Thus, our compiler combines the expressiveness and safety of Scheme with the portability of Java without much loss of efficiency.")

(id serpette2002compiling)
(type article)
(title "Compiling Scheme to JVM bytecode: a performance study")
(author "Serpette, Bernard Paul")
(author "Serrano, Manuel")
(journal "ACM SIGPLAN Notices")
(volume "37")
(number "9")
(pages "259--270")
(year 2002)
(publisher "ACM New York, NY, USA")
(pdf-sha1 "be0f1c8bbbd9be5140dc339f83ba8fc6753052e4")
(pdf "https://www.researchgate.net/profile/Bernard_Serpette/publication/221241204_Compiling_scheme_to_JVM_bytecode/links/0deec52ad969b2efd4000000/Compiling-scheme-to-JVM-bytecode.pdf")
(abstract "We have added a Java virtual machine (henceforth JVM) bytecode generator to the optimizing Scheme-to-C compiler Bigloo. We named this new compiler BiglooJVM. We have used this new compiler to evaluate how suitable the JVM bytecode is as a target for compiling strict functional languages such as Scheme. In this paper, we focus on the performance issue. We have measured the execution time of many Scheme programs when compiled to C and when compiled to JVM. We found that for each benchmark, at least one of our hardware platforms ran the BiglooJVM version in less than twice the time taken by the Bigloo version. In order to deliver fast programs the generated JVM bytecode must be carefully crafted in order to benefit from the speedup of just-in-time compilers.")

(id miller2002sisc)
(type techreport)
(title "SISC: A complete scheme interpreter in java")
(author "Miller, Scott G")
(year 2002)
(institution "Indiana University")
(pdf-sha1 "0e752abc43138fcb75ac4785a8abde65a18ff925")
(pdf "http://sisc-scheme.org/sisc.pdf")
(ps-gz "http://sisc-scheme.org/sisc.ps.gz")
(abstract "We will examine the design of SISC, a fully R5RS compliant heap-based inter- preter of the functional language Scheme, with proper tail-recursion and first-class continuations. All noteworthy components of the interpreter will be described, and as well as discussion of some implementation details related to interpretation optimizations and efficient use of the Object-Oriented host language Java.")

(id anderson2000silk)
(type inproceedings)
(title "SILK: a playful blend of Scheme and Java")
(author "Anderson, Kenneth R")
(author "Hickey, Timothy J")
(author "Norvig, Peter")
(booktitle "2000 Workshop on Scheme and Functional Programming")
(year 2000)
(pdf-sha1 "c91711cf98dc5376d43865c6295e6974df22ae4f")
(pdf-sha1 "6fbaae9cd2b75e0b5fa72c6278cc338658035b63")
(ps-sha1 "c2e5eab900c23a1b5092c920e76084a7bf93cc80")
(pdf "https://www.researchgate.net/profile/Peter_Norvig/publication/242392064_Silk_a_playful_combination_of_scheme_and_java_workshop_on_scheme_and_functional_programming_rice_university/links/566e43e408ae62b05f0b4c51.pdf")
(abstract "SILK (Scheme in about 50 K) is a compact Scheme implemented in Java. It is currently in its fourth implementation. The first version implemented a nearly R4RS Scheme in Java, but its access to Java was awkward. The current version has altered SILK's syntax and semantics slightly to better integrate with Java. This has simplified its implementation, and made SILK an effective Java scripting language, while preserving its Scheme flavor. SILK applications, applets and servlets are suprisingly compact because they take advantage of Scheme's expressiveness. Because SILK is interactive and has reflective access to Java, it provides a view into a Java application that few Java programmers have seen. For example, it easily reveals a security issue involving inner classes. SILK is an Open Source project at http://silk.sourceforge.net")

;; Also Brandeis University CS-02-224
(id hickey2002incorporating)
(type article)
(title "Incorporating Scheme-based Web Programming in Computer Literacy Courses")
(author "Hickey, Timothy J")
(journal "2002 Workshop on Scheme and Functional Programming")
(pages "9")
(year 2002)
(pdf-sha1 "018731d1b984c42a7fac564c04928df64c4a7d08")
(pdf-sha1 "f36c83c9b215e4ed8f7ba25ce5f6ab6c3ce2ca53")
(pdf "https://www.cs.brandeis.edu/~tim/Papers/jscheme2002.pdf")
(abstract "We describe an approach to introducing non-science majors to computers and computation in part by teaching them to write applets, servlets, and groupware applications using a dialect of Scheme implemented in Java. The declarative nature of our approach allows non-science majors with no programming background to develop surprisingly complex web applications in about half a semester. This level of programming provides a context for a deeper understanding of computation than is usually feasible in a Computer Literacy course. The course does not require the students to download any software as all programming can be done with Scheme applets. The instructor however must provide a Scheme server which will run the students' servlets.")

(id hickey2002incorporating2)
(type article)
(title "Incorporating Scheme-based Web Programming into Computer Literacy Courses")
(author "Hickey, Timothy J")
(year 2002)
(pdf-sha1 "0942cbd0b78a6e2599575e2e991ff8ddc9017d6f")
(pdf "https://www.cs.brandeis.edu/~tim/Papers/icfp2002.pdf")
(abstract "We describe an approach to introducing non-science majors to computers and computation in part by teaching them to write applets, servlets, and groupware applications using a dialect of Scheme implemented in Java. The declarative nature of our approach allows non-science majors with no programming background to develop surprisingly complex web applications in about half a semester. This level of programming provides a context for a deeper understanding of computation than is usually feasible in a Computer Literacy course.")

(id hickey2002incorporating)
(type article)
(title "Jscheme Web Programming for CS0")
(author "Hickey, Timothy J")
(organization "Brandeis University")
(serial "CS-02-223")
(year 2002)
(month 1)
(ps-sha1 "fbfbf0e89b3ab45666cded82dc48f40e9d841f39")
(ps "http://www.cs.brandeis.edu/~tim/Papers/sigcse-jscheme.ps")
(abstract "We describe an approach to introducing non-science majors to Computer Science by teaching them to write applets, servlets, and webapps using a dialect of Scheme implemented in Java.")

(id anderson1999reflecting)
(type inproceedings)
(title "Reflecting java into scheme")
(author "Anderson, Kenneth R")
(author "Hickey, Timothy J")
(booktitle "International Conference on Metalevel Architectures and Reflection")
(pages "154--173")
(year 1999)
(organization "Springer")
;; SHA of whole lecture notes
(pdf-sha1 "10463558f189347e139e692fceefd489d56862f5")
(pdf "ftp://nozdr.ru/biblio/kolxoz/Cs/CsLn/M/Meta-Level%20Architectures%20and%20Reflection,%202%20conf.,%20Reflection'99(LNCS1616,%20Springer,%201999)(ISBN%203540662804)(282s)_CsLn_.pdf#page=164")
(abstract "We describe our experience with SILK, a Scheme dialect written in Java. SILK grazes symbiotically on Java's reflective layer, enriching itself with Java's classes and their behavior. This is done with three procedures. (con- structor) and (method)provide access to a specific Java constructor or method respectively. (import) allows the entire behavior of a class to be im- ported easily. (import) converts Java methods into generic functions that take methods written in Java or Scheme. In return, SILK provides Java applica- tions with an interactive development and debugging environment that can be used to develop graphical applications from the convenience of your web browser. Also, because SILK has introspective access into Java, it can also be used for compile time metaobject scripting. For example, it can generate a new class using an old one as a template.")

(id hickey1998lisp)
(type inproceedings)
(title "LISP: a Language for Internet Scripting and Programming")
(author "Hickey, Timothy J")
(author "Norvig, Peter")
(author "Anderson, Kenneth R")
(booktitle "Proceedings of the Lisp User Group Meeting")
(organization "Franz Inc.")
(year 1998)
(pdf-sha1 "6929e1e52830cf4ea61ca323d4a569f933374c0e")
(pdf "http://www.norvig.com/lugm.pdf")
(abstract "In this paper we argue that LISP can provide a powerful tool for web programmers, at both the novice and expert level, and that LISP has the potential to become a language of choice for writing both client-side and server-side internet programs. The syntactic and semantic simplicity of LISP enables non-experts to quickly master a basic level of LISP programming. Its higher order functions enable the implementation of a simple and elegant LISP interface to Java methods, elds, and constructors. With this interface, LISP provides full and simple access to the versatile and omnipresent Java class libraries. The conciseness of some dialects of LISP (e.g., Scheme) makes it relatively easy to implement compact LISP interpreters in Java and LISPto-Java compilers. LISP can then be called from Java programs and Java-enabled browsers. The declarative nature of LISP allows one to design and implement simple, declarative interfaces to the Java class libraries, which allow one to create applets and client-server software which is much more concise and comprehensible than the same programs written in imperative languages such as Java or Javascript (for applet programming) or Java, Perl, C++, or C for client-server programs. Two additional fertile applications for LISP on the internet are debugging and scripting of Java code. In this paper, we provide small examples of all of these applications, describe our LISP implementation (SILK - Scheme In 50 KB), and ponder the future of LISP as a language for internet scripting and programming.")

(id bothner1998kawa)
(type inproceedings)
(title "Kawa: Compiling Dynamic Languages to the Java VM")
(author "Bothner, Per")
(booktitle "Proceedings of the annual conference on USENIX Annual Technical Conference")
(pages "41--41")
(year 1998)
(ps-sha1 "53adef59abebbb4c0d607f125d970f1e46d444f2")
(ps "http://sources.redhat.com/kawa/papers/Freenix98.ps.gz")
(pdf-sha1 "8e4e0137128d34b3935a81c076601b1d99747517")
(pdf "https://www.usenix.org/legacy/publications/library/proceedings/usenix98/freenix/bothner.pdf")
(abstract "Many are interested in Java for its portable bytecodes and extensive libraries, but prefer a different language, especially for scripting. People have implemented other languages using an interpreter (which is slow), or by translating into Java source (with poor responsiveness for eval). Kawa uses an interpreter only for \"simple\" expressions; all non-trivial expressions (such as function definitions) are compiled into Java bytecodes, which are emitted into an in-memory byte array. This can be saved for later, or quickly loaded using the Java ClassLoader." "Kawa is intended to be a framework that supports multiple source languages. Currently, it only supports Scheme, which is a lexically-scoped language in the Lisp family. The Kawa dialect of Scheme implements almost all of the current Scheme standard (R5RS), with a number of extensions, and is written in a efficient objectoriented style. It includes the full \"numeric tower\", with complex numbers, exact infinite-precision rational arithmetic, and units. A number of extensions provide access to Java primitives, and some Java methods provide convenient access to Scheme. Since all Java objects are Scheme values and vice versa, this makes for a very powerful hybrid Java/Scheme environment." "An implementation of ECMAScript (the standardized \"core\" of JavaScript) is under construction. Other languages, including Emacs Lisp, are also being considered. Kawa home page: http://www.cygnus.com/ bothner/kawa.htm")

(id bothner1998kawa)
(type article)
(title "Kawa: Compiling Scheme to Java")
(author "Bothner, Per")
(year 1998)
(conference "Lisp Users Conference: Lisp in the Mainstream (40th Anniversary of Lisp)")
(month "11")
(publisher "Citeseer")
(pdf-sha1 "481c8681c71a029519986201f11976208cfcbb80")
(pdf "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.5572&rep=rep1&type=pdf")
(ps-sha1 "aae4393b4c6cb351dbcfbb2a3acb91778071ee65")
(ps-gz "http://sources.redhat.com/kawa/papers/KawaLisp98.ps.gz")
(abstract "Kawa is a set of Java classes useful for implementing dynamic languages, such as those in the Lisp family. Kawa is also an implementation of near-R5 RS Scheme using these classes, and which compiles Scheme to the bytecode instructions of the Java Virtual Machine. This paper discusses the various issues involved in implementing Scheme using an abstract machine designed for a very different language. and how Kawa solves these problems." "The Kawa home page is http://www.cygnus.com/~bothner/kawa.html." "An earlier version of this paper was presented at Usenix in June 1998.")

(id depristo2000sintl)
(type inproceedings)
(title "SINTL: A Strongly-Typed Generic Intermediate Language for Scheme")
(author "DePristo, Mark")
(booktitle "Northwestern University, Computer Science Honors Thesis")
(year 2000)
(organization "Citeseer")
(ps-sha1 "3fb2b8b9f147526799e4d106eb9bc924ef160596")
(pdf-sha1 "07a62d83bfd5caf9bf55ee3a1fb26da11202a11f")
(pdf-sha1 "ac4e1973e7d6c5a4b6c1c487875ab2a3d889d99e")
(pdf "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11.4917&rep=rep1&type=pdf")
(ps-sha1 "3fb2b8b9f147526799e4d106eb9bc924ef160596")
(abstract "This paper describes SINTL, a strongly-typed generic intermediate language for Scheme. The paper begins by outlining the motivation for developing a sophisticated intermediate language for a new Scheme compiler. We consider two novel aspects of SINTL as an intermediate language for Scheme, a declarative type system and type inference algorithm, and a register to stack machine conversion algorithm. We then demonstrate the effectiveness of these two techniques by discussing the JVM-SINTL backend, a fully functional backend to the Java Virtual Machine. Following a discussion of the representational choices and compilation techniques used in JVM-SINTL, we compare the performance of the JVM-SINTL backend relative to several popular Scheme compilers. Ultimately, this thesis demonstrates that a sophisticated compiler with well-selected analyses and optimizations can generate high-quality code running on the JVM, and acheive performance an order of magnitude better than current Scheme compilers to the JVM.")

(id carlstrom2000embedding)
(type phdthesis)
(title "Embedding scheme in Java")
(author "Carlstrom, Brian David")
(year 2000)
(school "Massachusetts Institute of Technology")
(pdf-sha1 "8e7f5394cbe5fe8ab5ae8d0c6591ead66fed9e46")
(pdf "https://dspace.mit.edu/bitstream/handle/1721.1/16764/48985095-MIT.pdf?sequence=2&isAllowed=y")
(abstract "Extension languages are an important part of modern applications development. Java as a platform does not provide a standard extension language. Scheme is one possible choice as an extension language for Java. There are a variety of techniques for implementing Scheme in Java varying from interpreting s-expressions to compiling into Java byte-codes. The historical evolution of one implementation is discussed over the course of several years. The design of the Java-to-Scheme and Scheme-to-Java interfaces is reviewed. The advantages and disadvantages of Java and Scheme are compared.")

(id bres2004compiling)
(type inproceedings)
(title "Compiling scheme programs to .NET common intermediate language")
(author "Bres, Yannis")
(author "Serpette, Bernard Paul")
(author "Serrano, Manuel")
(author "others")
(booktitle "2nd International Workshop on .NET Technologies, Pilzen, Czech Republic")
(year 2004)
(pdf-sha1 "d40f014f342ce979f1a8a41b6a631273cd68c044")
(pdf "http://www-sop.inria.fr/members/Manuel.Serrano/publi/bss-dotnet04.pdf")
(abstract "This paper presents the compilation of the Scheme programming language to .NET platform. .NET provides a virtual machine, the Common Language Runtime (CLR), that executes bytecode: the Common Intermediate Language (CIL). Since CIL was designed with language agnosticism in mind, it provides a rich set of language constructs and functionalities. Therefore, the CLR is the first execution environment that offers type safety, managed memory, tail recursion support and several flavors of pointers to functions. As such, the CLR presents an interesting ground for functional language implementations." "We discuss how to map Scheme constructs to CIL. We present performance analyses on a large set of real-life and standard Scheme benchmarks. In particular, we compare the performances of these programs when compiled to C, JVM and .NET. We show that .NET still lags behind C and JVM.")

(id bres2004bigloo)
(type article)
(title "Bigloo.NET: compiling Scheme to .NET CLR")
(author "Bres, Yannis")
(author "Serpette, Bernard P")
(author "Serrano, Manuel")
(journal "Journal of Object Technology")
(volume "3")
(number "9")
(pages "71--94")
(year 2004)
(month 10)
(pdf "https://core.ac.uk/download/pdf/194202027.pdf")
(abstract "This paper presents the compilation of the Scheme programming language to .NET. This platform provides a virtual machine, the Common Language Runtime (CLR), that executes bytecode, the Common Intermediate Language (CIL). Since CIL was designed with language agnosticism in mind, it provides a rich set of language constructs and functionalities. As such, the CLR is the first execution environment that offers type safety, managed memory, tail recursion support and several flavors of pointers to functions. Therefore, the CLR presents an interesting ground for functional language implementations." "We discuss how to map Scheme constructs to CIL. We present performance analyses on a large set of real-life and standard Scheme benchmarks. In particular, we compare the speed of these programs when compiled to C, JVM and .NET. We show that in term of speed performance of the Mono implementation of .NET, the best implementing running on both Windows and Linux, still lags behind C and fast JVMs such as the Sun's implementations.")

(id loitsch2005javascript)
(type article)
(title "JavaScript to Scheme compilation")
(author "Loitsch, Florian")
(journal "2005 Workshop on Scheme and Functional Programming")
(year 2005)
(publisher "Citeseer")
(ps-sha1 "a43b79a15372d955760622033830020fbcb7590d")
(pdf-sha1 "bbcb5d920209b780dbe6c47f875523130521371e")
(abstract "This paper presents Jsigloo, a Bigloo frontend compiling Javascript to Scheme. Javascript and Scheme share many features: both are dynamically typed, they feature closures and allow for functions as first class citizens. Despite their similarities it is not always easy to map Javascript constructs to efficient Scheme code, and in this paper we discuss the non-obvious transformations that needed special attention." "Even though optimizations were supposed to be done by Bigloo the chosen Javascript-Scheme mapping made several analyses ineffective and some optimizations are hence implemented in Jsigloo. We illustrate the opportunities Bigloo missed and show how the additional optimizations improve the situation.")

(end-group)

(group "Compiling Scheme to C")

(id bartlett1989scheme)
(type techreport)
(title "Scheme->C: A Portable Scheme-to-C Compiler")
(author "Bartlett, Joel F")
(booktitle "WRL Research Report 89/1")
(year 1989)
(month 1)
(organization "Citeseer")
(ps-sha1 "07fb66928e442b1164e205eea61653676d53d718")
(ps "ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/s2c.ps.gz")
(pdf-sha1 "72adbd182688eaa90af0eb96942c0eec9211bfc4")
(pdf "https://www.hpl.hp.com/techreports/Compaq-DEC/WRL-89-1.pdf")
(abstract "One way to make compilers portable is to have them compile to an intermediate language which is implemented on multiple architectures. By using C as the intermediate language and compiling the LISP dialect Scheme to it, it might be possible to achieve the following benefits. First, since C is the lingua franca of workstations the resulting system should be very portable. Second, it should allow Scheme programs to interact with those written in other languages. Finally, it should simplify the compiler as it need not repeat the optimization capability available in the C compiler." "However, there might be some unacceptable costs associated with this. First, there might not be a clean translation from Scheme to C, so that the implementation is not quite Scheme. Second, the two-stage translation might result in inefficient code. Finally, the generated code might be so stylized that it is neither portable nor compatible with other programming languages." "To investigate these issues, such a compiler and run-time system were constructed at Digital Equipment Corporation's Western Research Laboratory. Experience with the system shows that there is a translation of Scheme to C, that has good performance, and is portable.")

;; R. Kent Dybvig. "C-Scheme". Masters Thesis. Indiana University Computer Science Department. Technical Report 149. 1983.

(id serrano1994vers)
(type phdthesis)
(title "Vers une compilation portable et performante des langages fonctionnels")
(author "Serrano, Manuel")
(year 1994)
(school "Paris 6")

(id tammet1995lambda)
(type article)
(title "Lambda lifting as an optimization for compiling Scheme to C")
(author "Tammet, Tanel")
(organization "Chalmers University of Technology, Department of Computer Sciences")
(year 1995)
(publisher "Citeseer")
(ps-sha1 "9dbecf8a332c312683ab17991c1b0f9e8bacf974")
(pdf-sha1 "37afd487da2e018cab76ddad135fe72a81ae8669")
(pdf-sha1 "eb849cd31df5c5aafc3941e0455828dbfb4f1ddd")
(ps "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.9787&rep=rep1&type=pdf")
(abstract "We describe an optimizing Scheme-to-C compiler Hobbit. The innovation implemented in Hobbit is the usage of the technique of lambda-lifting (see [Hughes 84], [Johnsson 85], [Peyton-Jones 87]) combined with standard closures to compile lambda expressions and higher-order functions in the context of an impure functional language like Scheme and the object language like C. Lambda-lifting avoids the need for accessing the variables through an environment." "Lambda-lifting is not always applicable to lambda-terms in Scheme. It is applicable only in case the code surrounding the lambda-term satis es certain criteria, which is checked by Hobbit using global analysis. In all the other cases the compiler reverts to using closures.")

(id benson1994libscheme)
(type inproceedings)
(title "Libscheme: Scheme as a C library")
(author "Benson Jr, Brent W")
(booktitle "Proceedings of the USENIX Symposium on Very High Level Languages")
(pages "7--19")
(year 1994)
(ps-gz "ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/libscheme-vhll.ps.gz")
(abstract "Because of its small size and simplicity, Scheme is often seen as an ideal extension or scripting language. While there are many Scheme implementations available, their interfaces are often complex and can get in the way of using the implementation as part of a larger software product. The libscheme library makes the Scheme language available as a C library. Its interface is through a single C header file and it is easily extended with new primitive procedures, new primitive types, and new syntax. It is portable to any system that has an ANSI C compiler and to which Hans Boehm's popular conservative garbage collector has been ported. It has been used to build a variety of special purpose data manipulation tools and as an extension language for an ethernet monitor.")
(ps-sha1 "a3638dc62bea0cf00102096eb5226023b14e6482")
(ps-sha1 "ff07ac55cc4c5862f393a538c1e2b14243dc8242")

(id rose1992integrating)
(type inproceedings)
(title "Integrating the Scheme and C languages")
(author "Rose, John R")
(author "Muller, Hans")
(booktitle "Proceedings of the 1992 ACM conference on LISP and functional programming")
(pages "247--259")
(year 1992)
(pdf-sha1 "005dab9169a881b3aee569e24b26e491dd40581e")
(pdf "https://3e8.org/pub/scheme/doc/lisp-pointers/v5i1/p247-rose.pdf")
(abstract "Most implementations of Scheme (and other Lisp dialects) provide some facility for calling functions defined in ANSI C (or other popular languages) even if only to implement Scheme's primitive operations. Some relatively sophisticated implementations provide access to non-Scheme data structures, Taking a Scheme-centered view, we will refer to these facilities as foreign call-out, for both data and functions access. Scheme implementations may also provide ways for C code to use Scheme functions and data structures more or less directly. We will refer to this as foreign call-in." "Call-in is usually more difficult than foreign call-out, because Scheme systems depend on a strong set of invariants relating to storage management, safety, and runtime dispatching, and these invariant must be restored and maintained by foreign code which makes call-ins. For these reasons, many Scheme systems are not packaged as libraries. Rather, they are full environments which must take over the management of the entire address space in which they run.")

(id baker1995cons)
(type article)
(title "CONS should not CONS its arguments, part II: Cheney on the MTA")
(author "Baker, Henry G")
(journal "ACM Sigplan Notices")
(volume "30")
(number "9")
(pages "17--20")
(year 1995)
(publisher "ACM New York, NY, USA")
(pdf-sha1 "078561f0488bfe78fb97bdbefbd0cfcc42877b07")
(pdf-sha1 "9113f30cedfaec0fb2ef5a619d7511c8fd41848f")
(pdf "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.7143&rep=rep1&type=pdf")
(abstract "Previous Schemes for implementing full tail-recursion when compiling into C have required some form of \"trampoline\" to pop the stack. We propose solving the tail-recursion problem in the same manner as Standard ML of New Jersey, by allocating all frames in the (garbage-collected) heap. The Scheme program is translated into continuation-passing style, so the target C functions never return. The C stack pointer then becomes the allocation pointer for a Cheney-style copying garbage collection scheme. Our Scheme can use C function calls, C arguments, C variable-arity functions, and separate compilation without requiring complex block-compilation of entire programs.")

(id feeley1997compiling)
(type article)
(title "Compiling higher-order languages into fully tail-recursive portable C")
(author "Feeley, Marc")
(author "Miller, James")
(author "Rozas, Guillermo")
(author "Wilson, Jason")
(journal "Rapport technique")
(volume "1078")
(year 1997)
(organization "Departement d'informatique et r.o., Universite de Montreal")
(ps-sha1 "a822ae791567456eebb6b01e7336fed2c4cfb00e")
(ps "http://www.iro.umontreal.ca/~feeley/papers/tr1078.ps.gz")
(pdf-sha1 "1ac8b1f3d16fd1f717c8a6ac97798a5b5de434ce")
(pdf "http://www.iro.umontreal.ca/~feeley/papers/FeeleyMillerRozasWilsonDIRO1078.pdf")
(abstract "Two independently developed implementations of Scheme have been extended to compile into portable C code that implements full tail-recursion. Like other compilers for higher-order languages that implement full tail-recursion, measurements of these systems indicate a performance degradation of a factor between two and three compared to the native code emitted by the same compilers. We describe the details of the compilation technique for a non-statically typed language (Scheme) and show that the performance difficulty arises largely from the cost of C function calls. In theory, these expensive calls can be eliminated. In practice, however, they are required to avoid excessively long compilation times by modern C compilers, and to support separate compilation.")

(id feeley2000portable)
(type article)
(title "A portable implementation of first-class continuations for unrestricted interoperability with C in a multithreaded Scheme")
(author "Feeley, Marc")
(year 2000)
(journal "2000 Workshop on Scheme and Functional Programming")
(ps-sha1 "b4750ac8fd1e7c3ec9aaa388b5fa04134818aa02")
(pdf-sha1 "9e3f82369fc1adaf2c5b0c18ba528cea005e2a9a")
(pdf-sha1 "b795ff27197efb4dcb0b92344e4f029b1df5a950")
(pdf "http://www-labs.iro.umontreal.ca/~feeley/papers/FeeleySW00.pdf")
(abstract "The implementation of rst-class continuations in a Scheme system that interfaces to a stack-based language such as C is difficult when Scheme and C frames can be interleaved (i.e. Scheme and C can nest calls to each other arbitrarily). Such a situation occurs when using a combination of callbacks, higher-order functions, exception processing, and a Scheme level thread system built on top of rst-class continuations. We show that in this context the use of C threads to implement rst-class continuations allows unrestricted interoperability with C.")

(end-group)

(group "VLISP: Formally Verified Scheme Implementation")

(id guttman1995vlisp)
(type article)
(title "VLISP: A verified implementation of Scheme")
(author "Guttman, Joshua D")
(author "Ramsdell, John D")
(author "Wand, Mitchell")
(journal "Lisp and Symbolic Computation")
(volume "8")
(number "1-2")
(pages "5--32")
(year 1995)
(publisher "Springer")
(pdf "https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.644.4699&rep=rep1&type=pdf")
(abstract "VLISP has produced a rigorously verified compiler from Scheme to byte codes, and a verified interpreter for the resulting byte codes. The official denotational semantics for Scheme provides the main criterion of correctness. The Wand-Clinger technique was used to prove correctness of the main compiler step. Then a state machine operational semantics is proved to be faithful to the denotational semantics. The remainder of the implementation is verified by a succession of state machine refinement proofs. These include proofs that garbage collection is a sound implementation strategy, and that a particular garbage collection algorithm is correct.")
(ps-sha1 "7bc629550280aeab609509aa9afb1e7dd994e8c0")
(pdf-sha1 "0a3d4df705b2ba5dfde19c2d1720c08c8b4964bd")
(pdf-sha1 "e8531291f5c0c6380769e2d1eff497b07de09677")

(id guttman1995vlisp)
(type article)
(title "The VLISP verified Scheme system")
(author "Guttman, Joshua D")
(author "Ramsdell, John D")
(author "Swarup, Vipin")
(journal "Lisp and Symbolic Computation")
(volume "8")
(number "1-2")
(pages "33--110")
(year 1995)
(publisher "Springer")
(ps-sha1 "4c6a036b50cb8729b1dca09b270f690870436124")
(pdf-sha1 "15a528b0cf2ec8f50fa06d3d82ab691a693e4e3b")
(pdf-sha1 "e8531291f5c0c6380769e2d1eff497b07de09677")
(abstract "The VLISP project has produced a rigorously verified compiler from Scheme to byte codes, and a verified interpreter for the resulting byte codes. The official denotational semantics for Scheme provides the main criterion of correctness. The Wand-Clinger technique was used to prove correctness of the primary compiler step. Then a state machine operational semantics is proved to be faithful to the denotational semantics. The remainder of the implementation is verified by a succession of state machine refinement proofs. These include proofs that garbage collection is a sound implementation strategy, and that a particular garbage collection algorithm is correct.")

;; Also printed in Lisp and Symbolic Computation. Vol. 8 No. 1/2. 1995.
(id oliva1995vlisp)
(type incollection)
(title "The VLISP verified PreScheme compiler")
(author "Oliva, Dino P")
(author "Ramsdell, John D")
(author "Wand, Mitchell")
(booktitle "VLISP A Verfied Implementation of Scheme")
(pages "111--182")
(year 1995)
(publisher "Springer")
(ps-gz "http://www.ccs.neu.edu/home/wand/papers/vlisp/lasc/prescheme.ps.gz")
(ps-sha1 "729768cae9d0698d4858021b1f3056229108bbc8")
(ps-sha1 "e6fe2549894430d2943655226845ca76b4f80d31")
(pdf-sha1 "65c4eaf82370cfc46039eb2f8ab4ebdd5e2928d6")
(abstract "This paper describes a verified compiler for PreScheme, the implementation language for theVLISP run-time system. The compiler and proof were divided into three parts: A transformational front end that translates source text into a core language, a syntax-directed compiler that translates the core language into a combinator-based tree-manipulation language, and a linearizer that translates combinator code into code for an abstract stored-program machine with linear memory for both data and code. This factorization enabled different proof techniques to be used for the different phases of the compiler, and also allowed the generation of good code. Finally, the whole process was made possible by carefully defining the semantics ofVLISP PreScheme rather than just adopting Scheme's. We believe that the architecture of the compiler and its correctness proof can easily be applied to compilers for languages other than PreScheme.")

(id guttman1992guide)
(type article)
(title "A guide to VLISP, a verified programming language implementation")
(author "Guttman, Joshua D")
(author "Monk, Leonard G")
(author "Ramsdell, John D")
(author "Farmer, William M")
(author "Swarup, Vipin")
(journal "M 92B091")
(organization "The MITRE Corporation")
(year 1992)
(pdf "https://www.researchgate.net/profile/Joshua-Guttman/publication/237128482_A_Guide_to_VLISP_A_Verified_Programming_Language_Implementation/links/0a85e5339adfadbd67000000/A-Guide-to-VLISP-A-Verified-Programming-Language-Implementation.pdf")
(ps-sha1 "273d9abfb422b83e82d46c29cc2c564477c6edf2")
(pdf-sha1 "4242c0aed2f34639461935cdf768e693dbe0af06")
(pdf-sha1 "c98ddc7d1b3fac719a09248ac7a16b691a5c5f3d")
(abstract "The Verified Programming Language Implementation project has developed a formally verified implementation of the Scheme programming language, called VLISP. This report summarizes the results of the project. It also provides an overview of a group of reports presenting the details of the VLISP implementation and the logical proofs of its correctness.")

(id ramsdell1992vlisp)
(type techreport)
(title "The VLISP PreScheme Front End")
(author "Ramsdell, John D")
(author "Farmer, William M")
(author "Guttman, Joshua D")
(author "Monk, Leonard G")
(author "Swarup, Vipin")
(number "MTR92B098")
(ortanization "The MITRE Corporation")
(year 1992)
(publisher "Citeseer")
(pdf "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.647.244&rep=rep1&type=pdf")
(ps-sha1 "729768cae9d0698d4858021b1f3056229108bbc8")
(pdf-sha1 "65c4eaf82370cfc46039eb2f8ab4ebdd5e2928d6")
(pdf-sha1 "4b0c218a4cb05f4e41f9eac830034dc7a26c058f")
(abstract "The Verified Programming Language Implementation project has developed a formally verified implementation of the Scheme programming language. This report documents the VLISP PreScheme language, used to program the VLISP Virtual Machine (interpreter). It contains detailed proofs that a set of transformations preserve the meanings of VLISP PreScheme programs.")

(id ramsdell1993revised)
(type techreport)
(title "The revised VLISP PreScheme front end")
(author "Ramsdell, John D")
(organization "The MITRE Corporation")
(number "M 93B095")
(year 1993)
(publisher "Citeseer")
(pdf "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.646.9935&rep=rep1&type=pdf")
(ps-sha1 "42781e6202882701d76bca8b178aa2a87dd2f947")
(pdf-sha1 "336bb39eb04decf833e8e290f5d44d227e7a66fd")
(pdf-sha1 "336bb39eb04decf833e8e290f5d44d227e7a66fd")
(abstract "The Verified Programming Language Implementation Pro ject developed a formally verified implementation of the Scheme programming language. It used a systems programming dialect of Scheme, called vlisp PreScheme, to program the vlisp Virtual Machine, a byte-code interpreter. The original compiler only accepted programs that specify iterative processes. This document describes a revision of the language and its compiler. The most important change is the compiler provides a stack to save control information for procedure calls so programs that specify recursive processes are accepted. The revision expands the systems programming tasks for which vlisp PreScheme can be used and simplifies the task of matching an algorithm with its code.")

(id oliva1991verified)
(type techreport)
(title "A Verified Compiler for Pure PreScheme: Final Report for Contract Number F19628-89-C-001")
(author "Oliva, Dino P")
(author "Wand, Mitchell")
(year 1991)
(institution "MITRE Corporation")
(pdf "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.646.2892&rep=rep1&type=pdf")
(abstract "This document gives a summary of activities under MITRE Contract Number F19628-89-C-001. It gives a detailed denotational specification of the language Pure PreScheme. A bytecode compiler, derived from the semantics, is presented, followed by proofs of correctness of the compiler with respect to the semantics. Finally, an assembler from the bytecode to an actual machine architecture is shown.")
(ps-sha1 "627246262a039d6c1aff628ec8017340534d4bdc")
(pdf-sha1 "610cef8d1029e1fa80297da64a172c60481a840a")

(id prescheme1996verified)
(type techreport)
(title "A Verified Compiler for Multithreaded PreScheme")
(author "PreScheme, Multithreaded")
(year 1996)
(institution "MITRE Corporation")
(pdf "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.646.4498&rep=rep1&type=pdf")
(ps-sha1 "6cae681aa1a5b075d3532f1dfbd8322996846318")
(pdf-sha1 "29db042b6b09fb6d754e1e2fd1c6eee973787f1c")
(abstract "Multithreaded PreScheme is a systems programming language for highassurance systems. It is based on VLISP PreScheme, a systems programming language dialect of Scheme developed by the VLISP project. Multithreaded PreScheme is an extension of VLISP PreScheme which allows programs with more than one thread of control. This document describes the language and also a verified compiler which generates code for mips-based architectures. The two ma jor contributions described in this report are a proof of the correctness of code generated for execution in the presence of multiple threads, and a new code generator that produces substantially faster code than that produced by the verified compiler for VLISP PreScheme.")

(id guttman1992vlisp)
(type techreport)
(title "The VLISP byte-code compiler")
(author "Guttman, Joshua D")
(author "Monk, Leonard G")
(author "Farmer, William M")
(author "Ramsdell, John D")
(author "Swarup, Vipin")
(number "M 92B092")
(institution "The MITRE Corporation")
(year 1992)
(publisher "Citeseer")
(pdf "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.646.9914&rep=rep1&type=pdf")
(ps-sha1 "417548a9a1894ebbe398cd0c2b4232f45f1d9031")
(pdf-sha1 "f07726ba207d024f7670dc0ea390332225679095")
(abstract "The Verified Programming Language Implementation project has developed a formally verified implementation of the Scheme programming language. This report provides a detailed presentation of the byte-code compiler and its proof of correctness.")

(id oliva1992verified)
(type techreport)
(title "A verified run-time structure for Pure PreScheme")
(author "Oliva, Dino P")
(author "Wand, Mitchell")
(year 1992)
(institution "The MITRE Corporation")
(ps-sha1 "b2d13e973e4138730780a287a00fc926d425a04f")
(pdf-sha1 "7427654695db77f6ec9b81630b058f5546ee0c02")
(abstract "This document gives a summary of activities under MITRE Corporation Contract Number F19628-89-C-0001. It gives an operational semantics of an abstract machine for Pure PreScheme and of its implementation as a run-time structure on an Motorola 68000 microprocessor. The relationship between these two models is stated formally and proved.")

(id swarup1992vlisp)
(type techreport)
(title "VLISP byte code interpreter")
(author "Swarup, Vipin")
(author "Farmer, William M")
(author "Guttman, Joshua D")
(author "Monk, Leonard G")
(author "Ramsdell, John D")
(year 1992)
(institution "MITRE Corporation")
(pdf "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.10.1711&rep=rep1&type=pdf")
(ps-sha1 "93b54ef41673cccc4424f62b1c7c36c3b071b9be")
(pdf-sha1 "123c1931c21e62fef38de351eb3fa4805cc6a66f")
(pdf-sha1 "c0ccf6415d06a7898d78cae724276c67f4abcdb5")
(abstract "The Verified Programming Language Implementation project has developed a formally verified implementation of the Sheme programming language. This report douments the byte-ode interpreter, whih exeutes a user program presented in the form of a binary image. It speifies several intermediate abstrat mahines, and proves that they are (suessive) faithful implementations of the Vlisp operational semantis. Garbage olletion and the finiteness of omputer memories are among the issues handled.")

(id farmer1992faithfulness)
(type article)
(title "Faithfulness of the VLISP operational semantics")
(author "Farmer, William M")
(author "Guttman, Joshua D")
(author "Monk, Leonard G")
(author "Ramsdell, John D")
(author "Swarup, Vipin")
(number "M 92B093")
(institution "The MITRE Corporation")
(year 1992)
(pdf "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.492.2366&rep=rep1&type=pdf")
(ps-sha1 "22bb8864651a3c546e7ce0874c32ce8f4bed755d")
(pdf-sha1 "cc8fb39786f7a1340165e3a4cd1dc59aa91322fa")
(abstract "The Verified Programming Language Implementation project has developed a formally verified implementation of the Scheme programming language. This report provides a detailed proof that the operational semantics for the highest-level interpreter (virtual machine) is faithful to the denotational semantics used in the byte-code compiler proof")

(id guttman1992vlisp)
(type article)
(title "The VLISP flattener")
(author "Guttman, Joshua D")
(author "Monk, Leonard G")
(author "Farmer, William M")
(author "Ramsdell, John D")
(author "Swarup, Vipin")
(number "M 92B094")
(institution "MITRE Corporation")
(year 1992)
(pdf "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.487.8154&rep=rep1&type=pdf")
(ps-sha1 "b83c7249df1833488cb48d659e43eb7b53113f86")
(pdf-sha1 "1757330c1389fd02ad746c504ea77219fb03a75d")
(abstract "The Verified Programming Language Implementation project has developed a formally verified implementation of the Scheme programming language. This report documents the flattener, which linearizes a tree-structured byte-code. It contains detailed proofs that the operational semantics of the attened output matches the operational semantics of the input.")

(id swarup1992vlisp)
(type techreport)
(title "The VLISP image builder")
(author "Swarup, Vipin")
(author "Farmer, William M")
(author "Guttman, Joshua D")
(author "Monk, Leonard G")
(author "Ramsdell, John D")
(number "M 92B096")
(institution "MITRE Corporation")
(year 1992)
(pdf "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.466.3441&rep=rep1&type=pdf")
(ps-sha1 "c3272d957ac263ef1fe11c07f64248e14c81c9f5")
(pdf-sha1 "df6c211fa63c5a959a1fb75d924b4a7e9d3d9ca5")
(abstract "The Verified Programming Language Implementation project has developed a formally verified implementation of the Scheme programming language. This report documents the image builder, which lays out a binary image for a program. It contains detailed proofs that the operational semantics of the resulting output matches the operational semantics of the input.")

(id farmer1992vlisp)
(type techreport)
(title "The VLISP linker")
(author "Farmer, William M")
(author "Guttman, Joshua D")
(author "Monk, Leonard G")
(author "Ramsdell, John D")
(author "Swarup, Vipin")
(number "M 92B095")
(institution "MITRE Corporation")
(year 1992)
(pdf "https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.646.7884&rep=rep1&type=pdf")
(abstract "The Verified Programming Language Implementation project has developed a formally verified implementation of the Scheme programming language. This report documents the linker, which lays out a single data structure for a program consisting of constants, variables, and procedures. It contains detailed proofs that the operational semantics of the linked output matches the operational semantics of the input.")
(ps-sha1 "fcbc75063717c89735ecfcf69590bbc2e73a4d12")
(pdf-sha1 "414a39af259cd5590164eeb91e3e88978e46e9f8")

(end-group)

(end-group)