Tabling for Memoization Flashcards

Which Picat directive marks a predicate so that its results are automatically cached?

Answer: table

The `table` directive placed before a predicate definition enables automatic memoization in Picat.

In Picat tabling, what happens when a tabled predicate is called with arguments it has already been called with?

Answer: The stored result is returned without re-executing the predicate body.

Tabling returns the cached result immediately, skipping redundant recomputation.

What is the primary algorithmic benefit of tabling in recursive Picat programs?

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.

In a tabled Picat predicate with mode (+,+,-), what do the `-` signs indicate?

Answer: Output arguments whose values are stored in the table.

In tabling mode declarations, `-` denotes output (answer) arguments that the table records.

Which classic dynamic programming problem is most naturally expressed using Picat tabling?

Answer: Fibonacci sequence computation

Fibonacci has heavily overlapping subproblems that tabling eliminates, making it a textbook tabling example.

How does Picat's tabling handle a predicate that is called recursively before its result is fully computed (i.e., a loop)?

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.

What does the `table` declaration `table(+,+,min)` communicate to Picat's tabling system?

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.