v0.21.0

What’s New?

• A new reference counter
• Functions for converting datatypes

New Reference Counter

Most programming languages today feature automatic garbage collection, so that programmers don’t have to manage memory manually. Keelung a bit differently since we don't deal with memory, but we do manage something equally important: variables.

Variable Allocation/De-allocation

The compiler allocates variables for each input and output in a Keelung program, as well as when users define computations or constraints between variables.

However, not every variable proves to be essential; many of these variables will be eliminated by the optimizer at a later stage.

Variable Renaming/Reindexing

Variables in the constraint system are indexed by integers. Some of these indices may be skipped after optimization, creating empty “holes” in the constraint systems.

To address this, we reassign variables with new indices so that no numbers are skipped, and the constraint system becomes compact again.

Reference Counting

To identify which variables are skipped, we keep track of each variable's occurrence within a constraint system. This allows us to remove variables whose counts drop to zero.

Precise Counting of Unsigned Integer Bits

However, in our previous implementation, we treated each unsigned integer as a singular variable, resulting in all bit variables of an unsigned integer being retained, even if only a subset was actually used elsewhere.

We've addressed this issue by implementing a new reference counter that differentiates between the individual bits of an unsigned integer. This allows for precise reference counting without compromising the counter's performance.

Datatype conversion

The functions for converting between the primitive datatypes have been rewritten and renamed:

• fromField: Field → Comp n (UInt w)
• toField: UInt w → Comp n Field
• fromBools: [Boolean] → Comp n (UInt w)

You'll notice that all operations are centered around UInt in this design: Field ↔ UInt ↔ Boolean. For example, if you want to convert [Boolean] into UInt, you need to convert it into UInt first.

Check out our documentation site for more on how to use them!

What’s Next?

• Operators for slicing and joining unsigned integers (join, slice, …)
• Optimization for the implementation of AES