mu 0.6¶

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.6. Earlier versions: 0.1, 0.2, 0.3, 0.4, 0.5.

Changes since 0.5¶

Four new helpers: to_digits and to_int turn a number into its list of digits and back, in any base (base=2 for bits); even and odd test parity.
scan(f, xs, reverse=True) folds from the right: scan(max, xs, reverse=True) is the running max of every suffix, as a list.
memo has a block form. memo f(i, j) with no = opens a body like a def. The function is cached and runs on the deep stack, as the case form does.
A fold may name no variable, as a loop already could: sum for xs: _ * 2. In both, the body reads the item as _.
{:list} is a defaultdict: {:list} for defaultdict(list), {:() -> [0, 0]} for defaultdict(lambda: [0, 0]).
The VS Code extension debugs current.mu directly: F5 in a mu file transpiles it and runs the Python debugger behind a proxy that reports every line as its mu line, so breakpoints, the current line and stepping all happen in the mu file.

An example¶

# 2231. Largest Number After Digit Swaps by Parity
def largestInteger(num: int) -> int
  ds = to_digits num
  by = {r: sorted(d for d in ds if d % 2 == r) for r in 0..1}
  to_int([by[d % 2] . for d in ds])

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

In VS Code, F5 in a mu file runs mu: Debug current.mu. It writes .mu_current.py and .mu_current.map.json, a map from each Python line to the mu line it came from, and starts debugpy on the Python behind a proxy (mu/vscode/adapter.js) that translates the protocol both ways: a breakpoint set in current.mu lands on the first Python line of that mu line, and every stack frame in the transpiled file is reported at its mu line, in current.mu. A step that lands on another Python line of the same mu line is repeated, so one step is one mu line. A breakpoint on a comment or blank line moves down to the next line of code. Frames inside a pasted helper stay in .mu_current.py, which is where that code is.

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.

A line of the body may start with ret. It assigns a variable, and that variable is the return value: the function returns it after its last line, and a bare return returns it too. A return with a value still returns that value. In ret res, k = [], 0 the first name, res, is the return value. A body has at most one ret line, and it cannot be inside a loop or an if.

# 1720. Decode XORed Array
def decode(encoded: [int], first: int) -> [int]
  ret res = [first]
  for i in range len encoded
    res <- encoded[i] ^ res[i]

ret is a keyword only at the start of a line and before name = or name,. Anywhere else it is an ordinary name, so ret = 0 is a plain assignment.

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
for xs            # runs once per item of xs, names no variable
for 0..<n         # so this runs n times
while cond        # as in Python

A loop may end with an else block, which runs when the loop finishes without break, as in Python.

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

A for with no in compiles to for _ in xs, so the body reads the item as _. _ is an ordinary Python name. In nested loops that name no variable, _ is the item of the innermost one; name the outer loop's variable to read its item.

for ps
  s += _[0]  # the first part of each pair

Push and pop¶

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

Both work on a heap too, because a heap has an append method that pushes.

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.

A target of = may be wrapped in a one-argument function. The name is assigned, then passed through the function:

int(id), ev, int(t) = log.split ':'

compiles to

id, ev, t = log.split(':')
id, t = int(id), int(t)

With "0:start:3", id is 0, ev is "start" and t is 3.

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)

Default dicts¶

A brace literal that starts with a colon is a defaultdict. What follows the colon is the factory: a name, or a lambda that takes nothing.

{:list}          # defaultdict(list)
{:int}           # defaultdict(int)
{:() -> [0, 0]}  # defaultdict(lambda: [0, 0])

Ranges¶

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

Lambdas¶

A lambda may appear only as a call argument or as the value of an assignment.

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

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

gain = (p, t) -> (p + 1) / (t + 1) - p / t

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 name no variable. Then the item is _, as in a loop with no in.

sum for node.children.values(): _.val["dur"]  # sum(_.val["dur"] for _ in ...)
count for xs if _ > 0

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.

When the value is not one expression per case, write memo f(i, j) with no = and give it a body, as for a def. The body may loop, collect and return. It is cached and runs on the deep stack the same way. It cannot have a ret line.

# 2684. Maximum Number of Moves in a Grid
def maxMoves(grid: [[int]]) -> int
  memo moves(i, j)
    m = []
    for (ni, nj) in nbrs(grid, i, j, dirs=[(-1, 1), (0, 1), (1, 1)])
      if grid[ni][nj] > grid[i][j]
        m <- moves(ni, nj)
    return max(m) + 1 if m else 0
  return max(moves(i, 0) for i in 0..<len(grid))

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)
scan(max, xs, reverse=True)   # list(accumulate(xs[::-1], max))[::-1], the fold from the right
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
cells(grid, eq=0)                     # only cells holding 0
cells(grid, gte=k)                    # only cells holding k or more; also lt, lte, gt
nbrs(grid, i, j)                      # on-grid neighbours: up, left, right, down
nbrs(grid, p)                         # the same, with the cell as one pair
nbrs(grid, p, eq=inf)                 # only neighbours holding inf; same comparisons
table(m, n, fill=0)                   # m rows of n cells
like(grid, fill=inf)                  # a new table with the shape of grid
shape(grid)                           # (rows, cols); shape(a, b) is (len(a), len(b))
shape(grid, last_index=True)          # the index of the last cell
put(grid, at, v)                      # grid[i][j] = v for every (i, j) in at
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
levels(q, grid, seen, gte=k)          # drops items seen before or whose value fails
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
heap(xs)                              # a min-heap of xs
heap(xs, type=max)                    # a max-heap of xs
to_digits(num)                        # the digits of an int or str, most significant first
to_digits(num, reverse=True)          # least significant first, digit i is the 10**i place
to_int(ds)                            # the int with these digits, most significant first
to_int(ds, reverse=True)              # the inverse of to_digits(num, reverse=True)
to_digits(num, base=2)                # the bits of num, most significant first; any base works
to_int(bits, base=2)                  # the int with these bits; any base works
even(n)                               # n % 2 == 0
odd(n)                                # n % 2 == 1

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

A heap has push(x), pop(), peek() and len. Iterating over a heap gives its items in no particular order.

cells, nbrs, table, like, shape, put, pairs, levels, adjacency, indegrees, to_digits, to_int, even, odd, 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.