Imperative/Interactive Behavior and "Compute Expressions"

[orcmid]

Although the oMiser model of computation is imperative in the sense of how computation progresses, the effect is entirely "functional." The obap.eval(e) and obap.ap(p, x) computational interpretations preserve well-definedness.

There is no assignment operation or any other kind of "side-effect" in oMiser operation. As mentioned in #29 there are not even exceptions.

At the oFrugal level, declarations of binding names are a kind of assignment operation. However, with the way that such names are defined progressively, the oFrugal language remains context free, syntactically, so long as there is a most-recent previous definition for a binding-name term. Semantically, occurrence of a binding-name term for which there is no previous definition is treated as an error, and it is reported as such. (In the formal semantics there are no failures and special lindies re the defined result of such "unresolvable" back references. It is nonetheless appropriate to issue warnings about them and also fail the continued parsing if it becomes excessive.)

There are many algorithms that are commonly and more-easily expressed when there is some stateful ground which is transformed by progressive computational operations. Named storage entities and the ability to select use and alter them is the historical approach.

In addition, there are situated computations, where there is external context not expressed in the computational model, as such, but on which a computation depends. This can be thought of, broadly, as interactive operation, since there are entities not in evidence. Something so simple as insertion in an output stream, acceptance of external inputs (including random values), synchronization of inputs-and-outputs as interactions, and distributed operation arise.

The Ladder of Complication

There appears to be a nice progression of increased reliance on context-dependent operations that lead to situated cases of concern.

1. The purely functional operations that are captured in the applicative interpretation established in obaptheory.txt, including the .proc extension (Introduce the obapx.PROC/obapx.DEF Extension #22) and devices such as the Capsule Hack (Make Stateful Constructions: The Capsule Hack #23).

2. Local-to-an application stateful progressions that expedite a computation but that do not extend beyond the applicative operation in which they occur. Well-definedness is preserved. This could be expressed at the oFrugal level as a sugaring, with the related oMiser script being akin to (1). The resulting applicative scripts are likely even more inscrutable. Verification of operation becomes difficult; study and operation for even this much could be too daunting. Modeling in oMiser appears to be achievable.

3. Replayable reproducible operations involving external states in some global sense, including progressive but with input streams uncoupled from output streams. The input stream is considered static and fixed even though it might be processed incrementally. Access to a pseudo random-number generator might fit at this level. This requires more data types and also accommodation of some form of environment beyond the simple evref .SELF and .ARG cases. This can be distinguished but it is definitely more than has comfortable expression in oMiser. Understanding that and also appreciating how the limitation is transcended becomes a focus of study. It is important to understand how, here, representation is also reductive and appreciate (at the least) what that entails.

4. Protocol-involved interactions are the ones where there are other parties involved in distributed/interactive activity and it is mutual behavior that is situated. I hypothesize that a different model of computation arises here (and in applications of 3) that is out of reach for oMiser. Whether oMiser is available for algorithmic bits in some blended way is a matter for study.

The Compute Expressions Mystery

My limited exposure to compute expressions is with regard to F# and commentary by Don Syme. Syme refers to computation-expressions as sugar, and my bafflement was over what is it sugaring for? F# has imperative operations with assignment; SML has assignment and the notion of references as well.

In simple Frugalese terms, the equivalent would be a statement oriented construction, {statement₁; ...; statement_n} where the sequence matters. The idea that there are cells, references to cells, and assignment operations of cell content also hinges on the notions of types and also how variables might be handled in a higher-level Frugal.

For oFrugal and oMiser, with oMiser's immutable "typeless" domain, the challenge is to find a counterpart of this syntax in which imperatives and assignment are synthesized in some manner. Some flavor of the Capsule Hack (#23) could provide that, serving as a form of working-set/environment localization. oFrugal will remain an assembler/calculator for Obs though.

Because there is imperative behavior, we now need to distinguish between construction of an ob that is the script, and the actual conduct of the computation that is represented. There is an inversion question. That is, we might have imperatives "inside" a purely-functional case where the imperative behavior is confined and does not in "pollute" the functional context. Then there are imperative situations where those effects matter, but bits and pieces are purely-functional. It is unclear whether separate idioms, and distinct oFrugal notations, are applicable.

We seem to be up against a mystery concerning how much we can isolate the functional with respect to situated imperative action and/or vice versa.

Maybe a Simple Idea

We can consider a translation of rE {s<si\ub>1; s₂; ..., s_n}, where rE is the environment-managing runner and the statement sequence being a sugaring of

^cT(rE.finale)  λ.E(sn) ... λ.E(s2)  λ.E(s1) rE

That is not enough however. There is provision of sequencing treating each s_i as a transform of a stateful input. What's missing is the availability of the compute expression as an entity that can be operated (e.g., as an iterator). There is also a need to deal with short-circuiting among the s_i along with iterations and recursions. Finally compute expressions can have other compute expressions as operands. The sugaring involved may simply be too complex for idiomatic introduction in oMiser. (There might be better resolution in lambda-calculus based approaches identified, for example, by Dana Scott.)

Ultimately, this direction can't be pursued without exceptions, asynchrony, and primitives for it. Then there is how these effects and what gives rise to them can be confined in ways that preserves the ability to reason about their employment in which "pure" functionality swims.

There seems to be more to this as a practical matter. A runner (builder in F#) produces a particular type of object. It ties the { ... } form into a context where stateful connections are exercised. It needs to run much better than chaining of successive semblance feature exercises. Indeed, we don't want anything so costly as all those intermediate proc constructions. There might be a clue about this in the oFrugal expression of ob-exp semantics for sequenced statements.

In the case of F#, we are talking about a source language and for oMiser and (presumably) oFrugal, we are talking about the runtime, the assembled obs and applicative operations.

Color me still baffled.

[to be continued]

[orcmid]

I am a bit concerned about appealing to the Capsule Hack here (#23). There needs to be something that operates with considerable efficiency and also supports reasoning about procedures and (environment) side-effects, stateful environments and how they are circumscribed.

The challenge is how to accomplish operations that are not well-defined because of stateful/interactive effects. These need to be distinguished and the scope of their effect confined in some manner.

There is a kind of inversion to be understood. The ordinary approach is to presume the embedding of the functional in a globally stateful/interactive situation and and the imperatives are connected up into that. But we want to be looking downward somehow. This can be the case of iterators, unless somehow iterators become lodged above. I am baffled. This is my lament.

[orcmid]

I still don't understand the F# Computation Expression.

I do understand that I don't understand it, though. In particular, an F# Computation Expression determines an object, not a result. So my use of runner is inappropriate, and the F# builder term is well-chosen.

The other thing to note is computation expressions are composable.

This has me considering that these are not something that works at the oFrugal/oMiser level.

I will save {s1; ...; sn} for some higher-level approach and omit them from the oFrugal ob-exp.

Since there is no statefulness and assignment in oMiser, I must leave that for now, although how to handle/model statefulness remains a concern.

[orcmid]

I just saw this intriguing article, recommended by Shriram Krishnamurthi.

It addresses compute expressions and some other cases by contrasting the F# constructions and some C# constructions that accomplish the same operations. It seems that continuations are at the core of it.

1. About operational sequence

In oFrugal, the expression a b c d is evaluated as applicative a( b( c ( d) ) ) . This is not always the desired construction for emphasizing the sequence of operation. In this case, piping is useful, borrowing the notation from F#, d |> c |> b |> a to the same effect as a b c d.

This is a simple sugaring, handled entirely by the grammar and interpretations. We do have to consider precedence with it, however.

2. Compute expressions

There is another well-known sequence-of-operation, and we have reserved { s1 ; s2; .., sn} for that. Notationally there is an optional runner prefix and `runner:{s1; s2; .... sn} is the general case.

For oFrugal, there is more here than sugar at the syntactic level, and that's problematic. We'd like this form, but we have to consider how it can be done generically without changing oFrugal parsing while having the s[i] be too contorted. The passing around and using of continuations is the challenge.

3. Figuring out how passing around of continuations can be abstracted

The use of callbacks and continuation needs to be understood, and then we need to see how well we can sugar it in 2, above. We'd like not to presume any kind of system-provided functions, but there might not be a way out of that. The nature of runner and having a default/inherited one might be where we accomplish that.

more analysis to come