5 ms·

Immediately I'm reminded of the SKI calculus as an extremely minimal model for computation [0]. Edit: in fact, they even define the SKI combinators in their de

by ryandv 2y ago

Immediately I'm reminded of the SKI calculus as an extremely minimal model for computation [0]. Edit: in fact, they even define the SKI combinators in their demonstration of Turing completeness, so I wonder how the tree calculus differs aside from being based on only a single combinator. [0] https://en.wikipedia.org/wiki/SKI_combinator_calculus https://en.wikipedia.org/wiki/SKI_combinator_calculus [1] https://treecalcul.us/live/?example=demo-turing-intensional https://treecalcul.us/live/?example=demo-turing-intensional

gatane 2y ago
Your example reminds me of Binary Lambda Calculus [0]: [0] https://tromp.github.io/cl/Binary_lambda_calculus.html https://tromp.github.io/cl/Binary_lambda_calculus.html
casey2 2y ago
The point of tree calculus as I understand is that all programs are valid data structures, so they can be modified and analyzed during runtime with nothing but other programs.
- adastra22 2y ago
  That is also true of Lisp. And Forth. And a dozen other homoiconic languages.
  - fmoralesc 2y ago
    Any Turing-complete language should be able to express programs that do this.
sitkack 2y ago
An Architecture for Combinator Graph Reduction (TIGRE) https://users.ece.cmu.edu/~koopman/tigre/index.html https://users.ece.cmu.edu/~koopman/tigre/index.html
xigoi 2y ago
The difference seems to be that tree-calculus is intensional – you can distinguish different trees within the language even if they have the same computational value.
tromp 2y ago
It's not based on a single combinator. It's based on the two standard basis combinators S and K, and a non-combinator that can inspect normalized terms to distinguish between degrees 0,1,and 2.
- quchen 2y ago
  A combinator is just a term without free variables. All the rules can be put as combinators, it’s just that they don’t have common names like SKICB(…).
- alan-crowe 2y ago
  As far as I understand it so far, the idea that the trees are "unlabeled" over simplifies. The most common kind of binary tree is defined as binary-tree = nil | node of binary-tree label binary-tree for example empty-tree node nil Alice nil node nil Bob (node nil Carol nil) node (node nil David nil) Edward (node nil Fred nil) node (node nil George nil) Harold nil If we erase the labels, there remains an implicit label Alice = 00, Bob = 01, Carol = 00, David = 00, Edward = 11, Fred = 00, George = 00, Harold = 10 encoded by the pattern of empty trees. The trees in the article seem to be doing it slightly differently, with implicit labels 0,1, or 2. Edward is erased, leaving an implicit 2 and the erasure of both Bob and Harold leaves an implicit 1 for both of them, removing the distinction between 01 and 10. Edited to add: I'm up to page 27 (pdf reader says page 39 of 176) and some nodes have three children. 0, 1, or 2 children represent "values". "It follows that trees containing a node with three of more branches is a computation that is not a value, and so must be evaluated."

by ryandv 2y ago

gatane 2y ago

Your example reminds me of Binary Lambda Calculus [0]: [0] https://tromp.github.io/cl/Binary_lambda_calculus.html https://tromp.github.io/cl/Binary_lambda_calculus.html

casey2 2y ago

The point of tree calculus as I understand is that all programs are valid data structures, so they can be modified and analyzed during runtime with nothing but other programs.

adastra22 2y ago
That is also true of Lisp. And Forth. And a dozen other homoiconic languages.
- fmoralesc 2y ago
  Any Turing-complete language should be able to express programs that do this.

sitkack 2y ago

An Architecture for Combinator Graph Reduction (TIGRE) https://users.ece.cmu.edu/~koopman/tigre/index.html https://users.ece.cmu.edu/~koopman/tigre/index.html

xigoi 2y ago

The difference seems to be that tree-calculus is intensional – you can distinguish different trees within the language even if they have the same computational value.

tromp 2y ago

It's not based on a single combinator. It's based on the two standard basis combinators S and K, and a non-combinator that can inspect normalized terms to distinguish between degrees 0,1,and 2.

quchen 2y ago
A combinator is just a term without free variables. All the rules can be put as combinators, it’s just that they don’t have common names like SKICB(…).
alan-crowe 2y ago
As far as I understand it so far, the idea that the trees are "unlabeled" over simplifies. The most common kind of binary tree is defined as binary-tree = nil | node of binary-tree label binary-tree for example empty-tree node nil Alice nil node nil Bob (node nil Carol nil) node (node nil David nil) Edward (node nil Fred nil) node (node nil George nil) Harold nil If we erase the labels, there remains an implicit label Alice = 00, Bob = 01, Carol = 00, David = 00, Edward = 11, Fred = 00, George = 00, Harold = 10 encoded by the pattern of empty trees. The trees in the article seem to be doing it slightly differently, with implicit labels 0,1, or 2. Edward is erased, leaving an implicit 2 and the erasure of both Bob and Harold leaves an implicit 1 for both of them, removing the distinction between 01 and 10. Edited to add: I'm up to page 27 (pdf reader says page 39 of 176) and some nodes have three children. 0, 1, or 2 children represent "values". "It follows that trees containing a node with three of more branches is a computation that is not a value, and so must be evaluated."