2

Curry, unlike its cousin Haskell, allows you to give multiple values to a function:

foo 1 2 = 3
foo 1 2 = 4

and it does backtracking (or some other search) to explore the implications of such non-determinism.

This makes it similar to Prolog (especially λProlog due to the type system and syntax), where you would instead state

foo 1 2 3.
foo 1 2 4.

Semantically, is there any difference between an N-ary Curry function and an N+1-ary Prolog relation?

MWB
  • 11,740
  • 6
  • 46
  • 91

2 Answers2

5

The difference between Curry and Prolog are the dependencies between arguments and results which are the basis for the optimal evaluation strategy used in Curry. Similarly to Haskell, Curry uses a lazy (needed) evaluation strategy. This has the consequence that the search space is explored in a demand-driven manner.

For instance, the expression

(xs ++ [1]) ++ ys =:= []

has a finite search space in Curry (without any answer), whereas the equivalent Prolog goal

?- append(Xs,[1],Zs), append(Zs,Ys,[]).

has an infinite search space. Similarly, there are examples where Curry computes a solution in contracst to Prolog (e.g., Curry allows computations with infinite structures similarly to Haskell).

Thus, Curry extends the demand-driven evaluation strategy of Haskell to non-deterministic programming, wheras Prolog is based on strict evaluation.

Michael Hanus
  • 176
  • 3
  • That's interesting. Could the same (lazy) strategy have been used in a language that is syntactically Prolog, or does it require the argument/output dichotomy of Curry? – MWB Dec 17 '20 at 13:21
  • BTW `?- append(Zs,Ys,[]), append(Xs,[1],Zs).` terminates right away. – MWB Dec 17 '20 at 14:40
  • 1
    The lazy strategy is dynamic, i.e., the execution order is determined by the demanded arguments, whereas Prolog has a more static strategy. You can simulate lazy evaluation in Prolog (actually, PAKCS compiles Curry into Prolog). What you suggest is related to dynamic rescheduling, e.g., by coroutining, which cause new problems (e.g., incompleteness due to floundering). Hence you can simulate lazy evaluation in Prolog but not by a simple static re-ordering of clauses. – Michael Hanus Dec 17 '20 at 16:07
  • @MaxB `append(Zs,Ys,[]), append(Xs,[1],Zs).` evidently terminates because the first literal has only one generate-able solution, namely `Zs = Ys = []` and the second one fails for that solution: `Xs + [1] = []`. The other way around, `append(Xs,[1],Zs), append(Zs,Ys,[]).` is a infinite failure-driven loop. If Prolog could extract the CLP(FD) condition on the list lengths, namely `XsLength#>=0,YsLength#>=0,ZsLength#>=0, XsLength+1 #= ZsLength, ZsLength+YsLength #= 0, label([XsLength,YsLength,ZsLength]).`, which fails, that would something. Sadly only usable in specifc cases. – David Tonhofer Dec 17 '20 at 19:53
  • @DavidTonhofer *"Sadly only usable in specifc cases."* Curry's search also diverges in some cases where you might wish it terminated, I believe. – MWB Dec 17 '20 at 21:26
  • @MaxB I'm sure of it. I hope to take a close look at some point in time... – David Tonhofer Dec 17 '20 at 21:34
0

After thinking about this some more I realized that the main difference is that in Prolog, both

foo 1 2 3.
foo 1 2 4.

can be true at the same time, while in Curry both of

foo 1 2 == 3
foo 1 2 == 4

cannot be true simultaneously. (In PAKCS, == and =:= return Bool)

MWB
  • 11,740
  • 6
  • 46
  • 91