In non-strict functionallanguages, a data structure may be read before all its components are written, and a function may return a value before finishing all its computation or even before all its arguments have been...
详细信息
Observationally equivalent programs are programs which are indistinguishable in all contexts, as far as their termination property is concerned. In this paper, we present rules preserving observational equivalence, fo...
详细信息
ISBN:
(纸本)089791595X
Observationally equivalent programs are programs which are indistinguishable in all contexts, as far as their termination property is concerned. In this paper, we present rules preserving observational equivalence, for the parallel evaluation of programs using call/cc. These rules allow the capture of continuations in any applicative context and they prevent from aborting the whole computation when a continuation is applied in the extent of the call/cc by which it was reified. As a consequence, these results prove that one can design a functional language with first-class continuations which has transparent constructs for parallelism.
This paper presents our practical experience gained from writing image processing programs in lazy functionallanguages. We give some benchmarking results comparing median filter operations written in C, Miranda and H...
详细信息
ISBN:
(纸本)089791595X
This paper presents our practical experience gained from writing image processing programs in lazy functionallanguages. We give some benchmarking results comparing median filter operations written in C, Miranda and Haskell. (The median filter is a common method for removing noise from images.) Also, using a profiling tool, we achieve remarkable improvement of the Haskell code. In particular, we show that the Haskell program runs in constant space, which is difficult to achieve in C without extra programming effort. Although the performance of lazy functional language is beginning to make them feasible for specific purposes such as rapid prototyping, better compilers and tools are still needed to encourage wider use in image processing applications.
The aggregate update problem in functionallanguages is concerned with detecting cases where a functional array or record update operation can be implemented destructively in constant time. Previous work on this probl...
详细信息
ISBN:
(纸本)089791595X
The aggregate update problem in functionallanguages is concerned with detecting cases where a functional array or record update operation can be implemented destructively in constant time. Previous work on this problem has assumed a fixed order of evaluation of expressions. In this paper we devise a practical analysis, for first order strict functionallanguages with flat aggregates, that derives a good order of evaluation for making the updates destructive. We show that for programs with no aliasing, our analysis is more precise than Hudak's abstract reference counting, even if the fixed order of evaluation assumed by Hudak happens to be the right order. We also show that our analysis algorithm runs in polynomial time, and in close to linear time for typical programs. To the best of our knowledge, all previous algorithms of this kind require exponential time.
Program fragments in functionallanguages may be observationally congruent in a language without effects (continuations, state, exceptions) but not in an extension with effects. We give a generic way to preserve pure ...
详细信息
ISBN:
(纸本)089791595X
Program fragments in functionallanguages may be observationally congruent in a language without effects (continuations, state, exceptions) but not in an extension with effects. We give a generic way to preserve pure functional congruences by means of an effects delimiter. The effects delimiter is defined semantically using the retraction techniques of [14], but can also be given an operational semantics. We show that the effects delimiter restores observational congruences between purely functional pieces of code, thus achieving a modular separation between the purely functional language and its extensions.
This paper describes how a general purpose programming language supporting the notion of data abstraction can be used as a data definition and manipulation language for database management systems. The examples used h...
详细信息
ISBN:
(纸本)9781450379212
This paper describes how a general purpose programming language supporting the notion of data abstraction can be used as a data definition and manipulation language for database management systems. The examples used here are based on a functional data model and on a database system called NDB. However, the approach is not limited to or biased towards any particular data model or architecture. The strong typing properties of the data abstraction language are carried over to the realm of database manipulation operations and provide useful consistency checking. The advantage of the approach is that the user deals with but one database programming language, thereby avoiding a separate query and host language.
Register transfer languages are inadequate as a convenient mathematical formalism which will facilitate the description, analysis, and synthesis of digital systems at various levels of complexity. functional programmi...
详细信息
Register transfer languages are inadequate as a convenient mathematical formalism which will facilitate the description, analysis, and synthesis of digital systems at various levels of complexity. functionalprogramming is considered as an alternative, where the functions correspond to basic modules of combinational logic and the functionals represent the interconnections of these modules. That information which constitutes memory is represented as elements of sequences. Several examples are given, along with a methodology for synthesis.
A new view of the high level computerarchitecture is introduced. Language theoretical concepts are applied to digital systems engineering in a manner which allows for more complete understanding of the direct executi...
详细信息
A new view of the high level computerarchitecture is introduced. Language theoretical concepts are applied to digital systems engineering in a manner which allows for more complete understanding of the direct execution machine. This new understanding places more emphasis on the system controller in the selection of the directly executed language. Direct execution system controller specification for any regular high level language is considered.
The design and implementation of a simulator for on-line arithmetic algorithms are described. The simulator evaluates arithmetic expressions given in a highly functional form. Presently, the set of operations supporte...
详细信息
The design and implementation of a simulator for on-line arithmetic algorithms are described. The simulator evaluates arithmetic expressions given in a highly functional form. Presently, the set of operations supported include addition, subtraction, multiplication, division, and square root. Several examples are presented to illustrate the usage of the simulator. The simulator package is implemented in 'C' language on a VAX 11/780 system.
This paper describes a method for eliminating a certain class of space leaks in lazy functionallanguages. A program that space leaks consumes more memory than would be expected. This may lead to longer execution time...
详细信息
ISBN:
(纸本)089791595X
This paper describes a method for eliminating a certain class of space leaks in lazy functionallanguages. A program that space leaks consumes more memory than would be expected. This may lead to longer execution time, or that the program unnecessarily runs out of memory. It has been known for a long time that functions returning tuples may give rise to space leaks. Hughes [Hug83] has shown that some programs must leak memory, if a sequential evaluator is used. Several researchers have tried to solve this problem, with varying approaches, by introducing the necessary parallelism. Some of them modify the garbage collector, or use special operators to parallelize the programs explicitly. The approach used here is to use pattern bindings in definitions, which are available in most functionallanguages, to control the parallelism. No modification of the garbage collector or special operators are needed. The method has been implemented in the Chalmers LML/HBC compiler [AJ93, AJ89].
暂无评论