10.9.7  Mutually Recursive Functions

Normally the Mythryl compiler processes the lines of each input file in reading order, left-to-right, top-to-bottom. Text as yet unseen has no effect upon the meaning of a statement. This semantics is a good match to what the human reader does, thus enhancing readability, and also supports interactive use by allowing Mythryl to evaluate expressions one by one as they are entered, rather than needing to see the entire input file before any output can be generated.

However, this semantics does not suffice for mutually recursive functions; somehow the compiler must be told that the first function in a mutually recursive set refers to as-yet unseen functions coming up, and thus that the compiler must postpone analysis until the complete set of mutually recursive functions has been read.

To do this Mythryl uses the reserved word also: Instead of closing the first mutually recursive function with a semicolon, it is connected to the next mutually recursive function with also.

As a simple contrived example, suppose that we wish to compute whether a list is of even or odd length using mutually recursive functions. A simpler way to do this would be to just use the existing list::length function and test the low bit of the result:

    linux$ cat my-script
    #!/usr/bin/mythryl

    fun list_length_is_odd  some_list
        =
        ((list::length some_list) & 1) == 1;

    printf "list_length_is_odd [1, 2] = %s\n"    (list_length_is_odd [1, 2]    ?? "TRUE" :: "FALSE");
    printf "list_length_is_odd [1, 2, 3] = %s\n" (list_length_is_odd [1, 2, 3] ?? "TRUE" :: "FALSE");

    linux$ ./my-script
    list_length_is_odd [1, 2] = FALSE
    list_length_is_odd [1, 2, 3] = TRUE

But we want to do it the hard way:

    linux$ cat my-script
    #!/usr/bin/mythryl

    fun list_length_is_odd  some_list
        =
        even_helper some_list
        where
            fun even_helper []          => FALSE;
                even_helper (a ! rest)  =>  odd_helper rest;
            end

            also
            fun  odd_helper []          => TRUE;
                 odd_helper (a ! rest)  => even_helper rest;
            end;
        end;

    printf "list_length_is_odd [1, 2] = %s\n"    (list_length_is_odd [1, 2]    ?? "TRUE" :: "FALSE");
    printf "list_length_is_odd [1, 2, 3] = %s\n" (list_length_is_odd [1, 2, 3] ?? "TRUE" :: "FALSE");

    linux$ ./my-script
    list_length_is_odd [1, 2] = FALSE
    list_length_is_odd [1, 2, 3] = TRUE

Here our two mutually recursive helper functions even_helper and odd_helper remember whether we have currently seen an even or odd number of nodes in the list, according to which is currently executing, and respectively return FALSE or TRUE when the end of the list is reached.

To signal the mutual recursion, even_helper lacks a terminal semicolon, instead being linked to odd_helper by the also reserved word.