mu 0.8¶

mu is a small language for LeetCode. mu/mu.py transpiles a mu file to Python that LeetCode accepts: the classes and functions it defines, the imports it needs, and the source of every helper it calls. This document describes version 0.8. Earlier versions: 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7.

Changes since 0.7¶

A class is written out: class Solution, then its defs indented under it. Each def directly under a class is a method: self is added to its parameters, and the body reads and calls the object through self, as in Python. Until 0.7 every top-level def was a method of an implicit class Solution; now a top-level def is a plain function. A file may hold several classes and functions, in any order, so a design problem (class LRUCache), a drill with a given class, and a Python drill are written in mu too.
class Name extends Base gives the class a base class. The top-level extends Base line of 0.7 is gone; the transpiler says so when it meets one.
__init__, and a def typed -> none, return nothing: their last line is not returned.
A decorator (@f) may go above a class as well as a def or a memo.

Changes since 0.6¶

pairs(n, back=True) yields the same pairs as pairs(n), grouped by the later index: for each j in turn, every (i, j) with i < j. That is the order of a 1-D dp where cell j looks back at every earlier cell. The transpiler folds for i in range(n): for j in range(i) into it.
x or d if v is x, or d when x equals v. dp[n] or -1 if inf reads "dp[n], or -1 if it is inf". x is evaluated once.
A def or a memo may have decorators: @f lines above it, as in Python. @as_list is a helper. It makes a def that yields return the list of its yields.
yield is a statement: yield x, yield a, b, yield from xs, and yield alone.
A lambda may be a dict value: {'+': (a, b) -> a + b}.
The body of a lambda may be a push: x -> stack <- x.
A default dict may be filled where it is written: {:list: c <- i for i, c in s} is the dict of each character's indices.
The element of a comprehension may be a push: [pos[v] <- i for i, v in s].
A lambda may name no argument: -> _ * 2. The body reads its one argument as _, or the tuple of them when there are several: -> _[0] + _[1].
A side of = may be a value instead of a target: a * b = pair assigns a and b from pair, then is the value a * b. See Assignment.

An example¶

# 300. Longest Increasing Subsequence
class Solution
  def lengthOfLIS(nums: [int]) -> int
    dp = table(len(nums), fill = 1)
    for (j, i) in pairs(len(nums), back = True)
      if nums[j] < nums[i]
        dp[i] = max(dp[i], dp[j] + 1)
    max dp

A design problem is a class with a constructor and methods:

# 146. LRU Cache
class LRUCache
  def __init__(capacity: int)
    self.d = OrderedDict()
    self.cap = capacity

  def get(key: int) -> int
    if key not in self.d
      return -1
    self.d.move_to_end(key)
    self.d[key]

  def put(key: int, value: int) -> none
    self.d[key] = value
    self.d.move_to_end(key)
    if len(self.d) > self.cap
      self.d.popitem(last = false)

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

make runs current.mu in place. The Python it transpiles to is never written: it is compiled under the name current.mu, with every statement at the mu line it came from, and run. A failed assert, or any exception, reports the mu line and shows that line of current.mu. The imports and harness helpers the transpiler pastes in are compiled apart, as <mu helpers>, so a frame inside one is labelled as such and shows the helper's own line. On a terminal the traceback is coloured: the line number yellow, the source line bold, the exception red, and in a failed assert the left side (what the code gave) red and the right side (what the assert wanted) green. --no-color turns that off and --color forces it. python mu/session.py run FILE.mu (the mu FILE.mu command) runs any mu file the same way, on its own.

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.

The same extension answers the editor's questions about a mu file through mu/ide.py. Hovering a name shows its type, written as a mu type, or, for a helper, its lines from this document. Completion lists the names in scope, the keywords and the helpers; after a dot, the attributes of the value. Go to definition jumps to the mu line that binds the name, to the class it was imported from, or to a helper's source in utils/harness/. Inside a call, the callee's signature is shown. The file is transpiled and Jedi answers on the Python; a line that does not parse yet is left out, so the rest of the file still answers.

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 four parts, in this order. Each part is optional.

Imports, written as in Python: import a.b, from a import b, c.
Top-level assignments before the first class or def. They become module-level Python, above the classes.
The classes and defs, in the order written. A def directly under a class is a method. A top-level def is a plain function.
A script: every statement after the classes and defs. It runs after them.

Classes¶

class Name
  def __init__(p: T)
    self.p = p

  def method(q: U) -> R
    body

class Name extends Base
  ...

A class holds defs, which are its methods, and assignments, which are its attributes. self is added to every method's parameters, and the body names the object as self, as in Python: self.p, self.other(x). A def nested inside a method is a plain function. extends Base makes class Name(Base); Base may be dotted. A class may not hold a class.

__init__ returns nothing, and so does any def typed -> none. Every other def returns its last line.

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
class Solution
  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.

Decorators¶

A line @f above a def, a memo or a class decorates it, as in Python. The expression after @ is any mu expression: a name, or a call such as @wraps(g). Several @ lines may be stacked. The one nearest the def is applied first. A decorator above a memo wraps the cached function.

@as_list is a helper. It runs a function that yields until it ends and returns the yields as a list. The function yields each answer when it finds it, and the caller receives the whole list.

# 78. Subsets
class Solution
  @as_list
  def subsets(nums: [int]) -> [[int]]
    for mask in 0..<(1 << len(nums))
      yield [x for i, x in nums if mask >> i & 1]

With nums = [1, 2] the masks are 0, 1, 2 and 3, the function yields [], [1], [2] and [1, 2], and subsets returns [[], [1], [2], [1, 2]].

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 method or 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.

Both may be the element of a comprehension. The comprehension is then a loop written on one line, and its value is not used.

[pos[v] <- i for i, v in s]   # [pos[v].append(i) for i, v in enumerate(s)]
[out <- st . for _ in 0..<2]  # [out.append(st.pop()) for _ in range(0, 2)]

With pos = {:list} and s = "egg", the first line leaves pos as {'e': [0], 'g': [1, 2]}.

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.

One conversion alone, int(a) = s, is also the value of the converted name when it is the last line of a block.

A side of = may be a value: an operation, a call, a comparison, anything Python could not assign to. The side binds its new names from the value on its right, then it is evaluated. One new name takes the whole value. Two or more unpack it, in the order they first appear.

def unequalPairs(nums: [int]) -> int
  a * b = counter(nums).values()

compiles to

a, b = Counter(nums).values()
return a * b

A name on such a side is read, not bound, in three cases: it is called, as int is in int(a) * b; something earlier in the file binds it (a parameter, an assignment, a loop, a def, an import); or it is a Python builtin, inf, or a helper. A name bound by an earlier line of this form does not count: it is bound again. A side with no new name is an error.

Sides chain from right to left. Each value side is the value for the side on its left, and a target on its left is assigned it:

best = max(best, area) = h * width = min(left, right)

compiles to

h = min(left, right)
area = h * width
best = max(best, area)

A name, a subscript, an attribute and a comma list are targets, as in Python: grid[r][c] = divmod(k, n) stores into grid. A ret line takes one plain assignment.

On a line that has a value side, a subscript or an attribute of a new name is a value side too, since there is nothing yet to store into:

sum(x[:3]) = x[::-1] = 0..10

compiles to

x = range(0, 10 + 1)
x = x[::-1]
return sum(x[:3])

and returns 27.

Yield¶

yield x         # yields x
yield a, b      # yields the pair (a, b)
yield from xs   # yields every item of xs
yield           # yields None

yield is a statement. A function whose body has one is a generator, as in Python. When the last line of a body is a yield, the function returns nothing after it.

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])

A second colon, then key op value and a for clause, fills the dict. For each item, op value is applied to the entry at key. The operator is a push or an augmented assignment.

{:list: c <- i for i, c in s}            # the indices of each character
{:set: b <- a for (a, b) in edges}       # a push onto a set adds
{:int: c += 1 for c in s}                # the count of each character
{:int: name += n for (name, n) in txs}   # the sum for each name
{:set: k |= xs for (k, xs) in groups}    # the union for each key

With s = "egg" the first is {'e': [0], 'g': [1, 2]} and the third is {'e': 1, 'g': 2}. The for clause is that of a comprehension: it may have an if, and there may be several.

A push adds to a set only when the factory is written set. With any other factory it appends.

Or if¶

x or d if v is x, or d when x equals v. x is evaluated once. There is no else; with an else the line is Python's conditional expression.

dp[n] or -1 if inf     # -1 if (_v := dp[n]) == inf else _v
t or -1 if inf         # -1 if t == inf else t
d[k] or "" if none     # "" if (_v := d[k]) == None else _v

Ranges¶

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

Lambdas¶

A lambda may appear only as a call argument, as the value of an assignment, or as a dict value. Its body is an expression or a push.

x -> x * 2       # lambda x: x * 2
(a, b) -> a + b  # takes a and b, or one pair that it unpacks
() -> []         # takes nothing
x -> stack <- x  # lambda x: stack.append(x)
-> _ * 2         # one argument, read as _
-> _[0] + _[1]   # several arguments, read as the tuple _

_ 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.

@as_list                              # above a def: its yields, returned as a list
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
put(grid, at, scan(+, xs))            # v may be an iterable: one item per cell, in the order of at
row(grid, i)                          # a copy of row i
col(grid, j)                          # a copy of column j, top to bottom
set_row(grid, i, v)                   # every cell of row i; v one value or an iterable
set_col(grid, j, v)                   # every cell of column j; v one value or an iterable
pairs(n)                              # every (i, j) with 0 <= i < j < n
pairs(n, back=True)                   # the same, grouped by j: cell j looks back at every i < j
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.

as_list, cells, nbrs, table, like, shape, put, row, col, set_row, set_col, 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.