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
10、1) p(X,Y):-e(X,Y),memo(p(X,Y). (p2) p(X,Y):-check_completion(p(X,Y). (p3)e(a,b). (e1) e(b,c). (e2),1. p(a,Y0).,2. p(a,Z1), e(Z1,Y0), memo(p(a,Y0).,3. e(a,Y0), memo(p(a,Y0).,4. memo(p(a,b).,5. check_comp(p(a,Y0).,First round,p1,p2,e1,p3,program,Linear Tabling,13,1. p(a,Y0).,6. p(a,Z1), e(Z1,Y0), memo
11、(p(a,Y0).,10. check_comp(p(a,Y0).,Second round,p1,p3,7. e(b,Y0), memo(p(a,Y0).,8. memo(p(a,c).,use p(a,b),e2,9. e(c,Y0), memo(p(a,Y0).,use p(a,c),p(X,Y):-p(X,Z),e(Z,Y),memo(p(X,Y). (p1) p(X,Y):-e(X,Y),memo(p(X,Y). (p2) p(X,Y):-check_completion(p(X,Y). (p3) e(a,b). (e1) e(b,c). (e2),p(a,b).,program,t
12、able,p2,p(a,b). p(a,c).,Linear Tabling,14,Characteristics of the Method,Fixpoints are computed by iterating the evaluation of top-most looping subgoals Followers consume answers only Pioneers consume answers lazily Top-most looping subgoals consume answers after they are complete Other looping subgo
13、als consume answers after all clauses have been tried,Linear Tabling,15,Adopted and Related Tabling Strategies,Lazy answer consumption Local scheduling strategy in SLG-WAM Freire96 What to do after a follower consumes all available answers? Steals the pioneers choice pointer Zhou00 Fails the followe
14、r Guo & Gupta 01 Where to start re-computation? At the top-most looping subgoal Shen98 At every looping subgoal Guo01,Linear Tabling,16,Strengths and Weaknesses,Lazy answer consumption is suitable for all-solution search A basic operation used in PRISM Not suitable for single-solution search or prog
15、rams with cuts For the query, once(p(X), all solutions are computed even though only one is needed.,Linear Tabling,17,Optimization Techniques,Subgoal Optimization In each round of evaluation of a top-most looping subgoal, each subgoal needs to be evaluated only once. Semi-nave Optimization Mimic the
16、 semi-nave technique in bottom-up evaluation: at least one new answer is involved in the join of answers for each rule.,Linear Tabling,18,Semi-nave Evaluation in Linear Tabling,Let H:-A1,Ak,An be a rule where Ak is the last dependent subgoal of H. For a subgoal C of H, it is safe for Ak to consume o
17、nly new answers if: 1. C has occurred in an early round 2. No subgoal Ai (ik) has consumed a new answer.,Linear Tabling,19,Performance Evaluation,BP vs. XSB (CPU time),BP vs. XSB (Stack space),Linear Tabling,20,Papers,N.F. Zhou, Y.D. Shen, L. Yuan, and J. You: A Linear Tabling Mechanism, The Journal
18、 of Functional and Logic Programming, 2001. N.F. Zhou and T. Sato: Efficient Fixpoint Computation in Linear Tabling, ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming (PPDP), pp.275-283, 2003. N.F. Zhou, Y. Shen, and T. Sato: Semi-naive Evaluation in Linear Tabling, ACM PPDP, pp.90-97, 2004.,
