scheme vs prolog 
Author Message
 scheme vs prolog

Hi,
I am a prolog man, have never used scheme but have been interested for
some years. I am currently doing a lot of work in prolog using BinProlog
by Paul Tarau which contains a very useful extension based around
assumptions (he calls the construction Assumption Grammar). In short,
the extension enables you to include backtrackable assertions as
preconditions to a particular call, which are automatically cancelled on
backtracking. It also enables one to get around one prolog limitation of
fixed arguments using assumptions. There is a similar construct which
provides backtrackable accumulators outside of the normal argument list.
These things (plus a few more) add up to a fairly powerful programming
tool and environment.
The only complaint I have is that prolog has no negative test - you have
to make a boolean statement and test to see if it fails - 'negation as
failure'. During development when you often get failures for reasons
other than negation, a failure within a no-driven loop has often caused
me infinite loops where I did not want them.
I dont understand scheme or lisp very well and so am in no position to
make comparisons. However, my observation is that you tend to spend a
lot of time writing machines which provide the sort of facilities which
prolog already provides i.e. non-determinism, continuations,
backtracking.
I would be very interested to hear some response from dedicated
scheme/lisp programmers, as I would very much like to get around the
'negation as failure' problem in prolog, and just for the fun of it
anyway.
thanks for your time,
mr



Sat, 17 Apr 1999 03:00:00 GMT  
 scheme vs prolog

Quote:

>When I write programs in prolog and prolog-like languages, I spend
>most of my time avoiding unwanted non-determinism and backtracking
>(i.e. inserting cut operators here and there).

Cut is not an operator, and that is not the method that good Prolog
programmers use for controlling nondeterminism.

Quote:
>Prolog's `backtrack by default' behavior is pain because I need simple
>loop or simple if-then construct far more frequently than brute-force
>exhaustive search.

If you want a simple if-then-else, the language offers one, with syntax
straight out of the Lisp 1.5 manual:

        ( Test1 -> Do_If_Test1_True
        ; ...
        ; Testn -> Do_If_Testn_True
        ;          Do_If_All_Tests_False
        )

Simple loops are coded in Prolog exactly the same way they are in
other pattern-matching languages (without backtracking) like ML:

        append([], L, L).
        append([H|T], L, [H|R]) :-
            append(T, L, R).

is as deterministic (when the first argument is known) as you could
possibly wish for.  No cuts are needed.

Quote:
>I would like prolog if it had made backtracking optional and made
>deterministic call the default.

In short, you would like Prolog if it wasn't a *logic* programming
language.  Backtracking is not some sort of optional extra in Prolog;
something of the sort is _required_ by the semantics.

Quote:
>I'd rather use KL1, a parallel logic
>programming language which doesn't have backtracking.  KL1 and other
>commited-choice languages have much cleaner semantics, too.

I haven't seen the semantics of KL1; would you care to post a reference?
I guarantee you that KL1 hasn't got a cleaner semantics than Mercury,
which is very Prolog-like except it is both *more* logical and *more*
efficient.  It would almost be fair to say
        Mercury:Prolog :: ML:Scheme.

Quote:
>Actually, I rarely need brute-force search (by backtracking) except
>for 10-lines-long toy programs.  And coding exhaustive search is
>trivial anyway.  It had better be left out from language feature, if
>the language has rich enough control-flow primitives.

"Brute-force search" is a straw man.
What Prolog gives you is a *relational* language.  It is a complete
relational data base query language, for example, and I find it a
lot simpler and more concise than SQL.  There are logic data base
systems that use Prolog syntax and give you logical semantics,
and you would hate them because they are not "deterministic"; a
query that logically _ought_ to have more than one answer _has_ more
than one answer.  Prolog also provides a very clean grammar definition
notation which yields practically useful parsers and test case
generators, and twisting it to be deterministic by default would wreck that.

If you want a basically deterministic single-solution language with a
little bit of backtracking exactly where you want it, then don't whinge
about how Prolog wasn't designed for your taste, use something that _was_.
Jeff Siskind's "Screamer" package is freely available, and extends Lisp
in what sounds like *exactly* the way you want.

--
Mixed Member Proportional---a *great* way to vote!
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.



Mon, 19 Apr 1999 03:00:00 GMT  
 scheme vs prolog

    mark> I dont understand scheme or lisp very well and so am in no position to
    mark> make comparisons. However, my observation is that you tend to spend a
    mark> lot of time writing machines which provide the sort of facilities which
    mark> prolog already provides i.e. non-determinism, continuations,
    mark> backtracking.

When I write programs in prolog and prolog-like languages, I spend
most of my time avoiding unwanted non-determinism and backtracking
(i.e. inserting cut operators here and there).

Prolog's `backtrack by default' behavior is pain because I need simple
loop or simple if-then construct far more frequently than brute-force
exhaustive search.

I would like prolog if it had made backtracking optional and made
deterministic call the default.  I'd rather use KL1, a parallel logic
programming language which doesn't have backtracking.  KL1 and other
commited-choice languages have much cleaner semantics, too.

Actually, I rarely need brute-force search (by backtracking) except
for 10-lines-long toy programs.  And coding exhaustive search is
trivial anyway.  It had better be left out from language feature, if
the language has rich enough control-flow primitives.

                                --mad



Mon, 19 Apr 1999 03:00:00 GMT  
 scheme vs prolog



    >> When I write programs in prolog and prolog-like languages, I spend
    >> most of my time avoiding unwanted non-determinism and backtracking
    >> (i.e. inserting cut operators here and there).

    > Cut is not an operator, and that is not the method that good Prolog
    > programmers use for controlling nondeterminism.

I'm not sure but some people use this terminology.  E.g.  "Concurrent
Prolog: Collected Papers" (Ehud Shapiro ed., MIT Press, 1987) has
index entry for "cut operator", not "cut".

    >> Prolog's `backtrack by default' behavior is pain because I need simple
    >> loop or simple if-then construct far more frequently than brute-force
    >> exhaustive search.

    > If you want a simple if-then-else, the language offers one, with syntax
    > straight out of the Lisp 1.5 manual:

    >        ( Test1 -> Do_If_Test1_True
    >        ; ...
    >        ; Testn -> Do_If_Testn_True
    >        ;          Do_If_All_Tests_False
    >        )

What's the essential difference with this and

    Head1 :- !, Do_If_Test1_True.
    ...
    Headn :- !, Do_If_Testn_True.
    HeadElse :- Do_If_All_Tests_False.

in top level?  I use both of them.

    > Simple loops are coded in Prolog exactly the same way they are in
    > other pattern-matching languages (without backtracking) like ML:

    >        append([], L, L).
    >        append([H|T], L, [H|R]) :-
    >            append(T, L, R).

    > is as deterministic (when the first argument is known) as you could
    > possibly wish for.  No cuts are needed.

Hmmm.

    intersection([H|T], L, [H|R]) :- member(X, L), !, intersection(T, L, R).
    intersection([_|T], L, R) :- intersection(T, L, R).
    intersection([], _, []).

Is the above code so weired?  Please correct me if it's so bad.

    >> I would like prolog if it had made backtracking optional and made
    >> deterministic call the default.

    > In short, you would like Prolog if it wasn't a *logic* programming
    > language.  Backtracking is not some sort of optional extra in Prolog;
    > something of the sort is _required_ by the semantics.

Not necessarily.  Many concurrent logic programming languages has no
notion of sequential backtracking.

    >> I'd rather use KL1, a parallel logic
    >> programming language which doesn't have backtracking.  KL1 and other
    >> commited-choice languages have much cleaner semantics, too.

    > I haven't seen the semantics of KL1; would you care to post a reference?

KL1 is based on flat-GHC and GHC family languages are described in
"The Family of Concurrent Logic Programming Languages", Ehud Shapiro,
ACM Computing Surveys 21(4): 629 (1989).

    > I guarantee you that KL1 hasn't got a cleaner semantics than Mercury,
    > which is very Prolog-like except it is both *more* logical and *more*
    > efficient.  It would almost be fair to say
    >        Mercury:Prolog :: ML:Scheme.

Looks like a good flame bait for comp.lang.scheme :-).  Seriously, I
feel KL1 (and other committed choice languages) `clean'
w.r.t. treatment of cuts.  In KL1, exactly one cut (`commit operator')
is *required* for every clause.

    > If you want a basically deterministic single-solution language with a
    > little bit of backtracking exactly where you want it, then don't whinge
    > about how Prolog wasn't designed for your taste, use something that _was_.
    > Jeff Siskind's "Screamer" package is freely available, and extends Lisp
    > in what sounds like *exactly* the way you want.

Of course I choose language that I prefer whenever possible.  And of
course I won't break into Prolog newsgroup and preach about how I
dislike Prolog.

I thought the original author wanted to hear a view of Prolog from
Lisp programmer.  And I just presented mine.

                                        --mad



Sat, 24 Apr 1999 03:00:00 GMT  
 scheme vs prolog


]

]    >> Prolog's `backtrack by default' behavior is pain because I need simple
]    >> loop or simple if-then construct far more frequently than brute-force
]    >> exhaustive search.
]
]    > If you want a simple if-then-else, the language offers one, with syntax
]    > straight out of the Lisp 1.5 manual:
]
]    >       ( Test1 -> Do_If_Test1_True
]    >       ; ...
]    >       ; Testn -> Do_If_Testn_True
]    >       ;          Do_If_All_Tests_False
]    >       )
]
]What's the essential difference with this and
]
]    Head1 :- !, Do_If_Test1_True.
]    ...
]    Headn :- !, Do_If_Testn_True.
]    HeadElse :- Do_If_All_Tests_False.
]
]in top level?  I use both of them.

The essential theoretical difference is that if-then-else has a declarative
semantics which is independent of the modes, whereas cut has
only mode-dependent (i.e. operational) semantics.

The essential practical difference is that people who use cut
rather than if-then-else very often make mistakes: they write
code that is not "steadfast", i.e. code which can give wrong
answers when called with the arguments more instantiated than expected.


]    intersection([H|T], L, [H|R]) :- member(X, L), !, intersection(T, L, R).
]    intersection([_|T], L, R) :- intersection(T, L, R).
]    intersection([], _, []).
]
]Is the above code so weired?  Please correct me if it's so bad.

Yes, the above code is awful (even after you correct the obvious bug: s/X/H/).
In particular, the query

        ?- intersection([1], [1], []).

fails, even though it ought to succeed.
If you write this using if-then-else rather than cut, e.g. as

    intersection([H|T], L, R) :-
                ( member(H, L) -> R = [H | R1] ; R = R1 ),
                intersection(T, L, R1).
    intersection([], _, []).

then the code will be steadfast, and so queries such as the one
above will return the correct result.

(Richard O'keefe's excellent book "The Craft of Prolog" explains
the problems of non-steadfast code.)

]    > I guarantee you that KL1 hasn't got a cleaner semantics than Mercury,
]    > which is very Prolog-like except it is both *more* logical and *more*
]    > efficient.  It would almost be fair to say
]    >       Mercury:Prolog :: ML:Scheme.
]
]Looks like a good flame bait for comp.lang.scheme :-).  Seriously, I
]feel KL1 (and other committed choice languages) `clean'
]w.r.t. treatment of cuts.  In KL1, exactly one cut (`commit operator')
]is *required* for every clause.

In traditional concurrent logic programming languages,
if you put the commit in the wrong place, then you can get
runtime errors.  Furthermore, the right place to put the
commit depends on the modes.

Mercury in fact supports committed-choice nondeterminism as well
as backtracking, so you can program in a KL1-like style (minus
parallelism) in Mercury if you want.  The difference is that
in Mercury the *compiler* figures out the right place to put the
commit(s).

--

WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"



Sun, 25 Apr 1999 03:00:00 GMT  
 scheme vs prolog

Quote:

>I'm not sure but some people use this terminology.  E.g.  "Concurrent
>Prolog: Collected Papers" (Ehud Shapiro ed., MIT Press, 1987) has
>index entry for "cut operator", not "cut".

"Concurrent Prolog" is not Prolog.  In FCP, you used to write
        Head :- Guard | Body.
and you will see that the cut _operator_ "|" does indeed have two
operands.  The cut _command "!" in Prolog has no operands.  In Prolog,
"operator" is a word used to describe syntax, and the things it describes
are symbols like +, *, <<, and so on having operator properties.  ! has
no such operator properties.

Quote:
>    >    ( Test1 -> Do_If_Test1_True
>    >    ; ...
>    >    ; Testn -> Do_If_Testn_True
>    >    ;          Do_If_All_Tests_False
>    >    )
>What's the essential difference with this and
>    Head1 :- !, Do_If_Test1_True.
>    ...
>    Headn :- !, Do_If_Testn_True.
>    HeadElse :- Do_If_All_Tests_False.
>in top level?  I use both of them.

There are two kinds of differences:  performance and readability.
Performance:
    in some Prolog systems "shallow" backtracking (as done between
    the branches of an if-then-else) is faster than "deep" backtracking
    (as done between the clauses of a predicate).

    clause-at-a-time compilers _know_ they are dealing with an
    if-then-else, and may generate specialised code for them.

Readability:
    I use the separate clauses form when the conditions are different
    *pattern matches* (possibly guarded), and the if-then-else form
    when its a matter of type and/or arithmetic tests, which _cannot_ be
    done by pattern matching (except in VM/Prolog and IBM Prolog, of
    course).

    Especially as the clause heads tend to be of very different lengths,
    so that a cut at the end of a line winds up being hard to see, it
    is easier to *see* an if-then-else written as an if-then-else than
    something written as clauses with cuts.

So I would write

        p(+, ....) :- !, ...
        p(-, ....) :- !,  ..

but
        p(N, ...) :- ( N > 0 -> ... ; N < 0 -> ... ).

Quote:
>Hmmm.
>    intersection([H|T], L, [H|R]) :- member(X, L), !, intersection(T, L, R).
>    intersection([_|T], L, R) :- intersection(T, L, R).
>    intersection([], _, []).
>Is the above code so weired?  Please correct me if it's so bad.

Can't you *see* the bug in it?

As for performance, when I went through library(sets) at Quintus,
discarding all of the cuts I could, performance went _up_ by about 30%.

(And of course the completely cut-free code in library(ordsets) has
O(N+M) performance instead of O(N*N).)

Quote:
>    > In short, you would like Prolog if it wasn't a *logic* programming
>    > language.  Backtracking is not some sort of optional extra in Prolog;
>    > something of the sort is _required_ by the semantics.
>Not necessarily.  Many concurrent logic programming languages has no
>notion of sequential backtracking.

Yes, necessarily.  The concurrent logic programming languages you speak
of have a great many virtues, but possessing the *semantics of Horn clauses*
is not one of them.  It has been seriously debated whether FCP merits the
title "logic" programming at all.  Programming languages whose semantics
is based on the Horn clause sublanguage of first order logic don't have
any choice, multiple solutions are part of the semantics, so they must be
handled *somehow*, either by backtracking of some sort or by splitting.

You will have noticed that Mercury requires you to *specify* when you
intend a predicate to have multiple solutions, but (a) in that case you
do get the multiple solutions, and (b) if you *don't* specify that you
intend multiple solutions the Mercury system doesn't start committing to
wild guesses like FCP, but verifies *at compile time* that no multiple
solutions are *possible*.

Quote:
>    > I haven't seen the semantics of KL1; would you care to post a reference?
>KL1 is based on flat-GHC and GHC family languages are described in
>"The Family of Concurrent Logic Programming Languages", Ehud Shapiro,
>ACM Computing Surveys 21(4): 629 (1989).

I am aware of GHC.  You still haven't said where I could find
Quote:
>>the semantics of KL1<<.  After all, Ada is "based on" Pascal, but

that doesn't mean the two have the same semantics!

Quote:
>Looks like a good flame bait for comp.lang.scheme :-).  Seriously, I
>feel KL1 (and other committed choice languages) `clean'
>w.r.t. treatment of cuts.  In KL1, exactly one cut (`commit operator')
>is *required* for every clause.

As far as I am concerned, the cut is perhaps the third worst feature of
old Prolog.  It was justifiable as a hack for getting the whole thing
off the ground (and is identical to FENCE in SNOBOL, where a formal
semantics for the pattern-matching sublanguage, including FENCE, was
later developed).  However, it drives a wedge between the declarative
and procedural readings of Prolog and is generally hard to reason about.
Requiring _every_ clause to have one is a lot like saying "hm, a few
people have ugly looking burn scars, let's burn _everyone_ and then
those people at least won't be _exceptionally_ ugly".

The thing I like about Mercury is that it manages to restrain backtracking
to the places where you really want it *without* sacrificing the link between
Prolog and standard first order logic, indeed, and this is the magic,
Mercury gets better performance than Prolog by being *more* faithful to logic!

--
Mixed Member Proportional---a *great* way to vote!
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.



Tue, 27 Apr 1999 03:00:00 GMT  
 scheme vs prolog


]Mercury requires you to *specify* when you
]intend a predicate to have multiple solutions, but (a) in that case you
]do get the multiple solutions, and (b) if you *don't* specify that you
]intend multiple solutions the Mercury system doesn't start committing to
]wild guesses like FCP, but verifies *at compile time* that no multiple
]solutions are *possible*.

Actually there is now (since Mercury 0.5) a third possibility: you can
specify that multiple solutions are possible, but that you're only
looking for one solution.  In that case, the Mercury system will verify
at compile time that that you don't use that predicate in a context in
which the system might need to try more than one solution of that
predicate.  The system can then safely commit to a clause as soon as it
knows that the remainder of the clause won't fail.

Support for committed choice non-determinism (CCND) is very important
for expressiveness, particularly when it comes to concurrency.
However, adding CCND to functional languages (as done in Eden, a
concurrent extension of Haskell) breaks referential transparency.
Looking towards logic languages, which are based on a semantic
framework that can support nondeterminism without violating referential
transparency, is a promising approach, but previous approaches to CCND
in logic languages (GHC, FCP, etc.) all require making "wild guesses"
that can lead to wrong or missing answers.  As far as I know, Mercury
is the first language to support CCND in a way that avoids the
semantic problems of these afore-mentioned approaches.

--

WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"



Wed, 28 Apr 1999 03:00:00 GMT  
 
 [ 7 post ] 

 Relevant Pages 

1. UNIX scheme vs MSDOS scheme

2. Scheme advocacy: scheme vs. perl

3. Scheme vs Haskell vs Erlang

4. SWI Prolog Vs GNU Prolog

5. Prolog/Lisp vs other languages (was Simple Prolog Question)

6. Amzi-Prolog vs. Visual Prolog

7. stdcall vs c vs cdecl vs pascal vs whosyerdaddy

8. 68K vs CFM68K vs Tk 8.0.3 vs AppearanceLib vs System 7

9. Metaprogramming: C++ templates vs Scheme macros?

10. Scheme vs. Erlang

11. Haskell vs. Scheme

12. Totally Newbie: Scheme vs. Haskell

 

 
Powered by phpBB® Forum Software