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.
This paper gives a method to extract redundancy free programs from constructive proofs, using the read-ability interpretation. The proof trees are analyzed in the style of program analysis, and they are mechani-cally ...
详细信息
LogScheme is an experiment in adding the main features of logic programming, nondeterminism and unification, into the (mostly) functional language Scheme. We use a minimalist approach, based on the observation that no...
详细信息
A method is proposed to search for an identifier by using its type as a key. This can be seen as an approximation of using the specification as a key. Functions that only differ in their currying or argument order are...
详细信息
Many programming environments make use data representations which are not native to the underlying hardware. Both untyped languages, such as Lisp or Scheme, and languages with static polymorphic typechecking, such as ...
One way to analyse programs is to to derive expressions for their computational behaviour. A time bound function (or worst-case complexity) gives an upper bound for the computation time as a function of the size of in...
详细信息
In this work we explore three modifications to the architecture of a Data-Driven VLSI array of processors, previously introduced in [1]. These modifications are geared towards improving the array utilization, as well ...
详细信息
We have implemented a parallel graph reducer on a commercially available shared memory multiprocessor (a Sequent Symmetry™), that achieves real speedup compared to a a fast compiled implementation of the conventional ...
详细信息
This paper addresses the declarative and computational issues of incorporating set abstraction into functional and logic programminglanguages. The main results are the following: (i) Relative set abstraction can comb...
详细信息
Relational programming is a generalization of functionalprogramming that includes aspects of logic programming. We describe a relational language, Drusilla, that retains the lazy, polymorphic and higher-order aspects...
详细信息
ISBN:
(纸本)089791595X
Relational programming is a generalization of functionalprogramming that includes aspects of logic programming. We describe a relational language, Drusilla, that retains the lazy, polymorphic and higher-order aspects of functionallanguages and the flexible handling of non-determinism and search based computation of logic languages. As a result it offers certain economy of expression not found in functional or logic programming. However a complex implementation, using a combination of polymorphic type inference and automatic program transformation to select appropriate representations, is needed to support this language.
暂无评论