Use the lambda to chemlambda parser to see when the translation doesn’t work

I use the parser page mainly and other pages will be mentioned in the text.

So chemlambda does not solve the problem of finding a purely local conversion of lambda terms to graphs, which can be further reduced by a purely local random algorithm, always. This is one of the reasons I insist both into going outside lambda calculus and into looking at possible applications in real chemistry, where some molecules (programs) do reduce predictively and the span of the cascade of reactions (reductions) is much larger than one can achieve via massive brutal try-everything on a supercomputer strategy.

Let’s see: choose

(\a.a a)(\x.((\b.b b)(\y.y x)))

it should reduce to the omega combinator, but read the comment too.

Another example took me by surprise. Now you can choose “omega from S,I combinators”, i.e. the term

(\S.\I.S I I (S I I)) (\x.\y.\z.(x z) (y z)) \x.x

It works well, but l previously used a related term, actually a mol file, which corresponds to the term where I replace I by S K K in S I I (S I I), i.e. the term

S (S K K) (S K K) (S (S K K) (S K K))

To see the reduction of this term (mol file) go to this page and choose “omega from S,K combinators”. You can also see how indeed S K K reduces to I.

But initially in the parser page menu I had  the term

(\S.\K.S (S K K) (S K K) (S (S K K) (S K K))) (\x.\y.\z.(x z) (y z))

It should reduce well but it does not. The reason is close to the reason the first lambda term does not reduce well.

Now some bright side of it. Look at this page to see that the ouroboros quine is mortal. I believed it is obviously imortal until recently. Now I started to believe that imortal quines in chemlambda are rare. Yes, there are candidates like (the graph obtained from) omega, or why not (try with the parser) 4 omega

(\f.(\x.(f(f (f (f x)))))) ((\x.x x) (\x.x x))

and there are quines like the “spark_243501” (shown in the menu of this page) with a small range of behaviours. On the contrary, all quines in IC are imortal.

Lambda calculus to chemlambda parser (2) and more slides

This post has two goals: (1) to explain more about the lambda to chemlambda parser and (2) to talk about slides of presentations which are connected one with the other across different fileds of research.

(1) There are several incremental improvements to the pages from the quine graphs repository. All pages, including the parser one, have two sliders, each giving you control about some parameters.

The “gravity” slider is kind of obvious. Recall that you can use your mose (or pinching gestures) to zoom in or out the graph you see. With the gravity slider you control gravity. This allows you to see better the edges of the graph, for example, by moving the gravity slider to the minimum and then by zooming out. Or, on the contrary, if you have a graph which is too spreaded, you can increase gravity, which will have as aeffect a more compactly looking graph.

The “rewrites weights slider” has as extrema the mysterious words “grow” and “slim”. It works like this. The rewrites (excepting COMB, which are done preferentially anyway) are grouped into those which increase the number of nodes (“grow”) and the other ones, which decrease the number of nodes (“slim”).

At each step, the algorithm tries to pick at random a rewrite. If there is a COMB rewrite to pick, then it is done. Else, the algorithm will try to pick at random one “grow” and one “slim” rewrite. If there is only one of these available, i.e. if there a “grow” but no “slim” rewrite, then this rewrite is done. Else, if there is a choice between two randomly choses “grow” and “slim” rewrites, we flip a coin to choose among them. The coin is biased towards “grow” or “slim” with the rewrites weights slider.

This is interesting to use, for example with the graphs which come from lambda terms. Many times, but not always, we are interested in reducing the number of nodes as fast as possible. A strategy would be to move the slider to “slim”.

In the case of quines, or quine fights, it is interesting to see how they behave under “grow” or “slim” regime.

Now let’s pass to the parser. Now it works well, you can write lambda terms in a human way, but mind that “xy” will be seen as a variable, not as the application of “x” to “y”. Application is “x y”. Otherwise, the parser understands correctly terms like

(\x.\y.\z.z y x) (\x.x x)(\x. x x)\x.x

Then I followed the suggestion of my son Matei to immediately do the COMB rewrites, thus eliminating the Arrow nodes given by the parser.

About the parser itself. It is not especially short, because of several reasons. One reason is that it is made as a machine with 3 legs, moving along the string given by the lexer. Just like the typical 3-valent node. So that is why it will be interesting to see it in action, visually. Another reason is that the parser first builds the graph without fanout FO and termination T nodes, then adds the FO and and T nodes. Finally, the lambda term is not prepared in advance by any global means (excepting the check for balanced parantheses). For example no de Bruijn indices.

Another reason is that it allows to understand what edges of the (mol) graph are, or more precisely what port variables (edge variables) correspond to. The observation is that the edges are in correspondence with the position of the item (lparen, rparen, operation, variable) in the string. We need at most N edge names at this stage, where N is the length of the string. Finally, the second stage, which adds the FO and T nodes, needs at most N new edge names, practically much less: the number of duplicates of variables.

This responds to the question: how can we efficiently choose edge names? We could use as edge name the piece of the string up to the item and we can duble this number by using an extra special character. Or if we want to be secretive, now that we now how to constructively choose names, we can try to use and hide this procedure.

Up to now there is no “decorator”, i.e. the inverse procedure to obtain a lambda term from a graph, when it is possible. This is almost trivial, will be done.

I close here this subject, by mentioning that my motivation was not to write a parser from lambda to chemlambda, but to learn how to make a parser from a programming language in the making. You’ll see and hopefully you’ll enjoy 🙂

(2) Slides, slides, slides. I have not considered slides very interesting as a mean of communication before. But hey. slides are somewhere on the route to an interactive book, article, etc.

So I added to my page links to 3 related presentations, which with a 4th available and popular (?!) on this blog, give together a more round image of what I try to achieve.

These are:

• popular slides of a presentation about hamiltonian systems with dissipation, in the form baptized “symplectic Brezis-Ekeland-Nayroles”.  Read them in conjuction with arXiv:1902.04598, see further why
• (Artificial physics for artificial chemistry)   is a presentation which, first, explains what chemlambda is in the context of artificial chemistries, then proceeds with using a stochastic formulation of hamiltonian systems with dissipation as an artificial physics for this artificial chemistry. An example about billiard ball computers is given. Sure, there is an article to be written about the details, but it is nevertheless interesting to infer how this is done.
• (A kaleidoscope of graph rewrite systems in topology, metric geometry and computer science)  are the most evolved technically slides, presenting the geometrical roots of chemlambda and related efforts. There are many things to pick from there, like: what is the geometrical problem, how is it related to emergent algebras, what is computation, knots,  why standard frames in categorical logic can’t help (but perhaps it can if they start thinking about it), who was the first programmer in chemlambda, live pages where you can play with the parser, closing with an announcement that indeed anharmonic lambda (in the imperfect form of kali, or kaleidoscope) soves the initial problem after 10 years of work. Another article will be most satisfactory, but you see, people rarely really read articles on subjects they are not familiar with. These slides may help.
• and for a general audience my old (Chemlambda for the people)  slides, which you may appreciate more and you may think about applications of chemlambda in the real world. But again, what is the real world, else than a hamiltonian system with dissipation? And who does the computation?

 

 

Slides for 10 years of emergent algebras

UPDATE: I added lots of links, if you need more please tell.

I put online the slides for the talk A kaleidoscope of graph rewrite systems in topology, metric geometry and computer science, Dec. 4th 2019, at IMAR. After I wrote them, it turns out that an alternative name would be: 10 years of emergent algebras :).

Quine graphs up to now

After I put the parser page online, it messed with the other pages, but now everything is allright.

All examples have comments.

See all the pages:

• Interaction Combinators and chemlambda quine graphs:  https://mbuliga.github.io/quinegraphs/ice.html
• The Ouroboros: https://mbuliga.github.io/quinegraphs/ouroboros.html
• Graphs figth arena (will turn into a tool to explore communities of quines): https://mbuliga.github.io/quinegraphs/arena.html
• Lambda terms reduced with chemlambda: https://mbuliga.github.io/quinegraphs/lambda.html
• Lambda calculus to chemlambda parser. https://mbuliga.github.io/quinegraphs/lambda2mol.html

 

Lambda calculus to chemlambda parser

To play with at this page.  There are many things to say, but will come back later with details about my first parser and why is it like this.

UPDATE: After I put the parser page online, it messed with the other pages, but now everything is allright.

UPDATE: I’ll demo this at a conference on Dec 4th, at IMAR, Bucharest.

Here are the slides.

The title is “A kaleidoscope of graph rewrite systems in topology,metric geometry and computer science“.

So if you are in Bucharest on Dec 4th, at 13h, come to talk. How to arrive there.

I already dream about a version which is purely “chemical”, with 3-legged parser spiders reading from the DNA text string and creating the molecules.

Will do, but long todo list.

Quine graphs (5), anharmonic logic and a flute

Several things:

• added a new control to the quine graphs pages (all can be accessed from here). Is caled the “rewrites weights slider”: you can either favor the rewrites DIST, which add nodes to the graph, or the rewrites β  which take away nodes from the graph (for chemlambda these are the L-A rewrite, but also the termination rewrites and FI-FOE). This changes, sometimes radically, the result of the algorithm. It depends what you want. In the case of reductions of lambda terms, you may want to privilege β rewrites, but as usual this is not generally true, see the last example. In the case of the fight arena for quines, you can favor a species of quines over another by your choice.
• of course in the background I continue with kali, or anharmonic lambda calculus. The new thing is that why not conceive a programming language which compiles to kali? It works fine, you can say things as

“from a see b as c” or

“let a mark b as c” or

“is a as b” or

“c := let x  = b in c”

and many others! Soon, hope at the beginning of December, will be available.

• It helps to do new things, so I finished t day my first flute. Claudia, my wife, is a music professor and her instrument of choice is the flute. From a physics point of view a flute is a tube with holes placed in the right possitions, how hard would it be to make one? After I made it, it is usable but I started to learn a lot of stuff about how unnatural is the modern flute and how much you can play with all variables. As a mathematician I  oscilate between “is a known thing to simulate a flute numerically” and “I shall concentrate on the craft and will play with various techniques”. My first flute was a craft only effort, but now, when I know more, I am hooked!

OK, so that’s the news, I like to make things!

 

A small ouroboros has a short life (Quine graphs 4)

As I said many times, there is a lot of background to the hundreds of chemlambda mol files and associated simulations. Now that I took the Quine graphs repository seriously, I have to select rather clear and short strings of facts associated to the mol files, so that I can tell clear and short enough stories.

So it came out of the depth of this pile of stuff I have that the ouroboros is not an immortal quine. It can die and his life is of the order exp(length) where length is the length of the double track it contains.  The shortest ouroboros appears here (look in the MENU).

Otherwise, I reorganize (and continue to do so) the js scripts, so that they become easy to understand. Now there is a chemistry, nodes, etc. so thare will be a convergence with the modules of hapax.