On 10/31/10 10:26 PM, Richard O'Keefe wrote:
On 1/11/2010, at 2:02 PM, wren ng thornton wrote:
(Though I find it curious that you think the logic version is so different...)
The logic programming version
uses a SINGLE data structure for lists and differences, so that
+ "converting" from the difference representation to the "plain"
representation
involves no more than binding a single (logic) variable
+ does not involve ANY overheads compared with building a list directly
+ can easily be traversed while still under construction,
> - can only be used once, after which the "hole" has *gone*.
Sure, but all of these come from the differences in how functional
languages and logic languages define their notions of "variable".
In logic programming you're allowed to play with open terms, so the
ability to move around difference lists before they're "complete" is the
same as being able to manipulate any other open term. Whereas in
functional languages you (typically) are not allowed to have open terms,
and terms with variables in them must be guarded by lambdas which
prohibit you looking underneath them. One benefit of lambdas is that
they lift the names of unknown substructure up to the top of an
expression; the difflist(xs,hole) structure is just there to give that
same lifting of names, since otherwise we wouldn't have any way of
knowing that xs is unground nor how to make it (more) ground[1]. The
various other differences regarding linear usage just come down to the
fact that difflist(xs,hole) is a closure, not a function. But there's
nothing to prevent functionalizing it, if the logic language provides a
mechanism for generating fresh variables.
When I look at difference lists in functional languages I see them in
the same light: as a mechanism for manipulating open terms. The details
of what manipulations are allowed is different (mostly because of
function vs closure), but that's to be expected given the paradigm
differences. But then I take the algorithmic idea of using open terms
for fast concatenation as primary and the implementation details of what
"open terms" are as secondary.
[1] Assuming a pure logic language, which Prolog is not.
--
Live well,
~wren
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
