Tabled Prolog and Linear Tabling.ppt
《Tabled Prolog and Linear Tabling.ppt》由会员分享,可在线阅读,更多相关《Tabled Prolog and Linear Tabling.ppt(20页珍藏版)》请在麦多课文档分享上搜索。
1、Linear Tabling,1,Tabled Prolog and Linear Tabling,Neng-Fa Zhou (City Univ. of New York) Yi-Dong Shen (Chinese Academy of Sciences) Taisuke Sato (Tokyo Inst. of Technology),Linear Tabling,2,Tabling is Useful,Eliminate infinite loops path(X,Y):-edge(X,Y). path(X,Y):-edge(X,Z),path(Z,Y). Reduce redunda
2、nt computations fib(0,1). fib(1,1). fib(N,F):-N1, N1 is N-1,fib(N1,F1), N2 is N-2,fib(N2,F2), F is F1+F2.,Linear Tabling,3,Tabling in OLDT (SLG-WAM),A.,A.,.,producer,consumer,suspend/resume Complicate implementation freeze stacks overhead on standard programs garbage collection,table,A is suspended
3、after the existing answers are exhausted,Linear Tabling,4,Linear Tabling,A.,A.,.,pioneer,follower,table,A fails or becomes a producer after consuming existing answersA needs to be re-evaluated in some cases,Advantages Easy to implement Space efficient Overhead-free Disadvantage Re-computation Optimi
4、zations Subgoal optimization Semi-nave evaluation,Linear Tabling,5,The Linear Tabling Framework,Augmented programs,p(X,Y):-p(X,Z),e(Z,Y),memo(p(X,Y). p(X,Y):-e(X,Y),memo(p(X,Y). p(X,Y):-check_completion(p(X,Y).,p(X,Y):-p(X,Z),e(Z,Y). p(X,Y):-e(X,Y).,Linear Tabling,6,The Linear Tabling Framework (con
5、t.),table_start(A) Executed when a tabled subgoal A is encountered memo(A) Executed when a clause succeeds check_completion(A) Executed after all clauses have been tried.,Linear Tabling,7,Definitions,Loops, pioneers and followers,A derivation GiGj forms a loop if Gi=(A,) and Gj=(A,) A and A are vari
6、ants A is an ancestor of A Subgoal A is called a pioneer and A is called a follower of A.,Linear Tabling,8,Definitions (cont.),Top-most looping nodes and subgoalsA node in an SLD-tree is called a top-most looping node if the selected subgoal of the node is the pioneer of a loop that is not contained
7、 in any other loops.,Linear Tabling,9,A Linear Tabling Method,table_start(A) If A is complete, resolve A by using answers. If A is a pioneer, register A and resolve A by using program clauses. If A is a follower, resolve A by using answers and fail A after all existing answers are exhausted.,Linear
8、Tabling,10,A Linear Tabling Method (cont.),memo(A) Add A into the table and fail.,Linear Tabling,11,A Linear Tabling Method (cont.),check_completion(A) If A has never occurred in a loop, complete A and resolve A by using the answers. If A is a top-most looping subgoal If no new answer was produced i
9、n the last round, then complete A and resolve A by using the answers Otherwise, start a new round of evaluation of A. If A is a looping subgoal but not a top-most one Set As state to temporary complete and resolve A by using the answers,Linear Tabling,12,Example,p(X,Y):-p(X,Z),e(Z,Y),memo(p(X,Y). (p
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
本资源只提供5页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
2000 积分 0人已下载
下载 | 加入VIP,交流精品资源 |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- TABLEDPROLOGANDLINEARTABLINGPPT
