pymdl

The pymdl book

13. Looping

10.1. PROG and REPEAT

PROG and REPEAT are almost identical FSUBRs which make it possible to vary the order of EVALuation arbitrarily -- that is, to have "jumps". The syntax of PROG ("program") is

<PROG act:atom aux:list body>

where

  • act is an optional ATOM, which is bound to the ACTIVATION of the PROG.
  • aux is a LIST which looks exactly like that part of a FUNCTION's argument LIST which follows an "AUX", and serves exactly the same purpose. It is not optional. If you need no temporary variables or "ACT", make it ().
  • body is a non-zero number of arbitrary MDL expressions.

The syntax of REPEAT is identical, except that, of course, REPEAT is the first element of the FORM, not PROG.

10.1.1. Basic EVALuation

Upon entering a PROG, an ACTIVATION is always generated. If there is an ATOM in the right place, the ACTIVATION is also bound to that ATOM. The variables in the aux (if any) are then bound as indicated in the aux. All of the expressions in body are then EVALuated in their order of occurrence. If nothing untoward happens, you leave the PROG upon evaluating the last expression in body, returning the value of that last expression.

PROG thus provides a way to package together a group of things you wish to do, in a somewhat more limited way than can be done with a FUNCTION. But PROGs are generally used for their other properties.

REPEAT acts in all ways exactly like a PROG whose last expression is <AGAIN>. The only way to leave a REPEAT is to explicitly use RETURN (or GO with a TAG -- section 10.4).

10.1.2. AGAIN and RETURN in PROG and REPEAT

Within a PROG or REPEAT, you always have a defined ACTIVATION, whether you bind it to an ATOM or not. [In fact the interpreter binds it to the ATOM LPROG\ !-INTERRUPTS ("last PROG"). The FSUBR BIND is identical to PROG except that BIND does not bind that ATOM, so that AGAIN and RETURN with no ACTIVATION argument will not refer to it. This feature could be useful within MACROs.]

If AGAIN is used with no arguments, it uses the ACTIVATION of the closest surrounding PROG or REPEAT within the current function (an error occurs if there is none) and re-starts the PROG or REPEAT without rebinding the aux variables, just the way it works in a FUNCTION. With an argument, it can of course re-start any Function (PROG or REPEAT or FUNCTION) within which it is embedded at run time.

As with AGAIN, if RETURN is given no ACTIVATION argument, it uses the ACTIVATION of the closest surrounding PROG or REPEAT within the current function and causes that PROG or REPEAT to terminate and return RETURN's first argument. If RETURN is given no arguments, it causes the closest surrounding PROG or REPEAT to return the ATOM T. Also like AGAIN, it can, with an ACTIVATION argument, terminate any Function within which it is embedded at run time.

<PROG () <RETURN>>                                              ⇒ T
<REPEAT ((I 0)) <SET I <+ .I 1>> <COND (<==? .I 3> <RETURN>)>>  ⇒ T
<BIND (X) 5>                                                    ⇒ 5

Found along the way. LPROG\ !-INTERRUPTS is a real ATOM on a real oblist, not a notation, and the backslash is part of its PNAME -- it is written that way precisely so no program can type it by accident. Chapter 18 has the trailer syntax that names it, and chapter 7's box has why an ATOM on INTERRUPTS is a different variable from one of the same spelling elsewhere. This is the mechanism behind "the closest surrounding PROG": there is no search of a stack, only an ordinary local value that each PROG rebinds and BIND does not.

10.1.3. Examples

Examples of the use of PROG are difficult to find, since it is almost never necessary, and it slows down the interpreter (chapter 27). PROG can be useful as a point of return from the middle of a computation, or inside a COND (which see), but we won't exemplify those uses. Instead, what follows is an example of a typically poor use of PROG which has been observed among Lisp (Moon, 1974) programmers using MDL. Then, the same thing is done using REPEAT. In both cases, the example FUNCTION just adds up all its arguments and returns the sum. (The SUBR GO is discussed in section 10.4.)

;"Lisp style"
<DEFINE MY+ ("TUPLE" TUP)
        <PROG (SUM)
                <SET SUM 0>
          LP    <COND (<EMPTY? .TUP> <RETURN .SUM>)>
                <SET SUM <+ .SUM <1 .TUP>>>
                <SET TUP <REST .TUP>>
                <GO LP>>>        ⇒ MY+
<MY+ 1 2 3>                      ⇒ 6
<MY+>                            ⇒ 0

;"MDL style"
<DEFINE MY+ ("TUPLE" TUP)
        <REPEAT ((SUM 0))
                <COND (<EMPTY? .TUP> <RETURN .SUM>)>
                <SET SUM <+ .SUM <1 .TUP>>>
                <SET TUP <REST .TUP>>>>   ⇒ MY+
<MY+ 1 2 3>                      ⇒ 6
<MY+>                            ⇒ 0

The manual's "MDL style" version is missing a > after the first SET SUM line, which would make the SET TUP an argument of the +; it is restored above.

Of course, neither of the above is optimal MDL code for this problem, since MY+ can be written using SEGMENT evaluation as

<DEFINE MY+ ("TUPLE" TUP) <+ !.TUP>>     ⇒ MY+
<MY+ 1 2 3>                              ⇒ 6

There are, of course, lots of problems which can't be handled so simply, and lots of uses for REPEAT.

10.2. MAPF and MAPR: Basics

MAPF ("map first") and MAPR ("map rest") are two SUBRs which take care of a majority of cases which require loops over data. The basic idea is the following:

Suppose you have a LIST (or other structure) of data, and you want to apply a particular function to each element. That is exactly what MAPF does: you give it the function and the structure, and it applies the function to each element of the structure, starting with the first.

On the other hand, suppose you want to change each element of a structure according to a particular algorithm. This can be done only with great pain using MAPF, since you don't have easy access to the structure inside the function: you have only the structure's elements. MAPR solves the problem by applying a function to RESTs of a structure: first to <REST structure 0>, then to <REST structure 1>, etc. Thus, the function can change the structure by changing its argument, for example, by a <PUT argument 1 something>. It can even PUT a new element farther down the structure, which will be seen by the function on subsequent applications.

Now suppose, in addition to applying a function to a structure, you want to record the results -- the values returned by the function -- in another structure. Both MAPF and MAPR can do this: they both take an additional function as an argument, and, when the looping is over, apply the additional function to all the results, and then return the results of that application. Thus, if the additional function is ,LIST, you get a LIST of the previous results; if it is ,VECTOR, you get a VECTOR of results; etc.

Finally, it might be the case that you really want to loop a function over more than one structure simultaneously. For instance, consider creating a LIST whose elements are the element-by-element sum of the contents of two other LISTs. Both MAPF and MAPR allow this; you can, in fact, give each of them any number of structures full of arguments for your looping function.

This was all mentioned because MAPF and MAPR appear to be complex when seen baldly, due to the fact that the argument descriptions must take into account the general case. Simpler, degenerate cases are usually the ones used.

A note on the manual's periods. Throughout this chapter the manual writes .LIST, .+, .STRING and .VECTOR where it means ,LIST, ,+, ,STRING and ,VECTOR -- the GVAL comma, not the LVAL period. The SUBRs are global values (section 4.2.3), so the period form would look for a local value that does not exist. Every example below is written with the comma, and that is the only change made to them.

10.2.1. MAPF

<MAPF finalf loopf s1 s2 ... sN>

where (after argument evaluation)

  • finalf is something applicable that evaluates all its arguments, or a FALSE;
  • loopf is something applicable to N arguments that evaluates all its arguments; and
  • s1 through sN are structured objects (any TYPE)

does the following:

  1. First, it applies loopf to N arguments: the first element of each of the structures. Then it RESTs each of the structures, and does the application again, looping until any of the structures runs out of elements. Each of the values returned by loopf is recorded in a TUPLE.
  2. Then, it applies finalf to all the recorded values simultaneously, and returns the result of that application. If finalf is a FALSE, the recorded values are "thrown away" (actually never recorded in the first place) and the MAPF returns only the last value returned by loopf. If any of the si structures is empty, so that loopf is never invoked, finalf is applied to no arguments; if finalf is a FALSE, MAPF returns #FALSE ().

That last sentence has two answers, and both are worth seeing:

<MAPF ,LIST ,+ '() '()>    ⇒ ()
<MAPF <> ,+ '() '()>       ⇒ #FALSE ()

10.2.2. MAPR

<MAPR finalf loopf s1 s2 ... sN>

acts just like MAPF, but, instead of applying loopf to NTHs of the structures -- that is, <NTH si 1>, <NTH si 2>, etc. -- it applies it to RESTs of the structures -- that is, <REST si 0>, <REST si 1>, etc.

10.2.3. Examples

Make the element-wise sum of two LISTs:

<MAPF ,LIST ,+ '(1 2 3 4) '(10 11 12 13)>      ⇒ (11 13 15 17)

Change a UVECTOR to contain double its values:

<SET UV '![5 6 7 8 9]>             ⇒ ![5 6 7 8 9!]
<MAPR <>
       #FUNCTION ((L) <PUT .L 1 <* <1 .L> 2>>)
       .UV>                        ⇒ ![18!]
.UV                                ⇒ ![10 12 14 16 18!]

The ![18!] is the MAPR returning the last value of loopf, because finalf was a FALSE -- and that last value is the last REST, which is why it prints as a one-element UVECTOR rather than as the whole thing.

Create a STRING from CHARACTERs:

<MAPF ,STRING 1 '["MODELING" "DEVELOPMENT" "LIBRARY"]>    ⇒ "MDL"

The loopf there is the FIX 1, applied to each STRING -- section 7.1.6's shorthand for NTH, doing real work.

Sum the squares of the elements of a UVECTOR:

<MAPF ,+ #FUNCTION ((N) <* .N .N>) '![3 4]>    ⇒ 25

A parallel assignment FUNCTION (note that the arguments to MAPF are of different lengths):

<DEFINE PSET ("TUPLE" TUP)
        <MAPF <>
              ,SET
              .TUP
              <REST .TUP </ <LENGTH .TUP> 2>>>>    ⇒ PSET
<PSET A B C 1 2 3>         ⇒ 3
.A                         ⇒ 1
.B                         ⇒ 2
.C                         ⇒ 3

That one repays study. The two structures are the whole TUPLE and its second half; MAPF stops when the shorter runs out, so SET is applied to (A 1), (B 2), (C 3) and then the pairing ends.

Note: it is easy to forget that finalf must evaluate its arguments, which precludes the use of an FSUBR. It is primarily for this reason that the SUBRs AND? and OR? were invented. As an example, the predicate =? could have been defined this way:

<DEFINE =? (A B)
        <COND (<MONAD? .A> <==? .A .B>)
              (<AND <NOT <MONAD? .B>>
                    <==? <TYPE .A> <TYPE .B>>
                    <==? <LENGTH .A> <LENGTH .B>>>
               <MAPF ,AND? ,=? .A .B>)>>

[By the way, the following shows how to construct a value that has the same TYPE as an argument.

<DEFINE MAP-NOT (S)
 <COND (<MEMQ <PRIMTYPE .S> '![LIST VECTOR UVECTOR STRING]>
        <CHTYPE <MAPF ,<PRIMTYPE .S> ,NOT .S>
                <TYPE .S>>)>>              ⇒ MAP-NOT
<MAP-NOT '(1 T 3)>                         ⇒ (#FALSE () #FALSE () #FALSE ())

It works because the ATOMs that name the common STRUCTURED PRIMTYPEs (LIST, VECTOR, UVECTOR and STRING) have as GVALs the corresponding SUBRs to build objects of those TYPEs.]

pymdl's own. "Have as GVALs the corresponding SUBRs" is the same fact chapter 7 makes usable in the other direction: a SUBR is nothing but an ATOM's initial global value, so it can be looked up by name at run time as here, and it can be replaced. <,<PRIMTYPE .S> ...> is that lookup written out, and it works here exactly as described.

10.3. More on MAPF and MAPR

10.3.1. MAPRET

MAPRET is a SUBR that enables the loopf being used in a MAPR or MAPF (and lexically within it, that is, not separated from it by a function call) to return from zero to any number of values as opposed to just one. For example, suppose a MAPF of the following form is used:

<MAPF ,LIST <FUNCTION (E) ...> ...>

Now suppose that the programmer wants to add no elements to the final LIST on some calls to the FUNCTION and add many on other calls to the FUNCTION. To accomplish this, the FUNCTION simply calls MAPRET with the elements it wants added to the LIST. More generally, MAPRET causes its arguments to be added to the final TUPLE of arguments to which the finalf will be applied.

Warning: MAPRET is guaranteed to work only if it is called from an explicit FUNCTION which is the second argument to a MAPF or MAPR. In other words, the second argument to MAPF or MAPR must be #FUNCTION (...) or <FUNCTION ...> if MAPRET is to be used.

Example: the following returns a LIST of all the ATOMs in an OBLIST (chapter 18):

<DEFINE ATOMS (OB)
        <MAPF ,LIST
              <FUNCTION (BKT) <MAPRET !.BKT>>
              .OB>>

Here is the same idea on a structure that needs no oblist, flattening one level:

<DEFINE FLAT (S)
        <MAPF ,LIST
              <FUNCTION (E)
                 <COND (<STRUCTURED? .E> <MAPRET !.E>)
                       (ELSE .E)>>
              .S>>                 ⇒ FLAT
<FLAT '(1 (2 3) 4)>                ⇒ (1 2 3 4)

10.3.2. MAPSTOP

MAPSTOP is the same as MAPRET, except that, after adding its arguments, if any, to the final TUPLE, it forces the application of finalf to occur, whether or not the structured objects have run out of objects. Example: the following copies the first ten (or all) elements of its argument into a LIST:

<DEFINE FIRST-TEN (STRUC "AUX" (I 10))
 <MAPF ,LIST
      <FUNCTION (E)
          <COND (<0? <SET I <- .I 1>>> <MAPSTOP .E>)>
          .E>
      .STRUC>>                     ⇒ FIRST-TEN
<FIRST-TEN '(1 2 3)>               ⇒ (1 2 3)
<FIRST-TEN '(1 2 3 4 5 6 7 8 9 10 11 12)>    ⇒ (1 2 3 4 5 6 7 8 9 10)

10.3.3. MAPLEAVE

MAPLEAVE is analogous to RETURN, except that it works in (lexically within) MAPF or MAPR instead of PROG or REPEAT. It flushes the accumulated TUPLE of results and returns its argument (optional, T by default) as the value of the MAPF or MAPR. (It finds the MAPF/MAPR that it should return from in the current binding of the ATOM LMAP\ !-INTERRUPTS ("last map").) Example: the following finds and returns the first non-zero element of its argument, or #FALSE () if there is none:

<DEFINE FIRST-N0 (STRUC)
        <MAPF <>
              <FUNCTION (X)
                <COND (<N==? .X 0> <MAPLEAVE .X>)>>
              .STRUC>>             ⇒ FIRST-N0
<FIRST-N0 '(0 0 7 0)>              ⇒ 7
<FIRST-N0 '(0 0)>                  ⇒ #FALSE ()

LMAP\ !-INTERRUPTS is the MAP analogue of LPROG\ !-INTERRUPTS in section 10.1.2, and it works the same way: an ordinary rebound local value, not a search. The default is visible too:

<MAPF <> <FUNCTION (X) <MAPLEAVE>> '(1 2)>    ⇒ T

10.3.4. Only two arguments

If MAPF or MAPR is given only two arguments, the iteration function loopf is applied to no arguments each time, and the looping continues indefinitely until a MAPLEAVE or MAPSTOP is invoked. Example: the following returns a LIST of the integers from one less than its argument to zero.

<DEFINE LNUM (N)
        <MAPF ,LIST
              <FUNCTION ()
                <COND (<0? <SET N <- .N 1>>> <MAPSTOP 0>)
                      (ELSE .N)>>>>          ⇒ LNUM
<LNUM 5>                                     ⇒ (4 3 2 1 0)

The manual writes the test as <=? <SET N <- .N 1>>>, a one-argument =?, which is TOO-FEW-ARGUMENTS-SUPPLIED; it is <0? ...>.

One principal use of this form of MAPF/MAPR involves processing input characters, in cases where you don't know how many characters are going to arrive. The example below demonstrates this, using SUBRs which are more fully explained in chapter 14. Another example can be found in chapter 16.

Example: the following FUNCTION reads characters from the current input channel until an $ (ESC) is read, and then returns what was read as one STRING. (The SUBR READCHR reads one character from the input channel and returns it. NEXTCHR returns the next CHARACTER which READCHR will return -- chapter 14.)

<DEFINE RDSTR ()
  <MAPF ,STRING
        <FUNCTION () <COND (<NOT <==? <NEXTCHR> <ASCII 27>>>
                            <READCHR>)
                           (T
                            <MAPSTOP>)>>>>   ⇒ RDSTR

<PROG () <READCHR> ;"Flush the ESC ending this input."
             <RDSTR>>$
ABC123<+ 3 4>$"ABC123<+ 3 4>"

That transcript is shown rather than run, because it depends on a terminal delivering an ESC; chapter 14 has how a CHANNEL is driven from a file instead.

10.3.5. STACKFORM

The FSUBR STACKFORM is archaic, due to improvements in the implementation of MAPF/MAPR, and it should not be used in new programs.

<STACKFORM function arg pred>

is exactly equivalent to

<MAPF function
      <FUNCTION () <COND (pred arg) (T <MAPSTOP>)>>>

In fact MAPF/MAPR is more powerful, because MAPRET, MAPSTOP, and MAPLEAVE provide flexibility not available with STACKFORM.

<STACKFORM ,LIST 1 <>>                         ⇒ ()
<SET I 0>                                      ⇒ 0
<STACKFORM ,LIST <SET I <+ .I 1>> <L? .I 4>>   ⇒ (1 2 3 4)

pymdl's own. "Archaic" in 1979, and still here, because the era's own compiler sources know it -- its name appears in three of them, so a program being compiled may still contain one. This is the book's general policy on deprecated things: an archaic SUBR is kept working and labelled, never removed, because the corpus of chapter 38 is the thing being run.

10.4. GO and TAG

GO is provided in MDL for people who can't recover from a youthful experience with Basic, Fortran, PL/I, etc. The SUBRs previously described in this chapter are much more tasteful for making good, clean, "structured" programs. GO just bollixes things.

GO is a SUBR which allows you to break the normal order of evaluation and re-start just before any top-level expression in a PROG or REPEAT. It can take two TYPEs of arguments: ATOM or TAG.

Given an ATOM, GO searches the body of the immediately surrounding PROG or REPEAT within the current Function, starting after aux, for an occurrence of that ATOM at the top level of body. (This search is effectively a MEMQ.) If it doesn't find the ATOM, an error occurs. If it does, evaluation is resumed at the expression following the ATOM.

<PROG () <SET X 0> LP <SET X <+ .X 1>> <COND (<L? .X 3> <GO LP>)> .X>   ⇒ 3

The SUBR TAG generates and returns objects of TYPE TAG. This SUBR takes one argument: an ATOM which would be a legal argument for a GO. An object of TYPE TAG contains sufficient information to allow you to GO to any top-level position in a PROG or REPEAT from within any function called inside the PROG or REPEAT. GO with a TAG is vaguely like AGAIN with an ACTIVATION; it allows you to "go back" to the middle of any PROG or REPEAT which called you. Also like ACTIVATIONs, TAGs into a PROG or REPEAT can no longer be used after the PROG or REPEAT has returned. LEGAL? can be used to see if a TAG is still valid.

<DEFINE TG () <PROG () <SET TT <TAG LP>> LP <RETURN <LEGAL? .TT>>>>   ⇒ TG
<TG>                       ⇒ T
<LEGAL? .TT>               ⇒ #FALSE ()

T inside, #FALSE () for the same TAG afterwards -- the same life story as the TUPLE of section 9.2.1 and the ACTIVATION of section 9.8.

10.5. Looping versus Recursion

Since any program in MDL can be called recursively, champions of "pure Lisp" (Moon, 1974) or somesuch may be tempted to implement any repetitive algorithm using recursion. The advantage of the looping techniques described in this chapter over recursion is that the overhead of calls is eliminated. However, a long program (say, bigger than half a printed page) may be more difficult to write iteratively than recursively and hence more difficult to maintain. A program whose repetition is controlled by a structured object (for example, "walking a tree" to visit each monad in the object) often should use looping for covering one "level" of the structure and recursion to change "levels".

pymdl's own. "The overhead of calls is eliminated" was measured on a PDP-10 and the ratio is not the same here, but the advice survives for a reason the manual could not have: pymdl's recursion sits on Python's, so a deeply recursive MDL program meets a ceiling in a place the era did not have one. A fresh interpreter raises Python's own limit well past its default for exactly this reason, and the evaluator carries a depth guard that reports runaway recursion as an MDL error rather than letting the host abort. Chapter 34's compiler is the other half of the advice, and it takes it literally: a REPEAT compiles to a Python loop, while recursion compiles to recursion.