18
$\begingroup$

I was introducing lists to someone young (in Scratch). Creating a list is boring, so I opted to introduce something that you can do with lists, but requires some thinking: swapping. I introduced it by putting out four pencils in a row, like this. I asked them to swap the second and fourth items in the array (in reality).

| | | |

They took both their hands, picked up the second and fourth pencils (each in one hand), and swapped them! That works in reality... but isn't right in computer science. So, I told them, try doing it with only one hand. Predictably, they couldn't. I introduced a temporary spot, where they could put one pencil. I was hoping they would do something like this:

Second Item -> Temp spot
Fourth Item -> Second spot
Temp spot -> Fourth spot

They figured it out. But they asked me something like this: "Why can't I use two hands?". I wasn't sure how to answer that. The obvious answer is... the computer only has one hand (this was Scratch, so multithreading didn't exist). But... I'm hesitant to say that for two reasons: (1) in Python, the "two-hands" approach works (a, b = b, a, see this Stack Overflow question) and (2) multithreading exists, and there are some (obscure) ways to swap two variables without a temporary variable. So, how should I answer the question "why can't I use two hands"?

Remember, they are just learning lists, so explaining something like multithreading would be too difficult.

What's a good way to answer that question, without confusing them?

$\endgroup$
1
  • 1
    $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Ben I.
    Jan 7 at 22:58

10 Answers 10

27
$\begingroup$

Don't overcomplicate things. Your first instinct, that the computer only has one hand, was the correct one.

This is a regular problem that new teachers have, and it sometimes takes a few years of frustration to burn out the idea that everything you say must be formally true. If we say something that is untrue, the reasoning goes, the students will remember it and use that wrong idea to badly misunderstand things later.

Let me give you a slightly different mental model of learning, and you'll find all of the support you need in the absolutely fantastic book "How People Learn II", which is a big volume that describes everything we really know from research about how learning actually works in the brain.

We (1) build mental models by (2) connecting new information (3) to things that we already know. Furthermore, (4) abstraction is the brain-process of finding the similarity in (5) similar mental models. (6) In order to build upon prior knowledge, (7) it must already be fairly well understood. If it's not, and you simply don't have the prerequisite knowledge, you are unlikely to build any mental model at all.

(That should make some sense; if it's not already fairly concrete within your mind, it's too nebulous to glom new ideas onto.)

So, with that as a model of learning, there are a few implications:

  1. We need to help students build small, clear mental models. They can then use these in the future to build further, richer models. This lends itself very nicely to the KISS principle. Don't try to introduce too many variations to the idea at once. Leave the complicating for the next step, or you won't obtain any model at all.
  2. Before there is already a fairly clear mental model, learning isn't really taking place, so little of what is said will be directly remembered. Corollary to this is that the danger of them being confused by some overly literal interpretation of what you said while explaining how to swap in Scratch once they encounter threading later down the line is completely negligible. They won't remember much of the explanation until they can build a mental model, so they won't remember those kinds of details. In addition, there are simply too many cognitive models that have to be built between swap in Scratch and multithreading for one to hamper the other.

Don't let perfect be the enemy of progress. Keep it simple and focused on the small concept they are learning right now, and be comfortable that that will support them best as they grow and develop and complexify ideas later.

$\endgroup$
4
  • 3
    $\begingroup$ Let me add that to justify using the simple (sequential, explicit temp) model, ask the students to think about all the ways the two handed model could go wrong. Especially how the simple model doesn't have those defects. $\endgroup$
    – Buffy
    Jan 4 at 20:29
  • 1
    $\begingroup$ It would also be fine to add the caveat that "right now in our example, the computer only has one hand." This would be less technically incorrect without distracting the student too much, I think. $\endgroup$
    – 2rs2ts
    Jan 6 at 20:42
  • $\begingroup$ @2rs2ts Sure! But realize that you do that basically for your own benefit. It won't help the student, and might, by admitting that more complex layers exist, hinder them in their current struggle. But I don't want to sound too negative; I play those sorts of word games every day, and could scarcely stop it if I tried. After all, it bothers me to say it wrong. I just have to be cautious about how much additional complexity I allow into a model that the student already isn't getting (ie they're already at the edge of their cognitive limits). In those moments, when in doubt, leave it out. $\endgroup$
    – Ben I.
    Jan 6 at 22:32
  • $\begingroup$ One name for the "small, clear mental model" you mentioned is Notional Machine, as someone else commented. This idea is why I often say that we have to teach people how computers actually work. I say: computers can only do 5 things - fetch, store, arithmetic, compare and jump. With that in mind, students are more likely to understand programming than if we start with something other than a Notional Machine. $\endgroup$
    – Scott Rowe
    Jan 7 at 2:04
22
$\begingroup$

Re-evaluate what you think is "right", because you aren't

but isn't right in computer science

This is simply incorrect. Your student can create two variables called LeftHand and RightHand. Copy value "red" from position 1 to LeftHand, copy value "green" from position 4 to RightHand, copy values back to positions 4 and 1 respectively. Job done.

Is this optimal? No - but you didn't ask for optimal, you asked for a solution which works. Your student gave you a working solution, and you've rejected it because of your own preconceptions of how many variables they "should" use, or how many steps it "should" take. Neither of those preconceptions are correct. There's no time or RAM pressures here, so the student is perfectly free to do it their way. (Edit following your comments elsewhere: Nor do they have to consider concurrency where someone else could move the pencils in between.)

And not only are they free to do it this way - if they find it easier to understand then they should. My background is in safety-related software. Coding standards in safety-related software prioritise readability, maintainability and ease of understanding by other coders, ahead of pure speed, because the most intractable bugs almost always come from people trying to be too clever. If you keep the concepts simple, you don't make mistakes and your code is more likely to work first time.

In short, you are committing a cardinal mistake in software engineering, which is premature optimisation (which as every software engineer should know is the root of all evil). Your student is not making that mistake, and that currently makes them a better software engineer than you!

Certainly after they've got a two-handed solution, you can have them do a one-handed version with a single slot. You can then show them that it takes fewer steps and one less variable. The answer to "why can't we...?" is simply "you can if you want, but look, it's more work". Most people would rather do less work, so it's a win all round.

$\endgroup$
5
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Ben I.
    Jan 7 at 22:58
  • $\begingroup$ I've added an answer that shows your LeftHand, RightHand version as actually better — for one extant architecture — than the OP's : cseducators.stackexchange.com/a/7223/8837 $\endgroup$
    – Rusi
    Jan 9 at 5:55
  • 1
    $\begingroup$ The gcc compiler happily turns the "standard one temp variable" in C into a 2 registers "both hands" versions. Probably because it is more efficient (read-write, cache...) $\endgroup$ Jan 13 at 21:27
  • $\begingroup$ @Michelbillaud That's really worth an answer! Hard data that the less efficient notionally is the more efficient actually. Just (1) input program (2) output cut down to relevant parts (3) gcc flags if any (4) gcc version just in case $\endgroup$
    – Rusi
    Jan 18 at 4:09
  • $\begingroup$ Well compiling this with gcc -03 -S void swap(int *a, int *b) { int c = *a; *a = *b; *b = c; } produces this assembler code movl (%rdi), %eax ; movl (%rsi), %edx ; movl %edx, (%rdi) ; movl %eax, (%rsi) ; ret $\endgroup$ Jan 21 at 9:30
16
$\begingroup$

Your problem is that you tried to let your student "program" without establishing a language. Thus they were free to write their own "language" in which you can do two things at once because you have two hands. If you'd asked them to rotate 3 objects, they would have picked up the third pencil in their mouth or so.

You could have asked them "suppose you're a crane driver" then, because they obviously have only one crane, they would have solved the problem "correctly".

May this also be a lesson to you to think very hard about everything you ask your students. Don't improvise. Or just learn for next time.

$\endgroup$
7
  • 4
    $\begingroup$ I do like your crane idea, and in hindsight, I should have done that... however, how do you come up with these ideas for alternate ways to phrase problems to get students to think about it in a certain way or come to a specific answer? $\endgroup$
    – cocomac
    Jan 4 at 23:27
  • 2
    $\begingroup$ I actually ran into a very similar problem, but it was about communcating processes. After a student uses the two-handed solution, I now tell them, "you have only one communication channel, so put your left hand in your pocket, and use your right hand". So I had to learn the hard way, like you. $\endgroup$ Jan 5 at 1:41
  • 1
    $\begingroup$ @cocomac -- apart from the obvious canned answer of "practice will do it" that, although true, doesn't help you up front :-), mostly just by going the opposite direction. To think about it first, like "I don't want them to use both hands, so I need to come up with some setup that makes it one hand only, so I need an interface between two-handed people and one-handed manipulator, let me see". $\endgroup$
    – Gábor
    Jan 5 at 11:23
  • 5
    $\begingroup$ @computercarguy And I'm sure there are people who can juggle with one hand, so they could still do the swap without a temporary variable. Analogies are always imprecise. $\endgroup$ Jan 5 at 20:05
  • 1
    $\begingroup$ @VictorEijkhout, juggling usually means you can handle more than one object with one hand. I've juggled for over 35 years and can do 3 balls in one hand, for example. So yes, the analogy is imprecise, but that doesn't mean it can't still work. I said there was an issue, not a problem. I should have been more precise that it wasn't a critical reason not to use the analogy. This issue with the analogy can easily be avoided by specifying the language, as you say, by not allowing double-picking. We just need to know how to specify the language to avoid these issues, that's all. $\endgroup$ Jan 5 at 20:23
5
$\begingroup$

This question reminds me of when a student failed to understand why a third variable was needed to exchange the value of two variables (i.e. to swap A and B, C=A, A=B, B=C). I managed to illustrate this to them by placing an item (mobile phone) in each of their hands, and asking them to swap the items between the hands. On attempting to do this, they immediately realised they needed a third location (the table) to achieve this.

You may find your list-swapping activity works better if you place the pencils in students' hands. This will help reinforce the idea that each pencil needs a location (hand) to be stored in at all times. You'll obviously need more than one student to make a list that's larger than two pencils, and pandemic-related distancing may be an obstacle.

I'd suggest trying this activity with two or three students sat in a row, and using an odd number of pencils. This will ensure that there is only one hand available for moving pencils about at any time, without appearing to be an arbitrary rule that you've introduced.

$\endgroup$
1
  • 2
    $\begingroup$ Neat! Hand not the mover (verb) but the place (noun) 👍 $\endgroup$
    – Rusi
    Jan 7 at 17:43
4
$\begingroup$

They took both their hands, picked up the second and fourth pencils (each in one hand), and swapped them! That works in reality... but isn't right in computer science.

It depends on your paradigm. You are teaching the swap algorithm you know, but haven't explained to the students (or at least in the question) what things are. Here is a perfectly valid way to look at the operation, using two temp variables, 'Left Hand' and 'Right Hand':

Second Item -> Left Hand
Fourth Item -> Right Hand
Left Hand -> Fourth spot
Right Hand -> Second spot

In fact many students will do it this way (with two temp variables) when they attempt to do swapping for the first time, I'm pretty sure I did. Some languages have swap operations built-in so you don't require a temporary variable.

In this particular case I think it would make more sense to say that you can only move one pencil at a time rather than you have only one hand. After all I could pick up the pencil in spot two and place it in slot four while picking up the pencil there at the same time with one hand.

The analogy breaks down in other ways, for instance normally you make a copy of the item in the temp variable and it exists in two places until you overwrite it in the array. I think using things like colored blocks here and making copies into variables would be a better way to visualize what is actually happening too...

$\endgroup$
3
$\begingroup$

In thinking about this, and especially the answer of Graham, I think that what we really do in the standard three step process is a two handed swap without thinking of it. So, it is a failure of the metaphor, actually. So, here is a reframing of the standard process:

Pick up one stick with the left hand (i.e. temp is associated with the left hand). THEN, move the other stick with the right hand (the assignment). THEN put the stick in the left hand into the proper slot.

Or:

Second Item -> Left Hand Fourth Item -> Second spot // using Right Hand Left Hand -> Fourth spot

All you need to explain is that (with a single processor) only one thing can be done at a time and so the swap-with-two-hands has to be sequenced in some way rather than happening simultaneously.

This is to avoid issues in the more general case where you want to swap(m,n) where m and n could be the same. Both hands can't pick up the same stick simultaneously if it has to be sequenced. The bright kids will want to complain that you can't pick up a stick from an empty slot, but the small variation isn't too hard to explain if you think of it beforehand. The really astute ones will notice that assignment is copying, so "picking up one stick" in the program doesn't really leave that slot empty, as it does with physical objects.

(ASIDE: there is a way to avoid that physical/virtual disconnect by using a reference (rather than copy) metaphor of variables, but it is likely not where you want to go with youngsters unless you do it ubiquitously. In essence, a variable is a reference to a value not a box that "holds" the value.)

It also avoids discussions of race conditions with multiple processors.

$\endgroup$
5
  • $\begingroup$ Why does "single processor" keep getting brought up? How would you sequence operations by 2 cores to get a swap done correctly? The relevant thing here is a scalar CPU, as opposed to modern superscalar CPU cores that literally can execute two independent load instructions in the same clock cycle. (e.g. AMD since K8, Intel since Sandybridge: realworldtech.com/sandy-bridge/7). Intel since Ice Lake can even execute two store-data uops in the same clock cycle, although commit from store-buffer to L1d cache can only commit two stores in 1 cycle if they're to the same line. $\endgroup$ Jan 6 at 16:19
  • $\begingroup$ As you say, a normal swap is 2 loads then 2 stores (assuming an optimizing compiler for an AoT compiled language for a register machine), whether we name one or both temporaries. (Or in Python, neither). For (much) more advanced students of CPU architecture, this might be a good illustration of hazards like write-after-read when finding parallelism between operations: you have to finish picking up an object (loading into regs) before a store of the other object writes that location. $\endgroup$ Jan 6 at 16:27
  • $\begingroup$ @PeterCordes "Why does "single processor" keep getting brought up?" Not because using multiple processors or multiple threads would enable a different solution, but because if you are explaining to a student why they have to solve the problem with one hand then the analogy is justified by the fact that their program can "only do one thing at a time". $\endgroup$
    – kaya3
    Jan 6 at 17:10
  • $\begingroup$ @kaya3: Thanks, you're right, I was thinking in terms of finding instruction-level parallelism within instructions for a sequential model of execution, not the need for there to be a sequence in the first place. I think I'd find it less weird to say the code or program is single-threaded, rather than to say there's only one processor to execute it on. As you rightly pointed out, the issue here is the execution model of the programming language, not the CPU details. $\endgroup$ Jan 6 at 18:17
  • $\begingroup$ @PeterCordes Because if you ask a centipede how it knows which leg to move next, it gets in a hopeless tangle. (That's just a metaphor, of course.) $\endgroup$
    – Scott Rowe
    Jan 7 at 2:19
3
$\begingroup$

I do the swap example pretending to have two largish (2-hands-to-lift) boxes side-by-side on a desk (with only enough room for two boxes). After we lift the first we have to look for a place to put it, which feels like creating the temp variable.

But I don't think swap is an especially good example with lists. It's easier to explain swapping just any two variables, x and y. Lists are about using indexes. In Scratch we don't get as much fun with loops, but can do 2 step find-the-index-first stuff like "turn the first 9 into a 6" or "put 12's before and after the first 3".

As far as "computer rules" I like a lighter touch. Swap is one of many clever tricks which happen to work, for now. Motivate the problem with how switching x and y starting with "set x to y" permanently erases x. Then explain how that 3-step dance is actually the standard swap trick. We could have had a built-in swap command but everyone was all "no, everyone knows the trick and it's just one extra step".

Esp. in Scratch you're hoping they like it and move onto a real language. At that point you're going to explain how "Scratch rules" like pre-making variables aren't computer rules at all. But we learned lots of concepts which mostly transfer over with minor changes. In the end: switching values of two variables is a thing; everyone calls it a swap; and it's good to know the trick just-in-case there's no built-in way.

$\endgroup$
4
  • $\begingroup$ well... to be fair you do need to "pre-make" variables in most languages... $\endgroup$
    – somebody
    Jan 5 at 20:43
  • $\begingroup$ @somebody My understanding is the Scratch language has no declarations -- variables are created manually through the GUI. I assume a Scratch user learning a text-based language would be surprised at something like int x=4. But I've only seen Scratch a few times, is there a better example? $\endgroup$ Jan 5 at 23:27
  • $\begingroup$ well. while that's true i'd argue that scratch variables are all global, and global variable declarations in other languages are little different from that of scratch - you still "create variables manually". to look at it another way, in scratch, not just variables but everything is created "through the GUI", no? (equivalently, scratch has no (official) textual syntax at all). but either way the point is, imo "pre-making variables" (and scratch in general) is little different from the so-called "computer rules" $\endgroup$
    – somebody
    Jan 5 at 23:47
  • $\begingroup$ tl;dr imo how variables are created in scratch are mostly a side effect of being a graphical (?) language rather than it being fundamentally different from other lanugages $\endgroup$
    – somebody
    Jan 5 at 23:48
3
$\begingroup$

Analogies & metaphors are imperfect, so let's share the expectation that they are just illustrative.

Rules of what is possible (and not) are very important, and we can compare the rules of pencils moved with hands and what computers can do — but we need to define both, in part so the rules for the metaphor can be compared with the those of a computer.

These rules can be reasonably terse and simple to state.

The computer can copy a value from one storage location to another storage location.  (Computers generally copy data rather than moving it.)

Your hand can simulate action of making a copy, and whether the hand itself represent another storage location that can be utilized while doing something else is a matter of definition and explanation of rules.

Since we're talking about information rather than physical items, I might prefer a metaphor of a spreadsheet: swapping two cells in a spreadsheet generally requires another free cell; a pencil and piece of paper with some boxes holding symbols might also work, you need to stipulate whether human memory is outside of the metaphor (i.e. not be used for storage).

Programming languages support constructs & expressions that require additional implicit storage, and language implementations introduced temporaries for these purposes: Python's a,b=b,a is such a construct, while any language's general purpose expressions is another: you can't really compute a*b+c*d without holding the result of one of the multiplications somewhere (on paper, in your head, in storage...), while doing the other.

$\endgroup$
8
  • $\begingroup$ "a * b + c * d" : lovely! This insight is at the heart of functional programming : elide useless names. The more technical name for that is combinatory logic. (The proper name "Haskell" is the name of its second founder) $\endgroup$
    – Rusi
    Jan 6 at 3:45
  • $\begingroup$ @Rusi Are there any Functional Machines? Computers that execute your high level idea of the calculation and not some lower level translation? I would like to see such a machine. I would also like to get to work using a map instead of a car, but you can't have everything. (Where would you put it?) Brains really do seem to implement a Neural Network, but computers not so much. Some day perhaps. $\endgroup$
    – Scott Rowe
    Jan 7 at 2:11
  • 1
    $\begingroup$ @Scott: Lisp machine, Scheme88. In fact Data flow architectures were actually made for improving efficiency of von Neumann languages eg SISAL. In fact among theoretical models, lambda calculus is more realiable than Turing machines because the latter has an infinite sub part -- the tape. How the F does an engineer make an infinite object?! Nothing infinite about the lambda calculus. Evolution...... is slow $\endgroup$
    – Rusi
    Jan 7 at 2:51
  • $\begingroup$ @ScottRowe All that FP does is generalize "a * b + c * d" from numbers to arbitrary memory data structures. Heck even python Java C# etc -- the whole current mainstream gang -- will allow you to handle complex data structures, manage ing the memory with gc etc. Only difference is the modern crop mess up memory semantics. FPLs don't. Java, C#, JS are identical modulo syntax and minor details. $\endgroup$
    – Rusi
    Jan 7 at 3:23
  • $\begingroup$ Of course IF you're prepared to go outside the mainstream there are heroic exceptions. Eg Rust which strives for C-level efficiency, memory-footprint. Plus almost haskellish purity. And is even highly portable (Compare to C's autoconf!!!). IF... Are you?? (In 1987 I pioneered and initiated C in edu. It was as new and uncharted then as it's passe now. Today I would use rust for that space (if I were younger... If...))" $\endgroup$
    – Rusi
    Jan 7 at 3:42
2
$\begingroup$

Ben's answer is great, but allow me to suggest that you don't need to "respond" to the two-handed approach at all: just say when you're explaining the problem in the first place that they can only use one hand and they can only hold one item at a time.

Students are less likely to need a justification this way, because you haven't changed the rules to forbid a solution after they've come up with it themselves. If a justification is required, the question is not "why can't I use two hands?", but rather "why is it useful to know how to do this with one hand?". And the answer to that is that the solution using one hand can be translated directly into code, whereas the solution with two hands can't be.

$\endgroup$
7
  • 2
    $\begingroup$ Except you perfectly well can translate the solution with two hands into code. Not picking up both simultaneously, sure - at least on most systems - but one at a time works fine. $\endgroup$
    – Graham
    Jan 5 at 13:36
  • $\begingroup$ except you cannot just let it slide without explanation - it's extremely important to make sure the student is understanding it how you think they are. so you'd at the very least have to explain (and get the student to agree) that they are describing a 4 step process left = a; right = b; a = right; b = left rather than a 1 step process a, b = b, a. the problem with this is that it runs the same risk of the student asking why the process must be split into those steps. $\endgroup$
    – somebody
    Jan 5 at 20:49
  • 1
    $\begingroup$ @Graham By "the solution with two hands" I refer to the one in the OP where a student picks up both items with both hands at the same time. If you interpret hands as variables rather than as the computer's action of moving (or really, copying) a value from one variable to another, then there are other two-handed solutions, but "the" two-handed solution still doesn't work. As for "on some systems", we are talking about whatever language the students are learning, not the capabilities of all programming languages. $\endgroup$
    – kaya3
    Jan 5 at 22:51
  • $\begingroup$ Maybe someday we will build computers that can do many things at once. Quantum, massively parallel, whatever. Then we will not be able to teach anyone how to program them, but we won't have to. $\endgroup$
    – Scott Rowe
    Jan 7 at 2:29
  • $\begingroup$ @ScottRowe I don't know what future you're imagining where nobody is a computer programmer, but I want no part of it - I like programming! $\endgroup$
    – kaya3
    Jan 7 at 6:03
2
$\begingroup$

Graham pointed out that the assumtions of the question are wrong. And Peter Cordes elaborated a bit in the comments.

Considering a target VLIW (Very Long Instruction Word) architecture can help sharpen this argument further.

The basic idea of VLIW is that a Very Long Instruction "horizontally" packs a number of instructions per single VL-instruction, all of which are executed in parallel in one machine cycle. The requirement is that the multiple instructions in a VL-instruction need to access disjoint memory/registers.

In terms of more popular architectures, VLIW is:

  • Like pipelined superscalar architectures except that the compiler rather than the hardware does parallelization scheduling
  • Like RISC in that the complexity is shifted to the compiler

So

x = 1
y = 2

can be packed as one VL-instruction

 x = 1 // y = 2

Whereas

x = 1
y = x + 1

can't because x overlaps.

(Using the notation that multiple VL instructions are on multiple lines and "subinstructions" packed into a VL instruction are on one line "//" separated).

With that background we can write swap as

lh = x // rh = y
x = rh // y = lh

Whereas your preferred solution

t = x 
x = y
y = t

is interlocked at each stage and so is hopelessly sequential.

tl;dr

The VLIW oriented swap is 33% faster — 2 vs 3 — than the standard imperative one. When it is naively sequentialized it's 25% slower — 4 vs 3.

Note

The two-hand analogy is right in being more efficient than with one hand. However it's not so right in this that it seems to be able to do it in one single 2-handed swoop. Whereas (for VLIW at least) it's two 2-handed swoops. Our hands have enough muscle intelligence to criss-cross without colliding whereas data-buses dynamically hop-skipping over each other is.. uh... still futuristic sci-fi😂.
IOW analogies/metaphors may help but don't go all the way.

$\endgroup$
2
  • 1
    $\begingroup$ Premature optimization is... Oh, you already heard that one. Could we venture to teach beginning students something without having to teach them everything? I had a great welding instructor, he could cover one topic or technique each class night. I still think of him as one of the best teachers I had, and still smile when I recall him whistling during class as he thought about going out with his wife afterwards. $\endgroup$
    – Scott Rowe
    Jan 13 at 1:40
  • 1
    $\begingroup$ 👍 @ScottRowe. In upholding the "Premature..." proverb you'll find me more extreme left (or is it right?) than anyone. The point of this post was.... O well... May the blessing of Fermat be on these comment columns... $\endgroup$
    – Rusi
    Jan 13 at 2:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.