A concatenative programming library in 5 lines of Clojure(blog.fogus.me)
blog.fogus.me
A concatenative programming library in 5 lines of Clojure
http://blog.fogus.me/2013/01/06/pesto5-a-concatenative-programming-library-in-5-lines-of-clojure/
4 comments
This isn’t concatenative except in the trivial sense of “stack-based”. Concatenative languages are functional languages with compositional semantics, which often happen to be most efficiently implemented as stack machines. Concatenative languages are interesting because they’re a combinator calculus like SKI[1] but with simpler semantics and useful algebraic properties.
Only allowing two-argument functions doesn’t cut it, and you need some means of returning multiple values as well. You also need a means of abstraction (e.g., Clojure fns) and combinators for application, abstraction, and stack manipulation. A full implementation of an interpreter for a concatenative DSL would be rather longer than this—though still probably in the realm of 100 lines.
[1]: http://en.wikipedia.org/wiki/SKI_combinator_calculus
Only allowing two-argument functions doesn’t cut it, and you need some means of returning multiple values as well. You also need a means of abstraction (e.g., Clojure fns) and combinators for application, abstraction, and stack manipulation. A full implementation of an interpreter for a concatenative DSL would be rather longer than this—though still probably in the realm of 100 lines.
[1]: http://en.wikipedia.org/wiki/SKI_combinator_calculus
Fogus linked to my project, Factjor:
https://github.com/brandonbloom/factjor
Factjor supports quotations, currying, composition, and has most of the primary combinators: dip, keep, cleave, spread, application, etc. It's only about 100 lines.
https://github.com/brandonbloom/factjor
Factjor supports quotations, currying, composition, and has most of the primary combinators: dip, keep, cleave, spread, application, etc. It's only about 100 lines.
> Concatenative languages are interesting because they’re a combinator calculus like SKI but with simpler semantics and useful algebraic properties.
It's difficult to have simpler semantics than SK calculus. Perhaps a more appropriate modifier in this instance would be "more convenient".
It's difficult to have simpler semantics than SK calculus. Perhaps a more appropriate modifier in this instance would be "more convenient".
Yes, that’s fair. The example I had in mind was to do with GC: I’m not sure you can implement an SK interpreter without it.
I'm not sure that the presense of a stack is required for a concatenative language, but your point is well taken. Pesto5 is not enterprise ready.
Right, that’s what I said. Just because it’s efficient to implement one language that way doesn’t mean it’s efficient to do that for every language in the same family. :)
With non-variadic arithmetic functions:
With non-variadic arithmetic functions:
(defn add [x]
(cons (+ (first x) (second x)) (rest (rest x))))
(defn dup [x]
(cons (first x) x))
(defn zap [x]
(rest x))
(defn swap [x]
(cons (second x) (cons (first x) (rest (rest x)))))
(defn ap [x]
(apply (first x) (rest x)))
...A data stack is indeed not required -- see Om (experimental):
http://concatenative.org/wiki/view/Om
It uses prefix notation: instead of a data stack, each function takes the remainder of the program for rewriting.
http://concatenative.org/wiki/view/Om
It uses prefix notation: instead of a data stack, each function takes the remainder of the program for rewriting.
I whether or not there is a stack is similar to the complementary nature of foldL vs parallel fold (ie Clojure's core/reduce vs reducers). Left-to-right concatenative languages make use of a stack and are appropriate for side effects and stream processing. However, there are pure concatenative languages that operate in parallel via term rewriting, which has a computational model akin to that of a DNA computer.
Enchilada is a concatenative language which is not stack based but instead works through term rewriting.
You seem to have missed the point of this fun little exercise. Search for "in no way indicative" and "debatable" in the OP.
No no, I only said this for the benefit of others who might not be familiar with concatenative programming. The OP clearly knows what they’re doing.
I, for one, appreciated the clarification.
Amusingly, just like whoever wrote the Haskell example linked in the blog, the very first thing I did with free monads was also write a trivial stack-based language. All I supported was pushing numbers to the stack and addition. Not a very complicated language! Programs look something like:
With a bit of cleverness, it's probably possible to encode some of the stack semantics into the type system, making running a program with too few or too many elements left on the stack a type error. Also, with GADTs, I can probably add support for something like strings and have a mini string/int type system just for my little language, without much effort.
prog = do {1; 2; add; 3; 4; add; add}
incr = do {1; add}
prog = do {1; incr; incr; incr}
With a bit of cleverness, it's probably possible to encode some of the stack semantics into the type system, making running a program with too few or too many elements left on the stack a type error. Also, with GADTs, I can probably add support for something like strings and have a mini string/int type system just for my little language, without much effort.
> it's probably possible to encode some of the stack semantics into the type system, making running a program with too few or too many elements left on the stack a type error
Indeed, Factor does this. In addition to checking for stack (over/under)-flows it's what allows really powerful behavior like the ability to say "run both these words with the current stack" without having to explicitly state how much of the stack to duplicate.
Indeed, Factor does this. In addition to checking for stack (over/under)-flows it's what allows really powerful behavior like the ability to say "run both these words with the current stack" without having to explicitly state how much of the stack to duplicate.
I’m working on a statically typed concatenative language and would be happy to chat about typing in your stack language. My username at Gmail.
Stack based and concatenative programming languages are something I find really interesting. It's really easy to implement a simple one, so one of my go-to benchmarks for trying out a new language is to implement a little stack based language in it.
They're a lot of fun, and some simple ideas can lead to really interesting results. Since all code is just a sequence of tokens it becomes trivial to treat words, quotations, and entire programs as lists and manipulate them a la Lisp. Another nice thing is many such languages give you access to the parser. One I wrote recently is (almost) interpreted directly from text and let's you hook into the parsing process. It doesn't have comments, but it's trivial to add them:
Also interesting is how the stack changes the way you write code. What you end up with is program that's entirely made of something like pipes in ML-like languages or chaining constructs in JavaScript. They're very easy to compose together (and generally there's less overhead) so it encourages "factoring" out into lots of little pieces; something you can do in almost any language but doesn't feel as natural IMO.
They're a lot of fun, and some simple ideas can lead to really interesting results. Since all code is just a sequence of tokens it becomes trivial to treat words, quotations, and entire programs as lists and manipulate them a la Lisp. Another nice thing is many such languages give you access to the parser. One I wrote recently is (almost) interpreted directly from text and let's you hook into the parsing process. It doesn't have comments, but it's trivial to add them:
IMMEDIATE: /* BEGIN NEXT-TOKEN STRING */ EQ? UNTIL ;
Also interesting is how the stack changes the way you write code. What you end up with is program that's entirely made of something like pipes in ML-like languages or chaining constructs in JavaScript. They're very easy to compose together (and generally there's less overhead) so it encourages "factoring" out into lots of little pieces; something you can do in almost any language but doesn't feel as natural IMO.
http://code.google.com/p/consize/
It is extensively documented in German — I plan to add some documentation in English as well. But you might enjoy reading the source code anyhow ;-) After reading consize.clj, I recommend to continue with prelude-plain.txt.
BTW: Adding object-orientation (i.e. polymorphism via generic words & multiple inheritance much like Clojure does) is possible in about 30 LOC.
Dominikus