The following is my submission for Assignment 1 in the course 20875 - SOFTWARE ENGINEERING taught by prof. Laurent Poirrier at Università Bocconi.
The assignment consisted of writing a program capable of parsing a boolean formula, simplifying it internally, and producing an .ppm image output, representing the computational graph of the formula as a circuit.
TLDR: Write a compiler that takes a boolean formula and converts it to a valid and compact circuit that encodes its logic.
The definition of the formula, which is provided in a Context Free Grammar Form, is a series of logical operations between variables, where the input variables have an associated "canonical" index, but intermediate variables may also get defined and referenced internally. Similarly, outputs are also created canonically by using a sequential output numerical ID.
The following is an example for the typical input:
Cin = in[0];
A = in[1];
B = in[2];
Cout = (A and B) or (A and Cin) or (B and Cin);
S = ((not Cout) or (A and B and Cin)) and (A or B or Cin);
out[0] = Cout;
out[1] = S;In the task, each pixel represents a building block, with color being used to differentiate the type:
White(VOID): empty space, does not carry signal.Blue(CARRY): propagates horizontal and vertical signals separately, without cross interference. Can be used as a safeintersectionbetween signals moving in perpendicular directions.Black(SPLIT): merges all the signals coming from all four sides. Can be used to split a signal or bend it around corners, but is not allowed to combine two differing signals.Red(NOT): consumes a signal and generates its logical negation to the right.Yellow(And): consumes two signals and produces to the right a new AND signal.Green(Or): consumes two signals and produces to the right a new OR signal.
As an additional constraint, the endpoint of the computation must always have the same structure (ie. in[index] but also out[index]). For a standardized input and output, the first layer of the circuit is fixed to provide the inputs with one White cell separating them vertically, and the same happens with the output layer. For example, a formula with a reference to in[9] inside of it must present on the first column left of the circuit, all 10 inputs as blue blocks, which are placed at positions (x, y) = (0, 2j). The same restriction is not imposed on the output layer: the last column must only connect the outgoing signals.
In order for a circuit to be valid, all logic gates must have the correct association between inputs and outputs, and no signal-carrying cell must be able to interfere with another directly. For example, merging signals without relying on a logic gate is not allowed, though it is possible to split a signal using a Black cell, for instance to consume a signal and obtain three more of them.
The following circuit diagram is the output of my submission for the formula shown above as an example.
Multiple constraints had to be accounted for in the development of the solution:
Correctness: the whole circuit has to be correct, without illegal states or combinations. In addition, for any combination of inputs, the output obtained by following the signals must always be correct. Any single mistake results in the whole circuit being considered wrong.
As a result, I inserted assert into every core aspect of the program. Moreover, auto-generated test cases were used to check the output of the program on known inputs after every update. I briefly relied on a fuzzer to further test the parser, but deleted it in later commits.
Length: the complete program must perform parsing, cleaning, sorting, laying and verifying, in order to take the formula as text and produce it as a valid and compact circuit. Each step introduces a new possibility of failure, as well as losing information due to a logical error in transforming representations. Since some of the inputs are too large to verify, this makes it theoretically possible for buggy code to appear correct.
Due to the size and time constraint of the assignment, as well as my limited familiarity with the Rust Language, I relied heavily on ChatGPT, while treating it as an untrusted companion. We were not forced to use the language, but I wanted a challenge.
Compactness: for a bonus point, the final solution had to produce results below a certain area. This did not bias the shape of the final output in width or height, but heavily encouraged more efficient logical steps.
I experimented thoroughly with different strategies on grid lined paper. This allowed me to find both a feasible approach to the problem, and a most compact set of basic layout patterns.
The development of the program was carried out in chunks following the control flow, as opposed to planning the whole logic before beginning with the implementation. Consequently, each component was developed with a slightly different attitude and tool set.
Parsing Pipeline: as a first step, the program reads the input one line at a time, verifying that the syntax for each line is correct, before parsing each expression and combining the variable references in order to build a directed acyclic graph representing the computation. Since the boolean functions have a variable number of inputs and outputs, the flexible structure of a computational graph is used.
Intermediate Pruning: after parsing the DAG, some light polishing is carried out in order to resolve duplicated links, encoding artifacts, and rebalance the tree in the case of chained operations (eg. NOT NOT -> ID). No advanced simplification or rewriting is carried out, since the formulas were already provided in a reduced form.
First Layer: constructing the first column, that is, the input layer, is straightforward, as the only necessary information needed is the highest index of the input variables mentioned in the formula. Following the specification, the input layer is obtained by alternating blue and white cells, where the signals of the blue cells are initialized to represent the appropriate signal references.
Topological Sort: Although I originally wanted to implement some highly-efficient parallel logic (who wouldn't really?) I quickly realized that the involved challenges called for a slow and steady wins the race mindset instead. As a result, I devised algorithms to derive the internal layers of the circuit by processing the DAG one node at a time. As a first choice heuristic, the DAG was sorted by dependency, and nodes were processed one at a time, resulting in a structure that gets paved column by column. Naturally, this choice makes the final outputs suboptimal, but definitely easier to work with.
Layer Processing: depending on the logical block, a different structure was used. As a general rule, the layer algorithm takes an existing layer and the description of the new logical gate, applies it, then extends all signals that need to be used in the future. At the same time, since it is possible for a signal to be used as input for many gates, an intermediate layer may have to be added in order to first duplicate a signal before applying the gate, which inevitably will consume one of them. The following code shows all Gate structs, depending on whether they extinguish the references they use or not. Since the implementation runs as a loop, but is memoryless (only the last layer matters), the instructions for the construction of each layer are passed as a list of IDs, coupled with the "surviving" values after the implementation of a gate.
pub enum Gate {
NotDrop { y_in: usize }, // input one of the gate
NotKeep { y_in: usize }, // input one of the gate
AndDrop { y_a: usize, y_b: usize }, // drop both refs
AndKeep { y_keep: usize, y_drop: usize }, // keep exactly one; true if input A is dropped
AndConserve { y_a: usize, y_b: usize }, // keep both
OrDrop { y_a: usize, y_b: usize },
OrKeep { y_keep: usize, y_drop: usize },
OrConserve { y_a: usize, y_b: usize },
}Which correspond to the following "canonical patterns", up to changing the relative vertical order between the circuits. Here, colored line over the cells show the signal identity: depending on drop/keep subtype, the signal must be preserved. Alternatively, it is possible to "lose" the signal from one layer to the next, allowing for more compact layers.
Assert and Necessary Checks: in order to somewhat guarantee the correctness of the output, I implemented a generic assert check at the end of each layer, verifying that the signals that were added and the ones that were dropped indeed match the requirements. Although it does not guarantee that the circuit is correct, it is a condition that must hold.
pub fn assert_layer_transition(prev: &[NodePixel], next: &[NodePixel]) {
// some ~500 lines
}Permutation: at this point, all the signals that need to be connected to the output layer are present at the last position, but they may be ordered vertically in the wrong order. As a result, it must be possible to rearrange the signals compactly, following an algorithm that is flexible enough to handle any case. Discussing the problem among colleagues, different strategies were being developed. One of the strategies that worked, consisted of converting all signals from being horizontally stacked to a vertical configuration, that is, one next to the other, going down. From this orientation, one signal at a time would be extracted, rearranging the information in a functional, albeit wide format. I set myself on considering alternative ideas: I constructed on paper a 5-cell wide tileable permuter, which could take two signals and swap them without intereference.
With this block, a solution would have involved a form of parallel bubble sort (brick sort) as an algorithm capable of sorting in ~5n sorting chunks. Still too wide. I then considered the idea of handling the position of each signal one at a time, in the following loop: bring a signal to the corrects position, extend the other signals, and repeat. Even better, this structure would be straightforward to implement, without background calculations or any algorithms like in the previous proposal. However, I quickly noticed a catch in my plan, as bringing the signal to the correct position would necessarily fight with any signal currently occupying that position. I also considered moving them out of the way, but as before, any change to the layout would have resulted in clunky rearrangements of the existing pathways, further messing with the current space...
It then hit me that if I could not move the signals to their final position in one step, I could at least bring them closer! As it turns out, a 1-vertical-offset incremental permuter could be constructed easily: bring each signal to its y-1 position, then propagate all signals forward by one step. At this point, it may look like there is a catch: a black block must be used to direct the path right, but this will create vertical interference. As it turns out, at the cost of permuting just one signal at a time, redirected signals will simply point to empty blocks, with no interference. This can be seen in the following image: although the black cells propagate the signal in all 4 directions, they eventually lead to a white cell, where the signals die.
At this point, we are almost done, but not quite: all signals are close to their destination, but lower by one cell. After some more brainstorming, I found a 2 wide tileable structure to address this final problem, with an exquisite lifting pattern that avoids interference by tiling in a grid manner. As before, signal redirections do not interfere, since they are made to point towards white cells. Neat!
|
The permuter structure can be appreciated in the following picture, in its
end-to-end form. Note that in spite of the high number of black cells,
there is On a personal note, I checked this fact multiple times, as it felt scarily close for comfort. As it turns out, the autograder also agreed with me. |
|
Final Linkage: having reached this step, I was quite satisfied with the code and the result. After a brief exchange with my classmate and friend Ali Emre Senel, I also noticed that I had a slightly different understanding of the final layer requirements. As it turns out, the first and last columns of the circuit had to be shown in full, and they had to be blue, not black. Great! So I added one more column at the ends and called it a day. I was not going to edit the pipeline, and I was pretty confident in my results anyway.
The final code produced the most compact images in the class. It produced correct circuits over the test set, and obtained near-full marks, excluding a parsing technicality which deducted half a point.
At the same time, the code ran about 30x slower than Ali's own submission (from 0.020s to 0.600s), as well as being twice as long in raw number of lines. I attribute these inefficiencies to the high degree of AI code, as well as the high number of assertions in my self-policing and paranoid code, which I did not remove for the release version.
Overall, I was quite happy with the results and the fun experience. In hindsight, I probably used more AI-generated code than was necessary, but the final results were correct, and given the fast-paced environment, I was happy with my submission.
For the task, we were allowed and encouraged to discuss strategies among each other, while not sharing the code directly, which was submitted individually. As a result, many early design choices were guided by close conversation with my friend Ali Emre Senel. Particularly, I never would have been able to obtain such a high score without the many edge case examples that he came up with, and the advice in setting up the fuzzer, which helped me detect additional bugs in my logic.
