inference for uses for `lift`?

[Aaron Bohannon]

Hi,

I was revisiting Elm today, and an interesting thought struck me:  why can't all uses of `lift`, `lift2`, etc simply be inferred?

I believe that applying these two rules should be sufficient:

1. Consider the case of a n-arg function `f` whose most general type contains no uses of `Signal`.  Wherever `f` is applied without a `lift`, replace it by `lift f`, `lift2 f`, etc, as appropriate.

2. Then, wherever a function application requires a parameter to be of type `Signal a` and the type of the actual parameter expression `e` does not have a Signal type, replace `e` with `constant e`.

Although I realize this would add complexity to Elm's type-checking and error reporting (and the fine print of the documentation as well), I feel like the benefits of doing this could be enormous.  As things are now, one must arrange their code in such a way so as to avoid excessive use of `lift`, which often means threading extra parameters through all of the functions.  But, aside from notational clutter, simply not having to think about where lifting is needed would make it much easier -- even for experts -- to write Elm code and would significantly lower the barrier to entry non-FP programmers and non-programmers.

I'm not really sure whether this has been suggested before...the idea seemed quite obvious to me once I noticed it, but perhaps I'm overlooking some potential problem.

...Aaron

[Evan Czaplicki]

Implicit lifting was used in FrTime. They used monadic FRP and implicitly made everything a signal though.

Apart from clarity (which I think is hurt by this) adding nodes apparently had a nontrivial performance impact. Each node is introducing new function calls, data structures, and caching that do not get compiled away by a host language. This inspired a paper about "lowering" in which you take a signal graph that has lots of things lifted unnecessarily and tries to remove them from the graph to get back some performance.

Overall, I think this approach made sense to try out in a dynamically typed language like Scheme or Racket. The goal was to take existing programs and make them reactive, so the motivation was quite strong. My sense is that the implicit lifting approach may not be ideal even in that setting though, but I am not an expert at all on FrTime. I do know the approach was not used in Flapjax which came out of the same group a two years after the lowering paper.

I think type inference already can give quite confusing error messages, so I suspect that making something like this implicit would make that even worse. I suspect this would be a major challenge. I think it would be comparable to implicitly converting (sqrt [1,2,3]) to (map sqrt [1,2,3]) which gets a lot more confusing when there are many arguments.

Before embarking on a route like that, I guess I'd be curious what the goal is really. Perhaps the problem this is trying to address is that lift is an unpleasant name? I wonder how far we improve this just be calling it map?

--
You received this message because you are subscribed to the Google Groups "Elm Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elm-discuss...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Dénes Harmath]

This is a FAQ. :) See this thread for an extensive answer from Evan.

[Aaron Bohannon]

Thanks for the link! And thanks, Evan, for the explanation despite
the fact it's come up before.

I do have a practical case in mind, and I guess it would be best just
to focus on that. Since I have some experience with hardware audio
synthesizers, I was trying to determine how one would most naturally
express signal modulations in Elm. Abstractly, a signal modulator is
just a time-varying voltage, i.e., a function from time to a float,
but hardware patching lets you easily combine them in arbitrary ways,
with modulations each having parameters that can themselves be
modulated over time. In essence, your building one or more big
functions from (time -> float) out of smaller one from (time ->
float). But this pattern isn't at all specific to audio processing.
It's often exactly how you'd want to express animations, like this
one:

http://elm-lang.org/edit/examples/Intermediate/Physics.elm

So there's situations when the only signal you have is an `fps` and
everything is a function of time...except that you really don't want
to think about time or pass it around everywhere (which you will be
doing if you're building up smaller reusable "modulators"). It seems
like the language should be able to automatically turn your code into
a function that takes a time parameter. That's when I thought, oh,
well, why not let the language lift the signals for you, too?

I think the problems come when you have to account for the full range
of possibilities and implications that come from having event-based
signals, recursive functions, etc.

...Aaron

> --
> You received this message because you are subscribed to a topic in the

> Google Groups "Elm Discuss" group.

> To unsubscribe from this topic, visit
> https://groups.google.com/d/topic/elm-discuss/PNtOH2CDHZo/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to

[Kim-Ee Yeoh]

On Tue, Apr 22, 2014 at 7:23 AM, Evan Czaplicki <eva...@gmail.com> wrote:

Before embarking on a route like that, I guess I'd be curious what the goal is really. Perhaps the problem this is trying to address is that lift is an unpleasant name? I wonder how far we improve this just be calling it map?

A huge benefit would be elimination of syntactic noise. Less keyboarding, less un-readability problems, etc.

But I grant you that eliminating lift opens up different problems. The net effect could be negative. And yet this could be precisely the kind of 'worse is better' tradeoffs that doom nice projects like Elm to success.

Unreadability dooms people not touching your language with a 10-foot pole. Illiteracy is taboo, an event horizon for any kind of conversation.

Typing errors are more like 'flappy bird dies this round -- try again?'. With opportunities to ask on mailing lists, Q&A sites, etc.

p.s. A succinct 3-page summary of Burchett et al.'s work is here

http://cs.brown.edu/research/pubs/theses/masters/2007/burchett.pdf

-- Kim-Ee

[Jeff Smits]

I think using the operators (<~) and (~) already reduces syntactic noise.

I thought I remembered a discussion on the mailing list about automatic lifting within something like (| banana brackets |). I think that should still be feasible, but I'm not sure how different it would turn out from using the lift operators. The biggest difference would be not needing to use `constant`.

The lowering idea is basically a great, simple compiler optimisation; regardless for whether you auto-lift or not. But AFAIK the Elm compiler doesn't optimise much yet anyway. That's a summer internship thing.

--

[Daniël Heres]

I support the idea of calling lift map instead of lift used in FRP literature. This would be the same as fmap in Haskell.

[Gábor Menyhért]

Hi Evan, I'm pretty sure that the ugliest part of it is the indexed function names such as lift2, lift3, lift4 etc. It's unnecessarily cumbersome and since lifting is one of Elm's main characteristics, it really need a syntactic support instead of plain functions. (better than inference because it's explicit)

For example:

{Mouse.x + Mouse.y} => lift2 (+) Mouse.x Mouse.y

{sqrt Mouse.x} => lift sqrt Mouse.x

{{cos Mouse.x} + Mouse.x} => lift2 (lift cos Mouse.x) Mouse.y

And it comes in handy to convert non-signal values to constant signals:

{example Mouse.x 100 100} => lift3 example Mouse.x (constant 100) (constant 100)

The brackets visually make sense because it shows similarity of nodes in the signal graph.

You can use another ASCII characters, I don't exactly know whics are available in the language..

What do you think?

[Kim-Ee Yeoh]

On Tue, Apr 22, 2014 at 7:21 PM, Gábor Menyhért <gaz...@gmail.com> wrote:

For example:

{Mouse.x + Mouse.y} => lift2 (+) Mouse.x Mouse.y

{sqrt Mouse.x} => lift sqrt Mouse.x

{{cos Mouse.x} + Mouse.x} => lift2 (lift cos Mouse.x) Mouse.y

And it comes in handy to convert non-signal values to constant signals:

{example Mouse.x 100 100} => lift3 example Mouse.x (constant 100) (constant 100)

Yes! These are wonderful readability improvements.

(I think there's a typo in the cosine example which, as written today using lift2, would be: lift2 (+) (lift cos Mouse.x) Mouse.y.)

This is classic LISP notation, so old veterans would be happy.

But the rest of Elm supports infix a+b and why shouldn't code be written as spoken out loud? It's basically the sum of Y- and the cosine of the X-coordinate!

-- Kim-Ee

[Max Goldstein]

@Aaron: I agree that Elm should have a way to handle modulation well, since as you say it's a stone's throw away from animation. I'll point you to two different conventions, the "sum datatype" and "model transformer". The latter takes a few minutes to grok - you are foldp-ing function application over a signal of functions that have events on different timers.

@Dan: Sorry, but I'm against renamng it map. At least not until and if we have proper type classes or similar. Presently, thinking in general algebraic structures just isn't part of Elm. We map over data structures but doing the same to signals is a big leap for non-Haskellers.

@Gabor: As Jeff has mentioned, the infix operators help, as do higher order combinators. For example, area = (*) <~ Window.width ~ Window.height or area = uncurry (*) <~ Window.dimensions

[Evan Czaplicki]

The {x + y} idea is called "idiom brackets". That particular syntax would be problematic for parsing because of records, but I get the idea. It seems like there aren't a lot of good links on this, but this one is okay and it was originally described in this paper. I think we discussed this in more detail a while ago, but I remember the issues came with escaping in and out of auto-lift world.

[Aaron Bohannon]

@Max: Thanks for those examples.  I will have to look at them a bit longer to really get a feel for the patterns there.

I don't think that the difference between the words "lift" and "map" is significant.  And I don't think the <~ and ~ notations are really helping anything.  In some sense, they may reduce a *bit* of syntactic clutter, but I think they reduce readability by just as much, especially for newcomers.  Ditto for the use of generic higher-order combinators.  Succinctness can make code easier to understand, or it can have the opposite effect -- although, if our opinions differ on which it's doing in a given situation, debating isn't really going to help much.

However, I *really* like the "idiom brackets" idea -- in fact, I think it's a far better idea than my suggestion of implicitly lifting everywhere.  Not only does it have the potential to reduce a huge amount of syntactic clutter, but it also visually identifies expressions as having a signal type.

[Dandandan]

@Max: I agree that map should be only be considered when having type classes. I don't think a general functor map is much harder to understand than "lift".

I personally don't think (<~) and (~) are easy to understand for newcomers, I remember it was hard to understand the Applicative functions in Haskell, for newcomers they may appear as magic :).

Still thinking about the implicit lifting. I think implicitly lifting everywhere would be better than lifting by some syntactic sugar, but probably would need to see more examples.

Op dinsdag 22 april 2014 20:52:52 UTC+2 schreef Aaron Bohannon:

[Aaron Bohannon]

This topic came to my mind as I was thinking about hardware patching of music synthesizers, so I did a bit of investigation into languages aimed more directly at music synthesis to see whether they run into similar issues...and apparently they do.  There's a language called "Faust" [http://faust.grame.fr/], which is a "functional" language for describing signal graphs and compiling them to very efficient real-time signal processors.  (It even has a nice IDE that draws the graphs on-the-fly as you edit your code.)  The type system has no notion of lifted/unlifted expressions.  However, performance problems can easily crop up, despite the language's performance claims.  According to one user [http://westkamper.wordpress.com/2011/11/09/polyphonic-faust/]:

"Other performance issues are ... with Faust’s if-else equivalents. Non-active branches can only be skipped in Faust if they have no memory. Memory, or state, is involved if you use any kind of delays, either explicitly or via usage of recursion. The always-on philosophy needs to be taken into account on every level, if low CPU usage is a goal."

In fact, that whole blog post is basically a case study illustrating the problems Evan mentioned.  I think putting some sort of explicit acknowledgement of lifting in the language semantics would probably make potential performance problems easier to see.  Perhaps the idiom brackets should take a cue from LaTeX and use the $ symbol, which Knuth apparently chose as way of indicating "this is where the expensive stuff happens". :)

...Aaron