This paper describes the principles underlying an efficient implementation of a lazy functional language, compiling to code for ordinary computers. It is based on combinator-like graph reduction: the user defined func...
详细信息
This paper describes the principles underlying an efficient implementation of a lazy functional language, compiling to code for ordinary computers. It is based on combinator-like graph reduction: the user defined functions are used as rewrite rules in the graph. Each function is compiled into an instruction sequence for an abstract graph reduction machine, called the G-machine, the code reduces a function application graph to its value. The G-machine instructions are then translated into target code. Speed improvements by almost two orders of magnitude over previous lazy evaluators have been measured;we provide some performance figures.
Contexts have been proposed as a means of performing strictness analysis on non-flat domains. Roughly speaking, a context describes how much a sub-expression will be evaluated by the surrounding program. This paper sh...
详细信息
Martin-Löf's type theory contains a logic, a specification language and a programming language, so it is a tool with different uses. Although it is traditionally used as an integrated programming logic, it ma...
详细信息
We present a method for computing the number of steps needed to compute a lazy first order functional program e (to an approximation of its value). The method itself is described as a lazy functional program. Moreover...
详细信息
ISBN:
(纸本)0897913280
We present a method for computing the number of steps needed to compute a lazy first order functional program e (to an approximation of its value). The method itself is described as a lazy functional program. Moreover, it is compositional, because it is denned by recursion on the structure of e. In other words, the number of steps needed to compute e is described in terms of the number of steps the parts of e need. (This is in contrast with the obvious operational method to define an interpreter and count the number of steps that it needs.) The equations that define the analysing program can also be used when reasoning about time complexity of lazy functional programs. Two simple examples are given at the end of the paper.
A method is proposed to search for an identifier in a functional program library by using its Hindley-Milner type as a key. This can be seen as an approximation of using the specification as a key. Functions that only...
Domain algebras are proposed as a tool for structuring compiler correctness proofs which are based on denotational semantics of the source and target language. The correctness of a compiler for a small imperative lang...
详细信息
Networks of communicating processes can be viewed as networks of stream transformers and programmed in a lazy functional language. Thus the correctness of concurrent systems can be reduced to the correctness of functi...
详细信息
Structural (manual or automated) testing today often overlooks typical programming faults because of inherent flaws in the simple criteria applied (e.g. branch or all-uses). Dedicated testing strategies that address s...
详细信息
暂无评论