6 ms·
The minimal Joy: [A] a = A [A] b = [[A]] [A] [B] c = [A B] [A] d = [A] [A] [A] e = [A] [B] f = [B] [A]
by compressedgas 5y ago
The minimal Joy:
[A] a = A
[A] b = [[A]]
[A] [B] c = [A B]
[A] d = [A] [A]
[A] e =
[A] [B] f = [B] [A]
- tromp 5y agoThat'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))
- lupire 5y agoYou can do (approximately) the same in Joy, so I don't know what parent meant by "minimal". http://tunes.org/~iepos/joy.html#conssipk 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.
- tromp 5y agoI 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-proof-of-nonexistence-of-a-proper-universal-combinator https://math.stackexchange.com/questions/839926/is-there-a-p...
- lupire 5y agoHonestly 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).
- harperlee 5y agoWhat’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.
- tromp 5y agoThere 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).
- stouset 5y agoAIUI, 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.
- sfvisser 5y agoInteresting 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.5163 https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19....
- l- 5y agoY'=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