Introduction

Single-Assignment Store is a set of variables that are initially unbound and that can be bound to ONE AND ONLY ONE value in their lifetime. In book "Concepts, Techniques, and Models of Computer Programming", it's the fundamental element in the declarative model. We call it store in the rest of the article. Below thoughts are about implementing single-assignment store that introduced in the book chapter 2. I agree with kernal language approach, but I agree more on making hands dirty; virtual machine approach is also a very good approach for understanding how things works. By mapping A to B, we’ll know more about both A and B.

Data Structures

To implement such store, we first need to design basic data structure of variables. Then, we need to create container data structures. Next, we need to implement unification and entailment. Once all of these are implemented, we'll get a working single-assignment store. Garbage collection is an optional add-on. We'll use https://github.com/orangeduck/tgc for memory management.

Store Node

A store_node_t is a two-elements struct. The first element indicates its type. The second element is a pointer to its real value. Such struct represents a variable in a single-assignment store, or as known as dataflow variable or declarative variable.

typedef enum {
  UNBOUND_TYPE,
  // ... (other types)
} store_node_type_t;

typedef void* store_node_value_t; 

typedef struct store_node_t {
  store_node_type_t type;
  store_node_value_t value;
} store_node_t;

Unbound Store Node

Once initialized with type=UNBOUND_TYPE by malloc , it can be bound to any other types. Once bound to one of the other types, it cannot bound to other types; otherwise, an error occurs. The given two rules satisfy an important property of the store: once bound, a declarative variable stays bound throughout the computation and is indistinguishable from its value.

Assume we have a type store_error_t for capturing errors, and function store_bind_intval for binding integer values. Below examples shows the first store_bind_intval call sets node type to INT_TYPE and node value to 1, while the second store_bind_intval call does nothing except setting an error.

store_node_t* node = (store_not_t)*malloc(sizeof(store_not_t))
node->type = UNBOUND_TYPE;
node->value = NULL;

store_error_t error = STORE_NO_ERROR;

store_bind_intval(node, 1, &error);
printf("%ld\\n", (long)(node->value)); // should print 1.

store_bind_intval(node, 2, &error);
printf("%ld %ld\\n", error, (long)(node->value)); // should still print 1.

To sum up, in out implementation, an unbound store node has below information in the store_node_t struct:

• Its type is UNBOUND_TYPE.
• Its value is NULL.

Int Store Node

Without the integer type, we are unable to perform basic calculations (or at least, very hard). We can extend store_node_type_t by adding one more type: INT_TYPE.

typedef enum {
  UNBOUND_TYPE,
  INT_TYPE, /* This is the new type we just added. */
  // ... (other types)
} store_node_type_t;

One more thing, we need store_error_t to indicate an error occurring on binding. It can also be an enum.

typedef enum {
  STORE_NO_ERROR,
  STORE_ALREADY_BOUND_ERROR,
} store_error_t;

Binding a integer can be quite simple - change the type to INT_TYPE and modify the value. We could have allocated a new memory and set the value to the pointer of the new address. However, it's insufficient; the value field can fit in a long value. This also means we added an upper bound to the maximum value we can have; it's 2^32 on a 32bit machine and 2^64 one a 64bit machine.