Prolog 无缘无故地从本地堆栈中取出
Prolog raises out of local stack for no good reason
我正在尝试在 Prolog 中实现 Levenshtein distance。
实现非常简单:
levenshtein(W1, W2, D) :-
atom_length(W1, L1),
atom_length(W2, L2),
lev(W1, W2, L1, L2, D),
!.
lev(_, _, L1, 0, D) :- D is L1, !.
lev(_, _, 0, L2, D) :- D is L2, !.
lev(W1, W2, L1, L2, D) :-
lev(W1, W2, L1 - 1, L2, D1),
lev(W1, W2, L1, L2 - 1, D2),
lev(W1, W2, L1 - 1, L2 - 1, D3),
charAt(W1, L1, C1),
charAt(W2, L2, C2),
( C1 = C2 -> T is 0; T is 1 ),
min(D1, D2, D3 + T, D).
% Returns the character at position N in the atom A
% The position is 1-based
% A: The atom
% N: The position at which to extract the character
% C: The character of A at position N
charAt(A, N, C) :- P is N - 1, sub_atom(A, P, 1, _, C).
% min(...): These rules compute the minimum of the given integer values
% I1, I2, I3: Integer values
% M: The minimum over the values
min(I1, I2, M) :- integer(I1), integer(I2), ( I1 =< I2 -> M is I1; M is I2).
min(I1, I2, I3, M) :- min(I1, I2, A), min(I2, I3, B), min(A, B, M).
但是,此代码因以下错误而失败:
?- levenshtein("poka", "po", X).
ERROR: Out of local stack
我在 Mac OS X Sierra
上使用 SWIPL
实现。
您的程序无法运行有一个很好的原因:您的递归调用导致无限循环。
这是由那些行造成的:
lev(W1, W2, L1 - 1, L2, D1),
lev(W1, W2, L1, L2 - 1, D2),
lev(W1, W2, L1 - 1, L2 - 1, D3),
min(D1, D2, D3 + T, D)
在 Prolog 中,像 L1 - 1
这样的表达式 不会 计算为数字。因此,您的代码将递归调用 lev
,第三个参数为 L1 -1
,然后是 L1 - 1 - 1
,等等,这与您的终止规则不匹配。
要解决此问题,您需要使用临时变量来计算结果,例如L1 - 1
.
这修复了它:
lev(W1, W2, L1, L2, D) :-
L11 is L1 - 1,
L22 is L2 - 1,
lev(W1, W2, L11, L2, D1),
lev(W1, W2, L1, L22, D2),
lev(W1, W2, L11, L22, D3),
charAt(W1, L1, C1),
charAt(W2, L2, C2),
( C1 = C2 -> T is 0; T is 1 ),
D4 is D3 + T,
min(D1, D2, D4, D).
现在这样做:
?- levenshtein("poka","po",X).
X = 0.
这可能不是你想要的结果,但至少不会报错。我会把它留给你来修复你的谓词。
你的程序有几个问题。
循环
@Fatalize 已经给了你一个理由,这里有一个通用的方法可以定位这些问题,使用 failure-slice 一些目标 false
被插入到您的程序中。如果剩余的程序循环,原始版本也会循环:
?- levenshtein("poka","po",X), false.
levenshtein(W1, W2, D) :-
atom_length(W1, L1),
atom_length(W2, L2),
lev(W1, W2, L1, L2, D), false,
!.
lev(_, _, L1, 0, D) :- D is L1, !.
lev(_, _, 0, L2, D) :- D is L2, !.
lev(W1, W2, L1, L2, D) :-
lev(W1, W2, L1 - 1, L2, D1), false,
lev(W1, W2, L1, L2 - 1, D2),
lev(W1, W2, L1 - 1, L2 - 1, D3),
charAt(W1, L1, C1),
charAt(W2, L2, C2),
( C1 = C2 -> T is 0; T is 1 ),
min(D1, D2, D3 + T, D).
您必须在剩余的可见部分中修改一些内容。否则,这个问题会一直存在。
使用列表!
与其使用原子或字符串,不如使用列表来表示单词。最好是添加到您的 .swiplrc
或 .sicstusrc
:
:- set_prolog_flag(double_quotes, chars).
以这种方式,以下内容成立:
?- "abc" = [a,b,c].
避免剪裁
以某种方式削减,有时有效,但此类程序难以调试。特别适合初学者。因此,不惜一切代价避免它们
使用简洁的算法
您正在使用经过高度修改的 Prolog 的 "olde" 算法。相反 use_module(library(clpfd))
以获得更纯净的代码。
我正在尝试在 Prolog 中实现 Levenshtein distance。
实现非常简单:
levenshtein(W1, W2, D) :-
atom_length(W1, L1),
atom_length(W2, L2),
lev(W1, W2, L1, L2, D),
!.
lev(_, _, L1, 0, D) :- D is L1, !.
lev(_, _, 0, L2, D) :- D is L2, !.
lev(W1, W2, L1, L2, D) :-
lev(W1, W2, L1 - 1, L2, D1),
lev(W1, W2, L1, L2 - 1, D2),
lev(W1, W2, L1 - 1, L2 - 1, D3),
charAt(W1, L1, C1),
charAt(W2, L2, C2),
( C1 = C2 -> T is 0; T is 1 ),
min(D1, D2, D3 + T, D).
% Returns the character at position N in the atom A
% The position is 1-based
% A: The atom
% N: The position at which to extract the character
% C: The character of A at position N
charAt(A, N, C) :- P is N - 1, sub_atom(A, P, 1, _, C).
% min(...): These rules compute the minimum of the given integer values
% I1, I2, I3: Integer values
% M: The minimum over the values
min(I1, I2, M) :- integer(I1), integer(I2), ( I1 =< I2 -> M is I1; M is I2).
min(I1, I2, I3, M) :- min(I1, I2, A), min(I2, I3, B), min(A, B, M).
但是,此代码因以下错误而失败:
?- levenshtein("poka", "po", X).
ERROR: Out of local stack
我在 Mac OS X Sierra
上使用 SWIPL
实现。
您的程序无法运行有一个很好的原因:您的递归调用导致无限循环。
这是由那些行造成的:
lev(W1, W2, L1 - 1, L2, D1),
lev(W1, W2, L1, L2 - 1, D2),
lev(W1, W2, L1 - 1, L2 - 1, D3),
min(D1, D2, D3 + T, D)
在 Prolog 中,像 L1 - 1
这样的表达式 不会 计算为数字。因此,您的代码将递归调用 lev
,第三个参数为 L1 -1
,然后是 L1 - 1 - 1
,等等,这与您的终止规则不匹配。
要解决此问题,您需要使用临时变量来计算结果,例如L1 - 1
.
这修复了它:
lev(W1, W2, L1, L2, D) :- L11 is L1 - 1, L22 is L2 - 1, lev(W1, W2, L11, L2, D1), lev(W1, W2, L1, L22, D2), lev(W1, W2, L11, L22, D3), charAt(W1, L1, C1), charAt(W2, L2, C2), ( C1 = C2 -> T is 0; T is 1 ), D4 is D3 + T, min(D1, D2, D4, D).
现在这样做:
?- levenshtein("poka","po",X).
X = 0.
这可能不是你想要的结果,但至少不会报错。我会把它留给你来修复你的谓词。
你的程序有几个问题。
循环
@Fatalize 已经给了你一个理由,这里有一个通用的方法可以定位这些问题,使用 failure-slice 一些目标 false
被插入到您的程序中。如果剩余的程序循环,原始版本也会循环:
?- levenshtein("poka","po",X), false. levenshtein(W1, W2, D) :- atom_length(W1, L1), atom_length(W2, L2), lev(W1, W2, L1, L2, D), false,!. lev(_, _, L1, 0, D) :- D is L1, !. lev(_, _, 0, L2, D) :- D is L2, !. lev(W1, W2, L1, L2, D) :- lev(W1, W2, L1 - 1, L2, D1), false,lev(W1, W2, L1, L2 - 1, D2),lev(W1, W2, L1 - 1, L2 - 1, D3),charAt(W1, L1, C1),charAt(W2, L2, C2),( C1 = C2 -> T is 0; T is 1 ),min(D1, D2, D3 + T, D).
您必须在剩余的可见部分中修改一些内容。否则,这个问题会一直存在。
使用列表!
与其使用原子或字符串,不如使用列表来表示单词。最好是添加到您的 .swiplrc
或 .sicstusrc
:
:- set_prolog_flag(double_quotes, chars).
以这种方式,以下内容成立:
?- "abc" = [a,b,c].
避免剪裁
以某种方式削减,有时有效,但此类程序难以调试。特别适合初学者。因此,不惜一切代价避免它们
使用简洁的算法
您正在使用经过高度修改的 Prolog 的 "olde" 算法。相反 use_module(library(clpfd))
以获得更纯净的代码。