Java进阶：使用Ruby amb解决说谎者谜题
<p >说谎者谜题是sicp4.3.2小节的一道题目，题目本身不难：<p >五个女生参加一个考试，她们的家长对考试结果过分关注。为此她们约定，在给家里写信谈到考试的时候，每个姑娘都要写一句真话和一句假话。下面是从她们的信里摘抄出来的句子：<p >Betty : kitty考第二，我只考了第三<p >Ethel : 你们应该很高兴听到我考了第一，joan第二<p >joan : 我考第三，可怜的Ethel垫底<p >kitty:我第二，marry只考了第四<p >marry: 我是第四，Betty的成绩最高。<p >这五个姑娘的实际排名是什么？<p ><p >Ruby本来就有call/cc，因此也可以实现amb操作符，网上已经有一个实现了：<p ><ccid_nobr><table width="400" border="1" cellspacing="0" cellpadding="2"bordercolorlight = "black" bordercolordark = "#FFFFFF" align="center"><tr><td bgcolor="e6e6e6" class="code" ><pre><ccid_code>class Ambclass ExhaustedError < RuntimeError; enddef initialize @fail = proc { fail ExhaustedError, "amb tree exhausted" }enddef 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 }enddef failure chooseend def assert(cond) failure unless condendalias :require :assertend</ccid_code></pre></td></tr></table></ccid_nobr><br><p ><p >这一段代码与scheme宏实现amb是完全相同的：<p ><ccid_nobr><table width="400" border="1" cellspacing="0" cellpadding="2"bordercolorlight = "black" bordercolordark = "#FFFFFF" align="center"><tr><td bgcolor="e6e6e6" class="code" ><pre><ccid_code>(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)))))))</ccid_code></pre></td></tr></table></ccid_nobr><br><p ><p >回到谜题，从题意可知每个姑娘的两句话的异或结果为true，并且姑娘的排名肯定不会相同，因此定义两个辅助过程：<p ><ccid_nobr><table width="400" border="1" cellspacing="0" cellpadding="2"bordercolorlight = "black" bordercolordark = "#FFFFFF" align="center"><tr><td bgcolor="e6e6e6" class="code" ><pre><ccid_code>require 'amb'def distinct?(items)items.uniq==itemsenddef xor(exp1,exp2) (exp1 or exp2) and !(exp1 and exp2)end</ccid_code></pre></td></tr></table></ccid_nobr><br><p ><p >剩下的完全就是将题目翻译成代码即可了，没有多少可以解释的东西：<p ><ccid_nobr><table width="400" border="1" cellspacing="0" cellpadding="2"bordercolorlight = "black" bordercolordark = "#FFFFFF" align="center"><tr><td bgcolor="e6e6e6" class="code" ><pre><ccid_code>amb=Amb.newbetty=amb.choose(*)ethel=amb.choose(*)joan=amb.choose(*)kitty=amb.choose(*)marry=amb.choose(*)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?())puts "betty:#{betty} ethel:#{ethel} joan:#{joan} kitty:#{kitty} marry:#{marry}"</ccid_code></pre></td></tr></table></ccid_nobr><br><p ><p >答案就是：<p ><p >betty:3 ethel:5 joan:2 kitty:1 marry:4 <p ><p >最后给出一个Prolog的解答：<p ><ccid_nobr><table width="400" border="1" cellspacing="0" cellpadding="2"bordercolorlight = "black" bordercolordark = "#FFFFFF" align="center"><tr><td bgcolor="e6e6e6" class="code" ><pre><ccid_code>notmember(A,[]).notmember(A,):-A\==B,notmember(A,L).distinct():- notmember(A,), notmember(B,), notmember(C,), notmember(D,), notmember(E,).xor(Exp1,Exp2):- (Exp1;Exp2),\+ (Exp1,Exp2).solve(Betty,Ethel,Joan,Kitty,Marry):- X=, member(Betty,X), member(Ethel,X), member(Joan,X), member(Kitty,X), member(Marry,X), distinct(), 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).</ccid_code></pre></td></tr></table></ccid_nobr><br><p ><p ><P align=right></P><p align="center"></p></p>
页:
[1]