lazyCHR.pl : Some examples of lazy evaluation using CHR We give an embedding of the Haskell language into CHR. Here you can try how it works in the following program: plus(0, Y) = Y plus(s(X), Y) = s(plus(X, Y)) double X = plus(X, X) head cons(X, _) = X zeros = cons(0, zeros) prec(s(X)) = X take(0, _) = void take(_, void) = void take(N, cons(X, Xs)) = cons(x, take(prec(N), Xs) It has been defined also the well know higher-order funtion map: map(f, void) = void map(f, cons(X, Y)) = cons(f(X), map(f,Y))
How to use: Remembering that a list is defined by means of the void/0 (the empty list) and cons/2 data construction. In order to run a ground expression *e* you just have to run a query of the form ?- eval(e, Z)., this will bond the result to the *Z* variable.
See also: 'John C. Reynolds. Deﬁnitional interpreters for higher-order programming languages. Higher-Order and Symbolic Computation, 11(4):363–397, 1998.' 'David H.D. Warren. Higher-order extensions to prolog: are they needed? In J.E. Hayes, Donald Michie, and Y-H. Pao, editors, Machine Intel ligence 10, pages 441–454. Ellis Horwood Ltd., Chicester, England, 1982.' S. Narain. A Technique for doing Lazy Evaluation in Logic
Program: Change the code, then submit! /* lazyCHR.pl: Some examples of lazy evaluation using CHR (C) Giovanni Bacci, 5/10/2009 This program is distributed under the terms of the GNU General Puplic License: http://www.gnu.org/licences/gpl.html %% DESCRIPTION We give an embedding of the Haskell language into CHR. Here you can try how it works in the following program:# *plus(0, Y) = Y* # *plus(s(X), Y) = s(plus(X, Y))* # *double X = plus(X, X)* # *head cons(X, _) = X* # *zeros = cons(0, zeros)* # *prec(s(X)) = X*# *take(0, _) = void*# *take(_, void) = void*# *take(N, cons(X, Xs)) = cons(x, take(prec(N), Xs)*# It has been defined also the well know higher-order funtion map:# *map(f, void) = void*# *map(f, cons(X, Y)) = cons(f(X), map(f,Y))*# %% HOW TO USE Remembering that a list is defined by means of the *void/0* (the empty list) and *cons/2* data construction. # In order to run a 'ground' expression *e* you just have to run a query of the form *?- eval(e, Z).*, this will bond the result to the *Z* variable. %% SEE ALSO 'John C. Reynolds. Deﬁnitional interpreters for higher-order programming languages. Higher-Order and Symbolic Computation, 11(4):363–397, 1998.' # 'David H.D. Warren. Higher-order extensions to prolog: are they needed? In J.E. Hayes, Donald Michie, and Y-H. Pao, editors, Machine Intel ligence 10, pages 441–454. Ellis Horwood Ltd., Chicester, England, 1982.' # 'S. Narain. A Technique for doing Lazy Evaluation in Logic' %% SAMPLE QUERIES % evaluation of a simple nested expression Q: eval(plus(plus(0,s(0)),0), Z). A: Z = s(0) % evaluation of a simple nested expression (version 2) Q: eval(plus(0,plus(0,0)), Z). A: Z = 0 % evaluation of a non-terminating infinite zero list Q: eval(zeros, Z). A: it does not terminate % lazy evaluation of a non-terminating sub-espression Q: eval(head(zeros), Z) A: Z = 0 % mapping a list with the successor function (defined as the section of the plus expression) Q: eval(map(plus(s(0)), cons(0,cons(s(0),void))), Z). A: Z = cons(s(0),cons(s(s(0)),void)) % mapping a list of lists (a matrix) Q: eval(map(map(plus(s(0))),cons(cons(0,void),cons(cons(s(0),void),void))), Z). A: cons(cons(s(0),void),cons(cons(s(s(0)),void),void)) % mapping a lazily evaluated list expression Q: eval(map(plus(head(zeros)),cons(0,cons(s(0),void))), Z). A: Z = cons(0,cons(s(0),void)) */ :- use_module(library(chr)). :- chr_constraint reduce/2, eval/2, lzyStep/2. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % data Succ = 0 | s Succ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% dataSucc_0 @ reduce(0, Z) <=> Z = 0. dataSucc_s @ reduce(s(X), Z) <=> Z = s(FX), reduce(X,FX). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % plus 0 Y = Y % plus (s X) Y = s (plus X Y) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% pl1 @ lzyStep(plus(0,Y), Z) <=> Z = Y. pl2 @ lzyStep(plus(s(X),Y), Z) <=> Z = s(plus(X,Y)). pl3 @ lzyStep(plus(X,Y), Z) <=> X \= 0, X \= s(_) | lzyStep(X,ZX), Z = plus(ZX,Y). ps1 @ reduce(plus(0,Y), Z) <=> reduce(Y, Z). ps2 @ reduce(plus(s(X),Y), Z) <=> reduce(s(plus(X,Y)), Z). ps3 @ reduce(plus(X,Y), Z) <=> X \= 0, X \= s(_) | lzyStep(X,ZX), reduce(plus(ZX,Y), Z). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % data Lst a = void | cons a (Lst a) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% dataLst_void @ reduce(void, Z) <=> Z = void. dataLst_cons @ reduce(cons(X,Ls), Z) <=> Z = cons(FX,FLs), reduce(X,FX), reduce(Ls,FLs). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % head (cons X _) = X %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% lzyStep(head(cons(X,_)), Z) <=> Z = X. lzyStep(head(X), Z) <=> X \= cons(_,_) | lzyStep(X,FX), Z = head(FX). reduce(head(cons(X,_)), Z) <=> reduce(X,Z). reduce(head(X), Z) <=> X \= cons(_,_) | lzyStep(X,FX), reduce(head(FX), Z). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % zeros = cons 0 zeros % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% lzyStep(zeros, Z) <=> Z = cons(0,zeros). reduce(zeros, Z) <=> reduce(zeros,Z). lzyStep(double(X), Z) <=> Z = plus(X,X). reduce(double(X), Z) <=> reduce(plus(X,X), Z). lzyStep(map(_,void), Z) <=> Z = void. lzyStep(map(F,cons(X,Ls)), Z) <=> Z = cons(apply(F,X), map(F,Ls)). reduce(map(_,void), Z) <=> reduce(void,Z). reduce(map(F,cons(X,Ls)), Z) <=> reduce(cons(apply(F,X), map(F,Ls)), Z). reduce(map(F,Ls), Z) <=> Ls \= void, Ls \= cons(_,_) | lzyStep(Ls,Fls), reduce(map(F,Fls), Z). %% TAKE EXAMPLE %%%%%%%%%%%%%%%%%%%%%%%%%%% reduce(prec(s(X)), Z) <=> reduce(X,Z). reduce(prec(X), Z) <=> X \= s(_) | lzyStep(X, FX), reduce(FX,Z). lzyStep(prec(s(X)), Z) <=> Z = X. lzyStep(prec(X), Z) <=> X \= s(_) |lzyStep(X, FX), Z = FX. reduce(take(0,_), Z) <=> reduce(void,Z). reduce(take(s(_),void), Z) <=> reduce(void, Z). reduce(take(s(N),cons(X,Xs)), Z) <=> reduce(cons(X,take(prec(N),Xs)), Z). reduce(take(N,Xs), Z) <=> N \= 0, N \= s(_), Xs \= void, Xs \= cons(_,_) | lzyStep(N, FN), reduce(take(FN,Xs), Z). lzyStep(take(0,_), Z) <=> Z = void. lzyStep(take(s(_),void), Z) <=> Z = void. lzyStep(take(s(N),cons(X,Xs)), Z) <=> Z = cons(X,take(prec(N),Xs)). lzyStep(take(N,Xs), Z) <=> N \= 0, N \= s(_), Xs \= void, Xs \= cons(_,_) | lzyStep(N, FN), Z = take(FN,Xs). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% APPLY ENCODING FOR DEFUNCTIONALIZATION %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% reduce(apply(double,X), Z) <=> reduce(double(X), Z). reduce(apply(plus,X1), Z) <=> reduce(plus(X1), Z). reduce(apply(plus(X1),X2), Z) <=> reduce(plus(X1,X2), Z). reduce(apply(head, X), Z) <=> reduce(head(X), Z). reduce(apply(map,X1), Z) <=> reduce(map(X1), Z). reduce(apply(map(X1),X2), Z) <=> reduce(map(X1,X2), Z). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% eval(T,Z) ==> reduce(T,Z).
Console: Enter query or select example from below, then submit and wait for answer! % loading chrww/lazyCHR.pl | ?- consult(...). yes [2.737 seconds] | ?-