Tree Calculus • Hacker News Board

Re: Tree Calculus

#31

Post by steego » Thu, Apr 09, 2026, 10:31 PM UTC

bawolff wrote: post #23

robot-wrangler wrote: post #21

Earlier quoted context omitted.

https://github.com/barry-jay-personal/tree-calculus/blob/mas...

Surely there is a middle ground between a book length treatment and whatever the linked page was that fails to give a definition or motivation.

This introduction to this paper explains the motivation:

https://dl.acm.org/doi/pdf/10.1145/3704253.3706138

Tree Calculus is an alternative to lambda calculus that is capable of doing meta-theory without having to construct or bolt on something else entirely.

If lambda calculus provides a theoretical foundation for a language like Lisp. Tree calculus provides a theoretical foundation for a Lisp with a macro system that is fundamentally part of the core calculus.

You don’t have to write parsers and other stuff to do meta programming. It’s fundamentally built in and the paper I posted above explores how to construct type systems as a library, not as something that is outside of the runtime environment.

Here’s what’s really cool about it too: Just like lambda calculus, you can evaluate tree calculus with pencil and paper.

It’s very slick.

Re: Tree Calculus

#32

Post by steego » Thu, Apr 09, 2026, 10:55 PM UTC

gram-hours wrote: post #13

> Tree calculus is minimal, Turing-complete, reflective, modular Ok. But what is it?

You can think of a calculus as a mathematical system one can use to define the essential computational basis for how a programming language or a runtime works mathematically.

Lambda calculus is often the foundation for functional programming languages, but lambda calculus is also a mathematical system you can calculate things with pencil and paper.

What makes lambda calculus interesting is it’s a relatively simple mathematical system where EVERYTHING is defined as a function. I’m serious. Imagine a programming language where you don’t have numbers, bools, if statements, while loops, gotos, etc.

You only have functions. All functions accept one argument (a function) and they always return functions.

Tree calculus is like lambda calculus, but it takes the idea a bit further. Not only can tree calculus do all this stuff where you create functions from other functions, tree calculus is fundamentally capable of reflecting on itself in a way that allows it to easily understand and transform its own interpreter.

In other words, if you base a programming language on tree calculus, your programming language or interpreter will allow you to create programs that can reflect on and transform other programs just like it was any other piece of data.

It’s pretty remarkable, especially when you find out how simple a core tree calculus based language can be implemented.

Re: Tree Calculus

#33

Post by bawolff » Thu, Apr 09, 2026, 11:43 PM UTC

robot-wrangler wrote: post #28

bawolff wrote: post #23

Earlier quoted context omitted.

Surely there is a middle ground between a book length treatment and whatever the linked page was that fails to give a definition or motivation.

My friend this ain't memes or celebrity news, it's theoretical computer science. You'll get out of it roughly what you're ready to put into it. If you're short on time, the grammar is like 5 characters and the proof of the halting problem isn't much bigger. If you don't already know why that is interesting though you really might have to read a bit to find out

That's my complaint, this page is essentially a meme.

And yes, i know enough about computer science to know that making an axinomic system with a short grammar that has a proof that the halting problem is undecidable, isn't particularly note worthy by itself. I highly doubt the reason people are interested in this is just code golfing a proof of the undecidability of the halting problem

Re: Tree Calculus

#34

Post by froh » Fri, Apr 10, 2026, 5:20 AM UTC

seanhunter wrote: post #9

timcobb wrote: post #2

I'm not used to math things being promoted like this (not to suggest that's a bad thing at all!). Can someone offer some context please.

This isn't a math thing[1], it's a theoretical computing model (ie instead of a Turing machine or lambda calculus, you can use this instead) that you might study as part of studying computation theory or other bits of theoretical computer science. [1] or not pure maths anyway. It's applied maths like all computer science.

is theoretical computer science (turing machines and automata theory, lambda calculus, complexity theory, computability, devidability, etc) pure maths? or applied maths indeed?

tree calculus is theoretical computer science for sure.

and that, computer science, in its beginnings at least, until the 1950s or so, was a field of mathematics, like algebra, or analysis or logic. all of which have pure maths parts and applied maths parts, don't they?

long story short, I don't think theoretical computer science is "applied maths", it to the contrary can be deep in pure maths land.

Re: Tree Calculus

#35

Post by phlakaton » Sun, Apr 12, 2026, 4:12 AM UTC

wordToDaBird wrote: post #26

phlakaton wrote: post #11

Earlier quoted context omitted.

I think it might be a bad thing. I'm no stranger to math or computer science, but even after staring at the front page for a minute I was ready to dismiss this as the ravings of a lunatic. It's like they had the idea of marketing this like a software project, not realizing that most front pages of software projects are utter bunk as well. It introduces terminology and syntax with no motivation or explanation. Even on…

Get good, IDK where you’re from but we don’t generally spoon feed here. https://github.com/barry-jay-personal/tree-calculus/tree/mas... If you don’t understand what it does, it’s not for you. But if you don’t understand what it does, get good. TLDR; what happens when a very small piece of js can be run in the browser or any environment and offer a meta programming layer, that is stupid simple, but also useful because…

I've been here longer than you, buddy. I think you're the one that needs to leave.

Re: Tree Calculus

#36

Post by barryjay » Tue, Apr 14, 2026, 5:15 AM UTC

Tree calculus is more expressive, can define more functions, than lambda calculus or traditional combinatory logic. This theorem is so startling, so outrageous, that mere proof, even a formal proof, is not enough to get the message across. This is no one’s fault. To help, I am currently writing a series of conversations, where the characters come at these ideas from many points of view, letting it all hang out. It doesn’t help that the current formal proof of the theorem is indirect. So here is a challenge for you all. Find a direct proof that the node operator of tree calculus is not definable in traditional combinatory logic. That is, no SK-combinator satisfies the equations of tree calculus. Conversely, trying to find such a combinator may give you a better feel for intensionality.

Re: Tree Calculus

#37

Post by pgt » Wed, Apr 15, 2026, 11:12 PM UTC

lupire wrote: post #18

pgt wrote: post #16

Earlier quoted context omitted.

@dang, pleaaase can we get proper markdown formatting on HN? I tried adding two spaces after each line, but I don't want paragraphs between code

4 spaces indent The inversion is really cool, e.g. > f = λa λb concat ["Hello ", a, " ", b, "!"] > f "Jane" "Doe" Hello Jane Doe! then, > g = f "Admiral" > invert g "Hello Admiral Alice!" Alice

thx that looks much better, but I'll forget that syntax in the next 3 months. nowadays I am just casual commenter on HN spending points on contrarian views that I know will be downvoted and I know no one else will say it.