Chemlambda, graph theory etc

[NodixBlockchain]

Hello Guy, ive been doing lot of expetimentation lately on parsers, grammar and graph theory, and started to dig the relationship between graph theory and computation theory.

Deep down, all those algorithm of parser combinators, ll/lr parser etc seem to always come down to a tree representation, and i started to dig the relationship between graph theory and computation model.

Just yesterday i found this article

 https://blog.reverberate.org/2013/07/ll-and-lr-parsing-demystified.html

There are three ways of traversing a binary tree, as explained on Wikipedia: in-order, pre-order, and post-order. They differ in whether you visit the parent node before (pre-order), after (post-order), or in between (in-order) the children of that parent. These three correspond exactly to infix, Polish, and Reverse Polish notation:

1 + 2 * 3 // Infix expression; in-order traversal.

• 1 * 2 3 // Polish (prefix) expression; pre-order traversal.
  1 2 3 * + // Reverse Polish (postfix) expression; post-order traversal.

So Polish and Reverse Polish notation fully encode a tree structure and the steps you would take to traverse it. The main difference between these encodings and an actual parse tree is that Polish and Reverse Polish encodings are not random access. With a real tree you can choose to follow an interior node to its right subtree, its left subtree, or even (for many trees) its parent. With these linear encodings there is no such flexibility: you have to follow the traversal as it is already encoded

Thats an example of how tree theory and the way to process a tree has also implication into computation model.

While digging this,i found this this thing called chemlambda, who seems To be a model of computation based on graph theory, with graph rewrite operations that allow to modify the graph, which allow a way of formal self modifying code.

 Apparently chemlambda is inspired from this model

 http://tuvalu.santafe.edu/~walter/AlChemy/Statement/organization.html

Which i find very inspiring, and i found it has implication in both complexity theory, and distributed systems.

Its extremely interesting To me, especially this part

A central theme of this project is our emphasis on the action of "agents" as consisting in a mapping from "agents" to "agents". The foundational distinction between this project and others sharing similar emphasis is that none of the others have the feature of being interpretable as mathematical structures. To bootstrap a theory of biological organization, requires a formalization of chemistry that is useful for biology. Ultimately this means defining "interaction" and "structure of an entity" mutually. In our case "structure of an entity" will specifically come to mean a formula, expression, or term within a syntactical system resulting from a theory about the possible interactions characterizing that class of entities. To be illuminating, a linkage between structure and interaction must connect to a mathematical theory.

Stable relational structures are what conventional dynamical systems take as a given. If we aim at a description of their genesis, we must extend our description of the world to include a sound and sufficiently general dynamics of relationships capable of generating stable relational structures as stationary outcomes. What enables any such dynamics from within, we submit, is at the very minimum a notion of entities that lead this subtle double-life: entities that simultaneously act as relationships between entities (by being interpretable as functions on them).

Which remove the barrier between "code" and "data" in sort that you can have functions that take a function as an input and output another function, which allow for this kind of algebra needed for self organising structures. It seem to be a solution for parallelism, decentralised distributed system, and self modifying code, which look like an holy grail to me :)

I started to experiment with this and exploring this relationship between graph theory and computation model, but cant seem to find lot of information on this. It seems to be a given that a parser can output parse tree, and that those parse tree can be turned to turing complete system but i cant really find real deep formal theory on this.

I have this hunch that for example sticking to what can be represented as a DAG without backward references prevent loop and infinite recursion.

As i use a blockchain system to store the tree, with nodes referenced by their hash, it naturally prevent cycles. I just added some instruction to have equivalent of map working on lists, and recursive operations on data tree like to compute skeletal animation based on quaternion, and it seems to works well.

With a lr parsing style it even seem to allow very clean handling of asynchronous function, as all the computation that has To be done on the result is on the stack when the asynchronous function is called, so it can easily be added to the handler code and executed asynchronously when the function is done, and all the dependancy graph is explicit.

In theory using this sort of algebra can also allow runtime polymorphism, as if you can have graph operation working on the computation graph, it can allow to generate monomorphised function based on the polymorphic version, while still keeping in the realm of formal system.

In theory it can be done at compile time, load time or runtime, and i think can even elucidate the interface problem as function can be checked for their type with graph operations. And in theory graph rewrite operation like in chemlambda seem to be a good way to represent polymorphism.

And in theory it can accomodate with self modifying code, and all kind of dynamic system modeling, even if it seems to escape common computation rules.

But i cant seem to find lot of formal definition of how tree properties translate to computation model, even if it seem to me computation model can always be mapped to a tree, and its very easy to have a system of formal operations working on graph, which i think can be a way to have runtime polymorphism.

Its a paradigm that got stuck in my mind and it seems i cant really nail this sort of relationship or find formal systems describing this.

[shelby3]

https://www.discovermagazine.com/the-sciences/new-theory-of-everything-unites-quantum-mechanics-with-relativity-and-much

https://www.wired.com/story/stephen-wolfram-invites-you-to-solve-physics/

https://www.scientificamerican.com/article/physicists-criticize-stephen-wolframs-theory-of-everything/

https://gizmodo.com/the-trouble-with-stephen-wolfram-s-new-fundamental-theo-1842985419

https://www.forbes.com/sites/startswithabang/2020/05/13/3-simple-reasons-why-wolframs-new-fundamental-theory-is-not-yet-science/

https://interestingengineering.com/the-theory-of-everything-by-wolfram-gets-criticized-by-physicists

[NodixBlockchain]

hello :)

I found out as well it has a connection with physics, even if that was not what i was seeking in the first place.

I could talk to a good physicist who told it looked close to prigogine thermodynamics
https://en.wikipedia.org/wiki/Ilya_Prigogine

As i'm also quite into edelman and whiteheads it would not suprise me that there are connections in physics. I would just answer this How is Natural Science Possible?: Whitehead's 1st Lecture at Harvard (1924) :)

I couldn't find a direct connection between wolfram model and this one, but it's close in the principle, it's likely one inspired the other or they have same implication with physics.

https://arxiv.org/pdf/1811.04960.pdf

The references and links in the text are left as they were and much improvement could be made concerning references pointing to Interaction Nets [2], for example; Berry and Boudol CHAM [1] is not explicitely mentioned here, but the initial version of this formalism, i.e. ”chemical concrete machine”[13], uses it. The Algorithmic Chemistry of Fontana and Buss [3] [4] appears here via a link to their research, perhaps this link is better. The same happens with the work [5] by Christoph Flamm, for which, in the body of the article, a link to his papers page is provided. Part of this was due to the ignorance of the author at the moment (a mathematician). A later hope was to keep the article as is and to link it with critical public reviews, as a weaker form of validation than, for example, an alternative Haskell implementation of chemlambda [5]. However, the main idea of the article is original, as are the self-imposed constraints, namely to restrict to only local rewrites on graphs, regardless their interpretation as lambda terms (or lack of such interpretation), restrict to only two algorithms of reduction (deterministic or random), the most simple possible.

This sort of model is more relevant for dealing with living organism than with inanimate objects like usual physics. There is already some hints of this in the way neural network works.

But it was not my original intent to get into physics.

Found this article that make a short summary of different way to achive polymorphism :

https://dev.to/jmcclell/inheritance-vs-generics-vs-typeclasses-in-scala-20op

Subtype Polymorphism (Inheritance)
subtyping allows a function to be written to take an object of a certain type T, but also work correctly, if passed an object that belongs to a type S that is a subtype of T (according to the Liskov substitution principle) [2]

Parametric Polymorphism (Generics)
Parametric polymorphism allows a function or a data type to be written generically, so that it can handle values uniformly without depending on their type [3]

Ad-hoc Polymorphism (Type Classes)
the term ad hoc polymorphism [refers] to polymorphic functions that can be applied to arguments of different types, but that behave differently depending on the type of the argument to which they are applied [4]

I will skip the first one based on subtyping because it still depend on static code, and some invariant among a category of different datatypes.

The 2 others are more relevant to where i want to get at, which is that you have a computation defined in a form that allow it to be combined with a type to yeld a version of the computation unique to that type.

So they both encode this notion of 'variable functions', but if i want to make a comparison on classic lambda function level, it's like if instead of computing the result from a value, you would pick an output value in a set of precomputed values based on the input. Much like you would use a table to compute a sinus if the cpu doesn't have sinus. The idea of dispatch table with a switch case is similiar to this principle. You have a set of predefined functions that are selected based on the input type. Whereas some computation rules applied to a graph could achieve the same thing. And it can also deal very well with asynchronous / simultaneous operations (even all of them are not executed in parrallel on the hardware).

My goal for the moment is not to have the whole range of operation that you would have in a real molecular computer, or to get to a physic model.

More to have some computation that can modify graph to alter the computation being done that can still fit into a formal model.

But it seems to me even having a graph represention is not enough to encode the computation because you also need to know the tree parsing method.

I already have this sort of things like to compute an HTML page based on a computation tree, need to compute leaf first, and embed the result into the parent node. While computing bones, you need to compute the branch in order and apply the result to the child branches. I'm pretty sure there must be a formal theory about that like explained in the article about ll/lr parsing, but can't put my finger on it.

[NodixBlockchain]

For those interested, i found the abstraction i was looking for in stepanov book 'elements of programming', he calls this 'coordinated structure' and gets into all the points i'm searching, in case someone end up with the same questions :)

I'm still digesting the two chapters but at least i feel less in uncharted territory :)

A concept is a coordinate structure if it consists of one or more coordinate
types, zero or more value types, one or more traversal functions, and zero or more
access functions. Each traversal function maps one or more coordinate types and/or
value types into a coordinate type, whereas each access function maps one or more
coordinate types and/or value types into a value type. For example, when considered
as a coordinate structure, a readable indexed iterator has one value type and two
coordinate types: the iterator type and its distance type. The traversal functions
are + (adding a distance to an iterator) and — (giving the distance between two
iterators). There is one access function: source.

Fun thing when i look for coordinated structure in google i find mostly result from chemistry =)

[keean]

@NodixBlockchain I think Stepanov's "Elements of Programming" is one of the best books on Generics I have read. I recommend reading it from start to finish several times. It is not an easy book, but once you get the idea of what is going on, the early chapters make a lot more sense.

I also recommend reading "From Mathematics to Generic Programming" by Stepanov & Rose as it presents the same material in a different way, which can help with understanding, plus some really interesting history of mathematics and programming.

[NodixBlockchain]

Yes there are all the algorithm to find isomorphism between "coordinated structures" and all those, couldn't find much reference to this term in the context of programming outside of stepanov book though.

The other book is also on my list, found some video on youtube as well.

[keean]

@NodixBlockchain Try "Data Structues and Network Algorithms" by Robert Endre Tarjan, which is a book on algorithms recommended by Stepanov.

[mbuliga]

I just found this issue, thank you for interest. There is now a new page of experiments and technical notes on chemlambda: https://chemlambda.github.io/index.html
which I hope can answer many questions. There is a lot of information which one can play with, spread over several repositories.
For more please let me know, I'd be happy to discuss more, because the project started from a question in geometry and it now returns to it, but there are many directions which I would like to develop, like the "made of money" idea from the repository hapax. or which I would like a real programmer to magically do it, like a graphical horoscope app which would allow chemlambda molecules to live and circulate between many phones :)

[NodixBlockchain]

https://youtu.be/2RMXujk5AhM?t=1543

Gerald Edelman - Brain Dynamics to Consciousness (Full Lecture)

the kind of theory i'm into :)

[NodixBlockchain]

I just found this issue, thank you for interest. There is now a new page of experiments and technical notes on chemlambda: https://chemlambda.github.io/index.html
which I hope can answer many questions. There is a lot of information which one can play with, spread over several repositories.
For more please let me know, I'd be happy to discuss more, because the project started from a question in geometry and it now returns to it, but there are many directions which I would like to develop, like the "made of money" idea from the repository hapax. or which I would like a real programmer to magically do it, like a graphical horoscope app which would allow chemlambda molecules to live and circulate between many phones :)

originally i found this project looking into relationship between graph and computation model, looked for things like 'graph theory + lambda calculus' and found this project :)

what i would have in mind is really some kind of computation model with self modifying code that would follow a formal computation theory, and i think going through graph theory is really the way to go, because chemlambda show how graph manipulation can lead to a whole computation model, that can be equivalent to lambda calculs, but also add more possibilities :)

In the video edelman mention several time graph theory as well.

i'm still digging the whole thing :)

[mbuliga]

Oh thank you. I'm more into applied biochemistry. Many links are available from the page of chemlambda, but maybe relevant for the situation we are in now is this short story https://archive.is/Ir9GG . I would search in databases of biochemical reactions for patterns akin to those I use (and everybody else does, in so various fields of math and computation). There is also the problem that graph rewrite systems (GRS) and term rewrite systems (TRS) are very different beasts. There is no clear way to define an isomorphism between a GRS and a TRS. Indeed, you can turn a term of a TRS into it's abstract syntactic tree, which is a graph. But you can't always turn a term rewrite into a graph rewrite on the tree graph, in such a way as to preserve the locality of the rewrite. In the opposite direction, it is sometimes possible to define a function which decorates the edges of a graph with terms, such that if the graph is the abstract syntactic tree of a term then the root edge of the graph is decorated with that term. However, if you pass to graph rewrites, even if the graph rewrite is local (like the graphical version of the beta rewrite say), the decoration of the graph changes globally. So I think that TRS and GRS are not comparable without the introduction of external hypotheses, which may destroy the meaning of the seeked isomorphism. An implication is that GRS-es with only local rewrites (like in nature) are not only a unnecessary graphical decoration of things which can be explained with TRS only (like lambda calculus), they are intrinsically interesting outside their (undefined properly) isomorphism with TRS-es. But you'll say that any GRS for which there is a program is equivalent with the TRS (the program). Agree! but the TRS will consist mainly of a generator of randomness and a destroyer of the supplimentary structure (like random shuffles of lists), all run on a machine whose code can't be controlled. On the other side a GRS like real chemistry uses real space and probability distributions which are function of the state, so again is not at all clear in what sense the two systems are really comparable. If though there is a low hanging fruit, is is that maybe in real chemistry we can identify a GRS which works (not perfectly but) well enough so we can use ideas from functional programming to get real chemical effects. And damned be the search for perfect semantics.

…

----- Original Message ----- From: "NodixBlockchain" <notifications@github.com> To: "keean/zenscript" <zenscript@noreply.github.com> Cc: "mbuliga" <Marius.Buliga@imar.ro>, "Comment" <comment@noreply.github.com> Sent: Tuesday, August 25, 2020 1:17:50 PM Subject: Re: [keean/zenscript] Chemlambda, graph theory etc (#48) https://youtu.be/2RMXujk5AhM?t=1543 Gerald Edelman - Brain Dynamics to Consciousness (Full Lecture) the kind of theory i'm into :)

-- You are receiving this because you commented. Reply to this email directly or view it on GitHub: #48 (comment)

[NodixBlockchain]

Thanks for the input :) I can see from your answer it doesn't seem there is a very clear formal system to get from GRS to TRS or vice versa.

Weirdly enough, edelman doesn't even really get into neurochemistry at all, he get his whole brain theory based on a mixture of philosophy, darwinism and computation model.

In theory it sort of lead to a category / type system, he made a robot that he called darwin, following this sort of principles

He make a statement like programs make mistake, mistake are a full part of darwinist process, but they don't crash from mistake, they learn from mistake.

I already started to get into computational model close to lambda calculus, based on blockchain which use a graph system, it's more limited than full lambda calculs/turing machine, but i'm pretty sure it can get close, even if i'm quite in the dark regarding the computation model it entails.

Already from the stepanov book i get that you need at least a tree/graph parsing order algorithm additionally to the graph itself, because the way it's processed change the result. He give all the algorithm to formalise how two 'coordinated structures' can be tested for isomorphism.

But it's already pretty cool, because the graph can be represented very easily graphically, so it allow to completely edit the computation visually automatically from the graph, and then the code to execute the graph looks very much like a parser combinator in the end.

It's not completely operational yet, i already have skeletal animation with a 3D scene represented using a graph like this. Using this system i think i'm already pretty close to have a full match between modification in the graph and term/functional programming representation.

But it's very experimental, i'm not sure where it's going to lead to, but so far i get pretty interesting result from it.

But what i got from chemlambda, is that it has this goal as well to have dynamic system that show some form of resillance in a random chaotic environment, or can form some organisational pattern based on some structural constraint and organise elements from random input. (not sure how to put that more eloquently :D )

kinda like this video

https://www.youtube.com/watch?v=7l38QUJENhE

https://www.youtube.com/watch?v=6LZvIkM6JqY

[mbuliga]

As long as your GRS is restricted to tree traphs, it is indeed equivalent with a TRS, where you translate terms to their AST. But what if the GRS does act on a class of graph larger than trees? Then the equivalence breaks (in interesting ways).

Here is, related to the video of Edelman lecture, the part about neural groups, an experiment with two "neurons".

available also in the collection here https://chemlambda.github.io/collection.html#159

These graphs are encodings of two linear systems with some inputs and outputs connected. Imagine something like having two lambda terms, say T1 and T2, and you mix their inputs (free variables) and outputs (values of the terms) in the sense that you feed some outputs into some inputs. Then you reduce this mix graphically.

[keean]

This is what electronics design tools like Symplectic do. The problem is that designs like this are very hard to reason about and verify. When I worked on VLSI designs we used to write a prototype in 'C' as it was much easier to validate, and then compare the data from the electronic system with the prototype for validation. The system I worked on was for MPEG encoding, so you would apply the same configuration settings to both systems and then compare the inputs and outputs bit for bit to validate the design. The point I am making is that designing free input/output systems is much harder than writing sequential code. So a language like this will not get used much, because not many people will be smart enough to use it, and those that do will spend a lot of time validating designs.

…

On Wed, 26 Aug 2020, 09:33 mbuliga, ***@***.***> wrote: As long as your GRS is restricted to tree traphs, it is indeed equivalent with a TRS, where you translate terms to their AST. But what if the GRS does act on a class of graph larger than trees? Then the equivalence breaks (in interesting ways). Here is, related to the video of Edelman lecture, the part about neural groups, an experiment with two "neurons". [image: 2neurons] <https://user-images.githubusercontent.com/39514942/91279759-95092c00-e78e-11ea-8d41-32bf778d8740.gif> available also in the collection here https://chemlambda.github.io/collection.html#159 These graphs are encodings of two linear systems with some inputs and outputs connected. Imagine something like having two lambda terms, say T1 and T2, and you mix their inputs (free variables) and outputs (values of the terms) in the sense that you feed some outputs into some inputs. Then you reduce this mix graphically. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#48 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAD4DYA5LC6Y3VQLNURQJBDSCTCFRANCNFSM4N6EKMMA> .

[NodixBlockchain]

This is what electronics design tools like Symplectic do. The problem is that designs like this are very hard to reason about and verify. When I worked on VLSI designs we used to write a prototype in 'C' as it was much easier to validate, and then compare the data from the electronic system with the prototype for validation. The system I worked on was for MPEG encoding, so you would apply the same configuration settings to both systems and then compare the inputs and outputs bit for bit to validate the design. The point I am making is that designing free input/output systems is much harder than writing sequential code. So a language like this will not get used much, because not many people will be smart enough to use it, and those that do will spend a lot of time validating designs.
…
On Wed, 26 Aug 2020, 09:33 mbuliga, @.***> wrote: As long as your GRS is restricted to tree traphs, it is indeed equivalent with a TRS, where you translate terms to their AST. But what if the GRS does act on a class of graph larger than trees? Then the equivalence breaks (in interesting ways). Here is, related to the video of Edelman lecture, the part about neural groups, an experiment with two "neurons". [image: 2neurons] https://user-images.githubusercontent.com/39514942/91279759-95092c00-e78e-11ea-8d41-32bf778d8740.gif available also in the collection here https://chemlambda.github.io/collection.html#159 These graphs are encodings of two linear systems with some inputs and outputs connected. Imagine something like having two lambda terms, say T1 and T2, and you mix their inputs (free variables) and outputs (values of the terms) in the sense that you feed some outputs into some inputs. Then you reduce this mix graphically. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#48 (comment)>, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAD4DYA5LC6Y3VQLNURQJBDSCTCFRANCNFSM4N6EKMMA .

yes ! it's not easy to write code like this, but the idea is that you don't build the graph by writing code, because the good thing about graph is that they can be very easily represented visually, and this sort of system works pretty well.

I had the chance to meet eric wenger, who is the author of meta synth/voyager etc for example, and this whole system works with graph that are edited visually and plugged into each others.

I already applied this principle like to build audio synth, dynamic web page, and 3D scenes, i think the mind still can cop very well with 'recursive graph' system, when they are presented visually.

For it to be meaningul it needs some amount of prebuilt basic functional/logic brick that can be semantically meaningful to begin with, as well as their composition/combination.

The meta synth system from eric wenger show it's possible to have this sort of functions that can work on audio/video/3d (depth field rendering with some algebra), that can be combined together. Didn't dig the software too much, but he showed me some quick demo of the system and the possibilities are amazing :)

Well that's mostly step 1, already if i manage to get there it would already be a thing :)

But then the step 2 to go in the edelman kind of direction is that you don't actually write the whole tree, but it's more 'goal oriented', and the 'system' will work by trial and error to find the graph solution to the problem.

In the video there is also this slide

And i think that's sort of the problem is that you can't really 'proove' too much why and how the solution work, or even if it's the best possible solution to the problem.

It would be similar to neural network, except neural network are complete black box, and they don't allow to extract meaningfull generalisation or categories or semantic by themselves, and often it require some pre step to prepare the data for the neural network to works well.

[mbuliga]

I agree, these GRS are not for humans, they are for machines or for understanding nature (biochemistry in this case). On the other hand, at first there were only (few) mathematicians playing with bits in the emerging computer architectures.

…

----- Original Message ----- From: "Keean Schupke" <notifications@github.com> The point I am making is that designing free input/output systems is much harder than writing sequential code. So a language like this will not get used much, because not many people will be smart enough to use it, and those that do will spend a lot of time validating designs.

-- You are receiving this because you commented. Reply to this email directly or view it on GitHub: #48 (comment)