26. Efficiency and tastefulness

24.1. Efficiency

Actually, you make MDL programs efficient by thinking hard about what they really make the interpreter do, and making them do less. Some guidelines, in order of decreasing expense:

1. Free storage is expensive.
2. Calling functions is expensive.
3. PROG and REPEAT are expensive, except when compiled.

Explanation:

1. Unnecessary use of free storage (creating needless LISTs, VECTORs, UVECTORs, etc.) will cause the garbage collector to run more often. This is expensive! A fairly large MDL (for example, 60,000 36-bit words) can take ten seconds of PDP-10 CPU time for a garbage collection. Be especially wary of constructions like (0). Every time that is evaluated, it creates a new one-element LIST; it is too easy to write such things when they aren't really necessary. Unless you are doing PUTs or PUTRESTs on it, use '(0) instead.
2. Sad, but true. Also generally ignored. If you call a function only once, or if it is short (less than one line), you are much better off in speed if you substitute its body in by hand. On the other hand, you may be much worse off in modularity. There are techniques for combining several FUNCTIONs into one RSUBR (with RSUBR-ENTRYs), either during or after compilation, and for changing FUNCTIONs into MACROs.
3. PROG is almost never necessary, given (a) "AUX" in FUNCTIONs; (b) the fact that FUNCTIONs can contain any number of FORMs; (c) the fact that COND clauses can contain any number of FORMs; and (d) the fact that new variables can be generated and initialized by REPEAT. However, PROG may be useful when an error occurs, to establish bindings needed for cleaning things up or interacting with a human.

pymdl's own. Guideline 1 survives the change of machine with its sign intact and its magnitude changed. Python allocates too, and a program that builds a fresh LIST per iteration still makes work -- but the ten seconds is gone, and with it the reason to contort a program around it. What is not gone is the part of the advice that was never really about speed: '(0) and (0) differ in whether the object is shared, and chapter 10's sharing rules make that a correctness question. Write '(0) because you mean a constant, and take the efficiency as a bonus.

Guideline 3 inverts here. PROG and REPEAT are not especially expensive in pymdl, and chapter 13's box notes that a REPEAT is what the compiler turns into a Python loop while recursion stays recursion -- so on deep iteration a REPEAT is the cheap choice, not the dear one. The stylistic half of guideline 3 stands unchanged: PROG is almost never necessary, for the four reasons given.

The use of PROG may be sensible when the normal flow of control can be cut short by unusual conditions, so that the program wants to RETURN before reaching the end of PROG. Of course, nested CONDs can accomplish the same end, but deep nesting may tend to make the program unreadable. For example:

<PROG (TEMP)
      <OR <SET TEMP <OK-FOR-STEP-1?>>
          <RETURN .TEMP>>
      <STEP-1>
      <OR <SET TEMP <OK-FOR-STEP-2?>>
          <RETURN .TEMP>>
      <STEP-2>>

could instead be written

<DEFINE OK-FOR-STEP-1? () T>       ⇒ OK-FOR-STEP-1?
<DEFINE STEP-1 () DID-1>           ⇒ STEP-1
<DEFINE OK-FOR-STEP-2? () T>       ⇒ OK-FOR-STEP-2?
<DEFINE STEP-2 () DID-2>           ⇒ STEP-2
<COND (<OK-FOR-STEP-1?>
       <STEP-1>
       <COND (<OK-FOR-STEP-2?>
              <STEP-2>)>)>         ⇒ DID-2

Note what the COND version gives up: chapter 11's rule says a failing COND answers the last FALSE it saw, so the "why did it stop" information the PROG version RETURNed by hand comes back anyway, for free.

By the way, REPEAT is faster than GO in a PROG. The <GO x> FORM has to be separately interpreted, right? In fact, if you organize things properly you very seldom need a GO; using GO is generally considered "bad style", but in some cases it's needed. Very few.

In many cases, a REPEAT can be replaced with a MAPF or MAPR, or an ILIST, IVECTOR, etc. of the form

<SET X 0>                  ⇒ 0
<ILIST 5 '<SET X <+ .X 1>>>    ⇒ (1 2 3 4 5)

which generates an N-element LIST of successive numbers starting at X+1. (The manual's version of that line is missing its closing >.)

Whether a program is interpreted or compiled, the first two considerations mentioned above hold: garbage collection and function calling remain expensive. Garbage collection is, clearly, exactly the same. Function calling is relatively more expensive. However, the compiler careth not whether you use REPEAT, GO, PROG, ILIST, MAPF, or whatnot: it all gets compiled into practically the same thing. However, the REPEAT or PROG will be slower if it has an ACTIVATION that is SPECIAL or used other than by RETURN or AGAIN.

24.1.1. Example

There follows an example of a FUNCTION that does many things wrong. It is accompanied by commentary, and two better versions of the same thing. (This function actually occurred in practice. Needless to say, names are withheld to protect the guilty.)

Blunt comment: this is terrible. Its purpose is to output the characters needed by a graphics terminal to draw lines connecting a set of points. The points are specified by two input lists: X values and Y values. The output channel is the third argument. The actual characters for each line are returned in a LIST by the function TRANS.

<DEFINE PLOTVDSK (X Y CHN "AUX" L LIST)
   <COND (<NOT <==? <SET L <LENGTH .X>><LENGTH .Y> >>
          <ERROR "LENGTHS NOT EQUAL">)>
   <SET LIST (29)>
   <REPEAT ((N 1))
       <SET LIST (!.LIST !<TRANS <.N .X> <.N .Y>>)>
       <COND (<G? <SET N <+ .N 1>> .L><RETURN .N>)> >
   <REPEAT ((N 1) (L1 <LENGTH .LIST>))
       <PRINC <ASCII <.N .LIST>> .CHN>
       <COND (<G? <SET N <+ .N 1>> .L1>
              <RETURN "DONE">)> >>

Comments:

1. LIST is only temporarily necessary. It is just created and then thrown away.
2. Worse, the construct (!.LIST !<TRANS ...>) copies the previous elements of LIST every time it is executed!
3. Indexing down the elements of LIST as in <.N .LIST> takes a long time, if the LIST is long. <3 ...> or <4 ...> is not worth worrying about, but <10 ...> is, and <100 ...> takes quite a while. Even if the indexing were not phased out, the compiler would be happier with <NTH .LIST .N>.
4. The variable CHN is unnecessary if OUTCHAN is bound to the argument CHANNEL.
5. It is tasteful to call ERROR in the same way that F/SUBRs do. This includes using an ATOM from the ERRORS OBLIST (if one is appropriate) to tell what is wrong, and it includes identifying yourself.

Comment 2 is chapter 10's section 7.7.4 turned into a bug report, and it is the one to internalize: a trailing LIST segment is free, a leading one copies. (!.LIST !<TRANS ...>) puts the growing LIST first, so every iteration copies everything accumulated so far. Comment 5 is chapter 19's section 16.2 as a style rule, and it is why every error in this book names an ATOM on the ERRORS oblist and the SUBR that complained.

So, do it this way:

<DEFINE PLOTVDSK (X Y OUTCHAN)
  #DECL ((OUTCHAN) <SPECIAL CHANNEL>)
  <COND (<NOT <==? <LENGTH .X> <LENGTH .Y>>>
         <ERROR VECTOR-LENGTHS-DIFFER!-ERRORS PLOTVDSK>)>
  <PRINC <ASCII 29>>
  <REPEAT ()
          <COND (<EMPTY? .X> <RETURN "DONE">)>
          <REPEAT ((OL <TRANS <1 .X> <1 .Y>>))
                  <PRINC <ASCII <1 .OL>>>
                  <COND (<EMPTY? <SET OL <REST .OL>>>
                         <RETURN>)>>
          <SET X <REST .X>>
          <SET Y <REST .Y>>>>

Of course, if you know how long is the LIST that TRANS returns, you can avoid using the inner REPEAT loop and have explicit PRINCs for each element. This can be done even better by using MAPF, as in the next version, which does exactly the same thing as the previous one, but uses MAPF to do the RESTing and the end conditional:

<DEFINE PLOTVDSK (X Y OUTCHAN)
  #DECL ((OUTCHAN) <SPECIAL CHANNEL>)
  <COND (<NOT <==? <LENGTH .X> <LENGTH .Y>>>
         <ERROR VECTOR-LENGTHS-DIFFER!-ERRORS PLOTVDSK>)>
  <PRINC <ASCII 29>>
  <MAPF <>
        #FUNCTION ((XE YE)
                   <MAPF <> #FUNCTION (TE <PRINC <ASCII .TE>>) <TRANS .XE .YE>>)
        .X
        .Y>
  "DONE">

All three versions are shown rather than run, since TRANS and the graphics terminal are both absent. The manual writes the DECL in both improved versions as #DECL ((OUTCHAN <SPECIAL CHANNEL>), which is unbalanced and puts the Pattern inside the ATOM LIST; section 14.3's syntax wants ((OUTCHAN) <SPECIAL CHANNEL>), as above. The final MAPF's inner FUNCTION also binds a variable named T in the manual, which chapter 11 shows is a perfectly ordinary ATOM but a poor choice of name; it is TE above.

pymdl's own. The <SPECIAL CHANNEL> on OUTCHAN is the single most reusable thing in this chapter, and chapter 14's section 11.2.7 explains why: rebinding OUTCHAN in the argument LIST redirects every output SUBR in the body with no further ceremony, and the SPECIAL is what makes it survive compilation. Chapter 17's box has the general rule.

24.2. Creating a LIST in Forward Order

If you must create the elements of a LIST in sequence from first to last, you can avoid copying earlier ones when adding a later one to the end. One way is to use MAPF or MAPR with a first argument of ,LIST: the elements are put on the control stack rather than in free storage, until the final call to LIST. If you know how many elements there will be, you can put them on the control stack yourself, in a TUPLE built for that purpose. Another way is used when REPEAT is necessary:

<REPEAT ((FIRST (T)) (LAST .FIRST) (N 0))
        #DECL ((VALUE FIRST LAST) LIST (N) FIX)
        <SET N <+ .N 1>>
        <SET LAST <REST <PUTREST .LAST (.N)>>>
        <COND (<==? .N 4> <RETURN <REST .FIRST>>)>>   ⇒ (1 2 3 4)

Here, .LAST always points to the current last element of the LIST. Because of the order of evaluation, the <SET LAST ...> could also be written <PUTREST .LAST <SET LAST (.NEW)>>. (The manual prints that alternative with a mismatched bracket.)

pymdl's own. This idiom is the payoff for chapter 10's two hardest facts, and it is worth naming them: PUTREST changes the LIST in place rather than building a new one, and REST shares rather than copies, so .FIRST sees everything .LAST appends without ever being touched. The (T) at the start is a throwaway head that <REST .FIRST> discards at the end. pymdl reproduces all of it, which it must, since the era's own programs are written this way.

24.3. Read-only Free Variables

If a Function uses the value of a free variable (<GVAL unmanifest:atom> or <LVAL special:atom>) without changing it, the compiled version may be more efficient if the value is assigned to a dummy UNSPECIAL ATOM in the Function's "AUX" list. This is true because an UNSPECIAL ATOM gets compiled into a slot on the control stack, which is accessible very quickly. The tradeoff is probably worthwhile if a special is referenced more than once, or if an unmanifest is referenced more than twice. Example:

<SETG DATA-BASE (A B C)>   ⇒ (A B C)
<DEFINE MAP-LOOKUP (THINGS "AUX" (DB ,DATA-BASE))
        #DECL ((VALUE) VECTOR (THINGS DB) <UNSPECIAL <PRIMTYPE LIST>>)
        <MAPF ,VECTOR <FUNCTION (TE) <MEMQ .TE .DB>> .THINGS>>   ⇒ MAP-LOOKUP
<MAP-LOOKUP '(B Z)>        ⇒ [(B C) #FALSE ()]

(The manual's inner FUNCTION again binds T; TE above.) The answer shows MEMQ returning a REST for the element it found and a FALSE for the one it did not, gathered into a VECTOR by the finalf -- section 10.2.1 and section 8.2.2 doing a day's work between them.

24.4. Global and Local Values

In the interpreter the sequence ,X .X ,X .X is slower than ,X ,X .X .X because of interference between the GVAL and LVAL mechanisms (appendix H). Thus it is not good to use both the GVAL and LVAL of the same ATOM frequently, unless references to the LVAL will be compiled away (made into control stack references).

pymdl's own. This one is genuinely obsolete: the interference it describes was a cache in the era's atom block, and pymdl has no such cache, so alternating costs nothing here. It is left in because it explains a shape you will meet in era sources -- a program that hoists ,X into an "AUX" variable for no visible reason is obeying this paragraph. Chapter 7's two orders are the part of that story that is still live.

24.5. Making Offsets for Arrays

It is often the case that you want to attach some meaning to each element of an array and access it independently of other elements. Firstly, it is a good idea to use names (ATOMs) rather than integers (FIXes or even OFFSETs) for offsets into the array, to make future changes easier. Secondly, it is a good idea to use the GVALs of the name ATOMs to remember the actual FIXes, so that the ATOMs can be MANIFEST for the compiler's benefit. Thirdly, to establish the GVALs, both the interpreter and the compiler will be happier with <SETG name offset> rather than <DEFINE name ("TUPLE" T) <offset !.T>>.

<SETG NAME-OFFSET 2>       ⇒ 2
<MANIFEST NAME-OFFSET>     ⇒ T
<NAME-OFFSET '[A B C]>     ⇒ B

That last line is the whole recipe working: the ATOM is a MANIFEST FIX, and applying it indexes the array by section 7.1.6's shorthand. A program written this way reads as <NAME-OFFSET .RECORD> rather than <2 .RECORD>, and changing the layout is one SETG.

24.6. Tables

There are several ways in MDL to store a table, that is, a collection of (names and) values that will be searched. Unsurprisingly, choosing the best way is often dictated by the size of the table and/or the nature of the (names and) values.

For a small table, the names and values can be put in (separate) structures -- the choice of LIST or array being determined by volatility and limitability -- which are searched using MEMQ or MEMBER. This method is very space-efficient. If the table gets larger, and if the elements are completely orderable, a (uniform) vector can be used, kept sorted, and searched with a binary search.

For a large table, where reasonably efficient searches are required, a hashing scheme is probably best. Two methods are available in MDL: associations and OBLISTs.

In the first method, PUTPROP and GETPROP are used, which are very fast. The number of hashing buckets is fixed. Duplicates are eliminated by ==? testing. If it is necessary to use =? testing, or to find all the entries in the table, you can duplicate the table in a LIST or array, to be used only for those purposes.

In the second method, INSERT and LOOKUP on a specially-built OBLIST are used. (If the names are not STRINGs, they can be converted to STRINGs using UNPARSE, which takes a little time.) The number of hashing buckets can be chosen for best efficiency. Duplicates are eliminated by =? testing. MAPF/MAPR can be used to find all the entries in the table.

<MOBLIST TBL 13>
<INSERT "KEY" <GET TBL OBLIST>>            ⇒ KEY!-TBL
<LOOKUP "KEY" <GET TBL OBLIST>>            ⇒ KEY!-TBL
<LOOKUP "NO-SUCH" <GET TBL OBLIST>>        ⇒ #FALSE ()

The !-TBL trailer is chapter 18's printing rule reporting that the ATOM lives somewhere off the search path -- which is exactly what you want from a table.

pymdl's own. The choice between the two hashing methods turns on the ==?/=? difference of section 8.2.2, and that difference is real here, so the advice transfers directly. What has changed is the reason to care about bucket counts: MOBLIST's prime-number argument tuned a real hash table on a real machine, and pymdl's oblists do not need the help. Ask for whatever number makes the OBLIST print legibly.

Both methods are in use in this book's own machinery. Chapter 16's box found the interrupt system keeping its handler table by association; chapter 18's section 15.8 and chapter 30's library are the OBLIST method at full scale.

24.7. Nesting

The beauty of deeply-nested control structures in a single FUNCTION is definitely in the eye of the beholder. (PPRINT, a preloaded RSUBR, finds them trying. However, the compiler often produces better code from them.) If you don't like excessive nesting, then you will agree that

<SET X ...>
<COND (<0? .X> ...) ...>

looks better than

<COND (<0? <SET X ...>> ...) ...>

and that

<REPEAT ...
        <COND ...
              (... <RETURN ...>)>
        ...
        ...>

looks better than

<REPEAT ...
        <COND ...
              (... <RETURN ...>)
              (ELSE ...)>
        ...>

You can see the nature of the choices. Nesting is still and all better than GO.

pymdl's own. It is a fitting end to the language manual that its last word is a matter of taste, offered without a ruling. The one thing this book can add is that the parenthetical about PPRINT is still true and still checkable: chapter 29's pretty-printer is the same program, and feeding it a deeply nested FUNCTION still produces something trying.

Part III picks up where this leaves off, with the second manual -- the one about the environment a program is written in rather than the language it is written in -- and Part IV with the machine underneath.