►
Description
Will Crichton discusses a particular programming problem — binary tree rebalancing — that proved problematic for students to implement in Rust. Crichton describes some of the paradigmatic difficulties students encountered, suggesting that this is a ripe area for educational research.
A
Cool
so
hi
everyone,
my
name,
is:
will
creighton
I'm
a
postdoc
at
brown
with
street
room
christian
murphy
and
I'm
currently
doing
research
about
what
makes
rust
difficult
to
learn.
So
this
workshop
is
very
relevant
to
me,
and
this
talk
is
about
my
experience,
teaching
rust
and
to
mix
up
the
format
instead
of
talking
broadly
about
the
course
I'm
going
to
instead
zoom
in
on
a
very
specific
homework
problem
called
rebalance,
and
so,
during
my
phd
at
stanford,
I
taught
the
programming
languages
course
and,
as
a
part
of
that
course,
I
taught
students
rust.
A
I
actually
wrote
a
whole
snapple
paper
about
it
if
you're
interested,
but
the
high
level
bit
is
just
that.
I
was
teaching
rust
to
fairly
advanced
students,
and
these
were
upper
level
undergraduates
and
grad
students
and
the
question
that
prompted
this
talk
is.
I
was
reflecting
on
what
homework
problems
really
tested
a
student's
knowledge
of
rust,
because
I
taught
the
pl
course
for
three
years
I
tried
out
a
bunch
of
different
assignments
and
saw
various
levels
of
efficacy.
A
In
terms
of
like
you
know,
people
could
kind
of
guess
and
check
their
way
through
this
one,
or
it
seems
like
this.
One
really
required
some
mastery
of
the
material
to
get
through,
and
so
the
one
problem
that
came
to
mind
is
the
rebalance
problem.
So
I'm
going
to
explain
the
problem
and
the
solution
and
then
I'll
talk
about
why.
I
think
it's
interesting
so
in
rust.
A
If
you
have
a
big
line,
a
b
c
d,
then
you
would
lift
b
up
to
the
root
and
then
you
would
have
a
b
c
d,
so
it
sort
of
does
a
one
step,
rebalancing
operation
and
here's
what
a
basic
solution
looks
like.
So
the
idea
is,
you
take
a
mutable
reference
to
the
tree
and
then,
if
it's
not
empty,
you
get
the
sizes
of
each
subtree
and
if
it,
if
there's
imbalance,
you
have
two
cases
and
we'll
just
look
at
one
case.
A
A
Then
you're
going
to
detach
the
whole
tree
itself
of
self
and
then
finally
you're
going
to
restore
that
new
tree
by
creating
a
thing
with
the
roots
that
you
had
just
attached
and
store
that
back
into
self
and
then
the
helper
function
right
spine
is
also
something
that
has
to
be
designed
as
part
of
this
assignment.
So,
roughly
speaking,
it
looks
like
this.
In
this
case,
this
is
left
spine.
A
A
A
So
I
thought
in
retrospect
it
might
be
interesting
to
look
back
and
boil
that
down
to
a
few
key
aspects,
and
so
first,
this
problem
combines
functional
with
imperative
programming,
so
students
who
are
unfamiliar
with
algebraic
data
types
or
like
sort
of
inductive
recursive
styles
of
function,
design,
option
types
all
of
these
things.
I
think
they
were
going
to
be
uncomfortable
like
in
this
particular
pl
course.
We
had
studied
a
camel
before
rust
to
give
people
some
functional
background,
but
you
know
they
had
only
seen
it
for
a
couple
of
weeks.
A
A
Like
you
probably
noticed
there
was
a
bunch
of
these
mem
replace
calls
right,
and
this
is
because,
when
you
move
objects
of
right,
you
have
to
move
objects
around
in
this
problem,
but
you
also
can't
clone
them
because
we
don't
allow
t
to
be,
and
so
it's
kind
of
like
this.
You
know
the
scene
from
indiana
jones,
you're
like,
oh
god,
I
gotta.
I.
A
The
idol
but
make
sure
there's
something
there,
so
the
boulder
trap
doesn't
fall
down.
On
top
of
me,
I
suspect
that
is
how
many
students
felt
and
students
from
it,
and
the
problem
is
right.
Students
familiar
with
c
plus
plus,
might
just
like
leave
a
null
pointer
there,
while
they're
doing
their
work
and
then
come
back
and
fill
it
in
later,
but
in
rust
that's
not
really
a
valid
option
unless
you
sort
of
wrap
everything
in
an
option
which
wasn't
allowed
by
the
representation
ascribed
by
the
problem.
A
Another
complication
is
that
there
were
a
ton
of
different
pointer
types
involved.
You
have
owned
teas,
immutable,
teas,
mutable,
teas,
boxed,
teas,
mutable
box,
teas
options
of
teas
and
and
so
on,
and
I
think
students
really
struggled
to
keep
all
of
these
straight
to
know
what,
when
a
given
variable
had
a
given
type,
and
that
this
is
made
even
worse
by
auto
dereferencing
semantics,
of
course,
where,
when
you
like
match
on
something,
are
you
do
referencing
it
or
not?
A
When
you
put
an
ampersand
or
a
star
on
it,
what
type
are
you
going
to
get
back
when
you
call
a
function?
Is
that
going
to
implicitly
convert
something,
and
so
the
the
combined
fact
of
many
of
these
concepts
being
mixed
in
plus
the
compiler
trying
to
hide
as
much
of
these
conversions
as
possible?
I
think
made
it
very
difficult
for
students
to
have
a
clear
conceptual
model
of
what
their
code
was
actually
doing
at
any
point
in
time.
A
This
is
also
pre-rust
analyzer,
so
it
was
even
trickier
and
one
particularly
tricky
bit
that
I
think
summarizes
a
lot
of
these
challenges
is
that
students
had
to
design
their
type
signatures
for
the
helper
functions
and
and
oftentimes.
If
the
students
got
the
wrong
type
signature,
then
they
would
spend
a
long
time
fighting
the
borrow
checker
to
implement
a
function
that
would
just
never
type
check.
A
A
I
think
this
is
where
students
really
struggled,
because
they
would
spend
hours
attempting
to
implement
a
function
that
was
never
going
to
work
in
the
first
place,
so
either
they
would
come
up
with
a
function
that
does
type
check
but
doesn't
do
what
they
want,
or
they
would
have
a
function
that
does
what
they
want,
but
wouldn't
pass
the
bar
tracker,
and
so
you
know,
I
think,
there's
that
kind
of
a
combination
of
design
and
implementation
that
students,
you
know
partially.
I
think
I
just
maybe
didn't
equip
them
fully
in
the
course
to
do
this.
A
This
was
maybe
just
too
challenging
of
a
problem
in
some
respects,
but
I
think
it
also
encapsulates
one
of
the
hardest
parts
of
rust.
Is
this
co-design
of
thinking
about
all
the
ownership
problems
that
are
going
to
arise
using
that
to
inform
the
design
of
your
function?
Recognizing?
Maybe
when
your
function
is
incorrect,
like
at
the
type
level
and
having
to
fix
that
this
was
just
a
particularly
tricky
thing,
I
think
for
a
lot
of
students,
and
so
that's
a
sample
of
the
challenges
that
students
had
solving
this
problem
and
stepping
up
a
level.
A
I
said
that
rebalance
might
be
what
I'm
calling
a
paradigm
problem
in
that
it's,
this
sort
of
small
self-contained
problem
that
requires
students
to
understand
many
relevant
concepts
to
correctly
implement.
So,
for
instance,
it's
very
hard
to
guess
and
check
your
way
to
a
solution
here.
Like
one
thing
I
have
seen
in
some
of
my
rest
assignments
is
people.
A
Students
will
avoid
gaining
a
mental
model
of
ownership,
because
they
can
often
rely
on
the
suggestions
by
the
compiler
to
fix
their
basic
mistakes,
and
then
they
just
blindly
copy
in
or
cargo
fix,
whatever
the
compiler
says,
and
then
it
ends
up
working,
but
of
course
that
doesn't
scale,
and
so
once
they
run
into
a
problem
that
has
too
big
of
a
design
space
or
an
exploration
space.
They
struggle
and-
and
it's
important
to
have
that
kind
of
problem,
because
right,
we
don't
want
to
just
say:
oh
always
rely
on
the
compiler.
A
This
touches
on
several
challenging
aspects
of
ownership.
Right,
you
have
own
values
versus
references
versus
boxes.
You
have
lots
of
overlapping
borrows
to
things
you
have
to
carefully
make
sure
you're
never
doing
anything
unsafe.
This
is
all
along
with
algebraic
data
types.
You
have
to
understand
the
relationship
between
matches
and
references,
so
I
think
it's
nice
to
have
one
problem.
A
I
I
don't
know
that
for
sure,
but
I
think
that
would
be
an
interesting
kind
of
statement
if
you
could
say
that
with
some
with
some
rigor,
some
guarantee
by
the
way,
just
for
the
the
concerned
amongst
you,
I
did
check.
Co-Pilot
cannot
solve
this
problem.
It
generates
both
ill-typed
code
and
incorrect
code
like
it
fails
the
tests
and
also
does
things
that
don't
pass
the
type
checker.
A
So,
at
the
very
least,
if
we,
if
we
think
this
is
an
important
problem,
I
think
it's
safe
to
say
you
know
it's,
it's
not
a
co-pilotable
level
of
difficulty
yet
and
I'm
sure
that'll
change
in
a
year.
Certainly,
if
a
bunch
of
these
solutions
got
published
to
the
internet,
then
that
would
change,
but
for
now
it
didn't
it
didn't
pass
the
co-pilot
test
and
so
just
to
wrap
up.
I
think
paradigm
problems
are
interesting
because
they
help
pin
down
specific
learning
challenges
for
a
language
like
rust.
A
We
can
instead
say
something
much
more
specific,
like
people
cannot
design
the
right
type
signature
for
a
helper
function
when
rebalancing
a
bsd
and
obviously
you
know
that
is
not
a
general
statement
that
captures
everyone's
difficulties:
learning
ownership
and
rest,
but
I
think
the
idea
is
that
it
focuses
our
efforts,
and
so
if
we
could
make
this
problem
really
easy
for
someone,
then
probably
that
would
be
making
it
easy
for
a
category
of
problems
that
all
have
this
flavor
right.
But
it's
much
easier
to
focus.
A
Your
efforts
on
something
very
specific
than
to
just
say
my
goal
would
say
to
make
ownership
and
rest
easier
and
for
what
it's
worth.
This
has
been
a
very
successful
strategy
within
the
cs:
education,
research,
community.
So,
for
instance,
there's
this
problem
called
rainfall.
That's
a
list
processing
problem
that
has
literally
been
studied
since
the
1980s
and
has
been
a
really
interesting
kind
of
paradigm
problem.
A
Usually
it's
used
for
planning
like
how
do
students
decompose
a
big
problem
in
the
sub
problems,
especially
when
they
involve
lists
and
conditional
checks
and
there's
a
whole
literature
on
this.
That's
just
used,
like
literally
one
simple
problem
in
a
variety
of
really
fascinating
ways.
There's
another
really
fun
paper
called
the
mystery
of
b
colon
equals
parentheses
b
is
equal
to
false.
You
can
see
the
citation
at
the
bottom
of
the
slide,
that's
like.
A
Basically,
they
showed
that
in
an
apcs
exam
from
I
think,
1989
or
something
there
was
like
one
problem:
that
if
students
got
it
right
correctly
predicted
their
performance
for
significantly
predicted
a
lot
of
their
performance
on
the
exam.
So
the
idea
being
that
I
think
there
are
definitely
cases
in
history
where
there
are
small
problems
that
if
you
can
get
them
right,
often
indicate
a
much
deeper
understanding
of
the
concepts
at
hand,
and
so
you
know
that's
about
it.
A
I'll
leave
you
all
with
a
question
for
discussion
which
is
have
any
of
you
designed
or
encountered
paradigm
problems
in
learning,
rust,
teaching
rust,
just
exploring
rust,
because
I
think
if
we
could
curate
a
collection
of
these
problems
as
a
community,
that
would
be
a
great
help
for
both
the
theory
and
practice
of
teaching
rest
all
right.
That's
it!
Thank
you
for
listening
and
I
will
pop
open
the
chats.
A
A
So
if
I
go
to
cs242
all
this
is
online,
we
didn't
give
them
significant
pseudo
code.
I'm
sure
there
was
some
algorithmic
difficulty
in
understanding
how
to
implement
this,
but
I
think
we
gave
them
enough
examples
that
the
challenge
was
not
understanding
the
algorithm
itself,
but
rather
understanding
the
kind
of
rusty
aspects
of
it.
So
the
specific
thing
we
gave
them
was
this:
we
we
gave
them
the
high
level
operation.
We
gave
them
several
examples
of
how
it
worked.
A
We
gave
them
a
slightly
more
formal
spec
and
we
even
mentioned
a
little
bit
on
some
of
the
relevant
functions
like
mem,
replace
some
of
the
relevant
concerns
that
they
would
need
in
order
to
solve
this.
I
think
actually,
this
piece
of
text
I
probably
added
halfway
through
the
assignment,
because
so
many
students
were
struggling
with
it
or
I
maybe
liked
it
forgot
to
cover
it
in
lecture
or
something
like
that,
and
it
was
very
important
to
solving
this
problem.
So
that's.
A
That's
the
full
set
of
texts
that
we
ended
up,
including
and
I'll
leave
this
in
the
chat.
If
you're
interested
okay
are
there
paradigm
problems
for
simpler
language,
fragments
that
might
be
amenable
to
an
intro
course?
I
think
it's
a
great
question.
You
know
I
don't
know
off
the
top
of
my
head.
I
I
will
say
this
is
something
that
I'm
kind
of
exploring
in
my
own
research
right
now
we're
trying
to
create
like
an
ownership
inventory.
A
That
is
a
collection
of
relatively
small
problems
that
could
test
whether
somebody
understands
different
aspects
of
ownership.
So
I'll
probably
have
a
better
answer
to
this
question
me
personally,
at
least
soon
you
know
in
in
a
couple
of
weeks
or
a
couple
of
months
keep
your
eye
out
on
my
twitter.
If
you
want
to
follow
me,
but
I
haven't
you
know,
rebalance,
I
think,
was
the
rebalance
just
stuck
out
of
my
mind,
because
it
was
particularly
hard.
A
There
were
just
so
many
people
that
struggled
with
it,
like
the
entire
course
was
struggling,
and
you
know
some
people
to
the
extreme,
like
the
eight
hours
thing
was
a
real
quote,
so
I
don't
know
of
simpler
problems
that
I
think
exhibited
that
same,
not
just
like
the
same
level
of
difficulty,
but
the
same
net
need
for
conceptual
understanding,
but
I'm
sure
they
exist.
You
know
we
just
haven't
found
them
yet
any
thoughts
on
the
advantages
of
http
style
scaffolding.
A
They
handle
some
of
the
more
complex
syntax
patterns
such
as
in-place
changes
and
allocations
yeah.
I
I
definitely
think
you
know
the
flip
side
of
a
tricky
problem
like
this
is,
of
course,
how
do
we
teach
it
right
and
I'm
I'm
absolutely
not
going
to
say
my
course
was
the
optimal
way
to
teach
rust.
So
as
people
would
solve
the
rebalance
problem
both
because
a
it
wasn't
a
rust
specific
course.
A
So
we
were
teaching
rust
as
one
of
a
couple
languages
that
were
intended
to
demonstrate
a
variety
of
pl
theory
and
but
but-
and
I
do
think
it
is
a
very
important
question
of
like
what.
How
would
we
expect
a
student
to
go
about
scaffolding,
their
process
here,
like?
What
is
the
series
of
mental
steps
they
need
to
go
through
to
say
this?
Is
the
high
level
problem
I'm
going
to
break
it
down
like
this?
A
I'm
going
to
turn
this
into
this
type,
I'm
going
to
design
a
helper
function
this
way-
and
I
think
maybe
the
http
htdp
style
of
like
design
recipes
could
be
useful
here.
Just
to
some
extent.
I
don't
know
how
much
commonality
there
is
in
rust
code
that
you
can
have
a
really
like
general
design
recipe.
A
I
think
it
might
be
more
idiom
just
idioms
than
full
templates,
like
you
know,
if
you're
trying
to
do
x
like
you're
trying
to
work
on
a
thing,
but
you
need
to
gain
ownership
of
a
thing,
but
you
don't
have
ownership
on
that
thing.
You
know
use
memory
plays,
for
instance,
this
is
actually
something
I
pointed
out.
Also
in
an
earlier
paper,
I
wrote
called
the
usability
of
ownership,
which
is
one
of
the
big
challenges
with
I
think
with
ownership.
A
Is
that
people
have
these
like
high-level
constructs
of
like
I
need
to
work
on
this
thing,
and
then
they
don't
or
I
need
to
take
ownership
of
this
thing
and
work
on
it.
But
then
I
they
don't
really
have
the
vocabulary
or
nor
do
they
know
the
set
of
standard
library
primitives
that
are
intended
for
kind
of
solving
these
sorts
of
issues
like
another
good
example,
is
like.
A
I
need
two
mutable
pointers
and
to
disjoint
indices
into
an
array,
and
it
just
turns
out
there's
like
a
function
for
that
that
you've
just
got
to
know,
and
if
you
don't
know
that
function
you're
not
going
to
do
this
without
unsafe,
which
we
don't
want
to
encourage
you
to
encourage
students
to
do
so.
There's
a
whole
separate
sub
problem
of
like
establishing
that
library
of
idioms
and
getting
students
to
have
access
to
that
library
to
understand
it
to
be
able
to
search
it.
That,
I
think,
is
a
really
interesting
open
question.
B
Of
video
type
I
have
found
that
sort
of
I
want
to.
I
want
to
say
the
size
of
the
standard
library
is
challenging.
It's
that
there
are
such
many
things
that
need
just
the
right,
unsafe
and
the
right
place
to
do
it
in
a
reasonably
efficient
manner
that
we
just
say:
okay
put
in
the
standard
library,
and
I
find
in
many
other
languages.
B
We
don't
need
as
much
of
that,
and
so
you
know
we
have
lots
of
of
like
okay.
Well,
let's
implement
this
standard
data
structure
because
we
can
do
it
in
the
language,
with
the
garbage,
collector
and
and
options
and
etc
just
as
efficiently
as
yo,
the
compiler
writer
could,
but
russ
doesn't
have
that
so
many
of
them,
and
so
then
the
larger
ecosystem
sort
of
pushes
you
towards
well
just
use
the
standard
library.
B
A
That's
a
great
observation,
and
you
know
it
speaks
to
in
a
sense
like
the
whole
rust
experiment
which
is:
can
you
you
does?
Does
the
bar
the
theory
of
the
bar
checker
scale
to
real
world
practice,
and
the
answer
is
clearly
yes
to
an
extent,
but
it
requires
so
much
unsafe
code
in
practice,
wrapped
in
these
safe
wrappers
that
someone
carefully
designed
that
like
to
then
have
a
fundamental
understanding
of
the
language
or
to
be
able
to
build
these
constructs
and
first
principles
is
quite
challenging.
A
So
yeah,
you
know-
and
I
think
just
the
major
question
then
is:
what
does
that
mean
for
students
right
like
how
do
we?
How
do
we
resolve
that
tension?
Does
that
mean
changing
the
the
way
we
teach
the
language?
Does
it
mean
focusing
less
on
data
structures
or
on
the
implementation
of
data
structures
versus
their
usage?
Do
we
just
buy
the
bullet
and
keep
people
unsafe
anyway,
and
then
have
them,
learn
that
fragment
of
the
language
which
also
feels
unsatisfactory
since,
like
I
don't,
I
don't
think
the
rust
book
actually
teaches
unsafe.
A
C
C
So
one
of
the
things
that
that
I
was
looking
at
in
my
paper
is,
you
know
the
tools
that
we're
using
in
in
the
how
to
design
program
space
course
is
like
what
are
the
strengths
and
weaknesses
of
the
tools,
like
dr
racket,
for
example,
and
one
thing
that
was
interesting
to
me
was
having
the
teach
packs
because,
like
each
little
language
that
you
use
for
different
lessons
can
have
its
own
documentation.
That
goes
with
it
and
so
probably
not
like
a
junior
level
horse
right.