# What is a "lifted representation"?

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.

• recommended reading: Discuss this \${blog}
– gnat
Commented Sep 8, 2014 at 13:20
• @gnat it seems that he did not invent that term, it doesn't look like an opinion, it's not likely to provoke a discussion and my gut feeling is that it's not going to be too broad (although feels like math).
– Den
Commented Sep 8, 2014 at 13:31
• I discuss the meaning of "lifted" in the context of C# here: blogs.msdn.com/b/ericlippert/archive/2007/06/27/… -- likely the Scala developers are using the term in an analogous, but more general fashion. Commented Sep 8, 2014 at 17:22

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).

• That's a good description of mathematical "lifting". We should also include a reference to the more formal description of lifting from Wikipedia. Commented Sep 8, 2014 at 14:48
• A perhaps more clear example of "lifting" is lifting to nullable (or "optional" or "maybe") types. For example, suppose you have an operator + defined such that int + int --> int. The lifted-to-nullable operator int? + int? --> int? has the semantics of "if either operand is null then the answer is null, otherwise use the non-lifted operator on the values". Commented Sep 8, 2014 at 17:21
• @ScottWhitlock Do you even lift? Commented Sep 8, 2014 at 19:29
• @Frank I read the Wikipedia article before writing my answer, and didn't understand it either. Instead, I found the Haskell Wiki on Lifting to be more accessible. Note that we don't really have four types. We have four concrete types, but only three type variables: two types A and B, and a functor F which is a type constructor.
– amon
Commented Sep 9, 2014 at 8:49
• I'm not too deep into all of this, but if F is a type constructor, then F[A] is one of its constructed types. So why is it wrong to speak of these four types? (two types and one type constructor would be equally fine though of course) Commented Sep 9, 2014 at 9:08

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).

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.