Picat Tabling for Memoization 3 — Questions and Answers
Question 1: What is the difference between Picat's `table` and a hand-written assert/retract memoization pattern in Prolog?
- assert/retract is faster because it uses native memory.
- There is no practical difference; both are equally automatic.
- `table` is declarative and automatically managed, while assert/retract requires manual cache management. (Correct answer)
- `table` only works for deterministic predicates, while assert/retract works for all predicates.
Correct answer: `table` is declarative and automatically managed, while assert/retract requires manual cache management.
Picat's `table` directive automates cache storage and retrieval, eliminating error-prone manual assert/retract coding.
Question 2: In Picat, if you declare `table fib(+,-)` and call `fib(10, X)`, what is stored in the table?
- The pair (10, X_value) mapping input 10 to the computed output. (Correct answer)
- The entire call stack leading to fib(10, X).
- Only the integer 10 as a key.
- The goal fib(10, X) in its unresolved form.
Correct answer: The pair (10, X_value) mapping input 10 to the computed output.
The table stores the input argument(s) mapped to their corresponding output value(s).
Question 3: When tabling is used with a non-deterministic predicate in Picat, what does the table store?
- Only the last answer found.
- Nothing, because tabling requires deterministic predicates.
- All answer tuples produced by the predicate for the given input. (Correct answer)
- Only the first answer found.
Correct answer: All answer tuples produced by the predicate for the given input.
Picat's tabling system stores the complete set of answers for non-deterministic predicates, supporting full tabled search.
Question 4: Which of the following best describes a 'table entry' in Picat's tabling mechanism?
- An entry in Picat's global variable store.
- A row in an external SQL database.
- A checkpoint in the Picat virtual machine's backtracking stack.
- A record associating a call pattern (input) with its set of computed answers. (Correct answer)
Correct answer: A record associating a call pattern (input) with its set of computed answers.
Each table entry pairs a call pattern with the answers accumulated for that pattern.
Question 5: What happens in Picat if you call a tabled predicate with an uninstantiated input argument declared as `+`?
- The call silently fails.
- Picat generates all possible inputs and tables each result.
- The predicate is called normally without tabling.
- An instantiation error is raised because `+` requires a bound argument. (Correct answer)
Correct answer: An instantiation error is raised because `+` requires a bound argument.
Mode `+` requires the argument to be bound at call time; calling with an uninstantiated `+` argument causes an instantiation error.
Question 6: Which statement about memory usage in Picat tabling is accurate?
- Tabling uses memory only for the first call to each predicate.
- Tabling uses less memory because it prunes the search space.
- Tabling uses more memory than naive recursion because it stores all computed results. (Correct answer)
- Tabling uses the same memory as non-tabled execution.
Correct answer: Tabling uses more memory than naive recursion because it stores all computed results.
The memoization cache consumes memory proportional to the number of distinct call patterns and their answers.
Question 7: In Picat tabling, what is a 'suspended call'?
- A call that exceeds the tabling depth limit.
- A call that was previously answered and is now being replayed.
- A call that has been explicitly paused by the programmer.
- A recursive call that is waiting for the answer of a subgoal that is already being computed. (Correct answer)
Correct answer: A recursive call that is waiting for the answer of a subgoal that is already being computed.
Suspended calls arise in tabled evaluation when a call depends on results from an ancestor call that hasn't completed yet.
Picat Tabling for Memoization 3
What is the difference between Picat's `table` and a hand-written assert/retract memoization pattern in Prolog?