The Compose Language

Compose is a concatenative, stack-based programming language. Programs in Compose are built by writing sequenced functions that modify the stack. Compose is functional programming inspired and makes use of functions as data. In concatenative languages, the flow of data is entirely determined by the stack. Each function operates on the stack: it takes some number of values from the top, performs a computation, and pushes results back onto the stack. Calling two functions side by side means “apply the first function, then the second, passing along the stack as the argument.”

For example, in a simple concatenative style:

2 3 +

This pushes 2 and 3 onto the stack, then applies the + function, adding the two numbers and leaving 5 on the stack.

Compose follows this model with a minimal set of primitives, allowing programs to be constructed by composing small, reusable functions. Its design emphasizes consistent stack behavior and predictable composition, keeping the core language simple and easily comprehensible.

Features

Lambda Composition

Compose allows functions to be stored as data on the stack as lambdas, and these lambdas can be composed into more complex functions. They can be manipulated like other stack data, and passed around as arguments for other functions.

List Processing

Compose provides the map, filter, and fold functions for processing lists. Lists can store an unlimited number of items, and do not require that their elements be the same type.

Recursive Functions

Compose allows the definition of recursive functions. Currently it only supports recursion of named functions, but recursion from within lambdas is a planned feature.

Installation

The Compose interactive environment, Compositor, can be installed easily with Cargo.

cargo install compositor

To start the interactive environment, use command cmpstr, and to exit from within the environment, use !exit.

Data

Data terms are functions that push the data item they represent to the stack.

Integers

Integers are dynamic-size, signed whole numbers.

0, 100, -2000, etc.

Booleans

Booleans are true or false values.

true, false

Lambdas

Lambdas are anonymous functions that can be stored and manipulated like data.

( copy * ), ( 1 + ), ( 2 % 0 = ), etc.

Lists

Lists are collections of unlimited length. They can store items of different types.

[ 1 2 3 4 5 ], [ true false false true ], [ 1 true 2 false 3 true ], etc.

Core Functions

Core functions are named functions built into the Compose language.

copy

Copies the item on top of the stack.

true copy → true true

1 2 copy → 1 2 2

[ 1 2 3 4 5 ] copy → [ 1 2 3 4 5 ] [ 1 2 3 4 5 ]

hop

Copies the item on top of the stack.

false true hop → false true false

10 20 hop hop → 10 20 10 20

[ 1 2 3 4 5 ] copy → [ 1 2 3 4 5 ] [ 1 2 3 4 5 ]

pick

Copies the item at a specified index on the stack. Indexes wrap around the stack, and negative indexes start at the bottom of the stack.

1 2 3 4 5 2 pick → 1 2 3 4 5 3

false true 3 pick → false true false

1 2 3 4 5 -1 pick → 1 2 3 4 5 1

drop

Removes an item from the top of the stack.

true false drop → true

1 2 3 4 5 drop drop → 1 2 3

[ 1 2 3 4 5 ] [ 6 7 8 9 10 ] drop → [ 1 2 3 4 5 ]

swap

Swaps the two items on top of the stack.

10 20 swap → 20 10

false true swap swap → false true

rotate

Moves the item on top of the stack under the two items below it.

1 2 3 rotate → 3 1 2

10 20 30 rotate rotate rotate → 10 20 30

+

Computes the sum of two integers on top of the stack.

5 10 + → 15

-500 200 + → -300

-

Computes the difference of two integers on top of the stack.

20 10 - → 10

50 100 - → -50

*

Computes the product of two integers on top of the stack.

10 20 * → 200

-5 6 * → -30

/

Computes the quotient of two integers on top of the stack.

-100 20 / → -5

20 6 / → 3

%

Computes the remainder of two integers on top of the stack.

-100 9 % → -1

20 6 % → 2

+

Computes the Boolean NOT value for a boolean value on top of the stack.

true ! → false

false ! ! → false

|

Computes the Boolean OR value for two boolean values on top of the stack.

false false | → false

false true | → true

true true | → true

&

Computes the Boolean AND value for two boolean values on top of the stack.

false false & → false

false true & → false

true true & → true

^

Computes the Boolean XOR value for two boolean values on top of the stack.

false false ^ → false

false true ^ → true

true true ^ → false

=

Consumes the top two items on the stack and produces true if they are equal, and false if they are not.

false false = → true

5 10 = → false

0 0 = → true

100 true = → false

>

Consumes two integers from the top of the stack and produces true if the integer second from the top is greater than the integer on top, otherwise produces false.

5 0 > → true

-5 0 > → false

0 0 > → false

<

Consumes two integers from the top of the stack and produces true if the integer second from the top is less than the integer on top, otherwise produces false.

5 0 < → false

-5 0 < → true

0 0 < → false

apply

Consumes a lambda and applies it to the top of the stack.

5 ( 2 * ) apply → 10

6 ( copy * ) apply → 36

100 100 ( hop hop = ) apply → 100 100 true

under

Consumes a lambda and applies it to the stack under the top item of the stack.

4 5 ( 2 * ) under → 8 5

5 6 ( copy * ) under → 25 6

deep

Consumes an integer index and a lambda below it, and applies the lambda at that index in the stack. Indexes wrap around the stack, and negative indexes start at the bottom of the stack.

1 2 3 4 5 ( copy * ) 2 deep → 1 2 9 4 5

true false false ( copy copy ) -1 deep → true true true false false

1 2 3 4 5 ( drop drop ) 8 deep → 3 4 5

compose

Composes two lambdas on top of the stack into a single lambda.

( 2 * ) ( 2 + ) compose → ( 2 * 2 + )

( 2 % ) ( 1 = ) compose → ( 2 % 1 = )

?

Consumes two lambdas from the top of the stack, and a boolean below them. If the boolean is true, the bottom lambda is applied to the stack, and if it is false, the top lambda is applied to the stack.

5 false ( 2 * ) ( 2 + ) ? → 7

5 true ( 2 * ) ( 2 + ) ? → 10

append

Consumes an item from the top of the stack and appends it to the list below it.

[ 2 4 6 ] 8 append → [ 2 4 6 8 ]

[] 1 append 2 append 3 append → [ 1 2 3 ]

[] [] append → [ [ ] ]

index

Consumes a list and returns the item at a specified index. Indexes wrap around the list, and negative indexes start at the end of the list.

[ 1 2 3 4 5 ] copy 2 index → [ 1 2 3 4 5 ] 3

[ 1 2 3 4 5 ] 5 index → 1

[ 1 2 3 4 5 ] -1 index → 5

join

Joins two lists on top of the stack.

[ 1 2 3 ] [ 4 5 6 ] join → [ 1 2 3 4 5 6 ]

[ true ] [ false ] join → [ true false ]

length

Consumes a list from the top of the stack and returns its length.

[ 1 2 3 4 5 ] length → 5

[ 1 2 3 4 5 ] copy length → [ 1 2 3 4 5 ] 5

[] length → 0

map

Consumes a lambda, and a list below it, and produces the list with each item in it mapped using the lambda. The lambda must consume the original list item and produce a new one.

[ 1 2 3 4 5 ] ( 2 * ) map → [ 2 4 6 8 10 ]

[ true false true ] ( ! ) map → [ false true false ]

filter

Consumes a lambda, and a list below it, and produces a list containing only items from the original list for which the lambda produces true. The lambda must consume the original list item and produce a boolean.

[ 1 2 3 4 5 6 7 8 9 10 ] ( 2 % 0 = ) filter → [ 2 4 6 8 10 ]

[ true false true ] ( true = ) filter → [ true true ]

fold

Consumes a lambda, a list, and an accumulator value. Reduces the list from left to right by applying the lambda to the accumulator and each list item. The lambda must consume the accumulator and list item, and produce a new accumulator. The final accumulator value is produced on top of the stack.

0 [ 1 2 3 4 ] ( + ) fold → 10

1 [ 1 2 3 4 ] ( * ) fold → 24