Signifying Application by Juxtaposition
PROVISIONAL RESOLUTION 2018-02-02: The grammar summarized here is being taken as the form of oFrugal REPL ob-exp expressions for the continuing work in developing mock-ups and prototype reference code. Questions, below, around practical use remain open. Extensive practice will be obtained before fixing on a version 1 of oFrugal. To protect against files used across breaking changes, *.ofrugal texts will have a version identified hash-bang prolog.
For oFrugal, it is proposed that application, denoted by (spaced-separated) juxtapositions, be right associative. That is,
h g f x = h ( g(f x) )
- White space is required anywhere that it serves to avoid combining two adjacent meant-to-be-separate identifiers into one. White space, including comments, is permitted anywhere it does not split a meant-to-be single identifier into more than one.
- Parentheses are required any time the default associative ordering is not intended.
- In the illustrative applicative expression, h, g, and f appear as operators and x, f x, and g f x appear as operands of applicative operations.
Similarity of Applicative Order between oFrugal and oMiser
The default right-to-left build up of operations in an oFrugal ob-exp evaluation corresponds to how build-up is treated in oMiser evaluations of applicative expressions in obap.eval(exp) and appearing as p in an obap.ap(p, x) evaluation. For example, all of the following oFrugal ob-exp examples yield the same result.
h g f x
(‵h :: ‵g :: ‵f :: .ARG) x
(‵h :: ‵g :: .ARG) f x
(‵h :: .ARG) g f x
Proposed Parentheses for Argument Order
In oFrugal applicative expressions, parentheses can be used to alter the default applicative order.
For example, as an oFrugal ob-exp, the representation by ^cS of combinator S satisfies the standard definition.
((^cS x) y) z = (x z)(y z) = (x z) y z = x(z) y z
where the last two forms rely on default ob-exp applicative order to eliminate redundant parentheses. The form x(z) is a function-form signifying that x(z) evaluates x as the operator applied to the evaluation of the y to yield the ob that is applied to the result of any applicative expression on the right.
The expression of arguments in a function-form can be in a comma-separated list.
f(g,h,z) =(((f g) h) z)
^cS(x, y, z) = ^cS(x, y) z = x(z, y z) = x(z) y z
Eliminating Ambiguity
The proposed syntax for a function-form is that it never begins with a "(" or "[" so it is clear that it is not part of a preceding function form. That rule is relaxed only when there is nothing preceding the form in the applicative expression in which it appears.
The following summary of the ob-exp grammar (in original BNF) captures the concrete syntax without getting into grammatical niceties. Viewing properly may depend on browser and text-editor font capabilities.
〈term〉 ::= 〈lindy〉 | 〈primitive〉 | 〈binding-name〉
〈list-terms〉 ::= 〈ob-exp〉 | 〈list-terms〉, 〈ob-exp〉
〈list-form〉 ::= [ ] | [ 〈list-terms〉 ] | [ 〈list-terms〉 :]
〈parameters-form〉 ::= ( 〈list-terms〉 ) | 〈list-form〉
〈function-form〉 ::= 〈term〉 | 〈function-form〉 〈parameters-form〉
〈obap-form〉 ::= ( 〈ob-exp〉 ) | 〈list-form〉 | 〈obap-form〉 〈parameters-form〉
〈unary〉 ::= 〈function-form〉 | ‵ 〈obap-form〉 | ‵ 〈unary〉
〈ae-tail〉 ::= 〈unary〉 | 〈unary〉 〈ae-tail〉
〈ae〉 ::= 〈ae-tail〉 | 〈obap-form〉 〈ae-tail〉
〈binary〉 ::= 〈ae〉 | 〈ae〉 :: 〈binary〉
〈ob-exp〉 ::= 〈binary〉
Not all of the permitted forms appear meaningful on the face of it. They are permitted for generality and to honor the fact that every ob has an applicative interpretation, no matter its original manner of construction. It is expected that coding practices will converge on expressive and understandable forms in interchange and presentation.
A formal version of the grammar, at ob-exp.txt, is used to rigorously specify the evaluation of an ob-exp to yield a single canonical ob.
QUESTION
It should be clear that the above BNF provides an unambiguous context-free grammar for ob-exp.
The key question is whether, after some modicum of use, it becomes straightforward to create ob-exp expressions that are correct for a given purpose and that it also be straightforward to read them.
Practice is called for. While one can conceive and write what appear to be pathological ob-exps, focus should be on intended practical ones and whether or not they are sufficiently expressive.
I conjecture that, not only is the grammar context-free, there is a straightforward precedence parser for conversion of an ob-exp to the resulting ob. Satisfaction will be in demonstration of an operational ob-exp parser for oFrugal reference implementations.
Related Material
Update 2018-01-29: Correct ‵ 〈unary-form〉 to ‵ 〈unary〉.
Add missing | in 〈list-form〉 rule, both with a hat tip to @rnd0101.
Update 2018-02-02: Touch up text and declare the provisional resolution of the grammar to be used in oFrugal mock-up and prototype work.
Signifying Application by Juxtaposition
PROVISIONAL RESOLUTION 2018-02-02: The grammar summarized here is being taken as the form of oFrugal REPL ob-exp expressions for the continuing work in developing mock-ups and prototype reference code. Questions, below, around practical use remain open. Extensive practice will be obtained before fixing on a version 1 of oFrugal. To protect against files used across breaking changes, *.ofrugal texts will have a version identified hash-bang prolog.
For oFrugal, it is proposed that application, denoted by (spaced-separated) juxtapositions, be right associative. That is,
Similarity of Applicative Order between oFrugal and oMiser
The default right-to-left build up of operations in an oFrugal ob-exp evaluation corresponds to how build-up is treated in oMiser evaluations of applicative expressions in obap.eval(exp) and appearing as p in an obap.ap(p, x) evaluation. For example, all of the following oFrugal ob-exp examples yield the same result.
Proposed Parentheses for Argument Order
In oFrugal applicative expressions, parentheses can be used to alter the default applicative order.
For example, as an oFrugal ob-exp, the representation by
^cSof combinator S satisfies the standard definition.where the last two forms rely on default ob-exp applicative order to eliminate redundant parentheses. The form x(z) is a function-form signifying that x(z) evaluates x as the operator applied to the evaluation of the y to yield the ob that is applied to the result of any applicative expression on the right.
The expression of arguments in a function-form can be in a comma-separated list.
Eliminating Ambiguity
The proposed syntax for a function-form is that it never begins with a "(" or "[" so it is clear that it is not part of a preceding function form. That rule is relaxed only when there is nothing preceding the form in the applicative expression in which it appears.
The following summary of the ob-exp grammar (in original BNF) captures the concrete syntax without getting into grammatical niceties. Viewing properly may depend on browser and text-editor font capabilities.
〈term〉 ::= 〈lindy〉 | 〈primitive〉 | 〈binding-name〉
〈list-terms〉 ::= 〈ob-exp〉 | 〈list-terms〉, 〈ob-exp〉
〈list-form〉 ::= [ ] | [ 〈list-terms〉 ] | [ 〈list-terms〉 :]
〈parameters-form〉 ::= ( 〈list-terms〉 ) | 〈list-form〉
〈function-form〉 ::= 〈term〉 | 〈function-form〉 〈parameters-form〉
〈obap-form〉 ::= ( 〈ob-exp〉 ) | 〈list-form〉 | 〈obap-form〉 〈parameters-form〉
〈unary〉 ::= 〈function-form〉 | ‵ 〈obap-form〉 | ‵ 〈unary〉
〈ae-tail〉 ::= 〈unary〉 | 〈unary〉 〈ae-tail〉
〈ae〉 ::= 〈ae-tail〉 | 〈obap-form〉 〈ae-tail〉
〈binary〉 ::= 〈ae〉 | 〈ae〉 :: 〈binary〉
〈ob-exp〉 ::= 〈binary〉
Not all of the permitted forms appear meaningful on the face of it. They are permitted for generality and to honor the fact that every ob has an applicative interpretation, no matter its original manner of construction. It is expected that coding practices will converge on expressive and understandable forms in interchange and presentation.
A formal version of the grammar, at ob-exp.txt, is used to rigorously specify the evaluation of an ob-exp to yield a single canonical ob.
QUESTION
It should be clear that the above BNF provides an unambiguous context-free grammar for ob-exp.
The key question is whether, after some modicum of use, it becomes straightforward to create ob-exp expressions that are correct for a given purpose and that it also be straightforward to read them.
Practice is called for. While one can conceive and write what appear to be pathological ob-exps, focus should be on intended practical ones and whether or not they are sufficiently expressive.
I conjecture that, not only is the grammar context-free, there is a straightforward precedence parser for conversion of an ob-exp to the resulting ob. Satisfaction will be in demonstration of an operational ob-exp parser for oFrugal reference implementations.
Related Material
::operations was investigated in Question Resolving infix/applicative-operation Precedence #13.Update 2018-01-29: Correct
‵ 〈unary-form〉to‵ 〈unary〉.Add missing
|in〈list-form〉rule, both with a hat tip to @rnd0101.Update 2018-02-02: Touch up text and declare the provisional resolution of the grammar to be used in oFrugal mock-up and prototype work.