Picat Tabling for Memoization Questions and Answers

Question 1

A programmer is writing a Picat function to calculate Fibonacci numbers, which is notoriously inefficient due to repeated calculations of the same subproblems. Which Picat directive should be used to automatically memoize the results of the function calls and significantly improve performance?

Accepted Answer

table

Answer

In Picat, the `table` directive is used to enable tabling, which is a form of memoization. When a predicate or function is declared with `table`, Picat stores the results of its calls and reuses them for subsequent identical calls, avoiding redundant computation. This is especially effective for functions like Fibonacci where the same subproblems are computed multiple times.

Question 2

Consider the following Picat code for finding a path in a graph. Without tabling, this code could enter an infinite loop if the graph contains cycles. How does adding the `table` directive prevent this issue?

```picat
path(X, Y) => edge(X, Y).
path(X, Y) => path(X, Z), edge(Z, Y).
```

Accepted Answer

It memorizes calls to `path/2` and reuses answers, preventing re-exploration of the same subgoals.

Answer

Tabling works by storing the subgoals that are called and their corresponding answers in a table. When a new call is made that is a variant of a previously tabled call, the system uses the stored answers instead of re-deriving them. In a graph with cycles, a simple recursive search can loop indefinitely. By tabling `path/2`, Picat will detect that it is trying to solve a subgoal it has already encountered in the current derivation path (a loop) and will use the existing answers or suspend the call, effectively breaking the infinite recursion.

Question 3

Which of the following is the primary benefit of using tabling in Picat for dynamic programming problems?

Accepted Answer

It changes the asymptotic time complexity of algorithms with overlapping subproblems from exponential to polynomial/linear.

Answer

The key advantage of tabling, a form of memoization, is performance improvement for problems with overlapping subproblems, which is the hallmark of dynamic programming. By storing and reusing the results of subproblems, it avoids redundant computations. This can change the complexity of a naive recursive algorithm from exponential (e.g., O(2^n) for Fibonacci) to linear (e.g., O(n)), which is a dramatic and crucial optimization.

Question 4

A developer needs to find the shortest path in an unweighted graph and decides to use tabling. They want Picat to automatically keep only the answer with the minimum path length for any given pair of nodes. Which feature of Picat's tabling system would be most suitable for this scenario?

Accepted Answer

Mode-directed tabling.

Answer

Picat offers 'mode-directed' tabling, which provides more control over what gets stored. By specifying modes like `min` or `max` for output arguments, you can instruct the tabling system to store only the best answer found so far for a given set of input arguments. For a shortest path problem, declaring a mode of `min` for the path length argument will ensure that the table automatically retains the path with the minimum cost.

Question 5

Which of the following statements about Picat's tabling mechanism is FALSE?

Accepted Answer

It requires manual cache invalidation using a special built-in predicate.

Answer

Picat's tabling is largely automatic. Once a predicate is declared with `table`, the system manages the storage and retrieval of answers without requiring the programmer to manually invalidate or clear the cache during normal execution. While there is a built-in `initialize_table` to clear all tables, it's for resetting the state, not for manual cache invalidation as part of the core logic. The other statements are true: tabling applies to both predicates and functions, uses a linear tabling mechanism, and is enabled with the `table` keyword before the rules.

Picat Practice Test

Picat Practice Test

Picat Tabling for Memoization Questions and Answers