Hacker News Reader

Comment by tromp | Hacker News Reader

That's 6 primitives (unquote,quote,cat,dup,drop,swap). For comparison, here's the minimal (non-concatenative) Combinatory Logic:

    S x y z = x z (y z)
    K x y   = x

The following by itself also suffices, but needs K in its definition:

    S' x y z = x z (y (K z))

View on HN

You can do (approximately) the same in Joy, so I don't know what parent meant by "minimal".

http://tunes.org/~iepos/joy.html#conssipk

This should be expected, because concatenative is a syntax style alternative to applicative syntax for functions, and has no trouble with lambda calculus semantics.

The main difference (why Joy uses (s',k) instead of (s,k)) is that Joy has quoting, but this just for convenience for large data, not essential.

I use minimal in the sense of the smallest number of primitive proper combinators [1]. Thanks for pointing out that Joy is similarly minimal.

Do you know of any concatenative language without quoting?

I find combinary languages simpler than concatenative ones, since the former uses only application as a composition mechanism, whereas the latter uses both concatenation and grouping with [].

[1] https://math.stackexchange.com/questions/839926/is-there-a-p...

Honestly I don't really understand the deeper meaning of quoting/grouping, so I might be quite wrong about its use.

How is concatenative grouping/quoting different from combinatory parentheses (or your binary equivalent).

In pure lambda calculus you need parentheses to disambiguate, because everything is a function and there are no natural non-functional values. In a concatenative language you need something to solve that problem, maybe quoting does that?

I'm over my head when I think about precisely how "small" these languages are, when trying to be explicit about how much is hidden in the virtual machine of evaluating a program (string of symbols).

Interesting related paper by Jeroen Fokker: The Systematic Construction of a One-Combinator Basis (1989)

https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19....

  Y'=SSK(S(K(SS(S(SSK))))K)=X(XX)X(XX)XX(X(XX)(XX(X(XX)X(XX)(X(XX)(X(XX)X(XX)XX))))XX)

X(XX)X(XX)XX [ 0, 1 ] == {(, X}] Binary Combinatory Logic Truth: 1101111

What’s the computational efficiency though? (Is there a general way to study the relative gains of adding primitives to a computation base*? I suspect just defining the complex one in terms of the simpler one would risk losing the measure of some expressivity options further than just defining the complex one).

* EDIT: Not merely expanding a base but e.g. comparing a 6-set with a /different/ 2-set, as above.

There are several possible ways to quantify expressiveness of a basis. For instance, you can count how many unique lambda normal forms you can generate with combinator expressions up to a certain size (modulo some terms that take too long to normalize). I once counted this for various choice of single-point combinator bases and up to size 16, and found that the above S' produced over 2 million normal forms whereas for instance the more well known \x.x S K produced only 244 normal forms. When you look only at how easy you can recover S and K, then the latter is much superior though (length 16/11 versus 3/3).

AIUI, in theory, they're all the same given a sufficiently advanced optimizing compiler. They're all equivalently-powerful way to model computation, so can all in principle be translated back and forth. In practice extracting optimal efficiency is difficult.

Reply on news.ycombinator.com