1. Oleg Kiselyov
Non-deterministic choice in a conventional programming language: Enough for logic programming?
Abstract:
Logic programming is a fascinating approach, especially for AI and
natural language processing. It is greatly appealing to declaratively
state the properties of the problem and let the system find the
solution. Most intriguing is the ability to run programs `forwards'
and `backwards'.
However, the built-in search methods of logic programming systems
don't fit all problems and hardly if at all customizable. Mainly,
quite many computations and models are mostly
deterministic. Implementing them in a logic programming language is
significantly inefficient and requires extensive use of problematic
features such as cut. Another problem is interfacing logic programs
with mainstream language libraries: if mode analysis is not available
(as is often the case), one has to live with run-time instantiatedness
errors.
An alternative to logic programming, where non-determinism is default,
is a deterministic programming system (such as Scheme, OCaml, Scala or
Haskell -- or even C) with (probabilistic) non-determinism as an
option. Is this a good alternative? We explore this question. We will
use Hansei -- a probabilistic programming system implemented as a
library in OCaml -- to solve a number of classic logic programming
problems, from zebra to scheduling, to parser combinators, to reversible
type checking.
http://okmij.org/ftp/kakuritu/logic-programming.html
2. Hugo Pacheco
Bidirectional Data Transformation by Calculation
Abstract:
The advent of bidirectional programming, in recent years, has led to
the development of a vast number of approaches from various computer
science disciplines. These are often based on domain-specific
languages in which a program can be read both as a forward and a
backward transformation that satisfy some desirable consistency
properties.
Despite the high demand and recognized potential of intrinsically
bidirectional languages, they have still not matured to the point of
mainstream adoption. We contemplate some usually disregarded features
of bidirectional transformation languages that are vital for
deployment at a larger scale. The first concerns efficiency. Most of
these languages provide a rich set of primitive combinators that can
be composed to build more sophisticated transformations. Although
convenient, such compositional languages are plagued by inefficiency
and their optimization is mandatory for a serious application. The
second relates to configurability. As update translation is inherently
ambiguous, users shall be allowed to control the choice of a suitable
strategy. The third regards genericity. Writing a bidirectional
transformation typically implies describing the concrete steps that
convert values in a source schema to values a target schema, making it
impractical to express very complex transformations, and practical
tools shall support concise and generic coding patterns.
Back to the top page