"From Bits and Gates to C and Beyond" has evolved from EECS 100, the first course in computer science and engineering at the University of Michigan. The course was taught for the first time Fall term 1995. It has been the required first course for computer science, computer engineering, and electrical engineering majors at Michigan since Fall, 1996. It is also regularly taken by other students (from engineering and elsewhere) who wish a serious introduction to computing. It has been offered both semesters each year since it was instituted. It is being taught this term (Fall 1998) to 475 students.
EECS 100 happened because faculty had been dissatisfied for many years with the lack of student comprehension of some very basic concepts. For example, students had a lot of trouble with pointer variables. Recursion seemed to be "magic," beyond understanding.
We decided in 1993 that the conventional wisdom of starting with a high level programming language, which was the way we (and most universities were doing it) was flawed. We decided that the reason students were not "getting it" was that they were forced to memorize technical details, when they did not understand the basic underpinnings.
The result is EECS 100, a bottom-up approach. We treat (in order) MOS transistors (very briefly, long enough for students to grasp their global switch-level behavior), logic gates, latches, logic structures, (MUX, Decoder, Adder, gated latches), finally culminating in an implemention of memory. From there, we move on to the Von Neumann model of execution, then a simple computer (the LC-2), machine language programming of the LC-2, assembly language programming of the LC-2, the high level language C, recursion, elementary data structures (arrays and linked lists), and finally basic analysis of some of the algorithms the students encounter throughout the book.
We do not endorse today's popular "information hiding" approach when it comes to learning. Information hiding is a useful productivity enhancement technique AFTER one understands what is going on. But until one gets to that point, we insist that "information hiding" gets in the way of understanding. Thus, we continually build on what has gone before, so that nothing is magic, and everything can be tied to the foundation that has already been laid.
The book breaks down into two major segments, (a) the underlying structure of a computer, as manifest in the LC-2, and (b) programming in a high level language, in our case C.
The LC-2.
The course starts with the underpinnings that are needed to understand the workings of a "real" computer. We start (Chapter 2) with an introduction to bits and operations (arithmetic and logical) on bits. Then we begin to build the structure needed to understand the LC-2. Chapter 3 takes the student from MOS transistors, step by step, to a "real" memory. The memory consists of 4 words of 3 bits each, rather than 64 megabytes, but the picture fits on one page (Figure 3.20), and by the time the students gets there, he/she has been exposed to all the elements that make the memory "work." Chapter 4 introduces the Von Neumann execution model, as a lead-in to Chapter 5, the LC-2.
The LC-2 is a 16 bit architecture that includes physical I/O via keyboard and monitor, TRAPs to the operating system for handling service calls, conditional branches on N, Z, and P condition codes, a subroutine call/return mechanism, a minimal set of operate instructions (ADD, AND, and NOT), and various addressing modes for loads and stores (direct, indirect, base+offset, and an immediate mode for loading effective addresses).
Students study the operating system routines (written in LC-2 code) for
carrying out physical I/O invoked by TRAP
Chapter 6 is devoted to Programming Methodology (stepwise refinement)
and Debugging, and Chapter 7 is an
introduction to assembly language programming. We have developed a Simulator
and an Assembler for the LC-2. Students use the Simulator to test and debug
programs written in LC-2 machine language and in LC-2 Assembler. The Simulator
allows on-line debugging (deposit, examine, single-step, set breakpoint, etc.)
from almost any workstation. The first program is written in machine language,
the second and third in LC-2 assembler.
Chapter 8 deals with physical input (from a keyboard) and output (to a monitor).Chapter 9 deals with TRAPs to the operating system, and subroutine calls and
returns. The first half of the book concludes with Chapter 10, a treatment
of stacks and data conversion at the LC-2 level, and a comprehensive example
that makes use of both. The example is the simulation of a Hand Calculator,
which is implemented by a main program and 11 subroutines.
The language C.
From there, we move on to C. The C programming language occupies the second
half of the book. By the time the student gets to C, he/she has an
understanding of the layers below. Each time a new construct in C is
introduced, the student is shown the LC-2 code that a compiler would produce.
We cover the basic constructs of C (variables, operators, control, functions),
pointers, recursion, arrays, structures, I/O, complex data structures,
C libraries and dynamic allocation.
We have found that pointer variables (Chapter 17) is not at all a problem,
since by the time students encounter them, they have a good understanding of
what memory is all about, since they have analyzed the logic design of a small
memory (Chapter 3). They know the difference, for example, between a memory
location's address and the data stored there.
Recursion ceases to be magic since, by the time a student gets to that point,
(Chapter 16), he/she has already encountered all the underpinnings. students
understand how stacks work at the machine level (Chapter 10), and they
understand the call/return mechanism from their LC-2 machine language
programming, and the need for linkages between a called program and the
return to the caller (Chapter 9). From this foundation, it is not a large
step to explain functions by introducting run-time activation records
(Chapter 14), with a lot of mystery about argument passing, dynamic
declarations, etc. going away. Since a function can call a function, it is
one additional small step (certainly no magic involved) for a function to
call itself.
Understanding, not memorizing.
Since the course builds from the bottom up, we have found that less memorization
of seemingly arbitrary rules is required than in traditional programming
courses. Students understand that the rules make sense since by the time
a topic is taught, the student has an awareness of how that topic is
implemented at the levels below it. This approach is good preparation for
later courses in design, where understanding of and insights gained from
fundamental underpinnings is essential to making the required design tradeoffs.
The student (not the TA) debugs the student's program.
We hear complaints from industry all the time about CS graduates not being able
to program. Part of the problem is the helpful TA who contributes far too much
of the intellectual component of the student's program, so the student never
has to really master the art for himself. Our approach is to push the student
to do the job without the TA. Part of this comes from the bottom-up approach
where memorizing is minimized and the student builds on what he/she already
knows. Part of this is the Simulator, which the student uses from day one.
The student is taught debugging from the beginning, and is required to use the
debugging tools of the Simulator to get his/her programs to work from the very
beginning. The combination of the Simulator and the order in which the subject
material is taught results in students actually debugging their own programs
instead of taking their programs to the TA for help. ...and the too-often
result that the TAs end up writing the programs for the students.
Preparation for the future: Cutting through protective layers.
In today's real world, professionals who use computers in systems
but remain ignorant of what is going on underneath are likely to discover
the hard way that the effectiveness of their solutions are impacted adversely
by things other than the actual programs they write. This is true
for the sophisticated computer programmer as well as the sophisticated
engineer.
Serious programmers will write more efficient code if they understand what
is going on beyond the statements in their high level language.
Engineers, and not just computer engineers, are having to interact with their
computer systems today more and more at the device or pin level. In systems
where the computer is being used to sample data from some metering device
such as a weather meter or feedback control system, the engineer needs to
know more than just how to program in FORTRAN. This is true of mechanical,
chemical, and aeronautical engineers today, not just electrical engineers.
Consequently, the high level programming language course, where the compiler
protects the student from everything "ugly" underneath, does not serve most
engineering students well, and certainly does not prepare them for the future.
Rippling effects through the Curriculum.
The material of "From Bits and Gates ..." clearly has a rippling effect on
what can be taught in subsequent courses. At Michigan, courses for computer
engineering and computer science majors continue with two required software
courses (EECS 280 and 380) and two required hardware courses (EECS 270 and 370).
EECS 280 used to start by teaching the syntax of C. Now, EECS 280 can not
only assume the students know the syntax of C but also understand how
it relates to the underlying architecture. Consequently, EECS 280 can focus
on problem solving with C++ and more sophisticated data structures. On the
hardware side, the students continue with a digital logic design course
(EECS 270) and an introduction to computer organization (EECS 370). Now,
EECS 270 can start with students who have an appreciation of what the logic
circuits they master are good for. In EECS 370, their jumping off point is
much further along than when they were seeing the term Program Counter for
the first time.
Feedback from faculty members in the follow-on courses have noticed substantial
improvement in student's comprehension, compared to what they saw before the
institution of EECS 100.
More information on EECS 100 can be obtained from the web page
http://www.engin.umich.edu/class/eecs100. The web page reflects the course
as it is being taught during the current semester. More information on the
EECS 100 paradigm can be obtained by contacting Professor Patt, at
patt@eecs.umich.edu.
3. Some observations:
4. More information: