Hacker News Reader

Comment by almostgotcaught | Hacker News Reader

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).

View on HN

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.

> 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".

> 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/mas...

[1] https://sci-hub.se/https://dl.acm.org/doi/abs/10.1016/j.tcs....

He sounds confused if he thinks that quotation involves turning programs into source code and then later recompiling them.

What he implemented IS quotation, despite his objections.

More precisely, the distinction would seem to be that programs in the tree calculus can analyze themselves with reference only to the reduction rules of the calculus, not needing to reach for some meta-language or theory outside the calculus that works on source code or some AST representation of the program [0]:

    Reflective programs are programs that can act on themselves to query their own struc-
    ture. The querying is important: that the identity function can be applied to itself does
    not make it reflective. A simple example is the size function defined in Chapter 5.
    When applied to itself, the result is (the tree of) the number 508 [...] Self-evaluation
    in a calculus provides good evidence for the ability to perform program analysis and
    optimisation within the calculus itself. Traditionally, self-interpreters were allowed to
    act on the syntax tree of a program, i.e. its quotation. [...] When quotation lies
    outside of the formal calculus then interpretation is separated from computation proper,
    so that some sort of staging is required.

A demo of a size function is given here [1], implemented directly in the tree calculus:

    size = \x (y $ \self \x compose succ $ triage id self (\x \y compose (self x) (self y)) x) x 0

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

[1] https://treecalcul.us/live/?example=demo-program-optimizatio...

Modern APL dialects have an inverse operator (https://aplwiki.com/wiki/Inverse). For example, in Dyalog APL (https://tryapl.com/):

        ⍝ Convert Fahrenheit to Celsius
        f_to_c ← (÷∘1.8)∘(-∘32)

        f_to_c 68
    20

        (f_to_c ⍣ ¯1) 20
    68

Now I'm an APL noob, I don't know how deeply this is implemented. I suspect it's very adhoc.

More interesting are logic languages such as Prolog. If you stick to the core logical features, you get the inverse of a function for free:

    ?- append([1,2,3], [4,5,6], X).
    X = [1, 2, 3, 4, 5, 6].

    ?- append(X, [4,5,6], [1,2,3,4,5,6]).
    X = [1, 2, 3].

    ?- append(X, Y, [1,2,3,4]).
    X = [], Y = [1, 2, 3, 4] ;
    X = [1], Y = [2, 3, 4] ;
    X = [1, 2], Y = [3, 4] ;
    X = [1, 2, 3], Y = [4] ;
    X = [1, 2, 3, 4], Y = [].

If I’m not mistaken this seems like something that would be possible in Bend/HVM

Reply on news.ycombinator.com