// oSigma.txt 0.5.0 UTF-8 2024-10-29 //--|----1----|----2----|----3----|----4----|----5----|----6----|----7----|--* // // OBAP ABSTRACTION FUNCTIONS // =========================== // // // // HAND-COMPILED oSigma(s, M) // -------------------------- // // // The sigma.s M function is introduced in Miser Project Discussion // Note #42, . This // oSigma.txt file demonstrates the manual compilation of the // sigma(s, M) Frugalese pseudo-language specification into a // raw oFrugal ^oSigma implementation. // // oSigma(s, M) derives a script that when applied to an operand, L, // determines a version of M with L substituted wherever s occured: // // oSigma(s, M) L = oSubst(L, s) M // // where obSubst(L, s) derives a substitution of L for s everywhere in // its operand M. Both forms are valuable. Here, we take oSigma as a // starting point and illustration for defining and confirming other // forms. // // The applicative computational scheme is defined in the file // . // // A sketch of oFrugal notation is at // . // // The formal syntax and semantics of oFrugal expressions is at // . // // See casep development for another demonstration of hand-compiling, // . // // This file is meant to be processable by oFrugal. // // There is a serious practical requirement for hand-compiling the // sigma script. The other abstraction procedures, λ.s, ρ.sigmas, and // λ.M in the σ.s definition rely upon σ.x applications in their // definitions/implementations. That chicken-and-egg problem is // resolved by hand-crafting an initial oSigma, here, which becomes // usable in the crafting and confirmation of all of the abstraction // utilities, including processing the λ-form expression of σ.s itself // (the ultimate test). // // This bootstrapping of an initial σ.s is reminiscent of using early // programming-language compilers to compile the compiler written in // the language it compiles (e.g., compiling a C Language compiler // written in C Language, and how that first C Language compiler is // obtained by other means). // // The goal is to have a carefully hand-crafted ^oSigma script that // facilitates crafting of the additional abstraction forms, ^oLambda, // ^oRec, and ^oSubst. From there, assembling procedure scripts in // Frugalese pseudo-code will be more easily-expressed and dependable. // As the dentist says, "It will only hurt for a little while." // // Although oSigma and the related oSubst are precise algorithms, // The scripts ^oLambda and ^oRec are heuristics and imperfect in // ways that will be accounted for with introduction of those scripts. // // 1. The Original Definition // 2. λ-form Expression // 3. Conditionals // 3.1 is-singleton(z), is-individual(z), and is-enclosure(z) // 3.2 is-enclosure(R) ∧ is-enclosure(S) // 4. let-/where-Form Expressions // 4.1 Single let/where form // 4.2 multiple let/where clauses // 5. Putting It All Together // 5.1 Everything but λ.s // 5.2 Completed hand-compilation // 6. Now for subst(L,s) and delta(s, L) // 6.1 subst(L, s) // 6.2 delta(s, P), δ.s(P) // // // // 1. THE ORIGINAL DEFINITION // // From , // // σ.s M = if M = s // (1) // then .arg // else if is-individual(M) // then ` M // else if is-enclosure(M) // then let R = σ.s .a M // in if is-enclosure(R) // then ` M // else .e :: R // else let R = σ.s .a M, // S = σ.s .b M // in if is-enclosure(R) ∧ is-enclosure(S) // then ` M // else .c :: R :: S // // // 2. λ-FORM EXPRESSION // // Switch to the mixed oFrugal/Frugalese pseudo-code that // relies on application of λ-abstraction procedures. // // sigma = λ.s ρ.sigmas λ.M // (2) // if M = s // then .arg // else if is-individual(M) // (2a) // then ` M // else if M = .b M // hence is-enclosure(M) // (2b) // then let R = sigmas .a M // (2c) // in if is-enclosure(R) // (2d) // then ` M // else .e :: R // else let R = sigmas .a M, // (2e) // S = sigmas .b M // in if is-enclosure(R) // (2f) // ∧ is-enclosure(S) // then ` M // else .c :: R :: S // // // 3. CONDITIONALS // // 3.1 is-singleton(z), is-individual(z), and is-enclosure(z) // // ob.is-individual(z) ⇔ ob.a(z) = z // ob.is-singleton(z) ⇔ ob.b(z) = z (from Ob4) // ob.is-enclosure(z) ⇔ ob.is-singleton(z) ∧ ob.a(z) ≠ z // // where ob.a(z) ≠ z is equivalent to ¬ is-individual(z). // // 3.1.1 is-singleton amd is-enclosure // // Translation of is-singleton(z) is directly to ( .d :: z :: .b :: z ). // We can produce an oFrugal script for the applicative form. The // companion is-individual is expressible in the same manner. !def ob ^oIsSingleton = // λz (z = .b z) .d :: .arg :: .b :: .arg ; !def ob ^oIsIndividual = // λz (z = .a z) .d :: .arg :: .a :: .arg ; // Note how the abstracted literal symbol "z" has no distinct residue // upon its abstraction. The .arg form abstracts away the use of "z" // paired with "λz". Any other literal symbol could be used, as in // λq (q = .b q) so long as there is no conflicting occurrence of the // alternative symbol. The abstracted forms are the same. // // // 3.1.2 is-enclosure // // The form ob.a(z) ≠ z is equivalent to ¬( ob.a(z) = z ). // // For // if ¬R then A else B // // use if R then B else A. // // Now for is-enclosure(R) of (2d), there are two ways to do this, with // // is-enclosure(R) = if is-singleton(R) // (3a1) // then if is-individual(R) // then .b // else .a // else .b // and with // // is-enclosure(R) = if is-individual(R) // (3a2) // then .b // else is-singleton(R) // // The (3a2) form seems the most elegant with its shallow definition, yet // (3a1) may be a better choice by ruling out non-singletons quickly. // Here, opt for the simplicity of (3a2), which expands further to // // is-enclosure(R) = if .a R = R // (3b) // then .b // else .b R = R // // Abstracting R achieves a hand-compilation: !def ob ^oIsEnclosure = // λR if is-individual(R) // (3c) .ev :: ^oIsIndividual :: ` ( // then .b .b :: // else is-singleton(R) ^oIsSingleton ); // Because ^oIsIndividual and ^oIsSingleton are non-recursive scripts // that have their operand already abstracted, it is as if R is already // abstracted and those scripts can be spliced "in-line" without the need // for (` ^oIsIndividual :: .arg) and (` oIsSingleton :: .arg). This // flattening device is very useful, although it depends on knowledge // of the incorporated script. // // That coupling can be error-prone. It is risked here because the // incorporated scripts are both well-known and defined nearby. // // // 3.2 is-enclosure(R) ∧ is-enclosure(S) // // The computational idiom for P ∧ Q in oFrugalese is // // if P then Q else .b (3d) // // This short-circuit determination is valid because there are no // side-effects in oMiser. Failing to evaluate Q when P evaluates // to .b is valuable. // // There is only one direct relation in oMiser; it is for equality // of two obs. That is sufficient. // // By (3d), the (2f) form // // is-enclosure(R) ∧ is-enclosure(S) // // expands to // // if is-enclosure(R) // (3e) // then is-enclosure(S) // else .b // // Using ^oIsEnclosure, this can be expressed as // // // if is-enclosure(R) // (3f) // .ev :: ( ` ^oIsEnclosure :: R ) // // :: ` ( // then is-enclosure(S) // ( ` ^oIsEnclosure :: S ) // :: // // else .b // .b ) // // Here, abstraction of R and S has not been accounted for and there is // nothing farther until that is addressed (cf. 4.2). // // In-lining ^oIsEnclosure application is unavailable here, in contrast // to the opportunity with ^obIsIndividual and ^obIsSingleton in the // (3c) implementation of ^obIsEnclosure. // // // 4. let-/where-FORM EXPRESSIONS // // 4.1 Single let/where Forms // // The oFrugal idiomatic handling of the forms // // let v = T in U // // U where v = T // // require abstraction of the literal v from U in this manner: // // (λv U) T // // The choice between let/where forms is driven by readability // considerations. // // Mixtures are possible, as in // // let v = T // in U // where r = M // // which becomes // // (λv ((λr U) M )) T // // The hand-compiling of these forms will be explored in depth later on. // // For oSigma.txt, the expression at (2c), // // let R = sigmas .a M (2c) // in if is-enclosure(R) (2d) // then ` M // else .e :: R // // is transformed to the form // // λ.R ( if is-enclosure(R) // (4a) // then ` M // else .e :: R // ) // sigmas .a M // // There is an occurrence of M in the body of the λ.R abstraction. This // leads to the M in ` M having to be inserted every time sigma recurses // on operand M, even for all the times is-enclosure(R) does not hold. // // Avoid such deep substitution by abstracting M and applying that result // at the level where M is the current operand. // // ( ( λ.R if is-enclosure(R) // (4b) // then λ.M ` M // else λ.M (.e :: R ) // ) // sigmas .a .M // ) // M // // Since the result of (λ.R ...) application yields an effectively // M-abstracted script, the result can be evaluated in-line since M // is already the current (abstracted) operand: // // .ev ( ( λ.R if is-enclosure(R) // (4c) // then λ.M ` M // else λ.M (.e :: R ) // ) // sigmas .a M // ) // // is sufficient. // !def ob ^_M-is-enclosure = // ρ.sigmas λ.M // (4d) // ( λ.R if is-enclosure(R) .ev :: `( .ev :: ` ^oIsEnclosure :: ` ( // then λ.M ` M `( .e :: .arg ) :: // else λ.M (.e :: R ) .e :: .c :: `.e :: .arg ) ) // ) where R = sigmas .a M :: .self :: .a :: .arg ; // // 4.2 Multiple let/where Clauses // // For the current M being a pair, the (2e) operation is // // let R = sigmas .a M, // (2e) // S = sigmas .b M // in if is-enclosure(R) ∧ is-enclosure(S) // then ` M // else .c :: R :: S // // Readability of the where-form seems unappealing for this case although // the transformation is easily done. // // For (2e) we can adapt the device employed at (4a) except there is no // benefit to creating a // // ( (λ.R λ.S ...) sigmas .a M ) sigmas .b M // // since both operands are always going to be required and consumed // immediately. // // The applicative structure can be simplifed by operating on R and S as // a pair, // // (λ.RS ...) ( sigmas .a M :: sigmas .b M ), // // employing a variant of form (4c): // // (4e) // .ev ( ( λ.RS if is-enclosure(.a RS) ∧ is-enclosure(.b RS) // then λ.M ` M // else λ.M ( .c :: RS ) // ) // ( sigmas .a M :: sigmas .b M ) // ) // // Expanding the conjunction from (3e), we obtain // // .ev ( ( λ.RS if (if is-enclosure .a RS // then is-enclosure .b RS // else .b) // then λ.M ` M // else λ.M ( .c :: RS ) // ) // ( sigmas .a M :: sigmas .b M ) // ) !def ob ^_M-is-pair = // ρ.sigmas λ.M // (4f) // ( λ.RS if if is-enclosure .a RS .ev :: `( .ev :: ( .ev :: ( ` ^oIsEnclosure :: .a :: .arg ) :: ` ( // then is-enclosure .b RS ( ` ^oIsEnclosure :: .b :: .arg ) :: // else .b .b ) :: ` ( // then λ.M ` M `( .e :: .arg ) :: // else λ.M (.c :: RS ) ) .e :: .c :: `.c :: .arg ) ) // ) where RS = sigmas .a M :: sigmas .b M :: .c :: (.self :: .a :: .arg) :: .self :: .b :: .arg ; // 5. PUTTING IT ALL TOGETHER // // We have been developing the chunks with ρ.sigmas λ.M abstraction. // The next step is to complete that for that portion of the λ-form // expression (2). The final challenge is to accomplish the λ.s // abstraction. This requires sigma itself, and we'll follow the // Frugalese for the final manual steps. // // 5.1 Everything But λ.s // // The oSigma code on which λ.s is to be applied is obtained from (2), // ^_M-is-enclosure (4d), and ^_M-is-pair (4f): // // // ρ.sigmas λ.M // (5a) // // // if M = s // .ev :: ( .d :: .arg :: ` s) // s is held constant // // :: `( // then // .arg // :: // // else if is-individual(M) // .ev :: ` ^oIsIndividual // :: `( // then // (.e :: .arg) // :: // // else if is-singleton(M) // .ev :: ` ^oIsSingleton // :: `( // then // ^_M-is-enclosure // :: // // else // ^_M-is-pair // ) // ) // ) // // When the given ob is already a script with arguments, additional // λ-abstraction is by sigma-extraction. That is, λ.s on (5a) is // obtained via σ.s on (5a). // // // 5.2 Completed Hand-Compilation // // Fortunately, there is only one occurrence of s and it is near the // beginning of the overall oFrugal script. The substitution of an // argument for the place of s after λ.s only requires building of the // top line of (5a), with the remainder preserved as an unchanged // enclosure: !def ob ^oSigma = // λ.s ρ.sigmas λ.M // if M = s .c :: `.ev :: .c :: (.c :: `.d :: .c :: `.arg :: .e :: .arg) ::``( // then .arg :: // else if is-individual(M) .ev :: ^oIsIndividual :: `( // then (.e :: .arg) :: // else if is-singleton(M) .ev :: ^oIsSingleton :: `( // then ^_M-is-enclosure :: // else ^_M-is-pair ) ) ); // NOTE: The insertion of parts is appropriate following the abstraction // of M, but not before. If they were included prior to application of // an actual λ.M application, the appearance of .arg in those inclusions // would mis-guide the abstraction operation. See how that is handled // in development of subst(L, s) and introduction of delta(s, P) below. // // 6. NOW FOR subst(L, s) // // 6.1 subst(L, s) // // The definition // // oSubst(L, s) M = oSigma(s, M) L // // is a mathematically straightforward way to define substitutions // of L for s in the given M. This may not be an efficient technique, // but it is simple to implement in this form. Here's how. // // oSubst = λ.L λ.s λ.M // oSigma(s, M) L // // = λ.L λ.s λ.M // (( oSigma :: s) :: M) :: L // // = λ.L λ.s // λ.M // ( ( oSigma :: s) :: .arg) :: L // // = λ.L // λ.s λ.M // .c :: (.c :: (`.e :: ^oSigma) // oSigma(s) flattened // :: `.arg) // :: `L // // NOTE 1: Until this point, nothing was done about the "free-occurrence" // of the oSigma in the oFrugal pseudo-code. Substitution before // abstraction of operand M will mislead the λ.M heuristic // detection of existing .arg occurrences. Now insertion of // ^oSigma is safe. The use of δ.s(P), introduced in (6.2, // below), supports a systematic practice for use in conjunction // with abstraction operations once they are available. // // NOTE 2: It is permissible to apply oSigma as soon as its operand s // is available. That simplification, with flattening of the // ^oSigma presence, is reflected in the hand-compiled λ.s // abstraction. For a more-systematic approach, see 6.2, below. // // Now finally, !def ob ^oSubst = // λ.L λ.s λ.M .c :: `.c :: .c :: `(.c :: (`.e :: ` ^oSigma) :: `.arg) :: .e :: .e :: .arg; // That is much easier than coming up with a direct implementation of // subst that operates with no dependence on oSigma. If that is ever // preferable, use this implementation for confirmation of matching // results and also for determining the difference in performance. // // // 6.2 delta(s, P), δ.s(P) // // Another way to deal with the occurrences of lindies that are intended // to be replaced by scripts defined elsewhere is by use of simplifier // function // // δ.s(P) M = oDelta(s, P) M = oSubst(P, s) M = oSigma(s, M) P // // The direct approach uses oSubst for the implementation. It is simply // reversal of the first two operands of oSubst. // // IMPORTANT: δ(s,P) M is intended for use in a convention for linking // pre-calculated/-bound scripts in place of occurrences of (lindy) s in // M. That usage is simulated in definition of δ.s(P) itself. // // oDelta = δ(subst, ` ^oSubst) λ.s λ.P λ.M // (6) // subst(P, s) M // // = δ(subst, ` ^oSubst) λ.s λ.P // ( subst :: P) :: s // // = δ(subst, ` ^oSubst) λ.s // λ.P // ( subst :: .arg) :: s // // = δ(subst, ` ^oSubst) // λ.s λ.P // .c :: `( subst :: .arg) // :: .e :: .arg !def ob ^oDelta = // δ(subst, ` ^oSubst) λ.s λ.P .c :: ` (` ^oSubst :: .arg) :: .e :: .arg; // The use of δ.s is often not explicit in manual compilation in the // manner of (6). When lambda transformations are implemented and there // is no manual observation of intermediates, post-λ linkings as with // // ^δ(subst, ` ^oSubst) // ^λ.s ^λ.P // ((subst :: P) :: s); // // are indispensible. // // Any clumsiness stems from the complete absence of anything like // programming-language variables and references in oMiser. oFrugal // bindings (^-forms) must be explicit and always previously-defined. // // NOTE 1: This is the recommended approach to linking in separately- // defined scripts that are already in abstracted applicative // form. Incorrect λ-heuristic determinations are avoided with // this precaution. // // NOTE 2: There may be multiple applications of δ.s(P) forms. This is // the intended practice. CAVEAT: The stacking of δ.s(P) forms // can be incorrect in the case that "s" occurs in the body of a // subsequent δ-linked component, or ambiguously in the current // P operand. That is a general risk of the abstraction // heuristics at this oFrugal low level. // // //--|----1----|----2----|----3----|----4----|----5----|----6----|----7----|--* // // Copyright 2024 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. // //--|----1----|----2----|----3----|----4----|----5----|----6----|----7----|--* // // ATTRIBUTION // // Hamilton, Dennis E. Hand-compiled sigma(s, M). Miser Theory Conception // text file oSigma.txt version 0.5.0 dated 2024-10-29, available on the // Internet as a version of // // //--|----1----|----2----|----3----|----4----|----5----|----6----|----7----|--* // // TODO // // * Step through and check once the oFrugal REPL is working well enough. // // * Confirm ^oSubst also. // // * I wonder if there is a better symbolism than δ.s // //--|----1----|----2----|----3----|----4----|----5----|----6----|----7----|--* // // 0.5.0 2024-10-19T17:42Z Use linking-style δ(s, P) form with linking usage // 0.4.0 2024-06-24T15:10Z Breaking change/fix to δ definition and usage // 0.3.3 2024-06-21T19:27Z Clean-up the simulated δ cases for non-inlined // insertions of defined applicative obs // 0.3.2 2024-06-20T16:19Z Expand on δ usage, with notes on hazards // 0.3.1 2024-06-19T19:30Z Be consistent with oDelta and δ // 0.3.0 2024-06-19T17:30Z Introduce ^oDef and δ // 0.2.1 2024-06-17T15:38Z Elaborate on flattening and avoiding inclusion of // other scripts prematurely // 0.2.0 2024-06-16T22:35Z Introduce ^oSubst // 0.1.1 2024-06-16T16:40Z Touch-up // 0.1.0 2024-05-31T22:56Z Creation of the complete script // 0.0.25 2024-05-31T19:17Z minor touch-ups // 0.0.24 2024-05-31T19:07Z Move from topic oFrugal to topic lambda // 0.0.23 2024-05-30T22:59Z Adjusted through ^_M-is-pair // 0.0.22 2024-05-30T01:35Z Touch-up ^_M-enclosure // 0.0.21 2024-05-30T00:03Z Improve through ^_M-enclosure // 0.0.20 2024-05-28T01:02Z Adding oIsIndividual, oIsSingleton, oIsEnclosure. // 0.0.19 2024-05-27T22:49Z Cleaning up layout and formula labels // 0.0.18 2024-05-26T20:10Z Adjusting to renaming again, working toward macros // 0.0.17 2024-05-26T18:07Z Adjust to the renaming and ponder macro helpers // 0.0.16 2024-05-26T16:10Z TODO Prep for renaming from sigma to obSigma // 0.0.15 2024-05-22T17:29Z Simple typo fixes // 0.0.14 2024-05-20T23:23Z Cleanup through 4.1 with more steps consistency // 0.0.13 2024-05-18T18:08Z Touching up around hand-codings // 0.0.12 2024-05-17T22:14Z More hand-coding of conjunctions // 0.0.11 2024-05-16T00:35Z More tidying around let-/where-forms // 0.0.10 2024-05-15T15:26Z Touch-ups and touching-on where-form. // 0.0.9 2024-05-14T16:47Z Polish down through section 4 // 0.0.8 2024-05-13T20:36Z Reorganize and smooth the material so far // 0.0.7 2024-05-12T23:42Z Reorganize and improve conditional forms // 0.0.6 2024-05-10T23:50Z Review and prepare to use temporary definitions // as a way of remaining comprehensible. // 0.0.5 2024-05-08T23:39Z Complete hand-compiling of the conjunction case // 0.0.4 2024-05-08T15:01Z Touch-Ups for printing and review // 0.0.3 2024-05-07T16:17Z Touch-up and start expanding conjunction handling // 0.0.2 2024-05-06T21:55Z Introduce listings for multiple let forms // 0.0.1 2024-05-05T21:16Z Introduce handling single let forms // 0.0.0 2024-05-05T18:36Z Create placeholder with boilerplate. // // *** end of oSigma.txt ***