wal.sh
home > research > uiua · Jan 01, 2024

Uiua

uiuaarray programmingstack-basedtacit programmingAPLJBQNreversible computinginverseununder

Uiua

Table of Contents

1. Introduction to Uiua

Uiua (pronounced "wee-wuh") is a modern array programming language that distinguishes itself through its unique stack-based paradigm. Unlike traditional array languages that rely on named variables, Uiua embraces a tacit programming style where data flows through an implicit stack. This approach creates remarkably concise and expressive code while maintaining readability through carefully designed glyphs.

The language builds upon decades of array programming research, drawing inspiration from APL, J, and BQN, while introducing innovative stack manipulation semantics that feel fresh and intuitive.

2. Comparison to APL/J/BQN

While APL pioneered array-oriented thinking with its mathematical notation, and J modernized it with ASCII characters, Uiua takes a different path. Where APL uses trains and J uses hooks and forks, Uiua employs stack combinators. BQN's influence is visible in Uiua's clean glyph design, but Uiua's stack-based execution model creates a fundamentally different programming experience.

The key distinction is immediacy: in Uiua, every function consumes arguments from the stack and pushes results back, creating a natural left-to-right flow that many find more intuitive than APL's right-to-left evaluation.

3. Key Concepts

3.1. Tacit Programming

Functions are composed without explicitly naming parameters. The stack serves as the implicit data channel between operations.

3.2. Stack Manipulation

Combinators like dup (duplicate), flip (swap), and over (copy second) enable elegant data flow without variables.

4. Simple Code Examples

# Sum of squares from 1 to 10
/+ⁿ2⇡10

285

# Reverse a list
⇌ [1 2 3 4 5]

[5 4 3 2 1]

# Fibonacci sequence (first 10)
⇌⍥(⊂⊸(/+↙2))8 [0 1]

[1 0 1 1 2 3 5 8 13 21]

Verified on FreeBSD 15.0-RELEASE (amd64) with uiua 0.18.1 (cargo install uiua). Some ° inverses may require newer versions.

5. Invariants as Assertions

Uiua's ⍤ (assert) makes property-based assertions concise. Each is a one-liner invariant – the same shapes used in formal verification, expressed in array notation. 

# Gauss: sum of 0..10 = 10*11/2
⍤"gauss" = (/+⇡11) (÷2 ×10 11)

# Reverse is an involution: reverse(reverse(x)) = x
⍤"reverse involution" ≍ [1 2 3] ⇌⇌ [1 2 3]

# Length is preserved under map
⍤"length preserved" = (⧻[1 2 3]) (⧻ +1 [1 2 3])

# Sort is idempotent: sort(sort(x)) = sort(x)
⍤"sort idempotent" ≍ (⍆[3 1 2]) (⍆⍆[3 1 2])

These are the array-language equivalents of property-based tests. The assertion message names the invariant; the expression encodes the universal quantifier over the concrete input. Compare to the pocket-es spec tokenizer invariants (idempotency, lowercase, no stopwords) – same contract shape, different notation.

6. Reversibility: ° (un), ⍜ (under), ⌅ (obverse)

Uiua has first-class support for derived inverses – the strongest real-world implementation of the Janus principle in a deployed language. Three modifiers formalize the relationship between forward and backward computation:

6.1. ° (un): mechanically-derived inverses

The ° modifier inverts any function whose inverse the compiler can derive. The inverse is not hand-written; it is produced from the function's definition.

Forward ° (inverse) Round-trip?
√ (sqrt) °√ (square) Yes
⊟ (couple) °⊟ (un-couple) Yes
⋯ (bits) °⋯ (un-bits) Yes
utf (encode) °utf (decode) Yes
⊥ (base) °⊥ (un-base) Yes
⍉ (transpose) °⍉ (un-transpose) Yes
⍆ (sort) °⍆ (shuffle) No – lossy

Most functions are not invertible. Wrapping a non-invertible function in ° produces a compile-time error – the language rejects the inverse statically. 

# sqrt / square round-trip
⍤"sqrt round-trip" ≍ 9 °√√ 9

The °⍆ (un-sort → shuffle) case is instructive: sorting is a surjection that discards ordering information. Its "inverse" can only produce a permutation, not the original. Uiua's designers made this explicit – an honest affordance that acknowledges the information loss rather than erroring.

6.2. ⍜ (under): do, transform, undo

The ⍜ modifier applies a function, operates on the result, then undoes the outer function. It is the lens/bracket pattern expressed as a stack combinator. 

# Multiply only the first element by 10, restore structure
⍤"under lens" ≍ [100 2 3] ⍜⊢(×100) [1 2 3]

# Negate the sorted version, then un-sort back to original positions
⍜⍆¯ [3 1 4 1 5]

Anything °-able is ⍜-able. Some non-invertible cores can also be used under ⍜ when the outer function provides enough context to reconstruct the original.

6.3. ⌅ (obverse): user-defined inverse pairs

The ⌅ modifier lets users specify custom inverse pairs for their own functions – the same :encode / :decode structure used by the encode pipeline tool. This bridges the gap between language-derived inverses and domain-specific encode/decode pairs.

6.4. Significance for reversible pipeline design

Uiua is arguably the strongest real-world example in the concatenative-language lineage for reversible computation. Compared to:

  • Forth: hand-written inverses, no compiler enforcement
  • Factor: verifies stack effects, not invertibility
  • Janus: structural guarantee via syntax, but an academic language

Uiua derives inverses (°), supports do-and-undo (⍜), and allows user-extensible inverse pairs (⌅) – all as deployed, shipped modifiers in a language with an active user community.

7. Encode Tool Codec Equivalents

Each codec from the reversible pipeline tool has a Uiua analog. The ° modifier makes the inverse? flag a language-level guarantee.

7.1. Reverse as involution (The Shining, American Dad)

The simplest reversible codec – and the one most recognizable from pop culture. See REDRUM and Roodpart examples.

7.2. Sqrt / square (bijection on non-negatives)

# °√ (un-sqrt) = square. Round-trips exactly on non-negatives.
⍤"sqrt round-trip" = 9 °√√ 9
⍤"sqrt round-trip" = 25 °√√ 25

7.3. Reverse (involution)

# Reverse is its own inverse -- the Crab Canon property.
⍤"reverse involution" ≍ "REDRUM" ⇌⇌ "REDRUM"
⍤"MURDER" ≍ "MURDER" ⇌ "REDRUM"

7.4. Sort (surjection – irreversible)

# Sort is idempotent but not invertible.
# "listen" and "silent" both sort to the same output.
⍤"sort idempotent" ≍ (⍆"listen") (⍆⍆"listen")
⍤"anagram collapse" ≍ (⍆"listen") (⍆"silent")
# °⍆ gives shuffle (random permutation) -- honest about information loss

7.5. Threading macro as stack pipeline

Uiua IS a threading macro – every line is (-> value f1 f2 f3). The stack is the implicit threading medium. There is no pipe operator because the entire language is a pipe.

The enforcement spectrum: Uiua's ° rejects non-invertible functions at compile time. Clojure's :inverse? true is a manual annotation checked by PBT. The gap between them is the gap between proof and empirical testing – see the enforcement spectrum table.

8. Connections to the Reversible Pipeline Research

9. Resources