Resolving infix/applicative-operation Precedence

[orcmid]

Because of spacing and use of brackets, there is a question whether applications should happen before or after infix operations, such as ::. I had been operating on the assumption that applicative operations are carried out first in determining operands of ::. There is a suggestion that :: is better to perform first, and some examples appear natural that way.

I need to resolve this, because the oFrugal syntax for expressions to evaluate as obs depends on the answer.

I am going to look in at least two places,

• In the grammar for Standard ML and its satisfaction in the implementation of SML/NJ.
• Perhaps in the more textual form of APL, the language "J" for how it does things, if it ever gets anything but strict right to left with no operator precedence.

What I'd like to see is good examples and convincing rationale.

Resolution: Applications Are Performed Before :: Operations

• This is reflected in the ob-exp grammar set forth in Question #14, Resolving oFrugal Appicative-Expression Grammar.

[orcmid]

No Further with APL and J

I looked into the J Language and its current status.

I have difficulty appreciating that J provides an ASCII text-form descendent of APL and the Backus FP/FFP approach. That is worth investigating further.

For the purpose of this Question, the lack of infix operators of any kind and some peculiarity of definition structure in J offers nothing with respect to applicative-expression mixing with infix operators, so J Language will not be considered further here.

[orcmid]

Interesting Situation with SML

I verified the SML syntax specified in

• The Definition of Standard ML (Revised) of 1997
• Paulson's ML for the Working Programmer, 2nd Edition, 1998 reprint
• Standard ML of New Jersey v110.82 build of 2017-10-25.

In all of these there are (1) peculiar non-treatment of unary operators and (2) evaluation of applicative expressions before evaluation of binary operators.

Non-Unary Operators

Instead of having unary operators in the SML grammar, certain special characters are permitted in a special form of identifiers. Appearances in operator position in applicative expressions is expected to have definitions as functions. This also means that the SML left-to-right application order applies, contrary to the case of unary operators in most notations.

For example, the candidate oFrugalese expression ‵ ‵ nester would, in SML, be treated as (‵ ‵) nester rather than ‵ (‵ nester) the case in oFrugalese. Likewise, in SML, ‵‵ is treated as a different identifer than a single ‵. For oFrugalese, the stacking in ‵‵nester is proposed to have the same interpretation as ‵(‵nester).

Conclusion. The SML arrangement may be suited to ML application as a "Meta Language." oFrugalese ob-exp format is more rigidly specialized. In oFrugal ob-exp syntax, ‵ will be a special symbol recognized syntactically as a unary operator that applies first before applications and binary operations. Also, ‵ is not an identifier in oFrugalese, it is a unary operator in the grammar and its interpretation is fixed.

:: and Applicative Expressions

In SML applicative expressions are evaluated first as operands of binary operations. This is clear in the SML expression p a x :: p b y :: [ ] evaluated as ((p a) x) :: ((p b) y) :: [ ]. Using the same precedence, the oFrugal interpretation of the same form is as (p a) x :: (p b) y :: [ ] because of right-to-left evaluation of applicative expressions in the absent of other grouping. Giving :: higher precedence in oFrugal will not preserve the associativity of :: in the illustrated case. Also, breaking up the applicative form between ... :: (p b) y :: ... is unclear and makes awkward cases. It is difficult to have a smooth interpretation of the :: as right-associative binary operations without having :: at lower precedence than applicative-expression evaluation.

Of course, parentheses can always be used to make the intended interpretation very clear. It is desirable, just the same, to have the cases where parentheses don't make any difference to be ones that provide straightforward expression.

Conclusion. It appears that the SML precedence, even with its different applicative-expression evaluation ordering, works best for oFrugal ob-exp grammar. In oFrugal, f x :: g y will be equivalent to (f x) :: (g y), and likewise for the completely equivalent f(x) :: g(y).

Please discuss any concerns that favor the contrary.

[rnd0101]

Good analysis!

One point: Use of application does not propagate to the oMiser level. We need to consider instead what will prevail in the scripts: Are building large oMiser structures (obs) and then do a few operations on them, or we have a lot of small blocks, which application will cling together (in oFrugal)? Is there any value in more conveniently express larger "pure ob" structures?

Please, give also explicit associativity examples for application - it seems to be lacking from conclusion. Application seems to be more natural with left-to-right, isnt't it?

Also note on:

+      andalso let fun p(f) = (fn x => f(x)) 
+               in p a (L"M" ## L"X" ## NIL) :: p b (L"X") :: [] 

this does not really distinguish, what is the application order (p a)(L...) or p(a(L...)) if I understand SML correctly the result will be the same?

[orcmid]

@rnd0101 Use of application does not propagate to the oMiser level.

I am thinking, now, that oFrugal is more of an "ob calculator" level. In that sense, none of the applicative expressions or the ‵ and :: operations "propagate." They are all carried out to deliver an ob.

The resulting ob can be a script that has an useful interpretation as p in an obap.ap(p,x). When that application happens, the ob p may direct evaluation of applicative operations. This is the case for application of ^cS.

Have I caught your meaning?

[rnd0101]

The difference is ‵ and :: operations become a structure, they are directly encoded in the ob, while application is evaluated here and now, in oFrugal. But, yes, maybe there is not that much of a difference.

[orcmid]

@rnd0101 Please, give also explicit associativity examples for application - it seems to be lacking from conclusion. Application seems to be more natural with left-to-right, isnt't it?

I am going to raise the applicative-expression grammatical ordering as a separate topic. It is proposed that an ob-exp expression

.A .B .B .B [M, N, O, P, Q, R]

yield the same value as

(.A :: .B :: .B :: .B :: .ARG) [M, N, O, P, Q, R]

namely, P.

One result, by design, will be that these ob-exp expressions all yield that same result.

(.A :: .B :: .B :: .ARG) .B [M, N, O, P, Q, R]
(.A :: .B :: .ARG) .B .B [M, N, O, P, Q, R]
(.A :: .ARG) .B .B .B [M, N, O, P, Q, R]

Here are some sticky spots.

(.A :: .ARG) (.B :: .ARG) .B .B [M, N, O, P, Q, R]
(.A :: .ARG) .B (.B :: .ARG) .B [M, N, O, P, Q, R]
.A (.B :: .ARG) .B .B [M, N, O, P, Q, R]

not intended to produce the same result as the previous examples. It is just about the interpretations of these based on syntax alone.

One consistent interpretation is that parenthesized/bracketed ob-exps that have something to their left in an applicative expression group to that left, in turn, in this manner:

((.A :: .ARG) (.B :: .ARG))  ( .B ( .B[M, N, O, P, Q, R] ) )
(.A :: .ARG)  (  (.B (.B :: .ARG))
                     (.B[M, N, O, P, Q, R])  )
(.A (.B :: .ARG)) ( .B (.B [M, N, O, P, Q, R]) )

The three forms are perhaps better expressed as the equivalent

(.A :: .ARG)( .B :: .ARG, 
                  .B .B [M, N, O, P, Q, R] )
(.A :: .ARG)(  .B(.B :: .ARG, 
                        .B [M, N, O, P, Q, R] ) )
.A (.B :: .ARG, .B .B [M, N, O, P, Q, R] )

NOTE: *This is about parsing and not whether or not such evaluations make any sense, even though there are definite, however strange, applicative interpretations of the examples given.

We need to look at sensible examples to see what bracketing works naturally given such a grouping rule. Resolution of this will be the subject of Question #14.

Update: Ensure that all ARG occurrences are as .ARG

[rnd0101]

Yes, this is true in the current implementation:

$ python shell.py 
oFrugal shell for oMiser computational model
Press Ctrl-D to leave.

oFrugal> .A .B .B .B [M, N, O, P, Q, R]
P

oFrugal> (.A :: .B :: .B :: .B :: .ARG) [M, N, O, P, Q, R]
P

and the rest:

oFrugal> .A .B .B .B [M, N, O, P, Q, R]
P

oFrugal> (.A :: .B :: .B :: .B :: .ARG) [M, N, O, P, Q, R]
P

oFrugal> (.A :: .B :: .B :: .ARG) .B [M, N, O, P, Q, R]
P

oFrugal> (.A :: .B :: .ARG) .B .B [M, N, O, P, Q, R]
P

oFrugal> (.A :: ARG) .B .B .B [M, N, O, P, Q, R]
ARG

oFrugal> (.A :: ARG) (.B :: .ARG) .B .B [M, N, O, P, Q, R]
ARG

oFrugal> (.A :: ARG) .B (.B :: .ARG) .B [M, N, O, P, Q, R]
ARG

oFrugal> .A (.B :: .ARG) .B .B [M, N, O, P, Q, R]
P

oFrugal> (.A :: ARG) ( (.B :: .ARG) .B .B [M, N, O, P, Q, R] )
ARG

oFrugal> (.A :: ARG) ( (.B (.B :: .ARG)) .B [M, N, O, P, Q, R] )
ARG

oFrugal> (.A (.B. :: ARG)) (.B .B [M, N, O, P, Q, R])   
Parsing error: Rule 'space' didn't match at '. :: ARG)) (.B .B [M' (line 1, column 8). <--- typo?

oFrugal> (.A (.B :: ARG)) (.B .B [M, N, O, P, Q, R])
(P :: (Q :: R))

[orcmid]

oFrugal> (.A :: ARG) .B .B .B [M, N, O, P, Q, R]
ARG

oFrugal> (.A :: ARG) (.B :: .ARG) .B .B [M, N, O, P, Q, R]
ARG

oFrugal> (.A :: ARG) .B (.B :: .ARG) .B [M, N, O, P, Q, R]
ARG

and a few others need (.A :: .ARG) with .ARG, not ARG.

[rnd0101]

I have one more idea - please say if you like it or now. Why not having two syntactical ways to express application? For example, there could be high-priority juxtaposition as you like and also low-priority another operation, I denote by | below:

oFrugal> (^has (31, [1,2,3,3,3,3,3,31,2])) ^bSAY
TRUE

oFrugal> (^has (311, [1,2,3,3,3,3,3,31,2])) ^bSAY
FALSE

oFrugal> ^has (311, [1,2,3,3,3,3,3,31,2]) | ^bSAY
FALSE

That is, f(x) ≡ f | x.

Of course, another symbol can be chosen. Plus, for example, there can be nice syntax for a pipe: f(x) ≡ x |> f .

[orcmid]

@rnd0101 I have one more idea - please say if you like it or now. Why not having two syntactical ways to express application?

In the syntax summarized at Question #14 now, there are already two ways and they can be mixed. For example,

(^has (31, [1,2,3,3,3,3,3,31,2])) ^bSAY

is also expressible as

^has (31, [1,2,3,3,3,3,3,31,2]) ^bSAY

or (my favorite)

^has(31)[1,2,3,3,3,3,3,31,2] ^bSAY

which reduces nesting and also avoids large spans of ( ... ).

Choosing expressive styles will depend on the ob-exp expression author, of course.

[orcmid]

Resolution: Applications Are Evaluated Before :: Operations

The discussion on Question #14 seems to have wound down. In that discussion and in the grammar now defined more rigorously at ob-exp.txt, the :: binary operator has precedence lower than application. This makes sense with regard to the associativity of ::.

With that in mind, I am closing this inquiry as resolved.