ob-exp.txt 1.1.0 UTF-8 2024-04-28 *---|----1----|----2----|----3----|----4----|----5----|----6----|----7----|--* The Miser Project Code ====================== repurposed from and tombstoned at FORMAL GRAMMAR FOR EXPRESSING OFRUGAL COMPUTATION OF OBS -------------------------------------------------------- Ob-exp texts are used as a means of specifying obs and computations with them to derive an ob result. Ob-exp is an expression language that is used in digital communication of computations with obs and also used to submit expressions for oMiser computation via oFrugal. ob-exp has a context-free grammar, here specified using the original Backus-Naur Form (BNF) as employed in the Revised Report on the Algorithmic Language ALGOL 60. The grammar specifies exactly those expressions that can be evaluated to (at most) a single ob when submitted to a processor such as an oFrugal implememtation. In addition to the grammatical structure for composing ob-exp expressions, there is also a formal definition of the computation by which an ob-exp is evaluated as computation of a canonical ob, the formal semantics of ob-exps. It is this fact that has ob-exp be defined under oMiser, even though it is oFrugal that will enact that semantics. For an informal introduction to the use of Frugalese in the computational model defined on the mathematical structure ‹ob› = 〈Ob,Of,Ot〉, see and other material cited there. CONTENT 1. Summary Grammar 2. Expression Interpretation 3. Text, Characters, Spacing, and Concrete Layout Considerations 4. Terms 5. List Forms 6. Functional Forms 7. Unaries 8. Applicative Expressions 9. Ob-Exp 10. References 1. SUMMARY GRAMMAR The following summary form of the grammar is useful for reference. It does not address the grammatical differences that are called for to align with the interpretation rules by which an ob-exp is evaluated. The notation is the same used for the ALGOL 60 Report [Naur1963], as adapted from a John Backus demonstration for ALGOL 58 [Backus1958]. All ob-exps satisfy the summary grammar. The "official" grammar rules detailed in subsequent sections employ syntactically-equivalent structures in order to provide a rigorous interpretation as expressions of ob computations. The concrete reference syntax consists of Unicode, usually in UTF8 encoding, and a %-escape mechanism is used when a character is not printable. It is recommended that characters that are not easily typed be avoided by authors of ob expressions, recognizing that a recipient may encounter %-encoding instead. If you don't know what this is about, you are probably on safe ground. Basically, white-space is allowed wherever it does not change the grammar of a 〈term〉 and required where consecutive 〈term〉 occurrences would not be disambiguated. The "//" form of comments to the end of lines are allowed. It counts as a whitespace line-end. For simplicity of keyboarding, the reversed-prime, ‵, left-tick, `, and apostrophe, ', are all treated the same. The reversed-prime is the "official" reference character. (See 〈unary〉, section 7 below.) 〈term〉 ::= 〈plane-lindy〉 | 〈primitive〉 | 〈binding-name〉 〈plane-lindy〉 is an alphanumeric name without spaces (see section 4) 〈primitive〉 ::= .〈plane-lindy〉 〈primitive〉s are not case-sensitive, although 〈plane-lindy〉s are otherwise. 〈primitive〉 interpretations in ‹ob› are established in particular obaptheory versions. (See section 4, below.) 〈binding-name〉 ::= ^〈plane-lindy〉 | ?〈plane-lindy〉 | ?〈primitive〉 〈binding-name〉 occurrences are references to previously-defined obs and one of the ?-forms is the interpretation when there is no such definition, an interaction with oFrugal that accounts for how ?-prefixed lindy forms arise in canonical ob forms to indicate errors. 〈list-terms〉 ::= 〈ob-exp〉 | 〈ob-exp〉 , 〈list-terms〉 〈list-form〉 ::= [ ] | [ 〈list-terms〉 ] | [ 〈list-terms〉 :] 〈parameters-form〉 ::= ( 〈list-terms〉 ) | 〈list-form〉 〈function-form〉 ::= 〈term〉 | 〈function-form〉 〈parameters-form〉 | 〈function-form〉.〈plain-lindy〉 〈function-form〉s always begin with a 〈term〉 〈obap-form〉 ::= ( 〈ob-exp〉 ) | 〈list-form〉 | 〈obap-form〉 〈parameters-form〉 | 〈obap-form〉.〈plain-lindy〉 〈obap-form〉s all begin with a bracket ("(" or "[") In 〈function-form〉 and 〈obap-form〉 patterns, the "." must have no preceding white space, avoiding confusion with primitive forms. 〈unary〉 ::= 〈function-form〉 | ‵ 〈obap-form〉 | ‵ 〈unary〉 〈ae-form〉 ::= 〈unary〉 | 〈unary〉 〈ae-form〉 〈ae〉 ::= 〈ae-form〉 | 〈obap-form〉 | 〈obap-form〉 〈ae-form〉 〈binary〉 ::= 〈ae〉 | 〈ae〉 :: 〈binary〉 〈ob-exp〉 ::= 〈binary〉 2. EXPRESSION INTERPRETATION Interpretation of expressions as obs is accomplished using a special schema notation that specifies the Ot (‹ob› theory-language) expression interpretation of a given ob-exp text. The interpretation schemas have distinct form. ‼ category ⎾pattern⏋{parameter-list} =: interpretation where category is one of the syntactic categories, such as 〈ob-exp〉, 〈ae〉, and 〈term〉 pattern is one of the patterns for the particular category, such as 〈binary〉, 〈obap-form〉 〈ae-form〉, and 〈lindy〉 {parameter-list} is an optional form consisting of a list of one-or-more parameters interpretation is an obaptheory expression schema in which any parameter and "‼ category {parameter-list}" forms are in reference to category appearances in the pattern; parameters of the pattern {parameter-list} may occur as variables in the interpretation, including in further {parameter-list} forms. The obaptheory formulation in Ot, the theory language of structure ‹ob› = 〈Ob,Of,Ot〉, is available at . For example, ‼〈ae〉⎾〈obap-form〉 〈ae-form〉⏋{ℰ} =: obap.ap(‼〈obap-form〉{ℰ},‼〈ae-form〉{ℰ}) On the right-hand side of the "=:" the category names refer to those in the pattern on the left-hand side, and the interpretations of those occurrences is called for to determine the individual ob that is their evaluation. The parameter ℰ employed in many interpretations signifies the ob-exp environment, the means by which the current oFrugal set of bindings is used to resolve binding names and provide unknown-name forms otherwise. This is tied to interpretation of oFrugal statement-level syntax. Although the rules are tied directly to the forms of the grammar, the notation is relaxed to also describe interpretation of parsing stages. For example (cf. section 9), ‼〈ob-exp〉⎾ f g x ⏋{ℰ} =: ‼〈binary〉⎾ f g x ⏋{ℰ} =: ‼〈ae-form〉⎾ f g x ⏋{ℰ} =: obap.ap( ‼〈unary〉⎾ f ⏋{ℰ}, ‼〈ae-form〉⎾ g x ⏋{ℰ} ) =: obap.ap( ‼〈function-form〉⎾ f ⏋{ℰ}, ‼〈ae-form〉⎾ g x ⏋{ℰ} ) =: obap.ap( ‼〈term〉⎾ f ⏋{ℰ}, ‼〈ae-form〉⎾ g x ⏋{ℰ} ) =: obap.ap( f, ‼〈ae-form〉⎾ g x ⏋{ℰ} ) =: obap.ap( f, obap.ap(‼〈unary〉⎾ g ⏋{ℰ}, ‼〈ae-form〉⎾ x ⏋{ℰ} ) ) =: obap.ap( f, obap.ap( g, x) ) where lindies such as Ʃ'f', Ʃ'g', and Ʃ'x' are written as f, g, and x without ambiguity in these cases. We can also work out that ‼〈ob-exp〉⎾ f g x ⏋{ℰ} :=: ‼〈ob-exp〉⎾ f (g x) ⏋{ℰ} signifying that the interpretations are the same (i.e., equivalent), keeping in mind that the f, g, and x here are literals and not variables. While the equivalence doesn't hold under arbitrary substitutions for f, g, and x, the following can be established. ‼〈ob-exp〉⎾ 〈unary〉₁ 〈unary〉₂ 〈unary〉₃ ⏋{ℰ} :=: ‼〈ob-exp〉⎾ 〈unary〉₁ ( 〈unary〉₂ 〈unary〉₃ ) ⏋{ℰ} with the subscripts used to distinguish among 〈unary〉 occurrences, following [Knuth1968]. 3. TEXT, CHARACTERS, SPACING, AND CONCRETE LAYOUT CONSIDERATIONS [DETAILS TBD] 4. TERMS 〈term〉 ::= 〈plane-lindy〉 | 〈primitive〉 | 〈binding-name〉 〈plane-lindy〉 is an alphanumeric name without spaces, corresponding to an XML Name without ":", ".", and middle-dot ("·") and allowing 0-9 as additional start characters. ‼〈term〉⎾〈plane-lindy〉⏋{ℰ} =: ‼〈plane-lindy〉, the lindy of that spelling, essentially Ʃ'〈plane-lindy〉' as used in obaptheory.txt 〈primitive〉 ::= .〈plane-lindy〉 ‼〈term〉⎾〈primitive〉⏋{ℰ} =: ‼〈primitive〉{ℰ}, the defined primitive lindy of that case- insensitive spelling, or the same as binding- name ?.〈plane-lindy〉 when there is no primitive ‼〈primitive〉⎾.NIL⏋{ℰ} =: ob.NIL, ‼〈primitive〉⎾.A⏋{ℰ} =: obap.A, ‼〈primitive〉⎾.B⏋{ℰ} =: obap.B, ‼〈primitive〉⎾.C⏋{ℰ} =: obap.C, ‼〈primitive〉⎾.D⏋{ℰ} =: obap.D, ‼〈primitive〉⎾.E⏋{ℰ} =: obap.E, ‼〈primitive〉⎾.ARG⏋{ℰ} =: obap.ARG, ‼〈primitive〉⎾.SELF⏋{ℰ} =: obap.SELF, ‼〈primitive〉⎾.EV⏋{ℰ} =: obap.EV 〈binding-name〉 ::= ^〈plane-lindy〉 | ?〈plane-lindy〉 | ?.〈plane-lindy〉 ‼〈term〉⎾〈binding-name〉⏋{ℰ} =: ‼〈binding-name〉{ℰ} defined in the oFrugal file syntax.txt 〈primitive〉s are not case-sensitive, although 〈plane-lindy〉s are otherwise. In oFrugal scripts, it is possible to bind an ob to a ^〈plane-lindy〉 form and then have that ob be the interpretation of that binding-name in 〈ob-exp〉 forms for which there has been no intervening change of binding. When there is a binding for ^〈plane-lindy〉, interpretation is the most- recently bound value. Otherwise, the interpretation is as ?〈plain-lindy〉. The ?〈plane-lindy〉 is treated the same as ^〈plane-lindy〉 when there is a binding for the 〈plane-lindy〉; otherwise the interpretation is as a lindy with spelling of the form Ʃ'?〈plane-lindy〉'. The ?.〈plane-lindy〉 is treated the same as 〈primitive〉 form .〈plane-lindy〉 when .〈plane-lindy〉 is interpreted as the primitive with that case- insensitive spelling. Otherwise, the interpretation is a lindy with spelling of form Ʃ'?.〈plane-lindy〉'. 5. LIST FORMS 〈list-body〉 ::= 〈ob-exp〉 ] | 〈ob-exp〉 :] | 〈ob-exp〉, 〈list-body〉 〈list-form〉 ::= [ ] | [ 〈list-body〉 ‼〈list-form〉⎾[ ]⏋{ℰ} =: ob.NIL ‼〈list-form〉⎾[ 〈list-body〉 ⏋{ℰ} =: ‼〈list-body〉{ℰ} ‼〈list-body〉⎾〈ob-exp〉 ]⏋{ℰ} =: ob.c( ‼〈ob-exp〉{ℰ}, ob.NIL) ‼〈list-body〉⎾〈ob-exp〉 :]⏋{ℰ} =: ‼〈ob-exp〉{ℰ} ‼〈list-body〉⎾〈ob-exp〉, 〈list-body〉⏋{ℰ} =: ob.c( ‼〈ob-exp〉{ℰ}, ‼〈list-body〉{ℰ} ) 6. FUNCTIONAL FORMS 〈function-form〉 ::= 〈term〉 | 〈function-form〉 〈list-form〉 | 〈function-form〉 ( 〈parameters〉 ) | 〈function-form〉.〈plain-lindy〉 〈obap-form〉 ::= ( 〈ob-exp〉 ) | 〈list-form〉 | 〈obap-form〉 〈list-form〉 | 〈obap-form〉 ( 〈parameters〉 ) | 〈obap-form〉.〈plain-lindy〉 〈parameters〉 ::= 〈ob-exp〉 | 〈ob-exp〉, 〈parameters〉 ‼〈function-form〉⎾〈term〉⏋{ℰ} =: ‼〈term〉{ℰ} ‼〈function-form〉⎾〈function-form〉 〈list-form〉 ⏋{ℰ} =: obap.ap( ‼〈function-form〉{ℰ}, ‼〈list-form〉{ℰ} ) ‼〈function-form〉⎾〈function-form〉 ( 〈parameters〉 )⏋{ℰ} =: ‼〈parameters〉{ ‼〈function-form〉{ℰ}, ℰ} ‼〈function-form〉⎾〈function-form〉.〈plain-lindy〉 ⏋{ℰ} =: obap.ap( ‼〈function-form〉{ℰ}, ‼〈plain-lindy〉 ) ‼〈obap-form〉⎾( 〈ob-exp〉 )⏋{ℰ} =: ‼〈ob-exp〉{ℰ} ‼〈obap-form〉⎾ 〈list-form〉 ⏋{ℰ} =: ‼〈list-form〉{ℰ} ‼〈obap-form〉⎾〈obap-form〉 〈list-form〉 ⏋{ℰ} =: obap.ap( ‼〈obap-form〉{ℰ}, ‼〈list-form〉{ℰ} ) ‼〈obap-form〉⎾〈obap-form〉.〈plain-lindy〉 ⏋{ℰ} =: obap.ap(‼〈obap-form〉{ℰ}, ‼〈plain-lindy〉) ‼〈obap-form〉⎾〈obap-form〉 ( 〈parameters〉 )⏋‼{ℰ} =: ‼〈parameters〉{ ‼〈obap-form〉{ℰ}, ℰ} ‼〈parameters〉⎾〈ob-exp〉, 〈parameters〉 ⏋{p, ℰ} =: ‼〈parameters〉{ obap.ap( p, ‼〈ob-exp〉{ℰ} ), ℰ} ‼〈parameters〉⎾〈ob-exp〉⏋{p, ℰ} =: ob.ap( p, ‼〈ob-exp〉{ℰ} ) 7. UNARIES 〈unary〉 ::= 〈function-form〉 | ‵ 〈obap-form〉 | ‵ 〈unary〉 ‼〈unary〉⎾〈function-form〉⏋{ℰ} =: ‼〈function-form〉{ℰ} ‼〈unary〉⎾ ‵ 〈obap-form〉 ⏋{ℰ} =: ob.e( ‼〈obap-form〉{ℰ} ) ‼〈unary〉⎾ ‵ 〈unary〉 ⏋{ℰ} =: ob.e( ‼〈unary〉{ℰ} ) 8. APPLICATIVE EXPRESSIONS 〈ae-form〉 ::= 〈unary〉 | 〈unary〉 〈ae-form〉 〈ae〉 ::= 〈ae-form〉 | 〈obap-form〉 | 〈obap-form〉 〈ae-form〉 ‼〈ae-form〉⎾ 〈unary〉 ⏋{ℰ} =: ‼〈unary〉{ℰ} ‼〈ae-form〉⎾ 〈unary〉 〈ae-form〉 ⏋{ℰ} =: obap.ap( ‼〈unary〉{ℰ}, ‼〈ae-form〉{ℰ} ) ‼〈ae〉⎾ 〈ae-form〉 ⏋{ℰ} =: ‼〈ae-form〉{ℰ} ‼〈ae〉⎾ 〈obap-form〉 ⏋{ℰ} =: ‼〈obap-form〉{ℰ} ‼〈ae〉⎾ 〈obap-form〉 〈ae-form〉 ⏋{ℰ} =: obap.ap( ‼〈obap-form〉{ℰ}, ‼〈ae-form〉{ℰ} ) 9. OB-EXP 〈binary〉 ::= 〈ae〉 | 〈ae〉 :: 〈binary〉 〈ob-exp〉 ::= 〈binary〉 ‼〈binary〉⎾ 〈ae〉 ⏋{ℰ} =: ‼〈ae〉{ℰ} ‼〈binary〉⎾ 〈ae〉 :: 〈binary〉 ⏋{ℰ} =: ob.c( ‼〈ae〉{ℰ}, ‼〈binary〉{ℰ} ) ‼〈ob-exp〉⎾ 〈binary〉 ⏋{ℰ} =: ‼〈binary〉{ℰ} The 〈ob-exp〉 grammar production is designed to allow for additional forms beyond 〈binary〉. None are anticipated at this time. 10. REFERENCES - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Copyright 2018-2022, 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. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ATTRIBUTION Hamilton, Dennis E. Formal Grammar for oFrugal Construction of Obs. Miser Theory Conception text file ob-exp.txt version 1.1.0 dated 2024-04-28, available on the Internet as a version of TODO * Revealing examples are needed here. Grace Hopper favored that and I should heed it for that reason alone. * Move up-level from ob-exp to the oFrugal command operation where the semantics of 〈binding-name〉 establishment, reference, and reference- failure are accounted for. The interpretation of REPL commands will be sequential and context-free! * We require a command separator ";" and a sequence terminator, ";;" so that parsing of command names is distinguishable without crazy backup. Having "ob ^mumble = ... " be disambiguated by the "=" might be troubling. The definition command removes that with "!def ob ^mumble = ...". * I am undecided about using ! or # as the command initiator in oFrugal. There is a certain harmony with # as the C Language preprocessor command initiator. I might do that for harmony alone. Need to think about the different uses of ! and # in various existing arrangements. [2022-08-02 The use of # will conflict with the use of # on numeric forms. There is also an use of ! around imperatives, or something like that. Need to be careful with that one.] * Add the handling of concrete cases and the tie-in to a reference character code, akin to the counterpart in the XML specification. * Use the XML 1.0 (Namespaces) characterization of white space, letters, digits, and the restricted allowance of other characters in ob-exp terms. Provide a reference. * Adopt the SML/NJ use of \\ as null? * I am thinking that "//" comments are better than block comments of various forms and I should do that. It also gets around the problem of comments that create white space in odd places. * Do we require white-space anywhere or is it optional everywhere except between two terms that must remain separated? * I think we do not want anything between a 〈function-form〉 and a parameter in the 〈function-form〉 pattern, at least not a comment. Yet I can envision cases where careful layout can be indifferent to white space. It might eventually be a lint-check on readability but not a formal condition. * Likewise, at the concrete term level, there is the matter of IRI encoding for characters having no available font glyph. How does that work into interchange of concrete ob-exp texts? Use a rigorous IRI case and provide reference to the (latest?) IETF specification on the matter. Masinter, where are you when I need you? :) * Complete the production of 〈term〉s and their interpretations. Binding has to be at oFrugal grammar level. * COMPLETE IN oFrugal Grammar: Complete this specification by including the oFrugal REPL statement sequencing and how the environment, E, is updated with definitions. * MOVE TO oFrugal Grammar: The function for resolving binding names can be expressed in oFrugal, but it requires a way to fail when the encountered binding name is not bound. So we need to have a *fail* interpretation different from there being an explicit fail in oMiser. We might call it an event, but need to be careful. [update 2022-03-11 The making of all binding names well-defined, and the use of ?-prefixed lindies as placeholders for undefined binding names and primitives resolves this problem. The oFrugal REPL will certainly remark on the occurrence of ^ and ?-forms that lack available bindings and the parser could balk at some level of murkiness.] * REFACTOR. The separation between file stream, lexical structure, and the context-free oFrugal grammar needs to be navigated better. The grammar for Power-FX has the quality I want to emulate. See the expression grammar in docs/ of . * It is necessary to make clear that these are geneative grammars and there should be some links about those. The Saul Gorn clarity would be useful. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 1.1.0 2024-04-28T16:26Z Clarify restriction on non-primitive "." usage. 1.0.4 2024-01-31T23:31Z Correct links and location of this file. 1.0.3 2024-01-22T22:28Z Adjust to repurposing and the tombstoned origin 1.0.2 2022-08-11T14:32Z Move grammar theory references to grammars.txt 1.0.1 2022-08-06T17:36Z Touch-ups, add missing .NIL primitive (?) 1.0.0 2022-07-31T00:16Z Transpose from oMiser\ob-exp.txt to oFrugal\, changing location links and nothing else yet. 0.2.4 2022-07-29T23:29Z Touch-ups 0.2.3 2022-03-11T01:26Z Correct some blunders in the interpretations and also manage TODOs 0.2.2 2022-02-18T23:49Z Add references, content list, and smooth for addition of examples. 0.2.1 2022-02-18T16:34Z Correct two typos in interpretations, TODOs 0.2.0 2022-01-11T00:18Z Update the Interpretation notation around ‼ { ℰ } and improve the commentary 0.1.0 2022-01-06T01:08Z Propogate (E), accomodating conditional bindings and properly unwrapping argument lists and application to their elements. 0.0.12 2021-05-25T16:45Z Update to deal with conditional lindies as prep for fully-defined semantics and also prep for refactoring the grammar. 0.0.11 2020-12-06-09:36 Add infix "." modeled on method-selection notations from C++ and Java, per Issue #24 0.0.10 2020-07-20-11:22 Change title, manage TODOs, small touch-ups. 0.0.9 2020-02-07-12:17 Expand and manage TODOs, reflecting going all the way up to the oFrugal REPL command input forms. 0.0.8 2019-04-29-11:10 Touch-ups, TODO management, connection to ob.txt along with more detailing of the summary grammar and concrete usage. 0.0.7 2019-02-10-09:29 More touch-ups. Adjust for bindings semantics in in anticipation of including REPL interpretation. 0.0.6 2018-02-03-14:33 Fix typo and correct for absence of an 〈ae〉 that is simply an 〈obap-form〉, including a standalone 〈list-form〉. Hat tip to Roman Susi (@rnd0101). 0.0.5 2018-01-31-10:56 Complete first pass through to 9, Ob-Exp, adding TODOs. 0.0.4 2018-01-30-21:42 extend the formal grammar through 6. Functional Forms 0.0.3 2018-01-30-18:17 Capture the summary grammar and the formalism by which grammatical constructions are interpreted as expressions of obs. 0.0.2 2018-01-29-21:34 Corrected with fixes from Roman Susi (@rnd0101) 0.0.1 2018-01-28-15:26 Provide initial summary grammar for ob-exp. *** end of oFrugal\ob-exp.txt ***