About The Contest
The first ever Olympiad of Misguided Geeks contest at Worse Than Failure (or OMGWTF for short) is a new kind of programming contest. Readers are invited to be creative with devising a calculator with the craziest code they can write. One lucky and potentially insane winner will get either a brand new MacBook Pro or comparable Sony VAIO laptop.
Entry #100348: VertexCalc
by Paul Gaspardo
I used the IDD methodology (impulse-driven development), paying no attention to organization or documentation, and started very, very late. Most of the code was written in the last few hours, and I submitted it at the last minute. As stated, In the end I ran out of time, and was left with an uncommented, unfinished, not totally tested slab of code in which not even addition worked completely. Since there are no comments in the code, I tried to replicate what they might have said here.
Note to possible future employers: Please consider that I wrote this as an undergrad, finishing up Computer Science II, when I should have been studying for final exams.
This calculator was supposed to do its math entirely using nodes on a graph. All numbers and the results of operations were to be represented using a node, or vertex (Vert). Each
Vert has two pointers (arrows), referred to as lt and rt, which can point to other Verts, or NULL. By chaining Verts together, virtually anything can be represented. Naturally, numbers are made from a Vert. The lt arrow points to the digits, and the rt arrow points to a Vert whose lt arrow specifies if the number is negative (if positive, NULL; otherwise, any Vert) and whose rt arrow specifies the number of decimal places. If this rt arrow is NULL, there are no decimal places, otherwise there are as many decimal places as there are Verts chained together through their lt arrows.
Digit Verts represent decimal digits. A Digit's lt arrow points to the digit to the left of the current one. If there is no digit to the lt, this value is NULL. A Digit's rt arrow points to a chain of Verts connected through their rt arrows, the length of which is the value of the digit. If the digit is zero, the rt pointer is NULL.
Verts are maintained on a statically allocated "heap", and garbage collected. Because the heap is statically allocated, and each Vert is the same size, the garbage collector is very simple. Each Vert has, in addition to its lt and rt pointers, a _gc_tag. When a new Vert is requested, the allocator simply returns the first Vert whose _gc_tag is not equal to the active tag (and of course updates the _gc_tag accordingly). If all the Verts are marked active, the collection system springs into action.
The collection system simply re-marks all the active objects--that is, all the Verts accessible from the stack--then resets the allocator. All the inaccessible Verts will have the old active _gc_tag, so they will automatically be inactive. To find these Verts, the collector utilizes a "shadow stack" statically allocated on the heap, with pointers to the Vert pointers on the real stack, managed with the help of a bunch of macros which replace most control structures. This system, while fragile, allows for precise garbage collection (at least for Verts) unlike the Boehm-Demers-Weiser conservative garbage collector.
A TOUR OF THE CODE
vertex: v, number: n, digit: d, char: c, boolean: b, string: s
The macros primarily maintain the shadow stack, an array of pointers to pointers to Verts, and, more specifically, update a global variable (sda__) storing the depth of the shadow stack so the collector knows what to collect. sda__ is incremented each time a variable is declared in the innermost block, then is decreased by that same amount when
the innermost block is left. The variable sdl__ is declared in every block, and is the number of declared Verts in the innermost block. Variable sdf__ is declared once per function, and maintains the number of declared Verts in the current function outside the innermost block (this handles Return statements). Additionally, sdb__ and sdx__ help deal
with Break and Continue statements. (sdx__ is the number of Verts in the innermost block outside the loop, and sdb__ is the number of Verts outside the innermost block but inside the loop.) Finally, sdl_ex__ seems to do nothing... :)
The My macro declares a fresh Vert in the current scope. The sugar__ variable is synctactic sugar so My(v)=VAlloc() works.
The Accept macro should be applied to function parameters. It ensures that Verts not declared by the calling function are accounted for, so the garbage collector won't collect more than it has to.
Both My and Accept place a pointer to the declared variable (a pointer to a Vect) at the end of the shadow stack and increment sda__
Note: Functions beginning with an underscore are functions internal to the following function without an underscore. Example: _VCopy_clear is internal to VCopy
VAlloc allocates a fresh Vert. It locates the first inactive Vert (a vert whose _gc_tag != active_tag) on the statically allocated heap, activates it (sets _gc_tag = active_tag), then returns a reference to it. If the end of the heap is reached (all Verts have been allocated) it's time to collect the garbage: VAlloc increments the active_tag, then re-tags all the Verts accessible from the shadow stack with this new tag (using _VAlloc_tag recursively), and finally returns to the start of the heap to find the first inactive Vert. (Note, there is a possibility of an infinite loop in the case of an "out-of-memory" error)
VCopy copies a subgraph of Verts, with the parameter v as the base. Each Vert has, in addition to lt and rt pointers and a _gc_tag, a pointer to a copy (_cp) which is always NULL except during a copy operation. (The _cp variable therfore specifies both where the copy is and if a copy exists--this is important for the _VCopy_follow function) The copy operation consists of two parts: first, _VCopy_follow is called recursively to actually copy the Verts, then _VCopy_clear is called to zero the _cp variables for cleanup.
Turn a decimal digit into a char. Decimal digits consist of a chain of Verts connected via their rt pointers, the length of this chain specifying the value of a digit (4 Verts in a row = '4', zero Verts = '0', etc)
Turn a string into a decimal number. This function creates a number skeleton, then hands off the actual building of the number to _NFromS_makeDigits, which calls itself recursively from the end of the string to the start, building the number up along the way: Each time a digit is found, it is tacked onto the start of the number; when a negative sign is reached, the number is set to be negative; and when a decimal place is found, the number's decimal place count is set to be the number of digits so far (dpAccum).
Turn a number into a string, by filling in a buffer backwards (from end to start). Basically, each for each digit in the number, a char representation of that digit is added to the start. While this happens, the chain of Verts representing the number of decimal places is walked, and when its end is reached, a decimal point is prepended to the string. Finally, if the number is negative, a negative sign is placed at the start.
Match the number of decimal places in two decimal numbers. This is important in the add operation, and probably subtraction at least. It works by recursively walking the chain of Verts for the number of decimal places for both numbers in parallel, until one of them ends. If both end, the function returns, but if only one did, additional decimal places are repeatedly added to the number with fewer decimal places, until they are both the
Remove extraneous zeroes from the start of a number. First, the first digit to the left of the decimal place is found. Next, the chain of digits is recursively walked until the first digit is reached; if it is a zero, it is cut off from the chain. Digits are then cut off until the first nonzero digit remains.
-DV (a macro)
This macro is a shorthand declaration for a Vertex.
The d0-d9 simply declare the digits 0-9, using the previous digits to be more efficient.
The s0-s27 and x0-x27 are for the add operation, described below
Add two numbers. After building a number skeleton, it is supposed to normalize the two numbers (by matching the decimal places) first. The number of decimal places in the sum is then set to be the number of decimal places in the two addends. To actually add the numbers, NAdd iteratively walks along the digit chains of the two numbers in parallel until they both finish there is no carry digit, stopping for a particular digit chain once it has ended. For each iteration, all 3 digits (2 from the numbers being summed,
plus the carry digit) are summed together by "counting"--starting from the Vert x0 (noted in the DV section) the rt pointers of the digits are successively followed in parallel with the rt pointers of the x
Testing function that somehow stuck around
First handle specific cases that don't work. Next, convert the two ops into strings, then Numbers. Add the numbers, then convert the numbers to strings, then return the string converted to a float.