News for hackers. Stuff that matters.

A comment on Tree Calculus.

Re:Tree Calculus by js8 on Tuesday December 10, 2024 @07:14AM (#42376130)
AFAIK there are many variations (I think infinite, even) of "tree calculi". You can build one easily from combinatory logic by using only one universal combinator, which will be implied at the leafs of the tree.

John Tromp in his repo has some research pertaining to short universal lambda expressions (each can be expressed as combinators) of this type: https://github.com/tromp/AIT/blob/master/Bases.lhs

[ Parent | on HN ]
Re:Tree Calculus by olydis on Tuesday December 10, 2024 @07:20AM (#42376171)
Super cool, thanks for the pointer! I'll note, though, that one of the main value adds of (this) TC is that it is also intensional.

See website for some elaboration and examples, I'd particularly recommend looking at https://treecalcul.us/live/?example=demo-fusion which demos a little stream fusion optimizer, entirely from scratch, including small test.

[ Parent | on HN ]
Re:Tree Calculus by js8 on Tuesday December 10, 2024 @07:27AM (#42376212)
Oh, OK! I think it would be interesting to know to which universal combinator (or lambda expression) is the 't' related to.
[ Parent | on HN ]
Re:Tree Calculus by chriswarbo on Tuesday December 10, 2024 @01:09PM (#42379458)
Reduction rules (1) and (2) correspond to those of K and S, respectively. Reduction rule (3) corresponds to the elimination form for a Scott-encoding of a datatype like `X = Leaf | Stem X | Fork X X`. The cases of rule (3) are essentially parsing the argument into one of these three forms, and dispatching on the result.
[ Parent | on HN ]