7
$\begingroup$

In creating a general introductory course on computers or computing (programming and/or CS), does one mostly present high level concepts (recursion, computational complexity, concurrency, etc.), practical concepts (write some code in language X that accomplishes Y), or low level concepts (bits and bytes, logic gates, wire and blink some LEDs)?

If more than one conceptual level (which I assume is necessary to some degree), in what mix or proportion? And what order might be best for what purposes or goals of the course? How does one get students started and intested?

This earlier question is about the order of teaching, but before ordering, it helps to clarify the content of that which is to be ordered.

Also, have instructors found benefit including any other semi-related material, such as was discussed in this previous question on the history of computing?

$\endgroup$
7
$\begingroup$

TL;DR Build a world, let the students program in that world.

This is largely a history lesson which, at the end, will give hints about how to teach students to become effective in a modern OOP language quickly.

A deeper principle than Higher to Lower abstraction, however, is the principle of teaching in a Spiral manner. This principle says that the student's education should not be linear, with each thing taught completely only once. Things should be reinforced repeatedly, with each turn of the spiral adding new concepts to old, but those new concepts themselves returned to later, each spiral reinforcing older lessons as well.

Another principle here is that students learn by doing, not by listening or reading. There are a few exceptions, of course, and teachers often fall into the exceptional class, but it is rare. I've written in answer to other questions here that learning involves physical, biological changes in the brain, requiring reinforcement. There is supporting research of course.

History

With that, let me take you back to about 1975 or so. The language Pascal existed then, but C did not. Pascal was not, at that time widely used in education. FORTRAN was. Early attempts to teach using Pascal resulted in "poorly spelled FORTRAN" programs, since that matched the thought processes of programmers and teachers well versed in FORTRAN. It is said that a new paradigm only takes hold after the people holding to the old one die out. This was actually the case with the Theory of Relativity in Physics. Einstein was dismissed (that "clerk") by the superstars of the physics establishment until Poincaré's influence waned (and he died).

Pascal was created with the purpose of having a tool to directly implement Procedural Programming (PP). The essence of PP is this. Envision a Problem, P, as decomposed into a set of sub-problems, P1, P2, .... The sub problems have one of two characteristics. Either they can be immediately solved, Sk = solutionOf(Pk), or they can be, recursively, decomposed into yet smaller problems. Additionally it is assumed in PP, that there is a Known Composition method for putting the solutions to the smallest, undecomposed, problems together into a solution of the larger problem of which they are a part. In other words, decompose into sub problems going down and then recompose solutions going up.

Thus, a Pascal program was intended to look like a collection of simple procedures that invoked other simple procedures until you reach a state in which the lowest level procedures can be written in the primitives of the language. This was also called Top Down analysis and programming.

HOWEVER, early Pascal programs didn't look like that. There was a single massive procedure, or even just a BEGIN ... END. block that did everything, with only trivial parts factored out, usually those things that needed to be executed more than once. Hence, misspelled FORTRAN. Advice in early teaching materials was to factor out a procedure when it could be used several times, otherwise just inline the logic.

That was the state of affairs in about 1980. Then something magic happened. Richard (Rich) Pattis wrote a book called Karel the Robot (1981) that showed how it could be done. The book came with a simulation program in which students could write "Karel Programs". The Robot Programming Language defined in the book and accepted by the simulator did not reveal primitive, machine level, constructs such as integer and real. There was a single robot that moved in a virtual grid-like world. There were five primitive actions: move (one block), turnleft (90 degrees), pickbeeper, putbeeper, and turnoff. Nothing else. beepers (a primitive kind of thing with no behavior) could be carried but there was no protocol for asking how many the robot carried. That was implicit in the program state, not something that could be queried. Beepers could also be found on the corners of the world. It was an error to try to pickbeeper with no beepers present.

In addition to the five primitives, the robot had a rudimentary sensing capability. It could sense a beeper on the same corner and it could sense a wall directly in front. Trying to move through a wall is a program error.

Notably, the robot programming language has no variables. Repeat: no variables. You can treat a corner, conceptually, as something like a variable since it can have several beepers and that can be treated something like an integer, but there is no protocol for converting it to an actual integer, and no way to build it.

With these tools, the programmer is able to write procedures (returning nothing) and predicates (returning booleans). There were no parameters of the procedures. Using the sensing capabilities, the student can utilize selection and looping to build sophisticated programs. Karel the Robot defined a Turing Complete language. More important, the book had a wonderful set of exercises. My contention is that if a student could solve every problem in the book they could, with their learned creativity, write any computer program (Turing Complete, remember). The book built programming skill, not just familiarity with machine concepts and language features.

The book has five chapters and in the original it was possible to cover it all in a bit over two weeks, at which point the path to Pascal was trivial. But at that point students could already produce a correctly structured PP program. No more misspelled FORTRAN.

The result is that students, in their first turn around the spiral, learn program structure with few low level details (five primitives, procedures, predicates, if, and while). The second edition of KtR by Pattis, Stehlik, and Roberts (1995) contains the first edition and adds specific hints on PP such as how to go about the problem decomposition and how to build IF and WHILE structures. But you can do anything. Sorting is fun, with beepers standing in as a kind of surrogate for integers, though you can't really count. Recursion is supported, though not discussed in the original. An interesting problem is to search an infinite space for a beeper.

Creativity Under Constraint

Another aspect of the teaching philosophy underlying this principle of Creativity Under Constraint. A naive view is that you can do more with more tools. However, learning to use a few tools to a very high level of skill builds mental structure that a fuller tool set will not. If a student depends on solving the next problem with the next tool, they will be a bit lost when there are no more tools available and you have to really think. Creativity Under Constraint tries to avoid this.

As a simple example, consider poetry. If I ask you to write a poem you have few constraints. But that problem is hard hard. But if I ask you to write a Haiku, I give you constraints, but I also give you guidance and structure. The problem, though constrained, is actually easier (but not trivial, of course). This is a Big Idea.

It was vital that KtR provided this rigidly constrained world in which programming occurred, but not so rigidly constrained that any programming idea could not be expressed.

And of course, no one suggest you should only and always write Haiku.

Paradigm Shift

It is natural when a new paradigm arises (Relativity, Procedural Programming, OOP, Functional) for the practice to be thrown into a state of flux for a while, but hopefully not forever. The paradigm shift from a simpler form of imperative programming (FORTRAN) to PP was long and hard. Rich provided a tool that showed the way. It was widely adopted and helped teachers over the hump.

The interesting thing about a true paradigm shift is that it renders the earlier paradigm obsolete. A mounted knight in shining armor stood no chance of success against Henry V and his army of peasant longbowmen. And in turn they stood no chance against properly deployed musketeers. But deploying longbowmen the same way you deploy knights is just dumb.

In CS, however, a paradigm shift may not have such a profound effect, but over time, it will. Actually the last English king who was fully trained as a knight was Henry VIII and that was about 100 years after Henry V and the battle of Agincourt.

But, my way of thinking and teaching is to treat a (lesser) paradigm shift as if it were truly profound. Learn it. Adopt it. Teach it. Your students will be looking forward, of course, not back. And as I've said here before, my job isn't to teach them what I know, but what they need to know. Today that is a good solid view of OOP, for the most part.

And, programs no longer look like FORTRAN, but they, sadly, too often look like Pascal.

The Present State

We have gone through another Paradigm Shift, though it is now quite old, but too many people have not made the jump to OOP from PP. Too many programs are just PP programs with a few classes. Moreover, I see methods that are too long and too complex, putting the complexity into the methods themselves, rather than into interactions between objects viewed as bundles of behavior. Java, and later languages enable this, but using it effectively is an acquired habit (and taste).

The successors to KtR are Object Oriented. Karel J Robot (java), Karel R Tuesday (ruby), and Monty Karel (python), by Bergin, Stehlik, Roberts, and Pattis, all provide a structure, along with a simulation, in which good OO programs can be written using inheritance and composition, but with only a few ideas other than the essential ones. None of the books use integer primitives in any way. Variables are references to objects. These books are more complex than the original and require about half of a first course to cover. But at the end, the student has a clear grasp of the structure of an OOP program and can think about problem decomposition into a set of interacting objects. (These books permit the creation of several robots, not just one.) Once they deeply learn what is presented in the books it is a relatively easy task to introduce lower level concepts (int, array, ...) but also things like Collections and within reach. One drawback of the OOP Karel books is that inheritance is, perhaps, overemphasized, at the expense of composition of objects to build other objects. My personal view is that OOP enables composition primarily and inheritance secondarily, though the latter is more obvious in the syntax provided. Early on, however, Polymorphism is discussed deeply and implemented via composition using primarily the Strategy design pattern. Concurrency is also discussed briefly, since there are multiple robots.

Another feature/bug of the current books is that they use the actual languages (Java, Ruby, Python), rather than a constrained subset. While only a subset is taught, instructors are free to add things not in the books, such as integer valued variables and counting. This is a mistake, as the example below will demonstrate. One of the important (vital) choices of the designers what what NOT to teach or even include in the book. The Java book has a follow up, however, which fills in quite a lot for a full course.


Example:

To illustrate some of the above ideas and extend them a bit also, consider an exercise from Karel the Robot.

The robot, Karel, is at a corner facing East. Somewhere directly in front of the robot is a beeper (possibly even on the same corner). The Karel's task is to move to the beeper, pick it up, turnleft and move the same distance that was traveled to get to the beeper initially and put it down again.

Note: no variables, no integers, no counting is possible, except via recursion with the count held in the runtime stack, implicitly. And, of course, the previous sentence is an explicit hint.

The advantages of this are legion. You have a deep way to talk about recursion, especially the fact that recursion has two "phases": winding - to get to the base case, and unwinding - to return all the calls. To do this exercise you need to do actual work in both phases, so you can talk about the fact that both are useful (and can introduce tail recursion which this example does NOT exhibit).

It is interesting in a way in which a standard recursive computation of, say, Fibonacci numbers is not.

It is an interesting problem because solving it changes the brain of the solver. However. If the student already knows how to count and has tools (int variables...) to solve it, this problem is completely boring and adds nothing (other than a bit of reinforcement) to changing the brain.

Moreover, later on, the instructor can return to this example (around the spiral) when counting is later taught and show how counting both simplifies it and makes it more dangerous, since such things as off by one errors are now more likely.

So, what seems simple, becomes profound because it is introduced into a constrained system. The constraints both give guidance/structure AND deepen learning in ways foreseen (we hope) by the designer.

Copacetic.


Notes: While Pascal set out to be the "best" language for PP, it turned out to have flaws, especially for team based work. Modula-2 is much better, but is a true successor. However, it took lots of users writing lots of Pascal software to reveal the flaws. C++ started out as a better C+Simula. Object Pascal (from Apple) started out as a simpler Smalltalk, and Java is in that family, as are Python, Ruby, and Scala.

$\endgroup$
  • $\begingroup$ It is domain specific only if the "domain" in question is student minds. It is not a language for actual robot programming. $\endgroup$ – Buffy Jul 23 '17 at 23:04
  • $\begingroup$ +1 . Nitpicky historical point: C was released in 1972. $\endgroup$ – pojo-guy Jul 24 '17 at 0:29
  • $\begingroup$ I guess I used the date of the book The C Programming Language, not the language itself. Thanks. $\endgroup$ – Buffy Jul 24 '17 at 0:31
4
$\begingroup$

There is no single answer to this question, as the best approach will depends very much on the goals of the instruction. If you have adults who have entered into a 4-week intensive in order to change careers, then it may be natural to focus almost entirely on the concrete (by this I mean to stick almost exclusively to the level of abstraction engendered by the language you are teaching in.) By contrast, if your goal is to teach about how computational thinking impacts many fields, then you will have a natural lead-in to far more abstract thinking.

My goal, where I teach, starts with the premise that I am training my students for the future. My kids have all been labelled as gifted (whatever that means, exactly), and many of them really will be the leaders of tomorrow. Not all of them will go into software development. Therefore, my fundamental need is to create flexible, powerful thinkers and leaders of tomorrow. To paraphrase a video I once saw:

We are preparing our students to solve problems that aren't yet problems using technologies that don't yet exist.

So, what can give students the tools for this kind of flexible thinking? Do we then want to focus on the abstract or the concrete? I would suggest that, if the goal is to create deeper expertise, the initial approach is almost entirely irrelevant.

Remember that expert thinkers work differently than novices. What it takes to become an expert is to revisit many different levels of thought repeatedly. As Buffy says in his answer,

...the student's education should not be linear, with each thing taught completely only once. Things should be reinforced repeatedly, with each turn of the spiral adding new concepts to old, but those new concepts themselves returned to later, each spiral reinforcing older lessons as well.

Over the course of these visitations and re-visitations to the various layers of abstraction, the ideas between the layers become highly interconnected. These interconnections are what ultimately allow for fast, flexible thinking.

Therefore, where you start can be dictated by secondary goals. Whichever layer you ultimately choose to begin with, the most important principle would be to ensure that you are creating a rich, foundational set of intellectual hooks that later layers can connect into. That is what will serve your students best in the long run.

$\endgroup$
  • 1
    $\begingroup$ My take on this is that one should not only try to teach high-practical-low level computational concepts, but how all these concept levels connect and build upon one another. $\endgroup$ – hotpaw2 Jul 23 '17 at 19:54
3
$\begingroup$

In an introductory course, start with the practical stuff, and build up or down as needed. All the theory in the world will do you no good if you cannot apply it, and while bits, bytes, and logic gates are all very well and good, it is hard to see the forest for the trees that far down. History can also help provide context and motivation, so weave that in with the practical stuff ('this method was discovered/invented by so-and-so') but remember, again, the practical stuff is your meat and potatoes.

$\endgroup$
2
$\begingroup$

Context is King
Explain the problem that a technique is aiming to solve. Then show in outline how the algorithm or practice really, perfectly solves it. CS is one area where humans can, at times, actually do something perfectly. Then take them back to the imperfect world where things do not usually go so smoothly.

Lady Lovelace is Queen
Definitely show the history so that we can answer the question "What am I here-after?" Without reasons, without 'why', we don't know the point and how precious this learning is to humanity.

"It is based in a world built on rules"
All the rules are simple, at base, or something as dumb as a rock could not follow them. There is no mystery, no magic in the functionings of an electrical machine. It is all invented, by us, we understand it, we control it. Show the bone-simple rules early on. Binary bits encode everything that can be digitized. All the computations can be achieved with NAND logic. 3 types of statements. 5 things a CPU can do. Indirect Reference...

Complexity is in Layers
"A problem cannot be solved at the level it was conceived on." Even simple problems are made simpler by composing relationships of defined things. Define a layer that solves some aspect of the problem, and other layers that solve other aspects. Anything else is spaghetti. This is not magic, it is where you use your smarts to make dumb things work together to do smart things.

So, to answer, "Begin at the beginning, go on until you reach the end, then

STOP
ENDS
END

$\endgroup$
2
$\begingroup$

For a general introductory course, the answer is mostly practical. High level concepts are abstract and difficult to grasp. Low level concepts may appeal to the strong math student, but can be a road block to the average student. I see value in focusing on code that students can write and run and see results. This is more likely to hook them and encourage the students to want to learn more.

However, we cannot avoid the low level concepts and CS is all about layers of abstraction, so we cannot honestly give students an introduction to this field without hitting bits, bytes, and abstraction. Students in an intro class should see the practical value of understanding bits and bytes. These are terms used in consumer products and data plans; my students appreciate learning what a megabyte is and how much information it can store. I don't get many "when will I ever need this?" questions.

$\endgroup$
  • $\begingroup$ Welcome to Computer Science Educators! This is a very good answer. I hope we'll be hearing more from you. $\endgroup$ – ItamarG3 Jul 24 '17 at 19:23
  • 1
    $\begingroup$ Not only strong math students, but also students who are mechanically oriented (kit building, etc.), or students who like puzzles of various sorts might like to see how a practical-level code solution works (or doesn't) at a lower level. $\endgroup$ – hotpaw2 Jul 24 '17 at 20:05

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.