CFob.txt 0.1.0                      UTF-8                          2023-11-10
----|----1----|----2----|----3----|----4----|----5----|----6----|----7----|--*


                           The Miser Project Code
                           ======================

             <https://orcmid.github.io/miser/ob/CFob.txt>

          FRUGALESE GRAMMAR FOR CANONICAL-FORM OB EXPRESSIONS
          ---------------------------------------------------

    CFob is a string expression of obs that exploits the right-
    associativity of "::" to eliminate unnecessary parentheses.  This
    is, apart from the presence of spacing, a unique string for an
    ob canonical form.  The form satisfies the oFrugal ob-exp grammar
    and oFrugal, if given such a string to evaluate, will produce a
    result that is canonical for the very same ob.

    See also
    <https://github.com/orcmid/miser/blob/master/oFrugal/ob-exp.txt> and
    <https://github.com/orcmid/miser/blob/master/oFrugal/grammars.txt>

 1. SUMMARY GRAMMAR

    Here is a BNF grammar for the Canonical-Form Obs.  Any of these forms are
    suitable.  Reducing the use of parentheses is handled in the procedure for
    expressing these forms.

    〈term〉 ::= 〈lindy〉 | 〈primitive〉

    〈unary〉 ::= 〈term〉 | ( 〈canonical〉 ) | ‵ 〈unary〉

    〈binary〉 ::= 〈unary〉 | 〈unary〉 :: 〈binary〉

    〈canonical〉 ::= 〈binary〉

 2. SIMPLE EXPRESSION

    Using SML/NJ, the CFob expression of an ob, x, is as follows:

    fun term(x: ob)
      = case x
          of L(s) => s
           | NIL => ".NIL"
           | A => ".A"
           | B => ".B"
           | C => ".C"
           | E => ".E"
           | D => ".D"
           | SELF => ".SELF"
           | ARG => ".ARG"
           | EV => ".EV"
           | _ => "?!"

    fun canonical(x: ob)
      = let fun unary(x)
            = if is_individual(x)
              then term(x)
              else if is_singleton(x)
                   then "`" ^ unary(a x)
                        (* XXX: Using back-tick here *)
                   else "( " ^ canonical(x) ^ " )"
         in if is_pair(x)
            then unary(a x) ^ " :: " ^ canonical(b x)
            else unary(x)
        end;

    To avoid console Unicode limitations/difficulties, the back-tick (grave
    accent) is used in this procedure.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

                Copyright 2018-2023 Dennis E. Hamilton

    Licensed under the Apache License, Version 2.0 (the "License");
    you may not use this file except in compliance with the License.
    You may obtain a copy of the License at

        http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

 ATTRIBUTION

   Hamilton, Dennis E. Frugalese Grammar for Canonical Form Ob Expressions.
   Miser Theory Conception text file CFob.txt version 0.1.0 dated 2023-11-10,
   available on the Internet as a version of
   <https://orcmid.github.io/miser/ob/CFob.txt>

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

TODO

  * Upgrade the cross-references in the synopsis.

  * Provide some links to more details on oFrugal grammar and related topics.

  * Split out the further engineering considerations to an appropriate topic
    other than under miser/ob/.

  * We need to have a simple CFob that does not include individuals from
    obaptheory (i.e., the primitives plus the extensions when they appear).
    We need the simpler form for argument that the the obs are denumerable.
    We don't need additional primitives for that demonstration.

  * In practice, we don't want to insert more than one space at
    any point in the ob-exp.  This simple expression avoids that but it
    is more involved when there are more forms.

  * A pretty-print form that uses indentation is a bit trickier.  That
    needs to be done.  Line wraps should be used to honor margins also.
    Lawrence Paulsen has an ML version of the D. C. Oppen "Pretty Printing"
    algorithm.  I thought I saw this in a different publication, and I wonder
    about that.  I had done one that formatted FORTRAN code.

  * When there are extensions, we need applicative expressions for their
    canonical expression.  These are for the application of specific
    extension primitives and they support maintenance of extensional
    identity among all obs.

  * For the pure lindy cases, consider a flattening that does not use "::"
    but uses a space instead and relies on the obap case producing the same
    thing because of pure-lindy treatment in obap.ev.  No, let's not do that
    here.

  * Update this to reflect the conditional lindies, or is that a case that
    is tied to oFrugal?  Yes, tie that to oFrugal pragmatics.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

 0.0.10 2023-11-10T00:52Z Touch-up as part of the refactored placement.
 0.0.9 2023-11-10T00:40Z Provide tombstone to GitHub orcmid/miser/oMiser
 0.0.8 2023-09-29T21:51Z Rethinking CFob for initial denumerability
 0.0.7 2022-08-11T20:39Z Add attribution, manage TODOs, touch-up
 0.0.6 2022-08-01T23:35Z Renamed from obstring.txt and adjusted to for naming
       CFob.txt in the adjusted narrative.
 0.0.5 2022-08-01T21:00Z Now refer to oFrugal/ob-exp.txt and manage TODOs
 0.0.4 2019-04-18-10:24 Manage TODOs and reconcile with latest refinement
       of applicable concepts.  Touch-ups
 0.0.3 2018-02-09-11:16 Rename to obstring.txt to reflect the expected
       function/method name.
 0.0.2 2018-02-07-18:24 Correct the term and canonical functions to agree with
       the test results for the implementation in obap.sml 0.0.9.
 0.0.1 2018-02-04-11:58 Provide direct basic expression.

                     *** end of obstring.txt ***