dikini.net

In this post I'll try to sketch a number of related ideas about working with sequential collections, all of them expressed in php. Enumerations, enumerables, interators, iteratees and their cousins have been tortured to death, but as Eric Meijer and his team working on LINQ and Rx frameworks for .net show, it pays off doing it systematically. I'll revisit the Iterator and Subject Observer design patterns and will derive them systematically from first principles.

In php iterators come handy for all kinds of work on sequences - usually using

foreach( $sequence in $key,value) { ... }

The problem with foreach is that it is not composable, but there are a lot of functions and operations on iterators which are, at least in theory. I will try to show how to achieve composability by, first, composing the processing of each individual step and, later, by composing iterators. This can lead to easily reconfigurable applications and a more declarative style of programming.

The array code in the previous post on binary search in haskell is messy. Mostly due to my lack of style and the use of arrays, which add a layer of indirection and bounds checks.

This time, I'm going to rewrite the examples to be slightly more readable and I'll implement a linear interpolation search routine. The latter could be handy if function evaluation or array access (access to data on disk?) are relatively slow, and the data is sorted and relatively linear. Although the implementations could be coded even tighter, with less checks, I skip that optimisation for the sake of readability.

In part 1 I've reported the results of a micro-benchmark designed to compare the performance of plain php includes vs includes via streams from a sqlite database. In this post I extend the test cases with two more no-includes same work, to serve as a base case and includes from a mysql database, the code is the same as in sqlite case, the connector differs. You can find the code attached at the end previous post.

Overall, having in mind the random factors like netbook load (CPU and IO), the differences between the different test cases are insignificant on the test machine - Acer Aspire One netbook.

Please let me know if you decide to run these benchmarks. I will be especially interested to see what are the differences.

These results are encouraging enough to merit developing a more substantial test. I'm interested in benchmarking drupal. What scenarios would you suggest?

• part 1
• the benchmark
• results
• conclusions

He Sells Shell Scripts to Intersect Sets is a good read. Set and multiset operations from the command line or in .sh. Rather clean, straightforward shell magic.

control resumed inspired me to take a small exercise.

"Code a minimal approximation of the python yield operator based generators"
Here follow the results I managed to get with help from Matthias Felleisen, via the plt mailing list. You can see the non-edited exchange via the mailing list archives and control and macors. All control&prompt are forms specific to plt scheme's control.ss module. The first attempt looks something like this:

(require (lib "control.ss"))

(define (make-step)
  (define (control-state)
    (yield 1)
    (yield 2)
    (yield 3)
    'finished)
  (define (yield value) (control resume-here (set! control-state resume-here) value))
  (define (generator) (prompt (control-state)))
  generator)

(define step (make-step))

(step) (step) 

It does the job. Kind of. For me the interesting bit is how the interplay of prompt and control achieve maintaining the current state of execution before the return and allowing to continue from that interruption. It can be done with call/cc but it looks a helluva a lot more complicated and is far more unreadable.

There is a problem with the code above though. As Matthias notes in his email:

LESSON: never 'test' by running things at the top-level prompt. It IS a prompt. -- Matthias

So comes version 2:

(require (lib "control.ss"))

(define (make-step)
  (define (control-state)
    (yield 1)
    (yield 2)
    (yield 3)
    'finished)
  (define (yield value) 
    (control resume-here 
             (set! control-state 
                   (lambda () (prompt (resume-here)))) 
             value))
  (define (generator) (prompt (control-state)))
  generator)

(define step (make-step))

(equal? '(1 2 3) (list (step) (step) (step)))

control-state is a variable holding a reference to a function with no arguments, doing what the python function would do. yield is a variable holding a reference to a function which does the interrupt magic. generator is a variable holding a reference to a (sugary) function which does the initial step.

The logic of the above algorithm is roughly as follows - mark thy state, do what you need to do, when you encounter control stop, remember your state by wrapping it in a function (resume-here), remember where do you what to continue from ( the set! control-state ...). Notice that the value of control-state is replaced. This is possible since the resume-here continuation is a function and a first class value.

So what next. Boilerplate code is tedious to write. And there is a lot of boilerplate code there. And every function, which needs to follow this recipe, will need to duplicate it.

So scheme macros to the rescue. It is not a trivial problem. A 'generator' function can look something like this: