Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Activity
    Dylan Ede
    @dylanede
    Hi Matthew, I've tried experimenting with Adapton. I was wondering if you could help me understand the output of a little program I've made. You can see it and its output at https://gist.github.com/dylanede/63d95a146bef23d6066f46c2ab4e1228. It is meant to be an implementation of a basic binary tree, with the output of a lookup getting updated as the tree is modified. It seems that an insert in the tree is causing a lot of recalculation for a lookup, indeed for insert depth l, O(l^2) node comparisons are performed to update the lookup (which is worse than a non-incremental version), when in this case I was expecting just one (or maybe two).
    Dylan Ede
    @dylanede
    @matthewhammer ?
    Matthew Hammer
    @matthewhammer
    Hey @dylanede! I wrote a response on github yesterday, but I forgot to put a note here. Sorry for the delay:
    https://gist.github.com/dylanede/63d95a146bef23d6066f46c2ab4e1228#gistcomment-2221595
    In hindsight, I should have written that comment here, not in the gist.
    Dylan Ede
    @dylanede
    Ah, thanks Matthew! I'll try out your suggestions and see what happens.
    Dylan Ede
    @dylanede
    Also, @matthewhammer, I'm slightly concerned by the statement in the adapton-lab readme that using adapton incorrectly can lead to memory faults. Does that mean that through entirely safe (in the Rust sense of memory safety) use of the API, undefined behaviour can be invoked? I'd much prefer if adapton instead did exhaustive runtime checks for incorrect usage and panicked with a helpful error message if necessary.
    Matthew Hammer
    @matthewhammer
    Great question!
    @dylanede I’ve sinced fixed the memory fault issues (mostly); if it becomes an issue for you, please let me know and I can apply the fix completely. It’s currently not an issue for us, so I haven’t prioritized fixing it
    Basically, the issue is that “names” in Adapton let the programmer choose "pointer addresses” (unique IDs), and if they use the same name at different types, unexpected behavior can ensure. To address this (since writing that README, which is outdated a bit), I’ve been using type IDs to dynamically check the otherwise unsafe casts in the Adapton engine.
    BTW: Sorry for my slow responses..it’s been a busy semester
    Matthew Hammer
    @matthewhammer
    Regarding the “incomplete fix” mentioned above:
    The most common cast problems are now checked dynamically, using Type IDs. I think there may be one less common case that does not perform this check, however.
    We are in the process of implementing a language with its own type system to avoid these dynamic checks:
    Here’s the theoretical idea: https://arxiv.org/abs/1610.00097
    Here’s the implementation, a work in progress: https://github.com/cuplv/iodyn-lang.rust/blob/master/tests/quicksort.rs
    The idea of the IODyn language is to be an embedded DSL (in Rust) for writing programs that use Adapton, and dynamic collections
    ousado
    @ousado
    Hi - I just learned about adapton's existence and I'm very pleased to find (in rust ) what seems to be one of the most evolved incremental computation libraries/approaches - An immediate thought/question is how adapton and the incremental library from jane street compare
    jomi-se
    @jomi-se
    Hello everyone :wave:
    I'm interested in the same points as @ousado . I just found this after being told about Jane Street's incremental. I had no idea what incremental computation was up to this point and it appears to answer my use-case very nicely. However, I saw that in incremental cycles in the dependencies graph are not allowed, whereas in Adapton there is a way to inject a way of handling cycles (https://docs.rs/adapton/0.3.30/adapton/#dcg-cycles-detection-and-valuation). Did I understand this difference correctly?
    jomi-se
    @jomi-se
    Additionally, what would be a good starting point to learning more about the implementation of incremental computation?
    Matthew Hammer
    @matthewhammer
    Hi @ousado and @jomi-se ! Thanks for your questions!
    (BTW: Sorry for not responding sooner!)
    Matthew Hammer
    @matthewhammer
    @ousado Great question! Here's a very technical, detailed answer, giving at least one point of contrast: https://gist.github.com/khooyp/98abc0e64dc296deaa48
    In particular, that gist illustrates how JSI (Jane Street's "Incemental" library) uses a different reevaluation strategy than Adapton.
    Here's a similar example in Adapton in Rust (the current implementation of Adapton):
    https://docs.rs/adapton/0.3.30/adapton/#demand-driven-change-propagation
    Matthew Hammer
    @matthewhammer
    @jomi-se Regarding the implementation of IC:
    I'd be happy to answer questions about the implementation of Adapton. The bulk of the implementation consists of its "engine" for building and maintaining the DCG.
    It's in a module called engine: https://docs.rs/adapton/0/adapton/engine/index.html

    If you want to see the engine in action, with examples, I'd actually recommend starting with Fungi: https://github.com/Adapton/fungi-lang.rust

    The macros of the Adapton Rust library have evolved into a new programming language, within Rust, with its own syntax and type system. Under the hood, its interpreter uses Adapton as an external library: https://docs.rs/fungi-lang/0/fungi_lang/reduce/index.html

    Matthew Hammer
    @matthewhammer
    So, in summary, as a "first step", I'd recommend cloning the fungi-lang.rust repo above, and running cargo test, which will generate a bunch of output that illustrates how Adapton supports Fungi programs that evaluate incrementally. Of course, Fungi is written in Rust, so the same ideas transfer beyond Fungi, to other Rust programs (that aren't necessarily new PLs).
    Matthew Hammer
    @matthewhammer
    Announcement:
    Moving to Zulip for the future:
    https://adapton.zulipchat.com/login/