Tabling for Memoization Flashcards
7 cards from real Picat practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.
Read the first 7 Tabling for Memoization flashcards as text
What is the effect of placing the `table` declaration after the predicate clauses in Picat?
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.
For the longest common subsequence (LCS) problem, why is tabling particularly effective in Picat?
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.
In Picat, what is the purpose of the `nt` (no-table) mode specifier within a `table` declaration?
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.
What is a potential pitfall when using global variables inside a tabled Picat predicate?
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.
Which property of a problem makes it well-suited for Picat tabling as a DP strategy?
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.
When Picat's tabling handles a mutually recursive pair of predicates (e.g., even/1 and odd/1), what mechanism ensures termination?
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.
What does Picat's `table_find/3` built-in allow a programmer to do?
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.