Adding a module system to lisp enhances program security and efficiency, and help the programmer master the complexity of large systems, thus facilitating application delivery. Talk's module system is based on a s...
详细信息
ISBN:
(纸本)0897916433
Adding a module system to lisp enhances program security and efficiency, and help the programmer master the complexity of large systems, thus facilitating application 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.
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 perf...
详细信息
ISBN:
(纸本)0897916433
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.
A tight, transparent, and portable integration between C++ and lisp is desirable and feasible. This paper describes the C++ interface supplied with [6], a modern lisp dialect which extends the proposed ISlisp standard...
详细信息
ISBN:
(纸本)0897916433
A tight, transparent, and portable integration between C++ and lisp is desirable and feasible. This paper describes the C++ interface supplied with [6], a modern lisp dialect which extends the proposed ISlisp standard with a module system [3], a metaobject protocol, and an extensive set of libraries. The interface parses C++ header files and generates C++ stub interface files, as well as Talk modules which implement proxy classes and Talk foreign function definitions for C++ functions. The programmer then has nearly complete access to the functionality of a C++ library.
An ML-style type system with variable-arity procedures is defined that supports both optional arguments and arbitrarily-long argument sequences. A language with variable-arity procedures is encoded in a core-ML varian...
详细信息
ISBN:
(纸本)0897916433
An ML-style type system with variable-arity procedures is defined that supports both optional arguments and arbitrarily-long argument sequences. A language with variable-arity procedures is encoded in a core-ML variant with infinitary tuples. We present an algebra of infinitary tuples and solve its unification problem. The resulting type discipline preserves principal typings and has a terminating type reconstruction algorithm. The expressive power of infinitary tuples is illustrated.
We describe an analysis of a parallel language in which processes communicate via first-class mutable shared locations. The sequential core of the language defines a higher-order strict functional language with list d...
详细信息
ISBN:
(纸本)0897916433
We describe an analysis of a parallel language in which processes communicate via first-class mutable shared locations. The sequential core of the language defines a higher-order strict functional language with list data structures. The parallel extensions permit processes and shared locations to be dynamically created;synchronization among processes occurs exclusively via shared locations. The analysis is defined by an abstract interpretation on this language. The interpretation is efficient and useful, facilitating a number of important optimizations related to synchronization, processor/thread mapping, and storage management.
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 t...
详细信息
ISBN:
(纸本)0897916433
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 to 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.
In our recent paper [22], we gave an efficient interprocedural update analysis algorithm for strict functional languages with flat arrays and sequential evaluation. In this paper, we show that the same algorithm exten...
详细信息
ISBN:
(纸本)0897916433
In our recent paper [22], we gave an efficient interprocedural update analysis algorithm for strict functional languages with flat arrays and sequential evaluation. In this paper, we show that the same algorithm extends to a parallel functional language with additional constructs for partitioning and combining arrays. Even with parallel evaluation, the complexity of the analysis remains polynomial. The analysis has been implemented and the results show that several numerical algorithms such as direct and iterative methods for solving linear equations, LU, Cholesky, and QR factorizations, multigrid methods for solving partial differential equations, and non-numeric algorithms such as sorting can be implemented functionally with all updates made destructive. We describe a new array construct to specify a collection of updates on an array and show that problems like histogram, inverse permutation, and polynomial multiplication have efficient parallel functional solutions. Monolithic array operators can be considered as a special case of this new construct.
The array update problem in the implementation of a purely functional language is the following: once an array is updated, both the original array and the newly updated one must be preserved to maintain referential tr...
详细信息
ISBN:
(纸本)0897916433
The array update problem in the implementation of a purely functional language is the following: once an array is updated, both the original array and the newly updated one must be preserved to maintain referential transparency. Previous approaches have mainly based on the detection or enforcement of single-threaded accesses to an aggregate, by means of compiler-time analyses or language restrictions. These approaches cannot deal with aggregates which are updated in a multi-threaded manner. Baker's shallow binding scheme can be used to implement multi-threaded functional arrays. His scheme, however, can be very expensive if there are repeated alternations between long binding paths. We design a scheme that fragments binding paths randomly. The randomization scheme is on-line, simple to implement, and its expected performance comparable to that of the optimal off-line solutions. All this is achieved without using compiler-time analyses, and without restricting the languages. The expected performance of the randomization scheme is analyzed in details, and some preliminary results are shown. Applications of the randomization technique to other functional aggregates, as well as its implications, are briefly outlined.
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 o...
详细信息
ISBN:
(纸本)0897916433
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.
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...
详细信息
ISBN:
(纸本)0897916433
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.
暂无评论