orcmid
commented
4 years ago Deriving pFinder script implementing finder(feature, cases)
Using functional Frugalese as a pseudo-code is rather confusing with the ob-exp notation of oFrugal as the assembly language for obs and obs taken as scripts.
Distinct use of letter-case for primitives helps differentiate: lower-case in pseudo-code, upper-case in oFrugal ob-exps.
Here is a demonstration with hand-compiled derivation of pFinder.
(WARNING: NONE OF THESE SCRIPTS HAVE BEEN VERIFIED. That will be easier to do when we have oFrugal to do progressive constructions and confirmations.)
First
(if is-singleton(cases)
then cases
else if feature = .b .a cases
then .a cases
else again .b cases )has the following hand-compiled ob-exp script
.EV :: (.D :: cases :: .B :: cases)
:: `( cases
:: .EV :: (.D :: feature :: .B :: .A :: cases)
:: `( (.A :: cases)
:: again :: .B :: cases
)
)Next,
λ.cases
(if is-singleton(cases)
then cases
else if feature = .b .a cases
then .a cases
else again .b cases )is achieved by simple substitution in the script ob-exp.
.EV :: (.D :: .ARG :: .B :: .ARG)
:: `( .ARG
:: .EV :: (.D :: feature :: .B :: .A :: .ARG)
:: `( (.A :: .ARG)
:: again :: .B :: .ARG
)
)In this case,
rec.again λ.cases
(if is-singleton(cases)
then cases
else if feature = .b .a cases
then .a cases
else again .b cases )also follows by simple substitution.
.EV :: (.D :: .ARG :: .B :: .ARG)
:: `( .ARG
:: .EV :: (.D :: feature :: .B :: .A :: .ARG)
:: `( (.A :: .ARG)
:: .SELF :: .B :: .ARG
)
)Abstraction of a variable can also be more complicated, as when we want to handle
let finder(feature)
= rec.again λ.cases
(if is-singleton(cases)
then cases
else if feature = .b .a cases
then .a cases
else again .b cases )where the rewriting to incorporate the feature operand into the recursive script is more involved.
^pFinder = .C :: `.EV
:: .C :: `(.D :: .ARG :: .B :: .ARG)
:: .E :: .C :: `.ARG
:: .C :: `.EV
:: .C :: .C :: ` .D
:: .C :: (.E :: .ARG)
:: `(.B :: A :: .ARG)
::` `( (.A :: .ARG)
:: .SELF : : .B :: .ARG
) ;
oMiser is not object-oriented in any sense that is applied in computer science and programming practice. The pure functional nature of the oMiser computational model would, on the face of it, suggest that encapsulating any state and operating via successive transformations of that state is not intrinsically available. That's not the case.
There are oMiser representations of encapsulation that provide for binding of state with scripts for acting on the state. A particular representation, the Capsule Hack convention, hinges on how enclosures can be used to connect a script and state data within an applicative individual.
The Capsule convention is termed a hack to direct attention to four considerations.
Capsules are an emergent arrangement, however latent in the computational model itself. Capsules are representation or interpretation, but produced bottom-up, a kind of "hey, look at what I can make oMiser do." It is grounded in the computation model's reliance on enclosures as a representation of the K combinator, capturing a way that a script, p, can access an enclosed portion of itself as unevaluated data, the current state, within ap(p, x) operation. (See combinators.txt for interpretation of combinatory structure ‹ca› in ‹ob›.)
Capsules are rather arbitrary and crufty, being a chosen representation that is not inherent at the computation model level yet assured by the stored-program principle as honored by the oMiser formulation.
Capsules are crude demonstrations that very useful computer codes, including classy algorithms, will not resemble the problem they are organized to solve. This is a critical factor when we consider automated deductions about oMiser scripts as representations of higher-level notions.
That Capsules be so terribly inscrutable and confined to complex arrangements of obs is something that must be overcome by ways of presenting representations at a level that captures the intended sense of a semblance and allows results of applications to be expressed at the intended level. The fundamental case will be introduction of strings of characters, with arithmetic another. The reasoning for that will be based on capabilities involving the Capsule Hack.
The development all the way to use of factory scripts as creators of semblance-instance constructors is not the most evident and heart-warming scheme. To ascertain value beyond mere demonstration of the possibility will take experimental demonstration and assessment of the degree to which confident usage is achievable.
1. Capsules
By convention, a capsule consists of an individual ob instance of the form
and the oFrugal (ob-exp) hand-compiled script implementing that construction is along the lines of
where
^obStateare sometimes use in specimen scripts to emphasize where variable are intended despite typographical limitations in code blocks.When obState is constrained to be a canonical form with respect to the abstract interpretation, equality of pInstance corresponds to identity of the represented abstract entities. Otherwise, any identity achieved by simulation must be verified by other means.
1.1 Semblance of Class Domain Instances
The notion of semblance (a corruption of resemblance) is employed here to signify a computationally-accomplished manifestation of an abstraction. There are many ways to have accomplished that, and there are additional incidental characteristics that accompany the representation of computational interpretations. Semblance is a pragmatically-appropriate distinction of such computational representations from the abstraction they stand as interpretations for.
Even when there is establishment of a clear interface boundary for the manifestation of a computational class, pragmatic features remain inescapable part of the established interface.
In this setting, there are two senses of "class." The shared conception is that there is a quality of an entity -- satisfaction of some predicate -- that determines an entity's membership in a particular class. Here capsules are taken to be computational-interpretations of abstract class domain entities, and the shared quality is having the capsule instance pattern with the same pRep. This is a syntactic distinction, not a semantic one. It is one semblance out of many. Generally, there can be many semblances of the same class, differentiated by differences in pRep, the representation of obState values, and the manner in which features of the semblance are manifest, both syntactically (by different namings) and semantically (by variation among operations and operands).
Demonstration that semblances be effective computational interpretations of some (semantic) abstract classes is by the constraints on obState that are honored in the creation of an initial pInstance and in how subsequent operations via application of the capsule to appropriate operands constitute interpretation-preserving representations.
In this arrangement, pInstance occurs as an individual, a kind of literal. As such it is immutable. And, at the same time, the pInstance provides a tight binding of the obState to the pRep by which semblance is achieved and preserved.
1.2 Applicative Interpretation of Capsules
The convention for use of a capsule is via
such that in ap-internal evaluation of the pRep script,
and a new capsule that differs only by introduction of obNext for obState is produced by script
The oMiser convention for producing traces for operations that cannot go further is sustained here by evaluating script
when feature (.arg in that context) is not a defined case.
These characteristics of the Capsule Hack provide the framework for computational interpretation of abstract classes by tightly packaging together (1) the representation of domain entities in obState and (2) associated computational interpretations of theoretical functions over such entities via pRep operations.
2. Idiomatic Semblances
There are additional conventions for the specification and operation of pRep scripts.
2.1 The List Searching Idiom
The feature cases of a Capsule Hack semblance can be represented by a list of pairs,
with default the case that is determined when feature does not match any of the ci.
The selection of cases for values of feature is obtained in functional pseudo-code by
In this arrangement, the result is always an ob r such that .a(r) is the corresponding case for the specified feature (or the default case otherwise). This is the Cluster Hack idiom for selecting cases by explicitly-matching obs. A close variant has the ci be scripts representing predicates, so the
portion becomes
2.2 Semblance Feature Selection
There is technical improvement by restating the definition of find(feature, cases) in a way that has feature fixed in the iteration through cases.
(In this Frugalese functional pseudo-code, the infix-dot notation (#24) provides a way to signal left-to-right application and is also a sugaring for rec and λ being defined by applicative scripts in the computational model. Hand-compiled scripts here illustrate how applicative abstraction can be mechanized in oMiser model of computation.)
Cluster Hack, cases are the same for all instances of the same semblance. This fixed nature is represented by
2.3 Semblance Instance Arrangement
Although we have functional characterizations for selector and finder, there is also indication of where there can be "code motion": evaluating some elements in advance for repeated use without repeated derivation, as in the binding of cases in the result from selector(cases) and in the binding of feature once in the recursive procedure yielded by finder(feature).
The fixed pRep value in a Capsule Hack Semblance Instance consists of the formulation
with selector(cases) returning the script that represents the selector-defined function for accepting feature operand. Because the selector result is not (directly) recursive, we can simplify by in-lining selector(cases), giving
and any .arg that is requested at the top level of that script sequence will correctly match to feature in the evaluation of ap(pInstance, feature). In-lining an applicative script is a counterpart of similar practices in optimizing compilers for conventional computers. It will arise often in hand-compiling oMiser applicative scripts.
The ob-exp code for pRep is then
This will be fully worked out in the oFrugal translations of the functional pseudo-code of selector and finder. For now, we trust that the elimination of a level of application is warranted from what is known about the script returned by selector(cases).
What happens with Capsule Hack semblance of an abstract data type is is that each defined feature operand will determine a script to be evaluated in the same context as evaluation of pRep. That is (from 1.2 above),
To complete construction of an instance, a specific list structure for cases is required along with establishment of the (initial) obState.
In addition, all semblances constructed via the Capsule Hack will behave the same when cases has no entry for the feature operand. The singleton that ends the cases list will always be
conforming to (1.2) by providing a trace where there is no way to take the evaluation further.
3. Semblance-Instance Constructors
The nature of a Cluster Hack semblance instance is as follows in the development so far.
the common pRep component of every semblance instance is determined by the cases list supplied to selector(cases) in the instance construction. This is what is typical of all instances of the same semblance.
validity of the initial obState must be established by some means.
3.1 Thinking Out-Loud
One possibility is to have a "new" feature such that instance.new(setup) produces a new instance with _obState derived from setup. There are two engineering objections: (1) how unacceptable state operands are treated and (2) whether one wants the ability to make new instances to be available to any function where instance is supplied as an operand. The second consideration applies to other methods as well, and this may involve differentiation of interfaces, a topic for later consideration.
For now, consider
Here prefix CH identifies the Cluster Hack conventions and CHT will be adjusted to identify a particular semblance of a "type.,"
The pCastOb will typically operate as follows
The pCastOb can also be more elaborate, deriving a state in different ways for given obSetup operands. That would be a semblance-specific situation. The ob.e(obSetup) yield is still employed in the case that the operand is invalid and the CHTConstructor must fail (resulting in a suitable trace)..
3.2 Factory Determination of Constructor Failure Modes
The ob.e(obSetup) result is distinguishable as a form of trace. What is wanted as the CHTConstructor in this situation is a trace-form of pCHTInstance that carries enough of its origin to be revealing under inspection.
In the invalid construction case, it is straightforward to replace obCases by the always-tracing singleton,
and the remaining question is what else to provide. A simple approach would be to employ
assuming pCHTConstructor to be a proc, perhaps. The resulting pCHTInstance is itself a trace and the obState of that is additional trace.
3.3 A Hack Too Far?
The test of this formulation will be in the successful creation of usable scripts that represent the signified functions under oMiser application. Updates of this issue will reflect implementation experience. There can then be assessment of utility, even as a demonstration.