Tuesday, May 28, 2013

Pushing and pulling

I'm mystified. The following definition of a program is efficient to execute:

sealed trait Program[A]
case class Result[A](x: A) extends Program[A]
case class NeedsInput[A](f: String => Program[A]) extends Program[A]

and in fact has a not bad definition of order():

def order[A1,A2](p1: Program[A1], p2: Program[A2]):
        Program[Either[(A1,Program[A2]),(A2,Program[A1])]] =
    p1 match {
      case Result(x) => Result(Left(x, p2))
      case NeedsInput(f) => p2 match {
        case Result(x) => Result(Right(x, p1))
        case NeedsInput(g) =>
          NeedsInput { s =>
            order(f(s), g(s))

but if you define map, flatMap, etc these turn out to be ineffecient (left as an exercise to the reader).

Programs represented in "pull style" (the preceding are essentially "push style") are not so efficient to execute (in the obvious way):

sealed trait Event[A]
case class Instantly[A](x: A) extends Event[A]
case object Input extends Event[String]
case class Computation[A,B](ev: Event[A], f: A => B) extends Event[B]
case class Chaining[A](ev: Event[Event[A]]) extends Event[A]
case class Ordering[A1,A2](ev1: Event[A1], ev2: Event[A2]) extends Event[Either[(A1,Event[A2]),(A2,Event[A1])]]

Wouldn't I love to be able to define

def compile[A](ev: Event[A], cc: ): Program[A] = ???

but I haven't thought how to do that.

What gives? Why is it so hard to achieve both the memory managing benefits of pull programs and the lack of wasted computation of push programs?

This is still puzzling me.

No comments:

Post a Comment