This material serves as lecture notes and background reading for the second-semester course “Programming 2” that I regularly teach since 2008 in the Computer Science Bachelor’s programs at Saarland University.
Our curriculum emphasizes a solid programming education that does not only cover practical aspects but also an introduction to foundations such as structure and semantics of programming languages, type systems, program correctness, and verification. As the name “Programming 2” suggests, this course follows “Programming 1”, an introduction to functional programming and computer science in general and it precedes an introduction to algorithms and data structures.
Programming 2 (and therefore this text) has the following objectives:
Provide solid practical skills in statically-typed practically-relevant imperative and object-oriented programming languages.
To this end, the course is accompanied by a series of programming projects in all languages covered (RISC-V, C, Java) that increase in size and difficulty.
Provide an introduction to simple algorithms and data structures from an imperative perspective.
One part of learning the practice of programming is also to learn about data structures and algorithms that solve interesting problems. We try to provide this experience through non-trivial programming projects that often rely on clever data structures and algorithms that make the project feasible in the first place (shortest paths in route planning, acceleration structures in ray tracing, dynamic programming, etc.).
Provide an overview of and experience with the software stack from machine code to a high-level language.
I consider it important that students are able to identify the different levels of abstractions that are at work in programming and they can mentally move between these abstractions without problems. Seeing a C/C++ program and actually having a vague idea of what happens on the machine is not only helpful to eliminate “cargo cult” thinking but also vital when it comes to performance or security considerations. Therefore, the course intentionally starts with computer arithmetic and machine code programming to convey an impression on how programs execute at the lowest level. This enables an understanding of the abstractions higher-level imperative languages provide to make programming machines more bearable and scalable, what these abstractions actually abstract from, and what the cost of these abstractions are.
Provide an introduction to the theoretical foundations of imperative programming languages and a basic understanding of program correctness, testing, and verification.
Being able to understand how computers execute is one thing. It is equally important to understand how to describe programs and their execution in mathematical terms to be able to talk about concepts like termination, undefined behavior, correctness, etc. in a meaningful way. It is important to understand that the details of these notions are so intricate, subtle, and important that it is impossible to leave it at hand waving. Additionally, one can make the experience that the process of formalizing things uncovers and clarifies ambiguities and makes precise what one is actually talking about.
Appendix C presents and discusses a sample course structure using this text. In this sample structure, some of the sections of this book are discussed in greater detail than others.
Happy hacking!