Thursday, 4 August 2016

Bookmarks replace Enumerators

In today's new version of Pyrrho, use of .NET Enumerator classes has been replaced with Bookmarks.
Throughout the source code in the new version you will see for statements of the form
for (var a=b.First();a!=null;a=a.Next()) {..} instead of foreach(var a in b).
This is because bookmarks cannot be used with foreach; but they bring other advantages which this posting will try to explain.
A quick reminder of how .NET's IEnumerators work: given a collection class C, GetEnumerator() returns an IEnumerator which initially does not have any value (it points before the first item in the collection). On such an IEnumerator, MoveNext() returns a boolean saying whether a move to the next item in the collection succeeds, Current gives the current member of the collection and Reset repositions the enumerator back to before the start. Evidently such enumerators contain mutable data, and MoveNext will modify the internal structure of the Enumerator class.
Pyrrho takes transactions and program state obsessively seriously. I like to control side effects of everything. Pyrrho uses immutable data structures wherever possible, e.g. for trees and even databases. Bookmarks can be implemented using immutable data (all fields are readonly) and this is a great advantage from my viewpoint.
So if b is a member of a collection class C, we can have an associated bookmark class (probably called C.Bookmark), with the following standard methods: 
  • a static method New(b). If the colection is empty New(b) will return null), otherwise it gives a bookmark for the first member of the collection. b.First() is implemented as New(b).
  • an instance method Next() which returns a bookmark for the next member of the collection, or null if there is none.
  • value() to access the current member of the collection.
I will get around to benchmarking the new version soon to see what effect on execution speed this change brings, and in the meantime I welcome comments!

1 comment: