Baba Yaga

A Scripting Language

Baba Yaga is a combinator-based scripting language that aims to be dangerously functional-brained, has minimal syntax, an intuitive approach to pattern matching, and hopefully enough of a standard library to be useful...but not too much of a standard library to be difficult to recall.

This whole thing started as an aesthetic curiosity, and continued on from there. I wanted to be able to do pattern matching like this:

factorial : n -> 
  when n is
    0 then 1
    _ then n * (factorial (n - 1));

I've implemented a whole bunch of forths, and a couple schemes, but never have I ever implemented something like a "regular" programming language. And, while, an ML-flavored programming language isn't exactly regular, this has grown from an aesthetic curiosity to a full-blown aesthetic indulgence.

Baba Yaga supports...

  • Function definitions using arrow syntax with lexical scoping
  • Pattern matching with a single when ... is ... then expression that handles wildcards and arbitrarily nested features
  • Tables inspired by Lua's tables, with array-like and key-value entries, including boolean keys
  • Function references using an @ operator for higher-order programming
  • IO Operations including input, output, and assertions, plus an ..emit and ..listen pattern for interfacing a functional core with the outside world. This contains side effects to a very limited surface area
  • Standard Library with a complete set of arithmetic, comparison, logical, and higher-order combinators...I think (let me know if I'm missing anything)
  • APL-style operations with element-wise and immutable table operations so that you can use broadcasting instead of looping
  • Function composition with compose, pipe, and via operators, supporting a bunch of different ways to chain functions together
  • Currying by default - all functions are automatically curried
  • Combinator-based architecture everything is "just" a function call or reference under the hood...because this supposedly made parsing easier...but I'm not yet totally sold on that reasoning

Example Script

/* Basic arithmetic */
result : 5 + 3 * 2;
..out result;

/* Function definition */
factorial : n -> 
  when n is
    0 then 1
    _ then n * (factorial (n - 1));

/* Function composition */
double : x -> x * 2;
increment : x -> x + 1;
composed : compose @double @increment 5;
..out composed;

/* Pattern matching */
classify : x y -> 
  when x y is
    0 0 then "both zero"
    0 _ then "x is zero"
    _ 0 then "y is zero"
    _ _ then "neither zero";

/* Tables */
person : {name: "Baba Yaga", age: 99, active: true};
..out person.name;
..out person["age"];

numbers : {1, 2, 3, 4, 5};
doubled : map @double numbers;
..out doubled[1]; 

/* APL-style element-wise operations over tables */
table1 : {a: 1, b: 2, c: 3};
table2 : {a: 10, b: 20, c: 30};
sum : each @add table1 table2;
..out sum.a;

Baba Yaga files should use either the .txt file extension, or the .baba extension.

Key Features

Function Application

Functions are applied using juxtaposition (space-separated), and you can use parentheses to help disambiguate precedence:

f x          /* Apply function f to argument x */
f x y        /* Apply f to x, then apply result to y */
f (g x)      /* Apply g to x, then apply f to result */

Pattern Matching

Use when expressions for pattern matching:

result : when value is
  0 then "zero"
  1 then "one"
  _ then "other";

Tables

Create and access data structures:

/* Array-like */
numbers : {1, 2, 3, 4, 5};

/* Key-value pairs */
person : {name: "Beatrice", age: 26};

/* Boolean keys */
flags : {true: "enabled", false: "disabled"};

Function References

Use the @ to make reference to functions as arguments for other functions:

numbers : {1, 2, 3, 4, 5};
doubled : map @double numbers;

Combinators and Higher-Order Functions

Baba Yaga tries to provide a comprehensive set of combinators for functional programming:

Core Combinators

  • map f x - Transform elements in collections
  • filter p x - Select elements based on predicates
  • reduce f init x - Accumulate values into a single result
  • each f x - Multi-argument element-wise operations

Function Composition

  • compose f g - Right-to-left composition (mathematical style)
  • pipe f g - Left-to-right composition (pipeline style)
  • via - Kinda like . composition syntax: f via g via h

Table Operations

All table operations are immutable so they return new tables.

  • t.map, t.filter, t.set, t.delete, t.merge, t.get, t.has, t.length

When to Use Which Combinator

  • Use map for general collections, t.map to emphasize table operations
  • Use map for single-table transformations, each for combining multiple collections.

Standard Library

The language includes a comprehensive standard library:

Arithmetic: add, subtract, multiply, divide, modulo, power, negate
Comparison: equals, notEquals, lessThan, greaterThan, lessEqual, greaterEqual
Logical: logicalAnd, logicalOr, logicalXor, logicalNot
Higher-Order: map, compose, pipe, apply, filter, reduce, fold, curry, each
Enhanced: identity, constant, flip, on, both, either
Table Operations: t.map, t.filter, t.set, t.delete, t.merge, t.get, t.has, t.length

Architecture

Baba Yaga uses a combinator-based architecture where all operations are translated to function calls:

  1. Lexer: Converts source code into tokens
  2. Parser: Translates tokens into AST, converting operators to combinator calls
  3. Interpreter: Executes combinator functions from the standard library

The idea behind this approach is that it should eliminate parsing ambiguity while preserving syntax and enabling functional programming patterns like currying and composition, but the implementation is likely a little bit janky.

Testing

Run the complete test suite!

./run_tests.sh

This assumes you are using bun, but I've also tested extensively with both node and the browser, too. I haven't validated it, yet, but I think Baba Yaga should work with quickjs, too.

Debug Mode

Enable debug output for development using the flag DEBUG=1 or DEBUG=2:

DEBUG=1 node lang.js your-script.txt

This'll output a lot of debug info, including the AST (as JSON).

Adding Features

If you wanna add language features, the easiest way to do it is to see if you can implement them in Baba Yaga script, if you need to get into the guts of the thing, though, you wanna follow this pattern,

  1. Add tests in tests/
  2. Add tokens in lexer.js
  3. Add parsing logic in parser.js
  4. Add evaluation logic in lang.js
  5. Validate against the tests you added earlier
  6. Update documentation