Delta: An Incremental Compiler
Step 16: For statements

Description

Add support for the for statement. It has the following syntax:

\( \; \; \; \; \texttt{for} \; \textit{loop-var} \; \texttt{=} \; \textit{start-expression} \; \texttt{upto} \; \textit{finish-expression} \; \texttt{\{} \; \)
\( \; \; \; \; \; \; \; \; \textit{statements} \)
\( \; \; \; \; \texttt{\} } \)

Note that \(\textit{loop-var}\) must be previously declared variable using a declaration statetment. The for statement is equivalent to:

\( \; \; \; \; \textit{loop-var} \; \texttt{=} \; \textit{start-expression} \texttt{;} \)
\( \; \; \; \; \texttt{while} \; \textit{loop-var} \; \texttt{<=} \; \textit{finish-expression} \; \texttt{\{} \; \)
\( \; \; \; \; \; \; \; \; \textit{statements} \)
\( \; \; \; \; \; \; \; \; \textit{loop-var} \; \texttt{=} \; \textit{loop-var} \texttt{ + 1;} \)
\( \; \; \; \; \texttt{\} } \)

Alternatively, the downto keyword can be used instead of upto so that \(\textit{loop-var}\) gets decremented in each iteration. Thus, the following syntax:

\( \; \; \; \; \texttt{for} \; \textit{loop-var} \; \texttt{=} \; \textit{start-expression} \; \texttt{downto} \; \textit{finish-expression} \; \texttt{\{} \; \)
\( \; \; \; \; \; \; \; \; \textit{statements} \)
\( \; \; \; \; \texttt{\} } \)

is equivalent to the following code:

\( \; \; \; \; \textit{loop-var} \; \texttt{=} \; \textit{start-expression} \texttt{;} \)
\( \; \; \; \; \texttt{while} \; \textit{loop-var} \; \texttt{>=} \; \textit{finish-expression} \; \texttt{\{} \; \)
\( \; \; \; \; \; \; \; \; \textit{statements} \)
\( \; \; \; \; \; \; \; \; \textit{loop-var} \; \texttt{=} \; \textit{loop-var} \texttt{ - 1;} \)
\( \; \; \; \; \texttt{\} } \)

Note that the body of the for statement might not be executed even once if the result of comparing \(\textit{loop-var}\) with \(\textit{finish-expression}\) is false (zero) from the start.

Make sure to consider for, upto, and downto as Delta reserved keywords from now on.

Example

The Delta program:

var r, i;
r = 1;
for i = 1 upto 5 {
    r = r * i;
}
r

should produce the following WAT code:

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

The above WAT function’s return value should be:

120

Unit Tests

# File: tests/test_16_for.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('for i = 1 upto {}')

    def test_semantic_mistake1(self):
        with self.assertRaises(SemanticMistake):
            self.c.realize('var for; 0')

    def test_semantic_mistake2(self):
        with self.assertRaises(SemanticMistake):
            self.c.realize('var upto; 0')

    def test_semantic_mistake3(self):
        with self.assertRaises(SemanticMistake):
            self.c.realize('var downto; 0')

    def test_for_fact(self):
        self.assertEqual(120,
                         self.c.realize(
                            '''
                            var r, i;
                            r = 1;
                            for i = 1 upto 5  {
                                r = r * i;
                            }
                            r
                            '''))

    def test_for_count_down(self):
        self.assertEqual(0,
                         self.c.realize(
                            '''
                            var i;
                            for i = 10 downto 1 {
                            }
                            i
                            '''))

    def test_for_skip_body(self):
        self.assertEqual(0,
                         self.c.realize(
                            '''
                            var i, s;
                            s = 0;
                            for i = 10 upto 1 {
                                s = s + 1;
                            }
                            s
                            '''))

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

    def test_for_nested(self):
        self.assertEqual(1500,
                         self.c.realize(
                            '''
                            var r, i, j, k;
                            r = 0;
                            for i = 1 upto 10 {
                                for j = 50 downto 1 {
                                    for k = 1 upto 3 {
                                        r = r + 1;
                                    }
                                }
                            }
                            r
                            '''))