1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
/*! Fungi standard library. Based on collections in these papers: - **Nominal memoization**: [_Incremental computation with names_, **OOPSLA 2015**](http://arxiv.org/abs/1503.07792). - **Type and effect structures**: The draft [_Typed Adapton: Refinement types for incremental computation with precise names_](https://arxiv.org/abs/1610.00097). */ #[macro_use] /// Vectors pub mod vec; /// Chunks: named, referenced vectors. pub mod chunk; /// Sequences, as balanced level trees. pub mod seq; /// Linked lists. pub mod list; // Proposal: // // ast::Module has a vector (or linked list) of DefType, DefVal and // DefFn forms, and nothing else. DefFn form is essentially // `Let+AnnoC+Fix`, but in a proper form of its own, to make it nicer // when we use tools to see the AST output. Given all of this, we can // remove the exp::DefType form, which we no longer need. // // fgi_mod!{ ... } // ==> // pub fn fungi_module () -> ast::Module { fgi_module![ ... ] } // // --- OLD ------------------------------------- // # Sequences in Fungi: // ## Linked lists vs Level trees // In most functional languages, **linked lists** play a central role in // organizing sequential data, the way that arrays play a central role in // imperative languages. // In Fungi, computations have the potential to be incremental, and as a // result, we reconsider the role of linked lists in our functional // programs. In Fungi, linked-lists represent "iterators" --- lists // sometimes organize sequences as their are processed or transformed --- // but in Fungi, lists not the data structure for storing or editing that // sequence data, or for aggregating it with folds or other iteration // patterns. // Instead, to organize sequences for accesses, updates or incremental // folds, Fungi programs use balanced **level trees**. In particular, // before we iterate over a linked list, we create a balanced level tree // from its elements to better organize later incremental reuse, via // change propagation. // ## Level trees // Level trees are balanced, binary trees that represent sequences of // elements, stored at their leaves. A level tree permits O(log n) reads // and writes to the sequence, where writes may overwrite, insert or // remove elements from the sequence. // When the editor updates a sequence, they often want to do so // imperatively. When the archivist updates a sequence, they do so // functionally, such that the update preserves (and does not overwrite) // existing store data. // Below, we focus on the archivist's operations for sequences: // Conversion to and from lists, and various flavors of folding (over // level trees, not lists). // During change propagation over the archivist's incremental folds, this // balanced tree structure ensures that the (isomorphic) dependency graph // it induces is shallow. In particular, from any root of a fold to any // thunk it calls (transitively), there are at most O(log n) transitive // force edges to clean or dirty.