Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!husc6!mailrus!purdue!decwrl!labrea!csli!johnson
From: johnson@csli.STANFORD.EDU (Mark Johnson)
Newsgroups: comp.lang.prolog
Subject: Re: In defence of difference-lists.
Keywords: Difference-lists, Dataflow analysis, Program transformation.
Message-ID: <6087@csli.STANFORD.EDU>
Date: 23 Oct 88 18:38:56 GMT
References: <3002@mulga.oz> <542@quintus.UUCP> <3005@mulga.oz> <2502@munnari.oz> <550@quintus.UUCP>
Reply-To: johnson@csli.UUCP (Mark Johnson)
Organization: Center for the Study of Language and Information, Stanford U.
Lines: 49


Given all the interest in Unfold/Fold, would anyone care to hear about
a toy program I wrote that uses the Unfold/Fold transformation on the
following input clauses to derive the following output?  If so, I will
write a short description for the net.

Mark Johnson

Preferred return address:  johnson@csc.brown.edu

Input clauses (assertions in database).

string(n(X,Y),S) <- [ string(X,SX), string(Y,SY), append(SX,SY,S) ].
string(X,[X]) <- [terminal(X)].
terminal(a) <- [].
terminal(b) <- [].
revpairwise([],[]) <- [].
revpairwise([A],[A]) <- [].
revpairwise([A,B|Es],Rs) <- [revpairwise(Es,Ms), append(Ms,[A,B],Rs)].
append([],Cs,Cs) <- [].
append([A|As],Bs,[A|Cs]) <- [ append(As,Bs,Cs) ].

Sample Interaction.

fold(string(_,_)).

%    string_f(A,B,C) :-
%        string(A,D),
%        append(D,B,C).

string_f(n(A,B),C,D) :-
    string_f(A,E,D),
    string_f(B,C,E).
string_f(A,B,[A | B]) :-
    terminal(A).

No
fold(revpairwise(_,_)).

%    revpairwise_f(A,B,C) :-
%        revpairwise(A,D),
%        append(D,B,C).

revpairwise_f([],A,A).
revpairwise_f([A],B,[A | B]).
revpairwise_f([A,B | C],D,E) :-
    revpairwise_f(C,[A,B | D],E).

No