Picat Tabling for Memoization 5 — Questions and Answers
Question 1: What is the effect of placing the `table` declaration after the predicate clauses in Picat?
- It causes a compilation error or warning because `table` must precede the predicate clauses. (Correct answer)
- Tabling is applied retroactively to all prior calls.
- The declaration is silently ignored.
- Tabling is still applied but only to the last clause.
Correct answer: It causes a compilation error or warning because `table` must precede the predicate clauses.
In Picat, `table` must appear before the predicate definition; placing it after leads to an error.
Question 2: For the longest common subsequence (LCS) problem, why is tabling particularly effective in Picat?
- LCS has no recursive structure so tabling reduces the code size.
- Tabling allows LCS to run in parallel across multiple cores.
- Tabling converts LCS from O(n²) to O(n log n).
- LCS has overlapping subproblems of the form lcs(i,j) that are recomputed many times without tabling. (Correct answer)
Correct answer: LCS has overlapping subproblems of the form lcs(i,j) that are recomputed many times without tabling.
LCS subproblems overlap heavily (each cell depends on three adjacent cells), making tabling essential for polynomial performance.
Question 3: In Picat, what is the purpose of the `nt` (no-table) mode specifier within a `table` declaration?
- It flags an argument as non-terminal in the grammar sense.
- It specifies that the argument may hold a null value.
- It marks an argument that should not be used as part of the tabling key, effectively ignoring it in the lookup. (Correct answer)
- It disables tabling for that specific clause.
Correct answer: It marks an argument that should not be used as part of the tabling key, effectively ignoring it in the lookup.
`nt` excludes an argument from the call pattern key, useful when an argument is always the same or irrelevant to caching.
Question 4: What is a potential pitfall when using global variables inside a tabled Picat predicate?
- Tabling automatically resets global variables on each reuse.
- Global variable side effects are not captured in the table, so replayed answers may reflect stale or incorrect state. (Correct answer)
- Global variables cause tabling to store extra state, increasing memory use.
- Global variables are forbidden inside tabled predicates.
Correct answer: Global variable side effects are not captured in the table, so replayed answers may reflect stale or incorrect state.
Tabling only caches logical outputs; if the predicate relies on or modifies global state, cached replays won't re-execute that state change.
Question 5: Which property of a problem makes it well-suited for Picat tabling as a DP strategy?
- Greedy-choice property and monotone objective
- Linear constraint satisfaction with a unique solution
- Optimal substructure and overlapping subproblems (Correct answer)
- Divisibility into independent non-overlapping subproblems
Correct answer: Optimal substructure and overlapping subproblems
DP—and by extension tabling—works best when subproblems overlap and solutions compose optimally, exactly the conditions tabling exploits.
Question 6: When Picat's tabling handles a mutually recursive pair of predicates (e.g., even/1 and odd/1), what mechanism ensures termination?
- An exception is raised for mutual recursion in tabled predicates.
- The tabling system converts mutual recursion into a single non-recursive predicate.
- Picat inserts an automatic depth counter to cut off recursion.
- The iterative fixpoint computation detects when no new answers are added and halts. (Correct answer)
Correct answer: The iterative fixpoint computation detects when no new answers are added and halts.
Picat's tabling uses iterative fixpoint evaluation: it repeats evaluation rounds until the answer set stops growing, guaranteeing termination for finite models.
Question 7: What does Picat's `table_find/3` built-in allow a programmer to do?
- Find all predicates that have been tabled in the current session.
- Search the tabling store for answers matching a partial pattern using Prolog-style unification.
- Query the tabling store to retrieve a cached answer for a given call pattern without re-executing the predicate body. (Correct answer)
- Locate the memory address of a specific table entry.
Correct answer: Query the tabling store to retrieve a cached answer for a given call pattern without re-executing the predicate body.
`table_find/3` lets you directly interrogate the memoization cache for a call's stored result.
Picat Tabling for Memoization 5
What is the effect of placing the `table` declaration after the predicate clauses in Picat?