►
From YouTube: RustFest Zürich 2017 - Impractical Macros by Alex Burka
Description
A whirlwind tour through a (macro_rules 1.0!) macro that interprets everyone’s favorite Turing tarpit, Brainfuck, completely at compile time. I’ll highlight various components such as number encoding, arithmetic, input/output and explain how they work.
This is not a macro tutorial. I’ll cover a few techniques that you might possibly be able to use in real code, such as how to set up a recursive macro with an accumulator, but I’ll be breezing through them to get to the fun stuff, like memory zippers and “Zermelo numbers” (a term I may have invented).
About Alex Burka:
Alex is a robotics graduate student at the University of Pennsylvania. He got into Rust by writing his research software (a hardware controller and web interface for a sensor suite), and continues to spend too much of his free time writing macros.
A
Okay,
I'm
Alex,
and
so
we
just
heard
about
the
way
right,
macros
that
you
would
want
to
use
and
so
I'm
going
to
talk
about
macros
that
you
would
never
want
to
use
so
I
figured
I
should
have
a
cat
on
my
slide,
but
this
would
be
a
more
relevant
kind
of
cat.
You
might
have
seen
this
April
Fool's
joke,
but
really
it's
this
cat
program,
so
I
just
want
a
quick
show
of
fans
who
can
read
this
program?
A
A
Ok,
so
we
just
have
a
whole
talk
about
this,
but
I'll
go
through
real
quickly,
what
I
think
of
as
macros.
So
what
if
I
told
you
I
have
a
new
language.
It's
pure
functional
language,
weak
typing!
Oh
my
Connick,
it's
mostly
pine
or
matching
okay,
but
this
language
is
rest
macro
rules.
So
a
macro
is
just
a
function
except
it
runs
at
compile
time
and
it
basically
processes
code
into
other
code.
A
So
then
you
can
get
around
that
restriction
by,
like
passing
some
incomplete
results
as
arguments
to
another
macro.
Do
some
we're
processing,
accumulate
your
permutations
or
whatever,
and
then
I
put
something
at
the
end,
so
these
end
up
being
called
munchers,
often
because
they
tend
to
munch
one
token
at
a
time,
and
specifically
I'll
be
talking
about
VF,
which
munches
brain
flex,
syntax
runs
it
at
compile
time
and
then
hence
the
output
of
the
brain
flow
program
to
rest
C
to
compile
so
here's
a
little
preview.
A
Here's
a
call
to
the
macro
and
here's
a
brain
v
program,
and
here
is
some
input
which
kind
of
looks
likes
numbers
and
there's
something
weird
about
it,
but
we'll
get
to
that
later
and
after
the
macro
is
expanded.
This
is
what
it
looks
like.
So
it's
basically
a
struct
literal
and
the
only
computation
this
left
to
do
is
adding
up
one
plus
one
plus
one
plus
one
plus
one,
and
then
it
prints
this
okay.
So
that
was
a
preview.
A
What
is
this
language
I'm
talking
about
so
brainfuck
is:
what's
called
a
Turing
tarpit,
which
means
it's
Turing
complete.
You
can
compute
any
computable
function,
but
it's
really
annoying
to
compute
any
computable
functions,
because
brainfuck
is
basically
an
assembly
language
with
eight
instructions,
so
I'm
gonna
go
through
those
instructions,
one
by
one,
with
a
little
cartoon
and
some
rest
code
to
illustrate
what
I'm
talking
about
so
the
brain
struck.
A
Abstract
machine
is
a
big
array
of
bytes
of
you,
eights
and
a
pointer
to
the
current
cell,
so
here's
a
drawing
of
themselves
and
a
pointer
to
the
current
cell,
so
the
first
type
of
instructions
you
can
do
are
shifting
the
pointer
back
and
forth
shift
right
shift
left
and
those
are
the
instructions
our
angle
brackets.
So
in
breasts
you
would
just
be
you
know
changing
this
index.
You
can
also
increment
and
decrement
the
value.
In
the
current
cell,
with
the
plus
and
minus
instructions,
you
can
do
input
and
output.
A
So
here
is
a
STD
in
and
here
is
STD
out,
and
so
you
can
do
input
one
byte
at
a
time,
so
usually
ask
you,
but
my
implementation
does
support
Unicode.
If
you
want
and
the
last
two
instructions
are
actually
the
most
interesting
because
they're
the
only
control
flow
instructions,
the
only
control,
so
you
can
do-
is
loop
and
it's
basically
a
while
loop
with
only
one
condition
available.
So
the
code
or
the
instructions
within
the
square
brackets
in
your
brain
flight
program
will
repeat
as
long
as
the
current
cell
doesn't
drop
to
zero
cool.
A
So
how
are
we
going
to
implement
this
in
a
macro?
So
I
don't
have
time
to
go
through
the
whole
thing,
but
I'm
gonna
go
through
a
few
specific
parts
of
the
macro
and
techniques
we
used
to
implement
this.
So
the
first
question
is:
what
are
we
going
to
do
about
integers?
We
just
saw
that
that
too,
full
indexing
and
succession
macro.
That
does
some
special
cases
of
addition,
because
macros
don't
know
what
integers
are.
Basically
the
data
structure
they
have
that
we
can
use
is
tokens
and
lists
of
tokens.
A
So
that's
how
I'm
going
to
define
integers
in
an
integer
n
is
a
list
square
bracketed
list
of
n
times
empty
parentheses.
So
here's
one
token
and
a
lit
and
a
number
n
is
a
list
of
n
tokens,
and
so
this
is
kind
of
a
recursive
definition.
Oh
by
the
way,
this
is
Zermelo
from
the
F
set
theory
this
bunch
of
sets.
A
So
because
this
is
a
recursive
definition,
I
can
write
it
as
a
recursive
background.
So
if
my
input
is
a
list
of
n
tokens
and
I
want
to
increment
I,
just
add
one
more
token,
and
if
I
want
to
decrement,
let's
say
I
have
at
least
one
token
and
then
I
have
some
more
and
I
just
toss
about
the
first
one
and
so
I've
decremented
my
numbers.
So
just
a
quick
example:
here's
that
machine
again
I
put
numbers
in
the
cells
and
the
current
value
is
2.
So
that's
2
tokens.
A
A
You
can
only
like
look
at
what's
at
the
beginning
of
the
list
like
this,
so
we're
going
to
use
a
really
cool
data
structure
called
a
zipper
where
you
can
represent
a
list
and
the
current
position
in
a
list
with
no
indexing
at
all,
and
we
do
that
by
storing
three
things.
We
store
the
current
value.
So
two,
we
store
the
values
to
the
right
three
and
four,
and
we
store
the
values
to
the
left,
zero
and
one,
and
then
when
we
want
to
move
that,
we
just
adjust
those
three
different
things.
A
So
this
is
the
elements
to
the
left,
the
current
element
and
the
elements
to
the
right.
So,
for
example,
the
current
element
is
two
elements
to
the
left:
one
and
zero
elements
to
the
right.
Three
and
four.
You
might
notice
that
these
are
stored
in
reverse
order.
So,
let's
see
what
happens
if
we
move
to
the
left
now,
the
current
element
is
one
there's
only
one
element
to
the
left
and
these
three
to
the
right.
A
A
Next,
big
question
is:
how
do
we
do
those
loops,
so
I'll
review
the
semantics
of
looping
in
brainfuck
if
we
get
to
an
opening
square
bracket,
if
the
current,
if
the
pointer
is
pointing
at
a
cell,
was
nonzero,
we
go
start
executing
the
loop.
Otherwise
you
just
skip
the
whole
thing
and
if
we
get
to
a
closing
bracket,
if
the
current
memory
cell
is
nonzero,
you
go
back
to
the
beginning
of
the
loop,
otherwise
we're
done
with
the
loop.
So
the
best
data
structure
that
I
came
up
with
to
implement.
A
This
is
two
stacks,
so
one
because
the
loops
come,
we
nested.
We
need
a
stack
of
the
currently
executing
loop
bodies,
but
when
I'm
executing
a
loop
I
have
this
variable
or
really
just
a
macro
argument:
that's
keeping
track
of
the
rest
of
the
program
to
execute
and
during
the
loop
I
just
set
that
to
the
body
of
the
loop.
So
when
we
exit
an
inner
loop,
we
need
to
remember
the
code
to
execute
after
that.
So
that's
what
I
call
the
tail
stack
by
the
way.
A
The
parsing
is
not
very
hard
because
macros
already
know
how
to
match
brackets.
Someone
has
written
a
brain-fuck
compiler
in
rust,
macros,
it
doesn't
do
this
and
it's
called
Luke
I'll
have
a
link
to
it
later.
Okay,
so
I'm
going
to
try
to
illustrate
this
with
the
two
stacks,
so
here's
my
machine
again
and
I'm,
showing
three
things:
the
rest
of
the
program.
That's
left
to
go
the
loop
stack
and
the
tail
stack
so
we're
just
going
to
run
through
this
program.
Okay,
let's
go
first,
it's
pretty
easy.
A
We're
going
to
increment
the
current
cell
and
notice
when
and
when,
when
an
instruction
executes,
it
gets
popped
off
of
the
list
of
instructions
that
are
left.
So
now
we
get
to
the
beginning
of
the
outer
loop
and
the
current
cell
is
not
zero.
So
we
push
the
loop
body.
We
push
the
tails
of
what's
left
of
the
program
after
the
loop
and
then
the
future
instructions
to
execute
just
become
the
body
of
the
loop.
Okay,
now
there's
another
loop
and
if
you
know
brain-fuck,
you
recognize
this
loop
with
just
a
in
it.
A
It's
going
to
zero
out
the
cell.
Okay,
so
again,
I
got
an
outer
loop
and
I'm.
Sorry,
an
inner
loop
and
the
current
cell
is
not
zero.
So
we
push
the
loop
body
we
push
what's
after
the
loop
body,
and
the
program
is
just
this
so
that
decrement,
the
cell
and
now
we're
at
the
closing
bracket
and
the
current
cell
is
still
nonzero.
A
So
nothing
happens
here,
but
the
future
program
to
execute
is
the
body
of
the
loop
again,
so
it
decrements
the
cell
again
and
now,
when
we
get
to
the
end
of
the
loop,
the
current
cell
is
zero,
so
we're
going
to
pop
those
two
entries
from
the
top
of
the
stacks,
because
we're
done
with
the
loop
for
now
and
then
so.
The
future
program
comes
from
remembered
from
the
tail
stack
and
it
becomes
these
two
instructions
here.
A
So
we
move
increment
this
cell
and
we're
at
the
end
of
the
outer
loop
and
the
current
cell
is
nonzero.
So
we
take
the
loop
body,
that's
on
the
top.
Here
we
peek
this
stack
and
put
it
in
the
future
program
instructions,
and
this
is
going
to
go
a
little
faster,
it
decrements
again
and
it
moves
over
and
this
ends
up
being
an
infinite
loop.
So
it
increments
this
cell
and
then
it's
going
to
clear
it
out
and
move
over,
and
then
we
would
run
out
of
space.
A
A
So
the
first
case
is
when
we
get
to
the
beginning
of
the
loop
and
the
current
cell
is
zero,
because
this
is
the
easiest
case.
We
can
just
skip
the
loop,
so
here's
some
code
at
the
top.
You
can
see
the
inputs
to
the
macro
and
the
bottom.
It
just
calls
itself
again
with
with
new
arguments.
I'm
gonna
have
some
color
coding,
okay,
so
this
is
the
current
instruction.
So
the
current
instruction
at
the
beginning
is
the
entire
loop
in
the
brackets.
A
Here's
the
state
of
the
machine.
So
here's
that
zipper
I
talked
about
here's.
The
current
cell
elements
to
the
left
elements
to
the
right-
and
this
is
the
rest
of
the
program-
that's
left-
to
be
executed
and
the
loop
stack
and
the
tail
stack
and
so
you'll
notice
that
all
of
these
are
just
lists
of
tokens
and
so
it's
to
skip
the
loop.
A
We
take
the
code
that
was
in
the
loop
and
we
throw
it
away
and
the
next
instruction
to
execute
we
take
from
the
from
the
program
list
and
then
the
instructions
left
after
that
are
the
rest
of
the
program
from
before,
and
everything
else
is
unchanged
for
a
little
bit
more
complexity.
What
happens
when
the
current
cell
is
not
zero
and
we
need
to
so.
We
need
to
enter
the
loop
code
and
more
colors
same
colors.
A
Ok,
so
again,
the
current
instruction
is
the
entire
loop,
but
we
have
to
deconstruct
it
into
the
beginning
of
the
loop
and
the
rest
of
the
loop,
because
the
next
instruction
that
the
Machine
executes
is
the
first
one
from
the
body
of
the
loop
and
the
future.
Instructions
are
the
tail
of
the
loop
plus
this
special
token
to
mark
the
end
of
a
stream,
and
then
we
take
our
two
stacks
for
the
loop
stack,
we're
going
to
push
the
loop
body
on
the
beginning
and
the
tail
stack.
A
A
Looks
colors
so
the
current
instruction
now
is
this
magic
end
of
code,
sentinel
value
and
the
current
cell.
The
memory
in
the
current
cell
is
zero,
so
we
take
our
two
stacks
and
we're
going
to
pop
off
the
entry
from
the
top.
So
we
pop
the
loop
stack
loops
head
and
throw
it
away
the
rest
and
the
loop
stack
is
the
rest
of
it.
A
Lastly,
when
the
current
cell
is
not
zero,
we're
going
to
restart
the
loop,
this
is
actually
a
little
bit
easier
because
we
don't
have
to
touch
the
tail
stack
and
all
we
do
is
we
peek
at
the
first
element
of
the
loop
stack?
So
it's
a
peek,
not
a
pop.
The
stack
is
unchanged,
but
the
next
instruction
to
execute
is
the
first
one
from
the
top
of
the
loop
stack
and
the
rest
of
it
is
the
rest
of
the
loop
body.
A
A
I
mentioned
that
macros,
don't
understand
numbers,
and
so
the
BF
macro
actually
has
a
parser
for
decimal
numbers,
and
you
just
have
to
have
every
digit
as
a
separate
token,
and
then
it
works
great,
oh,
and
by
the
way
we
need
a
pretty
high
recursion
limit
for
this
macro.
It
doesn't
have
to
be
quite
this
high,
but
it
doesn't
work
with
the
default
okay.
So
if
we
run
this
code,
it's
pretty
fast
and
it
works.
A
A
Okay,
so
I
just
wanted
to
mention
real
quick
that
there's
a
long
tradition
of
implementing
brain
suck
in
ridiculous
environments
like
Luke
or
Hodor.
That
I
mentioned
before
is
a
brain
fed
compiler
from
brain
psych,
syntax
to
rest
syntax.
So
it
doesn't
run
a
compile
time,
but
it
compiles
the
brain
s
de
Leffler
made
this
insanity
and
the
type
system
implementing
small,
which
is
like
brain
track
with
fools.
Instead
of
you
eighths
someone
has
implemented
it
in
vim,
someone
has
implemented
a
full
Turing
machine
in
PowerPoint
and
every
time
I
go
to
finish
this
slide.