[erlang-questions] Updates, lenses, and why cross-module inlining would be nice

[Jesper Louis Andersen]

It has the same problems as Richard alludes to: in order to run fast, you
need functional optimizations to remove the intermediate functions and make
access fast.

I toyed with building a parse transform for producing stuff, but I'd much
rather want a JIT.


On Thu, Nov 26, 2015 at 2:35 PM, Tristan Sloughter <t@REDACTED> wrote:

> Jesper also created https://github.com/jlouis/erl-lenses a few years
> back for this.
>
> --
>   Tristan Sloughter
>   t@REDACTED
>
> On Wed, Nov 25, 2015, at 10:52 PM, Richard A. O'Keefe wrote:
> > Summary:
> >  (1) A promising way to solve the nested updates problem
> >      is to be more functional, not less.
> >  (2) There's an approach we could steal from Haskell.
> >  (3) There's free code to play with, worth every penny.
> >
> > Consider a simplified version of Pascal:
> >
> >   <variable> ::= <identifier> <selector>*
> >   <selector> ::= <dereference> | <field> | <index>
> >   <dereference> ::= '^'
> >   <field> ::= '.' <identifier>
> >   <index> ::= '[' <expression> ']'
> >
> > If we think of a selector as a function
> >   f :: var T1 -> var T2
> > it's clear that <identifier> <selector> is function
> > application and <selector 1> <selector 2> is
> > function composition.
> >
> > Yet in Pascal, and C, and languages like them,
> > while you can *apply* selectors and *compose* them,
> > they cannot be passed as parameters or even named.
> >
> > If a functional language has something like selectors,
> > they should be first class values, just like other
> > more-or-less-function-like things.  But what kind of
> > value?
> >
> > I think it was Reynolds, analysing Algol 60, who came
> > up with the idea that a pass-by-name parameter was
> > really a *pair* of functions:  one to fetch a value
> > and one to store it, and thereby freed us from the
> > limiting idea that there needed to be a 'var T' type.
> >
> > The Haskell community have taken this idea and
> > developed it.  There this concept is called a "Lens".
> >
> > http://www.cs.otago.ac.nz/staffpriv/ok/lens.erl
> >
> > is a crude implementation of lenses in Erlang.
> > A lens is a selector from (values of) type A to
> > (values of) type B.  It's represented as a triple
> >
> >     {Get, Put, Upd}
> >     Get :: (A) -> B
> >     Put :: (A, B) -> A
> >     Upd :: (A, (B) -> B) -> A
> >
> > The Get function says how to extract a B value from an
> > A value.  The Put function says how to put a B value
> > into an existing A value, returning a new A value.
> > The Upd function says how to compute a new A value by
> > extracting a B, applying a function to it, and putting
> > it back.  We expect the following laws to hold:
> >
> >     Get(Put(A, B)) = B
> >     Put(A, Get(A)) = A
> >     Upd(A, Fun) = Put(A, Fun(Get(A)))
> >
> > That is, if you make a lens by hand, you should ensure
> > that this is true.
> >
> > There are functions for using lenses so you don't have
> > to think about the representation.
> >
> >     lens:get(Lens, A) -> B
> >     lens:put(Lens, A, B) -> A'
> >     lens:update(Lens, A, F) -> A'
> >
> > There are also functions for making simple lenses.
> > For example, if you have a record 'rec' with a field
> > 'fld', lens:tuple(#rec.fld) will give you a lens
> > for that field.
> >
> > Warning: the functions in the lens returned by
> > lens:tuple(#rec.fld)
> > do NOT check at run time that they are dealing with
> > a 'rec' record.  They can't, because #rec.fld is just
> > a number, and you can't get back from that number to
> > 'rec' or the arity of the record.
> >
> > The important thing is that these functions compose.
> >
> > For example, suppose you have
> >   -record(foo, {boo,coo,goo,zoo}).
> > and Foozle is a list of these, and you want to find
> > the first record with boo=42, and increment its zoo
> > field by 137.
> >
> >     Find = lens:where(fun (#foo{boo=Boo}) -> Boo == 42 end)
> >
> > is a lens for finding the record you want and
> >
> >     Field = lens:tuple(#foo.zoo)
> >
> > is a lens for getting at the zoo field of such a record.
> > lens.erl provides composition of 2 .. 6 lenses.  So
> >
> >     Selector = lens:c(Find, Field)
> >
> > is a selector that refers to a field of a record in a list,
> > and
> >
> >     lens:update(Selector, Foozle, fun (Zoo) -> Zoo + 137 end)
> >
> > does the whole job (in just one pass through the list, too,
> > which is why the Upd function is there).
> >
> > More simply,
> >     lens:c(lens:tuple(#a.b), lens:tuple(#c.d),
> >            lens:tuple(#e.f), lens:tuple(#g.h))
> > is the equivalent of .b.d.f.h in Pascal, except that it is
> > a value you can pass around like any other.
> >
> > You are not limited to fields that actually exist as such.
> > For example, you could do
> >
> > gb_set(Element) ->
> >     {   fun (Set) -> gb_sets:is_member(Element, Set) end
> >     ,   fun (Set, false) -> gb_sets:delete_any(Element, Set)
> >           ; (Set, true)  -> gb_sets:add(Element, Set)
> >         end
> >     ,   fun (Set, Fun) ->
> >             Old = gb_sets:is_member(Element, Set),
> >             case Fun(Old)
> >               of Old   -> Set
> >                ; true  -> gb_sets:insert(Element, Set)
> >                ; false -> gb_sets:delete(Element, Set)
> >             end
> >         end
> >     }.
> >
> > and make a gb-set act like a dictionary with Boolean elements.
> >
> > There's even a combinator all/1 so that
> >     All = lens:c(lens:tuple(1)),
> >     Data = [{3,a},{1,b},{4,c},{6,d}]
> >     lens:get(All, Data)
> >  => [3,1,4,6]
> >     lens:update(All, Data, fun (N) -> N*10 end)
> >  => [{30,a},{10,b},{40,c},{60,d}]
> >
> > So what about cross-module inlining?
> >
> > By the time you've made and composed a couple of lenses,
> > you have a tangle of funs.  If the compiler (a) always
> > inlines (fun (...) -> ... end)(...) and (b) inlines the
> > functions from the lens module, then the tangle resolves
> > tidily into reasonably straightforward code.
> >
> > But the cross-module inlining step is crucial.  Without
> > that, the compiler has nothing to work on.
> >
> > At its crudest, consider
> >
> >     lens:get(lens:tuple(#rec.fld), Rec)
> >
> > *With* cross-module inlining and inlining of funs that
> > are applied to known arguments and dead code elimination,
> > you end up with
> >
> >     element(#rec.fld, Rec)
> >
> > *Without* cross-module inlining, three funs are built,
> > only one of which will ever be called.
> >
> >
> > _______________________________________________
> > erlang-questions mailing list
> > erlang-questions@REDACTED
> > http://erlang.org/mailman/listinfo/erlang-questions
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>



-- 
J.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20151126/57e1a19e/attachment.htm>