implementing 'delay' and 'force' in Scala

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|

implementing 'delay' and 'force' in Scala

John Williams
I recently tried implementing Scheme's "delay" and "force" functions
in Scala, and in doing so I found a surprising number of interesting
issues.

Here is my code:



/**
 * Pseudo-package for lazy evaluation.
 */
object lazy {
  /** Delay the evaluation of an expression until it is needed. */
  def delay[A](value: => A) = new Susp[A](value)

  /** Get the value of a delayed expression. */
  implicit def force[A](s: Susp[A]): A = s()

  /**
   * Data type of suspended computations. (The name froms from ML.)
   */
  class Susp[+A](lazyValue: => A) extends Function0[A] {
    private var func: () => Any = () => lazyValue: A // workaround
    private var value: Any = null

    override def apply() = {
      if (func != null) {
        value = func()

        // This line has two purposes: it signals that the computation
        // has been evaluated, and it allows func to be
        // garbage-collected.
        func = null
      }
      value.asInstanceOf[A]
    }

    override def toString() =
      if (func == null) "Susp(" + value + ")"
      else "Susp(?)"
  }
}

/**
 * Test program.
 */
object lazy_test {
  import lazy._

  def main(args: Array[String]) = {
    val s: Susp[Int] = delay { Console.println("evaluating..."); 3 }
    Console.println("s = " + s)     // show that s is unevaluated
    Console.println("s() = " + s()) // evaluate s
    Console.println("s = " + s)     // show that the value is saved
    Console.println("2 + s = " + (2 + s)) // implicit call to force()
  }
}


And here is the output of the test program:

s = Susp(?)
evaluating...
s() = 3
s = Susp(3)
2 + s = 5



This implementation has the following features:
1. The type parameter of Susp is covariant, so delayed computations
interact with inheritance the same way as regular values.
2. Delayed computations have their own data type, but they can also be
treated as 0-ary functions.
3. The force() function can be applied implicitly to delayed
computations but not to arbitrary 0-ary functions.
4. Susp.toString() produces useful values for debugging.
5. The closure used to implement Susp could be garbage-collected once
it has been evaluated. (Unfortunately this is not the case in
practice.)

A much simpler implementation is possible by sacrificing features 2-5:

object lazy2 {
  def delay[A](lazyValue: => A): () => A = {
    var evaluated = false
    var value: A = null
    def f(): A = {
      if (!evaluated) {
        value = lazyValue
        evaluated = true
      }
      return value
    }
    return f
  }

  implicit def force[A](f: () => A) = f()
}



Some things tripped me up while writing this code.  First, because I
wanted Susp's type parameter A to be covariant, I could not use A in
the types of the member variables because the compiler only allows
constant fields to have covariant types. Although the final solution
of changing A to Any and adding a type cast turned out to be very
simple, I did not find this solution obvious at first, and I think
changing the types of the member variables obscures the intent of the
code. Perhaps Scala should allow variant types for private member
variables. (This would of course create a small hole in the soundness
of the type system, but I have a hard time believing this would be a
major problem in practice.)

Changing the types of the member variables also uncovered a bug in the
Scala compiler. I've already reported this bug so I won't describe it
except to say that the  workaround was to add an extra type annotation
in the initializer of Susp.func.

A smaller issue I found is that it seems unnecessarily hard to define
implicit functions. Since it is impossible to define functions at the
package level, I've been using this workaround:

/*1*/ object myFunction { /*2*/ def apply(...) = ... }

Unfortunately this style doesn't work for implicit functions. I've
tried adding the word "implicit" at /*1*/ and /*2*/ but neither has
any effect, so I borrowed an idiom from the nsc codebase and
implemented my "module" as an object. It would be nice if modules
supported the full set of declarations like objects do, but I suppose
this would probably create problems with separate compilation and Java
integration.

Once I got the code working, I started using javap to examine the Java
bytecode, and I was surprised to see that a number of seemingly simple
optimizations were not done. I realize that these optimizations are
probably either not as simple or not as useful as I imagine, but I
think they're worth considering.

The biggest surprise for me is that private member variables have
their own accessor methods. I can't think of any circumstance in which
this has any advantage over accessing the member variables directly.
Was this not done because the JVM is able to optimize away calls to
these methods during the JIT compilation process?

The compiler seems to generate fields for all constructor parameters
even when they are never used outside the primary constructor. I think
it's important to remove these fields whenever possible because I'm
fairly sure they prevent constructor arguments from being garbage
collected. Memory leaks are among the hardest problems to debug in a
garbage-collected environment, and holding references that most Java
programmers would expect to be temporary seems like a sure way to
create chaos.

Finally, it would be really neat if the compiler could optimize away
the closure in { () => x } when x is a call-by-name parameter.



Well, I think that's plenty of armchair-quarterbacking for one day.
Thanks to the Scala team for making such a nifty language to play
around with!

Cheers,
jw
Reply | Threaded
Open this post in threaded view
|

RE: implementing 'delay' and 'force' in Scala

Judson, Ross
I wrote some Alice ML-style delay/force primitives; you can see them on
the Scala Wiki at http://scala.sygneca.com/code/futures.  Generalizing
the notion of delay/force into a future seems like a pretty good idea
overall; like you, I made my futures a Function0[T].  

Recent discusion on the Responder class had me look at it quickly; I
converted it over to extend a Function instead of using "answer", and
changed answer to apply.  

I'm not sure of the state of Scala 2 vs. Scala 1 vis-a-vis
optimizations, but you should try declaring the private variables as
final; that may assure the compiler it is allowable to use a direct
access.  I am not sure how much the inliner is doing at the moment.

RJ
Reply | Threaded
Open this post in threaded view
|

Re: implementing 'delay' and 'force' in Scala

Lex Spoon
In reply to this post by John Williams
Cool stuff, John.  One little thing:

>     private var value: Any = null
[...]
>       value.asInstanceOf[A]


Scala includes an Option class hierarchy to deal with this situation.
If you declare value as type Option[A] instead of Any, then your code
will simplify.  Option[A] means that there *might* be an A there, or
there might be nothing.

In more detail, Option is a class with two subclasses: None, and Some.
"None" means there is nothing there.  "Some" means that there is.

As one more trick, Option integrates nicely with pattern matching,
letting you write things like:

  value match {
    case Some(it) => it
    case None =>  // force evaluation here
  }


-Lex


Reply | Threaded
Open this post in threaded view
|

Re: implementing 'delay' and 'force' in Scala

Lex Spoon
In reply to this post by Judson, Ross
"Judson, Ross" <[hidden email]> writes:
> I wrote some Alice ML-style delay/force primitives; you can see them on
> the Scala Wiki at http://scala.sygneca.com/code/futures.  Generalizing
> the notion of delay/force into a future seems like a pretty good idea
> overall; like you, I made my futures a Function0[T].  

Agreed -- this is well worth looking at.  Incidentally, if you post it
in the bazaar, it will be even easier for people to play with.  ;)



> I'm not sure of the state of Scala 2 vs. Scala 1 vis-a-vis
> optimizations, but you should try declaring the private variables as
> final; that may assure the compiler it is allowable to use a direct
> access.  I am not sure how much the inliner is doing at the moment.


This is a good optimization idea, but I would recommend not worrying
about it until there is a definite problem.  Scala is a high-level
language, so it is best to first optimize for expressiveness.

    http://xp.c2.com/LazyOptimization.html

I have been a heavy Scala user for 6 months, and I have yet to spend
serious time optimizing anything.  I am happy to say, I have managed
to spend most of my time exploring interesting things to express.


That said, LAMP focusses on partial compilation but also has some work
on whole-program analysis.  For whole-program analysis, be sure to
read into Iulian Dragos' ongoing work!  It is not the default, though,
because it fundamentally assumes that the Scala compiler sees an
entire program.  Among other things, that would mean that scalac has
to be the last stage of building a program.  That's a huge assumption,
and in many cases it is an outright show stopper.  To contrast,
running at merely Java speeds does not seem so bad.


-Lex

Reply | Threaded
Open this post in threaded view
|

Re: implementing 'delay' and 'force' in Scala

John Williams
In reply to this post by Lex Spoon
On 23 Apr 2006 12:41:02 +0200, Lex Spoon <[hidden email]> wrote:
> >     private var value: Any = null
> [...]
> >       value.asInstanceOf[A]
>
> Scala includes an Option class hierarchy to deal with this situation.
> If you declare value as type Option[A] instead of Any, then your code
> will simplify.  Option[A] means that there *might* be an A there, or
> there might be nothing.

Unfortunately the Option class doesn't solve the problem of variance:

test.scala:2 error: covariant type A occurs in invariant position in
type scala.Option[A] of variable member
  private var member: Option[A] = None

I have very mixed feelings about the Option class. It imitiates the
style of ML or Haskell types but without the substance, since
reference types already have null as a possible value, and throwing
Option into the mix just confuses things more by expanding the usual
null/non-null dichotomy into four cases: null, None, Some(null) and
Some(non-null). I'd be hard-pressed to explain to an average Java
programmer how that's an improvement.

I'd like the Option type a lot more if it where a value type (so null
is not a value of Option) and if Some(null) would throw an exception,
since this would help to locate unexpected null values closer to where
they are produced.

<half-baked idea>
I'd *really* like it if null were not part of the language and
None/Some were implemented as null/non-null at the JVM level. I
realize such a draconian solution is not possible because it would
mean that any Java reference type A would have to appear as Option[A]
in Scala, and that would be impossibly painful use. OTOH, what if Java
reference types appeared in Scala as JavaRef[A], with values Null and
NotNull(x), and the following implicit conversions:

  implcit def unwrapJavaRef(x: JavaRef[A]): A = x match {
    case NotNull(x) => x
    case Null => throw new NullPointerException()
  }
  implicit def javaRefToOption(x: JavaRef[A]): Option[A] = x match {
    case NotNull(x) => Some(x)
    case Null => None
  }
</half-baked idea>

--jw
Reply | Threaded
Open this post in threaded view
|

RE: implementing 'delay' and 'force' in Scala

Judson, Ross
In reply to this post by John Williams
Inside the Scala compiler is an implementation for a "NonNull" trait,
which disallows "null" from being set to any reference to that type.
It's commented out in the code right now -- not sure why but I'm sure
there's a good reason.  If I recall correctly you do something like
this:

trait Opt extends NonNull;
case object Nothing extends Opt
case class Something(k) extends Opt

class q {
  var a: Opt = Nothing //// legal
  var b: Opt = null //// illegal when NonNull
}

Perhaps this feature will make its way back into the Scala system at
some point.

RJ
Reply | Threaded
Open this post in threaded view
|

Re: implementing 'delay' and 'force' in Scala

Jamie Webb-3
In reply to this post by John Williams
On Wed, Apr 26, 2006 at 02:43:29PM -0500, John Williams wrote:
> Unfortunately the Option class doesn't solve the problem of variance:
>
> test.scala:2 error: covariant type A occurs in invariant position in
> type scala.Option[A] of variable member
>   private var member: Option[A] = None

Yeah, type systems are by definition imperfect. It looks like one
could soundly typecheck your code by adding a notion of a covariant
type used invariantly (we know that lazyValue has type '=> A' exactly
since it's a constructor parameter, so we could assign it to value if
value were declared as some 'exactly A' type). A lot of complication
for a pretty unusual case though.

> I have very mixed feelings about the Option class. It imitiates the
> style of ML or Haskell types but without the substance, since
> reference types already have null as a possible value, and throwing
> Option into the mix just confuses things more by expanding the usual
> null/non-null dichotomy into four cases: null, None, Some(null) and
> Some(non-null). I'd be hard-pressed to explain to an average Java
> programmer how that's an improvement.

Because the typechecker will force you to consider the None case. No
more NPEs. That's got to be a good argument.

I think I might hurt someone if I encountered Some(null) in real
code... :-)

> I'd like the Option type a lot more if it where a value type (so null
> is not a value of Option) and if Some(null) would throw an exception,
> since this would help to locate unexpected null values closer to where
> they are produced.

As far as I am concerned, null is an unfortunate side-effect of the
JVM, and the use of nulls is bad style in Scala. I admit to using them
occasionally as an optimisation within self-contained code, but never in
an API. (In the code you gave, I would probably have used null too.)

> <half-baked idea>
> I'd *really* like it if null were not part of the language and
> None/Some were implemented as null/non-null at the JVM level. I
> realize such a draconian solution is not possible because it would
> mean that any Java reference type A would have to appear as Option[A]
> in Scala, and that would be impossibly painful use. OTOH, what if Java
> reference types appeared in Scala as JavaRef[A], with values Null and
> NotNull(x), and the following implicit conversions:

Looks fragile, mainly because it doesn't round-trip. E.g. what happens
if you store an Option in a Java collection? You'd have to treat it
specially if you wanted to get an Option back out, and that wouldn't
work with erasure.

The 'Nice' language uses the trick of treating null/non-null as a kind
of option type though. Trouble is, it requires you to declare as such
each Java method that can't return null.

-- Jamie Webb
Reply | Threaded
Open this post in threaded view
|

Re: implementing 'delay' and 'force' in Scala

Lex Spoon
In reply to this post by John Williams
"John Williams" <[hidden email]> writes:

> On 23 Apr 2006 12:41:02 +0200, Lex Spoon <[hidden email]> wrote:
> > >     private var value: Any = null
> > [...]
> > >       value.asInstanceOf[A]
> >
> > Scala includes an Option class hierarchy to deal with this situation.
> > If you declare value as type Option[A] instead of Any, then your code
> > will simplify.  Option[A] means that there *might* be an A there, or
> > there might be nothing.
>
> Unfortunately the Option class doesn't solve the problem of variance:
>
> test.scala:2 error: covariant type A occurs in invariant position in
> type scala.Option[A] of variable member
>   private var member: Option[A] = None
>

Ah, yes....

Hmm, Jamie points towards a solution.  You can declare the abstract
type of Susp using a covariant type parameter, while using invariance
in the implementation:

  abstract class Susp[+A] extends Function0[A]

  class SuspImpl[A](lazyValue: => A) extends Susp[A] { ... }

  def delay[A](value: => A): Susp[A] = new SuspImpl[A](value)

Code appended.

This is a general trick to get more out of the Scala type system.  If
you cannot express what you want with just one class, it can pay to
introduce extra subclasses or superclasses.

Granted, the downside is that your code becomes more complicated.
IMHO it is better style to avoid this level of care with the types
unless (a) you are just having fun :) or (b) the code is a heavily
used library where you really want to get it right.  The invariantly
typed version is quite useful, and the cast in the original version is
not really a big deal, either!



> I have very mixed feelings about the Option class. It imitiates the
> style of ML or Haskell types but without the substance, since
> reference types already have null as a possible value, and throwing
> Option into the mix just confuses things more by expanding the usual
> null/non-null dichotomy into four cases: null, None, Some(null) and
> Some(non-null). I'd be hard-pressed to explain to an average Java
> programmer how that's an improvement.

I agree in general that if null is in the language you may as well use
it!

Actually, though, in this case you run into trouble, because it is
perfectly legal to write "delay {null}" !  This turns up in many
places actually.  Another example is the find() method from the
collection library.  Sometimes it needs to report that it found a
null, and sometimes it needs to report that it did not find anything,
so it cannot use null for both of these.


Incidentally, I have mixed feelings about whether it is really a good
idea to eliminate null as a possibility as in ML.  The question comes
with the kind of code that is written under it.  There's an empirical
question here, but *IF* you end up writing lots of option types and
strewing .get's (valOf's) all over the place, then the overall
situation seems worse.  The code has gotten longer, but we haven't
substantially improved the relibiality.  Just like casts in Java 1.4,
the .get's become so common that programmers stop bothering trying to
get rid of them.

Short code is good.  Each extra character should buy something new.

-Lex


/**
 * Pseudo-package for lazy evaluation.
 */
object lazy {
  /** Delay the evaluation of an expression until it is needed. */
  def delay[A](value: => A): Susp[A] = new SuspImpl[A](value)

  /** Get the value of a delayed expression. */
  implicit def force[A](s: Susp[A]): A = s()

  /**
   * Data type of suspended computations. (The name froms from ML.)
   */
  abstract class Susp[+A] extends Function0[A]

  /** Implementation of suspended computations, separated
    * from the abstract class so that the type parameter can
    * be invariant.
    */
  class SuspImpl[A](lazyValue: => A) extends Susp[A] {
    private var maybeValue: Option[A] = None

    override def apply() = {
      maybeValue match {
        case None => {
          val value = lazyValue
          maybeValue = Some(value)
          value
        }
        case Some(value) => value
      }
    }

    override def toString() =
      maybeValue match {
        case None => "Susp(?)"
        case Some(value) => "Susp(" + value + ")"
      }
  }
}

/**
 * Test program.
 */
object lazy_test {
  import lazy._

  def main(args: Array[String]) = {
    val s: Susp[Int] = delay { Console.println("evaluating..."); 3 }
    Console.println("s = " + s)     // show that s is unevaluated
    Console.println("s() = " + s()) // evaluate s
    Console.println("s = " + s)     // show that the value is saved
    Console.println("2 + s = " + (2 + s)) // implicit call to force()

    val sl = delay { Some(3) }
    val sl1: Susp[Some[int]] = sl
    val sl2: Susp[Option[int]] = sl1   // the type is covariant

    Console.println("sl2 = " + sl2)
    Console.println("sl2() = " + sl2())
    Console.println("sl2 = " + sl2)
  }
}


Reply | Threaded
Open this post in threaded view
|

Re: implementing 'delay' and 'force' in Scala

Martin Odersky
In reply to this post by Jamie Webb-3
Jamie Webb wrote:
>
> As far as I am concerned, null is an unfortunate side-effect of the
> JVM, and the use of nulls is bad style in Scala. I admit to using them
> occasionally as an optimisation within self-contained code, but never in
> an API. (In the code you gave, I would probably have used null too.)
>
I have adopted the following policy (which I learned from Corky
Cartwright) in most of my code:

    It's OK to use `null' but you should never test for equality with it.
    I.e your code should not contain the expressions

        x == null    or    x != null

The idea is, that `null' represents an undefined value. As long as you
don't care whether a value is defined or not, it's OK to use `null' for
the undefined case. Likewise if you can ascertain that a value is
defined or undefined by other means. For instance, the following is OK:

var isDefined: boolean = false
var value: T = null

def getT = {
   if (!isDefined) { value = computeT(); isDefined = true }
   value
}

I admit that I also use occasionally tests for `null' as an
optimization, but only if I think the code is performance-critical.

Cheers

  -- Martin


Reply | Threaded
Open this post in threaded view
|

Re: implementing 'delay' and 'force' in Scala

Stéphane Micheloud
In reply to this post by Lex Spoon
Thanks to Lex whose nice example (renamed to
lazyEvaluation.scala) is now available from:

   http://scala.epfl.ch/examples/more.html


Bye
--Stephane

Lex Spoon wrote:

> "John Williams" <[hidden email]> writes:
>
>>[..]
>
> Hmm, Jamie points towards a solution.  You can declare the abstract
> type of Susp using a covariant type parameter, while using invariance
> in the implementation:
>
>   abstract class Susp[+A] extends Function0[A]
>
>   class SuspImpl[A](lazyValue: => A) extends Susp[A] { ... }
>
>   def delay[A](value: => A): Susp[A] = new SuspImpl[A](value)
>
> Code appended.
>
> [..]
>
> Short code is good.  Each extra character should buy something new.
>
> -Lex
>
>
> /**
>  * Pseudo-package for lazy evaluation.
>  */
> object lazy {
>   /** Delay the evaluation of an expression until it is needed. */
>   def delay[A](value: => A): Susp[A] = new SuspImpl[A](value)
>
>   /** Get the value of a delayed expression. */
>   implicit def force[A](s: Susp[A]): A = s()
>
>   /**
>    * Data type of suspended computations. (The name froms from ML.)
>    */
>   abstract class Susp[+A] extends Function0[A]
>
>   /** Implementation of suspended computations, separated
>     * from the abstract class so that the type parameter can
>     * be invariant.
>     */
>   class SuspImpl[A](lazyValue: => A) extends Susp[A] {
>     private var maybeValue: Option[A] = None
>
>     override def apply() = {
>       maybeValue match {
> case None => {
>  val value = lazyValue
>  maybeValue = Some(value)
>  value
> }
> case Some(value) => value
>       }
>     }
>
>     override def toString() =
>       maybeValue match {
> case None => "Susp(?)"
> case Some(value) => "Susp(" + value + ")"
>       }
>   }
> }
>
> /**
>  * Test program.
>  */
> object lazy_test {
>   import lazy._
>
>   def main(args: Array[String]) = {
>     val s: Susp[Int] = delay { Console.println("evaluating..."); 3 }
>     Console.println("s = " + s)     // show that s is unevaluated
>     Console.println("s() = " + s()) // evaluate s
>     Console.println("s = " + s)     // show that the value is saved
>     Console.println("2 + s = " + (2 + s)) // implicit call to force()
>
>     val sl = delay { Some(3) }
>     val sl1: Susp[Some[int]] = sl
>     val sl2: Susp[Option[int]] = sl1   // the type is covariant
>
>     Console.println("sl2 = " + sl2)
>     Console.println("sl2() = " + sl2())
>     Console.println("sl2 = " + sl2)
>   }
> }
>
>
Reply | Threaded
Open this post in threaded view
|

Re: implementing 'delay' and 'force' in Scala

Jamie Webb-3
In reply to this post by Lex Spoon
On Thu, Apr 27, 2006 at 10:32:32AM +0200, Lex Spoon wrote:
> Hmm, Jamie points towards a solution.  You can declare the abstract
> type of Susp using a covariant type parameter, while using invariance
> in the implementation:

Heh. Didn't realise you could do that. Makes sense now I think about
it.

> Incidentally, I have mixed feelings about whether it is really a good
> idea to eliminate null as a possibility as in ML.  The question comes
> with the kind of code that is written under it.  There's an empirical
> question here, but *IF* you end up writing lots of option types and
> strewing .get's (valOf's) all over the place, then the overall
> situation seems worse.  The code has gotten longer, but we haven't
> substantially improved the relibiality.  Just like casts in Java 1.4,
> the .get's become so common that programmers stop bothering trying to
> get rid of them.

But why would you be using an option type if you know the value is
present? Wouldn't this just suggest that you should have unwrapped the
underlying value earlier on?

I use option types extensively, and almost never use a parameterless
get. I view them much as I view casts: sometimes necessary, but
usually a sign of bad design. If there's a possibility of None, it's
there for a reason, and there should be code to handle it.

-- Jamie Webb
Reply | Threaded
Open this post in threaded view
|

Re: implementing 'delay' and 'force' in Scala

Lex Spoon
In reply to this post by Stéphane Micheloud
Stéphane Micheloud <[hidden email]> writes:
> Thanks to Lex whose nice example (renamed to
> lazyEvaluation.scala) is now available from:
>
>    http://scala.epfl.ch/examples/more.html

To be clear, the vast bulk of the code is of course John Williams' .

-Lex


Reply | Threaded
Open this post in threaded view
|

Re: implementing 'delay' and 'force' in Scala

Lex Spoon
In reply to this post by Jamie Webb-3
Jamie Webb <[hidden email]> writes:

> > Incidentally, I have mixed feelings about whether it is really a good
> > idea to eliminate null as a possibility as in ML.  The question comes
> > with the kind of code that is written under it.  There's an empirical
> > question here, but *IF* you end up writing lots of option types and
> > strewing .get's (valOf's) all over the place, then the overall
> > situation seems worse.  The code has gotten longer, but we haven't
> > substantially improved the relibiality.  Just like casts in Java 1.4,
> > the .get's become so common that programmers stop bothering trying to
> > get rid of them.
>
> But why would you be using an option type if you know the value is
> present? Wouldn't this just suggest that you should have unwrapped the
> underlying value earlier on?

Appel's compiler design for the Tiger books has a lot of them, and I
think that compiler is well designed.  It happens in that design
because the compiler has multiple passes, and later passes fill in
information left out by earlier passes.  Later passes know for sure
that the information is there.

I am sure Appel looked closely at this, and I remember that I looked
closely at it.  I could not find a good redesign, though, and after
some amount of time one needs to stop hacking the types and write down
the behavior, no?  One rejected redesign, I recall, was to duplicate
the data structures in question, having one version using options and
another using bare values.  However, that seemed like too much
duplication of code to be worth the benefit.

It wasn't just options, by the way.  Later passes also desugar away
other datatype branches.  Sufficiently late passes can assume that the
desugared options were no longer there, but that means your switch
statements can appear to the type checker to have incomplete coverage.


> I use option types extensively, and almost never use a parameterless
> get. I view them much as I view casts: sometimes necessary, but
> usually a sign of bad design. If there's a possibility of None, it's
> there for a reason, and there should be code to handle it.

If you can consistently accomplish such code, then I agree it is nice
that optionality is explicit.  The emperical question is whether
practitioners can consistently accomplish it....

As another example, given parametric polymorphism, I find casts
infrequent, so it's worth having to make them explicit.  In the
original Java, though, I really suspect that casts are so frequent
that they may as well have been implicit!

Note that implicit casts would not make the type checker pointless.
The type checker could still find errors for you where the types in
question do not overlap at all, e.g. when you use a filename (String)
instead of an open file (FileReader).  Also, you would still get
benefits to code structure and to performance.

Yet another example is exception checking in Java.  In practice,
programs seem to have so many handlers sprinkled around that the
checking causes more harm than good.  Scala in fact does omit this
checking....


-Lex


Reply | Threaded
Open this post in threaded view
|

Re: implementing 'delay' and 'force' in Scala

Jamie Webb-3
On Thu, Apr 27, 2006 at 03:01:49PM +0200, Lex Spoon wrote:
> > But why would you be using an option type if you know the value is
> > present? Wouldn't this just suggest that you should have unwrapped the
> > underlying value earlier on?
>
> Appel's compiler design for the Tiger books has a lot of them, and I
> think that compiler is well designed.  It happens in that design
> because the compiler has multiple passes, and later passes fill in
> information left out by earlier passes.  Later passes know for sure
> that the information is there.

Scala is more expressive than ML or Java though... I haven't read the
books, but how about this: define a new type isomorphic to Option for
each phase, and an implicit conversion from each option type to its
element type. Then each phase can import only those implicit
conversions that are appropriate. Now we have no explicit gets, and
the compiler will catch members accessed out of place.

> It wasn't just options, by the way.  Later passes also desugar away
> other datatype branches.  Sufficiently late passes can assume that the
> desugared options were no longer there, but that means your switch
> statements can appear to the type checker to have incomplete coverage.

Supposing Scala detected incomplete matches (I wish it did, at least
for sealed traits), I imagine one could make use of subtyping to get
around this.

> As another example, given parametric polymorphism, I find casts
> infrequent, so it's worth having to make them explicit.  In the
> original Java, though, I really suspect that casts are so frequent
> that they may as well have been implicit!

Indeed.

> Yet another example is exception checking in Java.  In practice,
> programs seem to have so many handlers sprinkled around that the
> checking causes more harm than good.  Scala in fact does omit this
> checking....

Yes, I think the principal is a reasonable one, but there were
certainly too many problems as implemented in Java. Maybe someone will
come up with a better design for them at some point.

-- Jamie Webb