Resolving oFrugal Applicative-Expression Grammar

[orcmid]

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

• The resolution of the relative precedence of applicative expressions and binary :: 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.

[rnd0101]

Ok. So now I need to make oFrugal's grammar more complex to care for this case correctly (right now not according to the above):

oFrugal> h (g) f x
(h :: (g :: (f :: x)))

Not yet sure whether this will make the grammar ambiguous.

For example, h (g) (f x) - is it h ((g) (f x)) or (h (g)) (f x) ? I bet the latter, so that "calls" propagate from left, otherwise applications from right, with "calls" having greater priority, right?

[orcmid]

@rnd0101

oFrugal> h (g) f x
(h :: (g :: (f :: x)))

I see how handy Lindies are in this case.
The above result should be (h :: g) :: f :: x, the same as (h :: g) :: (f :: x).

For example, h (g) (f x) - is it h ((g) (f x)) or (h (g)) (f x)? I bet the latter ...

Yes, the grouping is to the left, so h (g) (f x) = (h g) (f x) = h(g, f x). As an ob-exp of lindies, the result should be the ob (h :: g) :: f :: x.

I have an unambiguous grammar for this. I will dress it up a little and present it.

[rnd0101]

👍 I've found an informal survey of juxtaposition in programming languages - interesting, that we touched all of them in our discussion already (LISP, Forth, ML, APL, ...).

[orcmid]

@rnd0101 I've found an informal survey of juxtaposition in programming languages - interesting, that we touched all of them in our discussion already (LISP, Forth, ML, APL, ...).

Unfortunately, the examples with respect to ML under Applicative FP are simply incorrect. In LISP/Scheme, the remainder is a list taken as the argument.

The LISP examples are better expressed in function form in the following table, where the ob-exp case mirrors the ML case. (In ML, the elements of variable-length lists must be of the same datatype, which is trivially true for oFrugal, of course.)

LISP/Scheme	Applicative/ML	ob-exp
(+ 1 2 3)	+ [1, 2, 3]	^sum [^1, ^2, ^3]
(* 2 2 (+ 0 3 4) )	* [2, 2, + [0, 3, 4] ]	^product [^2, ^2, ^sum [^0, ^3, ^4] ]

Since we don't have a numerical datatype and its arithmetic, I had to fudge the ob-exp for brevity.

In ob-exp format, ^ is part of the binding name, and I see here the benefit of allowing any alphanumeric string for the rest of it, with no need to start with a letter after the ^. Of course, the result is going to be a canonical ob, and reading that is a challenge. There are ways around that that to be demonstrated when we have a programming cookbook and attention on complexity.

[rnd0101]

👍 I have not yet had time to input the grammar to antlr, but I foresee left-recursion problem for the PEG I am using in the current oFrugal shell implementation due to at least this case of left-recursion:

〈obap-form〉 ::= ( 〈ob-exp〉 ) | 〈list-form〉 | 〈obap-form〉 〈parameters-form〉

usually, left recursion can be eliminated, so no worry.

Also pipe is missing here 〈list-form〉 ::= [ ] | [ 〈list-terms〉 ] | [ 〈list-terms〉 :], IMHO.

Also, what is 〈unary-form〉?

More left-recursion cases are 〈list-terms〉 ::= 〈ob-exp〉 | 〈list-terms〉, 〈ob-exp〉 and 〈function-form〉 ::= 〈term〉 | 〈function-form〉 〈parameters-form〉. BTW, why parameters-form also includes a list? Will a [x,y,z] have same priority as a (x,y,z)?

[orcmid]

@rnd0101 Also pipe is missing here 〈list-form〉 ::= [ ] | [ 〈list-terms〉 ] | [ 〈list-terms〉 :], IMHO.

I don't understand about pipe. I have not used it. I don't understand the need. I also thought pipe was an operator. Please clarify.

[orcmid]

@rnd0101 Will a [x,y,z] have same priority as a (x,y,z)?

Yes.

[orcmid]

@rnd0101 what is 〈unary-form〉?

Oh, it was a typo. It should be 〈unary〉. Fixed.

[rnd0101]

Sorry. By pipe I mean | - it's missing between two list representations in the grammar.

[orcmid]

@rnd0101 usually, left recursion can be eliminated, so no worry.

There is no occasion for back-tracking with the grammar I have provided. It should be possible to use a form of left-recursive parsing pattern that takes the widest form it can find on patterns such as these two.

〈obap-form〉 ::= ( 〈ob-exp〉 )  〈parameters-form〉...   
              | 〈list-form〉  〈parameters-form〉...

where ... signifies none-or-more in succession.

This is a generative grammar. A parser needs a variety of adjustments, and the generative grammar I offered is simplifed. The official one will be slightly more complicated so that the semantics is properly specifiable. Exactly the same expressions will be allowed.

[orcmid]

@rnd0101 Sorry. By pipe I mean | - it's missing between two list representations in the grammar.

Good eye. Fixed.