7 ms·

Why concatenative programming matters (2012)

adastra22 4y ago
2012
moomin 4y ago
I can understand why people get excited about the concatenative paradigm, but I’ll concede that my personal take is “Sounds like some bits of LISP married to the point free obsession of some Haskell programmers”
- iostream25 4y ago
  actually.... FORTH... https://en.wikipedia.org/wiki/Forth_(programming_language) https://en.wikipedia.org/wiki/Forth_(programming_language)
  - astrobe_ 4y ago
    Except perhaps that Forth doesn't "obsess" over theory, it is rooted in pragmatism: making a Forth interpreter is easy.
- voxl 4y ago
  Most if not all concatenative languages are linear. Lisps can also be linear, and languages like Forth can also be non-linear, but there is a cultural divide there.
iostream25 4y ago
Great stuff, this is a different approach than the FORTH books provide, and I suspect it may open other doors.
amelius 4y ago
Sounds like something you'd rather not work in directly, but could be useful as an intermediate representation for a compiler (?)
- pxeger1 4y ago
  Some compilers do indeed use a stack-based IR (which is a concatenative system). Also mentioned in the blog post are JVM and CPython bytecode. More common, though, is Static Single Assignment.
  - amelius 4y ago
    I was thinking more in terms of supercombinators, lambda lifting, etc.
layer8 4y ago
The ergonomic drawback of concatenative languages is that when you see `a b c d e`, you don’t know whether it means `e(d(c(b(a))))`, or `e(b(a), d(c))`, or `e(a, b, c, d)`, or `b(a), e(c, d)`, etc. The answer depends on the types of a, b, c, d, and e. The syntax `a b c d e` is a linearization of the call tree, whose node structure can be recovered from the types of the symbols (assuming the language is statically typed). As a human reader, it means you have to know the types to understand the structure of the expression. This imposes a cognitive load that other types of languages don’t. It also removes redundancy that can be helpful to prevent programming errors. While the type checker verifies that the types match a structuring of the expression, that derived structure is not directly visible to the human programmer, and the programmer cannot easily see whether it actually matches the programmer’s understanding.
- js8 4y ago
  But this is true for ML syntax too, isn't it? And ML-likes are widely considered to be readable. There are also features of concatenative languages, like quoting in Joy or Factor, which can help alleviate the problem.
  - zetalyrae 4y ago
    I think currying by default is an antifeature and ML would be better off with f(x,y,z) call syntax. It interacts poorly with type inference: forget a parameter, or swap a parameter, and get an incomprehensible type error message about some function type that has little to do with the actual fault. This is prevented by parenthesizing expressions and using tuples as the sole argument.
  - yakubin 4y ago
    > But this is true for ML syntax too, isn't it? And ML-likes are widely considered to be readable. I don't see how that's true for ML. Could you give an example showing the ambiguity? Edit: I think I can see how the presence of infix syntax may cause that. As in: when you see "a b c" it will read differently based on whether "b" is a function that's declared to be infix by default. Yeah, I think infix notation is a mistake. The more I think about syntax, the more appeal I see in S-expressions.
avgcorrection 4y ago
Author ended up doing a lot of work on Kitten https://github.com/evincarofautumn/kitten https://github.com/evincarofautumn/kitten
zetalyrae 4y ago
If you're interested, this article by Henry Baker draws a connection between permutation stack machines and linear types/GC-free memory management: "Linear Logic and Permutation Stacks--The Forth Shall Be First" https://www.plover.com/~mjd/misc/hbaker-archive/ForthStack.html https://www.plover.com/~mjd/misc/hbaker-archive/ForthStack.h...
vitiral 4y ago
I'm writing a concatenative language with a C-similar syntax. As a first language (to write) I've found it very pleasant. Following the forth models, I start with an extremely lean (~2000 lines of C) VM and assembly and that builds a macro-based language in a few thousand lines -- all in a single build+execute step. I'm currently implementing function syntax, and the type system will be next (also C like with a bit of interface-like "Role" objects and type extension) GitHub.com/civboot/fngi
carapace 4y ago
I didn't see it linked from the article, Jon Purdy has a great talk about this too: "Concatenative Programming: From Ivory to Metal" (2017) https://www.youtube.com/watch?v=_IgqJr8jG8M https://www.youtube.com/watch?v=_IgqJr8jG8M There's also "A Conversation with Manfred von Thun" http://archive.vector.org.uk/art10000350 http://archive.vector.org.uk/art10000350 which is worth reading (IMO) if you're interested in concatenative languages. He's the creator of Joy. I've been working with Joy over the last few years now and I really think there's something there. It seems to combine the best features of both Forth and Lisp.
- adastra22 4y ago
  It’s still possible to work with Joy today?
  - carapace 4y ago
    The C source on the old site compiled and ran when I tried it: https://www.kevinalbrecht.com/code/joy-mirror/joy.html https://www.kevinalbrecht.com/code/joy-mirror/joy.html (mirror) My own project is here: https://joypy.osdn.io/ https://joypy.osdn.io/ It includes interpreters in Python, Prolog, and Nim (and a start on Rust) and some explorations of compilers and type inference/checking written in Prolog.
iostream25 4y ago
https://www.concatenative.org/ https://www.concatenative.org/ might be interesting for some folks
BaseballPhysics 4y ago
I completely disagree with this analysis: > The reason “Why Functional Programming Matters” was necessary in the first place was that functional programming had been mischaracterised as a paradigm of negatives—no mutation, no side-effects—so everybody knew what you couldn’t do, but few people grasped what you could. The issue with functional programming, and the reason for that referenced piece, aren't because people don't know what you can do with functional programming languages. It's because people don't know why they should care. Things like "immutability, referential transparency, mathematical purity" are pretty, and it's neat to see the machinery applied in practice, but in the end people pick their tools because they help them get their jobs done more effectively, and it's exceedingly difficult to explain to a working programmer why "referential transparency" is gonna meaningfully improve their lives. This piece, then, starts from this basic misunderstanding and proceeds to make precisely the same mistake. Yes, what the author demonstrates in this piece is pretty neat. But why should I care? What would motivate me to move off of the imperative languages I'm already familiar with?
- avgcorrection 4y ago
  You say that people know what they can do with FP. Then you say that it is “pretty” and it is “neat” to see the machinery in action. I.e. it’s just superficial stuff. Seems your precise disagreement with the author is: the author thinks that FP is useful and you don’t. Because people who argue for FP don’t do it because it’s a neat and pretty exercise.
  - BaseballPhysics 4y ago
    > Seems your precise disagreement with the author is: the author thinks that FP is useful and you don’t. I'm afraid you've misunderstood my point. I had no intent to make a value judgement about FP whatsoever, one way or the other. My criticism is about the messaging. IMO this piece misses the mark because it starts off with a faulty premise, and it's the same mistake I've seen made by every other article about FP. My comment was inspired by the fact that I got to the end of the piece thinking "that's pretty cool, but I still don't understand why I should care about this in practice", and then I looked back at the thesis and realized the author never intended to explain that because they misunderstood the motivation for writing "Why Functional Programming Matters" in the first place.

2012

I can understand why people get excited about the concatenative paradigm, but I’ll concede that my personal take is “Sounds like some bits of LISP married to the point free obsession of some Haskell programmers”

iostream25 4y ago
actually.... FORTH... https://en.wikipedia.org/wiki/Forth_(programming_language) https://en.wikipedia.org/wiki/Forth_(programming_language)
- astrobe_ 4y ago
  Except perhaps that Forth doesn't "obsess" over theory, it is rooted in pragmatism: making a Forth interpreter is easy.
voxl 4y ago
Most if not all concatenative languages are linear. Lisps can also be linear, and languages like Forth can also be non-linear, but there is a cultural divide there.

iostream25 4y ago

Great stuff, this is a different approach than the FORTH books provide, and I suspect it may open other doors.

amelius 4y ago

Sounds like something you'd rather not work in directly, but could be useful as an intermediate representation for a compiler (?)

pxeger1 4y ago
Some compilers do indeed use a stack-based IR (which is a concatenative system). Also mentioned in the blog post are JVM and CPython bytecode. More common, though, is Static Single Assignment.
- amelius 4y ago
  I was thinking more in terms of supercombinators, lambda lifting, etc.

layer8 4y ago

The ergonomic drawback of concatenative languages is that when you see `a b c d e`, you don’t know whether it means `e(d(c(b(a))))`, or `e(b(a), d(c))`, or `e(a, b, c, d)`, or `b(a), e(c, d)`, etc. The answer depends on the types of a, b, c, d, and e. The syntax `a b c d e` is a linearization of the call tree, whose node structure can be recovered from the types of the symbols (assuming the language is statically typed). As a human reader, it means you have to know the types to understand the structure of the expression. This imposes a cognitive load that other types of languages don’t. It also removes redundancy that can be helpful to prevent programming errors. While the type checker verifies that the types match a structuring of the expression, that derived structure is not directly visible to the human programmer, and the programmer cannot easily see whether it actually matches the programmer’s understanding.

js8 4y ago
But this is true for ML syntax too, isn't it? And ML-likes are widely considered to be readable. There are also features of concatenative languages, like quoting in Joy or Factor, which can help alleviate the problem.
- zetalyrae 4y ago
  I think currying by default is an antifeature and ML would be better off with f(x,y,z) call syntax. It interacts poorly with type inference: forget a parameter, or swap a parameter, and get an incomprehensible type error message about some function type that has little to do with the actual fault. This is prevented by parenthesizing expressions and using tuples as the sole argument.
- yakubin 4y ago
  > But this is true for ML syntax too, isn't it? And ML-likes are widely considered to be readable. I don't see how that's true for ML. Could you give an example showing the ambiguity? Edit: I think I can see how the presence of infix syntax may cause that. As in: when you see "a b c" it will read differently based on whether "b" is a function that's declared to be infix by default. Yeah, I think infix notation is a mistake. The more I think about syntax, the more appeal I see in S-expressions.

avgcorrection 4y ago

Author ended up doing a lot of work on Kitten https://github.com/evincarofautumn/kitten https://github.com/evincarofautumn/kitten

zetalyrae 4y ago

If you're interested, this article by Henry Baker draws a connection between permutation stack machines and linear types/GC-free memory management: "Linear Logic and Permutation Stacks--The Forth Shall Be First" https://www.plover.com/~mjd/misc/hbaker-archive/ForthStack.html https://www.plover.com/~mjd/misc/hbaker-archive/ForthStack.h...

vitiral 4y ago

I'm writing a concatenative language with a C-similar syntax. As a first language (to write) I've found it very pleasant. Following the forth models, I start with an extremely lean (~2000 lines of C) VM and assembly and that builds a macro-based language in a few thousand lines -- all in a single build+execute step. I'm currently implementing function syntax, and the type system will be next (also C like with a bit of interface-like "Role" objects and type extension) GitHub.com/civboot/fngi

carapace 4y ago

I didn't see it linked from the article, Jon Purdy has a great talk about this too: "Concatenative Programming: From Ivory to Metal" (2017) https://www.youtube.com/watch?v=_IgqJr8jG8M https://www.youtube.com/watch?v=_IgqJr8jG8M There's also "A Conversation with Manfred von Thun" http://archive.vector.org.uk/art10000350 http://archive.vector.org.uk/art10000350 which is worth reading (IMO) if you're interested in concatenative languages. He's the creator of Joy. I've been working with Joy over the last few years now and I really think there's something there. It seems to combine the best features of both Forth and Lisp.

adastra22 4y ago
It’s still possible to work with Joy today?
- carapace 4y ago
  The C source on the old site compiled and ran when I tried it: https://www.kevinalbrecht.com/code/joy-mirror/joy.html https://www.kevinalbrecht.com/code/joy-mirror/joy.html (mirror) My own project is here: https://joypy.osdn.io/ https://joypy.osdn.io/ It includes interpreters in Python, Prolog, and Nim (and a start on Rust) and some explorations of compilers and type inference/checking written in Prolog.

iostream25 4y ago

https://www.concatenative.org/ https://www.concatenative.org/ might be interesting for some folks

BaseballPhysics 4y ago

I completely disagree with this analysis: > The reason “Why Functional Programming Matters” was necessary in the first place was that functional programming had been mischaracterised as a paradigm of negatives—no mutation, no side-effects—so everybody knew what you couldn’t do, but few people grasped what you could. The issue with functional programming, and the reason for that referenced piece, aren't because people don't know what you can do with functional programming languages. It's because people don't know why they should care. Things like "immutability, referential transparency, mathematical purity" are pretty, and it's neat to see the machinery applied in practice, but in the end people pick their tools because they help them get their jobs done more effectively, and it's exceedingly difficult to explain to a working programmer why "referential transparency" is gonna meaningfully improve their lives. This piece, then, starts from this basic misunderstanding and proceeds to make precisely the same mistake. Yes, what the author demonstrates in this piece is pretty neat. But why should I care? What would motivate me to move off of the imperative languages I'm already familiar with?

avgcorrection 4y ago
You say that people know what they can do with FP. Then you say that it is “pretty” and it is “neat” to see the machinery in action. I.e. it’s just superficial stuff. Seems your precise disagreement with the author is: the author thinks that FP is useful and you don’t. Because people who argue for FP don’t do it because it’s a neat and pretty exercise.
- BaseballPhysics 4y ago
  > Seems your precise disagreement with the author is: the author thinks that FP is useful and you don’t. I'm afraid you've misunderstood my point. I had no intent to make a value judgement about FP whatsoever, one way or the other. My criticism is about the messaging. IMO this piece misses the mark because it starts off with a faulty premise, and it's the same mistake I've seen made by every other article about FP. My comment was inspired by the fact that I got to the end of the piece thinking "that's pretty cool, but I still don't understand why I should care about this in practice", and then I looked back at the thesis and realized the author never intended to explain that because they misunderstood the motivation for writing "Why Functional Programming Matters" in the first place.