11. Truth

8.1. Truth Values

MDL represents "false" with an object of a particular TYPE: TYPE FALSE (unsurprisingly). TYPE FALSE is structured: its PRIMTYPE is LIST. Thus, you can give reasons or excuses by making them elements of a FALSE. (Again, EVALing a FALSE neither copies it nor EVALs its elements, so it is not necessary to QUOTE a FALSE appearing in a program.) Objects of TYPE FALSE are represented in "# notation":

#FALSE list-of-its-elements

The empty FORM evaluates to the empty FALSE:

<>                         ⇒ #FALSE ()
<TYPE <>>                  ⇒ FALSE
<TYPEPRIM FALSE>           ⇒ LIST
#FALSE (BECAUSE)           ⇒ #FALSE (BECAUSE)

Anything which is not FALSE, is, reasonably enough, true. In this document the "data type" false-or-any in metasyntactic variables means that the only significant attribute of the object in that context is whether its TYPE is FALSE or not.

pymdl's own. A FALSE carrying its reasons is not decoration; it is how nearly every refusal in this book is reported. The compiler answers #FALSE ("a QUOTEd parameter") when it will not compile a FUNCTION (chapter 34), the package system answers a FALSE naming the package it could not find (chapter 30), and an era RSUBR that fails to load says so the same way. Because a FALSE is a LIST, <1 <COMPILE ...>> reads the reason out with no special machinery.

8.2. Predicates

There are numerous MDL F/SUBRs which can return a FALSE or a true. See appendix A to find them all. Most return either #FALSE () or the ATOM with PNAME T. (The latter is for historical reasons, namely Lisp (Moon, 1974).) Some predicates which are meaningful now are described next.

Found along the way. T is not a constant, a keyword, or a global. It is an ordinary ATOM with no value at all -- and an ATOM with no value, evaluated on its own, is itself (chapter 9). That is the whole mechanism:

T                          ⇒ T
<TYPE T>                   ⇒ ATOM
<GASSIGNED? T>             ⇒ #FALSE ()
<ASSIGNED? T>              ⇒ #FALSE ()

Which explains something section 8.3.1 does otherwise unannounced: its factorial writes (ELSE ...) for the catch-all clause and never defines ELSE anywhere. It does not need to. ELSE is also an unbound ATOM, also evaluates to itself, and is also not FALSE, so it succeeds for exactly the same reason T does, and any other unbound ATOM would serve as well.

8.2.1. Arithmetic

<0? fix-or-float>

evaluates to T only if its argument is identically equal to 0 or 0.0.

<1? fix-or-float>

evaluates to T only if its argument is identically equal to 1 or 1.0.

<G? n:fix-or-float m:fix-or-float>

evaluates to T only if n is algebraically greater than m. L=? is the Boolean complement of G?; that is, it is T only if n is not algebraically greater than m.

<L? n:fix-or-float m:fix-or-float>

evaluates to T only if n is algebraically less than m. G=? is the Boolean complement of L?.

<0? 0>                     ⇒ T
<0? 0.0>                   ⇒ T
<1? 1.0>                   ⇒ T
<G? 3 2>                   ⇒ T
<L=? 3 2>                  ⇒ #FALSE ()
<L? 2 3>                   ⇒ T
<G=? 2 3>                  ⇒ #FALSE ()

Note that there are four names and only two SUBRs' worth of comparison here: L=? is G? complemented and G=? is L? complemented. There is no E?; equality is the next section's business.

8.2.2. Equality and Membership

<==? e1:any e2:any>

evaluates to T only if e1 is the same object as e2 (appendix H). Two objects that look the same when PRINTed may not be ==?. Two FIXes of the same "value" are "the same object"; so are two FLOATs of exactly the same "value". Empty objects of PRIMTYPE LIST (and no other structured PRIMTYPE) are ==? if their TYPEs are the same. Example:

<==? <SET X "RANDOM STRING"> <TOP <REST .X 6>>>    ⇒ T
<==? .X "RANDOM STRING">                           ⇒ #FALSE ()
<==? () ()>                                        ⇒ T
<==? [] []>                                        ⇒ #FALSE ()
<==? 1 1>                                          ⇒ T
<==? 1.0 1.0>                                      ⇒ T

The first line is the substance of REST and TOP from chapter 10: RESTing a STRING six characters and then TOPping it back gets you the same object, not a copy of it. The second line is the reverse point -- a second STRING that reads the same is a different object. And the two empty structures are the parenthetical rule: () is ==? to () and [] is not ==? to [].

N==? is the Boolean complement of ==?.

<=? e1:any e2:any>

evaluates to T if e1 and e2 have the same TYPE and are structurally equal -- that is, they "look the same", their printed representations are the same. =? is much slower than ==?. =? should be used only when its characteristics are necessary: they are not in any comparisons of unstructured objects. ==? and =? always return the same value for FIXes, FLOATs, ATOMs, etc. (Mnemonically, ==? tests for "more equality" than =?; in fact, it tests for actual physical identity.)

Example, illustrating non-copying of a SEGMENT in Direct Representation of a LIST:

<SET A '(1 2 3)>                   ⇒ (1 2 3)
<==? .A (!.A)>                     ⇒ T
<==? .A <SET B <LIST !.A>>>        ⇒ #FALSE ()
<=? .A .B>                         ⇒ T

This is section 7.7.4 measured rather than described. (!.A) is a LIST being built whose only element is a trailing LIST segment, so nothing is copied and the answer is .A itself. <LIST !.A> copies, so the answer only looks the same.

N=? is the Boolean complement of =?.

<MEMBER object:any structured>

runs down structured from first to last element, comparing each element of structured with object. If it finds an element of structured which is =? to object, it returns <REST structured i> (which is of TYPE <PRIMTYPE structured>), where the (i+1)th element of structured is =? to object. That is, the first element of what it returns is the first element of structured that is =? to object.

If no element of structured is =? to object, MEMBER returns #FALSE ().

The search is more efficient if structured is of PRIMTYPE VECTOR (or UVECTOR, if possible) than if it is of PRIMTYPE LIST. As usual, if structured is constant, it should be QUOTEd.

If object and structured are of PRIMTYPE STRING [or BYTES], MEMBER does a substring search. Example:

<MEMBER "PART" "SUM OF PARTS">     ⇒ "PARTS"
<MEMBER 2 '(1 2 3)>                ⇒ (2 3)
<MEMBER 9 '(1 2 3)>                ⇒ #FALSE ()
<MEMBER "part" "SUM OF PARTS">     ⇒ #FALSE ()

<MEMQ object:any structured> ("member quick") is exactly the same as MEMBER, except that the comparison test is ==?.

<MEMQ 2 '(1 2 3)>                  ⇒ (2 3)
<MEMQ "PART" "SUM OF PARTS">       ⇒ "PARTS"

That second line looks like it should fail, since two separately-read STRINGs are not ==? -- but the substring search does not compare the STRINGs, it compares their CHARACTERs, and CHARACTERs of PRIMTYPE WORD are ==? when they are equal. So MEMQ searches substrings exactly as MEMBER does.

<STRCOMP s1 s2>

("string comparison") can be given either two STRINGs or two ATOMs as arguments. In the latter case the PNAMEs are used. It actually isn't a predicate, since it can return three possible values: 0 if s1 is =? to s2; 1 if s1 sorts alphabetically after s2; and -1 if s1 sorts alphabetically before s2. "Alphabetically" means, in this case, according to the numeric order of ASCII, with the standard alphabetizing rules.

<STRCOMP "A" "A">          ⇒ 0
<STRCOMP "B" "A">          ⇒ 1
<STRCOMP "A" "B">          ⇒ -1
<STRCOMP FOO BAR>          ⇒ 1
<STRCOMP "abc" "ABC">      ⇒ 1

"According to the numeric order of ASCII" is the last line: lower case sorts after upper case, because that is where ASCII puts it.

[A predicate suitable for an ascending SORT (which see) is <G? <STRCOMP .ARG1 .ARG2> 0>.]

8.2.3. Boolean Operators

<NOT e:false-or-any>

evaluates to T only if e evaluates to a FALSE, and to #FALSE () otherwise.

<AND e1 e2 ... eN>

AND is an FSUBR. It evaluates its arguments from first to last as they appear in the FORM. As soon as one of them evaluates to a FALSE, it returns that FALSE, ignoring any remaining arguments. If none of them evaluate to FALSE, it returns EVAL of its last argument. <AND> returns T. AND? is the SUBR equivalent to AND, that is, all its arguments are evaluated before any of them is tested.

<OR e1 e2 ... eN>

OR is an FSUBR. It evaluates its arguments from first to last as they appear in the FORM. As soon as one of them evaluates to a non-FALSE, it returns that non-FALSE value, ignoring any remaining arguments. If this never occurs, it returns the last FALSE it saw. <OR> returns #FALSE (). OR? is the SUBR equivalent to OR.

<NOT <>>                   ⇒ T
<NOT 1>                    ⇒ #FALSE ()
<AND>                      ⇒ T
<OR>                       ⇒ #FALSE ()
<AND 1 2 3>                ⇒ 3
<AND 1 <> 3>               ⇒ #FALSE ()
<OR <> <> 5>               ⇒ 5
<OR <> #FALSE (LAST)>      ⇒ #FALSE (LAST)
<AND? 1 2 3>               ⇒ 3
<OR? <> 5>                 ⇒ 5

Two of those are worth naming. <AND 1 2 3> is 3 and not T: these return a value, not a truth value, which is what makes section 8.4.1 possible. And <OR <> #FALSE (LAST)> returns the last FALSE it saw, reasons and all, so a chain of ORed attempts hands back the last one's excuse rather than a bare #FALSE ().

Measured, MDL 55. AND and OR are FSUBRs here, as they must be -- a SUBR cannot decline to evaluate an argument. It is worth knowing that the era's compiler could not compile its own <AND> and <OR> with no arguments at all: the code it generated for those two shapes will not run (chapter 34's oracle records both). pymdl's native compiler declines to compile what it cannot do rather than emitting code that faults, which is the refusal floor of chapter 34.

8.2.4. Object Properties

<TYPE? any type-1 ... type-N>

evaluates to type-i only if <==? type-i <TYPE any>> is true. It is faster and gives more information than ORing tests for each TYPE. If the test fails for all type-i's, TYPE? returns #FALSE ().

<APPLICABLE? e>

evaluates to T only if e is of a TYPE that can legally be applied to arguments in a FORM, that is, be (EVAL of) the first element of a FORM being evaluated (appendix B).

<MONAD? e>

evaluates to #FALSE () only if NTH and REST (with non-zero second argument) can be performed on its argument without error. An unstructured or empty structured object will cause MONAD? to return T.

<STRUCTURED? e>

evaluates to T only if e is a structured object. It is not the inverse of MONAD?, since each returns T if its argument is an empty structure.

<EMPTY? structured>

evaluates to T only if its argument, which must be a structured object, has no elements.

<LENGTH? structured fix>

evaluates to <LENGTH structured> only if that is less than or equal to fix; otherwise, it evaluates to #FALSE (). Mnemonically, you can think of the first two letters of LENGTH? as signifying the "less than or equal to" sense of the test.

<TYPE? 1 FIX FLOAT>        ⇒ FIX
<TYPE? "A" FIX FLOAT>      ⇒ #FALSE ()
<APPLICABLE? ,+>           ⇒ T
<APPLICABLE? 1>            ⇒ T
<MONAD? 1>                 ⇒ T
<MONAD? ()>                ⇒ T
<MONAD? '(1)>              ⇒ #FALSE ()
<STRUCTURED? ()>           ⇒ T
<STRUCTURED? 1>            ⇒ #FALSE ()
<EMPTY? ()>                ⇒ T
<EMPTY? '(1)>              ⇒ #FALSE ()
<LENGTH? '(1 2 3) 5>       ⇒ 3
<LENGTH? '(1 2 3) 2>       ⇒ #FALSE ()

<APPLICABLE? 1> being T is not a mistake and not a curiosity: a FIX really is applicable, and section 7.1.6 is what it does when applied. The empty-structure line is the one the text warns about -- () is both MONAD? and STRUCTURED?, so neither predicate is the other's inverse.

This SUBR was invented to use on lists, because MDL can determine their lengths only by stepping along the list, counting the elements. If a program needs to know only how the length compares with a given number, LENGTH? will tell without necessarily stepping all the way to the end of the list, in contrast to LENGTH.

[If structured is a circular PRIMTYPE LIST, LENGTH? will return a value, whereas LENGTH will execute forever. To see if you can do <REST structured <+ 1 fix>> without error, do the test <NOT <LENGTH? structured fix>>.]

pymdl's own. Both halves of that bracketed note hold here exactly, and chapter 10's box on section 7.8 explains why they must: a circular LIST is unbounded in width, so nothing in the interpreter can catch it, and LENGTH? is the only escape there is. Its answer on the WALTZ of section 7.8.1 is #FALSE () no matter how large the bound.

8.3. COND

The MDL Subroutine which is most used for varying evaluation depending on a truth value is the FSUBR COND ("conditional"). A call to COND has this format:

<COND clause-1:list ... clause-N:list>

where N is at least one.

COND always returns the result of the last evaluation it performs. The following rules determine the order of evaluations performed.

1. Evaluate the first element of each clause (from first to last) until either a non-FALSE object results or the clauses are exhausted.
2. If a non-FALSE object is found in (1), immediately evaluate the remaining elements (if any) of that clause and ignore any remaining clauses.

In other words, COND goes walking down its clauses, EVALing the first element of each clause, looking for a non-FALSE result. As soon as it finds a non-FALSE, it forgets about all the other clauses and evaluates, in order, the other elements of the current clause and returns the last thing it evaluates. If it can't find a non-FALSE, it returns the last FALSE it saw.

8.3.1. Examples

<SET F '(1)>                                       ⇒ (1)
<COND (<EMPTY? .F> EMP) (<1? <LENGTH .F>> ONE)>    ⇒ ONE
<SET F ()>                                         ⇒ ()
<COND (<EMPTY? .F> EMP) (<1? <LENGTH .F>> ONE)>    ⇒ EMP
<SET F '(1 2 3)>                                   ⇒ (1 2 3)
<COND (<EMPTY? .F> EMP) (<1? <LENGTH .F>> ONE)>    ⇒ #FALSE ()
<COND (<LENGTH? .F 2> SMALL) (BIG)>                ⇒ BIG

The third one is the "returns the last FALSE it saw" rule: no clause succeeded, so the value is the FALSE from <1? <LENGTH .F>>. The fourth is a one-element clause -- BIG is both the test and the value, and since an unbound ATOM evaluates to itself and is not FALSE, it succeeds and is returned.

<DEFINE FACT (N)        ;"the standard recursive factorial"
        <COND (<0? .N> 1)
              (ELSE <* .N <FACT <- .N 1>>>)>>      ⇒ FACT
<FACT 5>                                           ⇒ 120

8.4. Shortcuts with Conditionals

8.4.1. AND and OR as Short CONDs

Since AND and OR are FSUBRs, they can be used as miniature CONDs. A construct of the form

<AND pre-conditions action(s)>

or

<OR pre-exclusions action(s)>

will allow action(s) to be evaluated only if all the pre-conditions are true or only if all the pre-exclusions are false, respectively. By nesting and using both AND and OR, fairly powerful constructs can be made. Of course, if action(s) are more than one thing, you must be careful that none but the last returns false or true, respectively. Watch out especially for TERPRI (chapter 14). Examples:

<AND <ASSIGNED? FLAG> .FLAG <FCN .ARG>>

applies FCN only if someone else has SET FLAG to true. (ASSIGNED? is true if its argument ATOM has an LVAL.) No error can occur in the testing of FLAG because of the order of evaluation.

<AND <ASSIGNED? FLAG> .FLAG>       ⇒ #FALSE ()

-- and no error, which is the point: .FLAG was never evaluated.

<AND <SET C <OPEN "READ" "A FILE">> <LOAD .C> <CLOSE .C>>

effectively FLOADs the file (chapter 14) without the possibility of getting an error if the file cannot be opened.

Found along the way. That idiom is not a period curiosity, and the corpus writes it with OR rather than AND, for two different jobs. mat.mud uses <OR <OPEN "READ" file> <ERROR "File Not Found" file>> to turn a FALSE into an error of its own wording, and inquire.mud uses <OR <OPEN "PRINT" one> <OPEN "PRINT" other>> to try a second directory when the first is not writable. Both depend on OPEN answering a FALSE rather than signalling. Chapter 14 has which of the I/O SUBRs do which, since that is what decides whether you may write this at all.

8.4.2. Embedded Unconditionals

One of the disadvantages of COND is that there is no straightforward way to do things unconditionally in between tests. One way around this problem is to insert a dummy clause that never succeeds, because its only LIST element is an AND that returns a FALSE for the test. Example:

<SET VEC '[1 2 3 4 5 6]>           ⇒ [1 2 3 4 5 6]
<SET N 5>                          ⇒ 5
<COND   (<0? .N> <F0 .N>)
        (<1? .N> <F1 .N>)
        (<AND <SET N <* 2 <FIX </ .N 2>>>>
                        ;"Round .N down to even number."
              <>>)
        (<LENGTH? .VEC .N> '[])
        (T <REST .VEC <+ 1 .N>>)>  ⇒ [6]
.N                                 ⇒ 4

The third clause did its work and then failed on purpose, so .N is 4 when the fourth and fifth clauses are reached. (F0 and F1 are never called here, so this runs without them being defined -- COND does not evaluate a clause it does not select.)

A variation is to make the last AND argument into the test for the COND clause. (That is, the third and fourth clauses in the above example can be combined.) Of course, you must be careful that no other AND argument evaluates to a FALSE; most Subroutines do not return a FALSE without a very good reason for it. (A notable exception is TERPRI (which see).) Even safer is to use PROG (section 10.1) instead of AND.

Another variation is to increase the nesting with a new COND after the unconditional part. At least this method does not make the code appear to a human reader as though it does something other than what it really does. The above example could be done this way:

<COND   (<0? .N> <F0 .N>)
        (<1? .N> <F1 .N>)
        (T
         <SET N <* 2 <FIX </ .N 2>>>>
         <COND  (<LENGTH? .VEC .N> '[])
                (T <REST .VEC <+ 1 .N>>)>)>