programming style: which is clearer? (iteration vs. recursion)

[Ed Davis]

I'm trying to decide which of the following programming styles is
better, as in easier to understand, and thus easier to maintain.

Keep in mind that for posting purposes, this is a greatly
simplified example.

The goal is to parse and build an AST for a print statement,
returning the base-node of the AST built.

print ::= "print" expr | string ("," expr | string )*

Given the following AST declaration:

typedef struct Tree {
TreeType type;
struct Tree *next;
union {
...
struct Print {
char *str;
struct Tree *expr;
struct Tree *next;
} Print;
...
};
} Tree;

------------------------------------------------------------
Iterative version - this version closely follows the
specification of the print statement, above. This is the style I
have found in several text-books.

static Tree *parse_print(void) {
Tree *t0, *t;

t = t0 = parse_print_expr(); // first expr
while (tok.sym == commasym) { // more exprs?
t = t->Print.next = parse_print_expr(); // next expr
}
return t0;
}

Supplemental function for above, to save code duplication:

static Tree *parse_print_expr(void) {
Tree *t;

t = newTree(Print);
getsym(); // skip "print" | ","
if (tok.sym == stringsym) {
t->Print.str = strdup(tok.str);
getsym();
} else
t->Print.expr = expr(MINPRIO);
return t;
}

------------------------------------------------------------
Recursive version - I like this version, but since this is C and
not Lisp, will it still be obvious to the maintainer in a year?
Was it a good idea to move the parse_print_expr function inline?

static Tree *parse_print(void) {
Tree *t;

t = newTree(Print);
getsym(); // skip "print" | ","
if (tok.sym == stringsym) {
t->Print.str = strdup(tok.str);
getsym();
} else
t->Print.expr = expr(MINPRIO);
if (tok.sym == commasym) // more exprs?
t->Print.next = parse_print(); // recursive call
return t;
}

------------------------------------------------------------
Iterative version - this version closely models the recursive
version. It seems simple, except for the messy "first-time"
test. Was it a good idea to move the parse_print_expr function
inline?

static Tree *parse_print(void) {
Tree *t0 = NULL, *t;

do {
if (t0) // first time?
t = t->Print.next = newTree(Print); // no, next expr
else
t = t0 = newTree(Print); // else first expr
getsym(); // skip "print" | ","
if (tok.sym == stringsym) {
t->Print.str = strdup(tok.str);
getsym();
} else
t->Print.expr = expr(MINPRIO);
} while (tok.sym == commasym); // more exprs?
return t0;
}

------------------------------------------------------------
Iterative version - this version has the messy 1st "iteration
only" code pulled out of the loop. But, this causes the loop to
terminate in the middle, via a "break". Was it a good idea to
move the parse_print_expr function inline?

static Tree *parse_print(void) {
Tree *t0, *t;

t0 = t = newTree(Print); // first expr
for (; {
getsym(); // skip "print" | ","
if (tok.sym == stringsym) {
t->Print.str = strdup(tok.str);
getsym();
} else
t->Print.expr = expr(MINPRIO);
if (tok.sym != commasym) // more exprs?
break; // no, exit loop
t = t->Print.next = newTree(Print); // next expr
}
return t0;
}

 

[Chris Priede]

I'm trying to decide which of the following programming styles is
better, as in easier to understand, and thus easier to maintain.

No comment from that perspective.

However, unless I could be certain that the number of recursions will always
be limited (and small), I would go with iterative code -- to avoid possible
stack overflow.

 

[Charles Harrison Caudill]

I'm trying to decide which of the following programming styles is
better, as in easier to understand, and thus easier to maintain.

Keep in mind that for posting purposes, this is a greatly
simplified example.

The goal is to parse and build an AST for a print statement,
returning the base-node of the AST built.

print ::= "print" expr | string ("," expr | string )*

I'm still a newbie to compilers, but it seems to me that you should parse
that as a function call, or procedure call or whatever, and then the
symantec analyzer should insert the appropriate code for the print
function into the IR.

 

[The Real OS/2 Guy]

I'm trying to decide which of the following programming styles is
better, as in easier to understand, and thus easier to maintain.

There is really NO what is better. Often the algorithm you have to use
makes it easier to think in a loop, often the algorithm is clearly
better readable when it is written as recursion.

When you've got some programming praxis you will smell which form is
better.

Whenever you have clearly defined conditions belonging only to exact
the level yo're working on (e.g. a tree) you would go recursive.
Whenever you have side effects you can't control easy (means you don't
know that you have anything well defined you will use some kind of
loop.

 

[James Hu]

I'm trying to decide which of the following programming styles is
better, as in easier to understand, and thus easier to maintain.
[...]

------------------------------------------------------------
Iterative version - this version closely follows the
specification of the print statement, above. This is the style I
have found in several text-books.

static Tree *parse_print(void) {
Tree *t0, *t;

t = t0 = parse_print_expr(); // first expr
while (tok.sym == commasym) { // more exprs?
t = t->Print.next = parse_print_expr(); // next expr
}
return t0;
}

Supplemental function for above, to save code duplication:

static Tree *parse_print_expr(void) {
Tree *t;

t = newTree(Print);
getsym(); // skip "print" | ","
if (tok.sym == stringsym) {
t->Print.str = strdup(tok.str);
getsym();
} else
t->Print.expr = expr(MINPRIO);
return t;
}

This is pretty clean, from my point of view.

------------------------------------------------------------
Recursive version - I like this version, but since this is C and
not Lisp, will it still be obvious to the maintainer in a year?
Was it a good idea to move the parse_print_expr function inline?

static Tree *parse_print(void) {
Tree *t;

t = newTree(Print);
getsym(); // skip "print" | ","
if (tok.sym == stringsym) {
t->Print.str = strdup(tok.str);
getsym();
} else
t->Print.expr = expr(MINPRIO);
if (tok.sym == commasym) // more exprs?
t->Print.next = parse_print(); // recursive call
return t;
}

How about:

static Tree *parse_print_r(Tree *T, Tree *t) {

getsym();
if (tok.sym == stringsym) {
t->Print.str = strdup(tok.str);
getsym();
} else {
t->Print.expr = expr(MINPRIO);
}

if (tok.sym != commasym) {
return T;
}

return parse_print_r(T, t->Print.next = newTree(Print));
}

static Tree *parse_print(void) {
Tree *T = newTree(Print);
return parse_print_r(T, T);
}

A decent compiler will now be able to optimize away the recursion
for you.

-- James