Packed evaluation, execution choices and output cost

Must one query produce the whole truth table? · 0:00

Must one query produce the whole truth table? A single query asks for one bit, a count asks how many assignments return one, and a full vector asks for every result in a declared order. Packed evaluation stores and processes truth bits together. We will learn to distinguish that representation from execution choices and the work required by the requested output.

See the unpacked truth vector · 0:28

In false-first assignment order, the first four outputs are zero, one, one, one. The next two groups repeat that pattern because A and B are not both true. The last four outputs are one, zero, zero, zero. The vector contains sixteen answers.

Pack each answer into its bit position · 0:46

The backend defines bit k as the answer for assignment row k. In our example the packed integer is seven thousand nine hundred eighteen. Its low bit stores row zero, the next bit row one, and so on. Ordinary printed binary notation puts the highest bit on the left, so label the direction.

Operate on columns of truth bits · 1:09

A packed evaluator constructs one bit column per input variable. Bitwise AND combines the A and B columns, OR combines C and D, and XOR combines those two results. Each bit position performs the same Boolean calculation for its own assignment.

Recover a count or unpack the vector · 1:25

The packed integer has ten set bits, so the satisfying-assignment count is ten. The runnable helper bitset to bool array takes the packed integer and number of variables, then returns the same sixteen-entry vector as the scalar oracle. The earlier word unpack was explanatory shorthand, not an API call.

Separate storage from eager and lazy execution · 1:45

Packed versus unpacked describes representation. Eager versus lazy describes when work is performed. The repository’s named evaluation and materialization modes have specific behavior, so we do not treat lazy as a promise that a requested full matrix is free. A materialize call still asks for a concrete array.

Show when materialization happens · 2:08

Compare two schedules for the same rule and layout. In the first, build the full matrix immediately and retain it for later lookup. In the second, keep the compiled graph and request the matrix later. Both schedules eventually return the same array; the distinction here is when the explicit output is produced.

Check the current lazy wrapper’s return value · 2:26

Names alone can mislead. The current function named compile expression to C M lazy builds the shared graph and calls materialize C M before returning. Our example confirms that it returns the same dense array as the other wrapper. To defer final materialization explicitly, retain the compiled node and call materialize later.

The full output still grows exponentially · 2:48

For k independent Boolean inputs, a complete truth vector has two to the k entries. Packing reduces storage overhead, but the mathematical output still contains that many bits. A graph may stay small while its explicit truth table becomes large. State which artifact a size claim describes.

Your turn: name the output contract · 3:08

A caller wants only to know whether one specified configuration is accepted. Another caller wants every accepted configuration listed. Are those the same benchmark task? Decide what must be returned before comparing their execution times.

Prediction pause: 8 seconds.

Answer: the contracts are different · 3:31

The first task returns one Boolean answer. The second must produce a potentially large list of assignments. Timing them as if they were equivalent would be misleading. Next we will define a fair comparison that accounts for preparation, repeated queries, and the exact output returned.