CSC 395 (Fall 2021)

Reading: Notional Machines

Notional Machines

One part of the action framework we haven’t talked about much with respect to programming is the user’s conceptual model of a system. Recall that this is the user’s “mental model” of how the system works which allows the user predict the effect of their actions upon the system. Benedict du Boulay first introduced the programmer’s conception of how a program executes as a notional machine in the 80s. This term has since come into resurgence as educational researchers and programming languages researchers have begun to cross-polinate ideas.

As an introduction to the concept, read this updated survey paper by Dickson, Brown, and Becker:

Paul E. Dickson, Neil C. C. Brown, and Brett A. Becker. 2020. Engage Against the Machine: Rise of the Notional Machines as Effective Pedagogical Devices. In Proceedings of the 2020 ACM Conference on Innovation and Technology in Computer Science Education (ITiCSE ’20). Association for Computing Machinery, New York, NY, USA, 159–165.


Reading Exercise (Notional Machines):

Consider the following C program:

typedef struct {
    int* v1;
    int* v2;
} cell_t;

void f(cell_t *c) {
    *c->v1 = *c->v1 + *c->v2;
    *c->v2 = *c->v1 + *c->v2;
}

void g(cell_t *c) {
    int z = 11;
    *(c->v1) = *(c->v1) + *(c->v2);
    c = (cell_t*) malloc(sizeof(cell_t));
    c->v1 = &z;
    c->v2 = &z;
    f(c);
    // SNAPSHOT HERE
}

int main(void) {
    int x = 3;
    int y = 7;
    cell_t *c = (cell_t*) malloc(sizeof(cell_t));
    c->v1 = &x;
    c->v2 = &y;
    g(c);
}

Trace through the code by hand to determine what the contents of x and y are at the end of main. Run the code to verify your work.

After you are done, reflect on what your mental model of computation was that allowed you to trace the code. Give an example “snapshot” of your model of computation at the // SNAPSHOT HERE point. You make draw the snapshot on paper, take a picture, and embed it into your write-up.

In a few sentences each, answer the following questions:

  1. What are the different components of this model?
  2. How do you represent function calls?
  3. How do you represent pointers to values versus values?
  4. How do you represent malloc-allocated memory?