Is it possible to store and retreive function definitions for later composition?

Design
1

Hi,

I would like to take a description that tells me the order in which a number of functions are to be applied and use that to generate a composition of those functions. In other words I would like to do run-time function composition. Because the description comes from a running Scala program, I at least have guarantees that the types are correct.

To be a little more concrete say I have the following definitions:

    def func1(a:Int): Double = a.toDouble
    def func2(a:Double): Double = a * 2
    def func3(a:Double): Boolean = if (a > 3) true else false

    def o[A,B,C](f1:(A) => B, f2:(B) => C) = (x:A) => f2(f1(x))

Now lets assume that I had a Scala program that did this:

  val c1: Int => Double = o(func1, func2)
  val c2: Int => Boolean = o( func1, o(func2, func3))

Lets also assume that from that I have the following information:

val saved = List("func1", "func2", "func3")

How can I use saved to reconstruct the function c2? Is this technically possible? If so how best to go about it?

Appreciate any pointer or references.

TIA

2

Hello,

Minor gripe: your func1 etc are methods, not functions. But you can use
them in places where functions are expected, and then the compiler will
convert (“lift”) your method of signature (A)B into a function A => B.

Since functions are objects, you can save them in a collection and retrieve
them at runtime according to inputs. The question is what about the static
types. There are different scenarios and approaches.

(1) You know in advance that a certain piece of code will only ever deal
with functions of a certain type, say Int => Double, so you can supply the
static types. You could have a collection of Int => Double, such as
Map[String, Int => Double], or your own collection that has a
getIntToDouble(name: String): Int => Double method.

(2) You don’t know the types of your function and you don’t care. You could
wrap your A => B function into an Any => Any function and then have a
collection of Any => Any functions.

(3) You only have a limited number of types, somehow store the type
information, and branch out. For example, you may have only Int and Double
values, then you only have four types of functions: Int => Int, Int =>
Double, Double => Int, Double => Double. You’d have to separately store the
type information to know the correct branch. This is repetitive and gets
quickly unwieldy when new types are added.

(4) You call the apply method of each function through reflection. This
circumvents any static typing.

(5) You create your composition by having your app generate the needed
Scala code, invoke the compiler to compile it, then have the classloader
load the resulting class and then you instantiate it via reflection.

Best, Oliver

3

The general technique for doing this is type-aligned data structures. The downside is that you cannot use the built-in collections directly for this; you must design a structure that fits your needs.

You can preserve all the type information in an hlist, but all you are doing that way is shifting the problem, if I’m interpreting your explanation correctly. (Of course, if you can use the singleton types of those strings instead of their runtime values, then there is no problem there; you can do all the lookups at compile-time. I’m not going to explain that because there’s plenty written elsewhere about that.)

Scalaz 8 includes some type-aligned structures that are commonly needed. For example, c2 can be modeled directly like so (tried in Scala 2.12.4, Scalaz 8 fcd2d2b3):

scala> import scalaz.data.AList1

scala> (func1 _) :: (func2 _) :: AList1(func3 _)
res0: scalaz.data.AList1[Function1,Int,Boolean] = AList1($$Lambda$5543/1591607484@3f1325e5, $$Lambda$5544/1336807449@52e210ee, $$Lambda$5545/1147158014@74782b5a)

The type of this structure works by throwing away type information that you won’t need and keeping type information that you do. In this case, only the argument type Int of the first function, and the return type Boolean of the last function, are preserved. The presumption is that you don’t care about the types in between; indeed, you can’t usefully take sections of this list because you wouldn’t know the argument type and/or return type anymore. You can think of the element types as follows:

// there are existential types
type e1
type e2
// and the function types are
Int => e1, e1 => e2, e2 => Boolean

So Function1 isn’t an interesting type to connect these. But what if you passed [a, b] => a => Either[Result[A], b]?

// there are existential types
type e1
type e2
// and the function types are
Int => Either[Result[A], e1], e1 => [Either[Result[A], e2], e2 => Either[Result[A], Boolean]

That affords some more interesting possibilities.

So here is the trouble with your string-selection idea. How do you limit the selection of functions to one that makes sense, i.e. one that takes an Int and returns a Boolean? You want to be able to pick func1 and func3 or all three, or func2 multiple times, but no other combination makes sense.

I don’t know exactly your goals, but here is an example of letting a particular dynamic selection goal design the datatype for me. So, like AList, I’m fixing the input and output types to T and R, but at each stage, you get to pick a “branch”, which leads either to another choice or a terminator, indicating you’ve reached the goal type.

package atree

object Funcs {
  def func1(a:Int): Double = a.toDouble
  def func2(a:Double): Double = a * 2
  def func3(a:Double): Boolean = a > 3
}

// Note the 'U', this is intended to be existential
final case class ResPair[T, U, R](next: T => U, tree: AChoiceTree[U, R])

final case class AChoiceTree[T, R](
  done: Option[T =:= R],
  // this existential means each `ResPair` in the map can have an
  // entirely different 2nd tparam (U); accordingly, there is no way
  // to tell what the Us internal to an AChoiceTree are
  choose: Map[String, ResPair[T, _, R]]
)

object AChoiceTree {
  /** Return the goal, or None if we weren't at an endpoint when choices
    * was exhausted. You don't need a `start` value to calculate a
    * function, though; you could even use a `tree` and `choices` to
    * calculate a `Option[scalaz.data.AList[Function1, T, R]]`.
    *
    * You don't have to drive this with a `List`; you can step through
    * the tree at your leisure. Just keep in mind that the internal
    * tree types are existential; *none* of the internal trees of an
    * `AChoiceTree[T, R]` have the same type.
    *
    * There are three reasons for failure: you ran out of choices
    * before getting to a terminus, you got to a terminus but still
    * had [valid or invalid] choices left, or you tried an invalid
    * choice.  You can differentiate between these as you like; I did
    * not for this example.
    */
  @annotation.tailrec
  def interpret[T, R](tree: AChoiceTree[T, R],
                      choices: List[String],
                      start: T): Option[R] =
    choices match {
      case Nil => tree.done map (_(start))
      case s :: ss => tree.choose.get(s) match {
        case None => None
        case Some(p: ResPair[T, u, R]) => // look up "variable type pattern"
          interpret(p.tree, ss, p.next(start))
      }
    }

  def finalFunction[T, R](f: T => R): ResPair[T, _, R] =
    ResPair(f, AChoiceTree(terminus, Map()))

  def terminus[R]: Option[R =:= R] = Some(implicitly)

  import Funcs._

  val tree: AChoiceTree[Int, Boolean] =
    AChoiceTree(None, Map("func1" -> ResPair((func1 _),
      AChoiceTree(None, Map("func3" -> finalFunction(func3 _),
                            "func2" -> ResPair((func2 _),
        AChoiceTree(None, Map("func3" -> finalFunction(func3 _)))))))))

  // 1st and 4th are only ones that should succeed
  val trials = (interpret(tree, List("func1", "func3"), 3),
                interpret(tree, List("func1"), 1),
                interpret(tree, List("func1", "func3", "func2"), 4),
                interpret(tree, List("func1", "func2", "func3"), 8))
}

scala> atree.AChoiceTree.trials
res0: (Option[Boolean], Option[Boolean], Option[Boolean], Option[Boolean]) =
  (Some(false),None,None,Some(true))

Again, if you want this kind of dynamic choice strategy, the burden is placed upon you to design a datatype like AChoiceTree with the kind of dynamism you want.

1 Like
4

Appreciate the feedback. In regards to options (1) and (2), they are not viable. I simply cannot foresee what functions I will need nor what their signatures will. Option (2) may be the simplest solution since I have some guarantees that the sequence of calls are valid (type checked, of-course this is true only if i do not change the definitions and recompile them). Hmmm… option (5) seems like overkill. That would be a last resort.

Stephen suggestions seem to be a more disciplined way of doing what I need, however I will do a test using option (2) to see what gives.

Thank you.

5

Some additional background. I already have a data structure that describes the functions and their composition. I use this to generate a set of composed functions using partial evaluation. Each composition is a “pipe” that consumes data and produces results.

This is correct. In fact both the AList1 and the ResPair have the same “intermediate” type that I use.

Interesting. Although in my case I don’t need this because the possible “pipes” are type checked at compile time. At run-time partial evaluation constructs the “pipes” (function composition).

Once the “pipes” have been constructed they are executed. During execution each function and the parameters used in the pipe are recorded. I want to take this recording and simply recreate a single “pipe” for use with another input.

Wow. This has given me an idea. I may adapt my existing “pipe compiler” to traverse the “pipe structure” again but now, using the list of function names, select and compose a single “pipe” much as you do in your interpreter (the parameters my be an issue though).

Hmmm… now this leave me wondering if I can “pickle” the “pipes description” to a file.

Your example also shows me that we can “delay” function composition to run-time and still ensure type safety. Still have to wrap my head around this.

Thank you.

6

@curoli Just to say that I tried solution (2) and wrapping the function to a Any => Any is doable. Of-course this is not type safe but its workable.

7

@hmf Hi, I was wondering if you got to any interesting point on this problem?

8

Don’t recall all the details but the code above worked. However I did not use it in the end because it is a maintenance headache, hard to save/load to file and it is also difficult for newcomers to Scala. In the end I used a set of case classes to encode the pipe and during runtime this is “compiled” into a function.

HTHs

9

Thanks for the update. if by any chance you found the code, I would love to look at the details.