bluuebunny/crossref_metadata_2025 huggingface dataset:
Adaptive multivariate three-timescale stochastic approximation algorithms for simulation based optimization
Authors: Bhatnagar Shalabh
Published: January 2005

We develop in this article, four adaptive three-timescale stochastic approximation algorithms for simulation optimization that estimate both the gradient and Hessian of average cost at each update epoch. These algorithms use four, three, two, and one simulation(s), respectively, and update the values of the decision variable and Hessian matrix components simultaneously, with estimates based on the simultaneous perturbation methodology. Our algorithms use coupled stochastic recursions that proceed using three different timescales or step-size schedules. We present a detailed convergence analysis of the algorithms and show numerical experiments using all the developed algorithms on a two-node network of
M/G/1
queues with feedback for a 50-dimensional parameter vector. We provide comparisons of the performance of these algorithms with two recently developed two-timescale
steepest descent
simultaneous perturbation analogs that use randomized and deterministic perturbation sequences, respectively. We also present experiments to explore the sensitivity of the algorithms to their associated parameters. The algorithms that use four and three simulations, respectively, perform significantly better than the rest of the algorithms.
DMG—object-oriented iterative knowledge acquisition for the generation of diagnostic hypertext systems
Authors: Tyrväinen Pasi T.
Published: January 2005

DMG is a development environment for building diagnostics applications of electrical equipment. Knowledge contained in an equipment model is compiled into a decision-tree like diagnostic logic, which is then used visually to pinpoint deficiencies in the performance of the equipment. The delivery application is a hypertext document which combines the diagnostic logic with links to sources of additional information. Benefits and experiences in real industrial use of DMG are presented; and practical issues on using a CLOS-based graphical user interface library are discussed.
Self-reproducing programs in Common Lisp
Authors: Norvig Peter
Published: January 2005

This paper reviews the classic self-reproducing expressions in Lisp, and presents some new ones that are unique to Common Lisp.
Efficient implementation of bit-vector operation in Common Lisp
Authors: Baker Henry G.
Published: January 2005

In this paper we show various techniques for the efficient implementation of the various functions of Common Lisp involving bit-vectors and bit-arrays. Bit-vectors are extremely useful for computing everything from the Sieve of Eratosthenes for finding prime numbers, to the representation of sets and relations, to the implementation of natural language parsers, to the performance of
flow analysis
in an optimizing compiler, to the manipulation of complex communication codes like those used in facsimile machines. However, the efficient manipulation of bit-vectors on modern computers represents a curious point on the spectrum of data processing tasks. On the one hand, the possibility of packing many bits within a single computer word and operating on all of them in parallel offers a potential for speedup not usually available for other types of tasks. On the other hand, the lack of the ability to efficiently manipulate single bits because of addressing schemes tuned for larger objects can actually
reduce
the speed of operating on bits. As a result of these observations, it should be obvious that no simple, automatic techniques such as "in-lining" (procedure integration) or "loop unrolling" of the obvious serial algorithms will produce the kinds of efficiency we are seeking. For these reasons, the efficient implementation of bit-vector operations requires special-case code, and is an interesting challenge in ingenuity and engineering.
Standard-output
Authors: Haynes Christopher T.
Published: January 2005

This is a brief report of efforts to standardize the Scheme programming language. Scheme inherits Lisp's rich set of symbol manipulation primitives, latent storage allocation, dynamic type checking, and simple syntax. Scheme is distinguished from most Lisp dialects by a single variable environment, block structure with static scope, and uniform evaluation of the operator and operand positions of a procedure call. Since there is no storage penalty for tail-recursive procedure calls, they may be used to express iteration. Provision is made for a rich set of numerical types, and exact and inexact numbers are distinguished. The ability to create first-class escape procedures allows almost all known forms of sequential control to be expressed. Above all, Scheme achieves its expressive power through the simplicity and generality of its design, and not by the accumulation of features. (The draft standard is about 50 pages long.) The reader may wish to consult books by Abelson and Sussman [1], Springer and Friedman [2], and Dybvig [3], among others, for tutorial introductions to Scheme.
A Lisp environment at IBM T J Watson Research
Authors: Mikelsons M. , Alberga C. N. , Skutt C. F.
Published: January 2005

We give a brief description of a Common Lisp programming environment developed at the IBM TJ Watson Research Center over the past two years. The two most novel features of this environment are a program analysis tool and a visual stepper. These are described in more detail.
The Series macro package
Authors: Waters Richard C.
Published: January 2005

The benefits of programming in a functional style are well known. Algorithms that are expressed as compositions of functions operating on series/vectors/streams of data elements are much easier to understand and modify than equivalent algorithms expressed as loops. Unfortunately, many programmers hesitate to use series expressions. In part, this is due to the fact that series expressions are typically implemented very inefficiently.A portable Common Lisp macro package (called Series) has been implemented that can evaluate a wide class of series expressions very efficiently by transforming them into iterative loops. When using this class of series expressions, programmers can obtain the advantages of expressing computations as series expressions without incurring any runtime overhead.
Concise reference manual for the Series macro package
Authors: Waters Richard C.
Published: January 2005

Series expressions are transformed into loops by pipelining them---the computation is converted from a form where entire series are computed one after the other to a form where the series are incrementally computed in parallel. In the resulting loop, each individual element is computed just once, used, and then discarded before the next element is computed. For this pipelining to be possible, four restrictions have to be satisfied. Before looking at these restrictions, it is useful to consider a related issue.
Improving binding times without explicit CPS-conversion
Authors: Bondorf Anders
Published: January 2005

A major obstacle in partial evaluation (program specialization) is the need for
binding time improvements
. By reorganizing a source program, the residual programs obtained by specializing the source program may be improved: more computations can be done statically, that is, at specialization time.

One well-known effective reorganization is (manual or automatic) conversion into
continuation passing style
(cps). This conversion allows data
consumers
to be propagated through
frozen
expressions to the data
producers
. In this paper we show how such improvements can be obtained without affecting the source program:
by writing the program specializer itself in cps
; traditionally, specialization has been formulated in direct style.

The advantages of avoiding cps-converting source programs are: (1) no cps-conversion phase is needed; (2) the generated residual programs are not in cps; (3) since no source level continuations are added, there is no overhead of manipulating closure representations in the generating extensions (e.g. compilers) obtained by self-application; (4) manual “binding time debugging” is easier since binding time analysis is done on a non-converted program.

We have implemented a cps-based program specializer; it is integrated in the partial evaluator Similix 4.0.

Using a cps-specializer,
partially static data structures
can be handled safely in a straightforward way. The difficulty is to ensure automatically that residual expressions that become part of a partially static data structure are neither duplicated nor discarded. This is achieved by binding such residual expressions in automatically inserted frozen let-expressions; cps is needed to propagate operations on the partially static data structure through these frozen let-expressions. Based on this idea, we have implemented an extension of Similix 4.0 that handles partially static data structures.
Safe fusion of functional expressions
Authors: Chin Wei-Ngan
Published: January 2005

Large functional programs are often constructed by decomposing each big task into smaller tasks which can be performed by simpler functions. This hierarchical style of developing programs has been found to
improve
programmers' productivity because smaller functions are easier to construct and reuse. However, programs written in this way tend to be less efficient. Unnecessary intermediate data structures may be created. More function invocations may be required.

To reduce such performance penalties, Wadler proposed a transformation algorithm, called
deforestation
, which could automatically
fuse
certain composed expressions together in order to eliminate intermediate tree-like data structures. However, his technique is only applicable to a
subset
of first-order expressions.

This paper will generalise the deforestation technique to make it applicable to all first-order and higher-order functional programs. Our generalisation is made possible by the adoption of a model for
safe fusion
which views each function as a producer and its parameters as consumers. Through this model, static program properties are proposed to classify producers and consumers as either safe or unsafe. This classification is used to identify sub-terms that can be safely fused/eliminated. We present the generalised transformation algorithm as a set of syntax-directed rewrite rules, illustrate it with examples, and provide an outline of its termination proof.
Improving the performance of SML garbage collection using application-specific virtual memory management
Authors: Cooper Eric , Nettles Scott , Subramanian Indira
Published: January 2005

We improved the performance of garbage collection in the standard ML of New Jersey system by using the virtual memory facilities provided by the Mach kernel. We took advantage of Mach's support for
large sparse address spaces
and
user-defined paging servers
. We decreased the elapsed time for realistic application by as much as a factor of 4.
Polymorphic type reconstruction for garbage collection without tags
Authors: Goldberg Benjamin , Gloger Michael
Published: January 2005

Several papers, have recently claimed that garbage collection can be performed on untagged data in the presence of ML-style type polymorphism. They rely on the ability to reconstruct the type of any reachable object during garbage collection. The bad news is that this is false—there can be reachable objects in the program whose type cannot be determined by the garbage collector. The good news is that tag-free garbage collection can be performed anyway—any object whose type cannot be determined by the collector is, in fact, garbage. Such objects can be discarded by the collector. This is the key result of this paper.

We present a type reconstruction algorithm that can determine the type of any non-garbage object. Unfortunately, the implementation of the tag-free collector for a polymorphically typed language is difficult in ways that were not described in the previous papers, and we address some implementation issues as well. However, we mainly describe how to perform type reconstruction during garbage collection and do not attempt to address practical issues of the garbage collection process.
Parsers in ML
Authors: Mauny Michel , de Rauglaudre Daniel
Published: January 2005

We present the operational semantics of streams and stream matching as discussed in. Streams are data structures such as lists, but with different primitive operations. Streams not only provide an interface to usual imput/output channels, but may used as a data structure
per se
, holding any kind of element. A special pattern matching construct is dedicated to streams and the actual matching process will be called
parsing
.

The primary parsing semantics that we propose here is predictive parsing, i.e. recursive descent semantics with a one token look-ahead: although this choice seems to restrict us to the recognition of LL9(1) languages, we show by examples that full functionality and parameter passing allow us to write parsers for complex languages. The operational semantics of parsers is given by transforming parsers into regular functions.

We introduce a non-strict semantics of streams by translating stream expression into more classical data structures; we also investigate different sharing mechanisms for some of the stream operations.
Interactive modular programming in Scheme
Authors: Tung Sho-Huan Simon
Published: January 2005

This paper presents a module system and a programming environment designed to support interactive program development in Scheme. The module system extends lexical scoping while maintainig its flavor and benefits and supports mutually recursive modules. The programming environment supports dynamic linking, separate compilation, production code compilation, and a window-based user interface with multiple read-eval-print contexts.
Abstract interpretation in weak powerdomains
Authors: Muller Robert , Zhou Yuli
Published: January 2005

We introduce a class of semantic domains,
weak powerdomains
, that are intended to serve as value spaces for abstract interpretations in which
safety
is a concern. We apply them to the analysis of PCF programs. In the classical abstract interpretation approach, abstract domains are constructed explicitly and the abstract semantics is then related to the concrete semantics. In the approach presented here, abstract domains are
derived
directly from concrete domains. The conditions for deriving the domains are intended to be as general as possible while still guaranteeing that the derived domain has sufficient structure so that it can be used as a basis for computing correct information about the concrete semantics. We prove three main theorems, the last of which ensures the correctness of abstract interpretation of PCF programs given safe interpretations of the constants. This generalizes earlier results obtained for the special case of strictness analysis.
Proving memory management invariants for a language based on linear logic
Authors: Chirimar Jawahar , Gunter Carl A. , Riecke Jon G.
Published: January 2005

We develop tools for the rigorous formulation and proof of properties of runtime management for a sample programming language based on a linear type system. Two semantics are diescribed, one at a level of observable results of computations and one describing linear connectives in terms of memory-management primitives. The two semantics are proven equivalent and the memory-management model is proven to satisfy fundamental correctness criteria for reference counts.
Parametric type classes
Authors: Chen Kung , Hudak Paul , Odersky Martin
Published: January 2005

We propose a generalization to Haskell's type classes where a class can have type parameters besides the placeholder variable. We show that this generalization is essential to represent container classes with overloaded data constructor and selector operations. We also show that the resulting type system has principal types and present unification and type reconstruction algorithms.
A calculus for overloaded functions with subtyping
Authors: Castagna Giuseppe , Ghelli Giorgio , Longo Giuseppe
Published: January 2005

We present a simple extension of typed λ-claculus where functions can be
overloaded
by adding different “pieces of code”. In short, the code of an overloaded function is formed by several branches of code; the branch to execute is chosen, when the function is applied, according to a particular selection rule which depends on the type of the argument. The crucial feature of the present approach is that a subtyping relation is defied among types, such that the type of a term generally decreases during computation, and this fact induces a distinction between the “compile-time” type and the “run-time”type of a term. We study the case of overloaded functions where the branch selection depends on the run-time type of the argument, so that overloading cannot be eliminated by a static analysis of code, but is an essential feature to be dealt with during computation. We prove Confluence and Strong Normalization for this calculus as well as a generalized Subject-Reduction theorem (but proofs are ommitted in this abstract.

The definition of this calculus is driven by the understanding of object-oriented features and the connections between our calculus and object-orientedness are extensively stressed. We show that this calculus provides a foundation for typed object-oriented languages which solves some of the problems of the standard record-based approach. It also provides a type-discipline for a relevant fragment of the “core framework” of CLOS.
Global tagging optimization by type inference
Authors: Henglein Fritz
Published: January 2005

Tag handling accounts for a substantial amount of execution cost in latently typed languages such as Common LISP and Scheme, espicially on architectures that provide no special hardware support.
Analysis of recursive types in Lisp-like languages
Authors: Wang Edward , Hilfinger Paul N.
Published: January 2005

We introduce a new algorithm to analyze recursive, structured types. It derives information from object uses (accesser functions with type checking), as well as from object allocation. The type description is a form of graph grammar and is naturally finite even in the presence of loops. The intended use of the algorithm is to discover and remove unnecessary type checks, but it can be augmented to provide alias information as well.
Taming the Y operator
Authors: Rozas Guillermo Juan
Published: January 2005

In this paper I present a set of conceptually simple but involved techniques used by LIAR, the MIT SCHEME compiler, to generate good code when recursive procedures are specified in terms of suitable versions of the Y operator. The techniques presented are general-purpose analysis and optimization tools, similar to well-known techniques used in the analysis and optimization of applicative languages, that combine synergistically to enable LIAR to generate identical machine code for ordinary recursive definitions written using
letrec
and those written using suitable forms of Y.
The Python compiler for CMU Common Lisp
Authors: MacLachlan Robert A.
Published: January 2005

The Python compiler for CMU Common Lisp has been under development for over five years, and now forms the core of a production quality public domain Lisp implementation. Python synthesizes the good ideas from Lisp compilers and source transformation systems with mainstream optimization and retargetability techniques. Novel features include strict type checking and source-level debugging of compiled code. Unusual attention has been paid to the compiler's user interface.
Tachyon Common Lisp
Authors: Nagasaka Atsushi , Shintani Yoshihiro , Ito Tanji , Gomi Hiroshi , Takahashi Junichi
Published: January 2005

Tachyon Common Lisp is an efficient and portable implementation of Common Lisp 2nd Edition. The design objective of Tachyon is to apply both advanced optimization technology developed for RISC processors and Lisp optimization techniques. The compiler generates very fast codes comparable to, and sometimes faster than the code generated by UNIX C compiler. Comparing with the most widely used commercial Common Lisp, Tachyon Common Lisp compiled code is 2 times faster and the interpreter is 6 times faster than the Lisp in Gabriel benchmark suit. Tachyon Common Lisp is the fastest among the Lisp systems known to the authors.
Dynamic program parallelization
Authors: Huelsbergen Lorenz , Larus James R.
Published: January 2005

Static program analysis limits the performance improvements possible from compile-time parallelization.
Dynamic program parallelization
shifts a portion of the analysis from complie-time to run-time, thereby enabling optimizations whose static detection is overly expensive or impossible.
Lambda tagging
and
heap resolution
are two new techniques for finding loop and non-loop parallelism in imperative, sequential languages with first-class procedures and destructive heap operations (
e.g.
, ML and Scheme).

Lambda tagging annotates procedures during compilation with a tag that describes the side effects that a procedure's application may cause. During program execution, the program refines and examines tags to identify computations that may safely execute in parallel. Heap resolution uses reference counts to dynamically detect potential heap aliases and to coordinate parallel access to shared structures. An implementation of lambda tagging and heap resolution in an optimizing ML compiler for a shared memory parallel computer demonstrates that the overhead incurred by these run-time methods is easily offset by dynamically-exposed parallelism and that non-trivial procedures can be automatically parallelized with these techniques.
Using *this-method* to plan and execute tasks in CLOS
Authors: Boyer Martin , Daneshmend Laeeque K. , Hayward Vincent
Published: January 2005

Advanced supervised/autonomous robotic systems may be characterized as large and long lived software environments, distributed over a large number of mechanical and computer subsystems. Appropriate hierarchical representations of such robotic systems are desirable, to facilitate system specification, implementation, and evolution. In the end product, this includes planning and programming of robotic tasks and recovery procedures, when tasks fail.
Eoops
Authors: Houser Chris , Kalter Scott D.
Published: January 2005

Eoops (Emacs OOP System) implements a Smalltalk-80-like language in GNU Emacs-Lisp (Lewis 90). Eoops is a simple but efficient compiler for a class-based, single inheritance, object-oriented language that uses explicit message passing for both method invocation and state access.This paper presents both a language description and a complete annotated implementation of Eoops. The reader of "The Eoops Language" section should be familiar with OOP, and ideally with Smalltalk-80. The reader of the "Implementation" section should be familiar with Common Lisp. Understanding some parts of the implementation requires knowledge of Emacs-Lisp.
The Scheme of things
Authors: Rees Jonathan
Published: January 2005

Most modern programming languages provide some way to define new types. Scheme doesn't. What gives?
*standard-output*
Authors: Steele Guy L.
Published: January 2005

ANSI Technical Committee X3J13 met on March 31 and April 1, 1992, to resolve outstanding issues in the draft proposal for Common Lisp. A few members had brought up some inconsistencies found at the last minute, and these were fairly easily resolved.
Continuation conscious compilation
Authors: Queinnec Christian
Published: January 2005

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.
PSD—a portable scheme debugger
Authors: Kellomäki Pertti
Published: January 2005

Psd is a portable debugger for the Scheme language. Debugging with Psd is accomplished by instrumenting the original source program. When the instrumented program is run, it presents the user with an interactive interface that lets him or her examine and change values of variables, set breakpoints, and single step evaluation. Psd is designed to be run within GNU Emacs, which is used for displaying the current source code position.
Macroexpand-All
Authors: Waters Richard C.
Published: January 2005

If you like to write Lisp macros, or even just use the macros other people write, you have no doubt felt the desire to see what particular macro calls expand into. The standard Common Lisp function
macroexpand
is very useful in this regard; however, since it only expands the topmost form in an expression, it does not necessarily show you the full result of a macro expansion.
Adventures in multiprocessing
Authors: Evans Shelly
Published: January 2005

This paper presents the multiprocessing architecture used to control the multiple window environment of a LISP-based Computer Aided Design tool. The multiprocessing control is implemented using the Lucid Common LISP Multitasking Facility. This paper will discuss the system motivation and goals, system architecture, and system development, including problems encountered, performance enhancements made, and areas for further improvement. This illustrates how using high-level, explicit LISP multitasking control within the LISP development environment can simplify the programmer's task.
Building common Lisp applications with reasonable performance
Authors: Boreczky John
Published: January 2005

This paper describes our experience with a number of methods that can be used to improve the performance of Common Lisp applications. These methods include vendor-independent optimizations such as recoding high traffic functions and vendor-dependent optimizations such as incremental loading. The results of these optimizations are quantified and compared.
SENEX; CLOS/CLIM in biomedical education
Authors: Ball Sheldon S. , Mah Vei H.
Published: January 2005

SENEX is a computer application in its fifth year of development focused on representation of molecular information, presentation of data, and reasoning with molecular information. It is written in a portable programming environment supported by Common Lisp, the Common Lisp Object System (CLOS), and the Common Lisp Interface Manager (CLIM). SENEX contains information about molecules, molecular events and disease processes, and provides tools for reasoning with and displaying this information in useful ways. This paper describes the architecture of SENEX and how that architecture facilitates development of a set a computer tools for education and research in molecular pathology. Several examples of how an individual might currently use SENEX to explore information related to the molecular basis of Alzheimer's disease are illustrated.
SKILL
Authors: Petrus Edwin S.
Published: January 2005

This paper describes an experience with Lisp as an extension language for a large electronics CAD environment and the role it plays in software design automation. This paper is not about extension languages in general, for an analysis of extension languages in CAD, see, [HNS90] and [Bar89]. Cadence is a full range supplier of software based Electronics CAD tools.
Sleeping with the enemy
Authors: Hodgkinson John R.
Published: January 2005

We examine the integration of Lisp and C in a commercial application, with a view towards the "proper place" of each language in large, practical applications in general. Topics addressed include portability, flexibility, efficiency, compactness, and user base of the two languages. We outline the pivotal role of Lisp-to-C translation tools in integration efforts. An attempt is made to dispel some half-truths about Lisp and inflated claims about C promulgated by interested parties.
Unifying software elements with LISP-based object-oriented technology
Authors: Fischer Markus
Published: January 2005

The paper describes the use of object-oriented techniques throughout all layers of software, in the design and the implementation phase. These techniques increase the productivity of the software engineer as well as the user's benefit from the application. Several tools and their interdependencies are described and supported with some examples. The resulting methodology is needed in order to match today's needs of innovative industrial users.
Lisp and portability
Authors: Egdorf H. W.
Published: January 2005

A primary mission of the Technology Modeling and Assessment group (A-7) of the Analysis Division of Los Alamos National Laboratory is to support the Department of Energy in performing analysis of both existing and future facilities that comprise the Nuclear Weapons Complex. Many of the questions to be addressed in relation to this mission involve an examination of the flow of material through a processing facility and the transformations of the material as it moves through the facility by the use of a discrete-event simulation tool.
A library of high level control operators
Authors: Queinnec Christian
Published: January 2005

Numerous high-level control operators, with various properties, exist in the literature. To understand or compare them is difficult since their definitions use quite different theoretical frameworks; moreover, to our knowledge, no implementation offers them all. This paper tries to explain control operators by the often simple stack manipulation they perform. We therefore present what we think these operators are, in an executable framework derived from abstract continuations. This library is published in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. For instance, we do not claim our implementation to be faithful nor we attempt to formally derive these implementations from their original definitions. The goal is to give a flavor of what control operators are, from an implementation point of view. Last but worth to say, all errors are mine.
Using Hindley-Milner type inference to optimise list representation
Authors: Hall Cordelia V.
Published: January 2005

Lists are a pervasive data structure in functional programs. The generality and simplicity of their structure makes them expensive. Hindley-Milner type inference and partial evaluation are all that is needed to optimise this structure, yielding considerable improvements in space and time consumption for some interesting programs. This framework is applicable to many data types and their optimised representations, such as lists and parallel implementations of bags, or arrays and quadtrees.
Space-efficient closure representations
Authors: Shao Zhong , Appel Andrew W.
Published: January 2005

Many modern compilers implement function calls (or returns) in two steps: first, a
closure
environment is properly installed to provide access for free variables in the target program fragment; second, the control is transferred to the target by a “jump with arguments (or results)”.
Closure conversion
, which decides where and how to represent closures at runtime, is a crucial step in compilation of functional languages. We have a new algorithm that exploits the use of compile-time control and data flow information to optimize closure representations. By extensive closure sharing and allocating as many closures in registers as possible, our new closure conversion algorithm reduces heap allocation by 36% and memory fetches for local/global variables by 43%; and improves the already-efficient code generated by the Standard ML of New Jersey compiler by about 17% on a DECstation 5000. Moreover, unlike most other approaches, our new closure allocation scheme satisfies the strong “safe for space complexity” rule, thus achieving good asymptotic space usage.
Tag-free garbage collection using explicit type parameters
Authors: Tolmach Andrew
Published: January 2005

We have constructed a practical tag-free garbage collector based on explicit type parameterization of polymorphic functions, for a dialect of ML. The collector relies on type information derived from an explicitly-typed 2nd-order representation of the program, generated by the compiler as a byproduct of ordinary Hindley-Milner type inference. Runtime type manipulations are performed lazily to minimize execution overhead. We present details of our implementation approach, and preliminary performance measurements suggesting that the overhead of passing type information explicitly can be made acceptably small.
Garbage collection for strongly-typed languages using run-time type reconstruction
Authors: Aditya Shail , Flood Christine H. , Hicks James E.
Published: January 2005

Garbage collectors perform two functions:
live-object detection
and
dead-object reclamation
. In this paper, we present a new technique for live-object detection based on run-time type reconstruction for a strongly typed, polymorphic language. This scheme uses compile-time type information together with the run-time tree of activation frames to determine the exact type of every object participating in the computation. These reconstructed types are then used to identify and traverse the live heap objects during garbage collection.

We describe an implementation of our scheme for the Id parallel programming language compiled for the *T multiprocessor architecture. We present simulation studies that compare the performance of type-reconstructing garbage collection with conservative garbage collection and compiler-directed storage reclamation.
Characterization of object behaviour in Standard ML of New Jersey
Authors: Stefanovic Darko , Moss J. Eliot B.
Published: January 2005

We describe a method of measuring lifetime characteristics of heap objects, and discuss ways in which such quantitative object behaviour measurements can help improve language implementations, especially garbage collection performance. For Standard ML of New Jersey, we find that certain primary aspects of object behaviour are qualitatively the same across benchmark programs, in particular the rapid object decay. We show that the heap-only allocation implementation model is the cause of this similarity. We confirm the weak generational hypothesis for SML/NJ and discuss garbage collector configuration tuning. Our approach is to obtain object statistics directly from program execution, rather than simulation, for reasons of simplicity and speed. Towards this end, we exploit the flexibility of the garbage collector toolkit as a measurement tool. Careful numerical analysis of the acquired data is necessary to arrive at relevant object lifetime measures. This study fills a gap in quantitative knowledge of the workings of heap-based compilers and their run-time systems, and should be useful to functional language implementors.
Signatures for a network protocol stack
Authors: Biagioni Edoardo , Harper Robert , Lee Peter , Milnes Brian G.
Published: January 2005

Advanced programming languages such as Standard ML have rarely been used for systems programming tasks such as operating systems and network communications. In order to understand more fully the requirements of systems programming, we have implemented a suite of industry-standard network communication protocols in a completely type-safe extension of Standard ML. While the implementation has only recently become operational, we already observe acceptable communications throughput. We make careful use of the Standard ML modules system, with the core component of the implementation being a signature which is generic to all communications protocols. This generic protocol is then specialized for specific protocols, and these are implemented by functors parameterized by generic protocols. This leads naturally to a layered system structure and also provides an important and useful “mix-and-match” capability in composing protocols into complex networking systems.

We have found the advanced features of Standard ML, in particular the modules system, static typing, and higher-order functions, to be extremely useful in building complex communications systems. The type compatibility of the various components of a system is guaranteed by the compiler. Furthermore, we find it significant that most of the information needed to understand the structure and interactions in our code can be obtained from a study of the signatures alone. Perhaps most important is that we have been able to use the expressive power of Standard ML modules to give concrete expression to previously
ad hoc
system-structuring concepts developed by other researchers in the field of network communications. For language designers and implementors, our experience has also pointed out specific areas for further work that may lead to advanced languages that are useful for systems programming.
Static dependent costs for estimating execution time
Authors: Reistad Brian , Gifford David K.
Published: January 2005

We present the first system for estimating and using data-dependent expression execution times in a language with first-class procedures and imperative constructs. The presence of first-class procedures and imperative constructs makes cost estimation a global problem that can benefit from type information. We estimate expression costs with the aid of an algebraic type reconstruction system that assigns every procedure a type that includes a static dependent cost. A
static dependent cost
describes the execution time of a procedure in terms of its inputs. In particular, a procedure's static dependent cost can depend on the size of input data structures and the cost of input first-class procedures. Our cost system produces symbolic cost expressions that contain free variables describing the size and cost of the procedure's inputs. At run-time, a cost estimate is dynamically computed from the statically determined cost expression and run-time cost and size information. We present experimental results that validate our cost system on three compilers and architectures. We experimentally demonstrate the utility of cost estimates in making dynamic parallelization decisions. In our experience, dynamic parallelization meets or exceeds the parallel performance of any fixed number of processors.
Talking about modules and delivery
Authors: Davis Harley , Parquier Pierre , Séniak Nitsan
Published: January 2005

Adding a module system to LISP enhances program security and efficiency, and help the programmer master the complexity of large systems, thus facilitating application and delivery. TALK's module system is based on a simple compilation model which takes macros into account and provides a solid basis for automatic module management tools. Higher-level structuring entities—libraries and executables—group modules into deliverable goods. The module system is secure because it validates interfaces, efficient because it separates compilation dependencies from execution dependencies, and useful because it offers a simple processing model, automatic tools, and a graceful transition from development to delivery.
Unrolling lists
Authors: Shao Zhong , Reppy John H. , Appel Andrew W.
Published: January 2005

Lists are ubiquitous in functional programs, thus supporting lists efficiently is a major concern to compiler writers for functional languages. Lists are normally represented as linked
cons
cells, with each
cons
cell containing a
car
(the data) and a
cdr
(the link); this is inefficient in the use of space, because 50% of the storage is used for links. Loops and recursions on lists are slow on modern machines because of the long chains of control dependencies (in checking for
nil
) and data dependencies (in fetching
cdr
fields).

We present a data structure for “unrolled lists”, where each cell has several data items (
car
fields) and one link (
cdr
). This reduces the memory used for links, and it significantly shortens the length of control-dependence and data-dependence chains in operations on lists.

We further present an efficient compile-time analysis that transforms programs written for “ordinary” lists into programs on unrolled lists. The use of our new representation requires no change to existing programs.

We sketch the proof of soundness of our analysis—which is based on
refinement types
—and present some preliminary measurements of our technique.
Complete proof systems for algebraic simply-typed terms
Authors: Cosmadakis Stavros S.
Published: January 2005

We show that reasoning by case analysis (on whether subprograms diverge or converge) is complete for proving PCF observational congruences of algebraic terms. The latter are applicative combinations of first-order variables and a constant Ω denoting a diverging program of base type. A restricted version of the logic is complete for proving equality of algebraic terms in the full continuous type hierarchy (equivalently, observational congruence in PCF with parallel conditional). We show that the provability in the latter logic is in co-NP. We also give complete equational proof systems for a subclass of algebraic terms; provability in these systems is in linear time.
Continuation-based partial evaluation
Authors: Lawall Julia L. , Danvy Olivier
Published: January 2005

Binding-time improvements aim at making partial evaluation (a.k.a. program specialization) yield a better result. They have been achieved so far mostly by hand-transforming the source program. We observe that as they are better understood, these hand-transformations are progressively integrated into partial evaluators, thereby alleviating the need for source-level binding-time improvements.

Control-based binding-time improvements, for example, follow this pattern: they have evolved from ad-hoc source-level rewrites to a systematic source-level transformation into continuation-passing style (CPS). Recently, Bondorf has explicitly integrated the CPS transformation into the specializer, thus partly alleviating the need for source-level CPS transformation. This CPS integration is remarkably effective but very complex and goes beyond a simple CPS transformation. We show that it can be achieved directly by using the control operators shift and reset, which provide access to the current continuation as a composable procedure.

We automate, reproduce, and extend Bondorf's results, and describe how this approach scales up to hand-writing partial-evaluation compilers. The first author has used this method to bootstrap the new release of Consel's partial evaluator Schism. The control operators not only allow the partial evaluator to remain in direct style, but also can speed up partial evaluation significantly.
A practical soft type system for Scheme
Authors: Wright Andrew K. , Cartwright Robert
Published: January 2005

Soft typing
is a generalization of static type checking that accommodates both dynamic typing and static typing in one framework. A soft type checker infers types for identifiers and inserts explicit run-time checks to transform untypable programs into typable form.
Soft Scheme
is a practical soft type system for R4RS Scheme. The type checker uses a representation for types that is expressive, easy to interpret, and supports efficient type inference. Soft Scheme supports all of R4RS Scheme, including uncurried procedures of fixed and variable arity, assignment, and continuations.
Towards better inlining decisions using inlining trials
Authors: Dean Jeffrey , Chambers Craig
Published: January 2005

Inlining trials are a general mechanism for making better automatic decisions about whether a routine is profitable to inline. Unlike standard source-level inlining heuristics, an inlining trial captures the effects of optimizations applied to the body of the inlined routine when calculating the costs and benefits of inlining. The results of inlining trials are stored in a persistent database to be reused when making future inlining decisions at similar call sites. Type group analysis can determine the amount of available static information exploited during compilation, and the results of analyzing the compilation of an inlined routine help decide when a future call site would lead to substantially the same generated code as a given inlining trial. We have implemented inlining trials and type group analysis in an optimizing compiler for SELF, and by making wiser inlining decisions we were able to cut compilation time and compiled code space with virtually no loss of execution speed. We believe that inlining trials and type group analysis could be applied effectively to many high-level languages where procedural or functional abstraction is used heavily.
In-place updates in the presence of control operators
Authors: Biswas Sandip K.
Published: January 2005

This paper presents a formal account of the concept of in-place updates in purely functional languages. In purely functional languages, updates of abstract objects involve creating duplicates of these objects. This paper reviews static conditions, which, if satisfied by λ-terms, guarantee that, even if updates are performed in-place, the purely functional semantics is retained. These static conditions, however, fail to guarantee the requisite safety in the presence of control operators like
callcc
and
throw
. The conditions are hence augmented by another condition which is defined on the operational semantics. Here we statically verify the satisfiability of a conservative approximation of this condition by data-flow analysis on
CPS
-terms. Also a significant class of programs is identified for which the condition holds even without data-flow analysis.
Set-based analysis of ML programs
Authors: Heintze Nevin
Published: January 2005

Reasoning about program variables as sets of “values” leads to a simple, accurate and intuitively appealing notion of program approximation. This paper presents approach for the compile-time analysis of ML programs. To develop the core ideas of the analysis, we consider a simple untyped call-by-value functional language. Starting with an operational semantics for the language, we develop an approximate “set-based” operational semantics, which formalizes the intuition of treating program variables as sets. The key result of the paper is an
O
(
n
3
) algorithm for computing the set based approximation of a program. We then extend this analysis in a natural way to deal with arrays, arithmetic, exceptions and continuations. We briefly describe our experience with an implementation of this analysis for ML programs.
An equational framework for the flow analysis of higher order functional programs
Authors: Stefanescu Dan , Zhou Yuli
Published: January 2005

We present a simple method for the general flow analysis of high-order functional programs. The method computes an abstraction of the program's runtime environment via a system of monotonic equations. As the environment can grow unbounded, we exploit patterns in the program's control structure (i.e., the call-tree) to determine some static partition of the environment, and merge points in the environment belonging to the same equivalent-class. High order functions are handled by embedding control information into closures. The method is proven correct with respect to a rewriting system based operational semantics. Various implementation issues are also considered.