mu 0.1¶

mu is a small language for LeetCode. mu/mu.py transpiles a mu file to Python that LeetCode accepts: one class Solution, the imports it needs, and the source of every helper it calls. This document describes version 0.1. The next version is 0.2.

An example¶

# 1143. Longest Common Subsequence
def longestCommonSubsequence(a: str, b: str) -> int
  memo f(i, j) =
    | i == len(a) or j == len(b) -> 0
    | a[i] == b[j]               -> 1 + f(i + 1, j + 1)
    | else                       -> max(f(i + 1, j), f(i, j + 1))
  f(0, 0)

Running¶

python mu/mu.py file.mu        # print the Python
python mu/mu.py --fmt file.mu  # print the file, formatted
python mu/mu.py -              # read from standard input

Lexical structure¶

Blocks are marked by indentation, as in Python. There is no colon at the end of a block header.
A line inside open brackets continues onto the next line.
Comments start with #.
Strings are Python strings: single or double quotes, triple quotes, and the prefixes f, r and b.
true, false and none are True, False and None. inf is math.inf and imports it.

Program structure¶

A file has five parts, in this order. Each part is optional.

Imports, written as in Python: import a.b, from a import b, c.
extends Base, which makes the class class Solution(Base).
Top-level assignments before the first def. They become module-level Python, above the class.
The defs. Each one becomes a method of Solution; self is added.
A script: every statement after the defs. It runs after the class. A def in the script is a plain function, not a method.

Functions¶

def name(p: T, q: U) -> R
  body

The last line of a body is its return value. If the last statement is an if, the last line of each arm is returned. return also works.

A nested def that assigns a name bound by an enclosing def gets a nonlocal declaration automatically.

Types¶

[T]          # list[T]
{T}          # set[T]
{K: V}       # dict[K, V]
(A, B)       # tuple[A, B]
T?           # Optional[T]
A -> B       # Callable[[A], B]
(A, B) -> C  # Callable[[A, B], C]
char         # str
none         # None

Any other name passes through unchanged.

Grid parameters¶

A parameter of a top-level def whose type is [[T]] is wrapped in Grid. A Grid takes a cell pair as one index: mat[p] is mat[i][j] when p = (i, j), for reading and for writing. Only such parameters are wrapped. A table built inside the function, for example with like, is a plain list of lists.

Statements¶

Loops¶

for x in xs       # x is each item
for (a, b) in ps  # unpacks each pair
for i, x in xs    # enumerate: i is the index, x the item
while cond        # as in Python

for a, b in xs without brackets always means enumerate(xs). To unpack pairs, write the brackets.

Push and pop¶

stack <- x  # stack.append(x)
stack .     # stack.pop()

A . followed by a name is attribute access. A . followed by anything else is a pop.

Assignment¶

Python assignment and every augmented operator (+=, //=, <<=, ...). Chained assignment a = b = 0 works.

Other statements¶

if/elif/else, break, continue, pass, del, assert, return, as in Python.

Expressions¶

Python expressions, with these additions.

Calls without brackets¶

A call with one argument may drop its brackets. It binds tighter than any operator.

len xs - 1           # len(xs) - 1
print len xs         # print(len(xs))
set f y for y in xs  # set(f(y) for y in xs)

Ranges¶

lo..hi   # range(lo, hi + 1)
lo..<hi  # range(lo, hi)

Lambdas¶

A lambda may appear only as a call argument.

x -> x * 2       # lambda x: x * 2
(a, b) -> a + b  # a lambda that takes one pair and unpacks it

_ may be used more than once among the names: (_, r) -> r.

Folds¶

sum, max, min and count followed by for form a fold.

sum for x in xs: x * x
max from 0 for x in xs if x > 0: x
count for x in xs if x % 2 == 0

from e gives the starting value. For max and min it is also the value of a fold over nothing.
if cond skips items.
count counts the items for which the condition, and the value after : if there is one, are true.

A fold may take a block instead of : value. The block runs once per item, and its last line is the value folded in.

sum for p in scan(+, nums)
  got = cnt[p - k]
  cnt[p] += 1
  got

First true¶

first k in lo..hi if pred

The least k in the range for which pred is true. pred must be monotone: false, then true. It compiles to bisect_left with a key, so it runs in O(log n) evaluations of pred. If pred is never true the value is one past the end of the range.

Memoized functions¶

memo f(i, j) =
  | i == len(a) or j == len(b) -> 0
  | a[i] == b[j]               -> 1 + f(i + 1, j + 1)
  | else                       -> max(f(i + 1, j), f(i, j + 1))

Each case is | guard -> value, tried in order; | else -> matches everything. A one-line form memo f(x) = expr has no cases. The function is cached with functools.cache. A method that defines a memo runs on a thread with a 256 MB stack and a raised recursion limit, so recursion depth of 10^4 and beyond is safe.

Calls with special meaning¶

ceil(a / b)     # -(-(a) // (b)), exact integers
floor(a / b)    # (a) // (b)
sort(xs, by=f)  # sorted(xs, key=f)
scan(+, xs)     # accumulate(xs)
scan(*, xs)     # accumulate(xs, operator.mul)
scan(f, xs)     # accumulate(xs, f)
counter(xs)     # Counter(xs)

Helpers¶

A call to any of these names includes the helper's source in the output, so the Python runs on LeetCode unchanged.

cells(grid)                           # every (i, j), row by row
cells(grid, start=1)                  # only i, j >= 1
nbrs(grid, i, j)                      # on-grid neighbours: up, left, right, down
nbrs(grid, p)                         # the same, with the cell as one pair
table(m, n, fill=0)                   # m rows of n cells
like(grid, fill=inf)                  # a new table with the shape of grid
pairs(n)                              # every (i, j) with 0 <= i < j < n
levels(q)                             # pops deque q level by level, yields (d, item)
levels(q, grouped=True)               # yields (d, items), one level at a time
adjacency(edges)                      # adjacency lists; also n, reverse, directed, weighted
indegrees(edges)                      # in-degree of every vertex; same flags
components(land, p -> nbrs(grid, p))  # connected components
graph(vs, edges)                      # a weighted graph; an edge (u, v) has weight 1
dijkstra(g, src)                      # shortest distance to every vertex, inf if unreachable
in_bounds(grid, i, j)                 # True if (i, j) is a cell of grid
in_bounds(grid, p)                    # the same, with the cell as one pair
edges(grid)                           # every (i, j) on the border, row by row
is_edge(grid, i, j)                   # True if (i, j) is on the first or last row or column
grid_bfs(grid, sources)               # steps from the nearest source to every cell, -1 if none
grid_bfs(grid, sources, ok=v -> v == 0)  # enters a cell only if ok(grid[cell]); also dirs
triples(n)                            # every (i, j, k) with 0 <= i < j < k < n
ceil_div(a, b)                        # (a + b - 1) // b
first_true(lo, hi, ok)                # smallest x in lo..hi with ok(x); hi + 1 if none
last_true(lo, hi, ok)                 # largest x in lo..hi with ok(x); lo - 1 if none
first_false(lo, hi, ok)               # smallest x in lo..hi without ok(x); hi + 1 if none
last_false(lo, hi, ok)                # largest x in lo..hi without ok(x); lo - 1 if none
min_chunks(nums, cap)                 # fewest runs of nums each summing to at most cap; inf if one exceeds cap
Multiset()                            # a Counter that drops a key when its count reaches 0

Items pushed onto q while levels(q) runs are yielded at the next level.

cells, nbrs, table, like, pairs, levels, adjacency, indegrees, in_bounds, is_edge, edges, grid_bfs, triples, ceil_div, first_true, last_true, first_false, last_false, min_chunks, Multiset match the harness builtins of the same names in utils/harness/. mu/test_mu.py checks that the two agree.