说谎者谜题是sicp4.3.2小节的一道题目，题目本身不难：
五个女生参加一个考试，她们的家长对考试结果过分关注。为此她们约定，在给家里写信谈到考试的时候，每个姑娘都要写一句真话和一句假话。下面是从她们的信里摘抄出来的句子：
Betty : kitty考第二，我只考了第三
Ethel : 你们应该很高兴听到我考了第一，joan第二
joan : 我考第三，可怜的Ethel垫底
kitty: 我第二，marry只考了第四
marry: 我是第四，Betty的成绩最高。
这五个姑娘的实际排名是什么？
Ruby本来就有call/cc，因此也可以实现amb操作符，网上已经有一个实现了：
class
Amb
class
ExhaustedError
<
RuntimeError; end def initialize @fail
=
proc { fail ExhaustedError,
"
amb tree exhausted
"
} end def choose(
*
choices) prev_fail
=
@fail callcc {
|
sk
|
choices.each {
|
choice
|
callcc {
|
fk
|
@fail
=
proc { @fail
=
prev_fail fk.call(:fail) }
if
choice.respond_to
?
:call sk.call(choice.call)
else
sk.call(choice) end } } @fail.call } end def failure choose end def
assert
(cond) failure unless cond end alias :require :
assert
end
这一段代码与scheme宏实现amb是完全相同的：
(define amb
-
fail
'
*)
(define initialize
-
amb
-
fail (
lambda
() (set! amb
-
fail (
lambda
() (error
"
amb tree exhausted
"
))))) (initialize
-
amb
-
fail) (define call
/
cc call
-
with
-
current
-
continuation) (define
-
syntax amb (syntax
-
rules () ((amb alt ) (let ((prev
-
amb
-
fail amb
-
fail)) (call
/
cc (
lambda
(sk) (call
/
cc (
lambda
(fk) (set! amb
-
fail (
lambda
() (set! amb
-
fail prev
-
amb
-
fail) (fk
'
fail)))
(sk alt))) (prev
-
amb
-
fail)))))))
回到谜题，从题意可知每个姑娘的两句话的异或结果为true，并且姑娘的排名肯定不会相同，因此定义两个辅助过程：
require
'
amb
'
def
distinct?(items) items.uniq
==
items end
def
xor(exp1,exp2) (exp1
or
exp2)
and
!(exp1
and
exp2) end
剩下的完全就是将题目翻译成代码即可了，没有多少可以解释的东西：
amb
=
Amb.new betty
=
amb.choose(
*
[
1
,
2
,
3
,
4
,
5
]) ethel
=
amb.choose(
*
[
1
,
2
,
3
,
4
,
5
]) joan
=
amb.choose(
*
[
1
,
2
,
3
,
4
,
5
]) kitty
=
amb.choose(
*
[
1
,
2
,
3
,
4
,
5
]) marry
=
amb.choose(
*
[
1
,
2
,
3
,
4
,
5
]) amb.require(xor(kitty
==
2
,betty
==
3
)) amb.require(xor(ethel
==
1
,joan
==
2
)) amb.require(xor(joan
==
3
,ethel
==
5
)) amb.require(xor(kitty
==
2
,marry
==
4
)) amb.require(xor(marry
==
4
,betty
==
1
)) amb.require(distinct?([betty,ethel,joan,kitty,marry])) puts
"
betty:#{betty} ethel:#{ethel} joan:#{joan} kitty:#{kitty} marry:#{marry}
"
答案就是：
betty:3 ethel:5 joan:2 kitty:1 marry:4
最后给出一个Prolog的解答：
notmember(A,[]). notmember(A,[B
|
L]):
-
A\
==
B, notmember(A,L). distinct([A,B,C,D,E]):
-
notmember(A,[B,C,D,E]), notmember(B,[A,C,D,E]), notmember(C,[A,B,D,E]), notmember(D,[A,B,C,E]), notmember(E,[A,B,C,D]). xor(Exp1,Exp2):
-
(Exp1;Exp2),\
+
(Exp1,Exp2). solve(Betty,Ethel,Joan,Kitty,Marry):
-
X
=
[
1
,
2
,
3
,
4
,
5
], member(Betty,X), member(Ethel,X), member(Joan,X), member(Kitty,X), member(Marry,X), distinct([Betty,Ethel,Joan,Kitty,Marry]), xor(Kitty
=
:
=
2
,Betty
=
:
=
3
), xor(Ethel
=
:
=
1
,Joan
=
:
=
2
), xor(Joan
=
:
=
3
,Ethel
=
:
=
5
), xor(Kitty
=
:
=
2
,Marry
=
:
=
4
), xor(Marry
=
:
=
4
,Betty
=
:
=
1
).
文章转自庄周梦蝶 ，原文发布时间2008-11-15
相关资源：安邦信AMB-V11系列通用变频器使用说明书.pdf
