This past week I’ve worked on adding list support to nom, including lazy lists and infinite lists. Lists in Perl 6 have had a bit of a convoluted history; early drafts were very non-specific about how Lists should work, and early designs tended to run into problems during implementation, leading to many redesigns of the spec.
Rakudo has gone through at least five different re-implementations of lists and arrays; the latest occured in Summer 2010 in preparation for the Rakudo Star release. Lists are extremely core to all of Perl 6, so small changes tend to impact the entire codebase. Also, features such as laziness and infinite lists invalidate many assumptions we Perl programmers have about working with lists and arrays. For example, asking a list for its size (i.e., +@a) generally destroys any laziness it might have had, as it has to go and generate all of its elements. Similarly, storing a lazy list inside of an array loses laziness, since array assignment is eager in Perl 6.
(For those who are wondering: array assignment defaults to eager evaluation because otherwise you get all sorts of surprising and non-Perlish action-at-a-distance effects.)
Similarly, passing I/O objects to various list functions would end up consuming the I/O stream entirely, such that the contents were lost to the caller. But you don’t want to adopt a model where you preserve every element all of the time, because then filters such as map and grep fail to act like pipelines and become very expensive in terms of memory consumption.
So, the Perl 6 specification and implementations have been through quite a few false starts before landing on a lists API that seems to work. We now have Lists, Arrays, Parcels, Captures, LoLs, Nil, Scalars, Seqs, flattening, interpolation, sinks, “mostly eager”, “mostly lazy”, and a bunch of other things that are used behind-the-scenes to get things to “just work” for the typical Perl 6 programmer. If seeing all of these new types frightens you, then perhaps a physics analogy helps: many of the details are like quantum physics to chemists — the Perl 6 implementors have to understand the quantum physics, while Perl 6 programmers can do a lot of useful chemistry without having to be aware of the gory details underneath.
Rakudo (master) contains the “first-draft” implementation of the latest lists API, developed last summer. Its emphasis was more on “get something working for Rakudo Star” than “make something elegant and efficient”. The key insight that enabled us to finally get something working is that iterators have to act immutable. More on this in a later post.
My original plan was to go back and revisit lists in Rakudo master, but with the “nom” branch making as much progress as it has (over 500 commits in the last 30 days!), I’ve decided to work on it there first. Nom’s new object and a ton of other internal improvements make the implementation a lot easier. In fact, unlike the previous implementation of lists, this new one is being written almost entirely in Perl 6. For efficiency reasons we may later convert parts of the newimplementation back to PIR, but we’ll do that only after we have a working P6 implementation first and we can benchmark it to see where the bottlenecks are.
Thus far the new implementation is working out extremely well. Because it’s in Perl 6, and because we now have far better object and container models than we previously had, it’s a much cleaner and more elegant implementation than before. So far it’s still slower than Rakudo master’s lists (which are already horribly slow), but it is also much easier to inspect and optimize than it was previously. For example, yesterday I was able to hotpath the code for generating numeric ranges such that it’s now several orders of magnitude faster than what we have in the master branch. Jonathan was able to profile the code and found a memory leak and another 30% improvement. So, we expect great increases in performance very soon. As far as capability, nom’s lists already handle some features that Rakudo master doesn’t get right yet.
I have a pending Hague Grant to write up the documentation for lists in Perl 6, primarily Synopsis 7. (The current Synopsis 7 draft is at least two iterations out of date with respect to the current design, which confuses a lot of people.) Over the next week or so I’ll finish up the implementation in nom, then write up the results as the new Synopsis 7 and make edits to the other synopses as appropriate. I’ll mark progress here on the blog and provide some examples of the various concepts as that progresses.
If you’re just dying to see what we have now, the source code for Lists and the other builtin types is available from the nom repository on github, in https://github.com/rakudo/rakudo/tree/nom/src/core .
Pm
