Tag Archives: GLC

Graphic lambda calculus and chemlambda (II)

Chemlambda v2 is an entirely different project than GLC and chemlambda v1. This post continues from the first part. It explains the passage towards chemlambda v2.

A problem of GLC and chemlambda v1 is that research articles are opinion pieces, not validated by programs and experiments. The attempt to use GLC with the Actor Model in order to build a decentralized computing proposal, aka distributed GLC, failed because of this. Does all of this work?

The CO-COMM and CO-ASSOC rewrites lead to the situation that,  in order to be useful, either:

  • they have to be applied by a human or by a(n unknown) very clever algorithm
  • or they are applied in both directions randomly, which implies that no GLC or chemlambda v1 reduction ever terminates.

Here is an early visual tutorial  which introduces the nodes of chemlambda v2.  At the end of it you are pointed to See also a gallery of examples which mixes chemlambda v1 with chemlambda v2, like these:

 

Or, another example, the Y combinator. In chemlambda v1, without using CO-COMM and CO-ASSOC, the Y combinator applied to an unspecified term behaves like this.  In chemlambda v2, where there is a supplimentary node and other rewrites, the Y combinator behaves almost identically, but some nodes (the yellow FOE here instead of the green FO before) are different:

 

ycombi

 

 

See this page for a list of works, tagged with the version of chemlambda used.

(continues with part III)

 

 

Graphic lambda calculus and chemlambda (I)

Looks like there is a need to make a series of posts dedicated to the people who try to use this blog as a source in order to understand graphic lambda calculus (aka GLC) and chemlambda. This is the first one.

Sources for GLC:

  • the best source is the article M. Buliga, Graphic lambda calculus. Complex Systems 22, 4 (2013), 311-360   (link to article in journal) (link to article in arXiv)
  • you can see the GLC page (link) here, which has been updated many times after chemlambda appeared, but it is unmodified starting from the section “What is graphic lambda calculus?” and there are links to many others posts here which explain GLC as it is, that is before chemlambda.

GLC is a graph rewriting system for fatgraphs made of trivalent or 1-valent nodes. The trivalent nodes used are A (application), L (lambda), FO (fanout), epsilon (for dilations). There is one 1-valent node, T (termination). Loops with no nodes and arrows, i.e. oriented edges with no nodes are accepted as well. There is no algorithm proposed for the reduction of these graphs.

The graph rewrites are:

– local ones (i.e. involving only a finite number, a priori given, of nodes and edges)

  •   graphic beta move, which is like Lamping graph rewrite, only purely local, i.e. there is no limitation on the global shape of the graph, thus it is  somehow more general than the beta rewrite from untyped lambda beta calculus; a possible interpretation is C= let x=B in A rewrites to x=B and C=A

 

  • betaCO-COMM and CO-ASSOC rewrites for the FO (fanout) which are, due to the orientation of the edges, really like graphical, AST forms of co-commutativity and co-associativity
  • local pruning group of rewrites, which describe the interaction of the trivalent nodes with the T node; incidentally T and FO interact like if T is a co-unit for FO
  • a group of rewrites for the dilation nodes, which are those of emergent algebras, which involve the fanout FO and the dilation nodes

 

– global rewrites:

  • global fan-out
  • global pruning

 

In section 3 of the article on GLC is given an algorithm of conversion of untyped lambda terms into graphs which is a little more than a modification of the AST of the lambda term, in such a way that the orientation of the edges is respected. That is because the lambda node L has one incoming edge and two outgoing edges!

I prove then that GLC can be used for untyped lambda beta calculus, but also for emergent algebras and also for a variant of knot theoretic graphs where there is no need for them to be planar. Finally, I show that there might be other “sectors” of graphs which may be interesting, regardless of their meaning (or lack of it) with respect to lambda calculus.

The problem of GLC is that it has these global rewrites. Can these be replaced by local rewrites?

That’s how chemlambda appeared.

I was aware that some applications of global fanout can be done with local rewrites, but not all. Also, the interest in GLC was not extended to the interest into emergent algebras, to my dismay.

On the other side I became obsessed with the idea that if the global fanout can be replaced by local rewrites entirely then it should be possible in principle to see the rewrites as chemical reactions between individual molecules. A bigger problem would be then: would these reactions reduce the graph-molecules under the dumbest algorithm among all, the random one? Nature functions like this, so any algorithm which would be global in some sense is completely excluded.

This led me to write the article: M. Buliga, Chemical concrete machine (link to DOI) (link to arXiv version).  This is chemlambda v1, which is actually a transition from GLC to something else, or better said to another research subject in the making.

Other sources for this mix glc-chemlambda v1:

 

Chemlambda v1, or the “chemical concrete machine”, is a graph rewriting algorithm which uses the trivalent nodes A, L, FI (fan-in), FO, and the 1-valent node T and only local rewrites:

  • the graphic beta rewrite (between the nodes L and A) and the fan-in rewrite (between the nodes FI and FO)

 

convention_2

 

  • the CO-COMM and CO-ASSOC rewrites

 

 

convention_3

 

  • two DIST (from distributivity) rewrites, for the pairs A-FO and L-FO

 

 

convention_6

  • local pruning rewrites (involving the 1-valent node T)

 

convention_4

 

  •  and elimination of loops

 

convention_5

 

As you see, all rewrites except CO-COMM and CO-ASSOC are alike the ones from Lafont article Interaction combinators, except that the graphs are directed and the nodes don’t have a principal port for interaction. Here are the interaction combinators rewrites

 

 

lafont-2

In the chemical concrete machine article are mentioned Berry and Boudol chemical abstract machine and Fontana and Buss alchemy, but not Lafont.  My fault. From what I knew then the beta rewrite came from Lamping or better Wadsworth, the fan-in came from Turaev (knotted trivalent graphs), and the DIST rewrites came from the graphical version of linear emergent algebras, or even better from the Reidemeister 3 rewrite in knot theory.

 

 

In this article there is no algorithm for application of the rewrites. (You shall see that in chemlambda v2, which is an artificial chemistry,  there are actually several, among them the deterministic greedy one, with a list of priority of the rewrites, because there are collisions otherwise, and the random one, which interested me the most.)

However I suggest that the rewrites can be seen as done in a truly chemical sense, mediated by (invisible) enzymes, each rewrite type with it’s enzyme.

I proved that we can translate from GLC to chemlambda v1 and that global fan-out and global pruning can be replaced by sequences of rewrites from chemlambda v1. There was no proof that this replacement of the global rewrites with cascades of local rewrites can be done by the algorithms considered. I proved the Turing universality by using the BCKW system of combinators.

The chemical concrete machine article ends however with:

“With a little bit of imagination, if we look closer to what TRUE, FALSE and IFTHENELSE are doing, we see that it is possible to adapt the IFTHENELSE to a molecule which releases, under the detection of one molecule (like TRUE), the ”medicine” A, and under the detection of another molecule (like FALSE) the ”medicine” B.”

The chemlambda page (link) here is reliable for chemlambda v1, but it also contain links to newer versions.

[UPDATE: I retrieved this view from 2014  of the story.]

(continues with part II)

 

500: a year review at chorasimilarity, first half

Personal post triggered by the coincidence of the year’s end and a round number of posts here: 500.

I started this year with high hopes about the project described in the article GLC actors, artificial chemical connectomes, topological issues and knots. Louis Kauffman wrote in the introduction some unbelievably nice words about graphic lambda calculus:

Even more generally, the movement between graphs and algebra is part of the larger picture of the relationship of logical and mathematical formalisms with networks and systems that was begun by Claude Shannon in his ground-breaking discovery of the relationship of Boolean algebra and switching networks.

We believe that our graphical formulation of lambda calculus is on a par with these discoveries of Shannon. We hope that the broad impact of this proposal will be a world-wide change in the actual practice of distributed computing. Implemented successfully, this proposal has a potential impact on a par with the internet itself.

But in June we got news that the project “Secure Distributed Computing with Graphic Lambda Calculus” will not be funded by NSF, see my comments in this post.  We got good reactions, from the reviewers, on the theoretical side (i.e. what is described in the GLC actors article), but fair critics on the IT part of the project. Another mistake was the branding of the project as oriented towards security.

I should have follow my initial plan, namely to start from the writing of simple tools, programs, which should also have some fun side, ideally, but which at least would allow to start the exploration of the formalism in much more detail than the what pen and papers allows. Instead of that, as concerns this project, there has been a waste of time from Jan to Jun, waiting for one puny source of funding before doing any programming work.

I parallel, a better trend appeared, one which I have not dreamed about two years ago: artificial life. During the summer of 2013 I thought it is worthy to try to get rid of a weakness of the graphic lambda calculus, namely that is has one global graph rewrite, called GLOBAL FAN-OUT. That’s why I wrote the Chemical concrete machine article, describing a purely local graph rewrite formalism which later was renamed  chemlambda. That was great, I even made an icon for it:

chemlambda4

which is made by two lambda symbols, one being up side down, to suggest that writing linear conventions are obsolete. The lambdas are  arranged into a DNA like double spiral, to suggest connections with life. (Of course that means I entered in the alife field, but everything about that was so fresh for me. Later I learned about Alchemy and other approaches, mixing either lambda calculus with alife, or rewriting systems with alife, but not both, and surely not the way is done in chemlambda, as abundantly documented in this blog)

Several (personal as well) novelties related to the article. One was that the article appeared on figshare too, not only on arXiv. This relates with another subject which I follow, namely what means of dissemination of research to use, seen that publishing academic articles is no longer enough, unless you want your work to be used only as a kind of fertilizer for future data mining projects.

More about this later.

The initial purpose of chemlambda was to be aimed at biologists, chemists, somewhere there, but apparently, with almost certainly, if a guy does computing then he will not do chemistry, or if he does chemistry then he has no idea about lambda calculus. I’m mean, there are exceptions, like to be part of an already existing team which do both, which I’m not. Anyway, so initially I hoped for interactons with biochemists (I still do, looking for that rare bird who would dare to lower himself to talk with a geometer from a non dominant country, motivated purely by the research content, and who would have the trivial idea to use his chemistry notions for something which is not in the scope of already existing projects).

With Louis Kauffman, we set out to write a kind of continuation of the GLC actors article, this time concentrated on chemlambda, as seen from our personal interests. The idea was to participate at the biggest event in the field, the ALIFE 14 conference. Which we did: Chemlambda, universality and self-multiplication.

Putting together the failure of the NSF project and the turn towards alife, is only natural that I set to write more explanations about the formalism, like this series  of 7  expository posts on chemlambda described with the help of g-patterns:

This was a bridge towards starting to write programs, that’s for later.

In parallel with other stuff, which I’ll explain in the second half.

_________________________________________________

More detailed argument for the nature of space buillt from artificial chemistry

There are some things which were left uncleared. For example, I have never suggested to use networks of computers as a substitute for space, with computers as nodes, etc. This is one of the ideas which are too trivial. In the GLC actors article is proposed a different thing.

First to associate to an initial partition of the graph (molecule) another graph, with nodes being the partition pieces (thus each node, called actor, holds a piece of the graph) and edges being those edges of the original whole molecule which link nodes of graphs from different partitions. This is the actors diagram.
Then to interpret the existence of an edge between two actor nodes as a replacement for a spatial statement like (these two actors are close). Then to remark that the partition can be made such that the edges from the actor diagram correspond to active edges of the original graph (an active edge is one which connects two nodes of the molecule which form a left pattern), so that a graph rewrite applied to a left pattern consisting of a pair of nodes, each in a different actor part, produces not only a change of the state of each actor (i.e. a change of the piece of the graph which is hold by each actor), but also a change of the actor diagram itself. Thus, this very simple mechanism produces by graph rewrites two effects:

  • “chemical” where two molecules (i.e. the states of two actors) enter in reaction “when they are close” and produce two other molecules (the result of the graph rewrite as seen on the two pieces hold by the actors), and
  • “spatial” where the two molecules, after chemical interaction, change their spatial relation with the neighboring molecules because the actors diagram itself has changed.

This was the proposal from the GLC actors article.

Now, the first remark is that this explanation has a global side, namely that we look at a global big molecule which is partitioned, but obviously there is no global state of the system, if we think that each actor resides in a computer and each edge of an actor diagram describes the fact that each actor knows the mail address of the other which is used as a port name. But for explanatory purposes is OK, with the condition to know well what to expect from this kind of computation: nothing more than the state of a finite number of actors, say up to 10, known in advance, a priori bound, as is usual in the philosophy of local-global which is used here.

The second remark is that this mechanism is of course only a very
simplistic version of what should be the right mechanism. And here
enter the emergent algebras, i.e. the abstract nonsense formalism with trees and nodes and graph rewrites which I have found trying to
understand sub-riemannian geometry (and noticing that it does not
apply only to sub-riemannian, but seems to be something more general, of a computational nature, but which computation, etc). The closeness,  i.e. the neighbourhood relations themselves are a global, a posteriori view, a static view of the space.

In the Quick and dirty argument for space from chemlambda I propose the following. Because chemlambda is universal, it means that for any program there is a molecule such that the reductions of this molecule simulate the execution of the program. Or, think about the chemlambda gui, and suppose even that I have as much as needed computational power. The gui has two sides, one which processes mol files and outputs mol files of reduced molecules, and the other (based on d3.js) which visualizes each step. “Visualizes” means that there is a physics simulation of the molecule graphs as particles with bonds which move in space or plane of the screen. Imagine that with enough computing power and time we can visualize things in as much detail as we need, of course according to some physics principles which are implemented in the program of visualization. Take now a molecule (i.e. a mol file) and run the program with the two sides reduction/visualization. Then, because of chemlambda universality we know that there exist another molecule which admit chemlambda reductions which simulate the reductions of the first molecule AND the running of the visualization program.

So there is no need to have a spatial side different from the chemical side!

But of course, this is an argument which shows something which can be done in principle but maybe is not feasible in practice.

That is why I propose to concentrate a bit on the pure spatial part. Let’s do a simple thought experiment: take a system with a finite no of degrees of freedom and see it’s state as a point in a space (typically a symplectic manifold) and it’s evolution described by a 1st order equation. Then discretize this correctly(w.r.t the symplectic structure)  and you get a recipe which describes the evolution of the system which has roughly the following form:

  • starting from an initial position (i.e. state), interpret each step as a computation of the new position based on a given algorithm (the equation of evolution), which is always an algebraic expression which gives the new position as a  function of the older one,
  • throw out the initial position and keep only the algorithm for passing from a position to the next,
  • use the same treatment as in chemlambda or GLC, where all the variables are eliminated, therefore renounce in this way at all reference to coordinates, points from the manifold, etc
  • remark that the algebraic expressions which are used  always consists  of affine (or projective) combinations of  points (and notice that the combinations themselves can be expressed as trees or others graphs which are made by dilation nodes, as in the emergent algebras formalism)
  • indeed, that  is because of the evolution equation differential  operators, which are always limits of conjugations of dilations,  and because of the algebraic structure of the space, which is also described as a limit of  dilations combinations (notice that I speak about the vector addition operation and it’s properties, like associativity, etc, not about the points in the space), and finally because of an a priori assumption that functions like the hamiltonian are computable themselves.

This recipe itself is alike a chemlambda molecule, but consisting not only of A, L, FI, FO, FOE but also of some (two perhaps)  dilation nodes, with moves, i.e. graph rewrites which allow to pass from a step to another. The symplectic structure itself is only a shadow of a Heisenberg group structure, i.e. of a contact structure of a circle bundle over the symplectic manifold, as geometric  prequantization proposes (but is a mathematical fact which is, in itself, independent of any interpretation or speculation). I know what is to be added (i.e. which graph rewrites which particularize this structure among all possible ones). Because it connects to sub-riemannian geometry precisely. You may want to browse the old series on Gromov-Hausdorff distances and the Heisenberg group part 0, part I, part II, part III, or to start from the other end The graphical moves of projective conical spaces (II).

Hence my proposal which consist into thinking about space properties as embodied into graph rewriting systems, inspred from the abstract nonsense of emergent algebras, combining  the pure computational side of A, L, etc with the space  computational side of dilation nodes into one whole.

In this sense space as an absolute or relative vessel does not exist more than the  Marius creature (what does exist is a twirl of atoms, some go in, some out, but is too complex to understand by my human brain) instead the fact that all beings and inanimate objects seem to agree collectively when it comes to move spatially is in reality a manifestation of the universality of this graph rewrite system.

Finally, I’ll go to the main point which is that I don’t believe that
is that simple. It may be, but it may be as well something which only
contains these ideas as a small part, the tip of the nose of a
monumental statue. What I believe is that it is possible to make the
argument  by example that it is possible that nature works like this.
I mean that chemlambda shows that there exist a formalism which can do this, albeit perhaps in a very primitive way.

The second belief I have is that regardless if nature functions like this or not, at least chemlambda is a proof of principle that it is possible that brains process spatial information in this chemical way.

__________________________________________________________________

How space is born (0)

This opens a new series of posts, which will turn us back to the “computing with space” theme, the main interest here at chorasimilarity.

Look again at the move R2 of graphic lambda calculus.

 

r2move

The epsilon and mu are, originally, elements of a commutative group. Suggestions have been made repeatedly that the commutative group can be anything.

The epsilon and mu are port names, just like the red 1, 2, 3 from the figure.

In the more recent drawing conventions (not that that matters for the formalism) the port names are in blue.

Here is again the same move, but without the epsilon and mu.

r2_newm

Of course, the green node is the fanout, in the chemlambda version.

Yes, eventually, everything is related to everything in this open notebook.

In the next posts I shall take it step by step.

________________________________________________________________

 

 

 

 

 

 

 

 

My first NSF experience and the future of GLC

Just learned that the project “Secure Distributed Computing with Graphic Lambda Calculus” will not be funded by NSF.

I read the reviews and my conclusion is that they are well done. The 6 reviewers all make good points and a good job to detect strong points and weaknesses of the project.

Thank you NSF for this fair process. As the readers of this blog know, I don’t have the habit to hide my opinions about bad reviews, which sometimes may be harsh. Seen from this point of view, my thanks look, I hope, even more sincere.

So, what was the project about? Distributed computing, like in the “GLC actors, artificial chemical connectomes, topological issues and knots”  arXiv:1312.4333 [cs.DC], which was branded as useful for secure computing. The project has been submitted in Jan to Secure and Trustworthy Cyberspace (SaTC) NSF program.

The point was to get funding which allows the study of the Distributed GLC, which is for the moment fundamental research.  There are reasons to believe that distributed GLC may be good for secure computing, principal among them being that GLC (and chemlambda, actually the main focus of research) is not based on the IT paradigm of gates and wires, but instead on something which can be described as signal transduction, see How is different signal transduction from information theory?   There is another reason, now described by the words “no semantics“.

But basically,  this is not naturally a project in secure computing. It may become one, later, but for the moment the project consists into understanding asynchronous, decentralized computations performed by GLC actors and their biological like behaviour. See What is new in distributed GLC?

Together with Louis Kauffman, we are about to study this, he will present at the ALIFE 14 conference our paper  Chemlambda, universality and self-multiplication,   arXiv:1403.8046.

There is much more to tell about this, parts were told already here at chorasimilarity.

From this moment I believe that instead of thinking security and secrecy, the project should be open to anybody who wishes to contribute, to use or to criticize. That’s the future anyway.

______________________________________________________

 

 

Experimental alife IoT with Tessel

Here is an idea for testing the mix between the IoT and chemlambda.  This post almost qualifies as an What if? one but not quite, because in principle it might be done right now, not in the future.

Experiments have to start from somewhere in order to arrive eventually to something like a Microbiome OS.

Take Tessel.

Tessel is a microcontroller that runs JavaScript.
It’s Node-compatible and ships with Wifi built in.

Imagine that there is one GLC actor per Tessel device. The interactions between GLC actors may be done partially via the Wifi.

The advantage is that one may overlap the locality of graph rewrites of chemlambda with space locality.

 

Each GLC actor has as data a chemlambda molecule, with it’s in and out free arrows (or free chemical bonds) tagged with names of other actors.

A bond between two actors form, in the chemlambda+Tessel world, if the actors are close enough to communicate via Wifi.

Look for example at the beta move, done via the behaviour 1 of GLC actors. This may involve up to 6 actors, namely the two actors which communicate via the graphic beta move and at most 4 other actors which have to modify their tags of neighbouring actors names as a result of the move. If all are locally connected by Wifi then this becomes straightforward.

What would be the experiment then? To perform distributed, decentralized computations with chemlambda (in particular to do functional programming in a decentralized way) which are also sprawled over the physical world.  The Tessel devices involved in the computation don’t have to be all in possible Wifi connections with the others, on the contrary, only local connections would be enough.

Moreover, the results of the computations could as well have physical effects (in the sense that the states of the actors could produce effects in the real world) and as well the physical world could be used as input for the computation (i.e. the sensors connected to Tessel devices could modify the state of the actor via a core-mask mechanism).

That would play the role of a very primitive, but functional, experimental ancestor of a Microbiome OS.

 

_______________________________________________