Concatenative Programming: An Overlooked Paradigm in Functional Programmng [pdf]

One of the most powerful traits of concatenative programming languages is that implicit parameter passing through the stack makes it possible to factor any code fragment into a new word that can act as a textual replacement. Anywhere you repeat a sequence of operations, you can factor it out. Most languages that use explicitly passed parameters make this more difficult as you have to start worrying about scoping and the "shipping and handling" of passing in arguments and unpacking results into a local scope.

I've linked this many times before, but I'm reminded of "Thinking Forth"[1], an excellent discussion of application architecture. It specifically deals with the Forth programming language, but carries lessons that are applicable to almost any language. I think the reason it works so well is because you can easily demonstrate factoring with a very short piece of Forth. In a language like C or Java you would need comparatively more involved examples to demonstrate the same principles.

[1] http://thinking-forth.sourceforge.net/

I love Factor, but this paper was frustrating to read. They use variables in their rewrite rules even though the whole point of the paper was that you don't need variables. So we never get to see a quotation function written in point-free style. The definitions are never used to actually prove or conjecture anything. Definition 3.4 is particularly content-free. Section 4 contained a 'cool' analogy with nothing to do with this programming style (4.1), 'research in progress' with no prototype (4.2), 'belief' (4.3), reference to 'an as yet unpublished paper' (4.3), and related work that should have been given its own section (4.4).

Perhaps it's not satisfied to be a position paper and the authors find themselves trying to show off novel research. I wish they'd resisted the temptation.

My suggestion is that concatenative programming languages are nearly direct representations of Combinatory Logic in the same way that Lisp (in its purest sense) is a direct representation of the Lambda Calculus:

http://github.com/raganwald/homoiconic/blob/master/2008-11-1...

In the early 2000s I wrote 'Basil'. It started as a macro language on steroids soon turned into a concatenative), functional web language that I used to build a number of large commercial sites. It turned out to be amazingly expressive while surprisingly efficient (or, at least, efficient enough).

It was a cross between lisp and C (and a touch of REXX). Everything was a string, strings were manipulated and stuck back together and everything returned a value (or the empty string {}) even a 'for' and an 'if'.

A very simple example is this piece of code (that I hastily dug up) that would make a stripy table.

  <!--begin stripey table-->
  
  <table>
  for(x in args)
  {

    <tr>
    for(y in x)
    {
      if(stripey)
      {
        stripey=t
        <td bgcolor="$dddddd"> y </td>
      }
      else
      {
        stripey=f
        <td bgcolor="$ffffff"> y </td>
      }
    }
    </tr>
  }
  </table>
  
  <!--end stripey table-->

Which on first view probably looks unremarkable until you see the invisible concats in all the white space and that the curly brackets all denote strings, even after the fors and ifs.

for instance:

  x = for(y in {1 2 3 4 5 6 7 8 9 10}){y}
  x

would return:

  12345678910

Just thinking about it has made me dig out the old code and take a look at it again. It had super-simple built in MySQL integration, an MVC-alike system of actions, objects & 'envelopes'. It automatically cleaned all CGI in and CGI out. It even had it's own NoSQL style database!

String concatenation was ideal for web programming (and a lot of other Unix tasks).

I'd love to return to it as it had a number of innovative features that I've yet to see in any other language (as well as a number I've seen appear since).

Interesting. Reminds me of the Cat programming language, which has term rewriting as well: http://www.cat-language.com/

One powerful concatenative language is Factor: http://factorcode.org/.

The implementation rocks, although the creator is now also sucked by the Google Vortex.

The APLs (APL, J, K, and Q) have a very strong concatenative element to them, as well.

Please ignore this, it's the key to my big idea that will change the world.