stage2: Extensively comment the source code

diff --git a/stage2.c b/stage2.c
index 90b19f1..b5b4f4a 100644 (file)
--- a/stage2.c
+++ b/stage2.c
@@ -54,7 +54,7 @@ load_reference_results(void)
  * Functions: ADD, SUB, MUL, DIV, IFEQ
  *
  * Variables: X (first operand), Y (second operand) and Z
- * (operator - ASCII value). */
+ * (operator letter - can be also thought of as its ASCII value). */
 
 
 /*** PROGRAM TREE STRUCTURE DEFINITIONS */
@@ -73,7 +73,7 @@ struct program_node {
        struct program_node *sibling; /* Sibling in tree. */
 };
 
-struct program_function;
+struct program_function; /* See below for function classes. */
 
 struct program_node_function {
        struct program_node pn;
@@ -90,16 +90,17 @@ struct program_node_variable {
        char name; // X, Y or Z
 };
 
-/* The way the program is called. This describes mainly
- * the program parameters. */
+
+/*** PROGRAM BUILTIN FUNCTIONS DEFINITIONS */
+
+
+/* The way the program tree itself is called. This describes
+ * the parameters of the program, i.e. the values of the variables. */
 struct program_call {
        int X, Y, Z;
 };
 
 
-/*** PROGRAM BUILTIN FUNCTIONS DEFINITIONS */
-
-
 /* Available functions are described by the program_function structure. */
 typedef int (*program_function_eval)(struct program_call *pc, int params[]);
 struct program_function {
@@ -108,6 +109,7 @@ struct program_function {
        program_function_eval eval; /* Evaluation function - takes parameters and produces value. */
 };
 
+/* ADD function */
 static int
 pf_add_eval(struct program_call *pc, int params[])
 {
@@ -119,6 +121,7 @@ static const struct program_function pf_add = {
        .eval = pf_add_eval,
 };
 
+/* SUB function */
 static int
 pf_sub_eval(struct program_call *pc, int params[])
 {
@@ -130,6 +133,7 @@ static const struct program_function pf_sub = {
        .eval = pf_sub_eval,
 };
 
+/* MUL function */
 static int
 pf_mul_eval(struct program_call *pc, int params[])
 {
@@ -141,6 +145,7 @@ static const struct program_function pf_mul = {
        .eval = pf_mul_eval,
 };
 
+/* DIV function */
 static int
 pf_div_eval(struct program_call *pc, int params[])
 {
@@ -154,12 +159,16 @@ static const struct program_function pf_div = {
        .eval = pf_div_eval,
 };
 
+/* IFEQ function */
+/* The parameter order here is a bit unusual:
+ * IFEQ(A, B, C, D) means if (C == D) then B else A */
 static int
 pf_ifeq_eval(struct program_call *pc, int params[])
 {
        /* The parameters are in this order so that the first
         * two parameters (and particularly the != case) have
-        * highest chance of having the largest subtrees. */
+        * highest chance of having the largest subtrees
+        * (when not using the hinting logic). */
        return params[2] == params[3] ? params[1] : params[0];
 }
 static const struct program_function pf_ifeq = {
@@ -168,6 +177,7 @@ static const struct program_function pf_ifeq = {
        .eval = pf_ifeq_eval,
 };
 
+/* List of all program functions, for randomly picking one. */
 static const struct program_function *program_functions[] = {
        &pf_add, &pf_sub, &pf_mul, &pf_div, &pf_ifeq
 };
@@ -193,6 +203,7 @@ program_node_function_eval(struct program_call *pc, struct program_node_function
        }
        assert(i == node->funct->n_params);
 
+       /* Then, evaluate the function itself with the given parameters. */
        return node->funct->eval(pc, params);
 }
 
@@ -213,7 +224,8 @@ program_node_variable_eval(struct program_call *pc, struct program_node_variable
        }
 }
 
-/* Evaluate a given program. */
+/* Evaluate a given program, returning the resulting return
+ * value of the function at the root of the tree. */
 static int
 program_node_eval(struct program_call *pc, struct program_node *node)
 {
@@ -293,7 +305,7 @@ program_node_function_copy(struct program_node_function *node)
        struct program_node *lastchild = NULL;
        for (struct program_node *param_node = node->pn.child; param_node; param_node = param_node->sibling) {
                struct program_node *child = program_node_copy(param_node);
-               /* Link them up. */
+               /* Link the children to the program tree. */
                if (!lastchild)
                        newnode->pn.child = child;
                else
@@ -324,6 +336,7 @@ program_node_variable_copy(struct program_node_variable *node)
        return (struct program_node *) newnode;
 }
 
+/* Produce a recursive memory copy of the given node and all its children. */
 static struct program_node *
 program_node_copy(struct program_node *node)
 {
@@ -357,19 +370,25 @@ program_node_random(int energy, struct program_node *parent)
         * will usually need to be accompanied by significantly raising
         * population size and/or the number of generations. */
 
+       /* Prepare information used by the hinting logic. */
+
        struct program_node_function *parentf = (struct program_node_function *) parent;
        bool allow_constant = true, variable_xy = true;
        if (parent) {
                parentf = (struct program_node_function *) parent;
-#if 0 /* Hint importance: low (small improvement) */
+#if 1 /* Hint importance: low (small improvement) */
                /* XXX: Hinting - allow constants only as parameters of IF. */
                allow_constant = (parentf->funct == &pf_ifeq);
 #endif
                variable_xy = (parentf->funct != &pf_ifeq);
        }
 
+       /* If energy is 1, this node will be a "simple" node:
+        * a constant or a variable, not function. */
+
        if (energy == 1) {
                if (allow_constant && random_boolean()) {
+                       /* Generate a constant node. */
                        struct program_node_constant *node = malloc(sizeof(*node));
                        node->pn.type = PNT_CONSTANT;
                        node->pn.child = node->pn.sibling = NULL;
@@ -380,7 +399,9 @@ program_node_random(int energy, struct program_node *parent)
                        node->value = random_int(256);
 #endif
                        return (struct program_node *) node;
+
                } else {
+                       /* Generate a variable node. */
                        struct program_node_variable *node = malloc(sizeof(*node));
                        node->pn.type = PNT_VARIABLE;
                        node->pn.child = node->pn.sibling = NULL;
@@ -398,10 +419,12 @@ program_node_random(int energy, struct program_node *parent)
                }
        }
 
+       /* Generate a function node. */
+
        /* Pick a random function. */
        const struct program_function *f = program_functions[random_int(program_functions_n)];
 
-       /* Create function node. */
+       /* Create the function node. */
        struct program_node_function *node = malloc(sizeof(*node));
        node->pn.type = PNT_FUNCTION;
        node->pn.child = node->pn.sibling = NULL;
@@ -439,8 +462,9 @@ program_node_random(int energy, struct program_node *parent)
        for (int i = 0; i < f->n_params; i++) {
                /* Remaining energy is randomly distributed between children. */
                int child_energy = 1 + random_int(energy - (f->n_params - 1 - i));
+               /* Recursively create randomized children. */
                struct program_node *child = program_node_random(child_energy, (struct program_node *) node);
-               /* Link them up. */
+               /* Link the children to the program tree. */
                if (!lastchild)
                        node->pn.child = child;
                else
@@ -453,11 +477,17 @@ program_node_random(int energy, struct program_node *parent)
 }
 
 
+/* Recursively release memory occupied by this node and all its children. */
 static void
 program_node_done(struct program_node *node)
 {
        struct program_node *cnode = node->child;
        while (cnode) {
+               /* cnode_sibling is temporary variable for storing the
+                * pointer of the next sibling. This is necessary since
+                * the moment we want to move on to the sibling, we cannot
+                * look at the pointer in the current node anymore since
+                * we have already free()d the node. */
                struct program_node *cnode_sibling = cnode->sibling;
                program_node_done(cnode);
                cnode = cnode_sibling;
@@ -470,6 +500,7 @@ program_node_done(struct program_node *node)
 /*** PROGRAM TREE WALKING (OTHER) */
 
 
+/* Measure size of a program sub-tree in term of number of nodes. */
 static int
 program_node_subtree_size(struct program_node *node)
 {
@@ -488,6 +519,8 @@ program_node_subtree_size(struct program_node *node)
        return size;
 }
 
+/* Store pointers to all nodes in the given subtree (and their corresponding
+ * fathers and left (previous) siblings) in a flat array nodes[]. */
 static int
 program_node_subtree_list(struct program_node *node, struct program_node *nodes[], struct program_node *fathers[], struct program_node *psiblings[])
 {
@@ -506,27 +539,45 @@ program_node_subtree_list(struct program_node *node, struct program_node *nodes[
        return i;
 }
 
+/* Randomly pick a node in the program tree rooted at @node. Also give
+ * (in *father and *psibling) pointers to its father and left (previous)
+ * sibling. */
 static struct program_node *
 program_node_subtree_random_pick(struct program_node *node, struct program_node **father, struct program_node **psibling)
 {
        int size = program_node_subtree_size(node);
 
+       /* Flat array to collect all nodes. */
        struct program_node *nodes[size], *fathers[size], *psiblings[size];
        nodes[0] = node; fathers[0] = NULL; psiblings[0] = NULL;
 
+       /* Collect all the nodes into the flat array. */
        int s = program_node_subtree_list(node, &nodes[1], &fathers[1], &psiblings[1]) + 1;
        assert(s == size);
 
+       /* Randomly pick an element of the array. */
        int i = random_int(size);
+       // printf("pick %d/%d\n", i, size);
        *father = fathers[i];
        *psibling = psiblings[i];
-       // printf("pick %d/%d\n", i, size);
        return nodes[i];
 }
 
 
 /*** CHROMOSOME MANAGEMENT */
 
+
+/* How is the program represented from GAUL view? The GAUL operates
+ * in terms of entities (members of the population) which are composed
+ * from chromosomes.
+ *
+ * We use only a single chromosome per entity, i.e. chromosomes are
+ * 1:1 with population members for us. The chromosome is then a pointer
+ * to the root node of the program tree corresponding to the entity. */
+
+
+/* A service routine for creating a chromosome (i.e. a single member
+ * of the population. */
 boolean
 program_chromosome_constructor(population *pop, entity *embryo)
 {
@@ -543,6 +594,8 @@ program_chromosome_constructor(population *pop, entity *embryo)
        return TRUE;
 }
 
+/* A service routine for releasing a chromosome (i.e. a single member
+ * of the population. */
 void
 program_chromosome_destructor(population *pop, entity *corpse)
 {
@@ -557,6 +610,8 @@ program_chromosome_destructor(population *pop, entity *corpse)
        corpse->chromosome = NULL;
 }
 
+/* A service routine for replicating a chromosome (i.e. a single member
+ * of the population. */
 void
 program_chromosome_replicate(const population *pop, entity *src, entity *dest, const int chromosomeid)
 {
@@ -588,15 +643,27 @@ static void
 mutate_entity(population *pop, entity *father, entity *son)
 {
        // printf("%p (%p) <- %p (%p)\n", son, son->chromosome[0], father, father->chromosome[0]);
+
+       /* A mutated entity starts off as a 1:1 copy of the original entity. */
        son->chromosome[0] = program_node_copy((struct program_node *) father->chromosome[0]);
 
+       /* Randomly pick a node. */
        struct program_node *mnode_father, *mnode_psibling;
        struct program_node *mnode = program_node_subtree_random_pick(son->chromosome[0], &mnode_father, &mnode_psibling);
 
-       /* Mutation means that this subtree gets replaced
-        * by a random different subtree. */
-       struct program_node *newnode = program_node_random(random_boolean() ? 1 : 8 * random_double_1() + 2, mnode_father);
+       /* Mutation means that this node (including a subtree it
+        * potentially holds gets replaced by a random new node. */
 
+       /* With 50% probability, the new node is a simple node
+        * with energy 1 (variable or constant). Otherwise, it is
+        * assigned a random energy in the range of 2 to 10 and
+        * therefore becomes a function node holding a small subtree
+        * of its own. */
+       int energy = random_boolean() ? 1 : 8.0 * random_double_1() + 2;
+
+       struct program_node *newnode = program_node_random(energy, mnode_father);
+
+       /* Link up the new node in stead of the original node. */
        if (mnode_psibling)
                mnode_psibling->sibling = newnode;
        else if (mnode_father)
@@ -605,6 +672,7 @@ mutate_entity(population *pop, entity *father, entity *son)
                son->chromosome[0] = newnode;
        newnode->sibling = mnode->sibling;
 
+       /* Release the original node. */
        program_node_done(mnode);
 }
 
@@ -615,9 +683,13 @@ crossover_entity(population *pop, entity *mother, entity *father, entity *daught
 {
        // printf("%p (%p) xx %p (%p) => %p (%p) xx %p (%p)\n", father, father->chromosome[0], mother, mother->chromosome[0], son, son->chromosome[0], daughter, daughter->chromosome[0]);
 
+       /* The new entities start off as copies of the original entities. */
        daughter->chromosome[0] = program_node_copy((struct program_node *) mother->chromosome[0]);
        son->chromosome[0] = program_node_copy((struct program_node *) father->chromosome[0]);
 
+       /* Randomly pick nodes in the new entities to be swapped together
+        * with the subtrees they hold. */
+
        struct program_node *cdnode_father, *cdnode_psibling;
        struct program_node *cdnode = program_node_subtree_random_pick(daughter->chromosome[0], &cdnode_father, &cdnode_psibling);
        struct program_node *cdnode_sibling = cdnode->sibling;
@@ -645,8 +717,9 @@ crossover_entity(population *pop, entity *mother, entity *father, entity *daught
        cdnode->sibling = csnode_sibling;
 }
 
-/* Execute a single entity, interpreting its chromosome.
- * Saves the results to a number array. */
+/* Execute a single entity, interpreting its chromosome supplying it with
+ * equations from a prepared text file. */
+/* The funciton saves the results to a number array. */
 static void
 execute_entity(entity *entity, int results[EQNO])
 {
@@ -682,6 +755,7 @@ execute_entity(entity *entity, int results[EQNO])
        fclose(f);
 }
 
+/* Assign fitness to an entity. */
 static boolean
 evaluate_entity(population *pop, entity *entity)
 {
@@ -704,12 +778,13 @@ evaluate_entity(population *pop, entity *entity)
        entity->fitness = 1.0 - (double) diffcount / EQNO;
 
        /* In addition, we encourage the simplest programs by
-        * subtracting a tree size based term. */
+        * subtracting a tree size based term from the fitness. */
        const int typical_size = 200;
        const double typical_weight = 0.01;
        int size = program_node_subtree_size(entity->chromosome[0]);
-       //entity->fitness -= log(1 + size / typical_size) * typical_weight;
        entity->fitness -= size / typical_size * typical_weight;
+       /* Alternative idea, does not work as well: */
+       //entity->fitness -= log(1 + size / typical_size) * typical_weight;
 
        return TRUE;
 }