Most functional languages rely on some kind of garbage collection for automatic memory management. They usually eschew reference counting in favor of a tracing garbage collector, which has less bookkeeping overhead at...
详细信息
ISBN:
(纸本)9781450375627
Most functional languages rely on some kind of garbage collection for automatic memory management. They usually eschew reference counting in favor of a tracing garbage collector, which has less bookkeeping overhead at runtime. On the other hand, having an exact reference count of each value can enable optimizations such as destructive updates. We explore these optimization opportunities in the context of an eager, purely functional programming language. We propose a new mechanism for efficiently reclaiming memory used by nonshared values, reducing stress on the global memory allocator. We describe an approach for minimizing the number of reference counts updates using borrowed references and a heuristic for automatically inferring borrow annotations. We implemented all these techniques in a new compiler for an eager and purely functional programming language with support for multi-threading. Our preliminary experimental results demonstrate our approach is competitive and often outperforms state-of-the-art compilers.
Most functional languages rely on some kind of garbage collection for automatic memory management. They usually eschew reference counting in favor of a tracing garbage collector, which has less bookkeeping overhead at...
详细信息
ISBN:
(纸本)9781450375627
Most functional languages rely on some kind of garbage collection for automatic memory management. They usually eschew reference counting in favor of a tracing garbage collector, which has less bookkeeping overhead at runtime. On the other hand, having an exact reference count of each value can enable optimizations such as destructive updates. We explore these optimization opportunities in the context of an eager, purely functional programming language. We propose a new mechanism for efficiently reclaiming memory used by nonshared values, reducing stress on the global memory allocator. We describe an approach for minimizing the number of reference counts updates using borrowed references and a heuristic for automatically inferring borrow annotations. We implemented all these techniques in a new compiler for an eager and purely functional programming language with support for multi-threading. Our preliminary experimental results demonstrate our approach is competitive and often outperforms state-of-the-art compilers.
We present a purelyfunctional implementation of search trees that requires O(log n) time for search and update operations and supports the join of two trees in worst case constant time. Hence, we solve an open proble...
详细信息
ISBN:
(纸本)3540388753
We present a purelyfunctional implementation of search trees that requires O(log n) time for search and update operations and supports the join of two trees in worst case constant time. Hence, we solve an open problem posed by Kaplan and Tarjan as to whether it is possible to envisage a data structure supporting simultaneously the join operation in O(1) time and the search and update operations in O(log n) time.
Cody, Hazel, and Theo, two experienced Haskell programmers and an expert in automata theory, develop an elegant Haskell program for matching regular expressions: (i) the program is purelyfunctional;(ii) it is overloa...
详细信息
ISBN:
(纸本)9781605587943
Cody, Hazel, and Theo, two experienced Haskell programmers and an expert in automata theory, develop an elegant Haskell program for matching regular expressions: (i) the program is purelyfunctional;(ii) it is overloaded over arbitrary semirings, which not only allows to solve the ordinary matching problem but also supports other applications like computing leftmost longest matchings or the number of matchings, all with a single algorithm;(iii) it is more powerful than other matchers, as it can be used for parsing every context-free language by taking advantage of laziness. The developed program is based on an old technique to turn regular expressions into finite automata which makes it efficient both in terms of worst-case time and space bounds and actual performance: despite its simplicity, the Haskell implementation can compete with a recently published professional C++ program for the same problem.
This paper presents an analysis of a type theory, which serves as a solid foundation for usage of the derivation system in Coq proof assistant. An overview of the extension path from simply typed lambda calculus to Ca...
详细信息
ISBN:
(纸本)9781538671962
This paper presents an analysis of a type theory, which serves as a solid foundation for usage of the derivation system in Coq proof assistant. An overview of the extension path from simply typed lambda calculus to Calculus of Inductive Constructions provides important insights about the type system of highly expressive functionalprogramming language inside Coq, called Gallina. The correspondence between type theory expressions and Coq constructions is established.
暂无评论