Notes on "Concepts, Techniques, and Models of Computer Programming"

chapter01.md

The Beginning of a Long Journey

This is the first in a series of posts I will be making about Van Roy and Haridi's Concepts, Techniques, and Models of Computer Programming. Several smart people have recommended the book for various reasons, and it fits in with my recent attempts to destroy and rebuild my knowledge of Computer Science and programming, from scratch.

The book is immensely long and complex, so posting may take a long time. I plan to post a summary of each chapter, along with some thoughts, and then I'll post as much of my note taking while reading as possible. I hope you'll follow along and enjoy my take.

Chapter 1 - Introduction to Programming Concepts

Summary

A whirlwind tour through pretty much every concept that is essential to understanding how to "tell a computer how to do its job." Refreshingly devoid of the baggage of other typical techniques for explaining difficult concepts, the authors plow through various subjects in a crisp, enlightening way. The relationships between each topic are made clear, and you get the sense that they are setting the stage for some deep exploration.

Here are some of my favorite quotes from the chapter, which mostly take the form of very precise definitions for key concepts, and highlight the very readable writing style:

• "This expression uses Fact, the very function we are defining! This is called recursion. It is perfectly normal and no cause for alarm."
• A program's specification is "a mathematical definition of the inputs that a program needs and the output that it calculates"
• Concurrency is "Several independent activities, each of which executes at its own pace"
• A race condition is "observable nondeterminism"
• "Programming with concurrency and state together is largely a question of mastering the interleavings"
• "An operation is atomic if no intermediate states can be observed"

The pedagogy that the authors employ is introduced in this chapter, and I find it effective. The authors introduce ideas with simple explanations and minimal examples, and pay close attention to the progression as they go.

Starting with a calculator that is used to describe functions, and running through data structures, program correctness, semantics, higher order programming, concurrency, nondeterminism, and atomicity, a system which starts simply and then becomes complexity is not only explained to us, it is plainly illustrated.

This chapter makes me very excited for the book though I'm nervous because I know things are going to get considerably more difficult. The end of the chapter contains some hints as to the means by which all of the various programming paradigms will be explored, and the breadth is impressive.

Unabridged Notes

• "Programming is telling a computer how it should do its job."
• A calculator - printing, variables, functions
• Recursion - factorial - "This expression uses Fact, the very function we are defining! This is called recursion. It is perfectly normal and no cause for alarm."
• Introduces concepts of time and space complexity right away - factorial functions
• A lot of talk about real world resource issues - memory, etc.
• Combinations, Functional abstraction - "top down" program design, decomposition
• Data structures like Lists, constructions, cons, head and rest, and their functions, Pattern matching
• A discussion of the concept of correctness and its application to computer programs. In order to ascertain a program's correctness, we need to reason about the program. We reason about programs with:
  • A model of the programming language's operations, defining what they should do - "This model is called the language's semantics"
  • A program's "specification" - "a mathematical definition of the inputs that a program needs and the output that it calculates"
  • Mathematical techniques such as induction - prove the simplest case, and then prove for the next case, and induce the rest of the cases - i.e. for integers, prove for 0, prove for 1, infer from 1 on
• Complexity is demonstrated by showing the Pascal function with and without a local variable for memoizing a step of a recursion
• 2^N or Exponential Time is impractical for all but the smallest number of inputs, while N^2 or Polynomial Time is practical for a wider range of input sizes
• We are teased with the concept of a "Future" during the section about Lazy Evaluation and its role in efficiency in program execution. Proof of concept is shown for how Mozart/Oz can execute lazy functions which are created by using the lazy keyword during function declaration.
• Higher order programming - "The ability to pass functions as arguments" - a flexible Pascal function is created which can execute arbitrary functions in place of the normal addition it uses for calculation.
• Concurrency - "Several independent activities, each of which executes at its own pace" - Concurrency is introduced by creating threads in an example that calls Pascal in a background thread and then independently displays a different value. I enjoyed this simple thread demonstration - it makes the ideas simple before scaring you about nondeterminism.
• Dataflow - introduced as a "civilized behavior" to help reason about concurrent operations and deal with issues of unbound variables. A nice illustration is given of a function that uses X without having to know if it has been bound or not. The execution is simply paused until the variable is bound.
• Explicit State - "How can we let a function learn from its past?" - we want a function to be able to count the number of times it is called, for example.
• Objects "A functional with internal memory is usually called an object"
• Local variables are mentioned along with the concept of encapsulation - an object can control the access to its internal attributes
• A factory for objects is called a class - a simple illustration of binding data and functions together to create an "OBJECT" with "METHODS"
• "Programming with classes and objects is called Object Based Programming"
• Object Oriented Programming is Object Based Programming + Inheritance
• A demonstration of nondeterminism and interleaving - different discrete operations from different threads can be interleaved in a way that can cause unexpected results if no protection is used
• A race condition is "observable nondeterminism"
• "A first lesson for programming with state and concurrency - if possible, do not use them together"
• "An operation is atomic if no intermediate states can be observed"
• Atomicity is offered as a means to avoid race conditions
• Locks are introduced as a mechanism to provide atomicity

chapter02.md

Chapter 2 - Declarative Computation Model

This begins "Section 1: General Computation Models." It contains a breakdown of the concept of a Programming Language, how it relates to the computer that it runs on, and how it relates to the real world. The thesis of the book includes the idea of the Kernel Language, which is an attempt to create a compact, reasonable set of operations by which a programming language can be represented. This Kernel Language (hereafter KL) can be translated to a Programming Language, which the developer actually uses. This translation can take place by means of Functional Abstraction or Syntactic Sugar. The text is clear that the idea behind KLs is to be able to explore multiple programming paradigms, and we start with a Declarative KL that can represent the semantics of Declarative and Functional PLs.

teaching_programming_with_the_kernel_language_approach.md

Notes on "Teaching Programming with the Kernel Language Approach"

These are some notes on a paper, Teaching Programming with the Kernel Language Approach" (PDF) outlining the teaching techniques used in Concepts, Techniques, and Models of Computer Programming by Van Roy and Haridi, which I am currently studying. As a former Computer Science educator I am intrigued by the approach that the book takes, and as a Functional Programming and Computer Science History fan I am intrigued by how it positions itself as an improvement on the techniques in The Structure and Interpretation of Computer Programs. Browsing around on the book's rather dense web site, I found a link to this paper, which seemed to provide an interesting link between the book and the classroom. Here's a bit from the abstract:

"We present the kernel language approach, a new way to teach programming that situates most of the widely-known programming paradigms (including imperative, object-oriented, concurrent, logic, and functional) in a uniform setting that shows their deep relationships and how to use them together. Widely-different practical languages (exemplified by Java, Haskell, Prolog, and Erlang) with their rich panoplies of abstractions and syntax are explained by straightforward translations into closely-related kernel languages, simple languages that consist of small numbers of programmer-significant concepts."

The following diagram covers the "steps in the kernel language approach," and describes how the approach can be used to describe programming paradigms from the simplest to the most complex:

I couldn't help but note thta my industry is entirely based on the most complex parts of this diagram, and that many of its practitioners jump straight into that without ever having even been exposed to the idea of the continuum that the above diagram represents.

Notes and Quotes

• "For the purposes of this paper, let us consider a broad definition of computer programming as bridging the gap between specification and running program."
• "Teaching programming in terms of a single paradigm or language has a detrimental effect on programmer competence and thus on program quality."
• Programming is taught in three different ways:
  • As a Craft
  • As a Branch of Mathematics
  • In Terms of Concepts

Thank you for your notes.