A long-standing problem in logic programming is how to cleanly separate logic and control. While solutions exist, they fall short in one of two ways: some are too intrusive, because they require significant changes to...
详细信息
ISBN:
(纸本)9781450329477
A long-standing problem in logic programming is how to cleanly separate logic and control. While solutions exist, they fall short in one of two ways: some are too intrusive, because they require significant changes to Prolog's underlying implementation;others are lacking a clean semantic grounding. We resolve both of these issues in this paper. We derive a solution that is both lightweight and principled. We do so by starting from a functional specification of Prolog based on monads, and extend this withthe effect handlers approach to capture the dynamic search tree as syntax. Effect handlers then express heuristics in terms of tree transformations. Moreover, we can declaratively express many heuristics as trees themselves that are combined with search problems using a generic entwining handler. Our solution is not restricted to a functional model: we show how to implement this technique as a library in Prolog by means of delimited continuations.
We present a translation scheme from a pure functional domain-specific language (DSL) to C. the over-arching idea of this scheme is to preserve the structure of the input program as much as possible. this includes, am...
详细信息
ISBN:
(纸本)9781450329477
We present a translation scheme from a pure functional domain-specific language (DSL) to C. the over-arching idea of this scheme is to preserve the structure of the input program as much as possible. this includes, among other things, to refrain from inlining user-written functions and to retain variable names as much as possible. We apply this translation scheme to GDSL, a DSL used for the specification of decoders for machine instructions. GDSL offers non-trivial language features such as monadic actions that our translation scheme maps one-to-one to C statements, resulting in code that closely resembles hand-written C code. Indeed, it is feasible to debug and profile the program at the C level and to interface the generated code with existing C code without marshaling data. Our translation scheme is therefore an attractive starting point for a light-weight DSL since no other language-specific tools besides the compiler are necessary. Moreover, the generated code is amenable to compiler optimizations found in off-the-shelf C compilers. this is illustrated by the performance achieved by a decoder for x86 machine instructions implemented in GDSL which is as fast as a production-quality decoding library shipped by Intel.
Higher-order constructs extend the expressiveness of firstorder (Constraint) Logic programming ((C) LP) both syntactically and semantically. At the same time assertions have been in use for some time in (C) LP systems...
详细信息
ISBN:
(纸本)9781450329477
Higher-order constructs extend the expressiveness of firstorder (Constraint) Logic programming ((C) LP) both syntactically and semantically. At the same time assertions have been in use for some time in (C) LP systems helping programmers detect errors and validate programs. However, these assertion-based extensions to (C) LP have not been integrated well with higher-order to date. this paper contributes to filling this gap by extending the assertion-based approach to error detection and program verification to the higher-order context within (C) LP. We propose an extension of properties and assertions as used in (C) LP in order to be able to fully describe arguments that are predicates. the extension makes the full power of the assertion language available when describing higher-order arguments. We provide syntax and semantics for (higher-order) properties and assertions, as well as for programs which contain such assertions, including the notions of error and partial correctness. We also discuss several alternatives for performing run-time checking of such programs.
Different XML formats are widely used for data exchange and processing, being often necessary to mutually convert between them. Standard XML transformation languages, like XSLT or XQuery, are unsatisfactory for this p...
详细信息
ISBN:
(纸本)9781450329477
Different XML formats are widely used for data exchange and processing, being often necessary to mutually convert between them. Standard XML transformation languages, like XSLT or XQuery, are unsatisfactory for this purpose since they require writing a separate transformation for each direction. Existing bidirectional transformation languages mean to cover this gap, by allowing programmers to write a single program that denotes both transformations. However, they often 1) induce a more cumbersome programming style than their traditionally unidirectional relatives, to establish the link between source and target formats, and 2) offer limited configurability, by making implicit assumptions about how modifications to both formats should be translated that may not be easy to predict. this paper proposes a bidirectional XML update language called BIFLUX (BIdirectional FunctionaL Updates for XML), inspired by the FLUX XML update language. Our language adopts a novel bidirectional programming by update paradigm, where a program succinctly and precisely describes how to update a source document with a target document, in an intuitive way, such that there is a unique " inverse" source query for each update program. BIFLUX extends FLUX with bidirectional actions that describe the connection between source and target formats. We introduce a core BIFLUX language, with a clear and well-behaved bidirectional semantics and a decidable static type system based on regular expression types.
this paper proposes an efficient parallel algorithm for an important class of dynamic programming problems that includes Viterbi, Needleman-Wunsch, Smith-Waterman, and Longest Common Subsequence. In dynamic programmin...
详细信息
We introduce a new approach to automatically extract an idealized logical structure from a parallel execution trace. We use this structure to define intuitive metrics such as the lateness of a process involved in a pa...
详细信息
ISBN:
(纸本)9781450326568
We introduce a new approach to automatically extract an idealized logical structure from a parallel execution trace. We use this structure to define intuitive metrics such as the lateness of a process involved in a parallel execution. By analyzing and illustrating traces in terms of logical steps, we leverage a developer's understanding of the happened-before relations in a parallel program. this technique can uncover dependency chains, elucidate communication patterns, and highlight sources and propagation of delays, all of which may be obscured in a traditional trace visualization.
State-of-the-art MPI libraries rely on locks to guarantee thread-safety. this discourages application developers from using multiple threads to perform MPI operations. In this paper, we propose a high performance, loc...
详细信息
ISBN:
(纸本)9781450326568
State-of-the-art MPI libraries rely on locks to guarantee thread-safety. this discourages application developers from using multiple threads to perform MPI operations. In this paper, we propose a high performance, lock-free multiendpoint MPI runtime, which can achieve up to 40% improvement for point-to-point operation and one representative collective operation with minimum or no modifications to the existing applications.
Functional algorithmic skeletons promise a high-level programming interface for distributed-memory clusters that free developers from concerns of task decomposition, scheduling, and communication. Unfortunately, prior...
详细信息
this paper proposes and evaluates a parallel strategy to execute the exact Smith-Waterman (SW) algorithm for megabase DNA sequences in heterogeneous multi-GPU platforms. In our strategy, the computation of a single hu...
详细信息
ISBN:
(纸本)9781450326568
this paper proposes and evaluates a parallel strategy to execute the exact Smith-Waterman (SW) algorithm for megabase DNA sequences in heterogeneous multi-GPU platforms. In our strategy, the computation of a single huge SW matrix is spread over multiple GPUs, which communicate border elements to the neighbour, using a circular buffer mechanism that hides the communication overhead. We compared 4 pairs of human-chimpanzee homologous chromosomes using 2 different GPU environments, obtaining a performance of up to 140.36 GCUPS (Billion of cells processed per second) with 3 heterogeneous GPUS.
the proceedings contain 27 papers. the topics discussed include: Lazier imperative programming;parametricity and proving free theorems for functional-logic languages;bijective collection encodings and Boolean operatio...
ISBN:
(纸本)9781450329477
the proceedings contain 27 papers. the topics discussed include: Lazier imperative programming;parametricity and proving free theorems for functional-logic languages;bijective collection encodings and Boolean operations with hereditarily binary natural numbers;design and implementation of a multithreaded virtual machine for executing linear logic programs;proofs in continuation-passing style: normalization of Gödel's system T extended with sums and delimited control operators;a type theoretic specification for partial evaluation;continuations, processes, and sharing;elimination of square roots and divisions by partial inlining;real-time matching of Antescofo temporal patterns;on the declarative structure of quantum concepts: states and observables;proving operational termination of declarative programs in general logics;theories of homomorphic encryption, unification, and the finite variant property;and BiFluX: a bidirectional functional update language for XML.
暂无评论