Concatenative programming language: Difference between revisions

Revision as of 19:34, 31 January 2008

Latest revision as of 09:23, 13 August 2025

(136 intermediate revisions by 79 users not shown)

Line 1:

{{Short description|Type of programming language}}

The '''concatenative''' or '''stack-based''' [[programming language]]s are ones in which the [[concatenation]] of two pieces of code expresses the [[function composition|composition]] of the functions they express. These languages use a [[stack (data structure)|stack]] to store the arguments and return values of operations.

A '''concatenative programming language''' is a [[Point-free programming|point-free]] computer [[programming language]] in which all expressions denote [[Function (mathematics)|functions]], and the [[juxtaposition]] of [[Expression (computer science)|expressions]] denotes [[function composition]].<ref name="dobbscodetalk">{{cite magazine |last1=Diggins |first1=Christopher |date=2008-12-31 |url=http://drdobbs.com/blogs/architecture-and-design/228701299 |title=What is a concatenative language |magazine=[[Dr. Dobb's Journal]] |access-date=2013-07-01}}</ref> Concatenative programming replaces [[function application]], which is common in other [[programming paradigm]]s, with [[Function composition (computer science)|function composition]] as the default way to build [[Function (computer programming)|subroutines]].

The most widely used concatenative language is certainly the page description language [[PostScript]], a restricted version of which is used in [[PDF]]; however, Poscript code is usually generated by programs written in other languages. Another language having played an important role in the history of programming languages is [[Forth (programming language)|Forth]]. The [[RPL_programming_language|RPL]] used on [[HP-28]] and [[HP-48]] scientific calculators is also well-known amongst engineers. Recent experimental concatenative languages include [[Joy programming language|Joy]], [[Cat (programming language)|Cat]] and [[Factor (programming language)|Factor]][http://www.tiobe.com/index.htm?tiobe_index]. The concatenative languages may be regarded as a language family, similar to the [[Lisp (programming language)|Lisp]] languages. As with the Lisps (including Scheme), there are strong "family resemblances" within the group. However, there are also major differences in the design, implementation, and purposes of these languages.

==Example==

== History and description ==

For example, a nesting of operations in an applicative language like the following:

<syntaxhighlight lang="javascript">

[[Forth (programming language)|Forth]] was the first language of this sort, but [[Joy programming language|Joy]] was the first language to call itself concatenative. The creator of Joy, [[Manfred von Thun]], has written much about concatenative theory.

baz(bar(foo(x)))

</syntaxhighlight>

...is written in a concatenative language as a sequence of functions:<ref>{{cite web |url=http://concatenative.org/wiki/view/Concatenative%20language/Name%20code%20not%20values |title=Name code not values |publisher=Concatenative.org |access-date=13 September 2013}}</ref>

Formally speaking, a programming language is concatenative (and not [[applicative]]) when: {{Fact|date=December 2007}}

*The elementary well-formed [[expression (programming)|expression]]s of the language are [[unary operation|monadic]] functions of one argument and one return value.

*If X and Y are well-formed expressions, then the concatenation of X and Y is well-formed.

*If Z is the concatenation of X and Y, then the value of Z is the composition of the values of X and Y.

x foo bar baz

In this definition, there is no mention of the stack; however, all concatenative languages do use a stack, as it is the most straightforward way to pass data from one operation to the next. The term "concatenative" is not universally accepted as a particularly useful term, with many users of these languages preferring to call them "stack-based".

Functions and procedures written in concatenative style are not [[Value-level programming|value level]], i.e., they typically do not represent the data structures they operate on with explicit names or [[Identifier#In computer science|identifiers]]. Instead they are [[Function-level programming|function level]] – a function is defined as a [[pipeline (software)|pipeline]], or a sequence of operations that take parameters from an implicit [[data structure]] on which all functions operate, and return the function results to that shared structure so that it will be used by the next operator.<ref>{{cite web |url=http://concatenative.org/wiki/view/Concatenative%20language |title=Concatenative language |publisher=Concatenative.org |access-date=13 September 2013}}</ref>

Operators or functions in these languages are usually referred to as ''words'', and this article will refer to them as such.

The combination of compositional [[Semantics (computer science)|semantics]] with a [[Syntax (programming languages)|syntax]] that mirrors such a semantic makes concatenative languages highly amenable to algebraic manipulation of programs;<ref>{{cite web |url=http://www.latrobe.edu.au/philosophy/phimvt/joy/j00rat.html |archive-url=https://web.archive.org/web/20110115151536/http://www.latrobe.edu.au/philosophy/phimvt/joy/j00rat.html |archive-date=2011-01-15 |title=Rationale for Joy, a functional language}}</ref> although it may be difficult to write mathematical expressions directly in them.<ref name="whymatters"/> Concatenative languages can be implemented efficiently with a [[stack machine]], and are commonly present implicitly in [[virtual machine]]s in the form of their [[instruction set]]s.<ref name="whymatters">{{cite web |last1=Purdy |first1=Jon |date=12 February 2012 |url=http://evincarofautumn.blogspot.com/2012/02/why-concatenative-programming-matters.html |title=Why Concatenative Programming Matters |website=The Big Mud Puddle |access-date=12 August 2025}}</ref>

== Postfix notation ==

==Properties==

Code in concatenative languages resemble the [[postfix notation]] or [[reverse Polish notation]] (RPN) form of arithmetic. Arguments, or code that produces arguments, comes first, followed by the words that use those arguments. Literals, such as numbers, place values on the stack; other words may consume some items from the stack and produce others.

The properties of concatenative languages are the result of their compositional syntax and semantics:

* The reduction of any expression is the simplification of one function to another function; it is never necessary to deal with the application of functions to objects.<ref>{{cite web |last1=von Thun |first1=Manfred |year=2011 |url=http://www.latrobe.edu.au/phimvt/joy/j08cnt.html |title=Joy compared with other functional languages |archive-url=https://web.archive.org/web/20111006225512/http://www.latrobe.edu.au/phimvt/joy/j08cnt.html |archive-date=2011-10-06}}</ref>

An example:

* Any subexpression can be replaced with a name that represents the same subexpression. In concatenative programming practice, this is called [[Code refactoring|factoring]], and is used extensively to simplify programs into smaller parts.

* The syntax and semantics of concatenative languages form the algebraic structure of a [[monoid]].<ref>{{cite web |last1=von Thun |first1=Manfred |year=2009 |url=http://www.latrobe.edu.au/philosophy/phimvt/joy/j02maf.html |title=Mathematical foundations of Joy |archive-url=https://web.archive.org/web/20100731060810/http://www.latrobe.edu.au/philosophy/phimvt/joy/j02maf.html |archive-date=2010-07-31}}</ref>

* Concatenative languages can be made well-suited to an implementation inspired by [[linear logic]] where no [[Garbage (computer science)|garbage]] is ever generated.<ref>{{cite report |last1=Baker |first1=Henry |year=1993 |url=http://home.pipeline.com/~hbaker1/ForthStack.html |title=Linear Logic and Permutation Stacks: The Forth Shall Be First |publisher=Nimble Computer Corporation |via=Home.pipeline.com |access-date=2013-07-01 |archive-url=https://web.archive.org/web/20140724091729/http://home.pipeline.com/~hbaker1/ForthStack.html |archive-date=2014-07-24 |url-status=dead}}</ref>

==Implementations==

2 3 + .

The first concatenative programming language was [[Forth (programming language)|Forth]], although [[Joy (programming language)|Joy]] was the first language which was termed concatenative. Other concatenative languages are [[dc (computer program)|dc]], [[Factor (programming language)|Factor]], Onyx, [[PostScript]], [[RPL (programming language)|RPL]], Staapl,<ref name="Staapl">{{cite web |last1=Schouten |first1=Tom (zwizwa) |date=<!-- Undated --> |url=http://zwizwa.be/staapl/ |title=Staapl: Forth on Scheme for Embedded Controllers |website=Zwizwa LLC |access-date=12 August 2025}}</ref> and experimental and discontinued ones including:<!-- Alphabetic order--> Enchilada,<ref name="Enchilada">{{cite web |author1=rapido |author2=NewDave |author3=jacintheford |author4=goren |date=2 January 2024 |url=https://concatenative.org/wiki/view/Enchilada |title=Enchilada |website=Concatenative.org |access-date=12 August 2025}}</ref> Om,<ref name="Om">{{cite web |author1=sparist |date=<!-- Undated --> |url=https://www.om-language.com/ |title=The Om Programming Language |website=Om-language.com |access-date=12 August 2025}}</ref> XY.<ref name="XY">{{cite web |last1=Apter |first1=Stevan |date=2004 |url=http://www.nsl.com/k/xy/xy.htm |title=The Concatenative Language XY |website=no stinking loops |access-date=12 August 2025}}</ref>

Most existing concatenative languages are [[Stack-oriented programming|stack-based]]. This is not required, and other models have been proposed.<ref name="XY"/><ref name="Enchilada"/><ref name="Om"/> Concatenative languages are currently used for [[Embedded system|embedded]],<ref name="Staapl"/> [[Application software|desktop]], and [[Web development|web programming]], as [[Translator (computing)|target languages]], and for research purposes.

In Forth and Factor, this is a valid program: <code>2</code> and <code>3</code> are literals, words that simply push a value onto the stack. <code>+</code> is a mathematical operator; it removes the top two values from the stack and pushes their sum. Finally, the <code>.</code> (dot) operator removes the top value and prints it to the display. Thus, this program will print the number 5.

Most concatenative languages are [[dynamically typed]]. Exceptions include the [[statically typed]] Cat language<ref>{{cite web|url=http://www.cat-language.com/manual.html |title=Cat Specification |publisher=Cat-language.com |access-date=2013-07-01 |archive-url=https://web.archive.org/web/20150205081218/http://cat-language.com/manual.html |archive-date=2015-02-05}}</ref> and its successor, Kitten<ref>{{Cite web |last1=Purdy |first1=Jon |title=Kitten Programming Language |url=https://kittenlang.org/ |access-date=2025-03-31 |website=kittenlang.org}}</ref>.

== Flow control ==

==See also==

In order to be [[Turing-complete]], a language must have some means of [[flow control]] -- the ability to make branches or choices based on the value of an expression. Concatenative languages implement flow control in different ways. Contrast the following examples in Forth and Factor:

* [[Function-level programming]]

* [[Homoiconicity]]

* [[Stack-oriented programming language]]

* [[Tacit programming]]

==References==

= IF 23 ELSE 17 THEN

{{Reflist}}

== External links ==

= [ 23 ] [ 17 ] if

* [http://www.concatenative.org/ Concatenative.org: Wiki], about concatenative programming

{{Programming paradigms navbox}}

Both examples do the same thing: compare the top two items on the stack; if they are equal, the value 23 is left on the stack; if they are not equal, the value 17 is left. In Forth, the word <code>IF</code> is special; it causes the code prior to the <code>ELSE</code> to be executed if the condition is true, or the code after the <code>ELSE</code> if it is false. In Factor, the word <code>if</code> is just another function; it consumes the condition and two ''quotations'', or quoted code fragments; it executes the first quotation or the second based on whether the condition is true. The <code>ifelse</code> operator in PostScript is similar.

{{Types of programming languages}}

{{DEFAULTSORT:Concatenative Programming Language}}

The formalization of code quotations, a feature ultimately inherited from [[Lisp programming language|Lisp]], distinguishes the later concatenative languages such as Factor and PostScript from earlier ones such as Forth. Words that operate on quotations are sometimes called [[combinator]]s.

[[Category:Concatenative programming languages]][[Category:Programming| paradigms]]

<!-- Hidden categories below -->

== Definitions and parsing words ==

[[Category:Articles with example JavaScript code]]

The concatenative languages differ widely in the syntax used to define new words. The following pieces of code in Cat, Forth or Factor, and Joy all do the same thing: define a new word called <code>add100</code> which adds 100 to the value on the top of the stack.

define add100 { 100 + }

: add100 100 + ;

DEFINE add100 == 100 + .

In each case, the body of the definition is the same: the words <code>100 +</code>. What differ are the ''parsing words'' used to tell the language that a definition is taking place. Parsing words are somewhat analogous to ''keywords'' in C or ''special operators'' in Lisp: rather than expressing operations on the stack, they control how the parser deals with the following words.

It is possible to define new parsing words. This ability gives concatenative languages their equivalent of Lisp macros: programmers can define new syntax.

[[Category:Concatenative programming languages]][[Category:Programming paradigms]]

== External links ==

*[http://www.vector.org.uk/archive/v203/fpjoy203.htm A Note on Functional Programming in Joy and K]

*[http://tech.groups.yahoo.com/group/concatenative/ Yahoo Discussion Group on Concatenative Languages]