We propose a unified approach to semantically rich knowledge representation, querying and exchange for the Web, based on functional-logic programming. JavaScript- and JSON-based so-called information scripts serve as ...
详细信息
ISBN:
(纸本)9783319137049;9783319137032
We propose a unified approach to semantically rich knowledge representation, querying and exchange for the Web, based on functional-logic programming. JavaScript- and JSON-based so-called information scripts serve as a unified knowledge representation and query format, with logical reasoning being a constraint solving or narrowing task. This way, our framework provides a highly versatile, easy to use and radically different alternative compared to conventional forms of knowledge representation and exchange for the Web.
functionallogicprogramming is a paradigm which integrates functional and logicprogramming. It is based on the use of rewriting rules for defining programs, and rewriting for goal solving. In this context, goals, us...
详细信息
functionallogicprogramming is a paradigm which integrates functional and logicprogramming. It is based on the use of rewriting rules for defining programs, and rewriting for goal solving. In this context, goals, usually, consist of equality (and, sometimes, inequality) constraints, which are solved in order to obtain answers, represented by means of substitutions. On the other hand, database programming languages involve a data model, a, data definition language and, finally, a query language against the data defined according to the data model. To use functionallogicprogramming as a database programming language, (1) we will propose a data model involving the main features adopted from functionallogicprogramming (for instance, handling of partial and infinite data), (2) we will use conditional rewriting rules as data definition language, and finally, (3) we will deal with equality and inequality constraints as query language. Moreover, as most database systems, (4) we will propose an extended relational calculus and algebra, which can be used as alternative query languages in this framework. Finally, (5) we will prove that three alternative query languages are equivalent.
Constructor-Based Conditional Rewriting logic is a general framework for integrating first-order functional and logicprogramming which gives an algebraic semantics for non-deterministic functional-logic programs. In ...
详细信息
Constructor-Based Conditional Rewriting logic is a general framework for integrating first-order functional and logicprogramming which gives an algebraic semantics for non-deterministic functional-logic programs. In the context of this formalism, we introduce a simple notion of program module as an open program which can be extended together with several mechanisms to combine them. These mechanisms are based on a reduced set of operations. However, the high expressiveness of these operations enable us to model typical constructs for program modularization like hiding, export/import, genericity/instantiation, and inheritance in a simple way. We also deal with the semantic aspects of the proposal by introducing an immediate consequence operator, and studying several alternative semantics for a program module, based on this operator, in the line of logicprogramming: the operator itself, its least fixpoint (the least model of the module), the set of its pre-fixpoints (term models of the module), and some other variations in order to find a compositional and fully abstract semantics w.r.t. the set of operations and a natural notion of observability.
Type systems are widely used in programming languages as a powerful tool providing safety to programs. functionallogic languages have inherited Damas-Milner type system from their functional part due to its simplicit...
详细信息
Type systems are widely used in programming languages as a powerful tool providing safety to programs. functionallogic languages have inherited Damas-Milner type system from their functional part due to its simplicity and popularity. In this paper we address a couple of aspects that can be subject of mprovement. One is related to a problematic feature of functionallogic languages not taken under consideration by standard systems: it is known that the use of opaque HO patterns in left-hand sides of program rules may produce undesirable effects from the point of view of types. We re-examine the problem, and propose two variants of a Damas-Milner-like type system where certain uses of HO patterns (even opaque) are permitted while preserving type safety. The considered formal framework is that of programs without extra variables and using let-rewriting as reduction mechanism. The other aspect addressed is the different ways in which polymorphism of local definitions can be handled. At the same time that we formalize the type system, we have made the effort of technically clarifying the overall process of type inference in a whole program. (C) 2014 Elsevier Inc. All rights reserved.
The CFLP scheme for Constraint functionallogicprogramming has instances CFLP(D) corresponding to different constraint domains D. In this paper, we propose an amalgamated sum construction for building coordination do...
详细信息
The CFLP scheme for Constraint functionallogicprogramming has instances CFLP(D) corresponding to different constraint domains D. In this paper, we propose an amalgamated sum construction for building coordination domains C, suitable to represent the cooperation among several constraint domains D-1,..., D-n via a mediatorial domainM. Moreover, we present a cooperative goal solving calculus for CFLP(C), based on lazy narrowing, invocation of solvers for the different domains D-i involved in the coordination domain C, and projection operations for converting D-i constraints into D-j constraints with the aid of mediatorial constraints (so-called bridges) supplied by M. Under natural correctness assumptions for the projection operations, the cooperative goal solving calculus can be proved fully sound w.r.t. the declarative semantics of CFLP(C). As a relevant concrete instance of our proposal, we consider the cooperation between Herbrand, real arithmetic and finite domain constraints.
This paper presents the integration of the optimization known as dynamic cut within the functional-logic system TOY. The implementation automatically detects deterministic functions at compile time, and includes in th...
详细信息
This paper presents the integration of the optimization known as dynamic cut within the functional-logic system TOY. The implementation automatically detects deterministic functions at compile time, and includes in the generated code the test for detecting at run-time the computations that can actually be pruned. The outcome is a much better performance when executing deterministic functions including either or-branches in their definitional trees or extra variables in their conditions, with no serious overhead in the rest of the computations. The paper also proves the correctness of the criterion used for detecting deterministic functions w.r.t. the semantic calculus CRWL.
In modern functionallogic languages like Curry or Toy, programs are possibly non-confluent and non-terminating rewrite systems, defining possibly non-deterministic non-strict functions. Therefore, equational reasonin...
详细信息
In modern functionallogic languages like Curry or Toy, programs are possibly non-confluent and non-terminating rewrite systems, defining possibly non-deterministic non-strict functions. Therefore, equational reasoning is not valid for deriving properties of such programs. In a previous work we showed how a mapping from CRWL -a well known logical framework for functionallogicprogramming-into logicprogramming could be in principle used as logical conceptual tool for proving properties of functionallogic programs. A severe problem faced in practice is that simple properties, even if they do not involve non-determinism, require difficult proofs when compared to those obtained using equational specifications and methods. In this work we improve our approach by taking into account determinism of (part of) the considered programs. This results in significant shortenings of proofs when we put in practice our methods using standard systems supporting equational reasoning like, e.g., Isabelle.
To alleviate the inefficiencies caused by the interaction of the logic and functional sides, integrated languages may take advantage of demand information, i.e. knowing in advance which computations are needed and, to...
详细信息
To alleviate the inefficiencies caused by the interaction of the logic and functional sides, integrated languages may take advantage of demand information, i.e. knowing in advance which computations are needed and, to which extent, in a particular context. This work studies demand analysis - which is closely related to backwards strictness analysis - in a semantic framework of partial predicates, which in turn are constructive realizations of ideals in a domain. This will allow us to give a concise, unified presentation of demand analysis, to relate it to other analyses based on abstract interpretation or strictness logics, some hints for the implementation, and, more important, to prove the soundness of our analysis based on demand equations. There are also some innovative results. One of them is that a set constraint-based analysis has been derived in a stepwise manner using ideas taken from the area of program transformation. The other one is the possibility of using program transformation itself to perform the analysis, specialty in those domains of properties where algorithms based on constraint solving are too weak.
An important property of strategies used to solve goals in functionallogicprogramming (FLP) languages is the complete exploration of the solution space. Integrating constraints into FLP proved to be useful in many c...
详细信息
ISBN:
(纸本)3540243623
An important property of strategies used to solve goals in functionallogicprogramming (FLP) languages is the complete exploration of the solution space. Integrating constraints into FLP proved to be useful in many cases, as the resulting constraint functionallogicprogramming (CFLP) offers more facilities and more efficient operational semantics. CFLP can be achieved by means of conditional rewrite systems with a narrowing-based operational semantics. A common idea to improve the efficiency of such operational semantics is to use specific algorithms from operations research as constraint solvers. If the algorithm does not return a complete set of solutions, the property of completeness might be lost. We present a real world timetabling problem illustrating this approach. We propose an algorithm, obtained as an integration of three known optimization algorithms for the linear assignment problem (LAP), enumerating solutions to the LAP in order of increasing weight, such that resolution of goals is complete again. We show, how the narrowing process can be tailored to use this algorithm and provide an efficient way to solve the timetable generation problem.
This paper presents a programming framework for incorporating XPath queries into the functional-logic language Toy. The proposal exploits the language characteristics, including non-determinism, logic variables, and h...
详细信息
ISBN:
(纸本)9783642183775
This paper presents a programming framework for incorporating XPath queries into the functional-logic language Toy. The proposal exploits the language characteristics, including non-determinism, logic variables, and higher-order functions and patterns. Our setting covers a wide range of standard XPath axes and tests. In particular reverse axes are implemented thanks to the double nature of XPath queries, which are both higher-order functions and data terms in our setting. The combination of these two different worlds, the functional-logic paradigm and the XML query language XPath, is very enriching for both of them. From the point of view of functional-logic programming, the language is now able to deal with XML documents in a very simple way. From the point of view of XPath, our approach presents several nice properties as the generation of XML test-cases for XPath queries, which can be useful for finding bugs in erroneous queries.
暂无评论