Concatenative programming language: Difference between revisions

Revision as of 20:38, 9 June 2005

Latest revision as of 09:23, 13 August 2025

(168 intermediate revisions by 89 users not shown)

Line 1:

{{Short description|Type of programming language}}

In '''concatenative''' [[programming language]]s, the [[concatenation]] of appropriate programs denotes the composition of the [[function (programming)|function]]s which the programs denote. Operations map an input [[stack (computing)|stack]] into a results stack, and so it is possible to repeatedly concatenate a sequence of operations to create a program.

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]].

A programming language is concatenative (and not [[applicative]]) when:

*The elementary well-formed [[expression]]s of the language are [[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.

==Example==

In this definition, there is no mention of the stack, and it is theoretically possible to have a concatenative language without a stack, but in practice, no such language exists. This precise definition of concatenative languages is very contravercial, and the actual meaning of "concatenative" is frequently debated.

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

<syntaxhighlight lang="javascript">

Arguably, [[Forth programming language|Forth]] was the first concatenative language, 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. The [[:Category:Concatenative programming languages|category Concatenative programming languages]] contains an exhaustive list of those known to [[Wikipedia]].

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>

Many people, particularly people on the more practical side of programming in languages like Factor and Forth, consider the term "concatenative programming language" to be mostly useless. There is still a lot of confusion about what "concatenative" means exactly, and the above definition isn't what everyone accepts. Opponents of the term suggest using words like "stack-based" instead, which is usually more meaningful.

x foo bar baz

== Examples ==

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>

In Joy, the program fragment:

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>

:2 7 +

==Properties==

Pushes "2" then "7" onto the stack. The "+" [[operator]] then replaces the stack with a new stack that contains the resulting sum "9", this notation is also known as "[[Reverse Polish notation]]".

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>

== External links ==

* 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.

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

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

*[http://www.mail-archive.com/[e-mail]/msg00907.html Joy and Concatenative Programming]

* 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==

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.

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

==See also==

* [[Function-level programming]]

* [[Homoiconicity]]

* [[Stack-oriented programming language]]

* [[Tacit programming]]

==References==

{{Reflist}}

== External links ==

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

{{Programming paradigms navbox}}

{{Types of programming languages}}

{{DEFAULTSORT:Concatenative Programming Language}}

[[Category:Concatenative programming languages| ]]

<!-- Hidden categories below -->

[[Category:Articles with example JavaScript code]]