5 ms·

I think this is really cool. It'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.

I think this is really cool. It'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?

cat5e 2y ago
Straight up dude. Can we get an explanation for the rest of us?
- quantadev 2y ago
  [flagged]
  - hollerith 2y ago
    Although it might turn out to be a waste of everyone's time, it is quite sincere (not a hoax).
    - ryandv 2y ago
      It's a sign of the times here when people decry computer science constructs they can't understand as hoaxes.
      - quantadev 2y ago
        Well, "hoax" may indeed not be the best word, because it implies intent. I've known of another highly intelligent software developer that invented similar symbology, but was suffering from a mental disorder which made him believe his work was useful even though it's only uses were 'self-referential'. Highly intelligent people, including software developers, are not immune from such disorders.
        ryandv 2y ago
        The author has been publishing math and compsci papers since the 80s [0] with another on the way [1]. Maybe stick to TypeScript? [0] https://scholar.google.com/citations?user=eWreFm4AAAAJ&hl=en https://scholar.google.com/citations?user=eWreFm4AAAAJ&hl=en [1] https://popl25.sigplan.org/details/pepm-2025-papers/5/Typed-Program-Analysis-Without-Encodings https://popl25.sigplan.org/details/pepm-2025-papers/5/Typed-...
        quantadev 2y ago
        Ok, thanks. I'll avoid the Turning Tarpits. https://en.wikipedia.org/wiki/Turing_tarpit https://en.wikipedia.org/wiki/Turing_tarpit
        mrkeen 2y ago
        Is the Y combinator a hoax? λf. (λx. f (x x))(λx. f (x x))
        quantadev 2y ago
        Y Combinator is the simple syntax for representing the concept of passing a function to itself, so it's useful, for symbolic manipulation. However the "Tree Calculus", just from those 5 little rules, is supposedly able to do all kinds of magic. I'm not buying it. It's nothing but musings and examples of binary trees, and how you can convert various data structures to binary trees.
- hollerith 2y ago
  If it turns out to be broadly useful (to working programmers) I'm sure someone will write up a better explanation. At its current state of development, it might be more appropriate for the blog "Lambda the Ultimate" than HN.
  - toxik 2y ago
    Do you know what a Y combinator is?
    - hollerith 2y ago
      Yes. And I needed to know to follow some of the code ("constructions"?) in the OP.
  - lolinder 2y ago
    By the measuring stick of "anything that gratifies one's intellectual curiosity," I'd say this submission has been a roaring success for a lot of people. The nice thing about HN is that if something on the front page doesn't gratify your personal curiosity there are 29 more things that might.
    - AnimalMuppet 2y ago
      And if the other 29 don't scratch your itch either, then there's a "More" link...
lolinder 2y ago
It's a very funny way to structure the main landing page—it takes cues from trendy programming language and framework websites (single word headings that feel slightly buzzwordy, animated code samples, etc), but then the text body is in quite overwhelmingly dense and lengthy academic language, but then it doesn't actually provide enough details in the academic language to really understand what is going on. I spent a while parsing the paragraphs in the hope of understanding what this is, only to discover that in spite of its verbosity the text on the landing page is no more informative than PL landing pages usually are—it tells you a lot about what the author thinks is great about the language while not actually explaining how any of it works. I guess I need to go to the specification for that?
- __MatrixMan__ 2y ago
  > it tells you a lot about what the author thinks is great about the language I did not get so far as to understand that it was a language. I thought maybe it was some kind of higher order function to be implemented in a language of your closing. Like a map/reduce sort of thing.
  - lolinder 2y ago
    You know, it's entirely possible that it isn't a language and I just assumed that into existence. It's a very confusing landing page. Edit: no, it's definitely a language of some sort: > The syntax and semantics of Tree Calculus are minimal and self-contained, relying on no platform-specific concepts or abstractions. As a result, it is trivial to write interpreters on any platform or in any programming language (demo). ... > The ability to bootstrap the full power of Tree Calculus anywhere makes it an excellent configuration as code language in a heterogeneous system. Developers could write Tree Calculus programs that generate, say, JSON, and use an interpreter ...
    - olydis 2y ago
      Thanks for the feedback! Tree Calculus is a calculus/logic, see Specification page or the book by Barry Jay (linked on that page) for way way better and detailed verbose explanations. It only defines what I chose to call "t" on the website, Barry uses "Δ" in his book and papers. So without anything else, we'd have to talk about programs in terms of "(t t) t ..." or binary trees, which gets unwieldy quickly. The first natural step, for practical purposes, is to allow definitions "foo = ...", then some syntactic sugar for lists, functions, etc. Ooops and now we have a "language". If you open the "Playground" page there's a summary of what exactly is TC and what is syntactic sugar (and really nothing more!) on top of it. I like to think that the line is so blurry precisely because TC needs nothing but a bit of syntactic sugar to feel like a usable PL haha.
almostgotcaught 2y ago
people are always so impressed by this kind of stuff but i'll never get why. doesn't your intuition already lead you to recognize what's going on? or do you recognize and are still impressed? look if it walks like an expression tree, talks like an expression tree, and quacks like... something else... then it's basically an expression tree with extra sugar and spice. that doesn't mean the sugar and spice isn't fun, it means the basic idea is exactly what you think it is - expression trees (plus in this case enough semantics to define combinators).
- bertylicious 2y ago
  I'm very much impressed with this. I have never seen a programming language that allowed me to de/serialize functions. Let alone calculate the inverse of a function. If you're saying one or more languages with these features already exist then I'm very interested in names, links or references.
  - almostgotcaught 2y ago
    > have never seen a programming language that allowed me to de/serialize functions. You can pickle functions in python? You can trivially serialize any lisp function (I'm not a lisp fan). Plenty of programming languages with both macros and first class function objects (those that can be passed around and thus have data representations). > Let alone calculate the inverse of a function Note it says "try to compute the inverse" because actually computing inverses is equivalent to the halting problem. "If it seems to good to be true it probably is" could be adapted here to "If it seems too magical to be true, it's probably just cherry-picked".
    - ryandv 2y ago
      > You can pickle functions in python? You can trivially serialize any lisp function (I'm not a lisp fan). The point of the tree calculus appears to be that it doesn't require the intermediate step of "pickling" or, as the author calls it, "quoting" the program to produce a data structure or other representation of the program [0]: Previous accounts of self-interpretation had to work with programs that were not normal forms, that were unstable. Stability was imposed by first quoting the program to produce a data structure, by putting on some make-up. In tree calculus, the programs are already data structures, so that no pre-processing is required; both of the self-evaluators above act on the program and its input directly. In short, tree calculus supports honest reflection without make-up. It sounds similar to the notion of homoiconicity as in Lisp, but probably more precisely or even strongly stated. > Plenty of programming languages with both macros and first class function objects (those that can be passed around and thus have data representations). A language may have first class function objects, but its actual structure may be opaque and not open to reflection or manipulation (beyond of course just munging the source code as plaintext). You can maybe create a function literal, pass the function around and to higher-order functions, but you can't inspect or modify its internal structure, or decide program equality (based on either exact structure, or one program reducing to another according to the reduction rules of the calculus). Lastly the tree calculus would also appear to differ from the lambda calculus in that programs are stable and won't reduce infinitely, instead converging on some normal form of irreducible terms. [1] [0] https://github.com/barry-jay-personal/tree-calculus/blob/master/tree_book.pdf https://github.com/barry-jay-personal/tree-calculus/blob/mas... [1] https://sci-hub.se/https://dl.acm.org/doi/abs/10.1016/j.tcs.2019.02.016 https://sci-hub.se/https://dl.acm.org/doi/abs/10.1016/j.tcs....
theogravity 2y ago
Thanks for writing what I was afraid to post.
tkgally 2y ago
A defining sentence at the top of the page, something like “Tree Calculus is a [noun phrase] for [summary of purpose],” would be helpful. Wikipedia articles typically begin with such sentences: “Lambda calculus (also written as λ-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution.” “In mathematics, matrix calculus is a specialized notation for doing multivariable calculus, especially over spaces of matrices.” “The felicific calculus is an algorithm formulated by utilitarian philosopher Jeremy Bentham (1748–1832) for calculating the degree or amount of pleasure that a specific action is likely to induce.”
- rtxgucci 2y ago
  [dead]
justinpombrio 2y ago
Quick summary: It's a programming language whose programs (and whose values) are unlabeled trees. An unlabeled tree is a tree-shaped data structure whose nodes hold no data. The children of a node are ordered, though. The "Tree Calculus" defines a set of rules by which you can "evaluate" an unlabeled tree to get another unlabeled tree. If you apply these rules repeatedly, either you'll get into an infinite loop, or you'll get a tree that the rules say doesn't change anymore. The rules are designed so that the rules don't effect binary trees, so if you evaluate a binary tree you'll get the same tree back out and the computation is "done". These rules are written as a small-step semantics (a standard way to write down evaluation rules in PL) in the "specifications" page. They claim that: - The evaluation rules for trees are Turing Complete, meaning that you can express any computation, e.g. any JS program, using the Tree Calculus. More precisely, the claim is that there's a straightforward way to convert any (say) JS Program into a tree, and any tree into a JS value, and now you can use tree evaluation to run a JS program by doing (i) convert the JS program into a tree, (ii) evaluate the tree to get another tree, and finally (iii) convert the tree into a JS value, which is the correct output of the JS program. To prove this you wouldn't actually use JS as the language, you'd use something simpler that we already know is Turing complete like the lambda calculus, but it's the same idea. Though glancing at the page they might have actually done this for JS. - The evaluation is asymptotically optimal, meaning that for any programming language P (like JS), there's a conversion f(prog) from programs in P to Tree Calculus trees and constants a and b such that running_time(f(prog)) <= a+b*running_time(prog). That is, you can run programs in any language using the Tree Calculus with ~constant overhead. This is true for all the programming languages you love, e.g. you could write a JS program that takes a Java program, compiles it to bytecode, and run that bytecode, and unless you did this reasonably badly the running time won't be worse than a factor of 1,000,000. - A whole bunch of other stuff too. It's all plausible at first glance (i.e., I don't think they're making any of it up), but not obviously consequential. What's it good for: Some PL people might think it's cool. Conceivably useful to simplify some theory of computation proofs. If you find this sort of thing interesting, though, I'd recommend learning the lambda calculus instead. The lambda calculus is simpler, more well known, and more useful (it's a model of functions, instead of some made up rules about trees).
- junon 2y ago
ryandv 2y ago
It's a stripped down model of computation like the SKI calculus [0] or its cousin the lambda calculus, which are formal systems with precise rules for mechanically evaluating or reducing expressions. It differs from the SKI calculus in that it can reflect on its own program structure, especially in ways the SKI calculus cannot - deciding if two programs are equal, for instance [1]. Further, unlike the lambda calculus, reducing a program with the reduction rules given [2] eventually converges upon a stable "normal form" of the program, which is expressed in irreducible terms, instead of leading to possibly infinite chains of reduction [3]. This allows for reflection without needing to "quote" or serialize the program into a stable data structure or other representation to sidestep the possibility of infinite reduction. This is similar to the notion of homoiconicity as in Lisp. [0] https://en.wikipedia.org/wiki/SKI_combinator_calculus https://en.wikipedia.org/wiki/SKI_combinator_calculus [1] https://github.com/barry-jay-personal/tree-calculus/blob/master/tree_book.pdf https://github.com/barry-jay-personal/tree-calculus/blob/mas... [2] https://treecalcul.us/specification/ https://treecalcul.us/specification/ [3] https://sci-hub.se/https://dl.acm.org/doi/abs/10.1016/j.tcs.2019.02.016 https://sci-hub.se/https://dl.acm.org/doi/abs/10.1016/j.tcs....
- cjfd 2y ago
  "reducing a program with the reduction rules given eventually converges upon a stable "normal form" of the program". How is that possible if the reduction rules define a Turing complete language?
  - ryandv 2y ago
    It would appear that programs in even SKI calculus and other combinatory logics can reduce to base combinators in finitely many steps, but when those combinators are applied to arguments, then the possibility of non-termination arises [0]: Combinatory logic [9,12] is very close to λ-calculus, and widely considered to be equivalent to it [8], but there are important differences. In particular, by modifying the usual account of recursion, i.e. by modifying the usual account of fixpoint functions, it is possible to ensure that all programs are represented by stable combinators, i.e. combinators that are irreducible or in normal form. Only when applied to arguments does non-termination become possible. That is, we may define a program to be a combinator in normal form. As such it is both an executable, since applications of it will trigger evaluation, and also a syntax tree, i.e. a binary tree of applications, with leaves labelled by the primitive combinators, say S and K. [0] https://sci-hub.se/https://dl.acm.org/doi/abs/10.1016/j.tcs.2019.02.016 https://sci-hub.se/https://dl.acm.org/doi/abs/10.1016/j.tcs....
Skeime 2y ago
I will also try to give some explanation: The specification says that the syntax of expressions in this thing is `E ::= t | E E`. This is a bit confusing, because it might lead you to believe that all expressions just look like `t t t t t t t`. In reality, you are supposed to keep the implied bracketing, so expressions really look like `(t t) (t ((t t) (t t)))` (note that at the top level and in each parenthesis, there always exactly two subexpressions). Essentially, the space character becomes a binary operator (similar to how we often write multiplication with no symbol). The expressions are a bit heavy on parentheses, so we say that this binary operator is left associative. This means that an expression `a b c` should be interpreted as `(a b) c`, an expression `a b c d` should be interpreted as `((a b) c) d`, and so on. If you think about it, this means that you can always get rid of an opening parenthesis at the left edge of an expression, i.e. we can assume that an expression always start without one. With this out of the way, we can now understand where the trees come from: As there is only one terminal symbol, `t`, after removing unnecessary parentheses, every expression will always start with `t`, which is followed by a number of other expressions. To draw this as a tree, draw a node representing the initial `t`, and a sub-tree for each of the follow-up expressions (by applying the same procedure to them). In this view, the semantic rules at the top of the specification page now tell you how to "simplify" a tree whenever there is a node with three or more sub-trees, or alternatively, how to reduce an expression that is a `t` followed by three or more sub-expressions. (In the syntax view, you replace the `t` and the first three expressions following it by whats on the right of the arrow. In the tree view, you replace the node and its first three children by some other sub-tree, then you attach the remaining children to the root of the new sub-tree.)
- Exuma 2y ago
  Great extra detail - thanks

I think this is really cool. It'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?

cat5e 2y ago

Straight up dude. Can we get an explanation for the rest of us?

quantadev 2y ago
[flagged]
- hollerith 2y ago
  Although it might turn out to be a waste of everyone's time, it is quite sincere (not a hoax).
  - ryandv 2y ago
    It's a sign of the times here when people decry computer science constructs they can't understand as hoaxes.
    - quantadev 2y ago
      Well, "hoax" may indeed not be the best word, because it implies intent. I've known of another highly intelligent software developer that invented similar symbology, but was suffering from a mental disorder which made him believe his work was useful even though it's only uses were 'self-referential'. Highly intelligent people, including software developers, are not immune from such disorders.
      - ryandv 2y ago
        The author has been publishing math and compsci papers since the 80s [0] with another on the way [1]. Maybe stick to TypeScript? [0] https://scholar.google.com/citations?user=eWreFm4AAAAJ&hl=en https://scholar.google.com/citations?user=eWreFm4AAAAJ&hl=en [1] https://popl25.sigplan.org/details/pepm-2025-papers/5/Typed-Program-Analysis-Without-Encodings https://popl25.sigplan.org/details/pepm-2025-papers/5/Typed-...
        quantadev 2y ago
        Ok, thanks. I'll avoid the Turning Tarpits. https://en.wikipedia.org/wiki/Turing_tarpit https://en.wikipedia.org/wiki/Turing_tarpit
      - mrkeen 2y ago
        Is the Y combinator a hoax? λf. (λx. f (x x))(λx. f (x x))
        quantadev 2y ago
        Y Combinator is the simple syntax for representing the concept of passing a function to itself, so it's useful, for symbolic manipulation. However the "Tree Calculus", just from those 5 little rules, is supposedly able to do all kinds of magic. I'm not buying it. It's nothing but musings and examples of binary trees, and how you can convert various data structures to binary trees.
hollerith 2y ago
If it turns out to be broadly useful (to working programmers) I'm sure someone will write up a better explanation. At its current state of development, it might be more appropriate for the blog "Lambda the Ultimate" than HN.
- toxik 2y ago
  Do you know what a Y combinator is?
  - hollerith 2y ago
    Yes. And I needed to know to follow some of the code ("constructions"?) in the OP.
- lolinder 2y ago
  By the measuring stick of "anything that gratifies one's intellectual curiosity," I'd say this submission has been a roaring success for a lot of people. The nice thing about HN is that if something on the front page doesn't gratify your personal curiosity there are 29 more things that might.
  - AnimalMuppet 2y ago
    And if the other 29 don't scratch your itch either, then there's a "More" link...

lolinder 2y ago

It's a very funny way to structure the main landing page—it takes cues from trendy programming language and framework websites (single word headings that feel slightly buzzwordy, animated code samples, etc), but then the text body is in quite overwhelmingly dense and lengthy academic language, but then it doesn't actually provide enough details in the academic language to really understand what is going on. I spent a while parsing the paragraphs in the hope of understanding what this is, only to discover that in spite of its verbosity the text on the landing page is no more informative than PL landing pages usually are—it tells you a lot about what the author thinks is great about the language while not actually explaining how any of it works. I guess I need to go to the specification for that?

__MatrixMan__ 2y ago
> it tells you a lot about what the author thinks is great about the language I did not get so far as to understand that it was a language. I thought maybe it was some kind of higher order function to be implemented in a language of your closing. Like a map/reduce sort of thing.
- lolinder 2y ago
  You know, it's entirely possible that it isn't a language and I just assumed that into existence. It's a very confusing landing page. Edit: no, it's definitely a language of some sort: > The syntax and semantics of Tree Calculus are minimal and self-contained, relying on no platform-specific concepts or abstractions. As a result, it is trivial to write interpreters on any platform or in any programming language (demo). ... > The ability to bootstrap the full power of Tree Calculus anywhere makes it an excellent configuration as code language in a heterogeneous system. Developers could write Tree Calculus programs that generate, say, JSON, and use an interpreter ...
  - olydis 2y ago
    Thanks for the feedback! Tree Calculus is a calculus/logic, see Specification page or the book by Barry Jay (linked on that page) for way way better and detailed verbose explanations. It only defines what I chose to call "t" on the website, Barry uses "Δ" in his book and papers. So without anything else, we'd have to talk about programs in terms of "(t t) t ..." or binary trees, which gets unwieldy quickly. The first natural step, for practical purposes, is to allow definitions "foo = ...", then some syntactic sugar for lists, functions, etc. Ooops and now we have a "language". If you open the "Playground" page there's a summary of what exactly is TC and what is syntactic sugar (and really nothing more!) on top of it. I like to think that the line is so blurry precisely because TC needs nothing but a bit of syntactic sugar to feel like a usable PL haha.

almostgotcaught 2y ago

people are always so impressed by this kind of stuff but i'll never get why. doesn't your intuition already lead you to recognize what's going on? or do you recognize and are still impressed? look if it walks like an expression tree, talks like an expression tree, and quacks like... something else... then it's basically an expression tree with extra sugar and spice. that doesn't mean the sugar and spice isn't fun, it means the basic idea is exactly what you think it is - expression trees (plus in this case enough semantics to define combinators).

bertylicious 2y ago
I'm very much impressed with this. I have never seen a programming language that allowed me to de/serialize functions. Let alone calculate the inverse of a function. If you're saying one or more languages with these features already exist then I'm very interested in names, links or references.
- almostgotcaught 2y ago
  > have never seen a programming language that allowed me to de/serialize functions. You can pickle functions in python? You can trivially serialize any lisp function (I'm not a lisp fan). Plenty of programming languages with both macros and first class function objects (those that can be passed around and thus have data representations). > Let alone calculate the inverse of a function Note it says "try to compute the inverse" because actually computing inverses is equivalent to the halting problem. "If it seems to good to be true it probably is" could be adapted here to "If it seems too magical to be true, it's probably just cherry-picked".
  - ryandv 2y ago
    > You can pickle functions in python? You can trivially serialize any lisp function (I'm not a lisp fan). The point of the tree calculus appears to be that it doesn't require the intermediate step of "pickling" or, as the author calls it, "quoting" the program to produce a data structure or other representation of the program [0]: Previous accounts of self-interpretation had to work with programs that were not normal forms, that were unstable. Stability was imposed by first quoting the program to produce a data structure, by putting on some make-up. In tree calculus, the programs are already data structures, so that no pre-processing is required; both of the self-evaluators above act on the program and its input directly. In short, tree calculus supports honest reflection without make-up. It sounds similar to the notion of homoiconicity as in Lisp, but probably more precisely or even strongly stated. > Plenty of programming languages with both macros and first class function objects (those that can be passed around and thus have data representations). A language may have first class function objects, but its actual structure may be opaque and not open to reflection or manipulation (beyond of course just munging the source code as plaintext). You can maybe create a function literal, pass the function around and to higher-order functions, but you can't inspect or modify its internal structure, or decide program equality (based on either exact structure, or one program reducing to another according to the reduction rules of the calculus). Lastly the tree calculus would also appear to differ from the lambda calculus in that programs are stable and won't reduce infinitely, instead converging on some normal form of irreducible terms. [1] [0] https://github.com/barry-jay-personal/tree-calculus/blob/master/tree_book.pdf https://github.com/barry-jay-personal/tree-calculus/blob/mas... [1] https://sci-hub.se/https://dl.acm.org/doi/abs/10.1016/j.tcs.2019.02.016 https://sci-hub.se/https://dl.acm.org/doi/abs/10.1016/j.tcs....

theogravity 2y ago

Thanks for writing what I was afraid to post.

tkgally 2y ago

A defining sentence at the top of the page, something like “Tree Calculus is a [noun phrase] for [summary of purpose],” would be helpful. Wikipedia articles typically begin with such sentences: “Lambda calculus (also written as λ-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution.” “In mathematics, matrix calculus is a specialized notation for doing multivariable calculus, especially over spaces of matrices.” “The felicific calculus is an algorithm formulated by utilitarian philosopher Jeremy Bentham (1748–1832) for calculating the degree or amount of pleasure that a specific action is likely to induce.”

rtxgucci 2y ago
[dead]

justinpombrio 2y ago

Quick summary: It's a programming language whose programs (and whose values) are unlabeled trees. An unlabeled tree is a tree-shaped data structure whose nodes hold no data. The children of a node are ordered, though. The "Tree Calculus" defines a set of rules by which you can "evaluate" an unlabeled tree to get another unlabeled tree. If you apply these rules repeatedly, either you'll get into an infinite loop, or you'll get a tree that the rules say doesn't change anymore. The rules are designed so that the rules don't effect binary trees, so if you evaluate a binary tree you'll get the same tree back out and the computation is "done". These rules are written as a small-step semantics (a standard way to write down evaluation rules in PL) in the "specifications" page. They claim that: - The evaluation rules for trees are Turing Complete, meaning that you can express any computation, e.g. any JS program, using the Tree Calculus. More precisely, the claim is that there's a straightforward way to convert any (say) JS Program into a tree, and any tree into a JS value, and now you can use tree evaluation to run a JS program by doing (i) convert the JS program into a tree, (ii) evaluate the tree to get another tree, and finally (iii) convert the tree into a JS value, which is the correct output of the JS program. To prove this you wouldn't actually use JS as the language, you'd use something simpler that we already know is Turing complete like the lambda calculus, but it's the same idea. Though glancing at the page they might have actually done this for JS. - The evaluation is asymptotically optimal, meaning that for any programming language P (like JS), there's a conversion f(prog) from programs in P to Tree Calculus trees and constants a and b such that running_time(f(prog)) <= a+b*running_time(prog). That is, you can run programs in any language using the Tree Calculus with ~constant overhead. This is true for all the programming languages you love, e.g. you could write a JS program that takes a Java program, compiles it to bytecode, and run that bytecode, and unless you did this reasonably badly the running time won't be worse than a factor of 1,000,000. - A whole bunch of other stuff too. It's all plausible at first glance (i.e., I don't think they're making any of it up), but not obviously consequential. What's it good for: Some PL people might think it's cool. Conceivably useful to simplify some theory of computation proofs. If you find this sort of thing interesting, though, I'd recommend learning the lambda calculus instead. The lambda calculus is simpler, more well known, and more useful (it's a model of functions, instead of some made up rules about trees).

junon 2y ago

ryandv 2y ago

It's a stripped down model of computation like the SKI calculus [0] or its cousin the lambda calculus, which are formal systems with precise rules for mechanically evaluating or reducing expressions. It differs from the SKI calculus in that it can reflect on its own program structure, especially in ways the SKI calculus cannot - deciding if two programs are equal, for instance [1]. Further, unlike the lambda calculus, reducing a program with the reduction rules given [2] eventually converges upon a stable "normal form" of the program, which is expressed in irreducible terms, instead of leading to possibly infinite chains of reduction [3]. This allows for reflection without needing to "quote" or serialize the program into a stable data structure or other representation to sidestep the possibility of infinite reduction. This is similar to the notion of homoiconicity as in Lisp. [0] https://en.wikipedia.org/wiki/SKI_combinator_calculus https://en.wikipedia.org/wiki/SKI_combinator_calculus [1] https://github.com/barry-jay-personal/tree-calculus/blob/master/tree_book.pdf https://github.com/barry-jay-personal/tree-calculus/blob/mas... [2] https://treecalcul.us/specification/ https://treecalcul.us/specification/ [3] https://sci-hub.se/https://dl.acm.org/doi/abs/10.1016/j.tcs.2019.02.016 https://sci-hub.se/https://dl.acm.org/doi/abs/10.1016/j.tcs....

cjfd 2y ago
"reducing a program with the reduction rules given eventually converges upon a stable "normal form" of the program". How is that possible if the reduction rules define a Turing complete language?
- ryandv 2y ago
  It would appear that programs in even SKI calculus and other combinatory logics can reduce to base combinators in finitely many steps, but when those combinators are applied to arguments, then the possibility of non-termination arises [0]: Combinatory logic [9,12] is very close to λ-calculus, and widely considered to be equivalent to it [8], but there are important differences. In particular, by modifying the usual account of recursion, i.e. by modifying the usual account of fixpoint functions, it is possible to ensure that all programs are represented by stable combinators, i.e. combinators that are irreducible or in normal form. Only when applied to arguments does non-termination become possible. That is, we may define a program to be a combinator in normal form. As such it is both an executable, since applications of it will trigger evaluation, and also a syntax tree, i.e. a binary tree of applications, with leaves labelled by the primitive combinators, say S and K. [0] https://sci-hub.se/https://dl.acm.org/doi/abs/10.1016/j.tcs.2019.02.016 https://sci-hub.se/https://dl.acm.org/doi/abs/10.1016/j.tcs....

Skeime 2y ago

I will also try to give some explanation: The specification says that the syntax of expressions in this thing is `E ::= t | E E`. This is a bit confusing, because it might lead you to believe that all expressions just look like `t t t t t t t`. In reality, you are supposed to keep the implied bracketing, so expressions really look like `(t t) (t ((t t) (t t)))` (note that at the top level and in each parenthesis, there always exactly two subexpressions). Essentially, the space character becomes a binary operator (similar to how we often write multiplication with no symbol). The expressions are a bit heavy on parentheses, so we say that this binary operator is left associative. This means that an expression `a b c` should be interpreted as `(a b) c`, an expression `a b c d` should be interpreted as `((a b) c) d`, and so on. If you think about it, this means that you can always get rid of an opening parenthesis at the left edge of an expression, i.e. we can assume that an expression always start without one. With this out of the way, we can now understand where the trees come from: As there is only one terminal symbol, `t`, after removing unnecessary parentheses, every expression will always start with `t`, which is followed by a number of other expressions. To draw this as a tree, draw a node representing the initial `t`, and a sub-tree for each of the follow-up expressions (by applying the same procedure to them). In this view, the semantic rules at the top of the specification page now tell you how to "simplify" a tree whenever there is a node with three or more sub-trees, or alternatively, how to reduce an expression that is a `t` followed by three or more sub-expressions. (In the syntax view, you replace the `t` and the first three expressions following it by whats on the right of the arrow. In the tree view, you replace the node and its first three children by some other sub-tree, then you attach the remaining children to the root of the new sub-tree.)

Exuma 2y ago
Great extra detail - thanks