Front Page All Articles Recent Changes Random Article

Contents

Concatenative language

  • ACL
  • Ait
  • Aocla
  • Breeze
  • Cat
  • Cognate
  • colorForth
  • CoSy
  • Deque
  • Elymas
  • Enchilada
  • ETAC
  • F
  • Factor
  • Forth
  • Freelang
  • Gershwin
  • Joy
  • Kitten
  • lang5
  • Lviv
  • min
  • mjoy
  • Mlatu
  • Ode
  • Om
  • Onyx
  • Plorth
  • Popr
  • Porth
  • PostScript
  • Quackery
  • r3
  • Raven
  • Retro
  • Staapl
  • Stabel
  • Trith
  • Worst
  • xs
  • XY
  • 5th
  • 8th

Other languages

  • APL
  • C++
  • Erlang
  • FP trivia
  • Haskell
  • Io
  • Java
  • JavaScript
  • Lisp
  • ML
  • Oberon
  • RPL
  • Self
  • Slate
  • Smalltalk

Computer Science

  • Type systems
  • Language paradigms
  • Compilers
  • Interpreters
  • Garbage collection

Meta

  • Search
  • Farkup wiki format
  • People
  • Etiquette
  • Sandbox

Concatenative language/Concatenation is composition

A fundamental property of stack languages is that the concatenation of two programs X and Y -- X Y -- is the program that applies Y to the result of X, that is, the composition of X and Y. This means that certain common quotation patterns can be written very concisely.

For example, in Factor we can filter a sequence by a predicate using the filter combinator:

( scratchpad ) { 1 2 3 4 5 6 7 8 } [ even? ] filter .
{ 2 4 6 8 }

If we want to remove elements matching the predicate instead, we can compose the predicate with the not word:

( scratchpad ) { 1 2 3 4 5 6 7 8 } [ even? not ] filter .
{ 1 3 5 7 }

Partial application works out very nicely too: write a quotation which pushes some of the parameters before calling a word:

( scratchpad ) { 1 2 3 4 5 6 7 8 } [ 4 > ] filter .
{ 5 6 7 8 }

Compare these three quotations,

[ even? ]
[ even? not ]
[ 4 > ]

This is shorter than the equivalent in an applicative language, because we have to name the input argument, that is only used once. In Common Lisp:

(function evenp)
(lambda (x) (not (evenp x)))
(lambda (x) (> x 4))

In Haskell:

(even)
(not . even)
(4 >)

Since concatenative languages do not have named parameters (let's ignore Factor's locals vocabulary for now), talking about free variables does not make sense. The nearest equivalent in a concatenative language is constructing new quotations from existing quotations.

In Factor, quotations look like a sequence of objects; for example, [ 2 2 + ] has three elements, the integer 2, the integer 2 again, and the word +; the latter is itself an object which can be introspected and executed. This means that we can use sequence operations to construct quotations.

Suppose we have the quotation [ + ]. When executed, it takes two numbers from the stack, adds them, and leaves the result on the stack. If we prefix the quotation with the integer 5, we get a new quotation, [ 5 + ], which adds 5 to the top of the stack. This is similar to currying in applicative languages, so Factor calls this operation curry.

Another fundamental operation on quotations is composition: suppose we take the quotation [ 2 + ] and the quotation [ 0 > ]; their composition is [2 + 0 > ]. Of course, this is just the concatenation of the two quotations.

These two fundamental operations -- curry and compose -- have very simple and intuitive semantics. Note that quotations are printable objects, whereas in applicative languages, closures are typically opaque.

Examples of curry:

( scratchpad ) 5 [ + ] curry .
[ 5 + ]

Compare with lisps applicative version; note the closure does not print readably:

* (let ((x 5)) (lambda (y) (+ x y)))
#<FUNCTION (LAMBDA (Y)) {11682335}>

or Haskell:

(5+)
Functions cannot be printed in Haskell

Examples of compose:

( scratchpad ) [ 3 = ] [ not ] compose .
[ 3 = not ]

Applicative version:

* (let ((f (lambda (x) (= x 3)))) (lambda (y) (not (funcall f y))))
#<FUNCTION (LAMBDA (Y)) {11680B3D}>
(not . (3 ==))
Again, functions cannot be printed

As you can see, function composition and partial application feels a lot more natural in stack languages, because of the duality between composition and concatenation.

This revision created on Wed, 26 Oct 2011 19:56:28 by DanielSwe

Latest Revisions Edit

All content is © 2008-2023 by its respective authors. By adding content to this wiki, you agree to release it under the BSD license.