We present an extension of Scala that supports constraint programming.over bounded and unbounded domains. The resulting language, Kaplan, provides the benefits of constraint programming.while preserving the existing f...
详细信息
ISBN:
(纸本)9781450310833
We present an extension of Scala that supports constraint programming.over bounded and unbounded domains. The resulting language, Kaplan, provides the benefits of constraint programming.while preserving the existing features of Scala. Kaplan integrates constraint and imperative programming.by using constraints as an advanced control structure;the developers use the monadic 'for' construct to iterate over the solutions of constraints or branch on the existence of a solution. The constructs we introduce have simple semantics that can be understood as explicit enumeration of values, but are implemented more efficiently using symbolic reasoning. Kaplan programs can manipulate constraints at run-time, with the combined benefits of type-safe syntax trees and first-class functions. The language of constraints is a functional subset of Scala, supporting arbitrary recursive function definitions over algebraic data types, sets, maps, and integers. Our implementation runs on a platform combining a constraint solver with a standard virtual machine. For constraint solving we use an algorithm that handles recursive function definitions through fair function unrolling and builds upon the state-of-the art SMT solver Z3. We evaluate Kaplan on examples ranging from enumeration of data structures to execution of declarative specifications. We found Kaplan promising because it is expressive, supporting a range of problem domains, while enabling full-speed execution of programs that do not rely on constraint programming.
Danvy's functional unparsing problem (Danvy in J. Funct. Program. 8(6), 621- 625, 1998) is to implement a type-safe 'printf' function, which converts a sequence of heterogeneous arguments to a string accor...
详细信息
We study the problem of automatically analyzing the worst-case resource usage a procedures with several arguments. Existing automatic analyses based or. amortization, or sized types bound the resource usage or result ...
详细信息
ISBN:
(纸本)9781450304900
We study the problem of automatically analyzing the worst-case resource usage a procedures with several arguments. Existing automatic analyses based or. amortization, or sized types bound the resource usage or result site of such a procedure by a sum of unary functions of the sizes of the arguments. In this paper we generalize this to arbitrary multivariate polynomial functions thus allowing bounds of the form inn which had to be grossly overestimated t y m(2) + n(2) before. Our framework even encompasses bounds like Sigma(i,j <= n) m(i)m(j) where the m(i) are the sizes of the entries of a list of length n. This allows us for the first time to derive useful resource bounds for operations on matrices that are represented as lists of lists and to considerably improve founds on other super-linear operations on lists such as longest common subsequence and removal of duplicates from lists of lists. Furthermore, resource bounds are now closed under composition which improves accuracy of the analysis of composed programs which some or all of the components exhibit super-linear resource or she behavior. The analysis is based or, a novel multivariate amortized resource analysis. We present it in form of a type system for a simple first-order functional language with lists and trees, prove soundness, and describe automatic type inference based on linear programming. We have experimentally validated the automatic analysis on a wide range of examples from functionalprogramming.with lists and trees. The obtained bounds were compared with actual resource consumption. All bounds were asymptotically tight, and the constants were close or even identical to the optimal ones.
The Manticore project is an effort to design and implement a new functional language for parallel programming. Unlike many earlier parallel languages, Manticore is a heterogeneous language that supports parallelism at...
详细信息
ISBN:
(纸本)1595936904
The Manticore project is an effort to design and implement a new functional language for parallel programming. Unlike many earlier parallel languages, Manticore is a heterogeneous language that supports parallelism at multiple levels. Specifically, we combine CML-style explicit concurrency with NESL/Nepal-style data-parallelism. In this paper, we describe and motivate the design of the Manticore language. We also describe a flexible runtime model that supports multiple scheduling disciplines (e.g., for both fine-grain and course-grain parallelism) in a uniform framework. Work on a prototype implementation is ongoing and we give a status report. Copyright 2007 acm.
We propose a new computation model which combines the operational principles of functional languages (reduction), logic languages (non-deterministic search for solutions), and integrated functional logic languages (re...
详细信息
We propose a new computation model which combines the operational principles of functional languages (reduction), logic languages (non-deterministic search for solutions), and integrated functional logic languages (residuation and narrowing). This computation model combines efficient evaluation principles of functional languages with the problem-solving capabilities of logic programming. Since the model allows the delay of function calls which are not sufficiently instantiated, it also supports a concurrent style of programming. We provide soundness and completeness results and show that known evaluation principles of functional logic languages are particular instances of this model. Thus, our model is a suitable basis for future declarative programming.languages.
The future annotations of Multilisp provide a simple method for taming the implicit parallelism of functional programs. Past research concerning futures has focused on implementation issues. In this paper, we present ...
详细信息
The future annotations of Multilisp provide a simple method for taming the implicit parallelism of functional programs. Past research concerning futures has focused on implementation issues. In this paper, we present a series of operational semantics for an idealized functional language with futures with varying degrees of intensionality. We develop a set-based analysis algorithm from the most intensional semantics, and use that algorithm to perform touch optimization on programs. Experiments with the Gambit compiler indicates that this optimization substantially reduces program execution times.
We exhibit a set of functions coded in Haskell that can be used as building blocks to construct a variety of interpreters for lisp-like languages. The building blocks are joined merely through functional composition. ...
详细信息
ISBN:
(纸本)0897916360
We exhibit a set of functions coded in Haskell that can be used as building blocks to construct a variety of interpreters for lisp-like languages. The building blocks are joined merely through functional composition. Each building block contributes code to support a specific feature, such as numbers, continuations, functions calls, or nondeterminism. The result of composing some number of building blocks is a parser, an interpreter, and a printer that support exactly the expression forms and data types needed for the combined set of features, and no more.
Narrowing is the operational principle of languages that integrate functional and logic programming. We propose a notion of a needed narrowing step that, for inductively sequential rewrite systems, extends the Huet an...
详细信息
ISBN:
(纸本)0897916360
Narrowing is the operational principle of languages that integrate functional and logic programming. We propose a notion of a needed narrowing step that, for inductively sequential rewrite systems, extends the Huet and Levy notion of a needed reduction step. We define a strategy, based on this notion, that computes only needed narrowing steps. Our strategy is sound and complete for a large class of rewrite systems, is optimal w.r.t. the cost measure that counts the number of distinct steps of a derivation, computes only independent unifiers, and is efficiently implemented by pattern matching.
In Milner's polyadic π-calculus there is a notion of sorts which is analogous to the notion of types in functionalprogramming. As a well-typed program applies functions to arguments in a consistent way, a well-s...
详细信息
ISBN:
(纸本)0897915607
In Milner's polyadic π-calculus there is a notion of sorts which is analogous to the notion of types in functionalprogramming. As a well-typed program applies functions to arguments in a consistent way, a well-sorted process uses communication channels in a consistent way. An open problem is whether there is an algorithm to infer sorts in the π-calculus in the same way that types can be inferred in functionalprogramming. Here we solve the problem by presenting an algorithm which infers the most general sorting for a process in the first-order calculus, and proving its correctness. The algorithm is similar in style to those used for Hindley-Milner type inference in functional languages.
暂无评论