[HN Gopher] Concatenative Language
___________________________________________________________________
Concatenative Language
Author : optimalsolver
Score : 84 points
Date : 2022-04-13 10:43 UTC (12 hours ago)
(HTM) web link (concatenative.org)
(TXT) w3m dump (concatenative.org)
| hoseja wrote:
| 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.
| compressedgas wrote:
| 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 wrote:
| 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))
| lupire wrote:
| 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.
| tromp wrote:
| 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...
| harperlee wrote:
| 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.
| tromp wrote:
| 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).
| stouset wrote:
| 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.
| sfvisser wrote:
| 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..
| ..
| aidenn0 wrote:
| 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 wrote:
| 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`).
| account-5 wrote:
| Excuse my ignorance but could lisp be considered concatenative?
| stonemetal12 wrote:
| 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.
| cyberbanjo wrote:
| I don't think so but Factor is a concatenation language with
| macros and extensible syntax.
| t-3 wrote:
| Not traditionally, but if viewed as a style, like functional
| programming, most every language can be used concatenatively.
| macintux wrote:
| Interesting you ask: there are a fair number of similarities
| between Forth and Lisp.
|
| http://wiki.c2.com/?ForthVsLisp
| JohnDeHope wrote:
| 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 wrote:
| 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.
| infogulch wrote:
| Logic languages
| mikewarot wrote:
| 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.
| agumonkey wrote:
| 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)
| mamcx wrote:
| You miss relational! (That is the hill I'm)
| dTal wrote:
| 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!
| artemonster wrote:
| FORTH like I.
| lupire wrote:
| * Forth I like
| jonsen wrote:
| I Forth like or
| cwmma wrote:
| 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
| carapace wrote:
| 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.
| protomyth wrote:
| 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.
| spindle wrote:
| (As you probably know), Factor comes with a really nice
| specialised IDE (written in Factor)
| protomyth wrote:
| 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?
| tromp wrote:
| 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
| toxik wrote:
| 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.
| carapace wrote:
| 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 wrote:
| >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?
| carapace wrote:
| > 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.
| t-3 wrote:
| 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.
| zozbot234 wrote:
| 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.
| codr7 wrote:
| 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.
| lupire wrote:
| 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.
| potiuper wrote:
| 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".
| agumonkey wrote:
| 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.
| astrobe_ wrote:
| 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.
| codr7 wrote:
| 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.
| johnisgood wrote:
| Factor (https://github.com/factor/factor) is a pretty good
| language!
| a3w wrote:
| Runs the linked wiki. Farkup for non-markdown rendered content
| sound like f*ckup, though. And: why another markup language?
___________________________________________________________________
(page generated 2022-04-13 23:01 UTC)