milibopp/carboxyl

Functional Reactive Programming library for Rust

carboxyl's Issues

Nested transactions

Currently, nesting transactions leads to a deadlock because of the single transaction mutex. This prevents certain useful usage patterns and is therefore considered a bug.

Improve the callback mechanism

Internally this crate currently has a triple (in some places quadruple) pointer indirection. This was done to work around certain limitations of the type system.

For instance, the registry of callbacks essentially requires boxing a trait object (Box<Listener<A> + 'static>), since there is an infinite number of types that must be able to register (e.g. maps are generic over their output type B in addition to A). However to build up the mechanisms for keeping the dependency graph of a stream or cell alive, one also has to put stuff into an Arc<RwLock<…>>. Then at some places more information than Listener<A> is required, thus there are different ways of wrapping objects in weak/strong reference and/or trait object containers.

So, in essence, the whole thing is a bit messy and should be cleaned up. This could have some benefits:

• The internals should be easier to reason about and maintain.
• Less pointer indirection typically means less cache misses in real life applications.
• Less reference counting could make sending an event down the dependency graph faster, too.

The latter two points probably require some benchmarking to confirm. How this could be done, may become more obvious in the process of reviewing and documenting the internals (see #4).

Implement never

Just a shortcut for Sink::new().stream().

Properly implement a transaction system

This is a plan to implement a transaction system to ensure that effects of events to not overlap inappropriately.

• Step 1: Implement sequential transactions using a global lock. This ensures the semantics to be correct first. (see PR #13)
• Step 2: Use software transactional memory (STM) to achieve concurrent transactions. This is important for performance at some point, but may be quite a large implementation effort.

Original post

To provide stronger guarantees on how events are ordered, a transaction system should be implemented. This needs some research though.

Sink::feed methods should take IntoIterator

Provide examples in readme and documentation

Create stream from an IntoIterator type

Essentially, impl<T> FromIterator<T> for Stream<T>. It should be clear that this will not consume the iterator directly but rather spawn a background thread to do so.

Rename `scan` to `fold`

This is a complete misnomer, and I only realized this now. o.O

Does not compile on current rust git

Compilation fails due to the api change in commit
rust-lang/rust@dfa4bca.

The solution is to change lines like let weak = src.downgrade(); to let weak = Arc::downgrade(&src);.

This should probably be changed when the next rust nightly is released. Or if possible it would be good to support both versions of rust, but I don't know rust well enough to know if that is possible.

Change argument sequence of scan closure

Should be .scan(init, update) where update: Fn(A, B) -> B

Allow non-Clone types

Currently all values passed into a sink to be processed by the event graph, have to satisfy quite a number of trait bounds, namely Send + Sync + Clone. Passing an object down the event graph is achieved by cloning. This is not optimal for larger heap-allocated types, say a Vec or a HashMap, where cloning is expensive. This can be alleviated by wrapping those types in an Arc, so that only references will be sent down the event graph. However, this is a bit clumsy to work with.

Using Arc

As an alternative we could use Arc internally for all values. Functions passed to the primitives would then have to take their arguments by reference and similarly .sample() and .events() would yield references.

On the upside, working with cells and streams would become more ergonomic, as one would not have to think about expensive cloning of each event sent into a stream. It also drops the Clone bound on the type of an event.

The downside is, of course, that this constitutes a bit of an unnecessary overhead for small types. But then again, the library currently uses a lot of atomic ref-counting, vtable dispatch and pointer indirection. One more indirection would likely not be that harmful.

Document the internals

Even though they are not pretty, or maybe exactly because of that, the internals should be documented.

Marble support

See RxMarbles. Some API that allows easy creation of scheduled event sequences without explicitly spawning a thread and feeding a Sink. Maybe as a separate crate.

Test the usage examples in the readme file

These ought to be continuously integrated as they were forgotten to be updated more than once. Maybe a build.rs could do this.

Acceptance Criteria

• The code examples in README.md should be run on Travis CI
• The examples should still be concise enough to be helpful for documentation purposes

Test algebraic laws of primitives using Quickcheck

This would be really nice to have to test the current implementation as thoroughly as possible. Requires a couple of issues to be resolved:

• Generate arbitrary streams and signals in a sensible manner.
• Generate test functions, as the algebraic laws often hold for any function.
• Test streams and signals for equality. (Fully implementing PartialEq or Eq is not feasible, but one can probe them for a while to see, whether they yield similar results.)
• Within a transaction sampling a signal should always yield the same value.
• Test that Signal and Stream are monoids, (applicative) functors and monads. (See push-pull paper for this.)
• Specify and test in how far SignalMut and Signal are equivalent.
• Specify and test the subset of algebraic properties implemented by SignalMut.

Note: marked items have been implemented & merged.

Comparison to Sodium?

This library looks very cool! Really exciting to see this possibility :D

How does it differ from Sodium, given the work-in-progress push-pull Rust port? https://github.com/clinuxrulz/sodium-rust-push-pull

Consistency with standard library conventions

There are a number of precedents in the standard library and the new conventions RFCs, that should be followed by this library.

Specifically, the semantics of the iterator extension trait should be mirrored by stream adaptor methods as far as it makes sense.

Implement hybrid push/pull semantics

See this paper by Conal Elliott for reference. The general idea to see cells as a sequence piecewise continuous functions of time makes sense.

Contrary to Elliott, time will not be handled explicitly but rather implicitly by the sequence of transactions. Also the implementation itself will be inherently imperative, as the purely functional, lazy evaluation approach is not feasible in Rust (too much boilerplate to emulate Haskell features).

Cyclic SignalMut definition

Is it possible to implement a function analogous to Signal::cyclic for SignalMut? Alternatively, is it possible to define SignalMut recursively using today's API?

Document public API

Can't compile crate with rust 1.2

What rustc version (compiler flags?) do you need?
I'm trying with 1.2 stable, and have following errors:

C:\temp\rust-carboxyl-master\carboxyl-master>cargo build
    Updating registry `https://github.com/rust-lang/crates.io-index`
 Downloading rand v0.3.11
 Downloading quickcheck v0.2.23
 Downloading log v0.3.2
 Downloading winapi v0.2.2
 Downloading lazy_static v0.1.14
 Downloading libc v0.1.10
 Downloading winapi-build v0.1.1
 Downloading advapi32-sys v0.1.2
   Compiling lazy_static v0.1.14
   Compiling carboxyl v0.1.1 (file:///C:/temp/rust-carboxyl-master/carboxyl-mast
er)
src\lib.rs:136:1: 136:29 error: #[feature] may not be used on the stable release
 channel
src\lib.rs:136 #![feature(arc_weak, fnbox)]
               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
error: aborting due to previous error
Could not compile `carboxyl`.

To learn more, run the command again with --verbose.

Pass streams and cells by value or reference?

Working with a couple of streams and cells, I found that I usually use a primitive only once to build up more complex event graphs from it.

I think there is an argument to be had, whether they should maybe be passed by value, instead of by reference, which is the status quo. This is just an idea, I am not really sure that this is the right way to go.

Semantically, they are pretty much equivalent, as both streams and cells can be cloned (and still respond to the same events as before).

Consider the following code:

let cell_c = lift!(|a, b| a * b, &stream_a.hold(3), &cell_b);
let cell_d = cell_c.snapshot(&stream_a);

Essentially I am thinking about this as an alternative:

let cell_c = lift!(|a, b| a * b, stream_a.clone().hold(3), cell_b);
let cell_d = cell_c.snapshot(stream_a);

Allow non-'static lifetimes

This is currently a fairly significant limitation of this crate. Only types T: 'static are allowed for streams and signals. It should in principle be possible to lift this restriction but it might require some tweaks to the implementation. Also, not all parts of the API can work that way. For instance, one cannot feed a sink non-statics in a detached background thread. But the borrow checker should take care of such limitations.

Concurrent transactions with Software Transactional Memory

Since merging #13 carboxyl has only very shallow concurrency, as all transactions must acquire a global lock to function.

As advised in the discussion in #6, Software Transactional Memory is most likely a better way to do the event dispatch.

Excessive cloning in Stream::fold

Tried to implement something that accumulates all the stream values into a Vec using Stream::fold, but found that it clones the accumulator values multiple times during it's operation. Example code:

extern crate carboxyl;
use carboxyl::Sink;
use std::fmt::Debug;

#[derive(Debug)]
struct Storage<T>
{
    vec: Vec<T>,
}

impl<T> Storage<T>
{
    fn new() -> Self
    {
        Storage{ vec: Vec::new() }
    }

    fn push(mut self, item: T) -> Self
    {
        self.vec.push(item);
        self
    }
}

impl<T: Clone + Debug> Clone for Storage<T>
{
    fn clone(&self) -> Self
    {
        println!("storage cloned! {:?}", self.vec);
        Storage{ vec: self.vec.clone() }
    }
}

fn main()
{
    let sink = Sink::new();
    let signal = sink.stream().fold(Storage::new(), Storage::push);

    sink.send(11);
    sink.send(22);
    sink.send(33);

    println!("result: {:?}", signal.sample());
}

output:

storage cloned! []
storage cloned! []
storage cloned! [11]
storage cloned! [11]
storage cloned! [11]
storage cloned! [11, 22]
storage cloned! [11, 22]
storage cloned! [11, 22]
storage cloned! [11, 22, 33]
storage cloned! [11, 22, 33]
storage cloned! [11, 22, 33]
result: Storage { vec: [11, 22, 33] }

Don't know if I'm using it wrong, but this seems pretty inefficient. A fold operation shouldn't require cloning the accumulator.

Add more exhaustive benchmarks

Carboxyl's current performance should be assessed more thoroughly. There is a repo listing a couple of benchmark scenarios.

Return intermediate values from `Signal::cyclic`

Currently it is a bit hacky to return an intermediate value from inside the defining closure passed to Signal::cyclic. There should be a more convenient alternative API method to do this.

Rename Cell to Signal/Behaviour

This is a bit of bike-shedding, but the current terminology has some issues:

• It is a bit confusing given the existence of the Rust standard library Cell and RefCell types
• A Cell seems to contain a certain value (also because the first reason), which carries a discretized notion of the FRP concept. This is likely also the reason why Sodium has adopted this name. With #52 this will no longer be suitable for Carboxyl.

Alternatives

Previously both Carboxyl and Sodium used Behaviour. There is also Signal as an alternative. Personally I like Signal better, but Behaviour appears to be more established.

Allow easier asynchronous sends

An asynchronous send into a sink currently means moving the sink into a newly spawned thread and performing the send in there. The library should provide a direct way to do so.

Use Result<(), EquivError> as return type for stream_eq

This can be done, as soon as quickcheck has released the most recent PRs (BurntSushi/quickcheck#79, BurntSushi/quickcheck#80) on crates.io.

Mutable scan for efficient in-place updates

The current signature of Stream::scan goes roughly like this:

pub fn scan<B, F: Fn(B, A) -> B>(&self, initial: B, f: F) -> Signal<B>;

An alternative would be to allow something like this additionally:

pub fn scan_mut<B, F: Fn(&mut B, A)>(&self, initial: B, f: F) -> Signal<B>;

The obvious advantage is the abstraction of efficient in-place operations, which are not possible at the moment (without depending on implementation details). It's probably be a good idea to address this along with #26.

A practical example of a project that would benefit from that is PistonDevelopers/conrod#400. Generally speaking it allows imperative APIs to be used in conjunction with carboxyl.

Relicense to MPL 2.0

Dear contributors (i.e. @Moredread, @killercup, @tilpner and @llogiq),

Would you agree to re-license your contributions to Carboxyl under the Mozilla Public License Version 2.0?

To provide some context just in case, anyone of you has not read this: I started a conversation about creating a reactive ecosystem based on Carboxyl. During that discussion it turned out that a lot of people consider LGPL problematic to use for Rust code, as it limits usage in proprietary software too much. I have been convinced that my original intention to make proprietary users contribute bug fixes & improvements back upstream is better implemented using MPL 2.0.

Of course, in order to change that, we need to have a consensus among contributors to change the license. Please state your opinion on that, and if you are fine with it, explicitly say: I hereby consent to make my contributions to Carboxyl available under the Mozilla Public License Version 2.0

Implement coalesce

From the Sodium docs:

coalesce :: (a -> a -> a) -> Event r a -> Event r a

If there's more than one firing in a single transaction, combine them into one using the specified combining function.

If the event firings are ordered, then the first will appear at the left input of the combining function. In most common cases it's best not to make any assumptions about the ordering, and the combining function would ideally be commutative.

That would translate into Rust as a method of Stream<A>:

fn coalesce<F: Fn(A, A) -> A>(&self, f: F) -> Stream<A>;

Merge streams with function

Would it be possible to have a function which merged two streams using a combining function?

The particular case which I have is that there is a Stream<A> and a Stream<B> and I need to merge them to create a Stream<(A,B)>

I imagine writing something like

let s1: Stream<A> = ...
let s2: Stream<B> = ...

let m : Stream<(A,B)> = fMerge(|a,b| (a,b), s1, s2);

Thanks

Robert

Interop with reactive in other languages?

I was wondering, how feasible it is to use this library in a custom business logic library (written in Rust), which is meant to be used in an interface-specific environment - say an iOS Swift app, which also use reactive (e.g. rxswift)?

The idea would be that the business logic library exposes observables (and other things) which can be somehow observed / composed in the apps.

* I'm a Rust newbie - I know this is a very broad (and maybe difficult) answer, just want to get an idea of the possibilities even if it's very vague.

Test semantics of SignalMut

Acceptance criteria

• Specify and test in how far SignalMut and Signal are equivalent.
• Specify and test the subset of algebraic properties implemented by SignalMut.

Perform all cell updates at the end of a transaction

Infinite loops currently happen in cyclic cells under certain conditions. This is most likely the way to avoid it.

status of the project and functional programing in rust ?

did it died ?

Add Signal::map

Lifting single signals effectively provides functor semantics. As such, there should be a map function. This should also improve ergonomics, as one does not have to think about whether one is working with a stream or a signal.

Allow lifting of n-ary functions

There is only lift2 right now. It is probably possible to do this generically, so that there is one generic function lift deprecating lift2. This will likely involve using a recursive macro to implement it for a finite but arbitrary number of arguments. Quickcheck has done something similar.

• Generic lifting for a few low arities (say, up to 4)
• Use a completely arbitrary arity

Make some pretty pictures for the docs

Revise `scan_mut`

In its current state scan_mut does not work particularly well, as it has subtly different semantics and allows one to side-step the abstraction provided by functional reactive programming, when used incorrectly. This must be fixed.

The concrete issue: If one propagates the result of scan_mut through further streams and signals, it will always reflect the status quo, as it remains a reference to the very same memory location. A possible solution would be to disallow this propagation by providing a separate interface with by-ref semantics for this kind of signal without exposing the underlying memory model.

Allow looping

• Looping of streams.
• Looping of signals. How is this supposed to be defined?

Edit: terminology cell -> stream, stream -> signal

Write a readme

Deal with dynamic switching more explicitly

The result of creating new events and signals in Carboxyl depends on when it is done. This is necessary to avoid space-leaks, i.e. memorizing the entire history of these objects. By design of the implementation, Carboxyl cannot memorize this, as it does not rely on a garbage collector to clean it up, but rather only has one memory location, where the current value of a signal is stored.

However, this behaviour could be expressed more explicitly. At the moment the semantics of an expression implicitly depend on when it is executed, which is somewhat undesirable. The API would have to be changed to allow this, so this is something to be considered for version 0.2.

The main offender is snapshot. In the paper on FRPNow (see below) it is argued that this could be alleviated by not returning the stream/signal directly, but rather a signal containing it to make the dependence on evaluation time explicit.

Background infos

• FRP - Dynamic Event Switching, Heinrich Apfelmus
• Practical Principled FRP (FRPNow), Atze van der Ploeg & Koen Claessen

Remove SignalMut

I have strong doubts, that the semantics of SignalMut are solid. Also, it is much cleaner to interface with a mutable component of the application, as one would interface with other services. That is, by listening to event streams, polling from signals and feeding into sinks.

Cells should depend on old state

In order to make loops, accumulators and such work, sampling a cell during a transaction must return its value before the transaction. Currently it is undefined, whether any samples of a cell during a transaction see the old or the new value.

Implement stream switching

At the moment one can only switch between cells, not between streams. This should be straightforward to implement.

No weak pointers?

According to @acrichton weak pointers won't be stabilized for 1.0. Internally this crate makes heavy use of them, so it is unlikely that it will be ready to use for 1.0.

Ideas to get around this

• Shipping own Weak<T>: Would not be exposed, so could be done as a mere implementation detail. Also fairly easy to do (just copy & paste from stdlib).
• Lifetime bounds instead of ref-counting: Good for performance, but it might make the library slightly harder to use, as this will propagate into the API. This approach is radically different and goes into afaik unexplored terrain for FRP libraries. Requires some experimentation.

Test panicking behaviour

It is currently not well tested, how the primitives behave when functions panic.