mu 0.11¶

mu is a small language that transpiles to Python. python -m mulang turns a mu file into Python that runs on its own, on LeetCode too: the classes and functions it defines, the imports it needs, and the source of every helper it calls. The helpers below are the LeetCode profile's; a project registers its own (see the README). This document describes version 0.11. Earlier versions: 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.10.

Changes since 0.10¶

A prime marks a name to bind again on a value side of =. In M = max(p - m', M) = min(m, p) the side max(p - m', M) binds m from min(m, p), though m is already bound. Until 0.10 that line was an error: the side bound no new name.
A parameter may have a default: def max_diff(xs: [int], by=x -> x, reverse: bool=false) -> [int]. Until 0.10 a def took names and types only. py2mu now translates Python defaults instead of refusing them.

Changes since 0.9¶

> and < mark the index in a loop target, and say which way it runs. for >i, x in xs is for i, x in enumerate(xs), and for >i in xs is for i in range(len(xs)). for <i in xs is for i in range(len(xs) - 1, -1, -1), and for <i, x in xs pairs that index with x = xs[i], so the loop walks xs from its last item to its first. The mark goes on the first name only, in a loop, a comprehension or a fold. Until 0.9 the mark was ~, which reads as a complement everywhere else; the transpiler refuses ~ in a target and says so.
c ? a : b is C's conditional: a when c, else b. It is Python's a if c else b, which still works. It nests to the right, so x > 0 ? 'R' : x < 0 ? 'L' : '.' is three cases in one line. A fold's if may not hold one unbracketed, since its : would sit beside the fold's. py2mu writes this form for a Python conditional.

Changes since 0.8¶

~ marks the index in a loop target. for ~i, x in xs is for i, x in enumerate(xs), and for ~i in xs is for i in range(len(xs)). The mark goes on the first name only. Until 0.8 a two-name target without brackets, for i, x in xs, enumerated on its own; now it unpacks each item, as in Python, so for a, b in edges and for (a, b) in edges are the same loop. The brackets are no longer needed, and the transpiler says so when ~ sits on a later name or more than one name follows ~i,.

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

A parameter may have a default, written after its name or its type with =, as in a call:

def max_diff(xs: [int], by=x -> x, reverse: bool=false) -> [int]

compiles to

def max_diff(xs: list[int], by=lambda x: x, reverse: bool = False) -> list[int]:

The default may be any call argument, a lambda among them. Once one parameter has a default, every parameter after it needs one too.

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 (a, b) in ps is the same
for >i, x in xs   # enumerate: i is the index, x the item
for >i in xs      # i runs over the indices of xs: range(len(xs))
for <i, x in xs   # the same pair, from the last item to the first
for <i in xs      # i runs down the indices of xs: range(len(xs) - 1, -1, -1)
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.

> marks the index, and < marks it running from the end. Either goes on the first name of the target, and the rest of the target is one pattern: for >i, (u, v) in edges. A target without a mark unpacks each item, as in Python. The same target works in a comprehension and in a fold: sum for >i, x in xs: i * x.

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 that is already bound can be bound again on a value side: write a prime after it, m'. The prime says that the side binds this name from the value on its right:

# 121. Best Time to Buy and Sell Stock
class Solution
  def maxProfit(prices: [int]) -> int
    ret M, m = 0, inf
    for p in prices
      M = max(p - m', M) = min(m, p)

compiles to

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        M, m = 0, inf
        for p in prices:
            m = min(m, p)
            M = max(p - m, M)
        return M

With prices = [7, 1, 5, 3, 6, 4], m is the lowest price so far, M is the best profit, and the answer is 5. A prime is a ' directly after a letter, a digit or _, with no space. A ' anywhere else starts a string, so in s' + 'x' the first ' is a prime and 'x' is a string. f', r' and b' start a string, as in Python, unless that name is bound and the line reads as a prime; then it is a prime. A prime on a name that is not bound yet, on a target, or outside a value side of = is an error.

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.

Conditional¶

c ? a : b is a when c, else b: Python's a if c else b, which mu also accepts. The ? binds last, so x > 0 ? 'R' : 'L' tests x > 0. It nests to the right.

x > 0 ? 'R' : x < 0 ? 'L' : '.'   # 'R' if x > 0 else 'L' if x < 0 else '.'
d = {k: v ? 1 : 0}                # the dict's colon comes first
sum for x in xs: x > 0 ? x : -x   # the fold's colon comes first

A fold's if may not hold a bare ? :; bracket it: count for x in xs if (x ? a : b).

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 by a pasted cache helper, a dict keyed on the arguments, written in Python rather than taken from functools so that the C recursion limit of Python 3.12 and 3.13 does not cut a deep recursion short. 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 a name the profile's library registers includes the helper's source in the output, after the helpers it depends on, with its imports at the top of the file, so the Python runs on its own. A name the file binds itself is the file's; a helper passed by name, sort(ds, by=even), counts as a call. Which names those are, and what they do, is the profile's to document: the LeetCode profile lists its library in the leet repo's mu/HELPERS.md.

The language's own helpers are Grid, the list of rows a [[t]] parameter arrives as, which also takes a (row, col) pair as an index, and deep, which runs a memo on a 256 MB stack.