PROLOG-REQUEST@SUSHI.STANFORD.EDU (Chuck Restivo, The Moderator) (04/30/87)
PROLOG Digest Thursday, 30 Apr 1987 Volume 5 : Issue 32
Today's Topics:
Query - CPUtime & Automatic Programming,
Implementation - Cut & Meta-interpreter
----------------------------------------------------------------------
Date: 29 Apr 87 09:51:00 EST
From: John Cugini <cugini@icst-ecf.arpa>
Reply-to: "CUGINI, JOHN" <cugini@icst-ecf.arpa>
Subject: broken cputime
When I invoke 'cputime' in C-Prolog, v. 1.5.5, under VAX/VMS, I
get a curt 'no'. Anybody else have this problem? Any fixes?
-- John Cugini
------------------------------
Date: 22 Apr 87 14:26:40 GMT
From: Michel Lang <lang@bigburd.prc.unisys.com>
Subject: self-reproducing programs
I recall a discussion in a while back about self-reproducing programs.
Does anybody have any references to any literature or any other
information about self-reproducing programs?
Many thanks.
-- Francois-Michel Lang
------------------------------
Date: 24 Apr 87 21:10:18 GMT
From: James A. Woods <jaw@ames.arpa>
Subject: self-reproducing programs
A formal discussion may be found in Hartley Rogers' classic text
"Theory of Recursive Functions and Effective Computability",
McGraw-Hill, 1967, p. 188-190. The existence of such programs date
back to a theorem of von Neumann, though the text uses a consequence
of the fixpoint "recursion theorem" of Kleene in proof.
More leisurely, one might peek at the European Unix User's Group
newsletter (EUUGN vol. 3, no. 4) for the article "Some
Self-Reproducing Programs" by Theo de Ridder.
Or, for the truly lazy, just compile and run
p="p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}
for a demonstration of such introspective behavior. The 66-byte C
version was the culmination of a lively net.sources discussion in
1984. However, some masochists were composing much more elaborate
self-reproducing code in FORTRAN at various institutions during the
1950's.
-- James A. Woods
------------------------------
Date: 24 Apr 87 22:55:09 GMT
From: Nabiel Elshiewy <mcvax!enea!erix!nabiel@seismo.css.gov>
Subject: cut for meta-interpreter
I think you better take a look into the record of 1985 IEEE Symp. on
Logic programming. You'll find the interpreter you need and a bit more
in an article there written by R. O'Keefe "On the Treatment of Cuts in
Prolog Source-Level Tools", pp 68-72.
------------------------------
Date: 24 Apr 87 19:00:14 GMT
From: Rafail Ostrovsky <raf@bu-cs.bu.edu>
Subject: cut for meta-interpreter
I have solved the question I have posed, so never mind. Here is the
meta-circular Prolog interpreter which includes both "cut" and
"ancestor cut". (For explanation of what "ancestor cut" is see
Sterling and Shapiro book "The Art of Prolog"). A proof of correctness
is going to appear elsewhere.
%----------------------------------------------------------
% meta-circular interpreter which includes
% "cut", "ancestor cut", "or" and "not" at the meta-level.
%----------------------------------------------------------
% Author: Rafail Ostrovsky 4/23/1987
%----------------------------------------------------------
%
solve(G) :- solve(G,_).
solve(!,X) :- var(X);X=cut.
solve(ancestor_cut(Pred),X) :- var(X);X=Pred.
solve(not(A),C) :- not solve(A,C).
solve((A,B),C) :- solve(A,C),solve(B,C).
solve((A;B),C) :- solve(A,C);solve(B,C).
solve(A,C)
:- nonvar(C);
(system_pred(A),!,A);
( clause(A,B),
solve(B,C1),
( var(C1);
(nonvar(C1),functor(A,C1,_),!,fail);
(C1==cut,!,fail);
(nonvar(C1),C=C1))).
system_pred(clause(_,_)).
system_pred(true).
system_pred(solve).
%----------------------------------------------------------
Example:
test(X) :- p(X),q(X).
test(X) :- q(X).
p(1).
p(2).
p(3) :- ancestor_cut(test).
p(4).
q(1).
q(2).
q(3).
q(4).
?- solve(test(X)) will succeed with X = {1,2,3}.
-- Raf
------------------------------
End of PROLOG Digest
********************