Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!uwm.edu!rutgers!att!dptg!ulysses!andante!alice!pereira
From: pereira@alice.UUCP (Fernando Pereira)
Newsgroups: comp.lang.prolog
Subject: Re: Fun. vs. Logic
Summary: varieties of function in logic programming
Message-ID: <10167@alice.UUCP>
Date: 20 Nov 89 15:44:37 GMT
References: <11500018@hpldola.HP.COM> <2743@munnari.oz.au> <2754@munnari.oz.au>
Reply-To: pereira@alice.UUCP ()
Organization: AT&T, Bell Labs
Lines: 81

In article <2754@munnari.oz.au> lee@munmurra.UUCP (Lee Naish) writes:
>I don't think current coroutining systems are quite smart enough to give
>you lazy evaluation.  My implementation of NU-Prolog + equations
>("NUE-Prolog") does allow lazy evaluation but it can run under a
>conventional Prolog with no problems.

Sanjai Narain's LOG(F) \cite{Narain86} is another example of lazy first-order
functional programming compilable into Prolog, working seamlessly with
logical variables. Lazy stream operations in LOG(F) are the basis for
narrowing grammars, a nice grammar formalism to describe traces of
concurrent processes [Chau&Parker89].

>>Prolog-as-we-know-it is not higher order, but that doesn't stop me using
>>maplist and such things in Prolog
>
>My system has some basic things like apply defined.
>Prolog-as-we-know-it has call and univ/functor+arg, which is all you
>need.

To notions of ``higher-order'' need to be distinguished here. ``Higher-order''
as in functional programming means having functions as first-class
*functional* citizens. This is whas I think Lee means here. The
point was made in [Warren82], and other variants are
possible [Ait-Kaci&Nasr86]. The other notion is where functions are
first-class *logical* objects, as in Church's simple theory of types.
Lambda-Prolog is the prime example of a logic programming system in
this category. While for the first notion basically what is necessary
is some means to create and apply closures (maybe with delaying until
things are sufficiently instantiated for functional evaluation as in
LeFun [Ait-Kaci&Nasr86]), the first notion requires much more complex
machinery including higher-order unfication.

Fernando Pereira
2D-447, AT&T Bell Laboratories
600 Mountain Ave, Murray Hill, NJ 07974
pereira@research.att.com


@Article{Narain86,
  author = 	"Sanjai Narain",
  title = 	"A Technique for Doing Lazy Evaluation in Logic",
  journal = 	"Logic Programming",
  year = 	"1986",
  volume = 	"3",
  number = 	"3",
  pages = 	"259-???",
  month = 	"October"
}
@TECHREPORT{Ait-Kaci&Nasr86,
	AUTHOR = {Hassan Ait-Kaci and Roger Nasr},
	TITLE = {Residuation: a paradigm for Integrating Logic and Functional
	Programming},
	INSTITUTION = {{MCC}},
	YEAR = {1986},
	TYPE = {Technical Report},
	NUMBER = {AI-359-86},
	ADDRESS = {Austin, Texas}
}
@incollection(Warren82,
   annote={Extensions; predicate objects; sets.},
   title={Higher-Order Extensions to {Prolog}---Are They Needed?},
   key={Warren},
   author={David H.D. Warren},
   booktitle={Machine Intelligence 10},
   editor={Hayes and Michie and Pao},
   publisher={Ellis Horwood},
   year={1982}
)
@InProceedings{Chau&Parker89,
  author = 	"H. Lewis Chau and D. Stott Parker",
  title = 	"Narrowing Grammars",
  booktitle = 	"Logic Programming: Proceedings of the Sixth
		 International Conference",
  year = 	"1989",
  editor = 	"Giorgio Levi and Maurizio Martelli",
  pages = 	"199-217",
  publisher = 	"{MIT} PRess",
  address = 	"Cambridge, Massachussets",
  month = 	"July",
  note = 	"Held in Lisbon, Portugal"
}