What is a "lifted representation"?

Question

Just ran across this term here:

http://www.codemesh.io/codemesh2014/viktor-klang

"We'll demonstrate the Flow API—a lifted representation—as well as a pluggable way of transforming the lifted representation into the execution representation—Flow Materialization."

Googling did not help much.

Answer 1

I am not familiar with the Flow API.

The term “lifting” comes from category theory. In programming languages such as Haskell or Scala, a lift function takes a function A => B, and somehow performs magic so that the lifted function F[A] => F[B] can be applied to a functor or monad F[A].

A concrete example using Scala's Seq container: Assume we have a function def double(x: Int): Int = 2 * x, and a sequence val xs = Seq(1, 2, 3). We cannot double(xs) due to incompatible types. But if we obtain a val doubleSeq = liftToSeq(double), we can do doubleSeq(xs), which evaluates to Seq(2, 4, 6). Here, liftToSeq can be implemented as

def liftToSeq[A, B](f: A => B): (Seq[A] => Seq[B]) =
  (seq: Seq[A]) => seq.map(f)

The Seq(…) constructor can also be seen as a lifting operation, which lifts the values 1, 2, 3 into a Seq instance, thus allowing us to use list abstractions for these values.

Monads allow us to encapsulate the inner workings of some type by offering a watertight but composable interface. Using a lifted representation can make it easier to reason about a computation. Using such abstractions also means that we lose knowledge of the abstracted-away specifics, but those are needed for providing an efficient implementation under the hood (finding a suitable execution representation).

Answer 2

The term to lift can of course have different meanings depending on the context.

In generic programming it describes the process of abstracting to the next higher level. For example, you could have two pieces of code, one type with int, and the other with float. Lifting this code would mean something like templating the method with a generic type T that works for both, int and float.

I found this usage of the term to be a good intuitive guideline for what lifting means. The only difference that seems to exist between the different contexts is what this higher abstraction really is.

In particular, Viktor is known in the context of functional programming, and in this context, you can find sightly different interpretations of lifting there. One example, is to lift values into a functor, or to lift functions to work on monadic values (i.e. Haskell's liftM2).

A very concrete example of a "lifted representation" could then f.ex. be a List(1), or a Some(1).

Answer 3

These sorts of concepts are usually easiest to understand with a concrete example. Consider the following excerpt from this Flow API example:

Flow(text.split("\\s").toVector).
      // transform
      map(line => line.toUpperCase).
      // print to console (can also use ``foreach(println)``)
      foreach(transformedLine => println(transformedLine)).
      onComplete(FlowMaterializer(MaterializerSettings())) {
        case Success(_) => system.shutdown()
        case Failure(e) =>
          println("Failure: " + e.getMessage)
          system.shutdown()
      }

This takes the following code:

text.split("\\s").toVector.
      map(line => line.toUpperCase).
      foreach(println)

and "lifts" it into a Flow context. That allows you to use the same syntax you are familiar with for specifying your algorithm, but behind the scenes the map is done in parallel on several processors or even machines, then the foreach(println) seamlessly collects that output back to one processor for printing.

This is a generic term that can refer to wrapping any context around any type. Another more familiar example is map takes a function that works on a single element and "lifts" it into the new context of working on a collection of those elements. Lifting is ubiquitous in functional programming and one of the main reasons it is so much easier to reuse functional code.