12
$\begingroup$

I'm currently preparing to teach a course on data structures and algorithms. In my past experiences helping teach similar courses, I've noticed that many students find it challenging to "hold multiple layers of abstraction" in their head. This problem manifests in several different ways:

  • Students find it challenging to transition from working on assignments where they need to implement only one or two classes to larger projects involving multiple, interlocking classes.
  • Students find it challenging to understand in full detail how more complex data structures work.

To help make this more concrete, I'll pick a specific lesson/assignment I'm developing: having students implement a hashmap with separate chaining as a part of a larger project (in Java).

In order to successfully implement just the hashmap, students need to understand that the hashmap has several different "layers" of abstraction.

  1. The Map abstract data type (ADT): in particular, understanding the difference between the ADT and this particular implementation.
  2. The key: understand what it means for a key to be hashable (both in general and within Java).
  3. The hashmap internals: understanding what we do with hashed keys, resizing strategies, etc.
  4. The chain: Understand that the chain can again be abstracted (we can use any map other then a hashmap for the chain).

And of course, once they're done, students need to successfully use the data structures they've written to complete some other task which might have even more layers of abstraction.

Ideally, I want students to develop the ability to selectively "abstract" and ignore different parts of a project when implementing something to reduce mental overhead. Some students seem to intuitively grok this idea but others instead try and hold the entire data structure (or project!) in their head, have a compulsive need to read all instructor provided code, etc, and quickly become overwhelmed.

In this particular case, I've observed students seem prone to becoming confused by where the hashing logic lives, or losing sight of what the map ADT is asking them to implement in the first place.

Some of this is certainly solvable by just explaining hashmap more effectively, but my core question is this: What are some strategies for helping students become more comfortable working with multiple layers of abstraction? How can I help students develop the meta-skill of being comfortable with abstraction?

I'd welcome answers discuss potential strategies in context of this hashmap example as well as answers that address the more general question.

$\endgroup$
7
$\begingroup$

Link to real life

“Who has came to school by bicycle?”
“OK so we need to know how to make a bicycle”
“What time did you get up? It must have taken a long time to build the bicycle?”

Take it to the limit; be absurd. So the pupils tell you “You don't need to know all this to get to school.” Agree with them.

“Any one here ever fix a bicycle?” — “yes”
“So you have to fix it every time you ride?” — “no”
“But you do have to think about how it work, the inner tubes, the oil, the gears, every time you ride it, right?” — “no”
“Why not?”

Link to past experience, in subject

“Now what about a print statement, we need to know how that work to be able to use it, right?” — “no”

“So over the next few days/week we are going to be looking at a more complex system than before. We can not hold it in your head all at the same time. So I am going to ask you to do what the professionals do: don't try to remember/understand it all at the same time. We only need to understand ‘how’ for the bit we are working on. It is enough to understand ‘what’ for the bits that this uses”


This is only the 1st draft of an idea, and not tried with a class.

$\endgroup$
  • 2
    $\begingroup$ This is a good way of illustrating "Separation of Concerns", which goes back to Dijkstra, I think. But it is good to at least once take apart and reassemble one of those old in-hub bike gear sets. I did that when I was about 13. Pulling apart old TV sets was good. It is easier to compartmentalize and ignore detail when you know what some of that detail is. $\endgroup$ – user737 Jul 25 '17 at 11:41
  • $\begingroup$ @nocomprende, I agree. I'd like to see your answer to this. :) And in general, I'd like to see more professionals who really do try to understand the entire system. It's not necessary to be paralyzed until you do, but when no one even tries the result is nasty complexity. $\endgroup$ – Wildcard Jul 25 '17 at 22:19
  • $\begingroup$ @nocomprende, yep. There are many great articles on there; I had a co-worker completely change his mind about a code "fix" he had proposed after he read "Make It Never Come Back." $\endgroup$ – Wildcard Jul 25 '17 at 23:34
4
$\begingroup$

Trial and error, as well as practice, are usually the best way to get students to be comfortable with anything.

"All" you have to do is give them time and plenty of opportunities to use multiple layers of abstraction. They will find it difficult at first, but after a while they'll become noticeably better at it, and eventually they would be quite ok with using many levels of abstraction. They'll develop that mindset by trial and error.

With all trial and error, a system of feedback is needed (to know when a trial is an error). You are their system, in the beginning. At first, you have to guide them very closely, only by giving feedback on their work.

This is crucial. If you don't give feedback, then it might as well be "error and error" (in their eyes). If you give too much feedback then they might not develop the wanted mindset, or worse, they would be confused about abstraction even more, setting them back even further.

So you're task is twofold:

  1. Give them as many opportunities to work on such abstractions
  2. At first, you have to give them the right amount of feedback on their work.

It's not easy, but it's a good way to get students to develop this skill\mindset on their own.

Added bonus: You can go over this process with them (i.e. literally explain to them what it is that you did to get them to develop this mindset) and tell them that this method can be used to learn any skillset, and the important bit is the feedback in the beginning.

By feedback, I am referring to actual code review. Give them feedback based on their work. Don't be too harsh, but don't be too forgiving. I cannot say exactly how lenient you should be, but you can let intuition guide you, seeing as you know the students better than I do ;).

Whilst giving feedback, remember that you are trying to get them comfortable with abstraction. In that spirit, give very positive feedback for good use of abstractions and multiple levels of it. Don't focus on other design problems you might spot, because that might confuse the students.

This feedback shouldn't be expressed in grades. Better to give, as I said, an actual code review, focusing on the abstractions.

As for not being too forgiving: If you spot a severe abstraction problem (something that might throw runtime exceptions because the abstraction isn't abstract enough, and special cases break the abstract system), then point out what sort of special cases might cause the abstraction to crumble1. This gets the students into the mindset of making things as abstract as possible, and only dealing with concepts. The more, the better.

Also, encourage them to give it a try. For some, the word abstraction might sound threatening. At first it might be, and that's ok. As they work with it more and more (trial and error), they'll be more comfortable with it.


1If it can crumble then it was neither concrete enough, nor abstract enough. It's a pun...

$\endgroup$
  • $\begingroup$ What kind of feedback do you think would be appropriate to give? I could certainly give feedback on things like the quality of their code, but it's not clear to me how I can effectively give feedback on a mindset or way of thought. $\endgroup$ – Michael0x2a Jul 25 '17 at 15:30
  • $\begingroup$ @Michael0x2a I'll edit my answer, shall I? (:D) $\endgroup$ – ItamarG3 Jul 25 '17 at 15:30
  • $\begingroup$ @Michael0x2a better? $\endgroup$ – ItamarG3 Jul 25 '17 at 16:49
3
$\begingroup$

tl;dr Build the layers with appropriate scaffolding, either top-down or bottom-up.

The goal is to understand an abstraction layer architecture. The teaching method is to have students build it layer by layer.

Here is a suggestion that you can adapt to quite a few situations, though it takes some work as well as some consideration of tradeoffs. The basic idea is that the students implement all of the levels of the abstraction stack in sequence starting either at the top or the bottom. I'll assume you are programming in Java. It translates pretty directly into similar languages, but with more work for dissimilar languages.

Envision, a three layer stack. In practice it could have any number of layers, but three is enough to show the strategy. I'll call the three layers

The Abstraction Layer Model

  • The Attic
  • The Main Floor
  • The Basement

The Basement is the lowest level, most concrete layer and the Attic is the highest layer. The Attic might represent a true API intended for others to use (such as the Map interface) and the Basement is a low-level, even physical layer, perhaps. In practice, The Basement provides services to the layer above through a set of public methods. The Main Floor is written in terms of services provided by the Basement and itself provides services to the layer above via its own public methods.

You can work either top-down or bottom-up. However, before you can take advantage of this teaching strategy you need to build some scaffolding for the students to use. How much you have to do depends on whether you work top-down or bottom-up.

Advantages and Disadvantages of Top-Down

To work top-down, students build first the Attic with the Basement coming last.

If your students work from the top down it will be easier for them to understand the reasons for doing all this work, since the services that they are building are at a level that they might find useful in their work. The lower levels, though in reality more concrete, are more opaque since they aren't normally visible to the programmer directly.

On the other hand you actually need to do more work yourself for this as the normal Java tools don't give you as much support. I'll explain below.

Advantages and Disadvantages of Bottom-Up

To work bottom-up the students will build the Basement layer first and the Attic last.

The advantage of this is that normal unit testing tools (JUnit) make it easy for you to provide the required scaffolding.

However, the students may find this less satisfying as the things they will build at the beginning may not be as obviously useful. This is mitigated by showing them how the parts will eventually fit together before they start. They need some overview information.

Building Bottom-Up

To have the students build the Basement layer, simply decide on the interface between that layer and the Main Floor. These are the services that the Basement layer must implement. Use JUnit to write tests against this interface, simulating the Main Floor, sending known values to the Basement Services and making assertions about the values returned.

Students then build the Basement and make those tests pass. Make the test suite public so that they can write their own tests, however. Everything is open and available for inspection.

The Basement Layer may consist of several classes, some, perhaps, unrelated to others at the same level. For example, in a hash map, the actual Hasher might be at this level but the storage mechanism might be independent. You will need tests for each of the services, perhaps distributed over the classes.

Once the Basement is built, do the same for the next level up. Create the interface between the Attic and the Main Floor in JUnit and then have the students implement the Main Floor, providing those services, but using services of the Basement layer they already built.

To build the Attic, just repeat. The public API of the whole system is given a test suite and the students build the Attic using services of the Main Floor.

Building Top-Down

Building Top-Down requires more work since JUnit isn't available, though you may be able to find some Stub Testing tools.

The basic idea is that you first define the interface between one layer and the one below and then provide a Stub (set of) class(es) that implement that interface but accept known values and return known values when services are required of it.

To build the Attic, then, when the Main Floor doesn't yet exist, first develop the interface between the two. You then give them a Stub that they can use in writing the Attic. They will need to use the services of the Main Floor, but instead will be writing against the Stub's services with well known behavior.

When they are ready to write the Main Floor, give students a Basement Stub to that provides the services that the Main floor needs but using well determined "test" values.

Finally the Basement layer is written without additional stubbing.

However to avoid chaos when a stub is replaced by the actual layer code it will be essential that you also have a sufficient test suite in JUnit so that you know that what arrives at the outermost level actually makes sense.

Note that some development environments, such as Eclipse, will create a stub class for a given interface (or set of interfaces). The stub will have methods that ignore arguments and produce default values. You can tailor these, of course.

Caveats and Advice

Note that in both of these methods as described above, the instructor is the one who defines the interface between layers. This lessens the work of the student, of course, but is in some ways less satisfying. One can, instead, have group discussions in which the instructor leads the class to the development of the interfaces (actual Java interfaces) that form the boundaries between the layers. If you use this method, you will need to build your infrastructure after this discussion, but it may be little more than renaming things you built earlier in preparation. However, these class discussions also give you a way to talk about the layer separation.

And note that large software systems with such an architecture are often built this way with different teams working on the different layers, with someone like an architect defining the boundary APIs. And not again, that in some such situations, with many layers, efficiency dictates at some point that intermediate layers might be combined or eliminated. But, for teaching this initially don't permit that or your students may wind up building a Big Ball of Mud

CF: Test Stub
Mock Object


An Example

If you do the above on a sophisticated problem (building a hash map) it could take up a fair amount of class/exercise time. If you want to do it in about one class period, here is an example.

The Attic provides a service that produces the means of collections of random numbers with a given distribution; say Binomial. It calls "down" to get the collections.

The Main Floor produces the collections themselves when asked. The collection could be represented by, say, an Iterator.

The Basement produces a single value from the required distribution. It could even provide services for several distributions: Uniform, Binomial, ...

Other variations are possible. The attic, could, for example, provide the collection as a sorted list, rather than just a statistic about it. You can also add other intermediate layers, of course.

Note that each layer here is pretty trivial to build. Beware that you don't give the impression that all such uses have this property. Also note that what we really have here is akin to a Unix pipe, simply because it is so simple.

$\endgroup$
  • $\begingroup$ I think that is interesting, but it is harder to maintain the levels of abstraction and easier to build the big ball 'o mud. So it takes discipline if is is really the levels of abstraction that you want to teach. However, much real software is built just that way if done entirely within a small team. $\endgroup$ – Buffy Jul 28 '17 at 13:49
2
$\begingroup$

You say that: students find it challenging to "hold multiple layers of abstraction" in their head. My advice would be to tell them: don't try to hold several levels in mind at once. Someone I know says that writing was invented to let us forget things. Similarly, layers were invented to let us focus on one aspect of a problem at a time. Edsger Dijkstra in 1974 explains that we must do this because we have limitations:

A scientific discipline separates a fraction of human knowledge from the rest: we have to do so, because, compared with what could be known, we have very, very small heads.

Dijkstra's explanation of Separation of Concerns in a 1976 paper says:

In order to master complexity, one has to deal with one important issue (or concern) at a time.

If this very smart person said that so long ago, it certainly applies now. Layers simplify the design and coding of programs, and they make it much easier to understand and maintain code. An example from life would be that you can drive a car while paying attention to traffic, the gauges, the radio, plan your route, and possibly even talk with someone all at the same time, because they are different faculties. You can only attend to one thing at a time, but by having some be 'automatic' and only urgent things rising to awareness, you can do this. Programming is the same way.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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