6 ms·

Bloom Programming Language

164 points by panic 8y ago

chewzerita 8y ago
How is this different from elixir?
- titanomachy 8y ago
  This is a ruby DSL. Elixir is a separate language which compiles to the Erlang VM.
- devmunchies 8y ago
  There is a FAQ on the website http://bloom-lang.net/faq/ http://bloom-lang.net/faq/
  - frankmcsherry 8y ago
    How is this FAQ different from Elixir's FAQ?
    - willsinclair 8y ago
      How is this question different from chewzerita's question?
- sriram_malhar 8y ago
  There's practically no overlap. The short summary is that Bloom's position is that as programmers we have been trained -- to our detriment -- to think too much in terms of order. Thinking of algorithms being a sequence of operations on data is unnecessarily constraining and non-parallelizable, particularly in reactive systems. Elixir's semantics are functional. Just as with any conventional language, it is your job to write code to track changes to some data structure and explicitly propagate those changes to other parts. For example, read from a socket into a buffer, parse and transform it, then write a formatted HTML output to the output. You are explicitly sequencing the order of computation. Bloom's semantics are based on logic, so it may seem unfamiliar to the average programmer. It is an enhancement of datalog (itself a subset of Prolog) Its rules are declarative, just as in a spreadsheet. For example, say you enter a formula in Excel for cell A1, "=B1 * 100 + C1". This is declarative. You merely declare what needs to happen, not how the internal data structures are traversed and in which order. It is "understood" (that's the semantics part) that when B1 or C1 change, A1 will be automatically changed. Now imagine B1 has a formula that depends on C1. Now when C1 changes, there are possibly two ways of calculating the value of A1 (i) old value of B1 + new C1 or (ii) new value of B1 + new C1. Spreadsheets resolve this problem by doing a topological sort of cell dependencies, and updating cells in that order. That is to say, the topological sort is part of the spreadsheet semantics. In the example above, the second option will be chosen in all spreadsheets. The limitation of course is that you cannot have B1 refer to C1 and vice-versa. Cycles are not permitted. Bloom (and Datalog) can have mutually dependent rules, so that if one datum changes, everything else dependent on it also changes, which results in that datum changing yet again, since it is dependent on others. Bloom has so called "fixpoint semantics", which means that the infrastructure keeps evaluating these rules (read formulas) in a loop until there is no more change (reached a "fixpoint") to any datum. As it turns out, the semantics are such that these loops are always guaranteed to terminate. Bloom has only one data structure, a table, whose values are primitives or lattices (the stuff that CRDTs are based on). Bloom's operators allow you to write rules that react to changes to any table and automatically update dependent tables. No explicit sequencing of code is needed; the language has a semantics of evaluation. Bloom adds two features (to Datalog) that make it suitable for reactive computation. First is time, which is not clock time, but refers to a round of computation; in each round, all pending input events are processed until there are no more changes. There are some operators that permit you to defer changes to the next round. Bloom couples this with the notion of transient tables whose value is only valid for a single round. All I/O is based on special transient tables called channels; these accumulate events that have to be processed (input or transmitted) in a given round. Hope this helps.
  - pfraze 8y ago
    > As it turns out, the semantics are such that these loops are always guaranteed to terminate. Does this mean it's not possible to specify something like B1 = C1 + 1 C1 = B1 + 1 ?
    - sriram_malhar 8y ago
      That's right, Not in a spreadsheet. Excel will reject it. It has to be a directed acyclic graph. But in Bloom, the only data structure you have available is a lattice, whose change operators have special properties. Consider a prominent example of lattices, namely, sets The only way to add to a set is to union in a new set (of changes). So following the spirit of your example, suppose there are ΔC items to be added to C. This results in some rules getting triggered that generate ΔB changes to B, which in turn produces (possibly) fresh ΔC changes to C and so on in a loop. You will find that given the operators, soon there will come a time when the deltas add nothing new to either table; the computation stops at that point. B and C have mutually coevolved to a new state. Lattices are basically data structures (like sets) fitted with a partial order, and a merge operator (like set union) that has these three simple properties: idempotence: The same stuff added to the set does not change the set commutative: Two sets can be merged either way (A union B == B union A) associative: Order of merges don't matter. A union (B union C) == (A union B) union C. As an aside, these are the building blocks of CRDTs, which is why you get eventual consistency (all replicas eventually converge to the same result) Edit: The merge operators are order-independent. The evaluation semantics don't care about the order in which rules are written down in the program. The Bloom docs speak of "disorder" which is a bit misleading, albeit catchy.
      - wruza 8y ago
        I think I don’t understand something important from your explanation, since I still can’t see how gp comment’s loop is possible in Bloom. Not even “possible”, but how it is implemented to be predictable and ever halting. More realistic example could be an invoice row with a tax or discount, where (discount / (price + discount)) != discount_percent, due to .00 rounding and ieee754 problems in general. How do such systems solve these disrepancies? Is stop point arbitrary or controllable? edit: i.e. 3% of 11.99 = 0.3597, which is 0.0003 off from 0.36
dnautics 8y ago
are others having difficulty finding a spec for the DSL?
- dnautics 8y ago
  https://github.com/bloom-lang/bud/blob/master/docs/cheat.md https://github.com/bloom-lang/bud/blob/master/docs/cheat.md
weatherlight 8y ago
The last version on the site came out in APRIL 23, 2013... is this project alive still?
- deleted 8y ago
  [deleted]
- 333c 8y ago
  Latest commit in November 2017: https://github.com/bloom-lang/bud/commits/master https://github.com/bloom-lang/bud/commits/master
  - pmontra 8y ago
    But it requires "Ruby (MRI) 1.8.7 and 1.9. Bud also has experimental support for Ruby 2." which means it's on life support. Fair for a research project started when 1.8.7 was current but not much for doing any real work today.
- espeed 8y ago
  See the just released paper on Anna, which subsumes the related projects: Anna: A Crazy Fast, Super-Scalable, Flexibly Consistent KVS https://databeta.wordpress.com/2018/03/09/anna-kvs/ https://databeta.wordpress.com/2018/03/09/anna-kvs/ Discussion: https://news.ycombinator.com/item?id=16551072 https://news.ycombinator.com/item?id=16551072 Also see... Peter Alvaro / Disorderly Labs https://people.ucsc.edu/~palvaro/ https://people.ucsc.edu/~palvaro/ Data-Centric Programming: Rendezvous, Bloom and CALM (Joe) https://ucbrise.github.io/cs294-rise-fa16/rendezvous.html https://ucbrise.github.io/cs294-rise-fa16/rendezvous.html BOOM http://boom.cs.berkeley.edu/ http://boom.cs.berkeley.edu/ Paper summary. Blazes: Coordination analysis and placement for distributed programs http://muratbuffalo.blogspot.com/2017/11/paper-summary-blazes-coordination.html http://muratbuffalo.blogspot.com/2017/11/paper-summary-blaze... A functional and logic programming language inspired by Scala, OCaml, and Datalog. https://flix.github.io/ https://flix.github.io/ From Doom and Gloom to BOOM and Bloom [video] https://www.youtube.com/watch?v=voQKPymcCfA https://www.youtube.com/watch?v=voQKPymcCfA
- russell_sears 8y ago
hammerandtongs 8y ago
Of note Bloom is an ancestor of Eve. Bloom is a descendant of Datalog via Dedalus. "Dedalus: Datalog in Time and Space" http://db.cs.berkeley.edu/papers/datalog2011-dedalus.pdf http://db.cs.berkeley.edu/papers/datalog2011-dedalus.pdf Here is Peter Alvaro's Strange Loop talk - https://www.youtube.com/watch?v=R2Aa4PivG0g https://www.youtube.com/watch?v=R2Aa4PivG0g It was a shame that most people, seemingly the Eve devs as well, seemed to focus on making Eve a language for easy programming for the masses. Thats a huge wall of a problem with a limited funding slope. I think if there had been more upfront work and focus on the distributed programming/database possibilities, that Eve would have founded an actual community to push it along. Eve as a language for doing business logic against say Kubernetes? As a language to wire up ETL processes? I think it could have found a niche that would have made it grow in power before trying to take on the mass market. Just a thought.
- roller 8y ago
  I assume Lineage Driven Fault Injection stuff [1] has some overlap with Eve's ability to tell you "Why is this blank?": The datalog model allows you to find the logical dependencies of results. Some other bloom related links: - Anna KVS[2] showed up recently on hacker news[3] and morning paper[4] - Lasp lang is in the same space[5], Christopher Meiklejohn has a comparison with bloom[6] [1]: https://disorderlylabs.github.io/# https://disorderlylabs.github.io/# [2]: https://databeta.wordpress.com/2018/03/09/anna-kvs/ https://databeta.wordpress.com/2018/03/09/anna-kvs/ [3]: https://news.ycombinator.com/item?id=16551072 https://news.ycombinator.com/item?id=16551072 [4]: https://blog.acolyer.org/2018/03/27/anna-a-kvs-for-any-scale/ https://blog.acolyer.org/2018/03/27/anna-a-kvs-for-any-scale... [5]: https://lasp-lang.readme.io/ https://lasp-lang.readme.io/ [6]: http://christophermeiklejohn.com/lasp/2018/03/02/lasp-vs-bloom.html http://christophermeiklejohn.com/lasp/2018/03/02/lasp-vs-blo...
agentultra 8y ago
This is a fascinating language with some great ideas. I tried years ago to create my own implementation in Python but while I found the paper straight-forward the implementation in Bud, to me at the time, was quite dense. It'd be interesting to revisit it again with some of the advances we've made in deep specifications and dependent type theory.

164 points by panic 8y ago

chewzerita 8y ago

How is this different from elixir?

titanomachy 8y ago
This is a ruby DSL. Elixir is a separate language which compiles to the Erlang VM.
devmunchies 8y ago
There is a FAQ on the website http://bloom-lang.net/faq/ http://bloom-lang.net/faq/
- frankmcsherry 8y ago
  How is this FAQ different from Elixir's FAQ?
  - willsinclair 8y ago
    How is this question different from chewzerita's question?
sriram_malhar 8y ago
There's practically no overlap. The short summary is that Bloom's position is that as programmers we have been trained -- to our detriment -- to think too much in terms of order. Thinking of algorithms being a sequence of operations on data is unnecessarily constraining and non-parallelizable, particularly in reactive systems. Elixir's semantics are functional. Just as with any conventional language, it is your job to write code to track changes to some data structure and explicitly propagate those changes to other parts. For example, read from a socket into a buffer, parse and transform it, then write a formatted HTML output to the output. You are explicitly sequencing the order of computation. Bloom's semantics are based on logic, so it may seem unfamiliar to the average programmer. It is an enhancement of datalog (itself a subset of Prolog) Its rules are declarative, just as in a spreadsheet. For example, say you enter a formula in Excel for cell A1, "=B1 * 100 + C1". This is declarative. You merely declare what needs to happen, not how the internal data structures are traversed and in which order. It is "understood" (that's the semantics part) that when B1 or C1 change, A1 will be automatically changed. Now imagine B1 has a formula that depends on C1. Now when C1 changes, there are possibly two ways of calculating the value of A1 (i) old value of B1 + new C1 or (ii) new value of B1 + new C1. Spreadsheets resolve this problem by doing a topological sort of cell dependencies, and updating cells in that order. That is to say, the topological sort is part of the spreadsheet semantics. In the example above, the second option will be chosen in all spreadsheets. The limitation of course is that you cannot have B1 refer to C1 and vice-versa. Cycles are not permitted. Bloom (and Datalog) can have mutually dependent rules, so that if one datum changes, everything else dependent on it also changes, which results in that datum changing yet again, since it is dependent on others. Bloom has so called "fixpoint semantics", which means that the infrastructure keeps evaluating these rules (read formulas) in a loop until there is no more change (reached a "fixpoint") to any datum. As it turns out, the semantics are such that these loops are always guaranteed to terminate. Bloom has only one data structure, a table, whose values are primitives or lattices (the stuff that CRDTs are based on). Bloom's operators allow you to write rules that react to changes to any table and automatically update dependent tables. No explicit sequencing of code is needed; the language has a semantics of evaluation. Bloom adds two features (to Datalog) that make it suitable for reactive computation. First is time, which is not clock time, but refers to a round of computation; in each round, all pending input events are processed until there are no more changes. There are some operators that permit you to defer changes to the next round. Bloom couples this with the notion of transient tables whose value is only valid for a single round. All I/O is based on special transient tables called channels; these accumulate events that have to be processed (input or transmitted) in a given round. Hope this helps.
- pfraze 8y ago
  > As it turns out, the semantics are such that these loops are always guaranteed to terminate. Does this mean it's not possible to specify something like B1 = C1 + 1 C1 = B1 + 1 ?
  - sriram_malhar 8y ago
    That's right, Not in a spreadsheet. Excel will reject it. It has to be a directed acyclic graph. But in Bloom, the only data structure you have available is a lattice, whose change operators have special properties. Consider a prominent example of lattices, namely, sets The only way to add to a set is to union in a new set (of changes). So following the spirit of your example, suppose there are ΔC items to be added to C. This results in some rules getting triggered that generate ΔB changes to B, which in turn produces (possibly) fresh ΔC changes to C and so on in a loop. You will find that given the operators, soon there will come a time when the deltas add nothing new to either table; the computation stops at that point. B and C have mutually coevolved to a new state. Lattices are basically data structures (like sets) fitted with a partial order, and a merge operator (like set union) that has these three simple properties: idempotence: The same stuff added to the set does not change the set commutative: Two sets can be merged either way (A union B == B union A) associative: Order of merges don't matter. A union (B union C) == (A union B) union C. As an aside, these are the building blocks of CRDTs, which is why you get eventual consistency (all replicas eventually converge to the same result) Edit: The merge operators are order-independent. The evaluation semantics don't care about the order in which rules are written down in the program. The Bloom docs speak of "disorder" which is a bit misleading, albeit catchy.
    - wruza 8y ago
      I think I don’t understand something important from your explanation, since I still can’t see how gp comment’s loop is possible in Bloom. Not even “possible”, but how it is implemented to be predictable and ever halting. More realistic example could be an invoice row with a tax or discount, where (discount / (price + discount)) != discount_percent, due to .00 rounding and ieee754 problems in general. How do such systems solve these disrepancies? Is stop point arbitrary or controllable? edit: i.e. 3% of 11.99 = 0.3597, which is 0.0003 off from 0.36

dnautics 8y ago

are others having difficulty finding a spec for the DSL?

dnautics 8y ago
https://github.com/bloom-lang/bud/blob/master/docs/cheat.md https://github.com/bloom-lang/bud/blob/master/docs/cheat.md

weatherlight 8y ago

The last version on the site came out in APRIL 23, 2013... is this project alive still?

deleted 8y ago
[deleted]
333c 8y ago
Latest commit in November 2017: https://github.com/bloom-lang/bud/commits/master https://github.com/bloom-lang/bud/commits/master
- pmontra 8y ago
  But it requires "Ruby (MRI) 1.8.7 and 1.9. Bud also has experimental support for Ruby 2." which means it's on life support. Fair for a research project started when 1.8.7 was current but not much for doing any real work today.
espeed 8y ago
See the just released paper on Anna, which subsumes the related projects: Anna: A Crazy Fast, Super-Scalable, Flexibly Consistent KVS https://databeta.wordpress.com/2018/03/09/anna-kvs/ https://databeta.wordpress.com/2018/03/09/anna-kvs/ Discussion: https://news.ycombinator.com/item?id=16551072 https://news.ycombinator.com/item?id=16551072 Also see... Peter Alvaro / Disorderly Labs https://people.ucsc.edu/~palvaro/ https://people.ucsc.edu/~palvaro/ Data-Centric Programming: Rendezvous, Bloom and CALM (Joe) https://ucbrise.github.io/cs294-rise-fa16/rendezvous.html https://ucbrise.github.io/cs294-rise-fa16/rendezvous.html BOOM http://boom.cs.berkeley.edu/ http://boom.cs.berkeley.edu/ Paper summary. Blazes: Coordination analysis and placement for distributed programs http://muratbuffalo.blogspot.com/2017/11/paper-summary-blazes-coordination.html http://muratbuffalo.blogspot.com/2017/11/paper-summary-blaze... A functional and logic programming language inspired by Scala, OCaml, and Datalog. https://flix.github.io/ https://flix.github.io/ From Doom and Gloom to BOOM and Bloom [video] https://www.youtube.com/watch?v=voQKPymcCfA https://www.youtube.com/watch?v=voQKPymcCfA
russell_sears 8y ago

hammerandtongs 8y ago

Of note Bloom is an ancestor of Eve. Bloom is a descendant of Datalog via Dedalus. "Dedalus: Datalog in Time and Space" http://db.cs.berkeley.edu/papers/datalog2011-dedalus.pdf http://db.cs.berkeley.edu/papers/datalog2011-dedalus.pdf Here is Peter Alvaro's Strange Loop talk - https://www.youtube.com/watch?v=R2Aa4PivG0g https://www.youtube.com/watch?v=R2Aa4PivG0g It was a shame that most people, seemingly the Eve devs as well, seemed to focus on making Eve a language for easy programming for the masses. Thats a huge wall of a problem with a limited funding slope. I think if there had been more upfront work and focus on the distributed programming/database possibilities, that Eve would have founded an actual community to push it along. Eve as a language for doing business logic against say Kubernetes? As a language to wire up ETL processes? I think it could have found a niche that would have made it grow in power before trying to take on the mass market. Just a thought.

roller 8y ago
I assume Lineage Driven Fault Injection stuff [1] has some overlap with Eve's ability to tell you "Why is this blank?": The datalog model allows you to find the logical dependencies of results. Some other bloom related links: - Anna KVS[2] showed up recently on hacker news[3] and morning paper[4] - Lasp lang is in the same space[5], Christopher Meiklejohn has a comparison with bloom[6] [1]: https://disorderlylabs.github.io/# https://disorderlylabs.github.io/# [2]: https://databeta.wordpress.com/2018/03/09/anna-kvs/ https://databeta.wordpress.com/2018/03/09/anna-kvs/ [3]: https://news.ycombinator.com/item?id=16551072 https://news.ycombinator.com/item?id=16551072 [4]: https://blog.acolyer.org/2018/03/27/anna-a-kvs-for-any-scale/ https://blog.acolyer.org/2018/03/27/anna-a-kvs-for-any-scale... [5]: https://lasp-lang.readme.io/ https://lasp-lang.readme.io/ [6]: http://christophermeiklejohn.com/lasp/2018/03/02/lasp-vs-bloom.html http://christophermeiklejohn.com/lasp/2018/03/02/lasp-vs-blo...

agentultra 8y ago

This is a fascinating language with some great ideas. I tried years ago to create my own implementation in Python but while I found the paper straight-forward the implementation in Bud, to me at the time, was quite dense. It'd be interesting to revisit it again with some of the advances we've made in deep specifications and dependent type theory.