Concatenative Language

https://concatenative.org/wiki/view/Concatenative%20language

by optimalsolver • 4 years ago

91 55 4 years 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]

tromp4• 4 years ago

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

lupire5• 4 years ago

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.

harperlee• 4 years ago

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.

sfvisser• 4 years ago

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

hoseja• 4 years ago

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.

JohnDeHope• 4 years ago

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.

cmrdporcupine• 4 years ago

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.

dTal• 4 years ago

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!

agumonkey2• 4 years ago

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)

infogulch• 4 years ago

Logic languages

mamcx• 4 years ago

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

psd1• 4 years ago

I think you need a NOT NULL on hill.verb

mikewarot• 4 years ago

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.

toxik• 4 years ago

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.

lupire5• 4 years ago

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.

agumonkey2• 4 years ago

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.

potiuper2• 4 years ago

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

carapace3• 4 years ago

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.

Banana699• 4 years ago

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?

astrobe_• 4 years ago

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.

codr72• 4 years ago

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.

artemonster• 4 years ago

FORTH like I.

lupire5• 4 years ago

* Forth I like

jonsen• 4 years ago

I Forth like or

account-5• 4 years ago

Excuse my ignorance but could lisp be considered concatenative?

cyberbanjo• 4 years ago

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

macintux• 4 years ago

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

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

stonemetal12• 4 years ago

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.

t-32• 4 years ago

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

cwmma• 4 years ago

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

carapace3• 4 years ago

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.

protomyth2• 4 years ago

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.

tromp4• 4 years ago

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

spindle2• 4 years ago

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

protomyth2• 4 years ago

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?

johnisgood2• 4 years ago

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

a3w• 4 years ago

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

aidenn0• 4 years ago

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.

d0mine• 4 years ago

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

Existenceblinks• 4 years ago

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

nuggets321• 4 years ago

website is currently not responding.

Concatenative Language

Related Stories