Before we go too far down the path of building a traditional compiler (#9), it probably makes sense to start thinking about how we might incrementalise things. This will be super important for supporting a good editor experience (#97). If we put this off for too long we might end up having to rebuild a bunch - this is what Rust is facing, for example.
Without knowing much about it, perhaps something like the Incremental Lambda Calculus would be handy for this. We could try to find the derivative of each pass of our compiler, based on the result of a previous run. This could also be a helpful framework for formalising our incremental compiler as well (#39)!
CRDT-style data structures could also be of potential use, and perhaps projects like timely-dataflow and differential-dataflow.
What is the difference between 'incremental' vs. 'query-driven'?
* [Rust's demand-driven compilation (Rustc Book)](https://rust-lang-nursery.github.io/rustc-guide/query.html) * [matklad/rust-analyzer](https://github.com/matklad/rust-analyzer) - experimental frontend for Rust with a focus on IDE support * [Swift's RequestEvaluator Docs](https://github.com/apple/swift/blob/master/docs/RequestEvaluator.md) * [Merlin: A Language Server for OCaml (Experience Report)](http://gallium.inria.fr/%7Escherer/drafts/merlin.pdf) * [Grzegorz Kossakowski: gkossakowski/kentuckymule](https://github.com/gkossakowski/kentuckymule) * [Grzegorz Kossakowski: Can Scala have a highly parallel typechecker?](https://medium.com/@gkossakowski/can-scala-have-a-highly-parallel-typechecker-95cd7c146d20) * [Grzegorz Kossakowski: Kentucky Mule — limits of Scala typechecking speed](https://medium.com/@gkossakowski/kentucky-mule-limits-of-scala-typechecking-speed-6a44bd520a2f) * [Anders Hejlsberg on Modern Compiler Construction (YouTube)](https://www.youtube.com/watch?v=wSdV1M7n4gQ) * [Tamás Szabó & Sebastian Erdweg - Better living through incrementality (YouTube)](https://www.youtube.com/watch?v=zuQf2E470RU) * [IncA: Incremental Program Analysis Framework](https://github.com/szabta89/IncA) * [Incremental Lambda Calculus](http://www.informatik.uni-marburg.de/~pgiarrusso/ILC/) * [Fungi: Typed incremental computation with names](https://github.com/Adapton/fungi-lang.rust) * [Adapton implementation in Rust](https://docs.rs/adapton/) * [Salsa: A generic framework for on-demand, incrementalized computation (in Rust)](https://github.com/salsa-rs/salsa) * [LINVIEW: Incremental View Maintenance for Complex Analytical Queries](https://arxiv.org/pdf/1403.6968.pdf) * [Differential Dataflow](https://blog.acolyer.org/2015/06/17/differential-dataflow/) * [Incremental Evaluation of Reference Attribute Grammars using Dynamic Dependency Tracking](https://lucris.lub.lu.se/ws/files/3312049/2543179.pdf) * [Answer to "In which way should I structure a compiler/Interpeter?"](https://softwareengineering.stackexchange.com/a/351294) * [Incremental Compilation In Sixten](https://github.com/ollef/sixten/blob/master/docs/QueryCompilerDriver.md)
Last active
November 24, 2023 23:13
-
-
Save tripleo1/aa99201bce3cce63928f4ebb22d25c8b to your computer and use it in GitHub Desktop.
Incremental stuff
Designing a stream-composable, (soft) real-time ready, chain-time-type-validated FSP cascade system and DSL #270
I have a bunch of ideas on this and am working out some draft ideas as part of chaining some small fsps in #268 but for now I'm just going to dump a research url set to avoid losing it 😂
So, more to come..
Resources from a ton of other projects (this needs to be better categorized, especially the existing python stuff):
* https://scopes.readthedocs.io/en/latest/tutorial/ * https://extemporelang.github.io/docs/overview/using-extempore/ * https://docs.rs/adapton/0.3.31/adapton/#programming-model * https://en.wikipedia.org/wiki/Dataflow_programming * https://www.stochasticlifestyle.com/why-numba-and-cython-are-not-substitutes-for-julia/ * http://adapton.org/ * https://blog.opencog.org/2020/04/08/value-flows/ * https://duckduckgo.com/?t=ffab&q=adapton.python&ia=web * https://docs.rs/adapton/0.3.31/adapton/#background-incremental-computing-with-names * https://coconut.readthedocs.io/en/master/DOCS.html#compose * https://github.com/PrefectHQ/prefect/blob/master/src/prefect/core/flow.py#L359 * https://en.wikipedia.org/wiki/Partial_evaluation#:~:text=Futamura%20projections,-A%20particularly%20interesting&text=This%20technique%20is%20known%20as,1)%2C%20yielding%20a%20compiler * https://en.wikipedia.org/wiki/Quine_(computing) * https://hobbes.readthedocs.io/en/latest/ * https://docs.sympy.org/latest/modules/tensor/indexed.html * https://numba.readthedocs.io/en/stable/reference/types.html?highlight=from_dtype#numba.from_dtype * https://returns.readthedocs.io/en/latest/pages/railway.html * https://stackoverflow.com/questions/58422690/filtering-a-numpy-array-what-is-the-best-approach * http://learnyouahaskell.com/higher-order-functions#composition * https://scala-lms.github.io/ * https://tuulos.github.io/pydata-2014/#/ * https://numba.readthedocs.io/en/stable/user/faq.html#can-i-pass-a-function-as-an-argument-to-a-jitted-function * https://toolz.readthedocs.io/en/latest/curry.html#id1 * https://stackoverflow.com/questions/16739290/composing-functions-in-python * https://toolz.readthedocs.io/en/latest/api.html?highlight=compose#toolz.functoolz.compose * https://funcy.readthedocs.io/en/latest/funcs.html#compose * https://labs.quansight.org/blog/2019/05/metadsl-dsl-framework/ * https://labs.quansight.org/projects/ * https://labs.quansight.org/blog/2019/04/python-moa-tensor-compiler/ * https://stackoverflow.com/questions/38470264/numpy-concatenate-is-slow-any-alternative-approach * https://stackoverflow.com/questions/7869095/concatenate-numpy-arrays-without-copying * https://stackoverflow.com/questions/3522946/using-numpy-arrays-as-lookup-tables * https://coconut.readthedocs.io/en/master/DOCS.html#compose * https://faust.grame.fr/community/made-with-faust/mi-faust/index.html * https://chuck.cs.princeton.edu/doc/learn/tutorial.html * https://scipy-cookbook.readthedocs.io/items/ViewsVsCopies.html * https://metadsl.readthedocs.io/en/latest/# * https://toolz.readthedocs.io/en/latest/purity.html * https://metadsl.readthedocs.io/en/latest/Roadmap.html * https://github.com/Quansight-Labs/metadsl * https://www.hillelwayne.com/post/spec-composition/ * https://vimeo.com/122066659 * https://wiki.postgresql.org/wiki/Incremental_View_Maintenance * https://www.sympy.org/scipy-2017-codegen-tutorial/
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment