[QUIZ] Ruby BASIC (#228)

Discussion in 'Ruby' started by Daniel Moore, Jan 30, 2010.

  1. Daniel Moore

    Daniel Moore Guest

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

    The three rules of Ruby Quiz:

    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 Quiz 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 Talk follow the discussion. Please reply to
    the original quiz message, if you can.

    - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

    RSS Feed: http://rubyquiz.strd6.com/quizzes.rss

    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], 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].

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

    Have fun!

    [1]: http://rubyquiz.strd6.com/quizzes/223
    [2]: http://en.wikipedia.org/wiki/Dartmouth_BASIC#Keywords
    --
    -Daniel
    http://rubyquiz.strd6.com
    Daniel Moore, Jan 30, 2010
    #1
    1. Advertising

  2. Daniel Moore

    Daniel Moore Guest

    [QUIZ][SUMMARY] Ruby BASIC (#228)

    This summary was written by Jean Lazarou.
    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=92s 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 =3D 0
    20 LET X =3D X + 1
    30 PRINT X, SQR(X)
    40 IF X <=3D 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 =3D~ /^(\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=92s 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 =3D {
    02 'DATA' =3D> :parse_data,
    03 'END' =3D> :parse_end,
    04 'FOR' =3D> :parse_for,
    05 'GOSUB' =3D> :parse_gosub,
    06 'GOTO' =3D> :parse_goto,
    07 'IF' =3D> :parse_if,
    08 'LET' =3D> :parse_let,
    09 'NEXT' =3D> :parse_next,
    10 'PRINT' =3D> :parse_print,
    11 'READ' =3D> :parse_read,
    12 'REM' =3D> :parse_rem,
    13 'RETURN' =3D> :parse_return,
    14 'STOP' =3D> :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 =3D 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 (<=3D>). 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 =3D nil
    06 @line, @type, @arguments =3D line, type, arguments
    07 end
    08
    09 def <=3D> 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 =3D BasicScanner.new(arguments)
    04
    05 scanner.skip_spaces
    06 to_line =3D 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=92t 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 =3D @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 =3D @parser.parse_expression('SQR(4) + INT(Y/2) * 3')
    02 assert_equal [4, 'SQR', :Y, 2, '/', 'INT', 3, '*', '+'], expr.to_postf=
    ix
    Testing that spaces are optional.

    01 def test_program_witout_spaces
    02
    03 program =3D <<PROGRAM
    04 10PRINT"HELLO"
    05 20END
    06 PROGRAM
    07
    08 statements =3D @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 =96 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=92s variables and the program
    position. Here is the main loop of the interpreter.

    01 def run_statements statements
    02
    03 runtime =3D create_runtime(statements)
    04
    05 while runtime.running?
    06
    07 statement =3D statements[runtime.program_pos]
    08
    09 statement.execute(runtime)
    10
    11 runtime.program_pos +=3D 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 []=3D 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=92s array of statements, not the source code line number.

    The next_data returns the sequence of data or nil when all the data is cons=
    umed.

    The end method puts the state to program ended.

    The print method is used by the PRINT statement.

    The [], []=3D and each_var give access to the current values of the
    program=92s 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=3D message, needed to set
    the actual program position.

    Turn the Statement objects into runnable objects=85

    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 =3D @to_program_pos
    06 end
    07
    08 def program_pos=3D line
    09 @to_program_pos =3D 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 =96 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 =3D 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 =3D <<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 =3D []
    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 =3D TestConsole.new
    03 @basic =3D 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 =3D 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 =3D 1
    30 READ N
    31 LET X =3D N
    35 IF N =3D 0 THEN 55
    40 LET F =3D F * N
    45 LET N =3D 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 =3D <<BASIC
    04 10 LET A =3D (23 + 5) / 2
    05 40 END
    06 BASIC
    07
    08 runtime =3D @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.



    <program> ::=3D <statement> {\n <statement>}
    <statement> ::=3D <let> | <read> | <data> | <print> | <goto> | <if> |
    <for> | <next> |
    <end> | <stop> | <def> | <gosub> | <return> | <dim> | <r=
    em>
    <let> ::=3D LET <variable> =3D <expression>
    <read> ::=3D READ <variable> {, <variable>}
    <data> ::=3D DATA <number> {, <number>}
    <print> ::=3D PRINT <label> | <label> <expression> | <expression>
    <goto> ::=3D GOTO <line-number>
    <if> ::=3D IF <expression> <relational> <expression> THEN <line-n=
    umber>
    <for> ::=3D FOR <unsubscripted-var> =3D <expression> TO
    <expression> [STEP <expression>]
    <next> ::=3D NEXT <unsubscripted-var>
    <end> ::=3D END
    <stop> ::=3D STOP
    <def> ::=3D DEF FN <letter> (<unsubscripted-var>) =3D <expression>
    <gosub> ::=3D GOSUB <line-number>
    <return> ::=3D RETURN
    <dim> ::=3D DIM <letter>(<integer>) | <letter>(<integer>, <integer=
    >)

    <rem> ::=3D <string>
    <variable> ::=3D <letter> [<digit>] [(<integer>) | (<integer>, <integer=
    >)]

    <label> ::=3D "<string>"
    <relational> ::=3D < | =3D | > | <=3D | >=3D | <>
    <unsubscripted-var> ::=3D <letter> [<digit>]

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

    Basic has next built-in functions: SIN, COS, TAN, ATN, EXP, ABS, LOG,
    SQR, RND, INT
    Daniel Moore, Apr 20, 2010
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ruby Quiz

    [QUIZ] Animal Quiz (#15)

    Ruby Quiz, Jan 14, 2005, in forum: Ruby
    Replies:
    11
    Views:
    347
    James Edward Gray II
    Jan 18, 2005
  2. David Tran
    Replies:
    9
    Views:
    174
    David Tran
    Jan 21, 2005
  3. Ruby Quiz

    [QUIZ] 1-800-THE-QUIZ (#20)

    Ruby Quiz, Feb 18, 2005, in forum: Ruby
    Replies:
    15
    Views:
    314
    gabriele renzi
    Feb 24, 2005
  4. Daniel Moore
    Replies:
    10
    Views:
    292
    James Gray
    Jan 31, 2009
  5. paleywiener
    Replies:
    3
    Views:
    371
    paleywiener
    Mar 9, 2012
Loading...

Share This Page