Hacker News new | comments | ask | show | jobs | submit login
D3.js visualization of a lambda calculus (chorasimilarity.github.io)
42 points by miesman on July 18, 2015 | hide | past | web | favorite | 20 comments

Is this supposed to be academic work? The documentation is pretty messy, questions are unclear (the FAQ honestly does not look like anyone would ask those questions frequently), and even though I spent a while I could not find any explanation/justification what this is for, or why it is useful for what it claims to be doing (first, the nodes are atoms, next - though same algorithm - the nodes are microbes). Looks pretty, the meaning however is currently elusive.

It looks beautiful, but could anyone give me a plain word explanation how does lambda calculus relate to moving dots?

The closest thing I can think about are L-systems, but I couldn't understand even Fibonacci numbers (http://chorasimilarity.github.io/chemlambda-gui/dynamic/fibo...).

"Chemlambda is a graph rewriting system derived from graphic lambda calculus which can be seen as a simple model of chemical or biological computing."

here are demonstrations of the graph rewrite rules:


the front page is a better start: http://chorasimilarity.github.io/chemlambda-gui/index.html

as is the FAQ: https://chorasimilarity.wordpress.com/2015/02/19/what-can-i-...

I am still having trouble to understand it. Is there something like an elementary picture/animation and it's mapping to lambda calculus (or a step)?

I agree. This looks amazing. Absolutely gorgeous. This really was done with just using JS? wow. But I have no idea what I just watched.

It's quite cute, but I'm surprised that you're surprised that JS can do it - it's only a few hundred moving objects, and JS has within-order-of-magnitude of native performance.

For shinier stuff, see the demoscene eg https://www.youtube.com/user/Annikras . Demoscene programmers love generative systems, especially when targetting the 4 kilobyte executable category. For example this one, which looks like a distorted Menger sponge: https://www.youtube.com/watch?v=E3qn1RsJlUM

Other things you ought to take a look at:

Sauerbraten in JS, called Bananabread┬╣, and jor1k an OpenRISC emulator running Linux┬▓. Although the latter uses a relay for networking.

1: https://developer.cdn.mozilla.net/media/uploads/demos/a/z/az...

2: https://s-macke.github.io/jor1k/demos/main.html

Warning: Causes Firefox latest on Mac to crash.

Probably due to the horrible way animations are set up with setTimeout:

    var step = -1;

    function nextval() {
        return 3000 + (20*step);
    setTimeout(function() {

        graph.removeLink("31", "31_1");

    }, nextval());
There are 9687 setTimeout on that page.

almost crashed my Firefox 39.0 on Windows 7, very close.

i propose a new practice of putting (DJS) at the end of a link which might cause problem, like we do now with PDF file links. D stands for dangerous or danger or something. half joking here.

Doesn't happen anything after clicking the Start button in Firefox on Linux.

Crashes Pale Moon (25.2.0) on Win 7.

Hmm. Requested an insecure script 'http://d3js.org/d3.v3.min.js'. This request has been blocked; the content must be served over HTTPS.


Some context. Marius Buliga isn't a native English speaker (he's Romanian), so parts of these pages may sound a little confusing. His academic papers are (I find) more clearly written.

The 'lambda' being referenced is the 'graphical lambda calculus' which is Marius's own invention of a family of graphs and graph rewrite rules that can act as a notation for the untyped lambda calculus. Chemlambda is a chemically themed specialisation of his graphical lambda calculus used as an artificial chemistry.

Artificial chemistries, in turn, are used to understand properties of chemical systems in the abstract, without the fiendish difficulties and complexities of actual chemical soups. Much as artificial evolution can be used to understand the dynamics of evolution without the long-time scales and messiness of actual organisms. Stuart Kauffman used the same technique in the 70s, shuffling punch card programs to show the presence of attractors in networks of chemical interactions. This sheds light on behavior such as 'autocatalytic sets': sets of chemicals that can catalyse their own production, which is a necessary condition of life.

For artificial chemistries, it isn't always essential to say what each element 'corresponds to' in real world chemistry. Hence some of the ambiguity between whether the nodes in the graph represent atoms, molecules, or in some cases bonds.

Marius's artificial chemistry is turing complete in an interesting way: it stores information in topology as well as linear sequences of discrete elements (though it isn't the only 'graph computation' approach). This makes it a good analog for biochemistry, which is also structural as well as linear. He is using this system to look at models of decentralised chemical computation.

As for many scientists who create a formalism, he is also evangelising it as a useful tool for others to work with in looking at chemical computation in the abstract. Take up is small so far, with only one other cited researcher to date.

The animations are very stylised, they illustrate simple underlying processes with a lots of visual action. The actual 'moves' are very discrete: they happen at regular intervals and rewrite parts of the graph in one go. When nodes in the graph are removed by a move, they float around in the animation for a while then disappear. Similarly when new nodes are about to be rewritten into the graph they appear and float around in the animation a little before they'll be incorporated. When a move takes place the graph is simply connected to new nodes, wherever they are on the canvas, and D3 is used to then relax the graph. Hence the violent pulsing of the simulation as moves take place.

Hope that helps. It's not my area of research interest (though I worked with Prof S. Kauffman in the late 90s), so feel free to correct my understanding if I'm off.

Thank you sago, that's accurate. Technically, chemlambda rewrites together with the reduction algorithm used in the script quiner.awk from the repository describe an asynchronous graph rewrite automaton.

(An addition to sago's comment is that the rewrites are done randomly; there is a cycle in the algorithm where rewrite patterns are identified, then coins are flipped and as a result some of them are done. The chemical analogy is that there are invisible "enzymes" which do the rewrites, and they roam around randomly. Alternatively one can make another version of the algorithm, for example one where these enzymes are produced and they choose randomly their preferred patterns. This is a way to erase the visual impression that there are global steps in time when the graph is updated.)

Graphic lambda calculus is the ancestor of chemlambda. Actually both formalisms don't have a lot in common with lambda calculus, in the sense that there is an algorithm to produce a graph from a term in untyped lambda beta calculus, such that the lambda calculus rewrites correspond to moves in these graphical formalism. But chemlambda works with a family of graphs which is much larger than the ones which represent lambda terms.

However, you can see in the demos page some classical computation problems: Ackermann function, factorial, predecessor. There are also some demos which can't be qualified as related to lambda calculus.

Chemlambda resembles most with the ALCHEMY of Fontana and Buss, which is also based on lambda calculus, with the main difference being that in ALCHEMY application is a chemical reaction and abstraction is a reactive site (very sketchy description), while in chemlambda the application and abstraction are, on equal footing, just nodes in a graph.

This replication and composition of permutations - in the same time - uses lambda calculus together for composition but otherwise the permutations and replications are not lambda calculus like https://chorasimilarity.wordpress.com/2015/07/22/permutation...

Just as a note, the site doesn't work when accessing it through https (like, with https everywhere)

It's a nice concept

If anyone needs help running these scripts I can offer help to run these scripts. You need awk (gawk).

Is this got something to do with how DNA molecules were formed?

It's an artificial chemistry which is inspired, but can do other things as well, from untyped lambda beta calculus. There are two projects related to it, one in meatspace, other in virtual space. Project 1 says that if this chemlambda can be done by real chemistry then it may help to build or understand biochemistry. The article is http://chorasimilarity.github.io/chemlambda-gui/dynamic/mole... Molecular computers (2015). Project 2 is about decentralized computing, without any higher layer of control. Pretty, short animations with some explanations in the https://plus.google.com/u/0/collection/UjgbX chemlambda collection. More meaty stuff in the http://chorasimilarity.github.io/chemlambda-gui/index.html . But you have to follow links to articles and read them :) Real stuff in the github repo, see https://github.com/chorasimilarity/chemlambda-gui/blob/gh-pa... . I'm a mathematician, not a programer, there has been no release yet, every possibility is left open. Play with it folks! I have not figured out why firefox is so lousy with some of these d3.js animations, but you can make your own and fiddle with them. True is that some of them have tens of thousands of nodes which appear/dissapear (several hundreds at a time). Safari works well, chromium decently.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact