Change IsLambda* trait structure

[RadicalZephyr]

I think it would make more sense to bound all the IsLambda* traits with Fn instead of FnMut. I have tried out this change on my fork and it seems to be pretty straightforward to do.

For reference, the Fn trait requires that any variables a Fn is closed over must be immutable references, thereby putting up a barrier to mutation.

While usage of any type that grants "interior mutability" will allow a user to get around this limitation and break referential transparency, by using the Fn trait we provide at least a safety check that the user isn't accidentally mutating something.

There are a few places I believe where IsLambda is now being used that actually should allow mutation (anything in the operational side of things I would imagine), and so I think it would make sense to also add corresponding IsLambdaMut and IsLambdaOnce traits to mirror the trio of Fn* traits.

[RadicalZephyr]

Also, the reason I started looking into this change is that I was looking at #46. With this change to IsLambda* it should be possible to actually make that happen in a straightforward way because the passed in function can be immutably shared.

[clinuxrulz]

Sorry I've taken so long to reply. Just been terribly busy.

There is a good reason for the FnMut over Fn.

In the "Denotational Semantics":
https://github.com/SodiumFRP/sodium/blob/master/denotational/Denotational%20Semantics%20of%20Sodium%20-%201.1.pdf

There is an extra method only found in the Haskell version of sodium. execute :: Stream (Reactive A) -> Stream A which permits executing side effects in the current transaction and passing the result of that side effect in that transaction. The execution time of the side effect will hold up the whole graph, so it should only be used for light weight side effects (such as updating a collection). Other side effects should be done asyncroniously.

So sodium Streams are like a superset of a functor, which has the addition of permitting mutation within a lambda through something like map. However the end-user can choose to stick to the pure lambdas if he/she wishes too.

A special use case is squeezing more performance out of collections. Instead of having collections being updated in O(log(N)) time at best. You can update collections in O(1) time without breaking the denotational semantics.

pseudo code example:

let myEntities = HashMap::<Entity>::new();
let cEntities = sChange.map(move |change| { /* apply change to myEntities */; return myEntitys; });

In the example above. cEntities can perform an update to the collection in O(1) time instead of O(log(N)) as with a immutable collection. Futher usages of cEntities in other combinators will receive a &HashMap<Entity> which Rust's type system will not allow the user to alter the contents and if the user wants to hold onto the data via collect etc. then they will need to copy/clone the data (defensive copying forced on user). So it is safe to do this, and indistinguishable from the immutable collection version in how it operates.

There are a few more bugs I've discovered in this version that I have not had time to fix.

I've been doing an alternative C++ version as well with fully automatic memory management implemented the same way as this Rust version: https://github.com/clinuxrulz/sodium-cxx-alt . And while doing that I've discovered bugs I'd expect to be in this Rust version too as the implementation is identical. The C++ version has the tests copied over from the original C++ version where the memory management is not quite right yet, and the C++ version had a few more tests that are missing from the Rust version that I'd expect to fail.

And I'd really like the tests in a single file too like "sodium_test.rs". It did not make sense to break down the tests in separate files like I've done. And then go through the C++ version code and add the missing tests to eliminate the remaining bugs.

Although the sodium objects hold a lazy value, that value should be evaluated/unboxed at the end of transaction to insure any side effects get executed in the transaction even if not listened too. (cEntities above should always have the correct value even when cEntities is not listened to.)

I can see in your fork you've done a few other changes too, they can be useful here and I'd like to merge some of it.

If you'd like to help me out some more and have the free time, I'd like some more of the tests from https://github.com/clinuxrulz/sodium-cxx-alt/blob/master/tests/test_sodium.cpp added to this Rust version.

I remember Cell::value needed a small fix. Here is the fix in the C++ version that needs to be applied to the Rust version.

clinuxrulz/sodium-cxx-alt@549da61

Basically I was not meant to use post, but instead send the current value of the Cell in the same transaction. And I believe a few lazyness bugs will exist with switchS / switchC that I've found and fixed in the C++ version due to the additional tests that helped me find the bugs.

Any additions to the exposed API will bump up the 2nd number in the version x.ThisOne.x. Any changes to the existing API will be changing the 1st number in the version ThisOne.x.x. So if we decide to change all the lambdas from mutable to immutable for whatever reason, then it will have to wait for version 3.

[RadicalZephyr]

Ah, that makes sense! I guess if I'm going to work on Sodium I should probably read and understand that "Denotational Semantics" appendix.

I would be happy to help out, I'm definitely interested in using sodium-rust for a few projects and I would love to help out. I'll separate out the other fixes on my branch from the lambda change and submit those as a pull request and take a look at porting and re-organizing the tests.

[RadicalZephyr]

I submitted a couple PRs with conceptually distinct sets of changes I've made on my fork. If you don't mind, I think I will also take your above comments and make issues for each of them to track the work on each individually.

I also have been thinking about the usage of Fn versus FnMut more, and I think that adding an extra hoop to jump through in order to do mutation inside of a sodium function like you describe would be valuable. As I mentioned in my first comment, a user could still do the kind of mutable update to a collection that you describe wanting to allow, they would just have to wrap their type inside an Arc<Mutex<...>> in order to do mutation inside one of the functions in an ostensibly side-effect free context. This could then transparently return an immutably borrowed version that doesn't expose the Mutex to other parts of the code. At least I'm pretty sure this would work, I'll have to experiment with it a bit to make sure.

This change would also be in keeping with Rust's general design ethic of being safe/immutable by default but allowing mutation, or unsafety escape hatches with more explicit syntax. I think there could be room for adding a new helper function to facilitate the boilerplate related to using this pattern for mutable update. As you say, that would definitely be a breaking change to the API so I'm not in a rush to make it.

I also think there is another breaking change that could result in a significant improvement in using Sodium. I believe the IsLambda* traits block type inferencing from working as it normally does when passing closures to functions that use those traits as a bound.

It looks like part of the reason for having the IsLambda* traits is to allow retrieving the dependency information from them with the deps_op method. A more idiomatic Rust trait design would probably be to have that method be in a separate trait, let's call it Deps, which could then be implemented for both the Lambda types and for the built-in Fn types. Then the places where IsLambda is used as a bound could use a combined bound of Fn(...) + Deps and this would (I believe) make type inferencing work correctly on closures passed to sodium methods.

I think related to this change, there is another benefit to using the Fn bound instead of FnMut. The other obvious thing that I can see the IsLambda traits currently do is enforce that all the arguments to the FnMut closures are passed as immutable references (which, side-note, I wonder if this might block implementing the collection mutation pattern you presented earlier? more tests!). By using Fn we get this bound automatically and can take away the & in the Fn bounds, which I think might actually be the source of the type inferencing problem.

[clinuxrulz]

I'm happy for you to add additional issues.

Might just need a little more thought for the inference. Rust's iterators from the std handle type inference on FnMut with no problems and they can process references to each of the elements too instead of copy of element passed to closure.

The next node in the graph receiving a immutable reference to the collection in the mutual collection example is for safety. It's like the one node in the graph takes ownership of the mutable state of that collection. And each node in the graph should only be able to mutate its own state then afterwards the state should remain unchanged for the lifetime of the transaction so all other dependent nodes all see the same state for that transaction. Accepting a non reference type in the input to a lambda would cause a copy of the collection defeating the O(1) making it O(n) due to the copying for dependent nodes to witness the new value of the collection.

It seems it is the dependency tracking causing the issue with the type inference. Maybe FnMut + Deps is a work around, not sure. Still would be a change to public API. No choice but to go v3 for inference. Which is OK with me, inference improves readability.

[clinuxrulz]

One question just came to mind:

Will Rust let us implement Fn or FnMut for our own types anyway? Such as Lambda. Last time I tried, Rust would not let me. Admittedly I was on an older version of Rust at the time.

[clinuxrulz]

I just realised since my lambdas are returning a non-reference type, I'd have to use Arc<Mutex<...>> or Arc<RwLock<...>> on collection types anyway for the mutable collection trick to remain O(1). Which can already be passed to Fn.

So I'd be happy to go from FnMut to Fn.

I'd also be not too fazed if lambdas accepted non-referenced types as inputs (especially if it helps with type inference). As using references can often cause a cache miss on the CPU. And if the user knew they had a structure that was expensive to copy, then they can always wrap it in a Arc<...> to pass along.

[RadicalZephyr]

Will Rust let us implement Fn or FnMut for our own types anyway? Such as Lambda. Last time I tried, Rust would not let me. Admittedly I was on an older version of Rust at the time.
@clinuxrulz

ooh, that is a very good question. perhaps not. another thing that would need to be experimented with.

[clinuxrulz]

Another option to keep dependency tracking and type inference is to make twins for all the API methods.

E.g.

fn map<FN:Fn(A)->B>(&self, fn: FN) -> Stream<B>

fn map_w_deps<FN:Fn(A)->B>(&self, fn: FN, deps: Vec<Dep>) -> Stream<B>

Just a bit painful with all the boilerplate.

[RadicalZephyr]

Hmmm, boilerplate can be solved with a macro, but I wonder how much complexity calling the two methods would add internally?

I'm discovering that this is a substantially harder problem to solve than a naively thought when I first posted (in hindsight this probably should not have been a surprise). I have a few other directions that might pan out, but I think I may have to seek from more experienced Rustaceans on whether it's possible to do what I'm aiming for and how to implement it cleanly. It might also be the case that the issue with type inference is not coming from the trait indirection of the IsLambda* traits, but actually the & restriction on the arguments, I'll keep exploring and hopefully come back with some more concrete ideas.

[clinuxrulz]

Have not had a chance to get on a computer yet. Just stuck on mobile phone. I wonder if hinting to the compiler a variable is a reference would help the type inference.

E.g.

    let s2 = s1.map(|&x| *x + 1);

Notice the & to say it is a reference, but still not providing the type of x

Edit: tested on Termux Linux terminal for Android. The & did not work.

Have a look at the Fn trait implementation for Box<Fn>

https://doc.rust-lang.org/src/alloc/boxed.rs.html#1020-1024

So maybe we can define Fn impls for our own types. Just might be a bit unstable with Rust version changes.

[clinuxrulz]

https://blog.rust-lang.org/2019/05/23/Rust-1.35.0.html

Actually looks like it is a stable feature. We can implement Fn for our own types since Rust v1.35.0.

What is interesting is:
Fn(A) <-- lambda with 1 arg
Fn(A,B) <-- lambda with 2 args
Fn<A> <-- lambda with any number of arguments all represented by the type A (notice the arrow brackets)

[RadicalZephyr]

I think that the change in 1.35 is actually just implementing the relevant traits for boxed versions of the various Fn types. It looks like it is possible to implement the fn traits, but it's currently behind an unstable feature flag which would mean that using sodium would require using a nightly compiler which is not super nice for users. Doesn't really look like it's even ready to be stabilized any time soon so probably best not to depend on that route.

[clinuxrulz]

Thanks for clearing that up. Just have to experiment a bit.

Having the twin methods as a option is no big deal internally. It's just delegating the "non with deps" method calls to the "with dep" ones carrying an empty Vec of deps.

[clinuxrulz]

I had a crazy idea once, not sure how workable it is.

The idea is to execute clone on a lambda, then work out which sodium object just had their reference count increased. That way you can work out which sodium objects are referenced in a lambda without the end user telling the library.

[clinuxrulz]

This works:
let s2 = s1.map(|x: &_| *x + 1);

It infers the type of x, but you still need to say it is a reference type (&_).

It means type inference should work fully (no type hints), if the IsLambda did not use & on its input types. Which is not a big deal, the user can wrap any expensive to copy types in Arc<..>.

[RadicalZephyr]

Oh, that's really good news. I didn't even think to try that abbreviated inferencing!

I think in general since most values are already passed by reference removing the &s on the arguments in the IsLambda actually won't change anything, because T and &T are different types that are both valid to be inferred as the type of an argument.

And if in 3.0 we change the FnMut to a Fn we'll get the same guarantee of not being able to mutate the arguments without using interior mutability that the current usage of & in the signature enforces.

[clinuxrulz]

Without the & the arguments are passed by copy. (Defensive copy). So mutation of the arguments does no harm. Both Fn and FnMut will let you mutate that copy of the arguments.

It's really passed by move, but since we want to keep the value/state in the sodium object we have no choice but to copy/clone. Making it pass by copy for the arguments.

fn main() {
    let x = 4;
    let y = |mut x| x = 5; // <-- y is Fn, not FnMut
    let z = move |f: &dyn Fn(u32)| f(x);
    z(&y);
    assert!(x == 4);
}

The only real difference between Fn and FnMut is that FnMut lets you mutate captured state. Which allows FnMut to return a different result each time it is executed with the same arguments.

[clinuxrulz]

https://docs.rs/serde_closure_derive/0.3.1/src/serde_closure_derive/lib.rs.html

Shows how to create a macro that can visit the captured variables in a closure. And it works on stable.

So it should be possible to create a lambda! macro that does not require the user to list the captured sodium objects.

E.g. let s2 = s1.map(lambda!(move |x| ca.sample() + x));

And lambda! above can work out that ca was captured.

Or even a get_deps! to use on regular closures and eliminate the need for IsLambda/Lambda altogether.

---

Maybe no need for this technique just yet. The example from serde seems quite complex. Worried if it would keep working as the Rust language changes over time.

[RadicalZephyr]

Without the & the arguments are passed by copy. (Defensive copy). So mutation of the arguments does no harm. Both Fn and FnMut will let you mutate that copy of the arguments.

It's really passed by move, but since we want to keep the value/state in the sodium object we have no choice but to copy/clone. Making it pass by copy for the arguments.

The only real difference between Fn and FnMut is that FnMut lets you mutate captured state. Which allows FnMut to return a different result each time it is executed with the same arguments.

Ah, you are totally right. I got a little overexcited about that idea and didn't really think it through.

I think my thoughts on this API change are pretty half-baked right now, and not really grounded in how sodium is actually implemented currently or what the goals are, though this discussion has certainly been making things clearer. I think I'll keep working on porting tests and fixing any bugs that they expose in the implementation and getting more experience working in the codebase that way.