Picat Tabling for Memoization 2 — Questions and Answers
Question 1: Which Picat directive marks a predicate so that its results are automatically cached?
- cache
- memo
- persist
- table (Correct answer)
Correct answer: table
The `table` directive placed before a predicate definition enables automatic memoization in Picat.
Question 2: In Picat tabling, what happens when a tabled predicate is called with arguments it has already been called with?
- The call is silently ignored and fails.
- An exception is raised to prevent duplicate calls.
- The stored result is returned without re-executing the predicate body. (Correct answer)
- The predicate body is re-executed to verify consistency.
Correct answer: The stored result is returned without re-executing the predicate body.
Tabling returns the cached result immediately, skipping redundant recomputation.
Question 3: What is the primary algorithmic benefit of tabling in recursive Picat programs?
- It parallelizes recursive calls across CPU cores.
- It prevents stack overflow by limiting recursion depth.
- It automatically optimizes tail recursion into a loop.
- It converts exponential-time recursion into polynomial-time computation by caching subproblem results. (Correct answer)
Correct answer: It converts exponential-time recursion into polynomial-time computation by caching subproblem results.
Tabling eliminates redundant recursive calls, reducing exponential blowups typical in naive recursion.
Question 4: In a tabled Picat predicate with mode (+,+,-), what do the `-` signs indicate?
- Arguments that must be uninstantiated when called.
- Arguments that are ignored by the tabling mechanism.
- Output arguments whose values are stored in the table. (Correct answer)
- Arguments that trigger a new table lookup.
Correct answer: Output arguments whose values are stored in the table.
In tabling mode declarations, `-` denotes output (answer) arguments that the table records.
Question 5: Which classic dynamic programming problem is most naturally expressed using Picat tabling?
- Bubble sort
- Binary search
- Breadth-first graph traversal
- Fibonacci sequence computation (Correct answer)
Correct answer: Fibonacci sequence computation
Fibonacci has heavily overlapping subproblems that tabling eliminates, making it a textbook tabling example.
Question 6: How does Picat's tabling handle a predicate that is called recursively before its result is fully computed (i.e., a loop)?
- It immediately raises a loop_detected exception.
- It returns false for all looping calls.
- It falls back to standard Prolog-style depth-first search.
- It uses iterative computation to accumulate answers incrementally until a fixpoint is reached. (Correct answer)
Correct answer: It uses iterative computation to accumulate answers incrementally until a fixpoint is reached.
Picat's tabling supports tabled logic programs with loops via iterative fixpoint computation.
Question 7: What does the `table` declaration `table(+,+,min)` communicate to Picat's tabling system?
- Only calls where the third argument is minimal will be tabled.
- The third argument must be a positive integer.
- The third argument is an optimization objective to be minimized over all answers. (Correct answer)
- The predicate takes exactly three arguments and uses min-cost search.
Correct answer: The third argument is an optimization objective to be minimized over all answers.
Mode `min` instructs the tabling system to keep only the answer with the smallest value for that argument, enabling optimal substructure computations.
Picat Tabling for Memoization 2
Which Picat directive marks a predicate so that its results are automatically cached?