Concatenative Language | Hacker News Reader

Concatenative Language

concatenative.org

91 pointsoptimalsolver55 comments

Allow me to plug my own little entry in this space: a dialect of Joy written in Python, Prolog, and Nim (there's a Rust version in progress.) The project is messy at the moment (I am folding all the implementations into one repo from separate repos right now) but FWIW it's here: https://joypy.osdn.io/

Some points:

- Working with Joy has convinced me that syntax is a MacGuffin. You have to have some syntax to "move the story along" but it's not important in and of itself. (The Maltese Falcon.) All this work on languages and parsing is fun and useful, but now it seems to me like a bit of a sideshow.

- It's relatively easy to manipulate Joy expressions in a kind of mathematical way. This is the "missing link" of Functional Programming: Do math to derive programs like Backus said.

- Related to the above, Joy is sooooooooo simple. It is simpler and more elegant that Forth or even Lisp.

- The Prolog interpreter is also a type inferencer! It can interpret over abstract stacks.

IMO, it's one of those languages like Prolog or APL that you should learn even if you never use it, just to expand your mind.

Factor (https://github.com/factor/factor) is a pretty good language!

Runs the linked wiki. Farkup for non-markdown rendered content sound like f*ckup, though. And: why another markup language?

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]

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

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

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.

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

It's like a competition for which alternative programming paradigm is a hill most worth dying on: functional, concatenative, or object oriented. There seem like a few runner-ups: contract based, quantum, APL (not sure what paradigm to call it?), I'd like to think of some others. It's kind of a fun exercise.

The majority of programmers seem to prefer procedural.

APL & descendants are array/vector (or matrix) languages.

Anyways, the majority of programmers like general purpose languages that are popular with other programmers, because that's how you get employed and make money. And what has happened in the last 20 years is that techniques from functional & vector languages have made their way into mainstream languages. Either in the syntax or in their libraries.

That's a good thing after the previous decade+ of "object orientation will solve all our problems" dogma.

Concatenative approaches remain relatively under-explored though.

They aren't mutually exclusive. If you use numpy, you're using array-oriented, procedural, and object oriented all at once; maybe functional too, depending on your programming style. They should be thought of less as all-consuming "paradigms" and more as useful tools, like regex. Sometimes a tool is so powerful you can do everything with it; that doesn't mean it's a good idea!

Personally I think the paradigm is not the right battle. OO is a child of modular programming, with other ingredients but to me the real pain point is aiming at low coupling subsystems to be able to iterate at low cost and navigate unknown problems or adapt to customer/market changes.

There's also the middle layer trick (ala middle ground DSLs).

But the goal is the same, ability to converge quickly on a proper solution. Something I rarely see talked about (but my radar has a short scope)

Logic languages

You miss relational! (That is the hill I'm)

I think you need a NOT NULL on hill.verb

Then there's the declarative languages like Excel.

The wildest one I've seen was one that allowed both Imperative and Declarative programming in a semi-sane, yet mixed manner, it was called Metamine. I have a clone of the source, but I want to get stoical working well before I dig into that one.

PostScript struck me as a really nice concatenative language. It has some really nice extras. It's probably in the nature of the languages and their users, but they seem like a class of languages where a specialized IDE would really help.

I agree; it's also nice for writing little obfuscated signatures, such as

    %!PS                           % -John Tromp http://tromp.github.io/
    /t{dup 1 sub gsave dup 0 gt{[.4 .2 -.2 .4 .4 .2]concat t currentgray
    .8 mul .2 add setgray -1 1 scale t -1 2 translate t 1 -1 scale t[0 1
    1 0 0 2]concat t pop}{0 moveto 1 0 lineto 0 2 lineto closepath clip
    fill}ifelse grestore}def 10 10 translate 600 600 scale 5 t showpage

for producing a pinwheel tiling [1].

[1] https://tromp.github.io/img/pinwheel.pdf

(As you probably know), Factor comes with a really nice specialised IDE (written in Factor)

Actually, I didn't. Thanks for telling me. I don't remember it from the time I looked into it. Is Factor a going concern?

I don't think anybody's writing anything impressive in it any more, but yes it's a going concern in the sense that fine people are keeping it from bitrotting. :-)

Very interesting, though I have to wonder if this wouldn’t become incredibly hard to read. You sort of always put the horse before the cart. Especially the if is incredibly difficult to parse, as the condition is already on the stack, AND the two branches. This is quite the reverse of what imperative languages do, which mimics natural language: if x then y else z.

Stack/RPN languages are nice because they are easy to evaluate left to right, because you collect the arguments before you call the function. The stack is reduced as soon as possible, so max execution stack size is equal to the essential complexity of the calculus, for eager-evaluation languages.

"Traditional" Verb-Object order is tricky because you have to save the whole stack of functions before you can start reducing anything. But it's nice if you have partial/lazy evaluation and might discard argument/function calls without evaluating them.

For human UI, it's trivial to view/edit a program displayed in reverse, and add some redundant parentheses, for an applicative syntax, if you like.

To me stack language helped my brain forget about intermediate couplings, where in imperative language you have to imagine and manage data structures with operation around. When all you have is a stack, it's one variable less to worry about, you focus your energy on primitive ops.

Verb-Object order is not traditional as English is SVO, and Latin by "tradition" puts it at the end; nor does the whole stack of functions have to be saved before reduction can start see the sum or product operators or "verbs".

English instructions (programs) are Verb-Object with no Subject.

English commands are still SVO, but the subject may be omitted when it is able to be inferred. Some verbs do not allow inference, i.e. fetch or get. "Get water" may mean "[you] get [me or us] water", or it could mean you get yourself water. The subject is also not able to be parsed as a subject by putting it [the subject] as the first word of the object as "[you] get 'you' water" would mean the command to get water for yourself instead of "you get [me or us] water". Additionally, the uniform function call syntax does not apply to English: "Get(Water,[context])" is not the same as "Water.Get([context])", which is even more ambiguous that could mean "Get water" - see above - or that the water absorbed something like "Water get [it/salt/fire]". Also, to clarify Latin by "tradition" puts the verb at the end of the sentence.

You get used to it.

Like Forth, the "killer app" of this RPN syntax is the ability to factor and refactor your code, along with the simple stack-based execution model this allows the code to pretty closely reflect the essential mental model of the problem you're trying to solve. There is a very precise mathematical model for this in Category Theory but I'm not a good enough mathematician to attempt to elucidate it. If you're "doing it right" your code is evolving towards something like the Kolmogorov complexity of the domain/problem. Chuck Moore pointed out that Forth programs can often be smaller than the equivalent program written in ASM.

Anyway, the result is that you have a lot of small definitions, but each one captures a single coherent thought about your program, so it's easy to read. Plus you get used to the RPN and stack themselves, which makes it easier.

>If you're "doing it right" your code is evolving towards something like the Kolmogorov complexity of the domain/problem.

Any pointers to where this is elaborated on more precisely?

Specifically, I'm skeptical about the universality of the claim, Forth allows you to approximate the essential complexity of _any_ problem ? I'm not an enemy of Forth but every language must surely make some things awkward right?

> Any pointers to where this is elaborated on more precisely?

No, not off the top of my head. There is "Thinking Forth" by Leo Brodie (it's a whole book but worth the read. You can get official free PDFs here: http://thinking-forth.sourceforge.net/ )

It's a natural consequence from the ease of refactoring. Boilerplate and repetitious stuff gets refactored, leaving just the actual gnarly bits to take up most of the LoC.

> every language must surely make some things awkward right?

I think there's some theorem to that effect, no? (I want to say Rice's Theorem but that's not it.)

Forth is typically implemented in such a way as to give easy access to the underlying hardware, so in theory (and often in practice too) if there's some faculty you're missing from some other language or execution model you can implement it in Forth. People have made, e.g. object models and logic engines in Forth.

Forth works quite well for problems that fit its stack-based model, but that's not every problem. For instance, having to manage and permute data on the stack is often more awkward than doing the same things in languages that use ordinary variables. And working with only a single stack at a time, it's not clear how such languages might express parallelism, which is otherwise a very natural expectation for a functional language. Even things like complex data types, pattern matching etc. get needlessly awkward.

It's quite possible to add variables to Forth, which means you can pick the best tool.

Keeping computations on the stack then feels similar to the push to keep computations out of the IO monad in Haskell.

In concatenative languages, every nontrivial program is a DSL. The difficulty is that other people have to learn the base language and your DSL to read or modify your programs, on top of the stack-based nature of most concatenative languages hiding the dataflow between functions.

In my opinion, some concatenative go one or two steps too. Forth is more pragmatic and less academic, and let you do things the (almost) normal way:

    : min 2dup < if drop else nip then ;

If you want to write programs that solve your daily problems you use normal Forth. If you want to write a PhD or play, you use the fancy stuff.

It's a kind of puzzle, much like the shift register memories of old, by keeping track of the order of your data you get rid of the requirement for addressing.

So yes, from my experience, it will take more effort to process mentally; simply because you're doing more work.

I read the title, thought it was about speaking languages and was confused because it's the non-concatanative one's that are interesting.

https://en.wikipedia.org/wiki/Nonconcatenative_morphology

The title made me ponder a programming language with grammar different from the default english-inspired one, with it's immutable tokens and other ease-of-parsing limitations.

If Om is concatenative, than so are lisp macros; they take the entire macro form as input and return a new form, which is then subject to macroexpansion.

Hmm, am I correct that shell commands is kinda concatenative? So are languages that have "pipe", if they only permit to only use pipe?

Shell has concatenative aspects: commands can be stacked while processing single data (command line) e.g.:

    $ timeout 1h notify <event> send-telegram <message>

here's we send <message> if <event> occurs within an hour (3 commands: `timeout`, `notify`, `send-telegram`).

Excuse my ignorance but could lisp be considered concatenative?

I don't think so but Factor is a concatenation language with macros and extensible syntax.

Interesting you ask: there are a fair number of similarities between Forth and Lisp.

http://wiki.c2.com/?ForthVsLisp

No, Lisp is applicative.

The link splits languages in to applicative vs concatenative. This is straight up Church-Turing. Where Applicative is Church's a program is function application, and Concatenative is Turing's a program is a list of instructions concatenated on an infinite tape.

Not traditionally, but if viewed as a style, like functional programming, most every language can be used concatenatively.

website is currently not responding.

FORTH like I.

* Forth I like

I Forth like or

me factor love-in-between? [ t ] [ f ] if

Reply on news.ycombinator.com