SWI-Prolog编写Wordle求解器时谓词返回true而非期望列表的问题

问题描述 #

在SWI-Prolog中实现Wordle求解器的绿色匹配（位置、字符完全一致的匹配）更新逻辑时，出现返回值异常：谓词基例中打印的结果正确，但顶层调用仅返回true，无法拿到最终的绿色匹配列表。
原始实现代码如下：

append_green([],[],X,X,5):-
    write('Final Green: '), 
    writeln(X).
append_green([CorrectHead|CorrectTail], [GuessHead|GuessTail], Grn, _FinalGreen, N):-
    N < 5,
    (    CorrectHead = GuessHead 
    ->   replace(Grn,N,GuessHead,FinalGrn),
         N1 is N + 1, 
         append_green(CorrectTail, GuessTail, FinalGrn, FinalGrn, N1)
    ;    N1 is N + 1, 
         append_green(CorrectTail, GuessTail, Grn, Grn, N1) ).

replace([_|T], 0, X, [X|T]).
replace([H|T], I, X, [H|R]):- 
    I > 0, 
    I1 is I-1, 
    replace(T, I1, X, R).

谓词参数定义 #

• 第一个参数：正确答案，字符列表格式，例如['w','o','r','d','s']
• 第二个参数：用户猜测词，格式同正确答案
• 第三个参数：已有的绿色匹配列表，初始值为['.', '.', '.', '.', '.']，.代表该位置暂未匹配
• 第四个参数：预期输出的更新后绿色匹配列表
• 第五个参数：当前遍历的字符位置索引，初始调用传入0

调试追踪记录 #

调用append_green([w,h,i,c,h],[h,i,t,c,h],[.,.,.,.,.],X,0)的trace输出如下：

[trace]  ?- append_green([w,h,i,c,h],[h,i,t,c,h],[.,.,.,.,.],X,0).
   Call: (10) append_green([w, h, i, c, h], [h, i, t, c, h], ['.', '.', '.', '.', '.'], _25506, 0) ? creep
   Call: (11) 0<5 ? creep
   Exit: (11) 0<5 ? creep
   Call: (11) w=h ? creep
   Fail: (11) w=h ? creep
   Redo: (10) append_green([w, h, i, c, h], [h, i, t, c, h], ['.', '.', '.', '.', '.'], _25506, 0) ? creep
   Call: (11) _30726 is 0+1 ? creep
   Exit: (11) 1 is 0+1 ? creep
   Call: (11) append_green([h, i, c, h], [i, t, c, h], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], 1) ? creep
   Call: (12) 1<5 ? creep
   Exit: (12) 1<5 ? creep
   Call: (12) h=i ? creep
   Fail: (12) h=i ? creep
   Redo: (11) append_green([h, i, c, h], [i, t, c, h], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], 1) ? creep
   Call: (12) _36790 is 1+1 ? creep
   Exit: (12) 2 is 1+1 ? creep
   Call: (12) append_green([i, c, h], [t, c, h], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], 2) ? creep
   Call: (13) 2<5 ? creep
   Exit: (13) 2<5 ? creep
   Call: (13) i=t ? creep
   Fail: (13) i=t ? creep
   Redo: (12) append_green([i, c, h], [t, c, h], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], 2) ? creep
   Call: (13) _42854 is 2+1 ? creep
   Exit: (13) 3 is 2+1 ? creep
   Call: (13) append_green([c, h], [c, h], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], 3) ? creep
   Call: (14) 3<5 ? creep
   Exit: (14) 3<5 ? creep
   Call: (14) c=c ? creep
   Exit: (14) c=c ? creep
   Call: (14) replace(['.', '.', '.', '.', '.'], 3, c, _48146) ? creep
   Call: (15) 3>0 ? creep
   Exit: (15) 3>0 ? creep
   Call: (15) _50430 is 3+ -1 ? creep
   Exit: (15) 2 is 3+ -1 ? creep
   Call: (15) replace(['.', '.', '.', '.'], 2, c, _48914) ? creep
   Call: (16) 2>0 ? creep
   Exit: (16) 2>0 ? creep
   Call: (16) _54222 is 2+ -1 ? creep
   Exit: (16) 1 is 2+ -1 ? creep
   Call: (16) replace(['.', '.', '.'], 1, c, _52706) ? creep
   Call: (17) 1>0 ? creep
   Exit: (17) 1>0 ? creep
   Call: (17) _58014 is 1+ -1 ? creep
   Exit: (17) 0 is 1+ -1 ? creep
   Call: (17) replace(['.', '.'], 0, c, _56498) ? creep
   Exit: (17) replace(['.', '.'], 0, c, [c, '.']) ? creep
   Exit: (16) replace(['.', '.', '.'], 1, c, ['.', c, '.']) ? creep
   Exit: (15) replace(['.', '.', '.', '.'], 2, c, ['.', '.', c, '.']) ? creep
   Exit: (14) replace(['.', '.', '.', '.', '.'], 3, c, ['.', '.', '.', c, '.']) ? creep
   Call: (14) _63346 is 3+1 ? creep
   Exit: (14) 4 is 3+1 ? creep
   Call: (14) append_green([h], [h], ['.', '.', '.', c, '.'], ['.', '.', '.', c, '.'], 4) ? creep
   Call: (15) 4<5 ? creep
   Exit: (15) 4<5 ? creep
   Call: (15) h=h ? creep
   Exit: (15) h=h ? creep
   Call: (15) replace(['.', '.', '.', c, '.'], 4, h, _4622) ? creep
   Call: (16) 4>0 ? creep
   Exit: (16) 4>0 ? creep
   Call: (16) _6906 is 4+ -1 ? creep
   Exit: (16) 3 is 4+ -1 ? creep
   Call: (16) replace(['.', '.', c, '.'], 3, h, _5390) ? creep
   Call: (17) 3>0 ? creep
   Exit: (17) 3>0 ? creep
   Call: (17) _10698 is 3+ -1 ? creep
   Call: (17) replace(['.', c, '.'], 2, h, _9182) ? creep
   Call: (18) 2>0 ? creep
   Exit: (18) 2>0 ? creep
   Call: (18) _14490 is 2+ -1 ? creep
   Exit: (18) 1 is 2+ -1 ? creep
   Call: (18) replace([c, '.'], 1, h, _12974) ? creep
   Call: (19) 1>0 ? creep
   Exit: (19) 1>0 ? creep
   Call: (19) _18282 is 1+ -1 ? creep
   Exit: (19) 0 is 1+ -1 ? creep
   Call: (19) replace(['.'], 0, h, _16766) ? creep
   Exit: (19) replace(['.'], 0, h, [h]) ? creep
   Exit: (18) replace([c, '.'], 1, h, [c, h]) ? creep
   Exit: (17) replace(['.', c, '.'], 2, h, ['.', c, h]) ? creep
   Exit: (16) replace(['.', '.', c, '.'], 3, h, ['.', '.', c, h]) ? creep
   Exit: (15) replace(['.', '.', '.', c, '.'], 4, h, ['.', '.', '.', c, h]) ? creep
   Call: (15) _24376 is 4+1 ? creep
   Exit: (15) 5 is 4+1 ? creep
   Call: (15) append_green([], [], ['.', '.', '.', c, h], ['.', '.', '.', c, h], 5) ? creep
   Call: (16) write('Final Green: ') ? creep
Final Green: 
   Exit: (16) write('Final Green: ') ? creep
   Call: (16) writeln(['.', '.', '.', c, h]) ? creep
[.,.,.,c,h]
   Exit: (15) append_green([], [], ['.', '.', '.', c, h], ['.', '.', '.', c, h], 5) ? creep
   Exit: (14) append_green([h], [h], ['.', '.', '.', c, '.'], ['.', '.', '.', c, '.'], 4) ? creep
   Exit: (13) append_green([c, h], [c, h], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], 3) ? creep
   Exit: (12) append_green([i, c, h], [t, c, h], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], 2) ? creep
   Exit: (11) append_green([h, i, c, h], [i, t, c, h], ['.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.'], 1) ? creep
   Exit: (10) append_green([w, h, i, c, h], [h, i, t, c, h], ['.', '.', '.', '.', '.'], _18, 0) ? creep
true 

根因分析 #

递归参数传递逻辑错误，导致结果无法向上绑定：

1. 递归子句头部将第四个输出参数声明为匿名变量_FinalGreen，主动切断了顶层调用变量和递归内部结果的绑定关系
2. 递归调用时，错误地将当前层的临时列表同时作为下一层调用的输入和输出参数，每一层的输出都只和当前层临时值绑定，没有把基例得到的最终结果沿着递归栈逐层传递回顶层
3. 从trace最后一行可以看到，顶层调用的第四个参数是未绑定的自由变量_18，全程没有和基例中计算出的['.', '.', '.', c, h]做统一，因此最终只返回true，拿不到结果值。

修复代码 #

调整参数传递逻辑，将输出参数沿递归栈透传，去掉冗余的临时变量绑定，同时把if-then分支拆分为两个独立子句，避免隐式cut干扰参数绑定：

% 基例：遍历完所有5位字符，当前累积的绿色列表即为最终结果，移除调试打印语句
append_green([], [], FinalGreen, FinalGreen, 5).

% 字符匹配分支：替换当前位置为匹配字符后递归下一位
append_green([CorrectHead|CorrectTail], [GuessHead|GuessTail], Grn, FinalGreen, N):-
    N < 5,
    CorrectHead = GuessHead,
    replace(Grn, N, GuessHead, TmpGrn),
    N1 is N + 1,
    append_green(CorrectTail, GuessTail, TmpGrn, FinalGreen, N1).

% 字符不匹配分支：不修改绿色列表，直接递归下一位
append_green([CorrectHead|CorrectTail], [GuessHead|GuessTail], Grn, FinalGreen, N):-
    N < 5,
    CorrectHead \= GuessHead,
    N1 is N + 1,
    append_green(CorrectTail, GuessTail, Grn, FinalGreen, N1).

replace([_|T], 0, X, [X|T]).
replace([H|T], I, X, [H|R]):- 
    I > 0, 
    I1 is I-1, 
    replace(T, I1, X, R).

修复后调用append_green([w,h,i,c,h],[h,i,t,c,h],['.','.','.','.','.'],X,0)，会直接返回X = ['.', '.', '.', c, h]，无需依赖打印即可拿到正确结果。

内容的提问来源于stack exchange，提问作者AnFruit