mu 0.14¶
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.14. Earlier versions: 0.1, 0.2,
0.3, 0.4, 0.5, 0.6,
0.7, 0.8, 0.9, 0.10,
0.11, 0.12, 0.13.
Changes since 0.13¶
by=is the keyword ofsort,max,min,nlargest,nsmallestandgroupby, Python'skey=. A value that is not a function is indexed:max(a, b, by=values)is the one of a and b with the larger entry in values, andsort(nodes, by=depth)orders the nodes by their entries in depth. See Keyed calls.lo..<hi by sandlo..hi by sare ranges with a step,range(lo, hi, s)andrange(lo, hi + 1, s);hi..lo by -1counts down. See Ranges.filter(xs, by=f)is the list of the items of xs that f holds for,list(filter(f, xs)), the sequence first as insort(xs, by=f); itsby=is a key as above, sofilter(0..<n, by=flags)is the indices whose flag holds. See Calls with special meaning.memobefore a block lambda caches it:memo {n ->opens the block,memo {n -> expr}is the one-line form. The hidden def is cached as amemostatement is, and the def that holds it runs on the deep stack.muinside is the cached function, so each argument is computed once. See Block lambdas.- The body of a block lambda may be a case list,
| guard -> valuelines as under amemo, with or withoutmemobefore the{. The case list is the whole body. See Block lambdas.
Changes since 0.12¶
- A lambda may take a block.
{p ->ends the line, the body is indented under it, and a}at the indent of the opening line closes it; the expression continues after the}. Inside the bracesmuis the lambda itself, so a body recurses with no name. On one line,{n -> n ? 1 + max(mu(n.left), mu(n.right)) : 0}(root). See Block lambdas. - A block lambda compiles to a def with a hidden name, placed before the statement that holds it. In a fold's block it is built before the fold too, unless its body reads a name that block binds per item; then it is built per item. One in a one-line fold or a comprehension may not read the loop's variable except as a parameter.
- A fold with a block may be the value of
=orret:res = count for c in cells(grid, eq=0)then the block. See Folds. first k in lo..hion a line of its own may take a block: the test is its last line. See First true.
Changes since 0.11¶
a, b, c = 0gives 0 to each name, andres, path = []..gives each name its own[]: the count of dots is the count of copies. See One value for several names.- A number directly before a name or a
(multiplies:2nis2 * n,1 + 8nis1 + 8 * n. See A number before a name. - A dict that mu makes gives its keys as attributes:
a = dict(a=1), thena.ais 1. See Dicts. mu file.muruns the file;mu --py file.muprints the Python. See Running.from m import a, bimports from a mu modulem.mu. See Modules.A | Bis a union type:def to_digits(num: int | str) -> [int].- A Python generic passes through as Python writes it,
...and the parameter list ofCallableincluded:Tuple[Cell, ...],Callable[[Any], bool]. Elsewhere in a generic,[T]is still mu's list:dict[str, [int]]isdict[str, list[int]]. (*e, 1): a tuple in brackets takes a starred item.- A name that a Python import binds is never pasted from the library,
and a relative import (
from .grid import table) stays Python. - A multi-line docstring takes the Python indent of its body.
mu now writes the Python of a numeric library, PyTorch code among it, and not only a LeetCode solution. Until 0.11 each of these was an error.
with, andtrywithexcept,elseandfinally, are blocks with no colon:with torch.no_grad(),except OSError as e.async def f()is a coroutine, andawait ewaits for e inside one:xs = await asyncio.gather(*[get(k) for k in keys]). The last line of an async def is returned, as in a plain def. Until 0.12asyncwas an error.raise,raise E,raise E from e,globalandnonlocalare statements. Until 0.11raise ValueError(x)compiled to a call of a function namedraise.- A def may take
*args,**kwargsand parameters named only in the call, after*or*args; those need no default. A call may pass**d, and a dict may unpack one,{**d, 'k': 1}. @multiplies matrices, and@=too. A@at the start of a line is still a decorator....is Python's Ellipsis:x[..., :3]. A subscript takes several slices apart by commas:x[:, none, -1].name: T = vis a typed assignment, andname: Ta field, as in a dataclass. T is a mu type.- A type may be dotted,
torch.Tensor, or quoted,"GPT". a, *rest = xsunpacks into a list,(n := len(xs))binds n in an expression, and0xff,0o7and0b1are numbers.- Strings written side by side are one string,
"a" "b", as in Python. class Name extends A, Bgives the class several bases.- The formatter keeps the line breaks inside brackets when the joined line would pass 88 characters or the brackets hold a comment, indenting each line one step per open bracket. Until 0.11 it joined every bracketed expression onto one line, and a comment inside one swallowed the code after it. A short one is still joined, without its trailing comma.
- The formatter keeps one-line defs written in a row together,
def __neg__(): self * -1, as Python style does. - A method under
@staticmethodtakes noself, and one under@classmethodtakescls. Until 0.11 both were givenself. - A file's parts may interleave. An assignment after a line of the script stays in its place in the script; until 0.11 every assignment before the first class or def moved above the classes, ahead of script lines written before it.
Changes since 0.10¶
-
A prime marks a name to bind again on a value side of
=. InM = max(p - m', M) = min(m, p)the sidemax(p - m', M)bindsmfrommin(m, p), thoughmis 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 xsisfor i, x in enumerate(xs), andfor >i in xsisfor i in range(len(xs)).for <i in xsisfor i in range(len(xs) - 1, -1, -1), andfor <i, x in xspairs that index withx = xs[i], so the loop walksxsfrom 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 : bis C's conditional: a when c, else b. It is Python'sa if c else b, which still works. It nests to the right, sox > 0 ? 'R' : x < 0 ? 'L' : '.'is three cases in one line. A fold'sifmay 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 xsisfor i, x in enumerate(xs), andfor ~i in xsisfor 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, sofor a, b in edgesandfor (a, b) in edgesare 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:selfis added to its parameters, and the body reads and calls the object throughself, as in Python. Until 0.7 every top-level def was a method of an implicitclass 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 Basegives the class a base class. The top-levelextends Baseline 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 aspairs(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 foldsfor i in range(n): for j in range(i)into it. -
x or d if vis x, or d when x equals v.dp[n] or -1 if infreads "dp[n], or -1 if it is inf". x is evaluated once. -
A
defor amemomay have decorators:@flines above it, as in Python.@as_listis a helper. It makes adefthat yields return the list of its yields. -
yieldis a statement:yield x,yield a, b,yield from xs, andyieldalone. -
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 = pairassigns 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¶
mu file.mu a b # run the file, with a and b in sys.argv
mu --py file.mu # print the Python
mu --fmt file.mu # print the file, formatted
mu - # read from standard input
mu file.mu runs the file as python file.py runs a Python file: a
traceback starts at the file and shows its mu lines.
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,randb. true,falseandnoneareTrue,FalseandNone.infismath.infand 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. An import from a mu module is described in Modules. - Top-level assignments before the first
classordef, and before any other statement. They become module-level Python, above the classes. - The classes and defs, in the order written. A
defdirectly under aclassis a method. A top-leveldefis a plain function. - A script: every statement after the classes and defs. It runs after them. Once a script line has been written, the classes, defs and assignments that follow are lines of the script, and run in their turn, as in a Python file.
Modules¶
A mu file is a module. from lib.nums import evens, lcm imports from
lib/nums.mu when that file is found; else the line is a Python import.
mu looks for the file in this order:
- the directory of the file that imports,
- the working directory,
- each directory in
$MUPATH, - each directory a profile adds with
mulang.mu_path(dir).
The import line is not in the Python. The defs, classes and constants of the module that the file uses are pasted in, with what they use and the imports they need, as a library helper is pasted. The Python therefore needs no mu at run time. The script of the module (its asserts and prints under the defs) is not part of the module, so a module can hold its own tests.
An import from a mu module names each def: import lib.nums,
from lib.nums import * and as are errors. An import cycle is an error.
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, and extends A, B gives two
bases. A class may not hold a class.
A typed assignment in a class body is a field, as in Python, so a dataclass is written out:
@dataclass
class GPTConfig
block_size: int = 1024
n_layer: int = 12
dropout: float = 0.0
A def under @staticmethod takes no self, and one under @classmethod
takes the class as cls.
__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, up to a
*.
*args takes the rest of the arguments as a tuple and **kwargs the
named ones as a dict. A parameter after *args, or after a bare *, is
named in the call, and needs no default:
def generate(idx, max_new_tokens: int, *, temperature=1.0, top_k=none)
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 # a.B, a dotted name
"B" # "B", a class defined further down
A -> B # Callable[[A], B]
(A, B) -> C # Callable[[A, B], C]
A | B # A | B, a union
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.
Typed assignment¶
n: int = 0 # n: int = 0
x: torch.Tensor # declares x, assigns nothing
The type is a mu type: best: [int]? = none is
best: Optional[list[int]] = None. A typed assignment before the first
class or def is a module-level line, like any assignment there.
Unpacking¶
first, *rest = xs binds the first item to first and the rest, as a
list, to rest, as in Python. A * may also go in a return or a yield:
return *xs, n.
One value for several names¶
When the right side of = is one number, inf, true, false or
none, each name on the left gets that value. Python cannot unpack these
values, so the line has no other meaning:
a, b, c = 0 # a, b, c = 0, 0, 0
lo, hi = -inf # lo, hi = -inf, -inf
An item on the right side that ends in dots is repeated, one copy per
dot. .. gives 2 copies, ... gives 3, .... gives 4:
a, b, c, d, e = 0..., 1.. # a, b, c, d, e = 0, 0, 0, 1, 1
x, y = 1, 2
a, b, c, d = 2x.., 2y.. # a, b, c, d = 2 * x, 2 * x, 2 * y, 2 * y
res, path, used = [].., table(len(nums), fill=false)
mu writes the item again for each copy, so each copy is a new value:
res and path are two lists, not one. The copies must give one value
per name, else mu stops with an error such as 5 names, 4 values. A
repeat is only on the right side of a plain =: not in a chained =,
not with a starred name, not in a return. In a ret line the first
name is still the return value: ret res, path = []...
.. before a comma or the end of the line is a repeat. Anywhere else it
is a range, 0..n.
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.
With¶
with torch.no_grad()
logits = model(idx)
with open(path) as f, ctx
data = f.read()
Python's with, with no colon. Each item may bind its value with as.
When a with is the last line of a def, the last line of its block is
returned, as for an if.
Try¶
try
import torch
except ImportError as e
raise SystemExit("no torch") from e
else
print 'ok'
finally
done = true
Python's try, with each header on its own line and no colon. There may
be several except blocks, each with a type or none, then an else,
then a finally. A try needs an except or a finally. As the last
line of a def, a try returns the last line of each except and of its
else, and of its own block when it has no else.
Raise, global, nonlocal¶
raise # re-raises the exception being handled
raise ValueError(f"bad {x}")
raise RuntimeError("no") from e
global iter_num
nonlocal count
A nested def that assigns a name of its enclosing def still gets its
nonlocal on its own; write one only to say it.
Other statements¶
if/elif/else, break, continue, pass, del, assert, return,
as in Python.
Expressions¶
Python expressions, with these additions.
Python operators¶
@ multiplies matrices, x @ w, and @= multiplies in place. ... is
the Ellipsis. A subscript takes several slices or indices apart by commas,
as in Python:
att = q @ k.transpose(-2, -1) # q @ k.transpose(-2, -1)
x[..., :half] # every leading axis, the first half of the last
logits[:, -1, :] # the last position of each row
(n := len(xs)) binds n and is its value, as in Python. 0xff, 0o17
and 0b101 are numbers. Two strings side by side are one,
"a" "b", so a long message may be split over lines inside brackets.
A call may pass *xs and **d, and a dict may unpack **d:
model = GPT(GPTConfig(**model_args))
cfg = {**defaults, 'lr': 3e-4}
A number before a name¶
A number directly before a name or a (, with no space, multiplies:
2n # 2 * n
start + 2i # start + 2 * i
sqrt(1 + 8n) # sqrt(1 + 8 * n)
k * (2n + k - 1) # k * (2 * n + k - 1)
2(a + b) # 2 * (a + b)
The product is one operand. ** binds tighter, as in maths, so 2x**2 is
2 * x ** 2, and 1/2x is 1 / (2 * x). A name after the number keeps
its subscripts and attributes: 2xs[i] is 2 * xs[i].
2 n, with a space, is an error. A name that starts with e or E after
a number is an error, because 2e5 is the number 200000.0: write 2 * e.
After 0, a name that starts with x, b or o is an error for the same
reason: 0x1f is a number.
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)
Dicts¶
A dict that mu makes is a Rec: a dict that also gives its keys as
attributes. A dict(...) call, a brace literal with k: v or **d
items, an empty {} and a dict comprehension each make one. The
transpiler pastes the Rec class into the Python.
a = dict(a=1) # Rec(a=1)
b = {'x': 2} # Rec({'x': 2})
c = {} # Rec()
d = {k: k * k for k in xs} # Rec({k: k * k for k in xs})
a.a reads the key a, a.b = 2 sets the key b, and del a.b
removes it. A key that is not in the dict raises AttributeError, so
hasattr(a, 'q') is false. A dict method has priority over a key with the
same name: a.items is the method. A Rec prints as a dict does,
{'a': 1}. A default dict, a Counter and a dict that Python code makes
stay plain dicts.
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)
lo..<hi by s # range(lo, hi, s)
lo..hi by s # range(lo, hi + 1, s)
hi..lo by -s # range(hi, lo - 1, -s)
by s is the step. An inclusive end moves one past hi the way the step
goes. A literal step says which way at compile time; any other step is
tested at run time, range(lo, hi + (1 if s > 0 else -1), s).
# Sieve of Eratosthenes
def primes(n: int) -> [int]
flags = table(n, fill=1)
flags[0] = flags[1] = 0
for i in 2..<n
if flags[i]
for j in 2i..<n by i
flags[j] = 0
filter(0..<n, by=flags)
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
Block lambdas¶
A lambda in braces may have a body of several lines. {p -> ends the
line, the body is indented under it, and a } at the indent of the
opening line closes it; what follows the } on that line continues the
expression. The last line of the body is the value. Inside the braces,
mu is the lambda itself.
The head may also stand on the line under the {, and the body one step
under the head. Both forms below are the one above:
res = count for c in cells(grid, eq=0)
{c ->
grid[c] = 1
all([mu(n) for n in nbrs(grid, c, eq=0)] + [not is_edge(grid, *c)])
}(c)
res = count for c in cells(grid, eq=0)
{
(c) ->
grid[c] = 1
all([mu(n) for n in nbrs(grid, c, eq=0)] + [not is_edge(grid, *c)])
}(c)
# Count Islands With Total Value Divisible by K
def countIslands(grid: [[int]], k: int) -> int
sum for p in cells(grid, gt=0): {p ->
total, grid[p] = grid[p], -1
total + sum for q in nbrs(grid, p, gt=0): mu(q)
}(p) % k == 0
On one line the body is an expression, so a recursion is one expression:
# 104. Maximum Depth of Binary Tree
def maxDepth(root: TreeNode?) -> int
{n -> n ? 1 + max(mu(n.left), mu(n.right)) : 0}(root)
The parameters are as written: {(r, c) -> takes two arguments, {->
takes none. mu outside braces is an error.
memo before the { caches the lambda, as a memo statement
caches a named function: one call per distinct argument, and the def that
holds it runs on the deep stack. mu is then the cached function. Anything
else after memo but a name or a {n -> is refused.
# Longest Path From Zero
def longestPath(G: {int: [int]}) -> int
memo {
n ->
max from 0 for v in G[n]: 1 + mu(v)
}(0)
The body may be a case list, | guard -> value lines tried in order with
| else -> matching everything, the same as under a
memo. The case list is then the whole body: a
statement after it is refused. Both forms below are the one above.
def longestPath(G: {int: [int]}) -> int
memo {n ->
| not G[n] -> 0
| else -> max for v in G[n]: 1 + mu(v)
}(0)
# 509. Fibonacci Number
def fib(n: int) -> int
{k ->
| k < 2 -> k
| else -> mu(k - 1) + mu(k - 2)
}(n)
A block lambda compiles to a def with a hidden name, placed just before
the statement that holds it, and mu to that name. A block lambda written
in a fold's block is placed before the fold as well, built once, unless
its body reads a name the block binds per item: then it stays in the
block, built per item, where that name is bound. Below, the body reads
seen, which the block sets for each start.
# 2101. Detonate the Maximum Bombs
def maximumDetonation(bombs: [[int]]) -> int
G = {i: [j for >j, (x2, y2, _) in bombs if j != i and (x - x2) ** 2 + (y - y2) ** 2 <= r * r] for >i, (x, y, r) in bombs}
max for i in 0..<len bombs
seen = set()
{j ->
seen.add(j)
1 + sum for k in G[j] if k not in seen: mu(k)
}(i)
A def placed before a one-line fold or a comprehension cannot see the
loop's variable, so a block in one that reads it is refused:
the mu block reads p from the loop around it; take p as a parameter.
A body that assigns a name of the enclosing def gets nonlocal, as any
nested def does:
# 543. Diameter of Binary Tree
def diameterOfBinaryTree(root: TreeNode?) -> int
ret best = 0
{n ->
if not n
return 0
l, r = mu(n.left), mu(n.right)
best = max(best, l + r)
1 + max(l, r)
}(root)
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 egives the starting value. Formaxandminit is also the value of a fold over nothing.if condskips items.countcounts the items for which the condition, and the value after:if there is one, are true.- A fold on one line is a list comprehension passed to
sum,maxormin, not a generator. Amemowhose cases fold over its own calls then recurses as deep as the 256 MB stack allows on every Python, 3.12 and 3.13 too. A generator pulled byminsends each level through C, and those two versions stop that short of depth 10000.
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
A fold with a block stands on a line of its own, or is the value of =
or ret: res = count for c in cells(grid, eq=0) then the block.
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.
When first k in lo..hi stands on a line of its own, the test may be a
block under it. The block runs once per probe, and its last line is the
test. It compiles to a def with a hidden name, passed as the key.
# 1011. Capacity To Ship Packages Within D Days
def shipWithinDays(weights: [int], days: int) -> int
first cap in max weights..sum weights
used, total = 1, 0
for w in weights
if total + w > cap
used, total = used + 1, 0
total += w
used <= days
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))
Keyed calls¶
sort, max, min, nlargest, nsmallest and groupby take by=,
which is Python's key=. A lambda, a block lambda, a call such as
cmp_to_key(f) or a function passed by name is the key as it is. Any
other value is indexed by the item, so a list, a dict or a string compares
the items by their entries in it.
max(a, b, by=values) # max(a, b, key=values.__getitem__): the index with the larger value
min(nodes, by=depth) # the node with the smallest depth
sort(nodes, by=depth) # sorted(nodes, key=depth.__getitem__)
sort(xs, by=x -> -x) # sorted(xs, key=lambda x: -x)
sort(words, by=len) # sorted(words, key=len)
A name the transpiler cannot tell a function from, a parameter or a local,
goes through a three-line helper, _by, pasted with the output: a
function passes through it, anything else is indexed.
class Solution
def findRoot(n: int, edges: [[int]], values: str) -> int
child = [false] * n
for a, b in edges
child[max(a, b, by=values)] = true
child.index(false)
Calls with special meaning¶
ceil(a / b) # -(-(a) // (b)), exact integers
floor(a / b) # (a) // (b)
sort(xs, by=f) # sorted(xs, key=f), see Keyed calls
filter(xs, by=f) # list(filter(f, xs)), the items f holds for; by= as in Keyed calls
scan(+, xs) # accumulate(xs)
scan(*, xs) # accumulate(xs, operator.mul)
scan(f, xs) # accumulate(xs, f)
scan(max, xs, reverse=True) # reversed(list(accumulate(xs[::-1], max))), the fold from the right
scan(f, xs, type=list) # list(accumulate(xs, f)); type=tuple builds a tuple
scan(f, xs, reverse=True, type=list) # list(accumulate(xs[::-1], f))[::-1]
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,
deep, which runs a memo on a 256 MB stack, and _by, the key of a
by= that is not a known function.