This is a continuation of Part VI. This time, we will be adding the FOR-NEXT loop and unary negation.

The FOR-NEXT loop takes a couple forms:

FOR <VAR> = <START> TO <STOP>
...
NEXT <VAR>

or

FOR <VAR> = <START> TO <STOP> STEP <STEP>
...
NEXT <VAR>

In the former case, the step size is set to be 1. In the latter case, it can be any numerical expression, although 0 is generally not a good idea (however, the loop could be exited using IF-THEN statements, so we shouldn’t disallow 0). The variable is a regular global variable, and will be accessible both inside and after the loop. The start/stop/step inputs are all arbitrary numerical expressions which do not have to be constant, since they will be evaluated each time through the loop.

Although this could be replaced by the IF-THEN and GOTO statements we have already implemented, the FOR-NEXT construct simplifies things for the BASIC programmer. For the BASIC interpreter writer, however, it makes things a little more complicated. Since neither FOR nor NEXT statements take a line number as input, we have to associate them in our pre-processing. We also have to have a way of determining whether we are on the initial loop, in which case we have to set the loop variable to its start value, or whether we have returned from a NEXT statement, in which case we need to increment the variable.

Let’s start with the For class. We will need to implement the usual Program functions, as well as a couple new ones for handling NEXT statements. We will need to store three DoubleExpression pointers: one for the start condition, one for the stop condition, and one for the step size. We also need to store the loop variable name.

Storing the related Next instance and a boolean for whether this is the first time through the loop is a little trickier. Logically, it would make sense to have these and instance variables. But since all our instances of Program subclasses are const, we can’t modify them after they are created, which we would need to do to update these variables. So instead we will use a couple class variables storing maps between For instances and their corresponding Next and loop status booleans. Here is the header file, for.h:

#ifndef _FOR_H_
#define _FOR_H_

#include <string>
#include <map>

#include "program.h"
#include "doubleexpression.h"

class Next;

/*
This class provides the functionality to handle the FOR
loop statement.
*/
class For : public Program {
public:
	For(DoubleExpression *start, DoubleExpression *stop, DoubleExpression *step, std::string var);
	~For();
	
	void execute() const;				// run this line of the program
	void list(std::ostream& os) const;		// list this line
	void preExecute() const;			// run before main program execution
	void registerNext(const Next *next) const;	// register NEXT statement
	void doNext() const;				// called from NEXT statement

private:
	DoubleExpression *start;			// expression to evaluate to start the loop
	DoubleExpression *stop;				// end condition expression
	DoubleExpression *step;				// step size expression
	std::string var;				// loop variable name
	static std::map<const For*, const Next*> nextLine;	// NEXT statement to jump past when loop terminates
	static std::map<const For*, bool> initial;	// is this the first time executing
};

#endif

Now let’s look at the implementation, in for.cpp. We start with our necessary includes, and define the static variables. The constructor is like most we’ve done so far, with one addition: we add our new instance to the static initial map, setting it to true. Likewise in the destructor, we remove the instance from the two static variables (the instance is inserted into nextLine elsewhere):

#include "for.h"
#include "basic.h"
#include "next.h"

std::map<const For*, const Next*> For::nextLine;
std::map<const For*, bool> For::initial;

// initialize with all necessary information
For::For(DoubleExpression *start, DoubleExpression *stop, DoubleExpression *step, std::string var){
	this->start = start;
	this->stop = stop;
	this->step = step;
	this->var = var;
	initial[this] = true;
}

// clean up pointers
For::~For(){
	delete start;
	delete stop;
	delete step;
	initial.erase(this);
	nextLine.erase(this);
}

Next, let’s look at the execute() function implementation:

// run this line of the program
void For::execute() const{
	double s = 1.0;				// default step size
	double val;
	
	if( step != NULL )
		s = step->value();		// evaluate the step every time
	
	if( initial[this] ){			// start the loop
		val = start->value();
	} else {			// increment the loop
		val = Basic::instance()->resolve(var) + s;
	}
	
	initial[this] = true;			// reset
	
	Basic::instance()->assign(var, val);	// store the value
	
	// check for loop termination
	if( (s > 0 && val > stop->value()) || (s < 0 && val < stop->value()) ){
		Basic::instance()->gotoProgram(nextLine[this]);
	}
	
	Program::execute();			// continue to next line
}

First, we create our local variables for storing the step size and the loop variable value. The FOR statement allows the user to omit the STEP part, in which case we will pass NULL for the DoubleExpression pointer, and use 1.0 as the step size.

Then we determine the loop variable value. If it is the first time through the loop (initial[this] is true), we evaluate the start DoubleExpression. Otherwise, we get the stored value of the BASIC variable with the loop variable name, and add the step size value to it. In either case, we then store this value into the BASIC variable with our loop variable name, so it will be available both inside and after the loop. We also set the initial value to true here. This value is only set to false when the corresponding NEXT statement is executed, so that if this FOR loop is entered just by the program’s going to the next line or executing a GOTO, the loop will start over.

Next we check to see if the loop is done. If the step size is greater than 0, the loop terminates if its value is greater than the stop value; if the step size is less than 0, the loop terminates if its value is less than the stop value. If the step size is equal to 0, the loop will not terminate on this iteration. If the loop should terminate, we make a call to gotoProgram() (which we will implement shortly) on the Basic singleton instance, passing it a pointer to the NEXT statement instance associated with this FOR statement. Otherwise, we continue to the next line (i.e., enter the loop).

Here is the final portion of the for.cpp file:

// list this line
void For::list(std::ostream& os) const{
	os << "FOR " << var << " = " << start->list() << " TO " << stop->list();
	if( step != NULL )
		os << " STEP " << step->list();
}

// run before main program execution
void For::preExecute() const{
	Basic::instance()->pushFor(this);
}

// register NEXT statement
void For::registerNext(const Next *next) const{
	nextLine[this] = next;
}

// called from NEXT statement
void For::doNext() const{
	initial[this] = false;
}

list() prints out a representation of this statement, choosing the appropriate form based on whether a step size expression was supplied. preExecute() registers this For instance with the Basic singleton, where it will be matched with its corresponding Next instance when its preExecute() function is called. registerNext() associates a Next instance with this For instance in the nextLine class variable, which is used by the execute() function. And doNext() is called by the corresponding NEXT statement to set the initial boolean mapped to this instance to false, so that the loop variable will be incremented when its execute() function is called.

Now, on to the NEXT statement! Here is the header file, next.h:

#ifndef _NEXT_H_
#define _NEXT_H_

#include <string>
#include <map>

#include "program.h"

class For;

/*
This class implements the NEXT part of a FOR/NEXT loop.
*/
class Next : public Program {
public:
	Next(std::string var);
	~Next();
	
	void execute() const;				// run this line of the program
	void list(std::ostream& os) const;		// list this line
	void preExecute() const;			// run before main program execution
	
private:
	static std::map<const Next*, const For*> loop;	// FOR loop to jump back to
	std::string var;				// loop variable name
};

#endif

We declare the For class so that we can reference it in the class variable loop, but we don’t need to know any of its implementation details at this point. Like in the For class, we encounter the limitation of needing to make an association between const instances, so we again resort to a class variable. The only instance variable we need is to store the loop variable name.

Here is the implementation, next.cpp:

#include "next.h"
#include "basic.h"
#include "for.h"

std::map<const Next*, const For*> Next::loop;

// initialize
Next::Next(std::string var){
	this->var = var;
}

// clean up
Next::~Next(){
	loop.erase(this);
}

// run this line of the program
void Next::execute() const{
	loop.at(this)->doNext();
	Basic::instance()->gotoProgram(loop[this]);
}

// list this line
void Next::list(std::ostream& os) const{
	os << "NEXT " << var;
}

// run before main program execution
void Next::preExecute() const{
	loop[this] = Basic::instance()->popFor();
	loop.at(this)->registerNext(this);
}

Since we have a static variable loop declared in the header file, we must define it here. The constructor receives and stores the loop variable name. The destructor removes this instance from the loop map. execute() tells the associated For instance that it is being called from a Next instance, so that its loop variable will be incremented, and then moves program execution to that statement. list() does the expected printing of the BASIC statement. preExecute() requests the associated For pointer from the Basic singleton instance, and then registers itself with it.

Now we will look at the changes in the Basic class. In the header file, include the stack STL header, and declare the For class:

...
#include <vector>
#include <deque>
#include <stack>

#include "program.h"
#include "doubleexpression.h"

class For;

...

Add three new function declarations needed by the FOR-NEXT statements:

	...
	void gotoLine(int line);			// jump to program line
	void nextLine();				// go to next program line
	void gotoProgram(const Program *program);	// go to program line
	void endProgram();				// end execution
	void read(std::string var);			// assign next data value to var
	void pushData(std::vector<double> vals);	// push more values onto data vector
	void pushFor(const For *forLoop);		// push a FOR loop onto the stack
	const For *popFor();				// pop last FOR off the stack
	...

And define the forLoops variable, which uses a stack to keep track of which FOR statement is associated with which NEXT statement:

	...
	std::map<int, const Program*>::iterator counter;	// program line to run next
	std::deque<double> data;				// stored data block for READ
	std::stack<const For*> forLoops;			// stack for registering FOR/NEXT statements
	...

Now let’s write the implementations for these functions. The first, gotoProgram(), takes a pointer to a Program instance, and jumps to that location in the lines map. This is function is needed so that statements can reference each other without knowing line numbers. The logic is pretty simple: iterate through the entries until the specified pointer is found, and then set the counter iterator:

// go to program line
void Basic::gotoProgram(const Program *program){
	for( map<int, const Program *>::iterator it = lines.begin(); it!= lines.end(); ++it ){
		if( it->second == program )
			counter = it;
	}
}

For keeping track of FOR-NEXT associations, we have the forLoops stack. Each time a FOR statement is encountered, the For instance that is created will push itself onto the stack. When a NEXT statement is encountered, its Next instance will take the top For instance from the stack and associate itself. This allows for nested loops to be correctly linked. Technically, the variable name passed to the NEXT statement is not needed, since it will link to the most recent FOR statement regardless, but it makes a handy visual reference for the BASIC code writer. Here are the two functions for pushing and popping instances on the forLoops stack:

// push a FOR loop onto the stack
void Basic::pushFor(const For *forLoop){
	forLoops.push(forLoop);
}

// pop last FOR off the stack
const For* Basic::popFor(){
	const For *loop = forLoops.top();
	forLoops.pop();
	return loop;
}

Now that we have our logic implemented, we need to update our parsing and grammar. In the flex input file, add four new token parsers:

...
FOR			{ return FOR; }
TO			{ return TO; }
STEP			{ return STEP; }
NEXT			{ return NEXT; }
...

In the Bison input file, start by including the two new header files:

...
#include "for.h"
#include "next.h"
...

Define the four new constant tokens:

...
%token FOR
%token TO
%token STEP
%token NEXT
...

And update the program rule to recognize the two forms of FOR statement and the NEXT statement:

program:
	PRINT exprList			{ $$ = new Print($2); }
	| LET VAR EQUAL doubleExpr	{
						$$ = new Let($2, $4);
						free($2);	// malloced in basic.l
					}
	| GOTO INT			{ $$ = new Goto($2); }
	| END				{ $$ = new End(); }
	| IF doubleExpr comp doubleExpr THEN INT
					{ $$ = new IfThen($2, $4, $3, $6); }
	| READ stringList		{ $$ = new Read(*$2); }
	| DATA doubleList		{ $$ = new Data(*$2); }
	| FOR VAR EQUAL doubleExpr TO doubleExpr {
						$$ = new For($4, $6, NULL, $2);
					}
	| FOR VAR EQUAL doubleExpr TO doubleExpr STEP doubleExpr {
						$$ = new For($4, $6, $8, $2);
					}
	| NEXT VAR			{ $$ = new Next($2); }
;

Add the new header and implementation files to your Makefile, and you can now create and run for loops:

Welcome to BASIC!
Enter a program name: loop
>10 for a = 1 to 3
>20 for b = 2 to 6 step 2
>30 print a*b
>40 next b
>50 next a
>run
2.000000
4.000000
6.000000
4.000000
8.000000
12.000000
6.000000
12.000000
18.000000

However, if you enter a negative value for the step size, you get a syntax error:

>10 loop for a = 3 to 1 step -1
Error: syntax error

We never implement the unary negation operator! You could sidestep this by using (0-1) as an expression instead, but we should really support unary negation.

First, update the OperatorExpression implementation. We will now allow 'n' to be passed as the operator character, and NULL to be passed as the second DoubleExpression, so we need to make sure we don’t try to delete it in our destructor if it doesn’t exist:

OperatorExpression::~OperatorExpression(){
	delete a;
	if( b != NULL )
		delete b;
}

The list() function now needs to check whether it’s printing out a unary or binary operator:

const std::string OperatorExpression::list() const{
	if( op != 'n' )
		return a->list() + op + b->list();
	else
		return "-" + a->list();
}

Lastly, we need to update the value() function:

double OperatorExpression::value() const{
	switch( op ){
		case '+':
			return a->value() + b->value();
		case '-':
			return a->value() - b->value();
		case '*':
			return a->value() * b->value();
		case '/':
			return a->value() / b->value();
		case '^':
			return exp(log(a->value()) * b->value());
		case 'n':
			return -a->value();
	}
}

That takes care of the logic, and since we already have a token for the minus sign, we now update basic.y to recognize it as a unary operation. Due to mathematical precedence rules, the new rule gets put into the mulExpr rule:

mulExpr:
	expExpr
	| expExpr MULT expExpr	{ $$ = new OperatorExpression($1, $3, '*'); }
	| expExpr DIV expExpr	{ $$ = new OperatorExpression($1, $3, '/'); }
	| MINUS expExpr		{ $$ = new OperatorExpression($2, NULL, 'n'); }
;

Recompile, and you can now run loops with negative step sizes:

>10 for a = 3 to 1 step -1
>20 print a
>30 next a
>run
3.000000
2.000000
1.000000

As always, the full source is available here: https://github.com/VisceralLogic/basic/tree/part-7