Home
Reading
Searching
Subscribe
Sponsors
Statistics
Posting
Contact
Spam
Lists
Links
About
Hosting
Filtering
Features Download
Marketing
Archives
FAQ
Blog
 
Gmane
From: martin odersky <martin.odersky-p8DiymsW2f8 <at> public.gmane.org>
Subject: Rethinking PartialFunction
Newsgroups: gmane.comp.lang.scala.internals
Date: Sunday 24th October 2010 12:06:05 UTC (over 7 years ago)
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 }
 
CD: 3ms