Compiler-generated lenses for record fields

[Tony Morris]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

OK, so we recently got the copy method for updating fields of case
classes.

However, what about lenses in a more general and composable form? It
is possible to implement as a library, right up to the point where it
would require you to implement the lens for each record (I use the
term "record" so as not to be necessarily specific to case classes) field.

Let us first define a lens in library code.

The Identity functor is trivial to get us started:

case class Identity[A](a: A) {
def map[B](f: A => B): Identity[A] = sys.error("todo")
def flatMap[B](f: A => Identity[B]): Identity[B] = sys.error("todo")
}

Next we define costate (the categorical dual to state) as a comonad
transformer:

// A Comonad for any Comonad[F] (todo)
case class CoStateT[A, F[_], B](put: F[A => B], set: A)

Next we are able to define a Lens:

case class Lens[T, R](k: T => CoStateT[R, Identity, T])

Now, I have been a bit elaborate here with the comonad transformer
then specialising to Identity. I did this because there is a huge and
useful library behind CoStateT, which benefits by being in transformer
version. Nevertheless, we may simplify for the purposes of staying on
track with lenses:

case class CoState[A, B](put: A => B, up: A) {
// A Comonad
def coFlatMap[C](f: CoState[A, B] => C): CoState[A, C] =
CoState(a => f(CoState(put, a)), up)
}

A lens is now a little simpler (specialised):

case class Lens[T, R](k: T => CoState[R, T])

Now, we sometimes think of a "lens" as the pair of a get and set method.

* get: T => R // get the field on T of type R
* set: T => R => T // set the field on T of type R, returning new T

I encoded it earlier with a representation using CoState to take
advantage of this particular data type and its library (it is very
rich). We can still construct a Lens using get/set pairs quite easily:

object Lens {
def lens[T, R](
get: T => R
, set: T => R => T
): Lens[T, R] =
Lens(t =>
CoState[R, T](set(t), get(t)))
}

We can also implement get and set methods on Lens easily (omitted for
brevity).

Now one of the important, killer useful properties of lenses is that
*they compose*. What does this mean? It means the following function
exists (also with an identity Lens[X, X]):

def compose[A, B, C](f: Lens[A, B], g: Lens[B, C]): Lens[A, C]

Let's write it as a method to demonstrate it:

case class Lens[T, R](k: T => CoState[R, T]) {
def compose[Q](that: Lens[R, Q]): Lens[T, Q] =
Lens[T, Q](t => {
val CoState(f, a) = k(t)
val CoState(g, b) = that.k(a)
CoState(f compose g, b)
})
}

To state it in English, "if we have a lens from T to R, and a lens
from R to Q, then we have a lens from T to Q." To provide an example:
if our Building has a (lens) Window and a Window has a (lens)
Perimeter, then our Building has a (lens) Window. This would allow us
to "get and set" the Window property on the Building class, thus,
answering the often-encountered questions regarding traversing down
object graphs and getting all messy. I digress, but hopefully, this
conveys an important point.

Further, this Lens class deserves to have all sorts of combinators on
it for manipulating record fields, but I have omitted them for brevity
- -- hopefully you can imagine the sorts of things that might appear. If
not, I'll follow-up with some examples.

So we are all fine and dandy at this point, with a nice useful
library. Looks promising! Let's try to put it into practice.

Suppose we have:

case class Person(name: String, age: Int, friend: Person)

We now want:

* lname: Lens[Person, String]
* lage: Lens[Person, Int]
* lfriend: Lens[Person, Person] // these compose in any Traversable!

However, this is tedious and full of boilerplate:

val lname = Lens.lens(_.name, p => n => p.copy(name = n))
val lage = Lens.lens(_.age, p => a => p.copy(age = a))
val lfriend = Lens.lens(_.friend p => f => p.copy(friend = f))

eek! We have required effort proportional to the number of fields in
our record type. This can't be fun.

So, now I can get to the question: Wouldn't it be useful to:
a) develop a library around these data structures?
b) have the compiler generate the latter boilerplate code?

I haven't thought too far ahead to implementation, or pondered on
issues of generating bytecode for each record field, however, I am
simply tempted by just how useful this particular feature could be. It
even has that "attraction" to Java programmers coming on over to Scala
and wondering how we deal with this sort of thing -- can we, y'know,
kick some serious arse!? Just askin'

Comments? Thanks for listening.

- --
Tony Morris
http://tmorris.net/

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk3c8UEACgkQmnpgrYe6r615SACgvbmIRGKgVhjrP6sWKfFfdiVg
MZMAoLNDD9IscdX2vE7huBLMkIkiU6WF
=lhww
-----END PGP SIGNATURE-----

[Josh Suereth]

+1 on a lenses library with a simple interface.   Most of the time I would need lenses though, it's in a different context.  One of interfacing with other teams who've defined the same data abstractions with slightly differing values and I want to use lenses to convert between the two.   Nothing in your API prevents that, but the bit about compiler magic is where we may start disagreeing on what it should look like :)

- Josh

[Tony Morris]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

How would you have it look such that you overcome a problem that is
not currently catered for?

> brevity -- hopefully you can imagine the sorts of things that might

iEYEARECAAYFAk3c+ZAACgkQmnpgrYe6r61fywCfbgLELh1KUD8tKMxbHyMwXuUv
4G0AoJIT5oO8O3WZZoV9rdnmQfJF9bfc
=ij7U
-----END PGP SIGNATURE-----

[Robert Wills]

Is there any other way to get rid of the boilerplate than with compiler magic?

According to this

http://stackoverflow.com/questions/3900307/cleaner-way-to-update-nested-structures

http://www.scala-lang.org/node/6622
there was once a prototype compiler extension for automatically generating the boilerplate 

associated with zippers:

@zip case class Pacman(lives: Int = 3, superMode: Boolean = false) 

Presumably something similar could be done with lenses.

Judging by the conversation on scala-user yesterday about producing compiler plugins I guess 

this would be quite difficult to do as a plugin.

-Rob

[Tony Morris]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 25/05/11 22:08, Tony Morris wrote:
> To provide an example: if our Building has a (lens) Window and a
> Window has a (lens) Perimeter, then our Building has a (lens)
> Window. This would allow us to "get and set" the Window property on
> the Building class, thus

Correction:

To provide an example:
if our Building has a (lens) Window and a Window has a (lens)

Perimeter, then our Building has a (lens) Permiter. This would allow us
to "get and set" the Permiter property on the Building class, thus,

- --
Tony Morris
http://tmorris.net/

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk3c+pIACgkQmnpgrYe6r62naQCfcspuiuyGr3leYq/AuY8JYnWp
bdAAn1+eAg8rCbdrlSlHIGKBGoX7dxAU
=mq/b
-----END PGP SIGNATURE-----

[Josh Suereth]

In my case I have type project1.Building and type project2.Building.   I want to define a lens from project1.Building => project2.Building so I can adapt incoming data from project1 for project2's use case.   This involves manipulating *all* the fields, not just a single one, so the boilerplate is larger.  The base abstraction is correct, but I think the boilerplate may be slightly different.   I'd just like to account for that if there were any sort of compiler magic going on.

- Josh

[Daniel Sobral]

I wonder how to build the compiler support for the lens without loss
of generality. One solution I can think of is this:

case class C(field1: T, field2: R)

// This gets auto-generated
object C {
object lens {
def field1: Tuple2[C => T, C => T => C] = ((_: C).field1,
(that: C) => (value: T) => that.copy(field1 = value))
def field2: Tuple2[C => R, C => R => C] = ((_: C).field2,
(that: C) => (value: R) => that.copy(field2 = value))
}
}

It could then be used as basis to provide any lens implementation:

object Lens {
implicit def lens[T, R](l: (T => R, T => R => T)): Lens[T, R] =
Lens(t =>
CoState[R, T](l._2(t), l._1(t)))
}

val lname: Lens[Person, String] = Person.lens.name

--
Daniel C. Sobral

I travel to the future all the time.

[Naftoli Gugenheim]

On Wed, May 25, 2011 at 8:08 AM, Tony Morris <tonym...@gmail.com> wrote:

However, this is tedious and full of boilerplate:

val lname = Lens.lens(_.name, p => n => p.copy(name = n))
val lage = Lens.lens(_.age, p => a => p.copy(age = a))
val lfriend = Lens.lens(_.friend p => f => p.copy(friend = f))

eek! We have required effort proportional to the number of fields in
our record type. This can't be fun.

If you're targeting case classes, without making the effort less than proportional to the number of fields, perhaps we can still make it less per field. Using scala.reflect.Code, maybe you could get the AST for _.name and infer the p=>n=>p.copy(name = n) part.

[Tony Morris]

In a similar spirit.

Edward Kmett: Lenses: A Functional Imperative
Presented @ Boston Area Scala Enthusiasts (BASE) 24 May 2011

http://www.youtube.com/playlist?p=PLEDE5BE0C69AF6CCE

On 25/05/11 22:08, Tony Morris wrote:
>

[Steven Obua]

Thank you for posting this talk! I have seen "Lenses" floating around and mentioned often lately, but had not yet looked up what they actually are; now I know. 

Turns out, I might have great use for lenses in my language Babel-17 (www.babel-17.com); I think Babel-17 should support this natively. You can already do 

val x = {a = 2, b = 3}

x.b = 7

in Babel-17; here x.b = 7 is just short for 

val x = {a = x.a, b = 7}

So it is basically what copy for case classes does in Scala, but more tightly integrated into the language. I always had in the back of my mind that I would like to generalize this shortcut update notation somehow, and lenses seem to be the perfect tool to do it as they seem to mix great with my concept of linear scope, just like they were made for each other.

There is a new version of Babel-17 coming out in the next 5 to 10 days, v0.3. Lenses will probably not make it into this release, but expect them in v0.3.1 .

Ah, two comments about the talk: I liked it a lot, but I noticed two things:

a) there is nothing wrong with exceptions in a purely functional language, they just need to be done right, like in Babel-17

b) there was a lot of typing involved in explaining what lenses are; I have no problems with this; but I can also see how lenses can be explained in a nice way to people and used by people without any static types getting in the way

- Steven

[Tony Morris]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Am I to assume the silence is a result of distaste for the idea, or
more that one would prefer to see the patch before taking it
seriously? (or something else)

On 25/05/11 22:08, Tony Morris wrote:

> brevity -- hopefully you can imagine the sorts of things that might

iEYEARECAAYFAk3hnIMACgkQmnpgrYe6r62Q6gCdGMnyzReb4Gu9c4W1/8VbqZ/O
JuEAoKNIUtxkfrpqQqFgUJ9bKQC8Cji3
=PIHN
-----END PGP SIGNATURE-----

[Andreas Scheinert]

I hope the later one.

On 29 Mai, 03:08, Tony Morris <tonymor...@gmail.com> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Am I to assume the silence is a result of distaste for the idea, or
> more that one would prefer to see the patch before taking it
> seriously? (or something else)
>

> Tony Morrishttp://tmorris.net/

>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.10 (GNU/Linux)

> Comment: Using GnuPG with Mozilla -http://enigmail.mozdev.org/

[Chris Marshall]

Speaking purely for myself; before watching Edward Kmett's presentation on lenses, I had little to no idea what they were for, hence why I should care about a compiler plugin for them. My interest is now piqued and I certainly agree that a compiler plugin is critical to their use. Or at the very least a lens-code-generator.

Chris

---

Date: Sun, 29 May 2011 11:08:19 +1000
From: tonym...@gmail.com
To: scala-...@googlegroups.com
Subject: [scala-debate] Re: Compiler-generated lenses for record fields

[Kevin Wright]

Boiling it down to the core requirement, I don't see that this would be especially nasty for a plugin to handle.

The main hurdle for any plugin at present is where type checking would fail in the absence of generated code, but that's not the case here.  If the definitions were made abstract and explicitly typed, with an annotation:

    @lens("Person.name") val lname: Lens[Person, String]
    @lens("Person.age") val lage: Lens[Person, Int]

    @lens("Person.friend") val lfriend: Lens[Person, Person]

This would pass through the namer and typer phases without problem (the check that calls are to a concrete method don't occur until a later compiler phase).

The plugin could then run after the typer phase, synthesising the necessary code and stripping the ABSTRACT flag from the methods.  The @lens annotation could be removed, but there's real benefit in doing so.

    @lens("Person.name")

    val lname: Lens[Person, String] =

      Lens.lens(_.name, p => n => p.copy(name = n))

    @lens("Person.age")

    val lage: Lens[Person, Int] =

      Lens.lens(_.age, p => a => p.copy(age = a))

    @lens("Person.friend")

    val lfriend: Lens[Person, Person] =

      Lens.lens(_.friend p => f => p.copy(friend = f))

Assuming that the above code is valid for lenses in Scalaz, I'll put this in my backlog to experiment with, on the offchance that I somehow manage to find any free time in the near future.

--
Kevin Wright

gtalk / msn : kev.lee...@gmail.com

mail: kevin....@scalatechnology.com

vibe / skype: kev.lee.wright

quora: http://www.quora.com/Kevin-Wright
twitter: @thecoda

"My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger" ~ Dijkstra

[Kevin Wright]

Looking back, that could be simplified further, there's no need to mention the target Type in the annotation:

    @lens("name") val lname: Lens[Person, String]
    @lens("age") val lage: Lens[Person, Int]

    @lens("friend") val lfriend: Lens[Person, Person]

[Naftoli Gugenheim]

Can someone show a sample application that would benefit from composing calls to copy in such a way?

[Chris Marshall]

Naftoli - watch Edward Kmett's presentation. The idea is to use imperative-like code with what will *look* like "deep" mutation using for comprehensions

Chris

---

Date: Sun, 29 May 2011 14:03:13 -0400
Subject: Re: [scala-debate] Re: Compiler-generated lenses for record fields
From: nafto...@gmail.com
To: kev.lee...@gmail.com
CC: oxbow...@hotmail.com; scala-...@googlegroups.com

[Daniel Sobral]

On Sun, May 29, 2011 at 15:03, Naftoli Gugenheim <nafto...@gmail.com> wrote:
> Can someone show a sample application that would benefit from composing
> calls to copy in such a way?

http://code.google.com/p/virtual-combat-cards/source/detail?r=789

--

[Rex Kerr]

On Sat, May 28, 2011 at 9:08 PM, Tony Morris <tonym...@gmail.com> wrote:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Am I to assume the silence is a result of distaste for the idea, or
more that one would prefer to see the patch before taking it
seriously? (or something else)

These would be considerably more exciting to me if
  (a) there were hooks for notifications as well
  (b) there was a mutable version also for efficiency and/or Java interaction

I rarely need lenses--case class copy does fine, plus local definition of a method for updating a single deep field if I have to do it more than once, used in conjunction with a pipe.  (Can compose the methods with andThen if you really want to.)

I also rarely need notification hooks; I build in what I need at the time, and generally try not to structure code that way anyway unless I have to (e.g. with Swing).

And if I have a mutable version I just go update it directly (except I sometimes have to do it in a side effecting block, which is a bit awkward--with lenses I could more easily do it in-line, which would reduce the risk of errors).

If there was one tool that would combine all of these getter/setter/notifier tasks under one framework, however, I would use it at least three times as often as rarely, which is probably often enough for me to be pretty interested.  Otherwise, it's just not very compelling for me.  There's only one project that I've created lately where they'd be really nice to have.

  --Rex

[Tony Morris]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 30/05/11 12:16, Rex Kerr wrote:
> On Sat, May 28, 2011 at 9:08 PM, Tony Morris
> <tonym...@gmail.com> wrote:
>
>>
>> -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
>>
>> Am I to assume the silence is a result of distaste for the idea,
>> or more that one would prefer to see the patch before taking it
>> seriously? (or something else)
>>
>
> These would be considerably more exciting to me if (a) there were
> hooks for notifications as well

That's what composition is all about!

> (b) there was a mutable version also for efficiency and/or Java
> interaction

It doesn't really make sense for there "to be a mutable version." In
particular, the differences between lenses and mutable getter/setter
is as big as the differences between any two arbitrary data
structures. I'm really not fond of the conflation of
"mutable/immutable" versions of data structures -- the consequences
are pretty disastrous.

>
> I rarely need lenses--case class copy does fine, plus local
> definition of a method for updating a single deep field if I have
> to do it more than once, used in conjunction with a pipe. (Can
> compose the methods with andThen if you really want to.)

It's not a matter of "needing" lenses, but rather exploiting the
library that it gives rise to. I've only alluded to it. If I had a
dollar for the number of projects that I have seen that invented
specialised lenses and the subsequent library... (I have a rough
version of it if you like)

>
> I also rarely need notification hooks; I build in what I need at
> the time, and generally try not to structure code that way anyway
> unless I have to (e.g. with Swing).

This is just composition -- lenses deliberately preserve compositional
program properties. That is, we intentionally have this.

>
> And if I have a mutable version I just go update it directly
> (except I sometimes have to do it in a side effecting block, which
> is a bit awkward--with lenses I could more easily do it in-line,
> which would reduce the risk of errors).

Email.scala:133 "mutable version" conflation error.

>
> If there was one tool that would combine all of these
> getter/setter/notifier tasks under one framework, however, I would
> use it at least three times as often as rarely, which is probably
> often enough for me to be pretty interested.

I bet if you realised you were already using it, you'd change your mind!

> Otherwise, it's just not very compelling for me. There's only one
> project that I've created lately where they'd be really nice to
> have.
>
> --Rex
>

Thanks for the feedback.

- --
Tony Morris
http://tmorris.net/

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk3jSrcACgkQmnpgrYe6r62cpQCggwy7kCIiPCf03L1zceLF4vY8
EAoAnjCMg0lYX+KYFZ/vrtzLFXHXUt5Y
=MnKB
-----END PGP SIGNATURE-----

[Rex Kerr]

On Mon, May 30, 2011 at 3:43 AM, Tony Morris <tonym...@gmail.com> wrote:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 30/05/11 12:16, Rex Kerr wrote:
> On Sat, May 28, 2011 at 9:08 PM, Tony Morris
> <tonym...@gmail.com> wrote:
>
>>
>> -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
>>
>> Am I to assume the silence is a result of distaste for the idea,
>> or more that one would prefer to see the patch before taking it
>> seriously? (or something else)
>>
>
> These would be considerably more exciting to me if (a) there were
> hooks for notifications as well

That's what composition is all about!

I don't see any place to insert side-effects _or_ to include an additional return value (without messing up composability) in auto-generated code.  I see how to do it if you're creating the lenses by hand.
 

> (b) there was a mutable version also for efficiency and/or Java
> interaction

It doesn't really make sense for there "to be a mutable version." In
particular, the differences between lenses and mutable getter/setter
is as big as the differences between any two arbitrary data
structures. I'm really not fond of the conflation of
"mutable/immutable" versions of data structures -- the consequences
are pretty disastrous.

The consequences of making immutable and mutable data structures so similar semantically that you cannot tell them apart are, I agree, pretty disastrous.  But if one is passing data through multiple functions in a single chain, then whether the underlying representation is mutable or immutable is just an implementation detail.

In particular, mutable and immutable constructs have opposite problems: with mutable structures, the error is that one forgets that one needs a copy of the state; with immutable structures, the error is that one forgets that the old copy of the state is now useless (out of date).

In both cases, chains of operations come to the rescue: the language syntax makes it nearly impossible for you to be mistaken about which version of the state you are working with; the correct state is the one that is the easiest to interact with.

Thus, I claim that the _most obvious_ application of lenses is almost equally useful in a mutable context.  Since I haven't seen the library you're alluding to, I can't really tell whether the less-obvious applications are also almost equally useful in both contexts.  So, barring any revelations, I'd like to see a similar capability for mutable constructs as well, preferably with semantics chosen so that anyone who knows one will recognize the other, but will also be under no delusion about which case they're dealing with.  (For example, for mathematics I've used + - * for immutable and +~ -~ *~ for mutable operations.  It's very hard to get confused about what is happening, but the math is still fairly readable even when done mutably.)

  --Rex

[Daniel Sobral]

On Mon, May 30, 2011 at 05:29, Rex Kerr <ich...@gmail.com> wrote:
>
>> > These would be considerably more exciting to me if (a) there were
>> > hooks for notifications as well
>>
>> That's what composition is all about!
>
> I don't see any place to insert side-effects _or_ to include an additional
> return value (without messing up composability) in auto-generated code.  I
> see how to do it if you're creating the lenses by hand.

The point is that you can declare a class LensPublisher[T](lens:
Lens[T, T]) extends Lens[T, T] with Publisher[Event[T]] and then use
it like this:

case class Person(name: String)

// Assuming my proposal for compiler aid
val personPublisher = new LensPublisher[Person](Lens(Person.Lens.person))
val personNamePublisher = personPublisher compose Lens(Person.Lens.name)
personNamePublisher subscribe (mySubscriber)

val person = Person(Rex)
personNamePublisher.set(person, "Rex Kerr")

And that will send a notification to mySubscriber. To make the point
clearer, you can create generic lenses for various purposes, and
compose them with specific lenses. Likewise, you can write code that
handles data structure generically, and pass it lenses that do the
right thing.

[Rex Kerr]

You move the responsibility for giving the notification from the source of the lens (the case class) to yourself (composing in a publisher), but I see the point.  With a little bit of discipline, this could be okay.

Incidentally, exactly the same construct as you proposed would work for mutable fields also.

  --Rex

[Andreas Scheinert]

Hi Rex!
I think the point was not to show how such a mechanism works for
immutable datastructures, all agreed before (have you seen e. Kmetts
talk?) that with mutably it works 'just' fine.
Regards Andreas
On 30 Mai, 20:53, Rex Kerr <icho...@gmail.com> wrote:
> On Mon, May 30, 2011 at 9:31 AM, Daniel Sobral <dcsob...@gmail.com> wrote:

[Naftoli Gugenheim]

I'm wondering if it would be possible to do something like this, possibly instead of special compiler support.

Given case class Case(n: Int), to automatically get a Lens[Case,Int] from the expression c.n, perhaps something like the following could be done:

def lens[A,B](accessor: scala.reflect.Code[A=>B]): Lens[A,B]

enabling you to write lens(c)(_.n). Internally lens would analyze the AST and generate a getter that just reads the field, and a setter that calls copy, via reflection.