Introduce `andThen` overload which combines two partial functions #7263

danslapman · 2018-09-25T18:39:52Z

Combined uses the fallbackOccurred trick to combine two partial funtions with domain of pf1 narrowed with domain of pf2

SethTisue · 2018-09-25T18:54:27Z

is this in reference to scala/bug#9968 ?

danslapman · 2018-09-25T19:01:05Z

Not really, I just needed it by myself. I widely use this andThen as an extension method at work, so I decided to contribute it to scala)

danslapman · 2018-09-25T19:21:57Z

Will also be glad to backport it to 2.12.x if there is a possibility to be merged to

SethTisue · 2018-09-25T19:35:38Z

we couldn't accept it for 2.12.x, because bincompat (https://docs.scala-lang.org/overviews/core/binary-compatibility-of-scala-releases.html)

xuwei-k · 2018-09-26T00:22:39Z

src/library/scala/PartialFunction.scala

+  /** Composite function produced by `PartialFunction#andThen` method
+    */
+  private class Combined[-A, B, +C] (pf: PartialFunction[A, B], k: PartialFunction[B, C]) extends PartialFunction[A, C] with Serializable {
+    def isDefinedAt(x: A) = pf.isDefinedAt(x) && k.isDefinedAt(pf(x))


Should we use checkFallback and fallbackOccurred? 🤔

scalaz/scalaz@030d4b9

Seems reasonable

lrytz · 2018-09-28T14:28:17Z

This looks good to me in principle, but it should come with tests cases. In particular we have to see how well overloading resolution behaves for the various possible arguments (selections of functions, partial functions, function literals, partial function literals).

danslapman · 2018-09-28T18:15:04Z

Added some test cases for partial function combinations.
For others:

totalFunction andThen partialFunction - will work as before, because there is no special overload in Function1 (and I don't think it is reasonable to add one)
partialFunction compose totalFunction - it's impossible to overload compose for this case

lrytz · 2018-09-28T20:36:25Z

Great, thanks for adding tests! I have to ask for more though :-) We should also test type inference. The following work in 2.13.0-M5:

scala> val pf: PartialFunction[Int, Int] = { case x if x > 10 => x + 1 }
pf: PartialFunction[Int,Int] = <function1>

scala> val pf2 = pf andThen (x => x + 1)
pf2: PartialFunction[Int,Int] = <function1>

scala> val pf3 = pf andThen { case x if x > 20 => x + 1 }
pf3: PartialFunction[Int,Int] = <function1>

(pf3 is misleading, because pf3.isDefinedAt(15) is true... this PR would fix that?)

Type inference needs to figure out the type of x in the definition of pf2 and pf3. In 2.12 this most likely not work if andThen is overloaded. There were a lot of improvements in this area in 2.13, so maybe everything works well - but we need to test it.

danslapman · 2018-09-28T21:02:39Z

@lrytz You cases work as expected
BTW it's great to see compiler now inferring types for things like pf andThen { case x if x > 20 => x + 1 } :)

lrytz · 2018-10-01T07:28:28Z

Thank you, glad that everything works out! Can we also test type inference for compose?

danslapman · 2018-10-02T06:48:25Z

Hmm, got errors for compose:

 /Users/danslapman/Projects/scala/test/junit/scala/PartialFunctionCompositionTests.scala:144: missing parameter type
[error]     val pf2 = pf compose (x => x + 1)
[error]                           ^
[error] /Users/danslapman/Projects/scala/test/junit/scala/PartialFunctionCompositionTests.scala:149: missing parameter type for expanded function
[error] The argument types of an anonymous function must be fully known. (SLS 8.5)
[error] Expected type was: ?
[error]     val pf3 = pf compose { case x if x > 20 => x + 1 }

Test is pretty identical:

val fb = (_: Int) => 42
    val pf: PartialFunction[Int, Int] = { case x if x > 10 => x + 1 }
    val pf2 = pf compose (x => x + 1)

    assertEquals(pf2.applyOrElse(11, fb), 13)
    assertFalse(pf2.isDefinedAt(10))

    val pf3 = pf compose { case x if x > 20 => x + 1 }
    assertEquals(pf3.applyOrElse(15, fb), 42)
    assertEquals(pf3.applyOrElse(21, fb), 23)
    assertFalse(pf3.isDefinedAt(15))
    assertTrue(pf3.isDefinedAt(21))

lrytz · 2018-10-03T13:48:42Z

@danslapman totally my bad, I'm sorry. Of course the compiler cannot infer the parameter type for compose, there's no constraint on the function's parameter type in compose[A](g: A => T1): A => R = .... Also for normal functions we get

scala> val f = (x: Int) => x
f: Int => Int = $$Lambda$1071/1578244276@12958360

scala> f compose (x => x + 1)
                  ^
       error: missing parameter type

scala> f compose { case x => x + 1 }
                 ^
       error: missing parameter type for expanded function
       The argument types of an anonymous function must be fully known. (SLS 8.5)
       Expected type was: ? => Int

So this PR LGTM!

lrytz · 2018-10-03T13:54:06Z

Asking for a review by @NthPortal and @Jasper-M who commented on the related ticket (scala/bug#9968).

Jasper-M · 2018-10-03T14:22:32Z

LGTM. Pretty cool that type inference can handle this now.

NthPortal

LGTM

I'm still a little bit concerned about the performance (see scala/bug#9968 (comment)) of having to apply the first pf in order to check if it's defined for the second -- thus a call to isDefinedAt followed by apply will evaluate the first function twice -- but I'm not sure what a good solution is. I don't think it should hold up this PR regardless, but I do think it's worth looking into.

src/library/scala/PartialFunction.scala

NthPortal · 2018-10-04T01:27:29Z

src/library/scala/PartialFunction.scala


+  /**
+    * Composes this partial function with other partial function that
+    * gets applied to results of this partial function.


Something about this description (as well as the one for compose seems confusing to me; I think it could use a clearer wording. I can't think of anything off the top of my head, but I will think on it.

src/library/scala/PartialFunction.scala

neontorrent · 2018-11-01T16:31:23Z

src/library/scala/PartialFunction.scala

+    */
+  private class Combined[-A, B, +C] (pf: PartialFunction[A, B], k: PartialFunction[B, C]) extends PartialFunction[A, C] with Serializable {
+    def isDefinedAt(x: A) = {
+      val b: B = pf.applyOrElse(x, checkFallback[B])


@NthPortal Maybe caching pf.applyOrElse into a lazy val class variable can achieve better performance?

Also since this method calls the pf.applyOrElse, in case that pf is impure (modifies external variable), this can mess up the external variable value.

For the best perfomance applyOrElse should be used

caching can be done outside isDefinedAt if it really needed, caching inside can lead to unexpected memory usage and other undesired effects

Memory and performance concerns aside, correct me if I am wrong, any side effect will be evaluated twice, which will result in undesired behavior.

If You need the results of combined function, call applyOrElse, both partial functions will be called at most once. It is impossible to check if k is defined on pf's result, so if pf is side-effectful You should avoid calling isDefinedAt. For me the most appropriate way is not to implement isDefinedAt for combined funcion, but PartialFunction trait forced to do this.

In the above snippet, c1 and c2 confusingly do different things

This PR makes andThen consistent in that way, that's why I think we should name this method andThen and nothing else.

caching the result of the first evaluation would prevent double evaluation in most cases
it's only one additional field - I'm not personally super concerned about memory usage

in fact it would lead to memoizing results into a mutable.Map, which can lead to significant memory consumption and, even, to OOM

any cashing assumes that function is pure

applyOrElse is existing and documented way to call PartialFunction effectively, and as I said earlier, PartialFunction provides no contract of non-evaluating body while checking if it is defined at some argument. I think there are no excuses to keep current inconsistent and confusing behaviour.

This PR makes andThen consistent in that way

I'm not understanding how this PR makes it consistent - my example is what would happen according to this PR. Unless the implementation of andThen(Function1) is changed to check for PartialFunction, the behavior depends on the static type of a function, rather than its actual type. At least to me, this is confusing and inconsistent.

what would happen according to this PR

That's wrong, c1.applyOrElse(2, 8) currently throws an exception, but would not with new andThen implementation: https://scastie.scala-lang.org/UFazJnXSSpyxAgCp8dDRPQ
The only aim of the PR was to make this thing consisten.

While caching would avoid executing the side effect twice, we're still in a weird situation where isDefinedAt of a combined PF executes parts of its side-effect. There's no way around this, isDefinedAt is part of the interface and needs to be implemented.

Caching the value can also be surprising because a call to apply (after isDefinedAt has been called somewhere) has no side-effect.

We have to pick one or the other evil, so it's a documentation issue. I think we should go ahead with the current design. The documentation should say that the resulting PF may apply the first PF and execute its side effect. (We could do an early return by checking pf.isDefinedAt first, and avoid evaluating pf in this case).

Then I think this PR is good to go.

@lrytz added notes on behavior of Combined.

Reconsidered if this is the best course of action, based on subsequent discussion

lrytz

Thanks, @danslapman, also for not giving up in 3 months :-)

NthPortal · 2018-12-19T05:58:51Z

I'm still not happy with how the behaviour depends on the statically known type of the argument to andThen, rather than its actual/runtime type.

Welcome to Scala 2.13.0-20181218-090557-f3c0b0f (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_191).
Type in expressions for evaluation. Or try :help.

scala> val f: PartialFunction[Int, Int] = { case x if x % 2 == 0 => x + 2 }
f: PartialFunction[Int,Int] = <function1>

scala> val g: PartialFunction[Int, Int] = { case x if x % 2 == 1 => x - 2 }
g: PartialFunction[Int,Int] = <function1>

scala> val c1 = f andThen g
c1: PartialFunction[Int,Int] = <function1>

scala> val c2 = f andThen (g: Int => Int)
c2: PartialFunction[Int,Int] = <function1>

scala> c1.applyOrElse(2, (_: Int) => 8)
res0: Int = 8

scala> c2.applyOrElse(2, (_: Int) => 8)
scala.MatchError: 4 (of class java.lang.Integer)
  at scala.PartialFunction$$anon$1.apply(PartialFunction.scala:308)
  at scala.PartialFunction$$anon$1.apply(PartialFunction.scala:306)
  at $anonfun$1.applyOrElse(<console>:1)
  at $anonfun$1.applyOrElse(<console>:1)
  at scala.runtime.AbstractPartialFunction$mcII$sp.apply$mcII$sp(AbstractPartialFunction.scala:38)
  at scala.runtime.AbstractPartialFunction$mcII$sp.apply(AbstractPartialFunction.scala:38)
  at scala.runtime.AbstractPartialFunction$mcII$sp.apply(AbstractPartialFunction.scala:30)
  at scala.PartialFunction$AndThen.applyOrElse(PartialFunction.scala:227)
  ... 29 elided

dwijnand · 2018-12-19T07:23:39Z

@NthPortal: #7552

needed in recent 2.13 nightlies because of the combination of scala/scala#7660 and scala/scala#7263

scala/scala#7263

SethTisue · 2021-07-06T16:03:39Z

reviewers here might like to weigh in on scala/bug#12426

kubudi · 2021-11-03T11:53:15Z

pls note that this breaks FSM implementation in akka(although it's deprecated)
akka/akka-core#30855

scala-jenkins added this to the 2.13.0-RC1 milestone Sep 25, 2018

SethTisue mentioned this pull request Sep 25, 2018

PartialFunction doesn't compose well scala/bug#9968

Closed

xuwei-k reviewed Sep 26, 2018

View reviewed changes

danslapman force-pushed the topic/combine-pf branch 2 times, most recently from 3087b3a to 0614541 Compare September 26, 2018 18:35

danslapman force-pushed the topic/combine-pf branch from 4bcac10 to bf1d9fd Compare September 28, 2018 18:13

NthPortal previously approved these changes Oct 4, 2018

View reviewed changes

neontorrent reviewed Nov 1, 2018

View reviewed changes

danslapman force-pushed the topic/combine-pf branch from 0c5b228 to e0702c3 Compare December 17, 2018 18:46

Introduce andThen / compose overloads to combine partial functions

5050915

lrytz force-pushed the topic/combine-pf branch from e0702c3 to 5050915 Compare December 18, 2018 08:13

lrytz approved these changes Dec 18, 2018

View reviewed changes

lrytz merged commit f3c0b0f into scala:2.13.x Dec 18, 2018

SethTisue added the release-notes worth highlighting in next release notes label Jan 2, 2019

SethTisue added a commit to scalacommunitybuild/scalaz that referenced this pull request Feb 26, 2019

eta expand explicitly in one place

a39c46a

needed in recent 2.13 nightlies because of the combination of scala/scala#7660 and scala/scala#7263

SethTisue mentioned this pull request Apr 11, 2019

[WIP] move to Scala 2.13.0-RC1 (drop -M5) typelevel/cats#2783

Closed

raquo added a commit to raquo/Waypoint that referenced this pull request Feb 23, 2021

Fix: Mitigate pf1.andThen(pf2) bug in Scala 2.12

162039f

scala/scala#7263

raquo added a commit to raquo/Waypoint that referenced this pull request Feb 26, 2021

Fix: Mitigate pf1.andThen(pf2) bug in Scala 2.12

b4c0ea4

scala/scala#7263

SethTisue mentioned this pull request Jun 4, 2021

PartialFunction's orElse and andThen aren't stack-safe and should be constant-time operations scala/bug#12385

Open

SethTisue mentioned this pull request Jul 6, 2021

PartialFunction$Combined.isDefinedAt throws an exception when the first function throws scala/bug#12426

Closed

danslapman deleted the topic/combine-pf branch July 7, 2021 07:06

kubudi mentioned this pull request Nov 3, 2021

FSM transform...using pattern double executes transform piece akka/akka-core#30855

Open

Introduce andThen overload which combines two partial functions #7263

Introduce andThen overload which combines two partial functions #7263

Uh oh!

Conversation

danslapman commented Sep 25, 2018

Uh oh!

SethTisue commented Sep 25, 2018

Uh oh!

danslapman commented Sep 25, 2018

Uh oh!

danslapman commented Sep 25, 2018

Uh oh!

SethTisue commented Sep 25, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

lrytz commented Sep 28, 2018

Uh oh!

danslapman commented Sep 28, 2018

Uh oh!

lrytz commented Sep 28, 2018

Uh oh!

danslapman commented Sep 28, 2018

Uh oh!

lrytz commented Oct 1, 2018

Uh oh!

danslapman commented Oct 2, 2018

Uh oh!

lrytz commented Oct 3, 2018

Uh oh!

lrytz commented Oct 3, 2018

Uh oh!

Jasper-M commented Oct 3, 2018

Uh oh!

NthPortal left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

neontorrent Nov 1, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

danslapman Nov 1, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

danslapman Nov 19, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

danslapman Nov 23, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

lrytz left a comment

Choose a reason for hiding this comment

Uh oh!

NthPortal commented Dec 19, 2018

Uh oh!

dwijnand commented Dec 19, 2018

Introduce `andThen` overload which combines two partial functions #7263

Introduce `andThen` overload which combines two partial functions #7263

neontorrent Nov 1, 2018 •

edited

Loading

danslapman Nov 1, 2018 •

edited

Loading

danslapman Nov 19, 2018 •

edited

Loading

danslapman Nov 23, 2018 •

edited

Loading