Compiler Design

Delta: An Incremental Compiler
Step 13: While statements

Description

Add support for while statements. This kind of statement should start with the while keyword, followed by an expression (the condition), followed by a list of zero or more statements enclosed inside curly braces (the body). If the condition evaluates to true (any non-zero value) the body is executed and afterwards the condition is evaluated again. The loop stops when the condition evaluates to false (zero).

Make sure to consider while as a Delta reserved keyword from now on.

Example

The Delta program:

var n, r, i;
n = 5;
r = 1;
i = 0;
while n - i {
    i = i + 1;
    r = r * i;
}
r

should produce the following WAT code:

(module
  (func
    (export "_start")
    (result i32)
    (local $n i32)
    (local $r i32)
    (local $i i32)
    i32.const 5
    local.set $n
    i32.const 1
    local.set $r
    i32.const 0
    local.set $i
    block
    loop
    local.get $n
    local.get $i
    i32.sub
    i32.eqz
    br_if 1
    local.get $i
    i32.const 1
    i32.add
    local.set $i
    local.get $r
    local.get $i
    i32.mul
    local.set $r
    br 0
    end
    end
    local.get $r
  )
)

The above WAT function’s return value should be:

120

Unit Tests

# File: tests/test_13_while.py

from unittest import TestCase
from delta import Compiler, SyntaxMistake
from delta.semantics import SemanticMistake


class TestWhile(TestCase):

    def setUp(self):
        self.c = Compiler('program_start')

    def test_syntax_mistake(self):
        with self.assertRaises(SyntaxMistake):
            self.c.realize('while {}')

    def test_semantic_mistake(self):
        with self.assertRaises(SemanticMistake):
            self.c.realize('var while; 0')

    def test_while_zero(self):
        self.assertEqual(0,
                         self.c.realize(
                            '''
                            var x, y;
                            x = 0;
                            y = 0;
                            while x {
                                x = x - 1;
                                y = 1;
                            }
                            x + y
                            '''))

    def test_while_fact(self):
        self.assertEqual(120,
                         self.c.realize(
                            '''
                            var n, r, i;
                            n = 5;
                            r = 1;
                            i = 0;
                            while n - i {
                                i = i + 1;
                                r = r * i;
                            }
                            r
                            '''))

    def test_while_count_down(self):
        self.assertEqual(0,
                         self.c.realize(
                            '''
                            var i;
                            i = 10;
                            while i {
                                i = i - 1;
                            }
                            i
                            '''))

    def test_while_skip_body(self):
        self.assertEqual(10,
                         self.c.realize(
                            '''
                            var n;
                            n = 10;
                            while !n {
                                n = n - 1;
                            }
                            n
                            '''))

    def test_while_fibo(self):
        self.assertEqual(55,
                         self.c.realize(
                            '''
                            var n, a, b;
                            n = 10;
                            a = 0;
                            b = 1;
                            while n {
                                var t;
                                t = b;
                                b = a + b;
                                a = t;
                                n = n - 1;
                            }
                            a
                            '''))

    def test_while_nested(self):
        self.assertEqual(1500,
                         self.c.realize(
                            '''
                            var r, i;
                            r = 0;
                            i = 10;
                            while i {
                                var j;
                                j = 50;
                                while j {
                                    var k;
                                    k = 3;
                                    while k {
                                        r = r + 1;
                                        k = k - 1;
                                    }
                                    j = j - 1;
                                }
                                i = i - 1;
                            }
                            r
                            '''))