XY: A Concatenative Language That Merges K's Power with Joy's Elegance

A new programming language named XY has appeared, positioning itself as a direct descendant of two influential but distinct paradigms: the vector-oriented K language and the concatenative Joy language. Its design philosophy is rooted in making the entire computational state explicit at every moment, offering a model that differs significantly from both its parents.

The Computational Model: Stack and Queue

XY's core innovation is its dual-state representation. Computation consists of a sequence of steps applied to a pair of objects: X (the stack) and Y (the queue). The stack contains everything that has been computed so far, while the queue contains everything that remains to be computed. Each step takes the next element from the queue, applies it to the stack and the remaining queue, and produces a new stack and a new queue.

This model is fundamentally "stackless" in the Joy sense. Instead of operations manipulating a single stack, evaluation proceeds by passing the current continuation at each step. When a defined symbol is encountered, its value is pushed onto the queue, where it is immediately evaluated. This creates a powerful flow of control where the queue itself becomes the program counter.

Heritage: K's Datatypes and Verbs

XY inherits K's rich set of datatypes: integer, float, character, symbol, null, function, list, and dictionary. It also adopts K's twenty elementary operators (verbs), each with three functional forms: dyad, monad, and commuted dyad. For example, the subtraction verb - can be used as:

• Dyad: 3 2 - → 1 (subtract)
• Monad: 2 - → -2 (negate)
• Commuted: 3 2 -. → -1 (commute subtract)

Many of these verbs are atomic, meaning they pervade their arguments to iterate over atoms. For instance, [1 2 3][4 5 6] + results in [5 7 9].

XY also maps K's six overloaded adverbs (' / \ ': /: \:) to distinct words in XY, and supports K system functions and input/output primitives.

Joy's Influence: Unary Stack Functions

From Joy, XY takes the concept of operators as unary functions that transform a stack. In Joy, + would take a stack, pop two numbers, add them, and push the result back. XY extends this concept by making operators functions of the form [stack queue] -> [stack' queue'].

For example, in XY, applying + to [X Y] where X is n^m (stack with numbers n and m on top) and Y is the queue, results in [X^(n+m) Y].

Core Primitives: Beyond Stack Manipulation

XY introduces seven core primitives that manipulate either the stack, the queue, or both:

1. -> (queue): Sets the queue to whatever is on top of the stack. This acts like an unconditional "go to." Example: 1 2 [+ 4 5 *] -> results in 10 20 30 3 20.

2. <- (stack): Sets the stack to the top value of the old stack (Joy's 'unstack' word).

3. => (cache): Appends to the queue whatever is on top of the stack. This can simulate Factor's >r.

4. <= (uncache): Pushes onto the stack whatever is last on the queue. This can simulate Factor's r>.

5. / (use): Prepends to the queue whatever is on top of the stack. This is Joy's 'i' combinator.

6. \ (mention): Appends to the stack whatever is next on the queue. This "escapes" execution and has no direct Joy analogue.

7. ` (enclose) and disclose: Self-dual operations that convert between lists and function-atoms.

Pattern Notation: Deconstructive Binding

XY supports a powerful pattern notation for deconstructing data structures. A pattern consists of a template (a list of names) followed by code, enclosed in curlies: { [a b c] a b + c * }

When evaluated, the pattern maps elements from the top of the stack into the template names, then maps those values into the code. The result is a new stack (with mapped elements removed) and a new queue (with the mapped code prepended).

Upper-case names in tail position can capture the remainder of a list. For example, { [[a A]] \a A } implements uncons, returning the first element and the remainder.

Shuffle Symbols: A Concise Notation

XY introduces shuffle symbols of the form A--B, which translate into patterns that rearrange elements. For example, abc--bca becomes { [a b c] b c a }. This notation supports < and > as shorthand for [ and ], allowing concise transformations like a<bB>c--cBa.

Flatness in XY 2.0

A language is considered "flat" if any sequence of tokens can be partitioned in multiple ways without affecting semantics. XY 1.0 was not flat, but XY 2.0 implements flatness by treating certain tokens as literals and defining bracket operations to collect stack elements into quotations.

In XY 2, you can write: ; f [1 ; g 2 3] f g / [1 2 3]. Here, f is evaluated, [ is placed on the stack, then 1, then g. The / moves the value of g to the queue. 2 and 3 are placed on the stack, then ] evaluates, taking [ 1 2 3, enlisting it, and placing [1 2 3] on the queue for evaluation.

XY 0: A Revised Approach

The language continues to evolve. XY 0 revisits certain features, removing patterns and adding quotations for both stack and queue with ( stack* and ) queue*. This simplification focuses on the core concatenative model while maintaining the explicit state representation.

Implementation and Ecosystem

Remarkably, XY is implemented in approximately 150 lines of K code, demonstrating the language's conciseness. The implementation includes whitespace and comments, showing that the core interpreter is compact enough to understand and modify.

The language ships with a standard script xy.xy that establishes modules for stack operations, list manipulation, general operators, predicates, queue operations, K monads, K adverbs, Joy combinators, call/cc, I/O, and miscellaneous utilities.

Programming Examples

The language specification includes several instructive examples:

1. Defining => and <=: Using patterns to implement queue manipulation primitives.

2. Joy's dip and step combinators: Showing how concatenative patterns can replicate higher-order control flow.

3. Call/cc in XY: Demonstrating continuation capture and resumption.

4. Infix K notation to postfix: A converter that transforms K's infix notation into XY's postfix evaluation.

The Philosophical Difference

What makes XY interesting is its explicit representation of both past and future computation. In most languages, the program counter or evaluation stack implicitly tracks what's been done and what's next. XY makes this explicit: the stack is the past, the queue is the future. This creates a programming model where control flow becomes a matter of manipulating the queue, and data flow becomes a matter of manipulating the stack.

The language's "stackless" nature—where evaluation proceeds by passing continuations—means that every operation has access to the complete computational context. This enables powerful metaprogramming and control flow patterns that would be difficult in conventional stack-based languages.

Conclusion

XY represents an experiment in concatenative language design that merges the practical power of K's array processing with Joy's elegant compositional model. Its explicit state representation and queue-based control flow offer a fresh perspective on program execution, making it a fascinating tool for exploring computational models and for writing programs where control flow is as important as data transformation.

For those interested in exploring further, the XY homepage provides the full specification and implementation details.