Laziness and chained implicit coercions

[Adriaan Moors]

Hi,

I've been experimenting with implementing Packrat parsers [3] in Scala and, in
trying to get the Scala version to mimick the original Haskell implementation as
closely as possible, I tried to implement a class Lazy[T] that encapsulates
memoisation and call-by-name evaluation. (By the way I was thrilled to
see Scala supports everything -- except true laziness ;-) -- to make porting
this kind of code from Haskell to Scala almost trivial.)

My goal was to write a class and some implicit coercions, so that, for an
argument to be passed lazily, a method simply has to define that argument as
having type Lazy[T] instead of type T. The implicit coercion makeLazy was
supposed to take care of this. On the other hand, when we want the actual value,
the forceLazy coercion returns the actual value when something of type T was
expected. In the case of method invocation on a lazy value, this amounts to
delegating methods not found in Lazy[T] to the value of type T (Lazy[T]
overrides some standard methods from Any so that they are also delegated
to the forced value).

This is the code for the class and a small main method that demonstrates its use
and the problems I encountered. (I also found an older post on this mailing list
with a similar implementation [1]) Ideally, this code should work as-is, but
currently, you have to uncomment the xxxxLazy calls.

object laziness {
    implicit def forceLazy[T](stub :Lazy[T]) :T = stub.__force
    // the makeLazy-coercion requires the special coercion of T to => T,
    //  but coercions are never combined --> maybe make an exception for the
    //  call-by-name coercion?
    implicit def makeLazy[T](stub : => T) :Lazy[T] = new Lazy[T](stub)
   
    class Lazy[T]( stub: => T) {
        private var memo :T = _
        private var memoed :Boolean = false
       
        def __force :T = {if(!memoed) { memo = stub; memoed = true}; memo}

        // override methods in Any and (manually) delegate to forced stub
        override def equals(other :Any) :Boolean = __force.equals(other)
        override def hashCode() :Int = __force.hashCode
        override def toString() :String = __force.toString
   
        // it's a pitty you can't override this anymore:
        //override def match[a, b](cases: a => b): b = __force.match(cases)
   
        // can't override reference equality
    }    

    implicit def int2string(i :Int) :String = i.toString
   
    def main(args :Array[String]) :Unit = {
        def loop(a :Int) :Int = loop(a)
        def nonstrict(a :Lazy[Int]) :Int = 42
        def strict(a :Lazy[Int]) :String = /*forceLazy(*/a/*)*/
        def strict2(a :Lazy[Int]) :String = /*forceLazy(*/a/*)*/ match {
                                             case 0 => "zero!"
                                             case _ => /*int2string(*/a/*)*/ }
                                                                       
        System.out.println(nonstrict(/*makeLazy(*/loop(13)/*)*/))
        System.out.println(strict(/*makeLazy(*/loop(13)/*)*/))
        System.out.println("Ceci is not printed...")
    }
}


In fact, Scala's only limitation (I think) here is that coercions are not
chained. I'm sure there is a good reason for this, but I was wondering if this
rule could be relaxed so that (at least) the built-in T to => T coercion can be
chained to another coercion (such as the makeLazy coercion). Another (slightly
less important) example of chained coercions can be seen in the strict method,
where the forceLazy and the int2string coercion should be chained. Finally (in
the strict2 method), it would be nice if pattern matching could be used to force
a lazy value, just like in Haskell.

More generally, I'm interested in what the rationale is behind disallowing
chaining of coercions (is it just that the resulting search space is too big?).
I haven't studied this problem much (although [2] is ranked high on my TODO-
list), but I'm very interested to hear what your opinion is on this.

greetings,
adriaan

[1] Matthias Zenger. Re: lazy evaluation. The Scala Mailing list, 2004.
(http://article.gmane.org/gmane.comp.lang.scala/241)
[2] John C. Reynolds. Using Category Theory to Design Implicit Conversions and
Generic Operators. In Semantics Directed Compiler Generation. LNCS 94, 1980.
(http://www.daimi.au.dk/~nygaard/CTfCS/papers/reynolds1.pdf)
[3] Bryan Ford. Packrat Parsing: a Practical Linear-Time Algorithm with
Backtracking. Master's Thesis, MIT, 2002.
(http://pdos.csail.mit.edu/~baford/packrat/thesis/)

[Martin Odersky]

Hi Adriaan:

There are several arguments against chaining of conversions:

1. Algorithmic: Since the space of types reachable by conversions is
infinite, how do you find a conversion path between two types without
the possibility of looping?

2. Ambiguities: How do you detect multiple possible paths and if you do,
which path do you choose?

3. Avoiding surprising coercions by some path a user had not thought about.

However, conversions can be nested. For instance, an implicit conversion
function might take another conversion function as implicit parameter.
This can achieve the same effect, but requires a bit more planning by
the library designer. In your example, I can force chaining of the
forceLazy and int2string conversions by defining the latter as follows:

   implicit def int2string[T](x: T)(implicit toInt: T => int): String =

     toInt(i).toString

or, equivalently, by using a view bound:

   implicit def int2string[T <% int](x: T): String = (i: int).toString

Btw: Please consider to make the library available as an sbaz package
when it is done.

Cheers

  -- Martin

[Judson, Ross]

I implemented the four basic future types outlined in AliceML's
documentation -- concurrent, lazy, promised, and failed...sort of a neat
exercise in Scala.  For laziness I used the trick Matthias Zenger
outlined -- the nested-class-calls-def bit.  Seems to work fine.  The
implicit keyword worked fine for creating conversion functions that
would move in and out of future values.  

If we could combine pattern matching and laziness it'd be a lot easier
to adapt Haskell code.  ;)  Plus there's the "where" clause in pattern
matching that always requires code rearrangement.

It's quite short so I'll try and post it to the list tonight for
comment.  

RJ

[Judson, Ross]

This is the future/lazy value code I've been playing with (Scala 2
syntax).

RJ



package scalax.future;

/** A Future is a function of arity 0 that returns a value of type T.
It can be queried to find out if the value is available, if a failure
has occurred, and what the failure is, if failure happened.  If the
value of the future is retrieved and a failure results, the failure
exception is thrown. */
mixin class Future[T] extends Function0[T] {
  def isSet: boolean;
  def isFailure: boolean;
  def failure: Throwable;
}

/** A Promise is a placeholding Future, where the result
of the computation can be set externally.  */
mixin class Promise[T] extends Future[T] {
  def set(t: T): unit;
  def fail(ex: Throwable): unit;
  def future: Future[T];
}

object Future {

  /** Implicitly convert arbitrary values of T into a Future[T]. */  
  implicit def lazyConst[T](t: T): Future[T] = LazyConst(t);
 
  /** Retrieve the value, which may result in forcing the value if it is
not already available. */
  implicit def fromFuture[T](lz: Future[T]): T = lz();
 
  /** We want to be able to treat our lazy values like regular values
when we're iterating over them, and so forth.  We define a kind of
"reverse lifter" here that wraps a function on T into a function on
Future[T]. */
  implicit def lazyLift[T,B](tfunc: (T) => B): (Future[T]) => B = (lt)
=> tfunc(lt());
 
  /** Directly construct a lazy value of type T. Note that using the
anonymous class this way seems to be the simplest way to prevent
execution of "f" until we really mean to, and still keep it around
cleanly. */
  def lazy[T](f: => T): Future[T] = new Lazy[T] {
    def func: T = f;
  }
 
  /** Create a future that is failed from the start. */
  def fail[T](ex: Throwable): Future[T] = Failed(ex);

  /** Build a concurrent future, starting a thread to perform the
computation. */  
  def spawn[T](f: => T): Future[T] = new ExceptionSyncVar[T] {
    val thread = new Thread() {
      override def run() = {
        try {
          set(f)
        } catch {
          case ex: Throwable => fail(ex)
        }
        Console.println("Spawn done");
      }
    }
    thread.start
  }

  /** Build a promise for a future value; the promise can be fulfilled
      on this or any other thread.  A thread getting the value will
block
      if the promise has not been fulfilled. */
  def promise[T]: Promise[T] = new ExceptionSyncVar[T] with Promise[T] {
    def future = this;
    override def toString = createString("Promise");
  }
 
}

mixin class Executor {
 
  def run(f: => unit): unit;
  def run[A](f: A => unit)(a: A): unit = run( f(a) );
  def run[A,B](f: (A, B) => unit)(a: A, b: B): unit = run( f(a,b) );
  def run[A,B,C](f: (A, B, C) => unit)(a: A, b: B, c: C): unit = run(
f(a,b,c) );
 
  def submit[T](f: => T): Future[T];
  def submit[A,T](f: A => T)(a: A): Future[T] = submit( f(a) );
 
  def invokeAll[T](tasks: Function0[T]*): Seq[Future[T]];
  def invokeAny[T](tasks: Function0[T]*): T;
 
  def isShutdown: boolean;
  def isTerminated: boolean;
  def shutdown: unit;
  def shutdownNow: unit;
 
}

object Executors {
     
}

private class ExceptionSyncVar[T] extends Future[T] {
  private var ex: Throwable = _;
  private var isDefined: Boolean = false;
  private var value: T = _;

  def failure = ex;
  override def apply() = get;
  def isFailure = isDefined && (ex != null);

  def set(x: T) = synchronized {
    value = x
    isDefined = true
    notifyAll()
  }
  def fail(e: Throwable): unit = synchronized {
    ex = e
    isDefined = true
    notifyAll()
  }

  def isSet: Boolean = synchronized {
    isDefined
  }

  def get = synchronized {
    if (!isDefined) wait();
    if (ex != null) throw ex;
    value
  }
 
  override def toString = createString("ESync");
   
  def createString(head: String) =
    if (!isDefined) head + "(?)"
    else if (ex != null) head + '(' + ex + ')'
    else head + '(' + value + ')';
}
 
private abstract class Lazy[T] extends ExceptionSyncVar[T] {
  def func: T;
  override def get: T = synchronized {
    if (!isSet)
      try {
        val ret = func;
        set(ret);
        ret
      } catch {
        case e: Throwable => fail(e)
        throw e;
      }
    else
      super.get
  }
  override def toString() = createString("Lazy");
}

private case class Failed[T](ex: Throwable) extends Future[T] {
  def apply(): T = throw ex;
  def failure = ex;
  def isFailure = true;
  def isSet = true;
}

private case class LazyConst[T](v: T) extends Future[T] {
  def apply() = v;
  override def failure = null;
  def isFailure = false;
  def isSet = true;
}

[Lex Spoon]

"Judson, Ross" <[hidden email]> writes:
> This is the future/lazy value code I've been playing with (Scala 2
> syntax).

Elegant, work!

-Lex

[Judson, Ross]

 Thanks :)  I like the unified notion of future values.  Now I just need
to find something to use it in.

On sbaz -- I was wondering if the default port could be moved from 8006
to the http default port...at home I can use sbaz fully but at the
office I cannot due to firewalls.  

-----Original Message-----
From: news [mailto:[hidden email]] On Behalf Of Lex Spoon
Sent: Tuesday, January 24, 2006 4:00 AM
To: [hidden email]
Subject: Re: Laziness and chained implicit coercions

"Judson, Ross" <[hidden email]> writes:
> This is the future/lazy value code I've been playing with (Scala 2
> syntax).

Elegant, work!

-Lex

[Lex Spoon]

"Judson, Ross" <[hidden email]> writes:
> On sbaz -- I was wondering if the default port could be moved from 8006
> to the http default port...at home I can use sbaz fully but at the
> office I cannot due to firewalls.  


Well let's figure this out for sure.  Sbaz uses HTTP precisely so that
it can be used from behind typical office firewalls.

I had hoped that typical Java VM's would use the OS's HTTP proxy
settings by default.  Could you try hacking your "sbaz" script (or
sbaz.bat for Windows) and adding to the java command line:

  -DproxySet=true -Dhttp.proxyHost=YOURHOST -Dhttp.proxyPort=YOURPORT


where YOURHOST and YOURPORT are for your office's proxy?


If that works, then perhaps there is a global file of system
properties that typical JVM's load by default?  Does anyone know?

If not, then I guess sbaz needs a little configuration file holding
the proxy information to use.  That, and/or it can sniff around with
getenv().



-Lex

[Clive Jevons-2]

... I think the problem is that Windows doesn't have a system wide  
proxy setting in the same sense that OS X has, for example. And in my  
experience, most larger companies deploy their IT infrastructure so  
that only Apps they want to reach the WWW have the necessary proxy  
settings ...erm ... set ;)
In furtherance of the first sentence - I'm not even sure whether Java  
on OS X uses the system wide proxy settings when you use the VM's  
HTTP connections ... haven't tried that yet, though, so maybe it does :)

Cheers,
C

On 26 Jan 2006, at 17:46, Lex Spoon wrote:

> "Judson, Ross" <[hidden email]> writes:
>> On sbaz -- I was wondering if the default port could be moved from  
>> 8006
>> to the http default port...at home I can use sbaz fully but at the
>> office I cannot due to firewalls.
>
>
> Well let's figure this out for sure.  Sbaz uses HTTP precisely so that
> it can be used from behind typical office firewalls.
>
> I had hoped that typical Java VM's would use the OS's HTTP proxy
> settings by default.  Could you try hacking your "sbaz" script (or
> sbaz.bat for Windows) and adding to the java command line:
>
>   -DproxySet=true -Dhttp.proxyHost=YOURHOST -Dhttp.proxyPort=YOURPORT
>
>
> where YOURHOST and YOURPORT are for your office's proxy?
>
>
> If that works, then perhaps there is a global file of system
> properties that typical JVM's load by default?  Does anyone know?
>
> If not, then I guess sbaz needs a little configuration file holding
> the proxy information to use.  That, and/or it can sniff around with
> getenv().
>
>
>
> -Lex
>
>

[Lex Spoon]

Okay, version 1.10 of sbaz has a hook to help people who need proxy
settings.  If you have a file config/sbaz.properties in your Scala
home directory, then sbaz will read that file into the Java system
settings.

So, if you are using a Sun JDK, and you want to set up sbaz to use an
HTTP proxy, you should create the file config/sbaz.properties and
put the following three lines in it:

http.proxySet=true
http.proxyHost=localhost
http.proxyPort=3128


Ross, or anyone, if you give this a try, I'd love to hear how it goes.


-Lex

[Adriaan Moors-2]

Hi,

Thank you for the clarifications! However, it's not yet clear to me how nested conversions solve the problem of the makeLazy coercion, which has to be preceded by the T to => T coercion. (If I understand correctly, with nested conversions, you apply the conversion after the argument has already been passed, but then it is too late in this case.)

So, to avoid having to write makeLazy explicitly, I see two possible solutions:

 1) define restrictions on implicit conversion (and overloaded functions?) so that, no matter which chain of conversions is chosen, the results are the same (similar to the seminal paper by Reynolds [1] -- by the way: does anyone have references for recent results in this area?)

 2) have a special case that allows chaining the T to => T coercion (and possibly other built-in coercions) with a user-defined coercion (since this seems to be the only kind of chaining you can't simulate by nesting coercions)

Although I think it should be possible to restrict implicit conversions so that they may be chained in certain cases, this is probably overkill. given that you can achieve the same by combining option 2) and -- as you demonstrated -- nested implicit conversions.  (Note that languages like C# also adopt option 2, in that a chain of implicit conversions may consist of at most 1 user-defined conversion and several standard conversions [2]. )

Btw: Please consider to make the library available as an sbaz package when it is done.

I'll do my best to package it up nicely :-)  (Or to integrate it with existing frameworks, such as Ross Judson's, if that's more appropriate.)

regards,

adriaan

ps: Since it's been a while since you replied to my original question (sorry about that), here is a link to my original post (on gmane) (http://article.gmane.org/gmane.comp.lang.scala/1743) and your reply (http://article.gmane.org/gmane.comp.lang.scala/1744).

[1] John C. Reynolds. Using Category Theory to Design Implicit Conversions and Generic Operators. In Semantics Directed Compiler Generation. LNCS 94, 1980.  (http://www.daimi.au.dk/~nygaard/CTfCS/papers/reynolds1.pdf)

[2]  Evaluation of user-defined conversions. (C# Language Specification, http://msdn.microsoft.com/library/default.asp?url=/library/en-us/csspec/html/vclrfcsharpspec_6_4_2.asp)

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm for more information.