matsud224 / wamcompiler

Prolog implementation based on Warren's abstract machine
The Unlicense
41 stars 6 forks source link

Bug in neck-cut remains #6

Open FemtoEmacs opened 4 years ago

FemtoEmacs commented 4 years ago

The bug in neck-cut remains. To test wamcompiler, I am using Werner Hett's P-99: Ninety-Nine Prolog Programs. Here are two examples where wamcompiler produces a bug (the triple %%% commented version avoids neck-cut and work):

% P09 (**):  Pack consecutive duplicates of list elements.
%% > ?-pack([2,3,3,3,4,4,5], L).
%% L = [[2],[3,3,3],[4,4],[5]]
%% bugneck-cut

pack([],[]) :- !.
pack([X|Xs],[Z|Zs]) :- transfer(X,Xs,Ys,Z), pack(Ys,Zs).

% transfer(X,Xs,Ys,Z) Ys is the list that remains from the list Xs
%    when all leading copies of X are removed and transfered to Z

transfer(X,[],[],[X]) :- !.
transfer(X,[X|Xs],Ys,[X|Zs]) :- !, transfer(X,Xs,Ys,Zs).
%%% transfer(Y,[X|Xs],Ys,[X|Zs]) :- Y == X, !, transfer(X,Xs,Ys,Zs).
transfer(X,[Y|Ys],[Y|Ys],[X]).

% P11 (*):  Modified run-length encoding
%% > ?-encode_modified([1,1,2,2,2,2,2,3,3,4], G).
%% G = [[2,1],[5,2],[2,3],4]
%% bugneckcut
encode_modified(L1,L2) :- encode(L1,L), strip(L,L2).

strip([],[]) :- !.
strip([[1,X]|Ys],[X|Zs]) :-  !, strip(Ys,Zs).
strip([[N,X]|Ys],[[N,X]|Zs]) :- N > 1, strip(Ys,Zs).

% P15 (**): Duplicate the elements of a list agiven number of times
%% > ?-dupli([1,2,2,3,3,3,5], 4,  L).
%% L = [1,1,1,1,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,5,5,5,5]
%% bugneckcut
dupli(L1,N,L2) :- dupli(L1,N,L2,N).

dupli([],_,[],_) :- !.
dupli([_|Xs],N,Ys, 0) :- !, dupli(Xs,N,Ys,N).
%%%dupli([_|Xs],N,Ys, K) :- K == 1, !, dupli(Xs,N,Ys,N).
dupli([X|Xs],N,[X|Ys],K) :- K > 0, K1 is K - 1,
                dupli([X|Xs],N,Ys,K1).
FemtoEmacs commented 4 years ago

IMHO, the problem is that, when the head builds a list with patterns such as [X|Xs], a neck-cut is not neck-cut anymore, it becomes a normal cut. If I add a dummy notneck predicate before the cut, the system works normally. By the way, I convinced a Canadian University and people from Apple Developer Academy to use wamcompiler, instead of cxprolog. Most of them are students and use 99 problems as test bench. Below, you will find the programs with the dummy notneck predicate.


% P09 (**):  Pack consecutive duplicates of list elements.
%% > ?-pack([2,3,3,3,4,4,5], L).
%% L = [[2],[3,3,3],[4,4],[5]]
%% bugneck-cut
notneck.

pack([],[]) :- !.
pack([X|Xs],[Z|Zs]) :- transfer(X,Xs,Ys,Z), pack(Ys,Zs).

% transfer(X,Xs,Ys,Z) Ys is the list that remains from the list Xs
%    when all leading copies of X are removed and transfered to Z

transfer(X,[],[],[X]) :- !.
transfer(X,[X|Xs],Ys,[X|Zs]) :- notneck, !, transfer(X,Xs,Ys,Zs).
%%% transfer(Y,[X|Xs],Ys,[X|Zs]) :- Y == X, !, transfer(X,Xs,Ys,Zs).
transfer(X,[Y|Ys],[Y|Ys],[X]).

length([],0) :- !.
length([_|L],N) :- length(L,N1), N is N1 + 1.

encode(L1,L2) :- pack(L1,L), transform(L,L2).

transform([],[]) :- !.
transform([[X|Xs]|Ys],[[N,X]|Zs]) :- length([X|Xs],N),
                              transform(Ys,Zs).

% P11 (*):  Modified run-length encoding
%% > ?-encode_modified([1,1,2,2,2,2,2,3,3,4], G).
%% G = [[2,1],[5,2],[2,3],4]
%% bugneckcut
encode_modified(L1,L2) :- encode(L1,L), strip(L,L2).

strip([],[]) :- !.
strip([[1,X]|Ys],[X|Zs]) :- notneck, !, strip(Ys,Zs).
strip([[N,X]|Ys],[[N,X]|Zs]) :- N > 1, strip(Ys,Zs).

% P15 (**): Duplicate the elements of a list agiven number of times
%% > ?-dupli([1,2,2,3,3,3,5], 4,  L).
%% L = [1,1,1,1,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,5,5,5,5]
%% bugneckcut
dupli(L1,N,L2) :- dupli(L1,N,L2,N).

dupli([],_,[],_) :- !.
dupli([_|Xs],N,Ys, 0) :- notneck, !, dupli(Xs,N,Ys,N).
%%%dupli([_|Xs],N,Ys, K) :- K == 1, !, dupli(Xs,N,Ys,N).
dupli([X|Xs],N,[X|Ys],K) :- K > 0, K1 is K - 1,
                dupli([X|Xs],N,Ys,K1).