Front Page All Articles Recent Changes Random Article

Contents

Concatenative language

  • ACL
  • Ait
  • Aocla
  • Breeze
  • Callisto
  • Cat
  • Cognate
  • colorForth
  • Concata
  • CoSy
  • Deque
  • DSSP
  • dt
  • Elymas
  • Enchilada
  • ETAC
  • F
  • Factor
  • Fiveth
  • Forth
  • Fourth
  • Freelang
  • Gershwin
  • hex
  • iNet
  • Joy
  • Joy of Postfix App
  • kcats
  • Kitten
  • lang5
  • Listack
  • LSE64
  • Lviv
  • Meow5
  • min
  • Mirth
  • mjoy
  • Mlatu
  • Ode
  • OForth
  • Om
  • Onyx
  • Plorth
  • Popr
  • Porth
  • PostScript
  • Prowl
  • Quest32
  • Quackery
  • r3
  • Raven
  • Retro
  • RPL
  • SPL
  • Staapl
  • Stabel
  • Tal
  • Titan
  • Trith
  • Uiua
  • Worst
  • xs
  • XY
  • 5th
  • 8th

Concatenative topics

  • Compilers
  • Interpreters
  • Type systems
  • Object systems
  • Quotations
  • Variables
  • Garbage collection
  • Example programs

Concatenative meta

  • People
  • Communities

Other languages

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

Meta

  • Search
  • Farkup wiki format
  • 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 for instance,

(function evenp)
(lambda (x) (not (evenp x)))
(lambda (x) (> x 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 the applicative version; note the closure does not print readably:

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

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}>

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, 31 Dec 2008 09:32:01 by mnestic (formatting)

Latest Revisions Edit

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