# Ruby BASIC (#228)

**URL:** <https://www.ruby-forum.com/t/ruby-basic-228/182574>\
**Category:** Ruby\
**Created:** [January 30, 2010, 7:26am UTC](https://www.ruby-forum.com/t/ruby-basic-228/182574 "2010-01-30T07:26:34Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![danmcb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/13edae/32.png) [@danmcb](https://www.ruby-forum.com/u/danmcb)\
**Post date:** [January 30, 2010, 7:26am UTC](https://www.ruby-forum.com/t/ruby-basic-228/182574/1 "2010-01-30T07:26:34Z")

</div>

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Q.:

1. Please do not post any solutions or spoiler discussion for this  
quiz until 48 hours have elapsed from the time this message was  
sent.

2. Support Ruby Q. by submitting ideas and responses  
as often as you can.

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem  
helps everyone on Ruby T. follow the discussion. Please reply to  
the original quiz message, if you can.

* * *

RSS Feed: [http://rubyquiz.strd6.com/quizzes.rss](http://rubyquiz.strd6.com/quizzes.rss)

Suggestions: [http://rubyquiz.strd6.com/suggestions](http://rubyquiz.strd6.com/suggestions)

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

## Ruby BASIC (#228)

10 PRINT “Hello Rubyists”  
20 END

Inspired by one of the solutions from quiz #223[1](http://rubyquiz.strd6.com/quizzes/223), this week’s quiz  
is to write a BASIC interpreter.

There are many different versions of BASIC with some subtle  
differences, so for the purpose of this quiz let’s focus on  
unstructured Dartmouth BASIC[2](http://en.wikipedia.org/wiki/Dartmouth_BASIC#Keywords).

Everyone should feel encouraged to post some samples of their favorite  
BASIC programs for testing.

Have fun!

---

<div class="post-metadata">

**Author:** ![danmcb](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/13edae/32.png) [@danmcb](https://www.ruby-forum.com/u/danmcb)\
**Post date:** [April 20, 2010, 8:25am UTC](https://www.ruby-forum.com/t/ruby-basic-228/182574/2 "2010-04-20T08:25:32Z")

</div>

This summary was written by Jean L…  
We received no solution for this quiz. Therefore we are going to  
present the one we wrote.

The basic language reference we consider is the one from Dartmouth  
college (back in October 1964). The language is rather simple, it only  
computes numbers. It does not contain any string handling, except for  
output printing. The variable naming is limited to a single letters  
followed by an optional digit. It does not support interactive input.

The language

Let us start with a short description of the language. For a deeper  
specification see annex or get the Dartmouth College’s document.

Each line of a basic program is a statement. Most statements are  
instructions to execute.

A line must start with a line number. After the line number comes a  
word denoting the type of the statement. Basic has fifteen statement  
types:

DATA  
DEF  
DIM  
END  
FOR  
GOSUB  
GOTO  
IF  
LET  
NEXT  
PRINT  
READ  
REM  
RETURN  
STOP  
Our implementation does not support the DEF and DIM statements.

Source code does not require lines to be ordered. Basic uses only  
capital letters and spaces are optional. Expression must appear on a  
single line.

The END statement must be the highest numbered statement, including  
the data statements. A number must contain up to nine digits with an  
optional minus sign and an optional decimal point.

As basic programs have no input statements, a program uses the data  
statements for data input.

A simple program

Next program outputs the first ten square roots.

10 LET X = 0  
20 LET X = X + 1  
30 PRINT X, SQR(X)  
40 IF X \<= 10 THEN 20  
50 END  
The parser

We are going to write a parser and an interpreter. Separating the  
parsing phase from the interpretation (or the run) makes writing tests  
easier, we separate the syntaxical aspects from the running aspects.

Parsing basic code is not very difficult, the syntax is not complex.  
We use a regular expression to validate each line.

01 unless line =~ /^(\d+)  
\*(DATA|DEF|DIM|END|FOR|GOSUB|GOTO|IF|LET|NEXT|PRINT|READ|REM|RETURN|STOP)  
_(._)$/  
02 raise error\_message(“INVALID STATEMENT”, line\_number, line)  
03 end  
The regular expression matches a string starting with digits, followed  
by optional spaces, one of the valid basic keywords, optional spaces  
and anyhting. We use regular expression’s groups so that if the line  
matches our rule the global variables $1 contains the line number, $2  
contains the statement and $3 the rest of the line. We discard any  
space in between.

After validating the statement type, we need statement specific  
validation. We use a hash table that maps the statement type to a  
method that parses each statements.

01 STATEMENT\_PARSERS = {  
02 ‘DATA’ =\> :parse\_data,  
03 ‘END’ =\> :parse\_end,  
04 ‘FOR’ =\> :parse\_for,  
05 ‘GOSUB’ =\> :parse\_gosub,  
06 ‘GOTO’ =\> :parse\_goto,  
07 ‘IF’ =\> :parse\_if,  
08 ‘LET’ =\> :parse\_let,  
09 ‘NEXT’ =\> :parse\_next,  
10 ‘PRINT’ =\> :parse\_print,  
11 ‘READ’ =\> :parse\_read,  
12 ‘REM’ =\> :parse\_rem,  
13 ‘RETURN’ =\> :parse\_return,  
14 ‘STOP’ =\> :parse\_stop  
15 }  
Each parse method needs the statement line number and the rest of the  
line (the part to parse). It also needs the current position in the  
script and the whole line to be able to generate a valuable error  
message.

01 statement = self.send(method, line\_number, line, $1.to\_i, $3)  
02 statements \<\< statement  
The parser sends the message (the parse method) to it self. If the  
parse method successfully parses the statement it returns a Satetement  
object. We add the statement object to the statements array.

Once the parser consumes all the input program, we need to sort the  
satements because the basic language does not require the statement to  
be ordered.

01 statements.sort!  
The sorting works because the Statement objects provide an  
implementation of the comparison method (\<=\>). The comparison method  
compares the line numbers. Here is the Statement base class.

01 class Statement  
02  
03 attr\_reader :line, :arguments  
04  
05 def initialize line, type, arguments = nil  
06 @line, @type, @arguments = line, type, arguments  
07 end  
08  
09 def \<=\> other  
10 @line - other.line  
11 end  
12  
13 def to\_s  
14 “#{@line} #{@type} #{@arguments}”.rstrip  
15 end  
16  
17 end  
We are not going to present all the parse methods, as an example we  
are going to look at parse\_goto which is rather simple. A goto  
statement looks like: 10 GOTO 90. Which means: the effect of line 10  
is to jump at line 90.

01 def parse\_goto line\_number, source, statement\_line, arguments  
02  
03 scanner = BasicScanner.new(arguments)  
04  
05 scanner.skip\_spaces  
06 to\_line = scanner.scan\_line  
07  
08 raise error\_message(“MISSING TO LINE”, line\_number, source)  
unless to\_line  
09  
10 scanner.skip\_spaces  
11 raise error\_message(“INVALID ‘GOTO’ STATMENT”, line\_number,  
source) unless scanner.eos?  
12  
13 GotoStatement.new(statement\_line, to\_line.to\_i)  
14  
15 end  
We use the BasicScanner class which derives from the StringScanner  
class. The reason for extending StringScanner is to add methods, like  
skip\_spaces, that makes it easier to read the code, not to mention  
that regular expressions are not easy to read.

The arguments parameter is a string containing everything following  
the basic statement type. We first skip spaces (line 5), then we try  
retrieving the line number to go to (line 6). If we don’t find a line  
number, we raise an error (line 8). Otherwise we skip trailing spaces  
(line 10) and check if we reached the end of the input (line 11).  
Finally, input was a valid GOTO statement and we return a  
GotoStatement.

Expressions

When a statement expects an expression the parse methods use the  
parse\_expression method.

parse\_expression  
a number (a floating point value) for literals,  
a string for operators (+, -, \*, /, ^), parentheses and built-in  
functions  
a symbol for variables  
The array of tokens is still an infix expression. The reason is that  
we can easier implement the to\_s method use by the to\_s method of a  
Statement object which produces a valid basic source code.

The to\_a method returns the array of tokens.

Expression  
Testing the parser

Testing the parser is easy, here are some examples.

Testing the expression parsing.

01 expr = @parser.parse\_expression(‘INT(X/Y) + 2’)  
02 assert\_equal [‘INT’, ‘(’, :X, ‘/’, :Y, ‘)’, ‘+’, 2], expr.to\_a  
Testing converting the expression to the postfix version.

01 expr = @parser.parse\_expression(‘SQR(4) + INT(Y/2) \* 3’)  
02 assert\_equal [4, ‘SQR’, :Y, 2, ‘/’, ‘INT’, 3, ‘\*’, ‘+’],  
expr.to\_postfix  
Testing that spaces are optional.

01 def test\_program\_witout\_spaces  
02  
03 program = \<\<PROGRAM  
04 10PRINT"HELLO"  
05 20END  
06 PROGRAM  
07  
08 statements = @parser.parse(program)  
09  
10 assert\_equal 2, statements.length  
11  
12 assert\_equal ‘10 PRINT “HELLO”’, statements[0].to\_s  
13 assert\_equal ‘20 END’, statements[1].to\_s  
14  
15 end  
We use the to\_s method of the Statement objects which returns a  
canonical string to make the test is easier to read. (notice that  
reading source code without spaces is not easy – line 4)

The interpreter

Now that a parser returns an array of Statement objects, executing the  
program is easy. We loop through them and keep track of the program  
position (we need a bit more, see later). The interpreter uses a  
runtime object which stores the programs’s variables and the program  
position. Here is the main loop of the interpreter.

01 def run\_statements statements  
02  
03 runtime = create\_runtime(statements)  
04  
05 while runtime.running?  
06  
07 statement = statements[runtime.program\_pos]  
08  
09 statement.execute(runtime)  
10  
11 runtime.program\_pos += 1  
12  
13 end  
14  
15 runtime  
16  
17 end  
The runtime object has also a running state.

The interpreter expects the statement objects to implement the execute  
method (line 9). The statement classes in the parser file  
(basic\_parser.rb) do not offer execute methods, we re-open the classes  
here in the interpreter file (basic.rb). Therefore our files are  
shorter and the separation of responsibilities does not imply doubling  
the set of classes.

At the end of the method (line 15) we return the runtime to the  
calling code so that it can access the variables.

The runtime object

Let us fisrt look at the runtime class layout.

01 class Runtime  
02  
03 attr\_accessor :program\_pos  
04  
05 def initialize console, data  
06 end  
07  
08 def running?  
09 end  
10  
11 def next\_data  
12 end  
13  
14 def end  
15 end  
16  
17 def print line  
18 end  
19  
20 def [] var  
21 end  
22  
23 def []= var, value  
24 end  
25  
26 def each\_var  
27 end  
28  
29 def save\_pos name, subject  
30 end  
31  
32 def restore\_pos name  
33 end  
34  
35 end  
A Runtime instance needs a console where the output is sent and an  
array of all the data available for the read statements.

The program position can be read or changed, for instance the GOTO  
statement changes it. Notice that the program position is an index in  
the program’s array of statements, not the source code line number.

The next\_data returns the sequence of data or nil when all the data is  
consumed.

The end method puts the state to program ended.

The print method is used by the PRINT statement.

The [], []= and each\_var give access to the current values of the  
program’s variables.

The last methods, save\_pos and restore\_pos are used to save the  
current program position and to retrieve the saved position. A name is  
accociated with each save, it is useful to validate the correct  
sequence of the NEXT statements and the RETURN statements. The saved  
positions are pushed on a stack and must be consumed in reverse order.

Creating the runtime object

The create\_runtime method instantiate a Runtime object.

It loops through all the statements creating:

a map table, mapping the basic line numbers to the index in the array  
of statements  
a collection of the goto-like statements (GOTO, GOSUB and IF)  
an array of all the data found in the statements  
After the first loop, it starts a second loop to set the mapped line  
number to the program position for all the goto-like statements. The  
test to find what statements are goto-like is done by searching all  
the objects that respond to the program\_pos= message, needed to set  
the actual program position.

Turn the Statement objects into runnable objects…

In the interpreter file we re-open the Statement classes and add the  
execute methods. The default implementation does nothing (some  
statements like DATA and REM just inherit the no-operation execute).

01 class Statement  
02  
03 def execute runtime  
04 end  
05  
06 end  
One interresting thing in Ruby is that we do not need to redeclare  
inheritance when we re-open a class. Therefore, if we ever need to  
change the class hierarchy we only need to change it at one place. If  
we declared the inheritance we would have to give exactly the same.

We are going to look at the STOP and the GOSUB statements.

01 class StopStatement  
02  
03 def execute runtime  
04 runtime.end  
05 end  
06  
07 end  
(We do not repeat that the class derives from the Statement class.)

The implementation for stop is very simple, it only needs to notify  
the runtime that the program stops running (line 4).

The gosub is just a bit more complicated.

01 class GosubStatement  
02  
03 def execute runtime  
04 runtime.save\_pos :gosub, self  
05 runtime.program\_pos = @to\_program\_pos  
06 end  
07  
08 def program\_pos= line  
09 @to\_program\_pos = line - 1  
10 end  
11  
12 end  
We ask the runtime to save the current program position, because when  
we later meet the return statement we must continue at the next  
statement relative to the current position. We register the save  
position with a special name, the :gosub symbol (line 4). And we set  
the position where we want to jump (line 5). Actually we set the goto  
index – 1 (see the way we store the line index at line 9).

Saving the current position prepares the runtime for a later use when  
the interpreter meets the return statement.

01 class ReturnStatement  
02  
03 def execute runtime  
04  
05 gosub = runtime.restore\_pos(:gosub)  
06  
07 raise “UNMATCHED ‘GOSUB’ AT LINE #{@line}” unless gosub  
08  
09 end  
10  
11 end  
Testing the interpreter

The tests that validate the interpreter look like:

01  
02 require ‘test/unit’  
03 require ‘basic’  
04  
05 class TestBasic \< Test::Unit::TestCase  
06  
07 def test\_print\_one\_string  
08  
09 program = \<\<BASIC  
10 10 PRINT ‘HELLO’  
11 20 END  
12 BASIC  
13  
14 @basic.run program  
15  
16 assert\_equal 1, @console.lines.length  
17 assert\_equal [“HELLO”], @console.lines  
18  
19 end  
20  
21 end  
The test requires the unit test framework and the interpreter (line  
3). We call the interpreter, at line 14, with the program. Next we  
assert we printed out one line (at line 16) and the output content  
(line 17). The console attribute is a false console that stores all  
the printed lines. The interpreter needs a console and calls its print  
method. We create a test console.

01 class TestConsole  
02  
03 attr\_reader :lines  
04  
05 def initialize  
06 @lines = []  
07 end  
08  
09 def print line  
10 @lines \<\< line  
11 end  
12  
13 end  
The test setup creates the interpreter.

01 def setup  
02 @console = TestConsole.new  
03 @basic = BasicInterpreter.new(@console)  
04 end  
If the interpreter was as follow, the test would pass.

01 class BasicInterpreter  
02  
03 def initialize console  
04 @console = console  
05 end  
06  
07 def run program  
08 @console.print “HELLO”  
09 end  
10  
11 end

$\>ruby basic\_test.rb  
Loaded suite basic\_test  
Started  
E  
Finished in 0.000369 seconds.

1. Error:  
test\_print\_one\_string(TestBasic):  
NoMethodError: undefined method `run' for nil:NilClass basic_test.rb:14:in`test\_print\_one\_string’

1 tests, 0 assertions, 0 failures, 1 errors  
Using programs for tests

We wrote some basic programs that we can use to validate our  
interpreter in automated tests. By using the technique presented above  
and adding some more methods, the tests become even easier to read.  
Here if the factorial program.

10 REM  
15 REM COMPUTE FACTORIAL  
20 REM  
25 LET F = 1  
30 READ N  
31 LET X = N  
35 IF N = 0 THEN 55  
40 LET F = F \* N  
45 LET N = N - 1  
50 GOTO 35  
55 PRINT “FACT”, X, “IS”, F  
60 GOTO 25  
65 DATA 1, 3, 5, 6, 20  
99 END  
Here is the test that runs the factorial program.

01 class TestRunningBasicPrograms \< Test::Unit::TestCase  
02  
03 def test\_factorial  
04  
05 script ‘fact.bas’  
06  
07 expects ‘FACT’, 1, ‘IS’, 1  
08 expects ‘FACT’, 3, ‘IS’, 6  
09 expects ‘FACT’, 5, ‘IS’, 120  
10 expects ‘FACT’, 6, ‘IS’, 720  
11 expects ‘FACT’, 20, ‘IS’, 2432902008176640000  
12  
13 assert\_output\_as\_expected  
14  
15 end  
16  
17 end  
At line 5 we set the program file under test, from line 7 up to 11 we  
declare the expectations and the last line (line 13) checks the  
outcome.

Tests using the runtime

As the interpreter returns the runtime object, we can use it during  
the assertion phase.

01 def test\_1et  
02  
03 program = \<\<BASIC  
04 10 LET A = (23 + 5) / 2  
05 40 END  
06 BASIC  
07  
08 runtime = @basic.run(program)  
09  
10 assert\_equal 14, runtime[:A]  
11  
12 end  
We run the program and store the runtime in the runtime variable (line  
8). Then we assert that the value of the variable A of the program is  
the one expected, using the runtime object.

Test results

The code attached to this summary contain tests. Here is the tests  
results.

$\>ruby basic\_parser\_test.rb  
Loaded suite basic\_parser\_test  
Started  
…  
Finished in 0.008335 seconds.

13 tests, 56 assertions, 0 failures, 0 errors

$\>ruby basic\_test.rb  
Loaded suite basic\_test  
Started  
…  
Finished in 0.020823 seconds.

13 tests, 23 assertions, 0 failures, 0 errors  
You can download the code here.

Annex

Here is a BNF description of the language syntax.

::= {\n }  
 ::= | | | | | |  
 | |  
 | | | | | |  
  
 ::= LET =   
 ::= READ {, }  
 ::= DATA {, }  
 ::= PRINT | |   
 ::= GOTO   
 ::= IF THEN  
  
 ::= FOR = TO  
 [STEP]  
 ::= NEXT   
 ::= END  
 ::= STOP  
 ::= DEF FN () =   
 ::= GOSUB   
 ::= RETURN  
 ::= DIM () | (,  
)  
 ::=   
 ::= [] [() | (,  
)]  
 ::= “”  
 ::= \< | = | \> | \<= | \>= | \<\>  
 ::= []

Expressions may contain the following arithmetic operations: +, -, \*, /,  
^.

Basic has next built-in functions: SIN, COS, TAN, ATN, EXP, ABS, LOG,  
SQR, RND, INT