TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

Tree Calculus

493 点作者 iamwil5 个月前

42 条评论

justosophy5 个月前
Tree Calculus is awesome with implications beyond this website.<p>Shame the website doesn&#x27;t attribute the creator and author Prof. Barry Jay. (Seems to be a pattern for them sadly, not sure why)<p>See Jay&#x27;s book on GitHub for more <a href="https:&#x2F;&#x2F;github.com&#x2F;barry-jay-personal&#x2F;tree-calculus&#x2F;blob&#x2F;master&#x2F;tree_book.pdf">https:&#x2F;&#x2F;github.com&#x2F;barry-jay-personal&#x2F;tree-calculus&#x2F;blob&#x2F;mas...</a>
评论 #42376008 未加载
评论 #42375581 未加载
__MatrixMan__5 个月前
I <i>think</i> this is really cool. It&#x27;s at least shaped like something really cool. But I need to have my hand held a little bit more than this page is set up for. Is there like a... for dummies version?
评论 #42374593 未加载
评论 #42373948 未加载
评论 #42375098 未加载
评论 #42374166 未加载
评论 #42374450 未加载
评论 #42373960 未加载
评论 #42373722 未加载
评论 #42374163 未加载
agnishom5 个月前
The homepage says &quot;Democratizing Functions&quot; and &quot;Democratizing Metatheory&quot;. Whatever that means, I have a strong feeling that this is an abuse of the word &quot;democraztizing&quot;
评论 #42374935 未加载
评论 #42377757 未加载
nlitened5 个月前
Here are some pictures I made for myself trying to &quot;feel&quot; the logic of Tree Calculus&#x27;s reduction rules: <a href="https:&#x2F;&#x2F;latypoff.com&#x2F;tree-calculus-visualized&#x2F;" rel="nofollow">https:&#x2F;&#x2F;latypoff.com&#x2F;tree-calculus-visualized&#x2F;</a> — might be handy for other people who are visual thinkers.
评论 #42380490 未加载
评论 #42376025 未加载
october81405 个月前
Is everyone upvoting this just pretending to understand what it is?
评论 #42375106 未加载
评论 #42375849 未加载
评论 #42375933 未加载
评论 #42375080 未加载
评论 #42375303 未加载
评论 #42375039 未加载
adastra225 个月前
Can someone explain how this is not Lisp with a different syntax? Or Forth?<p>I don’t mean that as a criticism or midwit dismissal. Just want to understand.
评论 #42374335 未加载
评论 #42375057 未加载
Trung02465 个月前
Interesting, I tried to convert Z combinator in SKI to this using the lambda calculus example then print out the tree. Untested:<p><pre><code> z = (t (t (t t (t (t (t (t (t t (t (t (t (t (t t)) (t t))) (t (t (t t)) (t t))))) (t (t (t t (t (t (t t (t (t (t t t)) t))) (t t)))) (t (t (t t (t (t (t (t (t t)) (t t)))))) (t t))))) (t t (t (t (t (t (t t))))))))) (t (t (t (t (t t (t (t (t (t (t t (t (t (t t (t (t (t t t)) t))) (t t)))) (t (t (t t t)) t))) (t t (t t))))) (t (t (t t (t (t (t (t (t t (t (t (t t (t (t (t t t)) t))) (t t)))) (t (t (t t t)) t))) (t t (t t))))) (t (t (t t (t (t (t t t)) t))) (t t))))) (t t (t (t (t (t (t t (t (t (t (t (t t)) (t t))) (t (t (t t)) (t t))))) (t (t (t t (t (t (t t (t (t (t t t)) t))) (t t)))) (t (t (t t (t (t (t (t (t t)) (t t)))))) (t t))))) (t t (t (t (t t (t (t (t (t (t t (t (t (t (t (t t (t (t (t t (t (t (t t t)) t))) (t t)))) (t (t (t t t)) t))) (t t (t t))))) (t (t (t t (t (t (t (t (t t (t (t (t t (t (t (t t t)) t))) (t t)))) (t (t (t t t)) t))) (t t (t t))))) (t (t (t t (t (t (t (t (t t)) (t t)))))) (t t)))))))) (t t))))))) </code></pre> Original tested but unoptimized and also converted using tool:<p><pre><code> var K = a =&gt; b =&gt; a; var S = a =&gt; b =&gt; c =&gt; a(c)(b(c)); var Z = S(K(S(S(K(S(S(K)(K))(S(K)(K))))(S(K(S(K(S))(K)))(S(K(S(S(K)(K))))(K))))(K(S(S(K))))))(S(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))(S(K(S))(K))))(K(S(S(K(S(S(K)(K))(S(K)(K))))(S(K(S(K(S))(K)))(S(K(S(S(K)(K))))(K))))(K(S(K(S(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))(S(K(S(S(K)(K))))(K))))))(K)))))); </code></pre> <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Fixed-point_combinator" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Fixed-point_combinator</a>
评论 #42375020 未加载
评论 #42375023 未加载
barryjay5 个月前
It’s great to see Johannes experimenting with tree calculus, and making explicit the possibilities which are merely implicit in my book GitHub.com&#x2F;barry-jay-personal&#x2F;tree-calculus&#x2F;tree_book.pdf Now that (finally) there is a typed tree calculus I have started blogging (all at GitHub.com&#x2F;barry-jay-personal)
评论 #42403568 未加载
评论 #42378650 未加载
blahedo5 个月前
Just spent a bunch of time with this and had a couple insights that might help (particularly if you have <i>some</i> familiarity with the lambda calculus or formal semantics and are trying to get a foothold on this):<p>- I had to go down to the OCaml implementation to work out what the small-step semantics were saying, in part because I couldn&#x27;t see what the underlying tree structure was. In each of the four-element reductions in the definition, put parentheses around the first three to see what is applying to what. Also I think the right-hand sides are under-parenthesised. So:<p><pre><code> (t (t) a) b -&gt; a (1) (t (t a) b) c -&gt; (a c) (b c) (2) (t (t a b) c) t -&gt; a (3a) (t (t a b) c) (t u) -&gt; b u (3b) (t (t a b) c) (t u v) -&gt; (c u) v (3c) </code></pre> Relatedly, the table is missing some cases because (I think) the authors see them as &quot;obviously&quot; falling out from the associativity of the written syntax, but I think it&#x27;s helpful to add:<p><pre><code> t a -&gt; (t a) (0a) (t a) b -&gt; (t a b) (0b) </code></pre> <i>Now</i> you can look at an expression with the syntax <i>E E</i> and more cleanly apply these semantic reductions to them.<p>- So wtf is all this doing? In the same way that working out the lambda calculus is frequently about bundling a lambda to &quot;choose&quot; between two options, this tree calculus is built to &quot;choose&quot; between three options based on whether it&#x27;s presented with a node that is a leaf, a &quot;stem&quot; (one child), or a &quot;fork&quot; (two children). This is the core of rules 3a, 3b, 3c. If the &quot;function&quot; being applied is a fork whose left child is a fork, we think of the left-left grandchild as A, the left-right grandchild as B, and the right child as C; and if applied to a leaf, we use A, if applied to a stem we apply B to the stem&#x27;s sole child, and if applied to a fork we apply C to the fork&#x27;s two children. That three-way &quot;choosing&quot; is going to be how the system builds up the rest of the things you can do with it.
评论 #42375010 未加载
ljouhet5 个月前
In Python:<p><pre><code> Leaf = [] Stem = lambda x: [x] Fork = lambda a, b: [a, b] is_leaf = lambda x: len(x)==0 is_stem = lambda x: len(x)==1 is_fork = lambda x: len(x)==2 def apply(a, b): &quot;&quot;&quot; From https:&#x2F;&#x2F;treecalcul.us&#x2F;specification&#x2F; (OCaml) &quot;&quot;&quot; if is_leaf(a): return Stem(b) if is_stem(a): return Fork(a[0], b) x, y = a # a == Fork(x, y) if is_leaf(x): return y if is_stem(x): return apply(apply(x[0], b), apply(y, b)) u, v = x # x == Fork(u, v) if is_leaf(b): return u if is_stem(b): return apply(v, b[0]) s, t = b # b == Fork(s, t) return apply(apply(y, s), t) T = {} T[&quot;false&quot;] = Leaf T[&quot;true&quot;] = Stem(Leaf) T[&quot;not&quot;] = Fork (Fork (T[&quot;true&quot;], Fork (Leaf, T[&quot;false&quot;])), Leaf) def show(tree): name = [k for k in T if T[k]==tree][0] print(name or tree) show(apply(T[&quot;not&quot;], T[&quot;false&quot;])) # true show(apply(T[&quot;not&quot;], T[&quot;true&quot;])) # false</code></pre>
评论 #42424267 未加载
GistNoesis5 个月前
Here is a visualization I made of the tree calculus rules as a pattern matching on binary trees <a href="https:&#x2F;&#x2F;github.com&#x2F;unrealwill&#x2F;tree-calculus-visualizer">https:&#x2F;&#x2F;github.com&#x2F;unrealwill&#x2F;tree-calculus-visualizer</a>
maxbond5 个月前
Reminds me of Modal.<p><a href="https:&#x2F;&#x2F;wiki.xxiivv.com&#x2F;site&#x2F;modal" rel="nofollow">https:&#x2F;&#x2F;wiki.xxiivv.com&#x2F;site&#x2F;modal</a><p><a href="https:&#x2F;&#x2F;wryl.tech&#x2F;projects&#x2F;modal.html" rel="nofollow">https:&#x2F;&#x2F;wryl.tech&#x2F;projects&#x2F;modal.html</a>
Vampiero5 个月前
On paper, it&#x27;s really cool and I hope that more comes out of it. In practice, I&#x27;m not sure that taking 9k eval steps to turn a string lowercase is viable for anything.
评论 #42375140 未加载
评论 #42374059 未加载
ranma_425 个月前
The idea might be nice but the syntax is so easy to mess up for humans that in the spec itself the author gets the translation of `not true` wrong (maybe a copy-paste from `not false`?).<p>Should be &quot;t (t (t t) (t t t)) t (t t)&quot;.
评论 #42375122 未加载
chewxy5 个月前
Barry Jay&#x27;s got an upcoming paper at PEPM regarding typed tree calculus. Good read too.
评论 #42374748 未加载
js85 个月前
AFAIK there are many variations (I think infinite, even) of &quot;tree calculi&quot;. You can build one easily from combinatory logic by using only one universal combinator, which will be implied at the leafs of the tree.<p>John Tromp in his repo has some research pertaining to short universal lambda expressions (each can be expressed as combinators) of this type: <a href="https:&#x2F;&#x2F;github.com&#x2F;tromp&#x2F;AIT&#x2F;blob&#x2F;master&#x2F;Bases.lhs">https:&#x2F;&#x2F;github.com&#x2F;tromp&#x2F;AIT&#x2F;blob&#x2F;master&#x2F;Bases.lhs</a>
评论 #42376171 未加载
kevindamm5 个月前
This strikes me as a good idea in the same way that counting in unary is a good idea.<p>Theoretically profound but ultimately needing to be somewhat removed from its application to be of much practical use.
vincentpants5 个月前
So wait. How is this not a lisp? And consider that a compliment, we need more lisp in our lives.
评论 #42374553 未加载
gatane5 个月前
This is like a weird child between Lisp&#x2F;Forth and Prolog (?). I do think it is neat tho, got me thinking on how you could implement it and parse it.<p>Thanks for the inspiration!
golol5 个月前
Lambda calculus consists pretty much just of function compositions, which in principle have a tree structure. Is this just lambda calculus in a dress?
评论 #42375041 未加载
visarga5 个月前
This is a good counterexample to &quot;syntax is not sufficient for semantics&quot;. It is sufficient when there is no distinction between data and code. Code can reflect on itself as data. Like bootstrapped autocompilers, Godel&#x27;s Arithmetization or neural nets. In all cases syntax is both data and behavior, it is deep, self reflective and self generative.
评论 #42375233 未加载
评论 #42375204 未加载
galaxyLogic5 个月前
So a given function would be reprsented by an unlabeled tree, and its result calculated by applying rules which transform the source-tree into a binary tree?<p>Then how do I &quot;call&quot; such a tree with some specific arguments? Do I have to create a new tree that represents both the function, and the arguments it is called with?<p>How do I represent numbers, and strings, and arrays?
评论 #42374733 未加载
评论 #42374761 未加载
GistNoesis5 个月前
I think the main problem people encounter understanding this thing is just parsing the expression tree for the rules.<p>It isn&#x27;t stated but all trees in question are binary trees.<p>Even though the expression tree syntax is really easy E := t | E E<p>The mental gymnastic needed to visualize that the string<p>not = t ( t (t t) (t t t)) t correspond to the only tree drawn in <a href="https:&#x2F;&#x2F;treecalcul.us&#x2F;specification&#x2F;" rel="nofollow">https:&#x2F;&#x2F;treecalcul.us&#x2F;specification&#x2F;</a><p>is quite overwhelming.<p>The left-associative notation to remove unneeded parenthesis makes it even harder.<p>It could be explained so much better if the author made the 10 pictures corresponding to the transformation rules of the trees. Eventually highlighting the subtrees a, b, c, in the corresponding color before after.<p>Brains are used to pattern matching images but not abstractly defined syntax unless you have been trained in grammar theory.
wslh5 个月前
I&#x27;m genuinely curious while skimming Jay’s book, I couldn’t help but notice parallels with LISP-based approaches, which are also tree-structured. How does this differ from those?<p>Additionally, I have another question: where is this theory [potentially] applied, even if only in niche areas?<p>Finally, I think there is a glitch in [1] where define &quot;false = t, true = t, etc&quot; I think they meant false = f ? I was mesmerized by a tree representation of not though.<p>[1] <a href="https:&#x2F;&#x2F;treecalcul.us&#x2F;specification&#x2F;" rel="nofollow">https:&#x2F;&#x2F;treecalcul.us&#x2F;specification&#x2F;</a>
评论 #42376831 未加载
ryandv5 个月前
Immediately I&#x27;m reminded of the SKI calculus as an extremely minimal model for computation [0].<p>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.<p>[0] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;SKI_combinator_calculus" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;SKI_combinator_calculus</a><p>[1] <a href="https:&#x2F;&#x2F;treecalcul.us&#x2F;live&#x2F;?example=demo-turing-intensional" rel="nofollow">https:&#x2F;&#x2F;treecalcul.us&#x2F;live&#x2F;?example=demo-turing-intensional</a>
评论 #42374133 未加载
评论 #42374934 未加载
评论 #42374392 未加载
评论 #42374079 未加载
评论 #42374574 未加载
scotty795 个月前
Right, two questions, how do you do this infinite loops and how do you do side effects.<p>All it can do is take programs and return values.<p>I can see how this could be useful for configuration generation.<p>But for it to be a programming language you would have to make it produce &quot;execution plant&quot; to be executed on more classical virtual machine that can do system calls and decide what to do next depending on what it gets back.
LudwigNagasena5 个月前
So it’s based on a universal combinator like Iota?
评论 #42374227 未加载
评论 #42374943 未加载
mojomark5 个月前
Sorry, I don&#x27;t understand what I just saw.
p4bl05 个月前
On the semantics page the reductions presented in the definition are not the same thing as the OCaml code does. Or if it is actually equivalent, it should be largely commented because it really is not obvious.<p>But this criticism is valid for most of the website. Nothing is really clear.
rep_lodsb5 个月前
Reminds me of Wolfram Physics: it&#x27;s just &quot;nodes&quot; that exist in relation to each other - and are in all other ways identical -, with some rules for manipulating them leading to all possible computations?<p>It&#x27;s certainly not a practical way to write programs.
keepamovin5 个月前
I like this idea. It&#x27;s hard to think about ways that trees might combine or operate on other trees. This is fantastic to get into. Thank you for posting and the other commenters for sources.
yayr5 个月前
Can someone explain to me what is so special here? It seems to be just a simple binary abstract syntax tree, which with varying syntax can represented by almost any programming language
nextaccountic5 个月前
Is there any programming language whose implementation uses tree calculus underneath? (Akin to how most programming languages use some variation of lambda calculus for its AST)
nixosbestos5 个月前
Oof. I thought I had a grip on my ADHD but these non-seekable, side-by-side demos are giving me whiplash.<p>EDIT: oh no, oh god, they are text, so maybe Asciinema, so, we&#x27;re light-years ahead of a GIF&#x2F;mp4, but also, please don&#x27;t disable the seekbar, come on.<p>:&#x2F; Even worse, they don&#x27;t scroll. They don&#x27;t need to be animated at all. Come <i>on</i> frontend people, just stop. Please, just... stop.<p>EDIT2: I have zero idea what &quot;stream fusion&quot; is and the 4 inscrutable paragraphs of text don&#x27;t explain it either. But maybe I&#x27;m just a dumb and don&#x27;t know what that is.
评论 #42374187 未加载
stronglikedan5 个月前
I couldn&#x27;t imagine trying to type the lambda character that much.
marsknight5 个月前
I&#x27;m too dumb for this
评论 #42376544 未加载
cyberax5 个月前
Reminds me of Refal, which is somewhat surprisingly Turing-complete.
Iwan-Zotow5 个月前
Isn&#x27;t it 1 to 1 to iota language&#x2F;combinator ?
spencerchubb5 个月前
the ability to invert a function sounds crazy to me. I never imagined that was possible
e-dant5 个月前
Feels like clojure from afar
评论 #42373817 未加载
olydis5 个月前
Hi all, author of the website here (I&#x27;m <a href="https:&#x2F;&#x2F;johannes-bader.com&#x2F;" rel="nofollow">https:&#x2F;&#x2F;johannes-bader.com&#x2F;</a>). Wow, thanks for the reactions and many good suggestions! I thought I&#x27;d add a bit of context here.<p>As has correctly been pointed out, Tree Calculus was developed by Barry Jay! The &quot;Specification&quot; page links to his book. And a preview of his PEPM 2025 paper (hi chewxy!) can now be found here: <a href="https:&#x2F;&#x2F;github.com&#x2F;barry-jay-personal&#x2F;typed_tree_calculus&#x2F;blob&#x2F;main&#x2F;typed_program_analysis.pdf">https:&#x2F;&#x2F;github.com&#x2F;barry-jay-personal&#x2F;typed_tree_calculus&#x2F;bl...</a><p>Compared to how long Barry has been professionally researching this, I entered the picture yesterday and joined the effort to help. Potential mistakes on the website are mine, not Barry&#x27;s, but I do firmly believe in some of the &quot;ambitious&quot; wording there. Blog posts and more concrete demos or details to come!<p>Just for the curious, here is my angle in all this:<p>I happened to (hobbyist!) research tiny, yet practical, languages for over a decade (see e.g. <a href="https:&#x2F;&#x2F;lambada.pages.dev&#x2F;" rel="nofollow">https:&#x2F;&#x2F;lambada.pages.dev&#x2F;</a>). In that work I started noticing that the Iota combinator (<a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Iota_and_Jot" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Iota_and_Jot</a>) is not a combinator in the most traditional sense: It is usually defined as behaving like &quot;\x x S K&quot;, but like, how can we just refer to a lambda in the <i>definition</i> of a logic? One could write reduction rules such as &quot;Iota Iota x -&gt; x&quot;, but now Iota appears on the left hand side, in argument position! Doesn&#x27;t that allow reflecting on arguments? Horror! I just started realizing that, while SK is perfectly Turing complete and sane, forcing down the number of combinators from 2 to 1 magically forces some amount of intensionality! Curious, isn&#x27;t it?<p>And that&#x27;s when I came across Barry&#x27;s work and book! A calculus that embraces intensionality. So I reached out to see if I can help. How can I be most useful? Barry has been figuring out theory, professionally, before I could think. So I felt like helping spread the word, maybe to a less academic developer crowd, would be a more effective way to contribute. I spent my entire career building developer tools, so I have some ideas what could be useful and what might be necessary to convince various kinds of developers. That&#x27;s how the website came to be, and it is very much a work in progress. We sync regularly, for instance Barry had excellent ideas for demos and I suggested slightly tweaked reduction rules at some point (not more powerful in theory, just more convenient in practice), see &quot;triage calculus&quot; in typed_program_analysis.pdf
评论 #42383534 未加载
评论 #42378279 未加载
评论 #42407138 未加载
jcmontx5 个月前
this looks like OCaml&#x2F;F# to me