Rethinking PartialFunction

While we're re-imagining partial functions, let me throw another one around:

http://gist.github.com/643539

-jason

On Sun, Oct 24, 2010 at 2:06 PM, martin odersky wrote:
> Hi Paul,
>
> I have been thinking of using PartialFunctions for some code that
> essentially does high-performance state machines. PartialFunctions are
> generally very nice, but have two efficiency problems in that respect.
> First, we need to generate the pattern matching code twice, once in the
> apply and then again in the isDefinedAt. Second, we also need to execute the
> code twice, first to test whether the function is applicable, and then to
> actually apply it.

While we're re-imagining partial functions, let me throw another one around:

 http://gist.github.com/643539

-jason

Martin,

I know this wasn't addressed to me, but I'd like to add my two cents.

I've been using PF a lot and think that your suggestion would benefit what I'm doing. I never call isDefinedAt and then not actually call the function. Also, I've implemented some PFs by extending PartialFunction and actually implementing the isDefinedAt and apply methods; in these cases I have to write the duplicate code myself.

However, I think that it would be better to add applyOrElse to the Function1 class and remove the distinction between partial and complete functions. The distinction between them is so minor that there's not much value in keeping them separate--however it does create a fair bit of inconvenience because one cannot simply use a complete function in place of a PF. In other words, if I have a function that takes a PF, then I have to provide one, even if what I actually have is a complete function that never throws MatchError.

I think that the issue arises from the mismatch between the notions of complete and partial functions and their positions in the class hierarchy. A complete function "is a" partial function in the sense that it defines return values for some set of input values; the set of valid input values just happens to include all of the values allowable by the type system. Any code can accept a partial function will conceptually work just fine with a complete function. The opposite is not true: code that requires a complete function may not work with a partial function. That suggests that Function1 should inherit from PF, not the other way around. However in Scala 2.8, PF is a subclass of Function1, because it adds the isDefinedAt function. Essentially Scala is defining a partial function as one that allows the caller to test whether or not the function is defined for some input value before actually applying it.

When I suggested removing PartialFunction before (at the time, I suggested adding isDefinedAt to Function1 and having it return true), your objection was that it would be inappropriate to return true from Function1.isDefinedAt because Function1 doesn't guarantee that it won't throw MatchError. That may be the design, but I don't think that PF makes that guarantee either, even after returning true from isDefinedAt. After all the PF may call another function that throws MatchError. In fact, if you take the point of view that any Function1 may throw MatchError (which you have!) then that means that any PF that calls any regular function may itself wind up throwing MatchError. Even ignoring that argument, consider a PF[String, File] representing a directory in a filesystem. The application may call isDefinedAt to discover whether or not some file exists, then apply to retrieve that file. But the file may be deleted by some other process between those two calls, causing apply to throw MatchError even though it previously indicated via isDefinedAt that the input was okay.

Now you're proposing removing the isDefinedAt method, which would change Scala's definition of a PF from one that allows the caller to test an input value to something else: a function that allows the caller to pass a default value. I think that this makes the distinction between Function1 and PF even smaller because now the caller always has to actually invoke the function.

How about something like this?

trait Function1[A, B] {
def apply(a: A): B
def applyOrElse(a: A, default: => B) = a
}

Defining a PF in code using { case ... } will produce a Function1 that looks like:

new Function1[A, B] {
def apply(a: A): B = applyOrElse(a, new MatchError(a))
def applyOrElse(a: A, default: => B) = a match { case ...; case _ => default }
}

W

On Oct 24, 2010, at 8:06 AM, martin odersky wrote:

> Hi Paul,
>
> I have been thinking of using PartialFunctions for some code that essentially does high-performance state machines. PartialFunctions are generally very nice, but have two efficiency problems in that respect. First, we need to generate the pattern matching code twice, once in the apply and then again in the isDefinedAt. Second, we also need to execute the code twice, first to test whether the function is applicable, and then to actually apply it.
>
> Can we do without the double duplication? We could if we had a slightly different type, call it FuntionWithDefault:
>
> FunctionWithDefault would have only one abstract method, applyOrElse:
>
> trait FunctionWithDefault[A, +B] extends (A => B) {
> def applyOrElse[B1 >: B](x: A, default: A => B1): B1
>
> The method takes a default function, which is applied in case of a failed match (note that this means that FunctionWithDefault needs to be non-variant in its domain type parameter). The apply function can then be implemented in terms of applyOrElse:
>
> def apply(x: A): B = applyOrElse(x, throw new MatchError(x))
>
> So only one copy of the pattern match is needed. The isDefinedAt function cannot be defined using applyOrElse. But then it seems that
> almost everything we do with PartialFunctions does not need isDefinedAt, and can do with just applyOrElse. As an argument in favor I have
> implemented all methods in PartialFunction with equivalent methods in FunctionWithDefault. It works, even though we need a somewhat ugly (private) exception for andThen and lift.
>
> Aside: We could change the contract and have a success continuation as well as an error continuation in applyOrElse. This would make
> andThen and orElse nicer and slightly more efficient (throwing and catching the exception is reputedly (**) about as costly as three virtual method calls). But it would make the code to be generated more diificult (have to thread the success comntinuation in everyhwere and also slower. So I am not sure it's worth it.
>
> Your thoughts?
>
> Cheers
>

Hi Paul,

I have been thinking of using PartialFunctions for some code that essentially does high-performance state machines. PartialFunctions are generally very nice, but have two efficiency problems in that respect. First, we need to generate the pattern matching code twice, once in the apply and then again in the isDefinedAt. Second, we also need to execute the code twice, first to test whether the function is applicable, and then to actually apply it.

Can we do without the double duplication? We could if we had a slightly different type, call it FuntionWithDefault:

FunctionWithDefault would have only one abstract method, applyOrElse:

  trait FunctionWithDefault[A, +B] extends (A => B) {
    def applyOrElse[B1 >: B](x: A, default: A => B1): B1

The method takes a default function, which is applied in case of a failed match (note that this means that FunctionWithDefault needs to be non-variant in its domain type parameter). The apply function can then be implemented in terms of applyOrElse:

    def apply(x: A): B = applyOrElse(x, throw new MatchError(x))

So only one copy of the pattern match is needed. The isDefinedAt function cannot be defined using applyOrElse. But then it seems that
almost everything we do with PartialFunctions does not need isDefinedAt, and can do with just applyOrElse. As an argument in favor I have
implemented all methods in PartialFunction with equivalent methods in FunctionWithDefault. It works, even though we need a somewhat ugly (private) exception for andThen and lift.

Aside: We could change the contract and have a success continuation as well as an error continuation in applyOrElse. This would make
andThen and orElse nicer and slightly more efficient (throwing and catching the exception is reputedly (**) about as costly as three virtual method calls). But it would make the code to be generated more diificult (have to thread the success comntinuation in everyhwere and also slower. So I am not sure it's worth it.

Your thoughts?

Cheers

 -- Martin

(**) That's what John Rose told me.

P.S. Here's the code of FunctionWithDefault:

package scala

/** A function with default of type `FunctionWithDefault[A, B]` is a
 *  unary function where the domain does not necessarily include all values of type
 *  `A`. The function `isDefinedAt` allows to
 *  test dynamically if a value is in the domain of the function.
 *
 *  @author  Martin Odersky
 *  @version 1.0, 16/07/2003
 */
trait FunctionWithDefault[A, +B] extends (A => B) {

  def applyOrElse[B1 >: B](x: A, default: A => B1): B1

  def apply(x: A): B = applyOrElse(x, throw new MatchError(x))

  /** Composes this function with default with a fallback function with default which gets applied where this function with default
   *  is not defined.
   *
   *  @param   that    the fallback function
   *  @tparam  A1      the argument type of the fallback function
   *  @tparam  B1      the result type of the fallback function
   *  @return  a function with default which has as domain the union of the domains
   *           of this function with default and `that`. The resulting function with default
   *           takes `x` to `this(x)` where `this` is defined, and to `that(x)` where it is not.
   */
  def orElse[B1 >: B](that: FunctionWithDefault[A, B1]) : FunctionWithDefault[A, B1] =
    new FunctionWithDefault[A, B1] {
    def applyOrElse[B2 >: B1](x: A, default: A => B2): B2 =
      FunctionWithDefault.this.applyOrElse(x, that)
  }

  /**  Composes this function with default with a transformation function that gets applied
   *   to results of this function with default.
   *   @param  k  the transformation function
   *   @tparam C  the result type of the transformation function.
   *   @return a function with default with the same domain as this function with default, which maps
   *           arguments `x` to `k(this(x))`.
   */
  override def andThen[C](k: B => C) : FunctionWithDefault[A, C] = new FunctionWithDefault[A, C] {
    def applyOrElse[C1 >: C](x: A, default: A => C1): C1 =
      try {
        k(FunctionWithDefault.this.applyOrElse(x, throw FunctionWithDefault.DoDefault))
      } catch {
        case ex: FunctionWithDefault.DefaultException => default(x)
      }
  }

  /** Turns this function with default into an plain function returning an `Option` result.
   *  @see     Function1#unlift
   *  @return  a function that takes an argument `x` to `Some(this(x))` if `this`
   *           is defined for `x`, and to `None` otherwise.
   */
  def lift: A => Option[B] = new (A => Option[B]) {
    def apply(x: A): Option[B] =
      try {
        Some(FunctionWithDefault.this.applyOrElse(x, throw FunctionWithDefault.DoDefault))
      } catch {
        case ex: FunctionWithDefault.DefaultException => None
      }
/* needs adaptation in Function1
    override def unlift[R1](implicit ev: Option[B] <:< Option[R1]): FunctionWithDefault[A, R1] =
      FunctionWithDefault.this.asInstanceOf[FunctionWithDefault[A, R1]]
      */
  }
}

/** A few handy operations which leverage the extra bit of information
 *  available in functions with default.  Examples:
 *
 * <pre>
 *  import FunctionWithDefault._
 *
 *  def strangeConditional(other: Any): Boolean = cond(other) {
 *    case x: String if x == "abc" || x == "def"  => true
 *    case x: Int => true
 *  }
 *  def onlyInt(v: Any): Option[Int] = condOpt(v) { case x: Int => x }
 * </pre>
 *
 *  @author  Paul Phillips
 *  @since   2.8
 */
object FunctionWithDefault
{
  /** Creates a Boolean test based on a value and a function with default.
   *  It behaves like a 'match' statement with an implied 'case _ => false'
   *  following the supplied cases.
   *
   *  @param  x   the value to test
   *  @param  pf  the function with default
   *  @return true, iff `x` is in the domain of `pf` and `pf(x) == true`.
   */
  def cond[T](x: T)(pf: FunctionWithDefault[T, Boolean]): Boolean =
    pf.applyOrElse(x, _ => false)
 
  /** Transforms a FunctionWithDefault[T, U] `pf' into Function1[T, Option[U]] `f'
   *  whose result is Some(x) if the argument is in pf's domain and None otherwise,
   *  and applies it to the value `x'.  In effect, it is a 'match' statement
   *  which wraps all case results in Some(_) and adds 'case _ => None' to the end.
   *
   *  @param  x     the value to test
   *  @param  pf    the FunctionWithDefault[T, U]
   *  @return `Some(pf(x))` if `pf isDefinedAt x`, `None` otherwise.
   */
  def condOpt[T,U](x: T)(pf: FunctionWithDefault[T, U]): Option[U] =
    pf.lift(x)

  private class DefaultException extends Exception
  private val DoDefault = new DefaultException
}

On Sun, Oct 24, 2010 at 3:49 PM, Jason Zaugg <jzaugg [at] gmail [dot] com> wrote:

While we're re-imagining partial functions, let me throw another one around:

 http://gist.github.com/643539

-jason

That seems to go very much in the same direction, and it's very elegant to boot! But it would be heavier weight, in the amount of closures generated (one per case it looks to me) and in the amount of indirections. I was after having a version of partial function with minimal performance penalties.

Btw, I worked it out now how to do FunctionWithDefault contravariantly in its argument. Result is attached.

Cheers

 -- Martin

Is there any potential for also combining this with the concept of translucent functions?

On 24 October 2010 15:15, martin odersky <martin [dot] odersky [at] epfl [dot] ch> wrote:

On Sun, Oct 24, 2010 at 3:49 PM, Jason Zaugg <jzaugg [at] gmail [dot] com> wrote:

While we're re-imagining partial functions, let me throw another one around:

 http://gist.github.com/643539

-jason

That seems to go very much in the same direction, and it's very elegant to boot! But it would be heavier weight, in the amount of closures generated (one per case it looks to me) and in the amount of indirections. I was after having a version of partial function with minimal performance penalties.

Btw, I worked it out now how to do FunctionWithDefault contravariantly in its argument. Result is attached.

Cheers

 -- Martin

--
Kevin Wright

mail / gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com
pulse / skype: kev.lee.wright
twitter: @thecoda

Hi Willis,

I think fundamentally, the distinction is stll the same. PartailFunction/FunctionWithDefault have some notion of testable domain whereas Function has not. As you write, we could give Function a trivial notion of testable domain.

However, that would make every function more expensive. For instance, every apply would have to forward to applyOrElse. This might well make a difference in complex optimizations. Since efficient function calls are of overwhelming importance, the tradeoffs have not changed, in my opinion.

Cheers

 -- Martin

Martin,

Please look at my example again. Every apply would not forward to applyOrElse. A regular function would implement apply, and there is a default implementation of applyOrElse that forwards to apply.

If someone was using a complete function as a partial function (by calling applyOrElse) then there would be a double call, from applyOrElse to apply, however, that is exactly what happens right now, because in order to use a Function1 where a PartialFunction is expected, the application must wrap it in a PartialFunction.

W

On Oct 24, 2010, at 10:58 AM, martin odersky wrote:

> Hi Willis,
>
> I think fundamentally, the distinction is stll the same. PartailFunction/FunctionWithDefault have some notion of testable domain whereas Function has not. As you write, we could give Function a trivial notion of testable domain. However, that would make every function more expensive. For instance, every apply would have to forward to applyOrElse. This might well make a difference in complex optimizations. Since efficient function calls are of overwhelming importance, the tradeoffs have not changed, in my opinion.
>
> Cheers
>

I'd love to see a new implementation of PartialFunction, but the challenge with applyOrElse is that if the body of the PartialFunction is side effecting and you're only testing for isDefinedAt, the side effect will still occur (there are places where Lift tests isDefinedAt on partial functions and caches the partial function for application when Lift has set up more machinery).

What if each case body was implemented as a separate method and there was a "functionForMatch" method such:

trait AnotherKindOfPartialFunction[A, +B] extends A => B {
  def functionForMatch(a: A): Option[() => B]
  def isDefinedAt(a: A): Boolean = functionForMatch(a).isDefined
  def apply(a: A): B = functionForMatch match {case Some(f) => f() case None => throw new MatchError}
}

Technically, it's 2 object allocations for each apply and isDefinedAt, but HotSpot might optimize the object allocations away or treat them as stack allocations after doing escape analysis.

This also means that the body of the pattern is much smaller.

Martin,

Please look at my example again.  Every apply would not forward to applyOrElse.  A regular function would implement apply, and there is a default implementation of applyOrElse that forwards to apply.

If someone was using a complete function as a partial function (by calling applyOrElse) then there would be a double call, from applyOrElse to apply, however, that is exactly what happens right now, because in order to use a Function1 where a PartialFunction is expected, the application must wrap it in a PartialFunction.

I'm with the family today so I don't know if I can properly respond
until tomorrow. And I'm glad to see there is no shortage of opinions.
I also think this is very important to get as right as we can.

On Sun, Oct 24, 2010 at 05:31:15PM +0200, martin odersky wrote:
> 3. Change the rules so that in a pattern matching expression
>
> x match { case P1 => ... case Pn => ... }
>
> that was the body of a function, a selector that was not matched by
> any of the patterns invoked missingCase(x) instead of immediately
> throwing a MatchError(x).

My initial intuition is that this is a winner. Structural things I
think should be considered include a) deprecating PartialFunction rather
than trying too hard to keep it relevant and b) considering a new common
supertype for F1 / PF / possible-third-creation. And we should be
taking an up to date look at things like the interactions of mixin
composition and specialization, such as this one:

// a.scala
class Bippy[T1, T2, R] extends Function2[T1, T2, R] {
def apply(x1: T1, x2: T2): R = error("")
}

// 33K!
% ls -l Bippy.class
-rw-r--r-- 1 paulp wheel 32885 Oct 24 08:55 Bippy.class

The conditions under which certain things were conceived and showed
little cost have changed. AbstractFunctionN works around this somewhat
under the current regime, but if we start introducing new Function
classes then that approach will break down quickly under the steely
glare of combinatorial reality.

Side note: interesting that curry exacts the same cost as curried even
though the entire implementation is:

@deprecated("Use 'curried' instead")
def curry = curried

% jp Bippy | grep public
public class Bippy extends java.lang.Object implements scala.Function2,scala.ScalaObject
public void apply$mcVII$sp(int, int);
public boolean apply$mcZII$sp(int, int);
public int apply$mcIII$sp(int, int);
public float apply$mcFII$sp(int, int);
public long apply$mcJII$sp(int, int);
public double apply$mcDII$sp(int, int);
public void apply$mcVIJ$sp(int, long);
public boolean apply$mcZIJ$sp(int, long);
public int apply$mcIIJ$sp(int, long);
public float apply$mcFIJ$sp(int, long);
public long apply$mcJIJ$sp(int, long);
public double apply$mcDIJ$sp(int, long);
public void apply$mcVID$sp(int, double);
public boolean apply$mcZID$sp(int, double);
public int apply$mcIID$sp(int, double);
public float apply$mcFID$sp(int, double);
public long apply$mcJID$sp(int, double);
public double apply$mcDID$sp(int, double);
public void apply$mcVJI$sp(long, int);
public boolean apply$mcZJI$sp(long, int);
public int apply$mcIJI$sp(long, int);
public float apply$mcFJI$sp(long, int);
public long apply$mcJJI$sp(long, int);
public double apply$mcDJI$sp(long, int);
public void apply$mcVJJ$sp(long, long);
public boolean apply$mcZJJ$sp(long, long);
public int apply$mcIJJ$sp(long, long);
public float apply$mcFJJ$sp(long, long);
public long apply$mcJJJ$sp(long, long);
public double apply$mcDJJ$sp(long, long);
public void apply$mcVJD$sp(long, double);
public boolean apply$mcZJD$sp(long, double);
public int apply$mcIJD$sp(long, double);
public float apply$mcFJD$sp(long, double);
public long apply$mcJJD$sp(long, double);
public double apply$mcDJD$sp(long, double);
public void apply$mcVDI$sp(double, int);
public boolean apply$mcZDI$sp(double, int);
public int apply$mcIDI$sp(double, int);
public float apply$mcFDI$sp(double, int);
public long apply$mcJDI$sp(double, int);
public double apply$mcDDI$sp(double, int);
public void apply$mcVDJ$sp(double, long);
public boolean apply$mcZDJ$sp(double, long);
public int apply$mcIDJ$sp(double, long);
public float apply$mcFDJ$sp(double, long);
public long apply$mcJDJ$sp(double, long);
public double apply$mcDDJ$sp(double, long);
public void apply$mcVDD$sp(double, double);
public boolean apply$mcZDD$sp(double, double);
public int apply$mcIDD$sp(double, double);
public float apply$mcFDD$sp(double, double);
public long apply$mcJDD$sp(double, double);
public double apply$mcDDD$sp(double, double);
public java.lang.String toString();
public scala.Function1 curried();
public scala.Function1 curried$mcVII$sp();
public scala.Function1 curried$mcZII$sp();
public scala.Function1 curried$mcIII$sp();
public scala.Function1 curried$mcFII$sp();
public scala.Function1 curried$mcJII$sp();
public scala.Function1 curried$mcDII$sp();
public scala.Function1 curried$mcVIJ$sp();
public scala.Function1 curried$mcZIJ$sp();
public scala.Function1 curried$mcIIJ$sp();
public scala.Function1 curried$mcFIJ$sp();
public scala.Function1 curried$mcJIJ$sp();
public scala.Function1 curried$mcDIJ$sp();
public scala.Function1 curried$mcVID$sp();
public scala.Function1 curried$mcZID$sp();
public scala.Function1 curried$mcIID$sp();
public scala.Function1 curried$mcFID$sp();
public scala.Function1 curried$mcJID$sp();
public scala.Function1 curried$mcDID$sp();
public scala.Function1 curried$mcVJI$sp();
public scala.Function1 curried$mcZJI$sp();
public scala.Function1 curried$mcIJI$sp();
public scala.Function1 curried$mcFJI$sp();
public scala.Function1 curried$mcJJI$sp();
public scala.Function1 curried$mcDJI$sp();
public scala.Function1 curried$mcVJJ$sp();
public scala.Function1 curried$mcZJJ$sp();
public scala.Function1 curried$mcIJJ$sp();
public scala.Function1 curried$mcFJJ$sp();
public scala.Function1 curried$mcJJJ$sp();
public scala.Function1 curried$mcDJJ$sp();
public scala.Function1 curried$mcVJD$sp();
public scala.Function1 curried$mcZJD$sp();
public scala.Function1 curried$mcIJD$sp();
public scala.Function1 curried$mcFJD$sp();
public scala.Function1 curried$mcJJD$sp();
public scala.Function1 curried$mcDJD$sp();
public scala.Function1 curried$mcVDI$sp();
public scala.Function1 curried$mcZDI$sp();
public scala.Function1 curried$mcIDI$sp();
public scala.Function1 curried$mcFDI$sp();
public scala.Function1 curried$mcJDI$sp();
public scala.Function1 curried$mcDDI$sp();
public scala.Function1 curried$mcVDJ$sp();
public scala.Function1 curried$mcZDJ$sp();
public scala.Function1 curried$mcIDJ$sp();
public scala.Function1 curried$mcFDJ$sp();
public scala.Function1 curried$mcJDJ$sp();
public scala.Function1 curried$mcDDJ$sp();
public scala.Function1 curried$mcVDD$sp();
public scala.Function1 curried$mcZDD$sp();
public scala.Function1 curried$mcIDD$sp();
public scala.Function1 curried$mcFDD$sp();
public scala.Function1 curried$mcJDD$sp();
public scala.Function1 curried$mcDDD$sp();
public scala.Function1 curry();
public scala.Function1 curry$mcVII$sp();
public scala.Function1 curry$mcZII$sp();
public scala.Function1 curry$mcIII$sp();
public scala.Function1 curry$mcFII$sp();
public scala.Function1 curry$mcJII$sp();
public scala.Function1 curry$mcDII$sp();
public scala.Function1 curry$mcVIJ$sp();
public scala.Function1 curry$mcZIJ$sp();
public scala.Function1 curry$mcIIJ$sp();
public scala.Function1 curry$mcFIJ$sp();
public scala.Function1 curry$mcJIJ$sp();
public scala.Function1 curry$mcDIJ$sp();
public scala.Function1 curry$mcVID$sp();
public scala.Function1 curry$mcZID$sp();
public scala.Function1 curry$mcIID$sp();
public scala.Function1 curry$mcFID$sp();
public scala.Function1 curry$mcJID$sp();
public scala.Function1 curry$mcDID$sp();
public scala.Function1 curry$mcVJI$sp();
public scala.Function1 curry$mcZJI$sp();
public scala.Function1 curry$mcIJI$sp();
public scala.Function1 curry$mcFJI$sp();
public scala.Function1 curry$mcJJI$sp();
public scala.Function1 curry$mcDJI$sp();
public scala.Function1 curry$mcVJJ$sp();
public scala.Function1 curry$mcZJJ$sp();
public scala.Function1 curry$mcIJJ$sp();
public scala.Function1 curry$mcFJJ$sp();
public scala.Function1 curry$mcJJJ$sp();
public scala.Function1 curry$mcDJJ$sp();
public scala.Function1 curry$mcVJD$sp();
public scala.Function1 curry$mcZJD$sp();
public scala.Function1 curry$mcIJD$sp();
public scala.Function1 curry$mcFJD$sp();
public scala.Function1 curry$mcJJD$sp();
public scala.Function1 curry$mcDJD$sp();
public scala.Function1 curry$mcVDI$sp();
public scala.Function1 curry$mcZDI$sp();
public scala.Function1 curry$mcIDI$sp();
public scala.Function1 curry$mcFDI$sp();
public scala.Function1 curry$mcJDI$sp();
public scala.Function1 curry$mcDDI$sp();
public scala.Function1 curry$mcVDJ$sp();
public scala.Function1 curry$mcZDJ$sp();
public scala.Function1 curry$mcIDJ$sp();
public scala.Function1 curry$mcFDJ$sp();
public scala.Function1 curry$mcJDJ$sp();
public scala.Function1 curry$mcDDJ$sp();
public scala.Function1 curry$mcVDD$sp();
public scala.Function1 curry$mcZDD$sp();
public scala.Function1 curry$mcIDD$sp();
public scala.Function1 curry$mcFDD$sp();
public scala.Function1 curry$mcJDD$sp();
public scala.Function1 curry$mcDDD$sp();
public scala.Function1 tupled();
public scala.Function1 tupled$mcVII$sp();
public scala.Function1 tupled$mcZII$sp();
public scala.Function1 tupled$mcIII$sp();
public scala.Function1 tupled$mcFII$sp();
public scala.Function1 tupled$mcJII$sp();
public scala.Function1 tupled$mcDII$sp();
public scala.Function1 tupled$mcVIJ$sp();
public scala.Function1 tupled$mcZIJ$sp();
public scala.Function1 tupled$mcIIJ$sp();
public scala.Function1 tupled$mcFIJ$sp();
public scala.Function1 tupled$mcJIJ$sp();
public scala.Function1 tupled$mcDIJ$sp();
public scala.Function1 tupled$mcVID$sp();
public scala.Function1 tupled$mcZID$sp();
public scala.Function1 tupled$mcIID$sp();
public scala.Function1 tupled$mcFID$sp();
public scala.Function1 tupled$mcJID$sp();
public scala.Function1 tupled$mcDID$sp();
public scala.Function1 tupled$mcVJI$sp();
public scala.Function1 tupled$mcZJI$sp();
public scala.Function1 tupled$mcIJI$sp();
public scala.Function1 tupled$mcFJI$sp();
public scala.Function1 tupled$mcJJI$sp();
public scala.Function1 tupled$mcDJI$sp();
public scala.Function1 tupled$mcVJJ$sp();
public scala.Function1 tupled$mcZJJ$sp();
public scala.Function1 tupled$mcIJJ$sp();
public scala.Function1 tupled$mcFJJ$sp();
public scala.Function1 tupled$mcJJJ$sp();
public scala.Function1 tupled$mcDJJ$sp();
public scala.Function1 tupled$mcVJD$sp();
public scala.Function1 tupled$mcZJD$sp();
public scala.Function1 tupled$mcIJD$sp();
public scala.Function1 tupled$mcFJD$sp();
public scala.Function1 tupled$mcJJD$sp();
public scala.Function1 tupled$mcDJD$sp();
public scala.Function1 tupled$mcVDI$sp();
public scala.Function1 tupled$mcZDI$sp();
public scala.Function1 tupled$mcIDI$sp();
public scala.Function1 tupled$mcFDI$sp();
public scala.Function1 tupled$mcJDI$sp();
public scala.Function1 tupled$mcDDI$sp();
public scala.Function1 tupled$mcVDJ$sp();
public scala.Function1 tupled$mcZDJ$sp();
public scala.Function1 tupled$mcIDJ$sp();
public scala.Function1 tupled$mcFDJ$sp();
public scala.Function1 tupled$mcJDJ$sp();
public scala.Function1 tupled$mcDDJ$sp();
public scala.Function1 tupled$mcVDD$sp();
public scala.Function1 tupled$mcZDD$sp();
public scala.Function1 tupled$mcIDD$sp();
public scala.Function1 tupled$mcFDD$sp();
public scala.Function1 tupled$mcJDD$sp();
public scala.Function1 tupled$mcDDD$sp();
public java.lang.Object apply(java.lang.Object, java.lang.Object);
public Bippy();

I'm with the family today so I don't know if I can properly respond
until tomorrow.  And I'm glad to see there is no shortage of opinions.
I also think this is very important to get as right as we can.

On Sun, Oct 24, 2010 at 05:31:15PM +0200, martin odersky wrote:
> 3. Change the rules so that in a pattern matching expression
>
>   x match { case P1 => ... case Pn => ... }
>
> that was the body of a function, a selector that was not matched by
> any of the patterns invoked missingCase(x) instead of immediately
> throwing a MatchError(x).

My initial intuition is that this is a winner.  Structural things I
think should be considered include a) deprecating PartialFunction rather
than trying too hard to keep it relevant and b) considering a new common
supertype for F1 / PF / possible-third-creation.  And we should be
taking an up to date look at things like the interactions of mixin
composition and specialization, such as this one:

// a.scala
class Bippy[T1, T2, R] extends Function2[T1, T2, R] {
 def apply(x1: T1, x2: T2): R = error("")
} 

// 33K!
% ls -l Bippy.class
-rw-r--r--  1 paulp  wheel  32885 Oct 24 08:55 Bippy.class

The conditions under which certain things were conceived and showed
little cost have changed.  AbstractFunctionN works around this somewhat
under the current regime, but if we start introducing new Function
classes then that approach will break down quickly under the steely
glare of combinatorial reality.

Side note: interesting that curry exacts the same cost as curried even
though the entire implementation is:

 @deprecated("Use 'curried' instead")
 def curry = curried

% jp Bippy | grep public
public class Bippy extends java.lang.Object implements scala.Function2,scala.ScalaObject
public void apply$mcVII$sp(int, int);
public boolean apply$mcZII$sp(int, int);
public int apply$mcIII$sp(int, int);
public float apply$mcFII$sp(int, int);
public long apply$mcJII$sp(int, int);
public double apply$mcDII$sp(int, int);
public void apply$mcVIJ$sp(int, long);
public boolean apply$mcZIJ$sp(int, long);
public int apply$mcIIJ$sp(int, long);
public float apply$mcFIJ$sp(int, long);
public long apply$mcJIJ$sp(int, long);
public double apply$mcDIJ$sp(int, long);
public void apply$mcVID$sp(int, double);
public boolean apply$mcZID$sp(int, double);
public int apply$mcIID$sp(int, double);
public float apply$mcFID$sp(int, double);
public long apply$mcJID$sp(int, double);
public double apply$mcDID$sp(int, double);
public void apply$mcVJI$sp(long, int);
public boolean apply$mcZJI$sp(long, int);
public int apply$mcIJI$sp(long, int);
public float apply$mcFJI$sp(long, int);
public long apply$mcJJI$sp(long, int);
public double apply$mcDJI$sp(long, int);
public void apply$mcVJJ$sp(long, long);
public boolean apply$mcZJJ$sp(long, long);
public int apply$mcIJJ$sp(long, long);
public float apply$mcFJJ$sp(long, long);
public long apply$mcJJJ$sp(long, long);
public double apply$mcDJJ$sp(long, long);
public void apply$mcVJD$sp(long, double);
public boolean apply$mcZJD$sp(long, double);
public int apply$mcIJD$sp(long, double);
public float apply$mcFJD$sp(long, double);
public long apply$mcJJD$sp(long, double);
public double apply$mcDJD$sp(long, double);
public void apply$mcVDI$sp(double, int);
public boolean apply$mcZDI$sp(double, int);
public int apply$mcIDI$sp(double, int);
public float apply$mcFDI$sp(double, int);
public long apply$mcJDI$sp(double, int);
public double apply$mcDDI$sp(double, int);
public void apply$mcVDJ$sp(double, long);
public boolean apply$mcZDJ$sp(double, long);
public int apply$mcIDJ$sp(double, long);
public float apply$mcFDJ$sp(double, long);
public long apply$mcJDJ$sp(double, long);
public double apply$mcDDJ$sp(double, long);
public void apply$mcVDD$sp(double, double);
public boolean apply$mcZDD$sp(double, double);
public int apply$mcIDD$sp(double, double);
public float apply$mcFDD$sp(double, double);
public long apply$mcJDD$sp(double, double);
public double apply$mcDDD$sp(double, double);
public java.lang.String toString();
public scala.Function1 curried();
public scala.Function1 curried$mcVII$sp();
public scala.Function1 curried$mcZII$sp();
public scala.Function1 curried$mcIII$sp();
public scala.Function1 curried$mcFII$sp();
public scala.Function1 curried$mcJII$sp();
public scala.Function1 curried$mcDII$sp();
public scala.Function1 curried$mcVIJ$sp();
public scala.Function1 curried$mcZIJ$sp();
public scala.Function1 curried$mcIIJ$sp();
public scala.Function1 curried$mcFIJ$sp();
public scala.Function1 curried$mcJIJ$sp();
public scala.Function1 curried$mcDIJ$sp();
public scala.Function1 curried$mcVID$sp();
public scala.Function1 curried$mcZID$sp();
public scala.Function1 curried$mcIID$sp();
public scala.Function1 curried$mcFID$sp();
public scala.Function1 curried$mcJID$sp();
public scala.Function1 curried$mcDID$sp();
public scala.Function1 curried$mcVJI$sp();
public scala.Function1 curried$mcZJI$sp();
public scala.Function1 curried$mcIJI$sp();
public scala.Function1 curried$mcFJI$sp();
public scala.Function1 curried$mcJJI$sp();
public scala.Function1 curried$mcDJI$sp();
public scala.Function1 curried$mcVJJ$sp();
public scala.Function1 curried$mcZJJ$sp();
public scala.Function1 curried$mcIJJ$sp();
public scala.Function1 curried$mcFJJ$sp();
public scala.Function1 curried$mcJJJ$sp();
public scala.Function1 curried$mcDJJ$sp();
public scala.Function1 curried$mcVJD$sp();
public scala.Function1 curried$mcZJD$sp();
public scala.Function1 curried$mcIJD$sp();
public scala.Function1 curried$mcFJD$sp();
public scala.Function1 curried$mcJJD$sp();
public scala.Function1 curried$mcDJD$sp();
public scala.Function1 curried$mcVDI$sp();
public scala.Function1 curried$mcZDI$sp();
public scala.Function1 curried$mcIDI$sp();
public scala.Function1 curried$mcFDI$sp();
public scala.Function1 curried$mcJDI$sp();
public scala.Function1 curried$mcDDI$sp();
public scala.Function1 curried$mcVDJ$sp();
public scala.Function1 curried$mcZDJ$sp();
public scala.Function1 curried$mcIDJ$sp();
public scala.Function1 curried$mcFDJ$sp();
public scala.Function1 curried$mcJDJ$sp();
public scala.Function1 curried$mcDDJ$sp();
public scala.Function1 curried$mcVDD$sp();
public scala.Function1 curried$mcZDD$sp();
public scala.Function1 curried$mcIDD$sp();
public scala.Function1 curried$mcFDD$sp();
public scala.Function1 curried$mcJDD$sp();
public scala.Function1 curried$mcDDD$sp();
public scala.Function1 curry();
public scala.Function1 curry$mcVII$sp();
public scala.Function1 curry$mcZII$sp();
public scala.Function1 curry$mcIII$sp();
public scala.Function1 curry$mcFII$sp();
public scala.Function1 curry$mcJII$sp();
public scala.Function1 curry$mcDII$sp();
public scala.Function1 curry$mcVIJ$sp();
public scala.Function1 curry$mcZIJ$sp();
public scala.Function1 curry$mcIIJ$sp();
public scala.Function1 curry$mcFIJ$sp();
public scala.Function1 curry$mcJIJ$sp();
public scala.Function1 curry$mcDIJ$sp();
public scala.Function1 curry$mcVID$sp();
public scala.Function1 curry$mcZID$sp();
public scala.Function1 curry$mcIID$sp();
public scala.Function1 curry$mcFID$sp();
public scala.Function1 curry$mcJID$sp();
public scala.Function1 curry$mcDID$sp();
public scala.Function1 curry$mcVJI$sp();
public scala.Function1 curry$mcZJI$sp();
public scala.Function1 curry$mcIJI$sp();
public scala.Function1 curry$mcFJI$sp();
public scala.Function1 curry$mcJJI$sp();
public scala.Function1 curry$mcDJI$sp();
public scala.Function1 curry$mcVJJ$sp();
public scala.Function1 curry$mcZJJ$sp();
public scala.Function1 curry$mcIJJ$sp();
public scala.Function1 curry$mcFJJ$sp();
public scala.Function1 curry$mcJJJ$sp();
public scala.Function1 curry$mcDJJ$sp();
public scala.Function1 curry$mcVJD$sp();
public scala.Function1 curry$mcZJD$sp();
public scala.Function1 curry$mcIJD$sp();
public scala.Function1 curry$mcFJD$sp();
public scala.Function1 curry$mcJJD$sp();
public scala.Function1 curry$mcDJD$sp();
public scala.Function1 curry$mcVDI$sp();
public scala.Function1 curry$mcZDI$sp();
public scala.Function1 curry$mcIDI$sp();
public scala.Function1 curry$mcFDI$sp();
public scala.Function1 curry$mcJDI$sp();
public scala.Function1 curry$mcDDI$sp();
public scala.Function1 curry$mcVDJ$sp();
public scala.Function1 curry$mcZDJ$sp();
public scala.Function1 curry$mcIDJ$sp();
public scala.Function1 curry$mcFDJ$sp();
public scala.Function1 curry$mcJDJ$sp();
public scala.Function1 curry$mcDDJ$sp();
public scala.Function1 curry$mcVDD$sp();
public scala.Function1 curry$mcZDD$sp();
public scala.Function1 curry$mcIDD$sp();
public scala.Function1 curry$mcFDD$sp();
public scala.Function1 curry$mcJDD$sp();
public scala.Function1 curry$mcDDD$sp();
public scala.Function1 tupled();
public scala.Function1 tupled$mcVII$sp();
public scala.Function1 tupled$mcZII$sp();
public scala.Function1 tupled$mcIII$sp();
public scala.Function1 tupled$mcFII$sp();
public scala.Function1 tupled$mcJII$sp();
public scala.Function1 tupled$mcDII$sp();
public scala.Function1 tupled$mcVIJ$sp();
public scala.Function1 tupled$mcZIJ$sp();
public scala.Function1 tupled$mcIIJ$sp();
public scala.Function1 tupled$mcFIJ$sp();
public scala.Function1 tupled$mcJIJ$sp();
public scala.Function1 tupled$mcDIJ$sp();
public scala.Function1 tupled$mcVID$sp();
public scala.Function1 tupled$mcZID$sp();
public scala.Function1 tupled$mcIID$sp();
public scala.Function1 tupled$mcFID$sp();
public scala.Function1 tupled$mcJID$sp();
public scala.Function1 tupled$mcDID$sp();
public scala.Function1 tupled$mcVJI$sp();
public scala.Function1 tupled$mcZJI$sp();
public scala.Function1 tupled$mcIJI$sp();
public scala.Function1 tupled$mcFJI$sp();
public scala.Function1 tupled$mcJJI$sp();
public scala.Function1 tupled$mcDJI$sp();
public scala.Function1 tupled$mcVJJ$sp();
public scala.Function1 tupled$mcZJJ$sp();
public scala.Function1 tupled$mcIJJ$sp();
public scala.Function1 tupled$mcFJJ$sp();
public scala.Function1 tupled$mcJJJ$sp();
public scala.Function1 tupled$mcDJJ$sp();
public scala.Function1 tupled$mcVJD$sp();
public scala.Function1 tupled$mcZJD$sp();
public scala.Function1 tupled$mcIJD$sp();
public scala.Function1 tupled$mcFJD$sp();
public scala.Function1 tupled$mcJJD$sp();
public scala.Function1 tupled$mcDJD$sp();
public scala.Function1 tupled$mcVDI$sp();
public scala.Function1 tupled$mcZDI$sp();
public scala.Function1 tupled$mcIDI$sp();
public scala.Function1 tupled$mcFDI$sp();
public scala.Function1 tupled$mcJDI$sp();
public scala.Function1 tupled$mcDDI$sp();
public scala.Function1 tupled$mcVDJ$sp();
public scala.Function1 tupled$mcZDJ$sp();
public scala.Function1 tupled$mcIDJ$sp();
public scala.Function1 tupled$mcFDJ$sp();
public scala.Function1 tupled$mcJDJ$sp();
public scala.Function1 tupled$mcDDJ$sp();
public scala.Function1 tupled$mcVDD$sp();
public scala.Function1 tupled$mcZDD$sp();
public scala.Function1 tupled$mcIDD$sp();
public scala.Function1 tupled$mcFDD$sp();
public scala.Function1 tupled$mcJDD$sp();
public scala.Function1 tupled$mcDDD$sp();
public java.lang.Object apply(java.lang.Object, java.lang.Object);
public Bippy();

--
Paul Phillips      | Eschew mastication.
Apatheist          |
Empiricist         |
i pull his palp!   |----------* http://www.improving.org/paulp/ *----------

On Sun, Oct 24, 2010 at 07:29:36PM +0200, martin odersky wrote:
> Yeah, that's pretty much a worst case scenario. Iulian has some data
> how much the scala-library.jar and scala-compiler.jar grew due to
> specialization. I recall it was overall reasonable, but he should
> comment with the details. If we can improve something, then by all
> means we should.

I'm not thinking so much of the standard distribution in isolation, but
the size of the tax being imposed on users of Function1 and any other
specialized traits. Right now if you directly use it as a trait you win
33K. And people want to specialize more types. Depending on how code
size sensitive the usage, one might reasonably be tempted to create
implicit conversions to Function1 to avoid mixing it in, this of course
bringing its own problems.

(I hear about code size all the time from android programmers, if we're
looking for a concrete example where it matters.)

Whether that one is a big problem or not (and for sure it would be
without AbstractFunctionN) it can only become more problematic as we
introduce more specialization: adding a single method to a single trait
results in (# of specialized combinations * # of classes mixing in)
forwarders. It starts to undermine the utility of traits.

On Sun, Oct 24, 2010 at 07:29:36PM +0200, martin odersky wrote:
> Yeah, that's pretty much a worst case scenario. Iulian has some data
> how much the scala-library.jar and scala-compiler.jar grew due to
> specialization. I recall it was overall reasonable, but he should
> comment with the details. If we can improve something, then by all
> means we should.

I'm not thinking so much of the standard distribution in isolation, but
the size of the tax being imposed on users of Function1 and any other
specialized traits.  Right now if you directly use it as a trait you win
33K.  And people want to specialize more types.  Depending on how code
size sensitive the usage, one might reasonably be tempted to create
implicit conversions to Function1 to avoid mixing it in, this of course
bringing its own problems.

(I hear about code size all the time from android programmers, if we're
looking for a concrete example where it matters.)

Whether that one is a big problem or not (and for sure it would be
without AbstractFunctionN) it can only become more problematic as we
introduce more specialization: adding a single method to a single trait
results in (# of specialized combinations * # of classes mixing in)
forwarders.  It starts to undermine the utility of traits.

On Sun, Oct 24, 2010 at 11:23:55PM +0200, martin odersky wrote:
> Well, yes, it's a tradeoff. But I have not seen an alternative yet,
> except, not specialize. You seem to imply that you might have one?

For starters we could offer some control to the classes mixing in
traits, to opt out of receiving specialized forms. General solutions
aren't something I've thought about very hard but I'd be happy to put
some brain cells on the case.

In my view there are a lot of problems in the programming in general and
even more so in scala specifically which come up only in a minority of
circumstances, but can be big problems when they do. If there's some
straightforward way to mitigate such problems as they arise, they are
minor problems. But if there isn't, then not only are they big problems
when they arise, but they have an impact even when they don't, because
people start having to program defensively against the day they do even
if it never comes.

Which is all to explain why I see monsters under the bed a little sooner
than most. I don't like digging monster-moats.

On Sun, Oct 24, 2010 at 11:23:55PM +0200, martin odersky wrote:
> Well, yes, it's a tradeoff. But I have not seen an alternative yet,
> except, not specialize. You seem to imply that you might have one?

For starters we could offer some control to the classes mixing in
traits, to opt out of receiving specialized forms.  

What would be the implementation of e.g. TraversableLike.collect in terms of applyOrElse or Function1 extended with missingCase?

Another option would be to replace the auto-generated isDefinedAt and apply methods by a single auto-generated method like this:

def applyPartial(x: A, doApply: Boolean, target: Ref[B]): Boolean

If doApply is false, the behavior would be equivalent to isDefinedAt:

def isDefinedAt(x: A) = applyPartial(false, null)

If doApply is true and the match succeeds it would actually evaluate the function and write the result to the ref cell passed as `target`. The return value would always be whether the match succeeded.

def apply(x: A) = { val r = new Ref[B]; if (applyPartial(x, true, r)) r.get else throw new MatchError }

This means no duplicate pattern matching code and fast-path use of applyPartial in loops or for actors by reusing the ref cell:

def collect[B, That](pf: PartialFunction[A, B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
val b = bf(repr)
val r = new Ref[B]
for (x <- this) if (pf.applyPartial(x,true,r)) b += r.get
b.result
}

One argument for ref cells over functions as success or failure continuations is that the target.set call sites within the partial function code are monomorphic. The doApply parameter could be replaced by using target ne null as trigger condition.

- Tiark

On Oct 24, 2010, at 6:08 PM, Paul Phillips wrote:

> I'm with the family today so I don't know if I can properly respond
> until tomorrow. And I'm glad to see there is no shortage of opinions.
> I also think this is very important to get as right as we can.
>
> On Sun, Oct 24, 2010 at 05:31:15PM +0200, martin odersky wrote:
>> 3. Change the rules so that in a pattern matching expression
>>
>> x match { case P1 => ... case Pn => ... }
>>
>> that was the body of a function, a selector that was not matched by
>> any of the patterns invoked missingCase(x) instead of immediately
>> throwing a MatchError(x).
>
> My initial intuition is that this is a winner. Structural things I
> think should be considered include a) deprecating PartialFunction rather
> than trying too hard to keep it relevant and b) considering a new common
> supertype for F1 / PF / possible-third-creation. And we should be
> taking an up to date look at things like the interactions of mixin
> composition and specialization, such as this one:
>
> // a.scala
> class Bippy[T1, T2, R] extends Function2[T1, T2, R] {
> def apply(x1: T1, x2: T2): R = error("")
> }
>
> // 33K!
> % ls -l Bippy.class
> -rw-r--r-- 1 paulp wheel 32885 Oct 24 08:55 Bippy.class
>
> The conditions under which certain things were conceived and showed
> little cost have changed. AbstractFunctionN works around this somewhat
> under the current regime, but if we start introducing new Function
> classes then that approach will break down quickly under the steely
> glare of combinatorial reality.
>
> Side note: interesting that curry exacts the same cost as curried even
> though the entire implementation is:
>
> @deprecated("Use 'curried' instead")
> def curry = curried
>
> % jp Bippy | grep public
> public class Bippy extends java.lang.Object implements scala.Function2,scala.ScalaObject
> public void apply$mcVII$sp(int, int);
> public boolean apply$mcZII$sp(int, int);
> public int apply$mcIII$sp(int, int);
> public float apply$mcFII$sp(int, int);
> public long apply$mcJII$sp(int, int);
> public double apply$mcDII$sp(int, int);
> public void apply$mcVIJ$sp(int, long);
> public boolean apply$mcZIJ$sp(int, long);
> public int apply$mcIIJ$sp(int, long);
> public float apply$mcFIJ$sp(int, long);
> public long apply$mcJIJ$sp(int, long);
> public double apply$mcDIJ$sp(int, long);
> public void apply$mcVID$sp(int, double);
> public boolean apply$mcZID$sp(int, double);
> public int apply$mcIID$sp(int, double);
> public float apply$mcFID$sp(int, double);
> public long apply$mcJID$sp(int, double);
> public double apply$mcDID$sp(int, double);
> public void apply$mcVJI$sp(long, int);
> public boolean apply$mcZJI$sp(long, int);
> public int apply$mcIJI$sp(long, int);
> public float apply$mcFJI$sp(long, int);
> public long apply$mcJJI$sp(long, int);
> public double apply$mcDJI$sp(long, int);
> public void apply$mcVJJ$sp(long, long);
> public boolean apply$mcZJJ$sp(long, long);
> public int apply$mcIJJ$sp(long, long);
> public float apply$mcFJJ$sp(long, long);
> public long apply$mcJJJ$sp(long, long);
> public double apply$mcDJJ$sp(long, long);
> public void apply$mcVJD$sp(long, double);
> public boolean apply$mcZJD$sp(long, double);
> public int apply$mcIJD$sp(long, double);
> public float apply$mcFJD$sp(long, double);
> public long apply$mcJJD$sp(long, double);
> public double apply$mcDJD$sp(long, double);
> public void apply$mcVDI$sp(double, int);
> public boolean apply$mcZDI$sp(double, int);
> public int apply$mcIDI$sp(double, int);
> public float apply$mcFDI$sp(double, int);
> public long apply$mcJDI$sp(double, int);
> public double apply$mcDDI$sp(double, int);
> public void apply$mcVDJ$sp(double, long);
> public boolean apply$mcZDJ$sp(double, long);
> public int apply$mcIDJ$sp(double, long);
> public float apply$mcFDJ$sp(double, long);
> public long apply$mcJDJ$sp(double, long);
> public double apply$mcDDJ$sp(double, long);
> public void apply$mcVDD$sp(double, double);
> public boolean apply$mcZDD$sp(double, double);
> public int apply$mcIDD$sp(double, double);
> public float apply$mcFDD$sp(double, double);
> public long apply$mcJDD$sp(double, double);
> public double apply$mcDDD$sp(double, double);
> public java.lang.String toString();
> public scala.Function1 curried();
> public scala.Function1 curried$mcVII$sp();
> public scala.Function1 curried$mcZII$sp();
> public scala.Function1 curried$mcIII$sp();
> public scala.Function1 curried$mcFII$sp();
> public scala.Function1 curried$mcJII$sp();
> public scala.Function1 curried$mcDII$sp();
> public scala.Function1 curried$mcVIJ$sp();
> public scala.Function1 curried$mcZIJ$sp();
> public scala.Function1 curried$mcIIJ$sp();
> public scala.Function1 curried$mcFIJ$sp();
> public scala.Function1 curried$mcJIJ$sp();
> public scala.Function1 curried$mcDIJ$sp();
> public scala.Function1 curried$mcVID$sp();
> public scala.Function1 curried$mcZID$sp();
> public scala.Function1 curried$mcIID$sp();
> public scala.Function1 curried$mcFID$sp();
> public scala.Function1 curried$mcJID$sp();
> public scala.Function1 curried$mcDID$sp();
> public scala.Function1 curried$mcVJI$sp();
> public scala.Function1 curried$mcZJI$sp();
> public scala.Function1 curried$mcIJI$sp();
> public scala.Function1 curried$mcFJI$sp();
> public scala.Function1 curried$mcJJI$sp();
> public scala.Function1 curried$mcDJI$sp();
> public scala.Function1 curried$mcVJJ$sp();
> public scala.Function1 curried$mcZJJ$sp();
> public scala.Function1 curried$mcIJJ$sp();
> public scala.Function1 curried$mcFJJ$sp();
> public scala.Function1 curried$mcJJJ$sp();
> public scala.Function1 curried$mcDJJ$sp();
> public scala.Function1 curried$mcVJD$sp();
> public scala.Function1 curried$mcZJD$sp();
> public scala.Function1 curried$mcIJD$sp();
> public scala.Function1 curried$mcFJD$sp();
> public scala.Function1 curried$mcJJD$sp();
> public scala.Function1 curried$mcDJD$sp();
> public scala.Function1 curried$mcVDI$sp();
> public scala.Function1 curried$mcZDI$sp();
> public scala.Function1 curried$mcIDI$sp();
> public scala.Function1 curried$mcFDI$sp();
> public scala.Function1 curried$mcJDI$sp();
> public scala.Function1 curried$mcDDI$sp();
> public scala.Function1 curried$mcVDJ$sp();
> public scala.Function1 curried$mcZDJ$sp();
> public scala.Function1 curried$mcIDJ$sp();
> public scala.Function1 curried$mcFDJ$sp();
> public scala.Function1 curried$mcJDJ$sp();
> public scala.Function1 curried$mcDDJ$sp();
> public scala.Function1 curried$mcVDD$sp();
> public scala.Function1 curried$mcZDD$sp();
> public scala.Function1 curried$mcIDD$sp();
> public scala.Function1 curried$mcFDD$sp();
> public scala.Function1 curried$mcJDD$sp();
> public scala.Function1 curried$mcDDD$sp();
> public scala.Function1 curry();
> public scala.Function1 curry$mcVII$sp();
> public scala.Function1 curry$mcZII$sp();
> public scala.Function1 curry$mcIII$sp();
> public scala.Function1 curry$mcFII$sp();
> public scala.Function1 curry$mcJII$sp();
> public scala.Function1 curry$mcDII$sp();
> public scala.Function1 curry$mcVIJ$sp();
> public scala.Function1 curry$mcZIJ$sp();
> public scala.Function1 curry$mcIIJ$sp();
> public scala.Function1 curry$mcFIJ$sp();
> public scala.Function1 curry$mcJIJ$sp();
> public scala.Function1 curry$mcDIJ$sp();
> public scala.Function1 curry$mcVID$sp();
> public scala.Function1 curry$mcZID$sp();
> public scala.Function1 curry$mcIID$sp();
> public scala.Function1 curry$mcFID$sp();
> public scala.Function1 curry$mcJID$sp();
> public scala.Function1 curry$mcDID$sp();
> public scala.Function1 curry$mcVJI$sp();
> public scala.Function1 curry$mcZJI$sp();
> public scala.Function1 curry$mcIJI$sp();
> public scala.Function1 curry$mcFJI$sp();
> public scala.Function1 curry$mcJJI$sp();
> public scala.Function1 curry$mcDJI$sp();
> public scala.Function1 curry$mcVJJ$sp();
> public scala.Function1 curry$mcZJJ$sp();
> public scala.Function1 curry$mcIJJ$sp();
> public scala.Function1 curry$mcFJJ$sp();
> public scala.Function1 curry$mcJJJ$sp();
> public scala.Function1 curry$mcDJJ$sp();
> public scala.Function1 curry$mcVJD$sp();
> public scala.Function1 curry$mcZJD$sp();
> public scala.Function1 curry$mcIJD$sp();
> public scala.Function1 curry$mcFJD$sp();
> public scala.Function1 curry$mcJJD$sp();
> public scala.Function1 curry$mcDJD$sp();
> public scala.Function1 curry$mcVDI$sp();
> public scala.Function1 curry$mcZDI$sp();
> public scala.Function1 curry$mcIDI$sp();
> public scala.Function1 curry$mcFDI$sp();
> public scala.Function1 curry$mcJDI$sp();
> public scala.Function1 curry$mcDDI$sp();
> public scala.Function1 curry$mcVDJ$sp();
> public scala.Function1 curry$mcZDJ$sp();
> public scala.Function1 curry$mcIDJ$sp();
> public scala.Function1 curry$mcFDJ$sp();
> public scala.Function1 curry$mcJDJ$sp();
> public scala.Function1 curry$mcDDJ$sp();
> public scala.Function1 curry$mcVDD$sp();
> public scala.Function1 curry$mcZDD$sp();
> public scala.Function1 curry$mcIDD$sp();
> public scala.Function1 curry$mcFDD$sp();
> public scala.Function1 curry$mcJDD$sp();
> public scala.Function1 curry$mcDDD$sp();
> public scala.Function1 tupled();
> public scala.Function1 tupled$mcVII$sp();
> public scala.Function1 tupled$mcZII$sp();
> public scala.Function1 tupled$mcIII$sp();
> public scala.Function1 tupled$mcFII$sp();
> public scala.Function1 tupled$mcJII$sp();
> public scala.Function1 tupled$mcDII$sp();
> public scala.Function1 tupled$mcVIJ$sp();
> public scala.Function1 tupled$mcZIJ$sp();
> public scala.Function1 tupled$mcIIJ$sp();
> public scala.Function1 tupled$mcFIJ$sp();
> public scala.Function1 tupled$mcJIJ$sp();
> public scala.Function1 tupled$mcDIJ$sp();
> public scala.Function1 tupled$mcVID$sp();
> public scala.Function1 tupled$mcZID$sp();
> public scala.Function1 tupled$mcIID$sp();
> public scala.Function1 tupled$mcFID$sp();
> public scala.Function1 tupled$mcJID$sp();
> public scala.Function1 tupled$mcDID$sp();
> public scala.Function1 tupled$mcVJI$sp();
> public scala.Function1 tupled$mcZJI$sp();
> public scala.Function1 tupled$mcIJI$sp();
> public scala.Function1 tupled$mcFJI$sp();
> public scala.Function1 tupled$mcJJI$sp();
> public scala.Function1 tupled$mcDJI$sp();
> public scala.Function1 tupled$mcVJJ$sp();
> public scala.Function1 tupled$mcZJJ$sp();
> public scala.Function1 tupled$mcIJJ$sp();
> public scala.Function1 tupled$mcFJJ$sp();
> public scala.Function1 tupled$mcJJJ$sp();
> public scala.Function1 tupled$mcDJJ$sp();
> public scala.Function1 tupled$mcVJD$sp();
> public scala.Function1 tupled$mcZJD$sp();
> public scala.Function1 tupled$mcIJD$sp();
> public scala.Function1 tupled$mcFJD$sp();
> public scala.Function1 tupled$mcJJD$sp();
> public scala.Function1 tupled$mcDJD$sp();
> public scala.Function1 tupled$mcVDI$sp();
> public scala.Function1 tupled$mcZDI$sp();
> public scala.Function1 tupled$mcIDI$sp();
> public scala.Function1 tupled$mcFDI$sp();
> public scala.Function1 tupled$mcJDI$sp();
> public scala.Function1 tupled$mcDDI$sp();
> public scala.Function1 tupled$mcVDJ$sp();
> public scala.Function1 tupled$mcZDJ$sp();
> public scala.Function1 tupled$mcIDJ$sp();
> public scala.Function1 tupled$mcFDJ$sp();
> public scala.Function1 tupled$mcJDJ$sp();
> public scala.Function1 tupled$mcDDJ$sp();
> public scala.Function1 tupled$mcVDD$sp();
> public scala.Function1 tupled$mcZDD$sp();
> public scala.Function1 tupled$mcIDD$sp();
> public scala.Function1 tupled$mcFDD$sp();
> public scala.Function1 tupled$mcJDD$sp();
> public scala.Function1 tupled$mcDDD$sp();
> public java.lang.Object apply(java.lang.Object, java.lang.Object);
> public Bippy();
>

What would be the implementation of e.g. TraversableLike.collect in terms of applyOrElse or Function1 extended with missingCase?

Another option would be to replace the auto-generated isDefinedAt and apply methods by a single auto-generated method like this:
 

       def applyPartial(x: A, doApply: Boolean, target: Ref[B]): Boolean

On Sunday, October 24, 2010 11:31:15 am martin odersky wrote:
> ...
> 2. Change the rules so that _any_ subclass of Function can be implemented
> by a closure { x => ... }, as long as the class contains a single abstract
> method named `apply'.

For reasons unrelated to the original issue, this would be interesting to me
if it could be generalized a bit. Specifically, I'd like to be able to write a
function literal for:

trait ~>[A[_], B[_]] {
def apply[T](t: A[T]): B[T]
}

For example, I currently have to write:
new (Option ~> List) {
def apply[T](o: Option[T]) = o.toList
}

but I'd like to do the more readable:

val toList: Option ~> List = _.toList

Or maybe with an imaginary anonymous type function syntax:

val toList = [T] (_: Option[T]).toList

I realize this might not be considered right now and probably requires a sid,
but I'll put it out there anyway.

-Mark

On Sunday, October 24, 2010 11:31:15 am martin odersky wrote:
> ...
> 2. Change the rules so that _any_ subclass of Function can be implemented
> by a closure { x => ... }, as long as the class contains a single abstract
> method named `apply'.

For reasons unrelated to the original issue, this would be interesting to me
if it could be generalized a bit.  Specifically, I'd like to be able to write a
function literal for:

trait ~>[A[_], B[_]] {
 def apply[T](t: A[T]): B[T]
}

For example, I currently have to write:
 new (Option ~> List) {
   def apply[T](o: Option[T]) = o.toList
 }

but I'd like to do the more readable:

 val toList: Option ~> List = _.toList

Or maybe with an imaginary anonymous type function syntax:

 val toList = [T] (_: Option[T]).toList

I realize this might not be considered right now and probably requires a sid,
but I'll put it out there anyway.

-Mark

On Mon, Oct 25, 2010 at 2:38 AM, Tiark Rompf <tiark [dot] rompf [at] epfl [dot] ch> wrote:

What would be the implementation of e.g. TraversableLike.collect in terms of applyOrElse or Function1 extended with missingCase?

It would need to be implemented with andThen, which itself uses a (preallocated) exception. That's the price we pay for not haviong isDefinedAt.

Another option would be to replace the auto-generated isDefinedAt and apply methods by a single auto-generated method like this:
 

       def applyPartial(x: A, doApply: Boolean, target: Ref[B]): Boolean

I am still worried about the allocation overhead, though.

On Oct 25, 2010, at 8:40 AM, martin odersky wrote:

On Mon, Oct 25, 2010 at 2:38 AM, Tiark Rompf <tiark [dot] rompf [at] epfl [dot] ch> wrote:

What would be the implementation of e.g. TraversableLike.collect in terms of applyOrElse or Function1 extended with missingCase?

It would need to be implemented with andThen, which itself uses a (preallocated) exception. That's the price we pay for not haviong isDefinedAt.

Another option would be to replace the auto-generated isDefinedAt and apply methods by a single auto-generated method like this:
 

       def applyPartial(x: A, doApply: Boolean, target: Ref[B]): Boolean

I am still worried about the allocation overhead, though.

That is a very valid concern, both for creating closures for applyOrElse or using ref cells. However it is specific to isolated apply calls. On the other hand, things like composing partial functions using orElse would get a lot faster, as well as TraversableLike.collect.

- Tiark

What about using switch with magic numbers for indexing cases? Ie.

def getBranch(x: A): Int = matching code
def isDefinedAt(x: A): Boolean = getBranch(x) != 0
def applyBranch(x:A, branch: Int) = applying code using switch construct
def apply(x: A) = applyBranch(x, getBranch(x))

2010/10/24 martin odersky :
> Hi Paul,
>
> I have been thinking of using PartialFunctions for some code that
> essentially does high-performance state machines. PartialFunctions are
> generally very nice, but have two efficiency problems in that respect.
> First, we need to generate the pattern matching code twice, once in the
> apply and then again in the isDefinedAt. Second, we also need to execute the
> code twice, first to test whether the function is applicable, and then to
> actually apply it.
>
> Can we do without the double duplication? We could if we had a slightly
> different type, call it FuntionWithDefault:
>
> FunctionWithDefault would have only one abstract method, applyOrElse:
>
>   trait FunctionWithDefault[A, +B] extends (A => B) {
>     def applyOrElse[B1 >: B](x: A, default: A => B1): B1
>
> The method takes a default function, which is applied in case of a failed
> match (note that this means that FunctionWithDefault needs to be non-variant
> in its domain type parameter). The apply function can then be implemented in
> terms of applyOrElse:
>
>     def apply(x: A): B = applyOrElse(x, throw new MatchError(x))
>
> So only one copy of the pattern match is needed. The isDefinedAt function
> cannot be defined using applyOrElse. But then it seems that
> almost everything we do with PartialFunctions does not need isDefinedAt, and
> can do with just applyOrElse. As an argument in favor I have
> implemented all methods in PartialFunction with equivalent methods in
> FunctionWithDefault. It works, even though we need a somewhat ugly (private)
> exception for andThen and lift.
>
> Aside: We could change the contract and have a success continuation as well
> as an error continuation in applyOrElse. This would make
> andThen and orElse nicer and slightly more efficient (throwing and catching
> the exception is reputedly (**) about as costly as three virtual method
> calls). But it would make the code to be generated more diificult (have to
> thread the success comntinuation in everyhwere and also slower. So I am not
> sure it's worth it.
>
> Your thoughts?
>
> Cheers
>
>  -- Martin
>
> (**) That's what John Rose told me.
>
> P.S. Here's the code of FunctionWithDefault:
>
> package scala
>
> /** A function with default of type `FunctionWithDefault[A, B]` is a
>  *  unary function where the domain does not necessarily include all values
> of type
>  *  `A`. The function `isDefinedAt` allows to
>  *  test dynamically if a value is in the domain of the function.
>  *
>  *  @author  Martin Odersky
>  *  @version 1.0, 16/07/2003
>  */
> trait FunctionWithDefault[A, +B] extends (A => B) {
>
>   def applyOrElse[B1 >: B](x: A, default: A => B1): B1
>
>   def apply(x: A): B = applyOrElse(x, throw new MatchError(x))
>
>   /** Composes this function with default with a fallback function with
> default which gets applied where this function with default
>    *  is not defined.
>    *
>    *  @param   that    the fallback function
>    *  @tparam  A1      the argument type of the fallback function
>    *  @tparam  B1      the result type of the fallback function
>    *  @return  a function with default which has as domain the union of the
> domains
>    *           of this function with default and `that`. The resulting
> function with default
>    *           takes `x` to `this(x)` where `this` is defined, and to
> `that(x)` where it is not.
>    */
>   def orElse[B1 >: B](that: FunctionWithDefault[A, B1]) :
> FunctionWithDefault[A, B1] =
>     new FunctionWithDefault[A, B1] {
>     def applyOrElse[B2 >: B1](x: A, default: A => B2): B2 =
>       FunctionWithDefault.this.applyOrElse(x, that)
>   }
>
>   /**  Composes this function with default with a transformation function
> that gets applied
>    *   to results of this function with default.
>    *   @param  k  the transformation function
>    *   @tparam C  the result type of the transformation function.
>    *   @return a function with default with the same domain as this function
> with default, which maps
>    *           arguments `x` to `k(this(x))`.
>    */
>   override def andThen[C](k: B => C) : FunctionWithDefault[A, C] = new
> FunctionWithDefault[A, C] {
>     def applyOrElse[C1 >: C](x: A, default: A => C1): C1 =
>       try {
>         k(FunctionWithDefault.this.applyOrElse(x, throw
> FunctionWithDefault.DoDefault))
>       } catch {
>         case ex: FunctionWithDefault.DefaultException => default(x)
>       }
>   }
>
>   /** Turns this function with default into an plain function returning an
> `Option` result.
>    *  @see     Function1#unlift
>    *  @return  a function that takes an argument `x` to `Some(this(x))` if
> `this`
>    *           is defined for `x`, and to `None` otherwise.
>    */
>   def lift: A => Option[B] = new (A => Option[B]) {
>     def apply(x: A): Option[B] =
>       try {
>         Some(FunctionWithDefault.this.applyOrElse(x, throw
> FunctionWithDefault.DoDefault))
>       } catch {
>         case ex: FunctionWithDefault.DefaultException => None
>       }
> /* needs adaptation in Function1
>     override def unlift[R1](implicit ev: Option[B] <:< Option[R1]):
> FunctionWithDefault[A, R1] =
>       FunctionWithDefault.this.asInstanceOf[FunctionWithDefault[A, R1]]
>       */
>   }
> }
>
> /** A few handy operations which leverage the extra bit of information
>  *  available in functions with default.  Examples:
>  *
>  *

>  *  import FunctionWithDefault._
>  *
>  *  def strangeConditional(other: Any): Boolean = cond(other) {
>  *    case x: String if x == "abc" || x == "def"  => true
>  *    case x: Int => true
>  *  }
>  *  def onlyInt(v: Any): Option[Int] = condOpt(v) { case x: Int => x }
>  * 

>  *
>  *  @author  Paul Phillips
>  *  @since   2.8
>  */
> object FunctionWithDefault
> {
>   /** Creates a Boolean test based on a value and a function with default.
>    *  It behaves like a 'match' statement with an implied 'case _ => false'
>    *  following the supplied cases.
>    *
>    *  @param  x   the value to test
>    *  @param  pf  the function with default
>    *  @return true, iff `x` is in the domain of `pf` and `pf(x) == true`.
>    */
>   def cond[T](x: T)(pf: FunctionWithDefault[T, Boolean]): Boolean =
>     pf.applyOrElse(x, _ => false)
>
>   /** Transforms a FunctionWithDefault[T, U] `pf' into Function1[T,
> Option[U]] `f'
>    *  whose result is Some(x) if the argument is in pf's domain and None
> otherwise,
>    *  and applies it to the value `x'.  In effect, it is a 'match' statement
>    *  which wraps all case results in Some(_) and adds 'case _ => None' to
> the end.
>    *
>    *  @param  x     the value to test
>    *  @param  pf    the FunctionWithDefault[T, U]
>    *  @return `Some(pf(x))` if `pf isDefinedAt x`, `None` otherwise.
>    */
>   def condOpt[T,U](x: T)(pf: FunctionWithDefault[T, U]): Option[U] =
>     pf.lift(x)
>
>   private class DefaultException extends Exception
>   private val DoDefault = new DefaultException
> }
>
>
>
>
>
>
>
>
>

On Sun, Oct 24, 2010 at 11:23:55PM +0200, martin odersky wrote:
> Well, yes, it's a tradeoff. But I have not seen an alternative yet,
> except, not specialize. You seem to imply that you might have one?

For starters we could offer some control to the classes mixing in
traits, to opt out of receiving specialized forms.  General solutions
aren't something I've thought about very hard but I'd be happy to put
some brain cells on the case.

In my view there are a lot of problems in the programming in general and
even more so in scala specifically which come up only in a minority of
circumstances, but can be big problems when they do.  If there's some
straightforward way to mitigate such problems as they arise, they are
minor problems.  But if there isn't, then not only are they big problems
when they arise, but they have an impact even when they don't, because
people start having to program defensively against the day they do even
if it never comes.

Which is all to explain why I see monsters under the bed a little sooner
than most.  I don't like digging monster-moats.

--
Paul Phillips      | Before a man speaks it is always safe to assume
In Theory          | that he is a fool.  After he speaks, it is seldom
Empiricist         | necessary to assume it.
i'll ship a pulp   |     -- H. L. Mencken

On Sunday, October 24, 2010 10:15:18 am martin odersky wrote:
> On Sun, Oct 24, 2010 at 3:49 PM, Jason Zaugg wrote:
> > While we're re-imagining partial functions, let me throw another one
> >
> > around:
> > http://gist.github.com/643539
> >
> > -jason
> >
> That seems to go very much in the same direction, and it's very elegant to
> boot! But it would be heavier weight, in the amount of closures generated
> (one per case it looks to me) and in the amount of indirections. I was
> after having a version of partial function with minimal performance
> penalties.

It would be a shame to rule out this approach without considering a version with a strict Option as the
result. A strict Option eliminates the one per case statement closure that comes with a lazy Option.
Attached is a demo implementation of the methods in FunctionWithDefault. You could manually inline the
getOrElse/orElse calls to avoid the extra closure.

-Mark

>
> Btw, I worked it out now how to do FunctionWithDefault contravariantly in
> its argument. Result is attached.
>
> Cheers
>

On Mon, Nov 01, 2010 at 01:52:20PM -0400, Mark Harrah wrote:
> It would be a shame to rule out this approach without considering a
> version with a strict Option as the result. A strict Option
> eliminates the one per case statement closure that comes with a lazy
> Option. Attached is a demo implementation of the methods in
> FunctionWithDefault. You could manually inline the getOrElse/orElse
> calls to avoid the extra closure.

...but you can't avoid allocating the option on every iteration in a
loop, right? I think the argument for avoiding allocation trumps the
argument for option elegance. (That is approximately the summary of what
I figured out from dinner with tiark and adriaan.)

On Mon, Nov 01, 2010 at 01:52:20PM -0400, Mark Harrah wrote:
> It would be a shame to rule out this approach without considering a
> version with a strict Option as the result.  A strict Option
> eliminates the one per case statement closure that comes with a lazy
> Option.  Attached is a demo implementation of the methods in
> FunctionWithDefault.  You could manually inline the getOrElse/orElse
> calls to avoid the extra closure.

...but you can't avoid allocating the option on every iteration in a
loop, right? I think the argument for avoiding allocation trumps the
argument for option elegance. (That is approximately the summary of what
I figured out from dinner with tiark and adriaan.)

On Monday, November 01, 2010 04:13:18 pm martin odersky wrote:
> On Mon, Nov 1, 2010 at 7:50 PM, Paul Phillips wrote:
> > On Mon, Nov 01, 2010 at 01:52:20PM -0400, Mark Harrah wrote:
> > > It would be a shame to rule out this approach without considering a
> > > version with a strict Option as the result. A strict Option
> > > eliminates the one per case statement closure that comes with a lazy
> > > Option. Attached is a demo implementation of the methods in
> > > FunctionWithDefault. You could manually inline the getOrElse/orElse
> > > calls to avoid the extra closure.
> >
> > ...but you can't avoid allocating the option on every iteration in a
> > loop, right? I think the argument for avoiding allocation trumps the
> > argument for option elegance. (That is approximately the summary of what
> > I figured out from dinner with tiark and adriaan.)
> >
> > At least in my original scenario, yes. I am looking for somethig that's
>
> _faster_ than the usual isDefinedAt/apply combination of partial
> functions. Starting by throwing extra allocations in looks like the wrong
> direction to this question (it might well be a good answer for a different
> question, though).

When I first looked at FunctionWithDefault, I thought I saw allocations for
several common uses, such as apply or applyOrElse for a composed
FunctionWithDefault. On closer inspection, I see that these methods don't
work as written (Nothing <: A => B).

Also, it doesn't look like orElse works right when chained (a orElse b orElse
c). Passing a FunctionWithDefault as a Function1 for 'default' means its
apply method gets called and a MatchError is thrown for the default case
instead of DoDefault.

-Mark

> Cheers
>

On Monday, November 01, 2010 04:13:18 pm martin odersky wrote:
> On Mon, Nov 1, 2010 at 7:50 PM, Paul Phillips <paulp [at] improving [dot] org> wrote:
> > On Mon, Nov 01, 2010 at 01:52:20PM -0400, Mark Harrah wrote:
> > > It would be a shame to rule out this approach without considering a
> > > version with a strict Option as the result.  A strict Option
> > > eliminates the one per case statement closure that comes with a lazy
> > > Option.  Attached is a demo implementation of the methods in
> > > FunctionWithDefault.  You could manually inline the getOrElse/orElse
> > > calls to avoid the extra closure.
> >
> > ...but you can't avoid allocating the option on every iteration in a
> > loop, right? I think the argument for avoiding allocation trumps the
> > argument for option elegance. (That is approximately the summary of what
> > I figured out from dinner with tiark and adriaan.)
> >
> > At least in my original scenario, yes. I am looking for somethig that's
>
> _faster_ than the usual  isDefinedAt/apply combination of partial
> functions. Starting by throwing extra allocations in looks like the wrong
> direction to this question (it might well be a good answer for a different
> question, though).

When I first looked at FunctionWithDefault, I thought I saw allocations for
several common uses, such as apply or applyOrElse for a composed
FunctionWithDefault.  On closer inspection, I see that these methods don't
work as written (Nothing <: A => B).

Also, it doesn't look like orElse works right when chained (a orElse b orElse
c).  Passing a FunctionWithDefault as a Function1 for 'default' means its
apply method gets called and a MatchError is thrown for the default case
instead of DoDefault.

-Mark

> Cheers
>
>  -- Martin

On Tuesday, November 02, 2010 01:02:49 pm martin odersky wrote:
> Hi Mark,
>
> Thanks for your remarks. I have to review the code with them in mind. In any
> case I think the current frontrunner is the idea to have a "missingCase"
> method in Function1 that can be overridden by applications. Then it becomes
> a separate question whether and how we implement andThen/orElse for such
> functions.

Thanks for the reply, Martin. I didn't realize the second alternative was favored already. Attached is an improved FunctionWithDefault anyway. It should work correctly and not allocate new thunks on calls to apply/applyOrElse.

> Here are the rules again:
>
> 1. Define Function1 like this:
>
> class Function1[-A, +B] {
> def apply(x: A): B
> def missingCase(x: A): B = throw new MatchError
> ...
> }
>
> 2. Change the rules so that _any_ subclass of Function can be implemented by
> a closure { x => ... }, as long as the class contains a single abstract
> method named `apply'.

Is there a reason it has to be a subclass of Function?

> 3. Change the rules so that in a pattern matching expression
>
> x match { case P1 => ... case Pn => ... }
>
> that was the body of a function, a selector that was not matched by any of
> the patterns invoked missingCase(x) instead of immediately throwing a
> MatchError(x).
>
> This would let you get the effective functionality of applyOrElse by
> subclassing Function1.

What is the advantage to this approach over FunctionWithDefault? It looks straightforward to provide Function1+missingCase given a FunctionWithDefault, but not the other way around.

-Mark

> Cheers
>

On Tuesday, November 02, 2010 01:02:49 pm martin odersky wrote:
> Hi Mark,
>
> Thanks for your remarks. I have to review the code with them in mind. In any
> case I think the current frontrunner is the idea to have a "missingCase"
> method in Function1 that can be overridden by applications. Then it becomes
> a separate question whether and how we implement andThen/orElse for such
> functions.

Thanks for the reply, Martin.  I didn't realize the second alternative was favored already.  Attached is an improved FunctionWithDefault anyway.  It should work correctly and not allocate new thunks on calls to apply/applyOrElse.

> Here are the rules again:
>
> 1. Define Function1 like this:
>
> class Function1[-A, +B] {
>   def apply(x: A): B
>   def missingCase(x: A): B = throw new MatchError
>   ...
> }
>
> 2. Change the rules so that _any_ subclass of Function can be implemented by
> a closure { x => ... }, as long as the class contains a single abstract
> method named `apply'.

Is there a reason it has to be a subclass of Function?

> 3. Change the rules so that in a pattern matching expression
>
>   x match { case P1 => ... case Pn => ... }
>
> that was the body of a function, a selector that was not matched by any of
> the patterns invoked missingCase(x) instead of immediately throwing a
> MatchError(x).
>
> This would let you get the effective functionality of applyOrElse by
> subclassing Function1.

What is the advantage to this approach over FunctionWithDefault?  It looks straightforward to provide Function1+missingCase given a FunctionWithDefault, but not the other way around.

-Mark

> Cheers
>
>  -- Martin
>
>
> On Tue, Nov 2, 2010 at 3:49 PM, Mark Harrah <harrah [at] bu [dot] edu> wrote:
>
> > On Monday, November 01, 2010 04:13:18 pm martin odersky wrote:
> > > On Mon, Nov 1, 2010 at 7:50 PM, Paul Phillips <paulp [at] improving [dot] org>
> > wrote:
> > > > On Mon, Nov 01, 2010 at 01:52:20PM -0400, Mark Harrah wrote:
> > > > > It would be a shame to rule out this approach without considering a
> > > > > version with a strict Option as the result.  A strict Option
> > > > > eliminates the one per case statement closure that comes with a lazy
> > > > > Option.  Attached is a demo implementation of the methods in
> > > > > FunctionWithDefault.  You could manually inline the getOrElse/orElse
> > > > > calls to avoid the extra closure.
> > > >
> > > > ...but you can't avoid allocating the option on every iteration in a
> > > > loop, right? I think the argument for avoiding allocation trumps the
> > > > argument for option elegance. (That is approximately the summary of
> > what
> > > > I figured out from dinner with tiark and adriaan.)
> > > >
> > > > At least in my original scenario, yes. I am looking for somethig that's
> > >
> > > _faster_ than the usual  isDefinedAt/apply combination of partial
> > > functions. Starting by throwing extra allocations in looks like the wrong
> > > direction to this question (it might well be a good answer for a
> > different
> > > question, though).
> >
> > When I first looked at FunctionWithDefault, I thought I saw allocations for
> > several common uses, such as apply or applyOrElse for a composed
> > FunctionWithDefault.  On closer inspection, I see that these methods don't
> > work as written (Nothing <: A => B).
> >
> > Also, it doesn't look like orElse works right when chained (a orElse b
> > orElse
> > c).  Passing a FunctionWithDefault as a Function1 for 'default' means its
> > apply method gets called and a MatchError is thrown for the default case
> > instead of DoDefault.
> >
> > -Mark
> >
> > > Cheers
> > >
> > >  -- Martin
> >
>