5 ms·
Why Concatenative Programming Matters (2012)
- tomxor 8y ago> A concatenative programming language is a point-free programming language in which all expressions denote functions and the juxtaposition of expressions denotes function composition. The combination of a compositional semantics with a syntax that mirrors such a semantics makes concatenative languages highly amenable to algebraic manipulation. This is the reason i hate so many (not all) wikipedia articles - the introduction is an exercise of code golf in human language. This is devoid of the key quality most readers want from an encyclopedia (understanding from an ignorant viewpoint), intros should not be a puzzle for the reader which attempts to fit comprehensive technical description into a single useless sentence.
- bunderbunder 8y agoLemme try in something closer to plain English: In most programming languages, the way you compose functions is by creating some other function that takes whatever arguments are necessary, applies the first function to some subset of them, collects its result, and then applies the second function to some other subset of the arguments, plus the result of the first function. IOW, while the syntax can be quite clean: let h(x) = f(g(x)) is doing quite a lot in the background. Moreso if some of the top-level arguments are to be passed to f and not g: let h(x, y) = f(g(x), y) In a concatenative language, all you have to do to compose functions is place them one after the other. So those two compositions both become something more like let h = g f One big difference here, and the main part of how most concatenative languages achieve this behavior, is that arguments are never stated or passed explicitly. Instead, inputs and outputs are typically retrieved from and placed onto some sort of stack. (edit: Just realized never really said why they're called "concatenative". It's because, at least in a Forth-style concatenative language where the compiler isn't doing any fancy footwork, you can compose functions by literally just concatenating them. So that `let h = g f` is basically saying, "To execute H, first execute G and then immediately execute F.")
- pointfree 8y agoMost languages that aim to be minimal bake in a minimal syntax, but without implicit parameter passing, composability is not going to be extensible.
- bunderbunder 8y agoIn a forth-like language, you can think of all functions as implicitly being unary: They take a stack, and return a stack. I've never used any other kind of concatenative language, so I'm less able to speak to them, but I'm guessing some similar situation applies for those as well.
- jeffdavis 8y agoHow about: "Concatenative programming style emphasizes function composition over function application. Complex operations are composed from many simpler operations, and the actual program input or state does not need to be referred to explicitly. Often, these composed operations resemble a data flow or pipeline, where the implicit input is passed along to each operation in sequence." (Disclaimer: not an expert on this style, just offering my own description that is hopefully correct and easier to understand.)
- bunderbunder 8y agoFunctional programming also emphasizes function composition. Especially anything that takes its intellectual heritage from John Backus. (viz, not lisp.) His seminal paper on the subject emphasized that, in well-designed functional languages, functions take only a single argument, because that's necessary to support a good composition-oriented programming style. I think the root of the distinction is more about how you achieve that composition: Does it smell more like Alonzo Church or Alan Turing?
- NoodleIncident 8y agoThe actual wikipedia page has a bunch of links that the OP doesn't include. To me, this is the opposite of code golf; rather than trying to concisely express the concept in the language's "builtins", it instead delegates the underlying concepts to their own "functions", and only describes the relationship between these concepts. https://en.wikipedia.org/wiki/Concatenative_programming_language https://en.wikipedia.org/wiki/Concatenative_programming_lang... If you know what the linked terms mean, you can move on quickly. If you don't, then explaining the higher-level concept in a way that skips these building blocks would be a waste of time; it's a better use of everyone's time for readers to at least skim the linked articles, first.
- binrec 8y agoWikipedia tends to be technical about math/CS subjects. In other fields, you can use it as a textbook for a 101 course - I once heard of an astronomy professor who did this, and this is what I recommend people do with linguistics. (Except syntax, which, as the most CS-adjacent subfield, gets the most technical treatment.) The page for Joy, Manfred von Thun's concatenative language, is a little better: > Joy is unusual ... in its ... lack of formal parameters. So, where in a standard ALGOL- or C-type language, you'd define a function that squares a number like this: def square(x): return x * x And in Haskell... OK, I don't know Haskell, but if I click through tryhaskell.org a bit, I see this: let square x = x * x in square 2 But in Joy, the way to write a function that squares a number doesn't involve explicit references to parameters at all: dup * Or, if you want to name your function: DEFINE square == dup *. Every function takes a stack and returns a stack. `dup` takes a stack [A B C...] and returns [A A B C...], for any values of A, B, and C. `` takes a stack [A:int B:int C...] and returns [AB C...]. Now, Joy in particular was written as a research language about recursive combinators. So a mostly-idiomatic* factorial function in Joy looks like this: DEFINE fac == [0 =] [1 +] [dup 1 -] [*] linrec. And then you call that with `5 fac` or something. The neat thing about this is that you don't need to define functions and reference them from inside themselves in order to get recursion, and you can write code that's a little more legible than using the Y combinator for everything. You could also write something like this: DEFINE fac-explicit-recursion == [0 =] [pop 1] [dup 1 - fac-explicit-recursion *] ifte. But you don't have to. `linrec` is a function that expects four quoted functions as the top elements on the stack. It executes the first function; if that 'returns' true, it executes the second one and stops, and if not, it executes the third function, recurses, and then executes the fourth. A while ago, I started working on a Joy interpreter in the browser. I haven't gotten around to finishing it yet, but it's at least working well enough that you can (hopefully) step through the https://defseg.io/joyjs/ https://defseg.io/joyjs/ For a flashier example (which won't work there right now, because I haven't implemented... `binrec`... yet), here's quicksort: [size 1 <=] [] [uncons [>] split] [[swap] dip cons concat] binrec `binrec` is another recursive combinator that expects four quoted functions. It handles the first two functions there the same way as `linrec` - executes the first (here, "does this list have one or fewer elements?"), and if true, executes the second (here, do nothing). But if the condition is false, it executes the third function to produce two values, recurses on both, and then uses the fourth function to combine them. So you get your pivot, split your list, recurse on both lists, and then stitch the two result lists and the pivot back together in sorted order. * 'Mostly' because you'd actually write `[null] [succ] [dup pred] [*] linrec`, but the two functions are identical. (`null` is overloaded to also test for zero elements in an aggregate, but if you pass it an aggregate it'll throw a type error anyway.) Similarly for quicksort: `[small] [] [uncons [>] split] [enconcat] binrec`.
- tombert 8y agoAbout a year ago, I decided that I'm going to learn Postscript for no other reason than to say that I know Postscript. Coming from a functional background, the point-free nature of it wasn't too confusing, and I actually grew to really enjoy it. I never got too far into that quest largely because I didn't have much of a practical need to be a Postscript expert, but it has since made me want to learn Forth, which I have been pushing off for months now.
- azhenley 8y agoI too recently got the itch to learn Forth. So I went forth and implemented a very simple interpreter for a small Forth dialect: https://github.com/AZHenley/goforth https://github.com/AZHenley/goforth It was quite fun but I still can't say that I know much about actually using Forth :)
- bunderbunder 8y agoI've fallen into that trap on both forth and lisp. It's fun as it is to implement interpreters for both, and it does give a sense of their simplicity. But, when you implement X in Y, you're not really learning X, you're learning how to write an interpreter (or compiler) in Y. Fortunately, the next step, which will teach you the language, is even more fun: Bootstrap your interpreter.
- JadeNB 8y ago> So I went and implemented a very simple interpreter for a small Forth dialect: You can't just write that. Chuck Moore, I assert with no evidence whatsoever, would require that you write "so I went forth and implemented …."
- azhenley 8y agoMy apologies, I have corrected the mistake!
- JadeNB 8y ago> About a year ago, I decided that I'm going to learn Postscript for no other reason than to say that I know Postscript. In case you're interested in having another reason, Bill Casselman does marvellous things with Postscript; e.g., http://www.math.ubc.ca/~cass/graphics/manual http://www.math.ubc.ca/~cass/graphics/manual .
- azhenley 8y agoDiscussion from 7 years ago: https://news.ycombinator.com/item?id=3582261 https://news.ycombinator.com/item?id=3582261 Hopefully the state of concatenative programming has changed a little since then?
- codr7 8y agoThe truth is somewhere between Forth and Lisp if you ask me, I find dogmatic Forth too primitive and Lisp too clever. The language I'm currently working on [0], aims to find the sweet spot starting from Lisp in Go. [0] https://github.com/codr7/g-fu https://github.com/codr7/g-fu
- crimsonalucard 8y agoIn functional programming... Replace immuteable variables with no declared variables. None. Like the immuteability rule in functional programming, if you follow this rule in any style of programming you will achieve concatenative programming.
- binrec 8y agoIt's technically possible to write in a concatenative style in a non-concatenative language, but in most cases, it's nowhere near idiomatic. How would you define a function that squares a number in a concatenative style in Javascript? Here's the best I can come up with: function compose(...funcs) { return stack => funcs.reduce((acc, cur) => cur(acc), stack) } function dup(stack) { stack.push(...[,,].fill(stack.pop())) return stack; } function mul(stack) { stack.push(stack.pop() * stack.pop()) return stack; } const square = () => compose(dup, mul) console.log(square()([4])) Then again, this could be a trick question someday - if the pipeline proposal goes through, it'll be possible to write idiomatic concatenative Javascript. (If you want to play with the pipeline operator, see here: https://defseg.io/etc/pipeline.html https://defseg.io/etc/pipeline.html) You'd still need to define all your functions as accepting a stack parameter, but you wouldn't need a compose function, so you could do something like this: function dup(stack) { stack.push(...[,,].fill(stack.pop())) return stack; } function mul(stack) { stack.push(stack.pop() * stack.pop()) return stack; } const square = stack => stack |> dup |> mul console.log([4] |> square) console.log([2] |> square |> square) Now to write an ECMA proposal for recursive combinators... /s
- crimsonalucard 8y agoThis is actually completely incorrect. Concatenative still retains immutability for parameters. It is a subset of functional programming. You are using a stack which is not immutable. A lot of javascript programmers think they are doing functional programming but they don't get the essence of it. Yes you know map, yes you know reduce. But you don't get it. functional programming is in essence a mathematical function rather than a procedural function. If you can fit your entire program into a single expression or a single function without computational steps or procedures you have achieved functional programming. Immutability is a side effect of converting everything into a single mathematical expression. Concatenative programming and functional programming are the same thing as imperative programming BUT with more restrictions so of course you can do concatenative programming in javascript AND you can be idiomatic. You are overcomplicating the concept. Literally: function square(x){ return x*x } is still concatenative. all concatenative programming is, is using the compose operator to compose your functions into a single function. for the given: function a(x){ return x*2 } function b(x){ return x*x } if your goal is to compute (2x)^2 procedural is this: var y = 1; y = a(y); y = b(y); //literally a list of procedures mutating a value. Order matters. console.log(y); functional (without concatenative): const x = 1; const y = a(x); const z = b(y); console.log(z); Above, the functions are applied on defined immutable variables. Order doesn't matter as long as you keep all definitions the same. While order happens sort of as a consequence to this, the concept for functional programming is to get rid of procedures. concatenative (still a valid functional program): const c = a |> b console.log(c(1)); In the above, a function application is only used here as the last step. The IO step where functional AND concatenative programming breaks down, but literally for concatenative programming your entire programming should be all made up of function definitions and composed functions and no declared variables and no applied functions. Just apply one function in the last step for IO and your program is concatenative. Javascript has been giving bootcampers completely wrong ideas about functional programming and what it is. Learn a real functional programming lang to actually get it. Haskell is a good one. Also your examples literally defeat the purpose of functional and concatenative programming. It makes the code worse. I would literally not think concatenative programming or functional programming is better if I saw that code for the first time. I would avoid functional programming like the plague if it caused your code to blow up into a mess like that. I'm not here to stretch my brain just to square a number.
- crimsonalucard 8y agoAnother way to put it is a program with zero state or temporary state.
- olodus 8y agoOh awesome. I found concaternative languages when I was trying to learn Forth last year. Forth was almost scary with how little syntax there is. Not even Lisp really felt like that. Types felt a great thing to get a bit more stability into it all. Really love how concat langs feel like a mid point of performance - lisp - static types. Are still very new to them of course but will continue to try to learn about them. I found Kitten then too. Didn't realized until the end of the article that this was it's creator. Really interesting post and glad to hear it might come more. Magnet sounds really interesting. Will certainly check it out.
- olodus 8y agoAww... Totally missed it was from 2012...