Rich, Thank you for writing this post. I had much fun reading your story - the footnotes are hilarious.
Anyway, I now understand why Stacks is written in Java, and indeed the choice is completely justified. Looking at the different tuple implementations (and after reading Mark’s story) I believe they are pretty optimal. There might still be an interesting opportunity for optimisation which I’ve employed in Enchilada: A ternary flag that indicates whether a (sub) tuple is (ascending/descending/not) sorted. This flag can be used to speed-up the sorting of big, nearly sorted, tuples. There are probably many more optimisations that can be thought of. The great thing is, Avail easily allows such optimisations to be implemented. Ah, the possibilities are endless. Cheers, Robbert. > On 27 Jan 2015, at 04:29, Richard Arriaga <[email protected]> wrote: > > Robbert, > > Sorry I've been missing in action. I was out of town unexpectedly for a > little more than a week dealing with some family stuff. All that time I was > without my computer. I tried to keep up with emails on my phone, but reading > and writing technical emails on a phone just doesn't work well for me. Being > without my computer for a week or so isn't generally a big deal, but between > correspondence and development, it seems that I ended up out of town during > quite an active Avail spell. I've only been back a few days, so between > catching up on my day job and spending a day deflating while playing computer > games, I haven't had a chance to really look at Avail yet. I only know about > this email chain because Todd came into my office today to poke me about it. > So consider this as my reentry into the world of Avail. > > While writing this email, I found that I kept typing up "asides". So much > so, I decided to add footnotes so that I can elaborate on things without > going off too much on a tangent. Besides, footnotes can hold fun facts1 > that don't really fit anywhere in the email! > > So onto tuples! ...or at least a less technical anecdote about my dealings > with tuples. > > To be honest, it has been a while since I built ReverseTupleDescriptor, so I > had forgotten that I had built them. If I'm not mistaken, that was my first > real entry into working under the Avail hood. When I first jumped on board > with Avail, I primarily programmed Avail. At the time, I really was the only > one as Mark and Todd were busy building things under the hood. It was my job > to suffer through Avail to discover the pain points in programming Avail as > well as to find holes in the library. This was during a time before the > Avail workbench, so Avail was mostly run in the console in Eclipse. Error > reporting was practically non-existent2 and Avail was just plain slow. > > Throughout a lot of my Avail adventures, I find myself defaulting to tuples > for a lot of things. Tuples, as they exist in Avail, are so damn useful. A > strongly typed heterogenous collection is something that is seemingly absent > in just about every language that I know of3. I could go on about why they > are great, but I don't think I need to preach to the choir. > > The bad thing about Avail's tuples is that they are slow and not so long ago, > they were painfully slow. Tuples have been the basis for a lot data > structures in the Avail library, thus making lots of things in Avail slow. > My initial 3 or 4 attempts at developing Stacks4 was actually done in Avail. > I was using iterators5 to achieve this. My work was heavily tuple-dependent. > The ultimate problem that drove me to build Stacks in Java was Avail could > not efficiently parse an Avail file. I believe a 500 line Avail file took > approximately 6 minutes to parse. That of course was not scalable for the > untold thousands of lines Avail code that would need to be parsed. That was > pretty much when it became glaringly obvious that tuples were just highly > inefficient. > > Creating primitives to perform tuple operations in constant time can actually > be quite easy. I believe a number of them are done through lazy evaluation > while others are just simple wrappers that benefit from Avail's immutability. > If I'm not mistaken, I think Leslie's introduction into primitive writing > was IntegerIntervalTupleDescriptor while mine was ReverseTupleDescriptor. > IntegerIntervalTupleDescriptor6 is an example of something evaluated lazily, > basically evaluating the value at an index when it is being asked for7. Todd > spoon fed me the ReverseTupleDescriptor assignment. At the time, I knew > tuples were a problem but I wasn't sure what I could do about it. Being > pointed in this direction actually helped in elevating my own level of > coding; from that point on, I began to look at problems with more of an eye > towards efficiency where I previously was more concerned with just completing > the task. ReverseTupleDescriptor is an example of a wrapper around a base > tuple8. The trickiest part of it was trying to decide how to handle > TreeTupleDescriptor. This was by far the most complex of all the > TupleDescriptors. It wasn't readily clear if I could just translate the > reverse of the indices into the tuple. I spent some time with Mark > understanding TreeTupleDescriptor before asserting the general solution also > worked for TreeTupleDescriptor. > > I know I didn't hit all the technical points you were asking about, but I > hope I gave you some insight into what it's like writing a tuple primitive. > If you can think up of a way to optimize some functionality of a tuple, > perhaps there is an opportunity to add a primitive to the VM. Doing so is > definitely a great way to get your hands dirty without tackling something too > imposing. > > -Rich > > Footnotes > 1. Fun fact #1, I skipped reading Mark's replies in this email chain because > what does Mark know about Avail anyway? ;) > 2. The absence of any semblance of error reporting made learning an > undocumented, unsupported, raw programming language as painful as you might > imagine. I spent many a night after a long day of Availing, crying myself to > sleep. > 3. I am open to being corrected. I take being wrong about a thing very > well. If I was always right, then life would be boring as there would be > nothing new for me to learn. In fact, the more I learn about other > languages, the more I feel I can contribute to Avail. > 4. Stacks is what takes Avail's comments and generates the library > documentation currently online. > 5. This was the version of iterators before Mark redid everything for file > IO. > 6. An example of an IntegerIntervalTupleDescriptor is the tuple with the > values 1 through 500 in that order. > 7. I'm being lazy here as I didn't verify that this is the case. I hazily > remember it to be lazy evaluation and that would make sense. Consider this > the anti-footnote as in I'm providing no verification! > 8. The majority of the solution was simply creating a wrapper for reversing > the indexing into the core immutable tuple; a little mathematical translation > to make the last element the first and the first element the last. Avail's > immutability ensured that I wouldn't need a copy of the tuple, though if the > tuple was arbitrarily small enough (64 elements I believe) a copy was made. > Many of the TupleDescriptors have their own implementation of A_Tuple > o_TupleReverse(final AvailObject object), where as TreeTupleDescriptor > inherits the generic TupleDescriptor. >
signature.asc
Description: Message signed with OpenPGP using GPGMail
