PROLOG-REQUEST@SUSHI.STANFORD.EDU (Chuck Restivo, The Moderator) (07/30/87)
PROLOG Digest Thursday, 30 Jul 1987 Volume 5 : Issue 51
Today's Topics:
Query - Naive Reverse & Database Recognition,
Implementation - Interfile Scoping
----------------------------------------------------------------------
Date: 28 Jul 87 22:12:01 GMT
From: MorrisseyKA <ihnp4!drutx!druhi!kam@ucbvax.Berkeley.EDU>
Subject: Naive Reverse
Here is a naive (:-) question:
What is the formula for determining the number of LIs needed
to reverse a list of length N, using the following definition?
nairev([],[]).
nairev([X|Xs],Zs) :- nairev(Xs,Ys), append(Ys,[X],Zs).
append([],L,L).
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).
It seems that the answer should be easy to determine, but I'm having a
heck of a time coming up with an answer that I feel confident about.
-- Karen A. Morrissey
------------------------------
Date: 26 Jul 87 20:37:16 GMT
From: Balu Raman <dartvax!balu.UUCP@seismo.css.gov>
Subject: Problem recognition in database
I am working on recognizing problem instances in Prolog database. The
problems can be typical Graph-color, Linear Programming Problem,
Critical Path Problems etc.etc. Does anybody have references,
pointers, programs to do what I am trying to do.
Thank you.
-- Balu Raman
------------------------------
Date: Tue 28 Jul 87 20:09:49-CDT
From: Hassan Ait-Kaci <AI.HASSAN@MCC.COM>
Subject: Interfile variable scoping
This message is in reaction to Mr. Jeff Klein's question about inter
file variable scoping in C-prolog.
The problem is that Mr. Klein's FILE1 and FILE2 are not just any
files---they are modules. To *link* selected information from and/or
into a module, one must specify which is the imported information,
which is the exported information, and which is the (hidden,
invisible) local information. This is also called abstract data
typing. In Mr.Klein's example, a solution (ad-hoc, since modules are
not supported in C-prolog) would be to proceed exactly thus:
MODULE-1 contains:
export([A,B,C]
,[A,B,C]).
MODULE-2 contains:
export([A,B,C]
,(A = 3, B = C + A)).
sample_predicate:- see('MODULE-1'), read(export(Vars,VECTOR)), seen,
see('MODULE-2'), read(export(Vars,TEST)),seen,
assert(( is_true(VECTOR):-TEST )).
The Vars are imported explicitly by the file containing the reading
clause, and thus locally shared by way of unification. In general, the
problem is not so simple as just plain physical equality, but might
involve quite non-trivial type checking (to ensure that all the wires
are connected as intended). My ad-hoc solution does that for the
variables A, B, and C.
The problem of independent variable naming from reading from separate
files in Prolog is just an instance in the logic programming context
of that posed by the semantics of modules---i.e., of syntactic program
entities sharing scopes of references for some parameters. The problem
presents itself in the lambda calculus when the scope of certain
variables does not obey the rules of lexical scoping. Lexical scoping
freezes the meaning of free parameters in any logical sentence (i.e.,
taking their information content from the static context of the
sentence definition), thus assuming a unique and well-determined
meaning by closing the sentence's parameters. Dynamic scoping lets
them be "context dependent" (i.e., expecting to be passed their
information content from "active contexts" which invoke the sentence),
thus assuming generically many potential meanings. This duality of
scoping is in fact precisely formalized by the semantic duality of
"for-all" (A-quantification) and "there-exists" (E-quantification) in
logic.
In functional programming, programs are first-class object, which
facilitates (in theory) module manipulation. Based on ideas by John
Mitchell (Bell Labs) and Gordon Plotkin (Edinburgh), David MacQueen
(Bell Labs) has proposed an operational semantics of modules for
standard ML. Roughly, A-quantification accounts for universal
polymorphic variables (which are lexical) and E-quantification
accounts for existential polymorphic variables (which are dynamic).
Mads Tofte, a student of Robin Milner's at Edinburgh, is also
developing in his PhD research a calculus of modules for ML based on
"realization maps" among program modules which are functions effecting
the inheritance of contextual information between modules. His ideas
are in curious similarity with my own notion of psi-term structures
(my U.of Penn. PhD thesis) in the context of subtype inheritance.
However, I have not looked at using my ideas on inheritance for
modular information linking (yet).
In (first-order) logic programming, programs are not first-class
objects, making the module problem theoretically more awkward.
Although my knowledge is not deep, I find ideas developed by Dale
Miller (U. of Penn.) and Gopalan Nadathur (formerly of U. of Penn.,
now at Duke) very elegant. They have defined a higher-order
operational logic (the logic programming language Lambda-Prolog,
Nadathur's PhD thesis), with explicit A and E quantification, which
accounts quite nicely for module linking by way of unification.
Finally, it is worth mentioning the original work by Peter Mosses at
University of Aarrhus (sp?) in Denmark whereby he develops a formal
operational semantics (Action Semantics) for modular programming.
-- Hassan Ait-Kaci
MCC, ACA Program
------------------------------
End of PROLOG Digest
********************