orcmid/miser

The Miser Project is practical demonstration of computation-theoretical aspects of software

miser's Issues

Resolving oFrugal Applicative-Expression Grammar

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 #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.

Change Internet/docs/blogs references from oMiser/ob-exp to oFrugal/op-exp

"Textual" substitution fails?

In the following plain .D is not equivalent to .A .D .B, even though .A .D .B evaluates to .D:

oMiser> (.D "x" "x") ("eq" "neq")
INPUT: ((.D :: ("x" :: "x")) :: ("eq" :: "neq"))
ev (.SELF) (.ARG) ("x") -> "x"
ev (.SELF) (.ARG) ("x") -> "x"
ev (.SELF) (.ARG) ((.D :: ("x" :: "x"))) -> .A
ev (.SELF) (.ARG) ("eq") -> "eq"
ev (.SELF) (.ARG) ("neq") -> "neq"
ap ("eq") ("neq") -> ("eq" :: "neq")
ev (.SELF) (.ARG) (("eq" :: "neq")) -> ("eq" :: "neq")
ap (.A) (("eq" :: "neq")) -> "eq"
ev (.SELF) (.ARG) (((.D :: ("x" :: "x")) :: ("eq" :: "neq"))) -> "eq"

OUTPUT: "eq"

oMiser> .A .D .B
INPUT: (.A :: (.D :: .B))
ev (.SELF) (.ARG) (.A) -> .A
ev (.SELF) (.ARG) (.D) -> .D
ev (.SELF) (.ARG) (.B) -> .B
ap (.D) (.B) -> (.D :: (`(.B) :: .ARG))
ev (.SELF) (.ARG) ((.D :: .B)) -> (.D :: (`(.B) :: .ARG))
ap (.A) ((.D :: (`(.B) :: .ARG))) -> .D
ev (.SELF) (.ARG) ((.A :: (.D :: .B))) -> .D

OUTPUT: .D

oMiser> ((.A .D .B) "x" "x") ("eq" "neq")
INPUT: (((.A :: (.D :: .B)) :: ("x" :: "x")) :: ("eq" :: "neq"))
ev (.SELF) (.ARG) (.A) -> .A
ev (.SELF) (.ARG) (.D) -> .D
ev (.SELF) (.ARG) (.B) -> .B
ap (.D) (.B) -> (.D :: (`(.B) :: .ARG))
ev (.SELF) (.ARG) ((.D :: .B)) -> (.D :: (`(.B) :: .ARG))
ap (.A) ((.D :: (`(.B) :: .ARG))) -> .D
ev (.SELF) (.ARG) ((.A :: (.D :: .B))) -> .D
ev (.SELF) (.ARG) ("x") -> "x"
ev (.SELF) (.ARG) ("x") -> "x"
ap ("x") ("x") -> ("x" :: "x")
ev (.SELF) (.ARG) (("x" :: "x")) -> ("x" :: "x")
ap (.D) (("x" :: "x")) -> (.D :: (`(("x" :: "x")) :: .ARG))
ev (.SELF) (.ARG) (((.A :: (.D :: .B)) :: ("x" :: "x"))) -> (.D :: (`(("x" :: "x")) :: .ARG))
ev (.SELF) (.ARG) ("eq") -> "eq"
ev (.SELF) (.ARG) ("neq") -> "neq"
ap ("eq") ("neq") -> ("eq" :: "neq")
ev (.SELF) (.ARG) (("eq" :: "neq")) -> ("eq" :: "neq")
ev ((.D :: (`(("x" :: "x")) :: .ARG))) (("eq" :: "neq")) (`(("x" :: "x"))) -> ("x" :: "x")
ev ((.D :: (`(("x" :: "x")) :: .ARG))) (("eq" :: "neq")) (.ARG) -> ("eq" :: "neq")
ev ((.D :: (`(("x" :: "x")) :: .ARG))) (("eq" :: "neq")) ((.D :: (`(("x" :: "x")) :: .ARG))) -> .B
ap ((.D :: (`(("x" :: "x")) :: .ARG))) (("eq" :: "neq")) -> .B
ev (.SELF) (.ARG) ((((.A :: (.D :: .B)) :: ("x" :: "x")) :: ("eq" :: "neq"))) -> .B

OUTPUT: .B

Here is one answer for this:

#7 (comment)
but discussion moved here.

The proposed addition of enclosures ((.A .D .B) ‵("x" ‵("y" "z")) ‵("x" ("y" "z"))) ("eq" "neq") does not solve the problem: result is still .B.

Construct like, again, when evaluated alone:

.A `(.A .D)

seems to handle all possible situations with .A and .B and .D.

But when it textually substitutes .D in the larger expression, .D stops to work.

oMiser> (.A `(.A .D)) `("x" "y")
INPUT: ((.A :: `((.A :: .D))) :: `(("x" :: "y")))
ev (.SELF) (.ARG) (.A) -> .A
ev (.SELF) (.ARG) (`((.A :: .D))) -> (.A :: .D)
ap (.A) ((.A :: .D)) -> .A
ev (.SELF) (.ARG) ((.A :: `((.A :: .D)))) -> .A
ev (.SELF) (.ARG) (`(("x" :: "y"))) -> ("x" :: "y")
ap (.A) (("x" :: "y")) -> "x"
ev (.SELF) (.ARG) (((.A :: `((.A :: .D))) :: `(("x" :: "y")))) -> "x"

OUTPUT: "x"

oMiser> (.B `(.A .D)) `("x" "y")
INPUT: ((.B :: `((.A :: .D))) :: `(("x" :: "y")))
ev (.SELF) (.ARG) (.B) -> .B
ev (.SELF) (.ARG) (`((.A :: .D))) -> (.A :: .D)
ap (.B) ((.A :: .D)) -> .D
ev (.SELF) (.ARG) ((.B :: `((.A :: .D)))) -> .D
ev (.SELF) (.ARG) (`(("x" :: "y"))) -> ("x" :: "y")
ap (.D) (("x" :: "y")) -> (.D :: (`(("x" :: "y")) :: .ARG))
ev (.SELF) (.ARG) (((.B :: `((.A :: .D))) :: `(("x" :: "y")))) -> (.D :: (`(("x" :: "y")) :: .ARG))

OUTPUT: (.D :: (`(("x" :: "y")) :: .ARG))

I am not sure if it's implementation or theory issue. Or maybe it's not the way miser supposed to perform evaluations, but how can I then apply applicative part (the .A .D. .B) to the data? And how to compose more complex applicative expressions?

So far my understanding was, that Miser evaluates a script (on the left) and applies to "data" on the right, but "data" can be script's "commands". What am I doing wrong?

I started those to figure out how can I evaluate combinators in Miser. That is, given S, K, I definitions, how to build something like (SK)(KS) and apply to the data / combinators. Can't find syntactical way for that.

What's the REPL/Ob input/output notation?

Here breaking down topics raised in #1 for separate threads.

@rnd0101: I want to see ... if I can make REPL from Coq representation.

The Miser REPL Idea

MAJOR UPDATE 2018-02-01 reflecting the latest thinking for the oFrugal REPL

MODEST UPDATE 2018-02-09 with adjustment to use of back-tick, not apostrophe

The basic idea for an oFrugal REPL is to have a written (i.e., text) form for reading obs as expressions, ob-exp. So the R-Read part is to accept the text, parse it, and provide any diagnostics in case the input is not well-formed, The E-Eval part consists of the evaluation of the parsed text, to arrive at the ob that the expression determines. The P-Print part is to then present that result in the same ob-exp text form used for input. This particular Read-Eval-Print-Loop notion stems back to the original implementation of LISP.

A common idea is to present the result in a form that, if itself read (via R-Read), the E-eval would produced the same result. There are other ways for the result to be retained, and the REPL may need command variations. That is, the REPL can accept statements, not just expressions for obs, and have more flexibility. That is all for oFrugal to handle, since, in the Miser project, it is oFrugal that provides a human interface for exercising oMiser operation.

Key Point 1 In the oFrugal formulation of a REPL, the ob-exp that is read is a formula for an ob. The Eval stage evaluates the ob-exp to compute the ob that is expressed. From this perspective, it is appropriate for the default P-Print to produce the result in the R-read notation that could be read back in to reconstruct the same ob without any applicative operations required.

Key Point 2 In the oFrugal notation, the :: and ‵ operators instruct the construction of the ob being read. In this notation, ( ... ) is for grouping, white space is for separation, and the symbols are all for individuals. By convention, primitive individuals all have names begun by "." and lindies all have names begun with a letter.

In the typography, the ‵-character has Unicode code point U+2035 (reversed prime). (Ed.Note: The Reader will allow ` (grave accent, the back-tick) for that, but output should always be the reverse-prime when Unicode is supported. The use of ` should not be used in code snippets because of conflicts raised if pasted into Markdown notation.

Key Point 3 there are "sugared" forms that the reader also accepts as expressions for obs. These can be chosen as more-expressive of an intended use of an ob for data or to include applicative-expressions to be used as part of the derivation of the resulting ob. The Eval process always produces a canonical ob, if it produces anything. So the output (Print) is always for a canonical ob.

The written text for oFrugal ob expressions is sketched in the file omiser/ob.txt. This file may also help in the explanation of the separation of obtheory from obaptheory, with the second an application atop the first, with supplemental additions in Ot, the theory language.

The ob-exp grammar and its interpretation are specified in the file ob-exp.txt. All future examples employ that notation.

WITH THE AVAILABILITY OF A PRECISE GRAMMAR AND EVALUATION, THIS TOPIC IS NOW CLOSED

Correct repo links from oMiser/ob-exp.txt to oFrugal/ob-exp.txt

The file has been moved. References in other repo files need to be fixed.

Learning to program

The following marvel implements "has" (taken from smlcheck). It would be interesting to know how to come up with my own scripts though. Like what are heuristics for composing scripts. Maybe, some useful intermediate "building blocks" need to be devised (like use of combinator here), but combining those into coherent program remains a mystery for me.

For simple example, given ob ^t = "a"::"b"::"c", I need a script, which retrieves a second member ("b") from the ob t.

Direct application is straightforward:

.A .B ^t

but it's encoding as a script could be challenging. With some trial-n-error I came up with:

(.A :: .B :: .ARG) (^t)

This approach to A and B seem to scale well to access n-th item:

(.A :: .B :: .B :: .B ::.ARG) (^t)

but I guess if I deal with a need to encode two-argument C and D and mix with A and B, some other way is needed.

There are some other interesting tricks:

oMiser> .B ((.ARG) ("x", "y", "z"))
INPUT: `("x")
OUTPUT: "x"

oMiser> .B ((`.ARG) ("x", "y", "z"))
INPUT: `("y")
OUTPUT: "y"

oMiser> .B ((``.ARG) ("x", "y", "z"))
INPUT: `("z")
OUTPUT: "z"

Confirm movement of miser-theory images/ and /readings from nfoCentrale

1. Create docs/images and docs/readings folders.
2. Bring essential images from miser/images.
3. Bring a reading page from miser/readings.
4. Confirm that the page is published as-is as .htm and, if not, as .html.
5. Confirm that the pages can continue to be edited and corrected on VXP2 and delivered to Astraendo's GitHub working folders from VSS on VXP2.

Typos in ob.txt

Another typo in obtheory (Q: shall I just put all typos into this issue?):

Lines 33,34:
* There are two selector functions, ob.a(z) and ob.b(z) that given
any ob and determine an ob as their result.

"given any ob determine an ob ...." -- the "and" does not belong there.

Originally posted by @band in #16 (comment)

Practical frugal shell issues and possible solutions

Ok, so now I have [...] list in the shell (except for zero-length and length-1 lists: I do not understand what they should correspond to because of lack of operations to understand what algebra is desired behind lists). (this builds on #10 (comment) )

oMiser> ["a", "b", "c"]
INPUT: ("a" :: ("b" :: "c"))

And I prepared namespace notion in shell, however, can't go ahead with that because I do not understand ob-encoding of the applicative expression and variable access (see my musing above on possible solutions). Plus there are grammar support problems with the f(x, y) syntax, which do not know yet how to resolve (left recursion).

To my mind ideal solution would be if shell input will be encoded into ob during parsing without any evaluations. Then that ob is evaluated given some namespace. This will enable recursion out of the box, because newly defined variable will be in the namespace at script execution time.

Of course, I foresee miser now has very limited support for recursion because some kind of pattern matching / if-clauses / destructors are needed for the recursion to stop. But it maybe beneficial if namespace access has some obap / frugal level support. This will keep the language self-serving.

To put in concrete terms, how to encode the following:

ob ^z = ^x :: (f (^y::"z"))

To quickly illustrate, I encoded new operations as lindies (LET for =, V for ^ and AP for juxtaposition/apply) and let "f" be just a kind of marker below:

("LET" ("V" "z") (("V" "x") :: ("AP" :: ("f" (("V" "y")::"z")))))

But then this needs some kind of super-eval to perform, and the difference of that super-eval from the normal obap eval is that it carries namespace with it and knows to do late binding of variables as it goes.
(namespace can be encoded like:

oMiser> [("z" "value"), ("x" "xvalue"), ("y" "yvalue")]
INPUT: (("z" :: "value") :: (("x" :: "xvalue") :: ("y" :: "yvalue")))

and even has nice property of using chained namespaces.

I suspect it is possible to do even now with oMiser, but given the S-combinator is that lengthy in oMIser, the interpretation of something like above would be possibly thousands of nodes... I was thinking of this kind of transformation:

ob_of_frugal_script(old_namespace, frugal_encoded_ob) -> updated_namespace :: ob_result

Any ideas?

PS. This Q&A suggests in the comments everything can be done with lambda and apply, so I wonder if oMiser still should have apply exposed similarly to pair and enclose, that is, to have primitive(s) to encode apply not just internal obap.ap?

Traps, Traces, Continuations, and Program Points

There are no exceptions in oMiser. Every oMisre ob has an applicative interpretation. That is, for obs p and e, obap.ap(p,e) and obap.eval(e) are admissible.

Trapping Undefined Interpretation in Traces

But not every ap(p, e) has defined behavior. This is not about failure to terminate but failure to have any means of going farther in the computation. This applies, for example, when p is a lindy. In this case, and some other similar ones, the applicative interpretation is a trace. Technically, the operation is trapped, and the result is a trace. It is the nature of traces that they are applicatively irreducible. They are trapped over and over.

This is a little like producing a null result (e.g., returning ob.NIL), except the trace provides evidence in terms of the trapped material. It is still necessary to check for those, of course, concerning the clues the trapped value provides as evidence of how an unintended result arose.

Obtaining a trace can also be intended, as a kind of symbolic confirmation of a script.

Excep;tions, Continuations and Program Points

There is no exception mechanism in the oMiser model of computation. And the prospect of traces is quite messy.

Technically, throwing an exception is not totally problematic. It just means there is no result instead of a trapped trace result. That continuation is elsewhere as if some other computation is now progressing requires more machinery, but it technically just means some case of a partial function are handled explicitly.

The additional machinery is that involved in establishing a continuation for a later exception.

Program Points for (Exception) Continuations

Peter Landin proposed Program Points as part of a general exception continuation mechanism. This depends on there being an environment that is part of the computation model. The idea is one can set a continuation at a place in evaluation for which there is an individual (the program-point) that when applied to an operand operation reverts to the point of continuation establishment and the continuation is applied to the program-point operand.

In order to handle faults, there must be a way to set program points as fault handlers for definite faults. That's to the degree that there are defined faults and an environment that handles this.

The other case is explicit application of a program point as a means of diverting to the continuation. That is like throwing an exxception as a purposive action during applicative processing. An example would be backtracking in some sort of search heuristic, as in a top-down parser.

The key to use of Program Points is that there is no continuation at the point of invocation, but only at the poiint of construction, something that need not be nearby with respect to the "flow" of operations.

The intriguing thing about Program Points at something close to the oMiser level is that functionality is preserved although some significant environmental support is required. The place where this becomes haiiry is with respect to stateful situations and whether or not they are (or even could be) "backed off."

That's why this is not a serious proposal for oMiser at this point.

Split oMiser and oFrugal grammars

The file ob-exp.txt combines two important cases that need to be separated for comprehension.

1. The canonical expression of obs is supported. The oFrugal output of such expressions will round-trip. That is, immediate re-input to oFrugal will yield essentially the same expression as output. That is, the same ob is determined.
2. There are additional capabilities that that are entirely resolved in oFrugal and it is useful to separate the accounts for that purpose. oFrugal provides all of the concrete syntax including lexical structure, handling of computer character sets, and progression of oFrugal-bound definitions to be used in subsequent oFrugal statements/commands.
3. There are also oMiser obs whose existence is on behalf of oFrugal and users thereof. That contextual situation needs to be reflected in a clear-cut manner.

This issue and its subtasks will account for achievement of all that.

Minimum number of primitives?

After a while, I revisited miser, trying to recall what I found so interesting about it. The main theme of my thought was however why oMiser defines so many rules? Can't the number be somehow made smaller?

And then I turned to the same question for Lisp, and found this summary: https://news.ycombinator.com/item?id=8714988

It is claimed there that Lisp has 10 primitives:

atom 
quote 
eq
car 
cdr 
cons 
cond 
lambda 
label 
apply

How many oMiser has? I see nine individuals and lindies. I can even roughly imagine correspondence like this:

atom -- ?
quote -- ob.e
eq -- inside ob.d?
car -- ob.a
cdr -- ob.b
cons -- ob.c
cond -- ob.d
lambda -- ?
label -- ?
apply -- ob.ap

Lisp has more primitives for definitions, so oMiser does not look verbose any more. The eq seems to be hidden inside the ob.d. This comparison looks very surprising: I doubt my analysis is correct. I still feel like both are too verbose (after all, it's possible to use just one combinator to produce any program so 2 primitives seems enough.).

The question is: Is there some redundancy in oMiser computational model? Can the number of primitives be less without sacrificing anything by syntax?

Define the look-up process for oFrugal binding resolution

There needs to be a function for

1. Inserting the bound ob for a binding name into a binding data structure (a list)

2. Checking to see if a binding name has a bound ob and returning that, returning a ?-prefixed lindy when there is no bound ob for that name.

The data structure is passed forward into subsequent oFrugal statements, so that all syntactically-valid oFrugal REPL always have a successful interpretation.

Seeking oMiser Accelerators

Immutability provides a variety of ways in which it is easier to reason about oMiser computational interpretations. Immutability also allows the underlying implementation of an oMiser to expedite matters so long as the results are indistinguishable from the literal semantics given for applicative operations.

One key factor in exploiting the opportunities of immutability is that the primitive operations be able to operate rapidly and simply. The script-interpretation "inner loop" is to be as simple as possible. The ‹ob› structure primitive notions are contrived with the idea of facilitating such economy of operation.

1. The Immutable List-Structure Assumption

It is presumed that the natural implementation of Obs is via linked-list structures. That is,

c = ob.c(a,b)

is manifest with a storage-structure cell, pointed to by &c, that contains two pointers, &a and &b. All of the primitive notions involve cells of this nature. When &c == &b, the cell represents a singleton. When &c == &a, the cell represents an individual, using == to signify the equality of pointers in the oMiser implementation.

e = ob.e(a)

operates similarly, except the b-position of the cell holds &e.

2. Distinction of Definite Individuals

It is desirable that individuals be distinguished and comparable. For two individuals x and y, it is required that

x = y ⇔ &x == &y

Here, &x == &y is comparable to the eq[x, y] in the formulation of LISP.

2.1 Differentiation of Primitives

The primitives, ob.NIL, ob.A, ..., ob.E, ..., obap.EV, ob.PROC, ob.DEF, etc., are each implemented by distinct, unique cells. oFrugal is able to determine those cells by some look-up mechanism that recognizes the various spellings of .nil, .a, ..., .e, ..., .ev, .proc, .def, etc.

For practical reasons, oFrugal uses a hash table to find links to the storage cells that represent these primitives. It is possible to locate the hash-table entry from the cell of the primitive for this and other purposes.

Implementation Note: It is desirable in what follows that these hashes be based on (case-adjusted) names and not anything about implementations, so that the hashes can be used across implementations for accelerator purposes, including interchange of serialized representations of obs..

2.2 Differentiation of Lindies

Similar arrangements are for creating distinct and unique cells for individual lindies. A different hash table is likely to be used since it will need to be expandable and accommodate variable-length names in some compact encoding. In this manner, each lindy will have a unique individual cell and it can refer to the hash entry where the string holding the printable name is also found. (Primitives could have the same features for simplicity in reporting canonical forms.)

Implementation Note: It may be appropriate to accommodate deletions when any garbage elimination algorithm determines that the lindy cell is no longer referenced from any in-use cells. It will depend on how chaining and hash-collision overflows are handled to know how to close up gaps following deletions. It is assumed that the same hash algorithm can be used as for primitives even if there are different tables. This leads into the structural equality case, below.

2.3 Handling of Binding-Names

Binding-names apply entirely in oFrugal and do not have any presence in oMiser.

Hash-table search for Binding-names is appropriate, although there is no need to adapt the same hash algorithm as the one applied to lindies and primitives, since these exist in oFrugal but not oMiser.

Implementation Consideration: Although binding names are handled at a level outside the oMiser engine, it exists at the boundary with an implementation. Because assigning a binding happens at an oFrugal level, cycling more slowly than ap and eval, this is a good point to consider acceleration and maybe some sort of JITting (4, below).

2.4 Handling of proc Individuals

To ensure that new individuals created from other obs are unique and distinct, it is valuable to use a hash-table search to find any existing proc of the same definition and employ the same oMiser cell for it. In this case, the proc is similar to an enclosure (in 3, below) insofar as hash differentiation is useful to determine when a just-derived proc is not already available.

Implementation Consideration: A proc may be short-lived and that suggests that the work to match up with an existing proc might be excessive. This needs to be considered in conjunction with acceleration procedures applied to pairs and enclosures. The clear identity case for individuals based on the cell location alone is very important when comparisons are made. The problem has to do with ephemeral procs versus ones that will be reused. The binding name case (2.3) might be useful.

3. Distinction of Pairs and Enclosures

When obs are not individuals, the semantics of equality depends on the correspondence of ob composition down to where a difference is encountered or there is a complete match. The presumption is that this is a time-consuming overhead. If there are measures to have matching structures have the same location, comparisons are accelerated.

Implementation Consideration: Effort to expedite structural comparison is justified only if there is a measurable benefit in practice. Instrumentation becomes important. It also becomes important to determine whether preservation of expedited matching be conveyed in serialized persistent forms for interchange and re-use in something more efficient than replaying an oFrugal script. For oMiser and oFrugal so far, we have not addressed distributed operation and sharing of obs (cf. Issue #31).

3.1 Pure Structural Comparison

Implementation of the obaptheory function d(x,y) can be expressed with simple functional pseudo-code.

let d(x, y)
    = if &x == &y
      then .A
      else if is-individual x or is-individual y
           then .B
           else if is-singleton x and is-singleton y
                then d(.a x, .a y)
                else if is-pair x and is-pair y
                     then if d(.b x, .b y) = .A
                          then d(.a x, .a y)
                          else .B
                     else .B ;

There is potential advantage to increasing the cases where &x == &y for non-individuals that are extensionally identical. It is also useful to increase determination when &x != &y yet there is extensional identity.

Implementation Anticipation: Arranging to re-use constructions is an automatic means of improving the incidence of equality in a pure structural comparison. Even if that is irrelevant with regard to comparisons, it is useful in terms of reduced storage footprint, since the same construction is referenced repeatedly. There are also patterns of construction that can be designed to increase this kind of economy.

3.2 Hash-Accelerated Structural Differentiation

Paul McJones pointed out to me that hash functions had been considered in acceleration of comparisons in implementations of LISP. In the case of oMiser implementation, we are already proposing hash-table lookups and we could provide hash codes in all cells.

For hashed constructions, if the hash codes are different, we know the obs are extensionally different. Assuming that every ob instance has a hash code derived from invariant structural features (i.e., the canonical form), we can use

let d(x, y)
    = if &x == &y
      then .A
      else if hash(x) != hash(y)  
           then .B
           else if is-singleton x
                then if is-singleton y
                     then d(.a x, .a y)
                     else .B
                else if is-singleton y
                     then .B
                     else if  .b x = .b y
                          then d(.a x, .a y)
                          else .B ;

where matching hashes might be collisions so it is necessary to go further.

3.3 Opportunistic Consolidation of Structural Matches

Another means of accelerating matches is by exploitation of immutability. References to cells in different locations that happen to be for extensionally-matching structures could have the references adjusted to be to the same cell. Immutability assures that the cases are indistinguishable. The preference is consolidation on the cell that is the older of the two. The idea is that the storage of the younger one is then more likely to be garbage-collected sooner rather than later. Also, it preserves the implicit precedence relationship, ¶.

Implementation Considerations: The situation of concern is only when hashes happen to be the same and we want, when they are found to be structurally identical, a subsequent check to arrive at &x == &y instead. It is unclear that there will be a repeated check very often and that garbage collection will turn out just fine regardless. Instrumented operation will be valuable. Note that, with the formulation of d(x,y) here, it is the d(.a x, .a y) and .b x, = .b y) that must intercede and make their arguments be the same cells on returning .A. For this, we can introduce da(x, y) and dab(x, y) so that we know which fields at &x and &y need to be checked and then made the same when ob-equality is determined. There may be further streamlining also.

4. Revisiting proc, Accelerating Applicative Operation

Every ob has an applicative interpretation. There is opportunity for acceleration in that respect. In particular, there can be code-behind techniques by which an accelerated application can be achieved. That is, every ob can have a direct short-cut implementation of its application to an operand. The default on construction would be to a simple employment of a direct applicative interpretation.

There are also opportunities to produce accelerated (native) implementations that bypass much of the recursive descent that is part of obap.ap reduction to yielding of a result. There are questions with respect to timing -- when and where should such optimization be inserted?

There are potential opportunities when an ob is being applied. There are also opportunities for hidden adjustments in the creation of a binding and perhaps in the use of certain already-provided objects, such as for ^rec and ^lambda.

There are two important limitations.

First, the rewriting that occurs as part of applications that deliver derived scripts must still happen, because the semantics, and especially extensional identity, must be preserved. On-the-fly creation of intermediate closures is a big reach. Approaching that level should be by stages that improve low-hanging fruit first.

Secondly, translation at what is essentially between two machine languages is very limited. The best case is being able to reverse engineer to an abstraction that can then be re-interpreted in the other machine language. Programming systems with definable types and functional abstraction provide essential hints for lower-level simulation.

Low-hanging fruit may be workable first, and addressing that may provide valuable insights for going farther -- or not.

There are other cases that are taken as variations of optimized compiling in oMiser terms. For example, in-lining can be used to eliminate applications.

[to be continued]

Resolving infix/applicative-operation Precedence

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.

Introduce the obapx.PROC/obapx.DEF Extension

[updated 2020-06-14T15:42Z to connect related issues.]
[updated 2020-05-25T25:43Z to clarify further and express commitment to having it.]
[updated 2020-05-21T22:20Z to clarify a bit more on the value of .proc.]
[updated 2020-01-15T15:43Z to add the ¶ condition and tidy up a bit.]

Although it is premature until the implementation and definitions are more-advanced, I have a few extensions in mind. This one is about scripts made into individuals.

proc Extension

There are two new primitives, obapx.PROC and obapx.DEF.

obapx.ap(obapx.PROC, p) determines an individual, standing for the script that p is. Designate that individual by proc(p). The computation model obapx has everything that obap does, along with identified obapx primitives and their computational interpretation.

proc(p) = proc(q) ⇔ p = q

q = proc(p) ⇒ q ¶ p

obapx.ap(proc(p), x) = ev(p, x, p) = obapx.ap(p, x).

obap.apx(obapx.DEF, q) yields p for which q = proc(p) and yields q otherwise.

From this, it is the case that when obapx.ap(obapx.DEF, q) ≠ q, q is a proc.

An ob that is not a proc is not equal to any proc.

Since ob p is essentially the unique identifier of proc(p), the canonical form for proc(p) is the expression obapx.PROC(cfp) which can be written .proc(cfp) for short with cfp the canonical form of p.

Why?

• proc(p) can be thought of as an encapsulation of the script, p.

• proc(p) is a distinct individual and all conditions on individuals apply to it. In particular, obapx.eval(proc(p)) = proc(p), preserving encapsulation of the script p.

• Although a proc script can be inspect by "reflection," since obapx.(obapx.DEF, proc(p)) = p, the intended confinement of proc semantics to the applicative interpretation, is signaled.

• Accordingly, lambda abstraction does not reach into the p of proc(p). proc(p) could be abstracted out of its occurrences in an ob taken as an applicative script though, just like any other (non-primitive) individual, as a form of refactoring.

• An accelerator (#26) can be used in implementation of a proc's application, so long as the result (and application of obapx.DEF) are indistinguishable. The sealing of a script in a proc also cues the applicative semantics and restricted semantics with regard to interior applications (e.g., in the Capsule Hack, #23).

Discussion

I did not originally consider having obapx.DEF, except there needed to be a canonical form, and oFrugal had to have a way to produce it. There is to be a serialized form of obs for retention in files and interchange, and that needs to be able to convey procs also.

Although I am not a fan of reflection in object-oriented programming systems, I see how it is compelled in the case of oMiser once any kind of procedural encapsulation is employed.

I had wondered about an alternative formulation, using

obap.ap(proc(p), x) = ev(proc(p), x, p)

as a way of having some sort of purity around the definition and use of procs. Unfortunately, this breaks the guarantee about equivalence to obap.ap(p, x) and then requires that p require

.def :: .self

to access its own code as data.

The reliance on extensional equality for the proc(p) perpetuates a very strong condition applied in oMiser. It seems appropriate that all obs be "comparable," even at this elementary level. Work on deduction will address how to take this further in appropriate contexts.

It may well be that the proc(x) approach is a solution looking for a problem to solve. I submit that the Capsule Hack (issue #23) is additional evidence that proc is invaluable in the creation of semblances akin to programming-language objects and their interfaces.

Combinator Representation and Interpretation-Preserving Procedures

In an important connection between computation theory and the oMiser computation model, the mathematical-logic combinatory functions, the combinators, are representable. Supporting combinators is characteristic of applicative- and functional-programming systems. There is a strong connection with λ-expression usage to be taken up later.

In the pure case, combinators are applicative entities that, viewed operationally, operate on combinators and yield combinators as results. With oMiser, there are only obs and functions on obs. Then how can obap.ap(p,x) and obap.eval(exp) be said to to achieve combinators when the arguments are always obs and all functions only yield obs?

The question is, "How do combinators arise, specifically, with oMiser?" And, "Of what importance is that for oMiser programming? What purchase does that give on aspects of practical software development?"

With oMiser, combinators are represented, not taken as given, primitive, or somehow directly present. An important aspect of the chosen representation of combinators is being interpretation preserving of suitable scripts to which combinators are applied. There is great utility beyond the "pure" case,

Combinator representation provides the first of many cases where higher-levels of abstraction are manifest by constructions using lower levels already at hand. With oMiser, this abstraction-raising depends on how structure ‹ob› is devised and exploited as a vehicle for stored-program computation via the chosen universal functions. This capability is representative of how the same is achieved with today's general-purpose computers and of how great utility is achieved thereby.

This question topic extends from the material in Question #2, employing notational variations introduced in Question #3.

Explain what has the expression of combinators be interpretation-preserving

That the combinators leave scripts intact and they are only applied as-is if applied at all. I what allows the emergence of simple types.

This needs to be explained in combinators.txt and it also leads to the interesting case of when scripts are acted on as data rather than used in their interpretation-preserving nature as applicative operations on obs and representations of other structures in Ob.

Transformation of scripts in other ways is a different matter and we need to bring that under scrutiny without breaking our heads on it.

typos in detailed grammar

Here list-form can't be standalone (eg [a] ). Summary grammar seems ok. Remove <obap-form> before <list-form> ?

miser/oMiser/ob-exp.txt

Line 111 in 0a57c7d

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

In other words, [x,y,z] or [] does not parse, while x[x,y,z] does. Just removing <obap-form> does not help, so summary grammar may be not ok after all... please, check.

(Adding obap_form to unary seems to work.)

Also -form-form in one place, in interpretation.

Adjust obaptheory to allow some singletons in traps

See #65 for what this is about.

The ob-exp a b c is now evaluated as a :: b :: c to provide a trap for there being no established applicative-interpretation for pure-lindy forms.

In an expanded form of the REPL output, such forms could be output in the applicative form as a simple variation on the pure CFob out;put case.

The adjustment to obaptheory will incorporate certain singleton cases (at least .NIL) in operand-position traps without changing the round-trip preservation of traps.

Change master branch name to main branch name

There are deep links to the main branch in text files in the code itself and these have been perpetuated in blog pages and other materials.

• First Confirm that main now works and that master redirects to main on GitHub (ideally, forever).
• Change Permalinks in skeleton .txt files to reflect presence in main, not in master. Have to walk the trees to accomplish this. ,
  . Notice when the change happens in the GitHub client for Windows
  . Do this first for miser, then tackle it for my other repositories where usage is expected to continue/resume at some point.

Split out CFob grammar from other round-tripping

The obstring.txt is perfect for mindelay output of obs in canonical form.

1. Change that to CFob.txt or CFstring.txt as considered most appropriate.

2. Make a version that is sugared to have pure-lindy constructions be like text. Maybe it is a CFtext. It still reduces to a CF and it outputs again as a CFtext. This is more likely for oFrugal.

3. The only problem is maybe this creates a conflict with more-extensive versions of Frugal.

This is discussed at #65

"enclosures" and "encapsulations"

obtheory.txt has a definition for what are called enclosures. In ob.txt lines 43 ff. describe what is called an "encapsulation". The function ob.e in obtheory.txt looks to me just like the function ob.e in ob.txt. Why is it not called an "enclosure"?

I think I am confused about what an "enclosure" is. I see what the functions ob.a and ob.b do when the argument is an enclosure, or I think I do. Is this just a matter of definition in obtheory.txt and use in ob.txt?

Convert Appropriate Issues to Discussions

Now that Discussions (beta) are available, identify every issue that is better identified as a Discussion with label "discussion" and then bulk convert those to the Discussions topic.

<!--
From the Discussion greeting text (illustrating the value of XML/HTML comments in Markdown:

🔗 If you use issue templates, link any relevant issue templates such as questions and community conversations to Discussions. Declutter your issues by driving community content to where they belong in Discussions. If you need help, here's a link to the documentation.

➡️ You can convert issues to discussions either individually or bulk by labels. Looking at you, issues labeled “question” or “discussion”.
-->

What is apint of arbitrary individual ob?

Can't find any formal definition for the case when ob is missing apint in the theories, so for example my REPL implementation breaks on the following input:

ob.c(ob.c(Ob('x'), Lindy('ImLindy')), ob.e(Ob('NIL')))

That is Ob('x') does not have an interpretation.

Is the program above incorrect, or should all extra obs come with apint? Or have I overlooked something in the theories? (there is that trace-related comment I have not understood in terms of interpreter pragmatics.)

(for now I've added ValueError: Ob individual Ob('x') can't be interpreted. to provide better error message)

Thanks!

PS. In SML implementation, it seems there are no other individuals at all. Is this right?

Persistent Namings: Libraries and Distributed Access

This is a place-holder for some important Computer Science topics that cannot be addressed with oMiser and oFrugal, yet are relevant in how higher-level activities are situated. There is no indication of how one might bridge to these in a fashion that preserves some level of purity and ability to reason about functional bits and the confinement of external dependencies/interactions.

The Naming Conundrum

There is no naming system in the oMiser model of computation. This has been intentional. The lindies are symbolic individuals having utility without any individually-distinct applicative interpretations. Lindies are merely constants. There is some limited intrinsic value using lindy traces as part of verifying an applicative procedure. The intended interpretations for chosen liindies are external, however they are selected for affordance-evocative purposes.

The handling of binding names is an ephemeral arrangement within an oFrugal console session. The binding names are established within a session and there is no carryover to any other session. The oFrugal processor always starts up without any defined binding names. Binding names are not even persistent within a session, since the name can always be reused for a new binding as oFrugal processing of an input stream progresses.

Having persistent storage of obs in libraries of some form requires agreement on how such obs are named. If (also-persistent) scripts may refer to other library-carried/-bound obs, there are new issues around referential integrity and versioning of obs with respect to extensional identity and its preservation. We also don't want to collapse what an ob is versus where it is retained/accessed.

Th notion of persistently stored obs is distinct from the oFrugal ability to merge stored oFrugal scripts into an oFrugal session stream. Even that introduces some naming and access considerations; it is interesting to consider how those might be inter-related in terms of reliable identification. For the most part, this occurs independent of oMiser, with changes to included scripts simply being of utilitarian value in oFrugal operation. With introduction of imperative behaviors and stateful considerations at the Miser level, interplay of considerations may arise with regard to management of dependencies.

When there are means for access to obs located elsewhere, there are important matters with regard to uniqueness of location and determination of the ob itself. It is conceivable that caching of distant obs will be desirable and determination of versioning is especially important there with regard to the integrity of dependence and consistency with respect to any nearby cache.

These are matters of greater significance than the rudimentary oMiser model. It is not expected that they be resolved with either oMiser or oFrugal. Instead, it is desired that any early introductions around namings and persistent identity be established in a manner that does not foreclose extension to higher-level cases hinted at in this issue.

The provision of operations at the Miser level that make programmatic presence of access to and establishment of persistent obs is definitely related to the treatment of computations (#30) and how assignment, continuations, and streaming are dealt with. There is also interaction with accelerators (#29) and the policy there is that accelerators are inherently local, maybe cached, but not conveyed with persistent forms of obs. Distributed presence/situation is a complication that requires more thought before distributed operation on an overall procedure is entertained.

Clearly, these considerations are not anything that oMiser should solve for us. Addressing them with respect to a purely-functional foundation is perhaps useful for insights on the matter, especially on how one can preserve (or better achieve) consistency and the ability to reason about the elaborate schemes of representation and encoding that can be appealed to.

Thoughts about Name Forms

The reliance on extensional identity in oMiser is a powerful feature as well as a serious limitation. It is desirable to appraise the prospect of accelerators for structural equality (#26) as both opportunity and necessity with regard to the enhancement of performance without loss of dependability. Here the question is whether something equivalent can be achieved with regard to persistent obs in (potentially) mutable storage.

It appears that we need to distinguish

1. what something (an ob) is

2. where it is/was found

3. what it is offered for

This last may have to do with some sort of logical attestation that constitutes demonstration of some representation. It might involve investigation of types relative to representations; that may have bearing on the semblance idea (#23, #20).

Attempting to account for all of this at or near the oMiser level is not necessarily practical. It may be worth it to the degree that there is some insight considering computational interpretation, representations/encodings, and higher-level notions, such as (simple) types. I am hopeful, but not that confident.

[to be continued]

Questions

The project interested me since circa 2001 ( https://mail.python.org/pipermail/python-list/2001-July/116910.html ) and I am glad it is continued. Now I'm being a bit more versed in type theory, so would be interesting to know the purpose and specialization of the project.

My understanding always was it's a way to embed algorithms in documents, but in the current form it's very low-level for that to be practical.

If it's a new model of computation, better lambda calculus or better LISP-machine, then what are highlights? For example, what is it's place on the lambda cube, any example on introducing types? How to attach semantics, and which kind of semantics better suits here?

Nowadays it's fashionable to prove properties of the new languages, for example, with systems like Coq, and current description (and current theory files are almost ready for that, though, more "constructivistic" formulation of some axioms/theorems would not hurt).

In other words, why people can be interested in this yet another representation of algorithms? I guess, it may be answered somewhere, but I have not found. (yes, I've seen Golden Geek in facebook)

Happy New Year 2018!

Confirm the restatement of obaptheory.txt

As of obaptheory.txt 0.0.32, the simplification and removal of the apint helper, there needs to be reconfirmation. In particular, we want to ensure the treatment of lindy traps is still correct.

• Review the obap test scripts and capture the expected results

• obap.obcheck.sml

• obapcheck.sml

• combdemo.sml

• Ydemo.sml

• revise obap.sml to correspond to the obaptheory.txt treatment

• reverify the test scripts to ensure expected results.

• obap.obcheck.sml

• obapcheck.sml

• combdemo.sml

• Ydemo.sml

• upgrade obaptheory.txt to 0.1.0 after any necessary fixes.

Need for On Ramp and Guard Rails

Although Miser Project focus has been on proof-of-concept demonstrations via mockups and supporting text files, I also want to provide a transparent way for the work to be replicated, tested, and also contributed to.

Currently, it requires substantial tacit knowledge to accomplish that.

I desire having supporting materials where anyone with sufficient interest could at least obtain the project, use the materials, and confirm the arrangements and also replicate the various test results.

For the use of SML/NJ mock-ups of oMiser and oFrugal, I started to provide such information here and I would much rather provide it in a separate location where it can be maintained once and also referenced from projects where it matters.

I do want the work to be on GitHub. I believe that the nfoTools project, https://github.com/orcmid/nfoTools, is the appropriate place.

I need to spend some time there to provide appropriate support for my SML/NJ usage in a kind of commons.

I don't want to devolve into an axe-sharpening death-spiral. I'll settle for adequate scaffolding that will hold the place for more detail and which can be applied in the Miser Project without need for serious reworking down the road. There is considerable faith that no speedbump will be catastrophic.

typo in obtheory

In Section 1. Logical Notation

I think "p ⇔ q read p if-and-only-if q, true when true both are true or"
should be
p ⇔ q read p if-and-only-if q, true when both are true or"

("true when true both" has an extra "true" ?)

Implement λ.x (lambda.x) and ρ.f (rho.f for rec.f)

One of the key features to be established for oMiser is the availability of heuristics by which ρλ-abstraction is performed on Obs taken to be scripts.

The basic approach is based on how that is accomplished with expressions involving combinators. The technique is fashioned after that in [Rosenbloom1950: pp.116-118].

oMiser scripts are not expressions in ‹ca› and there needs to be accommodation, in particular, of the occurrences of .C, .D, and .EV in particular, along with other primitives having operator significance, including enclosures.

It may be the case that operation of the mechanized procedures may depend on adherence to certain amenable forms of scripts. In that case, failure modes may need to be addressed as well.

1. The Basic Idea

Fundamentally, λ.x(e) in terms of combinators follows the following pattern when there are no special forms. In ‹ca›, we have

    λ.x(e) = |Ke for e a term different from x
            = I when e = x
   λ.x(|pq) = ||S(λ.x(p))(λ.x(q))

In the absence of special forms (Obap6: speccialop or evref), there are direct counterparts in the ‹ob› computation model.

        λ.x(e) = ^cK(e) = ` e, when e is a term not x
               = ^cI = ob.NIL, when e = x
   λ.x(p :: q) = ^cS(λ.x(p))(λ.x(q))

There is often an opportunity for in-lining, leading to the simplification

        λ.x(e) = ` e, when e is a term not x
               = .ARG , when e = x
   λ.x(p :: q) = λ.x(p) :: λ.x(q)

when minding our p's and q's.

2. Engineering Considerations

Essentially, if x is not free in λ.x(e), we want λ.x(e) = _e_ or just _e_ when eval(_e_) = eval( e), e being literal in some sense.

When x occurs in λ.x(e), we want those occurrences replaced by .ARG in a script such that ap( λ.x(e), v) yields the same as eval(e) with `( v) everywhere that x was.

The λ.x(e) computation operates by recursive descent into the components of e. On the ascend back to assembly of the final script, steps are taken to minimize reconstruction. The more parts of e that can be retained as either literals or enclosures in λ.x(e) the better, including reaching the `(e) or literal e case.

[to be continued]

[Rosenbloom1950]

Rosenbloom, Paul. The Elements of Mathematical Logic. Dover Publications (New York: 1950). 2005 edition ISBN 0-486-44617-4 pbk.

Seeking Lexical and Precedence Parsing

Although it is easy to fashion an top-down (recursive-descent) parser, and that is relatively common these days, the proposal for oFrugal, at least, is with a finite-state lexical parser underneath a precedence language parsing. This takes advantage of the straight-forward semantics that is expressed by oMiser applicative operations. The parser proceeds rapidly through an input text, completing the parsing and evaluations in a linear progression. The idea is to expedite oFrugal input with high-speed parsing not counting the costs of explicit apply operations, which ideally are delayed until the correctness of the input is established.

APPROACH

1. Rapid lexical parsing scans included data streams as well as console inputs. There are no parser back-up requirements at this level. The lexical rules should be clean and accommodate full Unicode input and output. (The XML-formed load scheme for saved objects is different, since the XML parsing is entirely different and semantically easier.)

2. Lexical tokens should be simple and eventually contain location information for tying error messages back to locations in the input stream. While most errors might be fatal at this level, there may become a time where there is more delay at the precedence-language operation to provide more-informative failure information in one shot. The lexer also recognizes ligatures (e.g., "::", ":]", and condenses and sometimes removes white-space (e.g., before and after brackets, separators, and operators including (* *) comments and the line continuing "\ ... ". There is a problem about infix "." versus prefix "." and that should be resolved in the lexer if possible. (The feature/method suffixing case is related to the Capsule Hack, #23.)

3. Rapid precedence-language parsing. This effectively turns a stream of infix- and bracketed material into a reverse-polish-stream form of applicative expression. There are checks that reject certain cases of non-grammatical occurrences, mainly where operands are missing as in "()", mismatches like "[ ... )" and also "," where there is a missing component on one side or the other. We can continue parsing by inserting .NIL in places, but the parsing will ultimately be rejected.

4. The precedence-language parsing will not proceed at any point where the operand and operation stacks cannot remain properly synchronized. Bracket mismatches tend to be deal-breakers as do unresolvable binding names. In failure cases, it is useful to know where problematic elements appear in the input stream so that error messages can localize relatively well. This is a handy feature of precedence-language parsers along with their considerable speed of operation. Error message output should be such that operating in an IDE can tie the messages to the identified places in the input stream.

5. Initially, the semantical apply operations resolved in (3) will occur as parsing happens. This can lead to semantic failures (e.g., non-terminating/exploding computations) in the midst of parsing. Production-level parser will defer evaluation of the reverse-polish stream until the parser completes the entire input and there are no grammatical errors. In this context, an unresolvable binding-name is still sudden death. The intermediate form can also be useful in analysis and transformations, going beyond the oFrugal level.

6. There was a concern for reserved words at the level of oFrugal commands (#24 item 3). This is finessed using "!" prefixes.

The case of (5) is a flavor of mindelayscandoer, a term introduced b Alan Perlis. That is, once the operands of an operation are all in hand, the operation is performed. In a one-pass compiler, instead of performing the operation, code can be emitted. And, either way, it is easy to delay the operations by constructing a reverse-polish stream of the operations that are needed, either emitting code or (as in oFrugal) carrying the operations out once it is determined that there are no errors in the input.

Implementation Note: The production of a reverse-Polish expression of a canonical Ob can be similar, going from recursive descent to emitted reverse-Polish for faster subsequent reloading. This can also be used to retain sharing of elements by providing backward references to elements that occur earlier in the stream. It is not clear how complex this can become and how complexity explosion can be avoided.

Editing Miser Project: Interpretation, Representation, Computation, and Manifestation

The 2019-02-11 First Public Draft of https://orcmid.wordpress.com/2019/02/11/miser-project-interpretation-representation-computation-and-manifestation/ needs some cleanups. This issue accumulates required edits.

• There are two section 4s. Renumber after the first section 4

• There needs to be more space between the Section 1 list on Interpretation and the list on Representation.

• Make the images link to the ones used

• Catalog the images in the models section, perhaps moving to an [H]IPO section.

• In the models section of the repo, distinguish Bratman (and the successor paper), the Hopper diagram with control, and the HIPO and Dataflow Diagram methodologies.

• In the section on Manifestation, add "try not to think of 'W' " in the discussion of the maximum magnification. (Other candidates are Y and X.)

• More diagrams are needed, especially for Representation. Also, the representation of functions is different because we don't have distinguished individuals in the _S_f.

• Add Notes and References and maybe items from Notebook #75.88 page.

• Link to the obaptheory.txt file in the mention around what the stored-program principle is.

• Apply simplifications of wording contributed in William Anderson's mind map at https://github.com/band/csTheoryAndPraxis

• Find clarification to the characterization of computation as conceptually "orchestrated performance of representations" in Anderson's mind map that nags at me.

long-Form Issues Not Printing Reliably

Printing long-form issues to desk-check the texts and for reference in comments is not reliable in the Microsoft Edge browser Version 83.0.478.45 (Official build) (64-bit). The problem is at page breaks where text is lost from the top of the subsequent page.

The workaround is to use Google Chrome Version 83.4103.61 (Official build) (64-bit) and maybe later.

I need a better way of doing this, perhaps using MarkDown pages in the repository, or possibly Gist pages. There is also the Wiki to consider.

Move lindies to obtheory from obaptheory

They are still uninterpreted but they are a way to exhibit more data structuring.

I am a little ambivalent about this, although it makes sense for having a way to encode things.

How to cite?

This is probably a question, which can be answered somewhere in readme and closed:

what is the preferred way to cite Miser-project? (or maybe even different parts of it)

(Not that I personally need it immediately, but who knows when it will be needed)

Thanks for you great efforts!

Make Stateful Constructions: The Capsule Hack

2020-06-17 Note Improve characterization of Constructor and Factory Capsule Hack Representations
I2020-06-14 Note: More about Semblance.
2020-06-06 Note: This issue on incorporation of state into computational interpretations has become an extended treatment. It is still offered as an issue, although it may also be the basis for documentation of the approach raised.

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.

1. 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›.)

2. 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.

3. 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.

4. 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

let instance = .proc (.ev :: ``pRep :: ` obState) ;

and the oFrugal (ob-exp) hand-compiled script implementing that construction is along the lines of

^pInstance = .C :: ` .PROC
                :: .C :: `.EV 
                      ::  .C :: ` ``^pRep 
                             :: `  `^obState ;

where

• pRep is a script that provides operations on .def(pInstance) in a manner that sustains the capsule's computational semblance as a member of an abstract class (cf. #22).
• obSstate is the ob representation of some abstract class domain entity relative to the operations and restraints of the applicative script pRep.
• binding names such as ^obState are 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

ap(pInstance, feature)  = ev(.EV :: ``pRep :: `obState, feature, pRep)

such that in ap-internal evaluation of the pRep script,

 .SELF = .EV :: ``pRep :: `obState
 .A  :: .A :: .A :: .B :: .SELF = pRep
 .A :: .B :: .B :: .SELF = obState
 .ARG = feature

and a new capsule that differs only by introduction of obNext for obState is produced by script

.PROC :: .C :: `.EV 
            :: .C :: (.A :: .B :: .SELF) 
                  ::  ` ` ^obNext

The oMiser convention for producing traces for operations that cannot go further is sustained here by evaluating script

.C :: (.PROC :: .SELF) 
   :: .E :: .ARG 

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,

case = (v1 :: c1) :: (v2 :: c2) :: ... :: (vn :: cn) :: ` default
     = [v1 :: c1, v2 :: c2, ... , vn :: cn, ` default :]

with default the case that is determined when feature does not match any of the c_i.

The selection of cases for values of feature is obtained in functional pseudo-code by

let find(feature, cases)
    = if is-singleton(cases)
      then cases
      else if feature = .b .a cases
           then .a cases
           else find(feature, .b cases);

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 c_i be scripts representing predicates, so the

   else if feature = .b .a cases  

portion becomes

   else if (.b .a cases) feature

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.

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 )  ;

(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

let selector(cases)
    = λ.feature ( finder(feature) (cases) ) ;

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

pRep = .ev :: .a :: ` selector(cases) :: .arg

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

pRep = .ev :: .a :: selector(cases).

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

^pRep = .C :: ` .EV
           :: .C :: ` .A
                 :: ^pSelector(^obCases)

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),

 .SELF = .EV :: ``pRep :: `obState
 .A  :: .A :: .A :: .B :: .SELF = pRep
 .A :: .B :: .B :: .SELF = obState
 .ARG = feature

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

` (.C :: ( (.PROC :: .SELF)
       :: .E :: .ARG )

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

CHTinstance = CHTTconstructor(obSetup) 
              where CHTconstructor =  CHFactory(pRep)(pCastOb)

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

• pCastOb(obSetup) yields ob.e(obSetup) if obSetup is invalid for the semblance implementation
• pCastOb(obSetup) yields an obState canonical form, if any, for the represented domain entity if relevant
• pCastOb(obSetup) simply yields obSetup when it is admissible as obState and alteration is unnecessary

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,

` ( .C :: (.PROC :: .SELF)
     :: .E :: .ARG )

and the remaining question is what else to provide. A simple approach would be to employ

obState = (^pCHTConstructor) :: ` obSetup

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.

Explain how the carrying of state is accomplished thanks to enclosures, cK, and obap.self

oFrugal grammar?

There are several examples of what is called frugalese, but is there any grammar or formal description for that?

Negations in axioms

Negative formulations of some axioms place cognitive burden on the reader, plus make implicit assumptions on the "universal set" implied. I guess, the intention is to safeguard the machinery by making some obs non-equal, but maybe explicit is better than implicit, even at the cost of adding more is-functions?

Move ob-exp.txt from oMiser to oFrugal.

1. ob-exp.txt is moved to oFrugal.

2. A tombstone is left at oMiser

3. Links in other materials are updated to refer to the oFrugal instance.

Imperative/Interactive Behavior and "Compute Expressions"

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.

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 (#22) and devices such as 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]

Move the introduction of Lindies to obtheory.txt

The applicative interpretations around Lindies in obaptheory Obap2 (b-e) remains there. But the definition of Lindies in Obap2 needs to be moved. Lindies should come into obtheory.txt at Ob8 and everything else moves down.

Bring the Ground Truth and Narrative to docs/

The organization is going to be web-centric, but the text-only materials will be preserved as underlying material in the same place as web pages that feature the same subjects.

Replicate orcmid/readings and miser/readings in orcmid.github.io/bib for consolidation of bibliographic material

This will complicate citations from Miser Project, so it is important to find and repair any references to the bib entries here. The idea is they can be found at orcmid.github.io/bib/ and it will all work by relative references, ideally.

Need intensional printing

One of the limitations of oFrugal is that the canonical form ob-exp is not as useful for representing anything else, in contrast with the way LISP S-Expressions are usable for practical disguises.

Until there is some rational handling of types and symbolic expression of type forms, and also printable strings for them, there are limited disguise forms.

Part of oMiser and oFrugal being the way they are is because I did not favor the disguising that is so common with LISP, especially when it comes to messing with the REPL reader. So oMiser is closer to the M-expression of LISP semantics and I am happy about that. The goal is to expose oMiser as realization of the ‹ob› model of computation in this consistent manner.

It is also desirable to express representations in a manner that manifests the entity being interpreted in ‹ob›. There are ways to accomplish that early, with a little help from oFrugal.

Default Bare Output

In the oFrugal REPL, the standard output for a bare ob-exp is a pretty-printed canonical form. The pretty printing uses the occurrence of obap primitives as clues to off-side layout that aligns certain operators and their operands. For example,

 .C :: `.C
    :: .C :: (.E :: .C :: (.E :: .ARG)
                       :: `.ARG)
          :: `(.C :: (.E :: .ARG)
                  :: `.ARG),

the value of ^cS, a representation of combinator S established in combinators.txt.

The use of indentation white-space in this manner is irrelevant to the semantics. The key provision is that if the output expression were submitted back to the oFrugal REPL, the output would be an expression for the same ob. That is, canonical forms expressed in ob-exp have that ob expressed by canonical form in the output once again. It is an elaborate expression for a constant ob.

Intensional Formatting

The bare oFrugal output does reflect some intensional presumptions based on appearance of primitives in the structure of an ob. Occurrence of primitives is taken as signalling likely intended use as a script. The pretty-printed forms set off indented parts such that the expression of operands for primitive-associated operations are easily identified.

What is also sought here is a kind of decompiling (or disassembly) into an ob-exp that gives rise to the same ob via applicative expression.

There is a simple case involving lindies. The evaluation of script A :: B :: C is the same as that of ob-exp A B C. And of [A, B, C:] for that matter. All three of these forms of ob-exp lead to result A :: B :: C, and one could choose to prefer the applicative or list expression based on knowledge of the intended situation.

For oMiser, it falls to oFrugal for satisfyiing such expectations. This would apply to the complete result of an ob-exp in the simplest case. More complex situations require extensions beyone oMiser.

Lindy Disguises

The rules for Lindies provide a means for expression of representations. An oFrugal command can be used to render a pure-lindy trace such as (x ;; z) :: y :: z in the form such as (x z) y z that has the same ob-exp semantics.

In this case, oFrugal commands

!apexp (x :: y) :: y :: z;
!apexp (x y) y z;;

are proposed to both produce output text (x y) y z.

This allows certain kinds of canonical forms to be more-readable disguises for a representation.

The idea is to present a stream-lined ob-exp the eval of which would yield the same canonical form ob given as the operand of the command. Essentially, x :: y is replaced by some form of .C (x, y) with some crafty in-lining depending on the nature of the operands.

Unfortunately, !apexp defined on every ob, is not so helpful. For example,

!apexp  .C :: `.C
           :: .C :: (.E :: .C :: (.E :: .ARG)
                              :: `.ARG)
                 :: `(.C :: (.E :: .ARG)
                         :: `.ARG);

is difficult to consider if the goal is an applicative expression with eval result being the same ob as that provided as the operand. Inference of a list form is helpful but not so useful.

[  .C, '.C, .C,  .E :: C :: (.E :: ARG) :: ` .ARG, ' [.C,  .E :: .ARG, ' .ARG :] :]

and then, being obsessive about it,

[  .C, '.C, .C, [ .E, .C, .E :: ARG , ` .ARG:], ' [.C,  .E :: .ARG, ' .ARG :] :]

Re-Abstraction

It would be even more useful to be able to re-abstract (what would be a better term?) an ob. It is possible to make functions that expose the applicative structure better. A sort of re-lambda procedure, such that

!def ob ^dcS =^dλ.z ^dλ.y ^dλ.x  ^cS;

(reading dλ as de-lambda) would result in

^dcS =( x :: z) :: y :: z

with

!apexp ^dcS;

yielding (x z) y z.

Note the reversal with respect to ^λ.x ^λ.y ^λ.z (x z) y z.

This case features two problems. First, choosing names (here represented by lindies) for the "bound" variables in the re-abstraction. oMiser has nothing comparable to a source-code that is retained somehow by the ^λ (and ^ρ) procedures. Secondly, binding names are ephemeral and the bindings are mutable. There are no reserved binding names and there is no means for naming obs that can be used for persistent collections (libriaries) of them (issue #31).

Without higher-level machinery and treatment of shared definitions, precise re-abstraction is unobtainable.

oFrugal Syntax Updates Needed

Several matters need to be addressed in the Frugalese grammer, including ob-exp.txt.

1. The lexical structure needs to be completed.
2. The progressive handling of declarations, shadowing, and by-value needs to be reflected above the 〈ob-exp〉 category. The semantics of the progression through a sequence of inputs will be expressed in terms of insertions in a key-value list and lookups of 〈binding-name〉 entries. This will cause an additional parameter on almost all productions so that resolution of 〈binding-name〉 terms is specified.
3. There needs to be agreement on the declaration form.

ob 〈binding-name〉 = 〈ob-exp〉

requires back-tracking or creation of a reserved word. Whatever form is settled on, those two considerations must be addressed.
4. There may be a bug in the semantics for I〈obap-form〉.
5. There needs to be a "." operator that allows chaining, and fits with introduction of the Capsule Hack (#22). This would have "methods" group properly. In general, the productions

〈function-form〉 ::= 〈function-form〉 . 〈term〉
〈obap-form〉 ::= 〈obap-form〉 . 〈term〉

are such that the expression ^lambda.x(mumble) is sugar for (^lambda x)(mumble) while right-associativity is preserved with

^lambda.x ^lamda.y ^lambda.z '( (x :: z) :: (y :: z) )

Computational complexity

Models of computation usually go hand-in-hand with computational complexity "payloads". This is probably more into engineering side than pure platonic point of view, but it already became common practice to provide cost of computation for models.

I believe complexity of the implementation is only partially depending on the "engineering" aspects, while another part is complexity of the theory itself, inherent complexity. This statement is justified by notion that both theory and implementation are systems. And domain of complexity notion's application are systems (in almost any definition).

(disclaimer: I am trying to enter my favorite philosophical area, which is Complexity.)

Offtopic (?). While speaking of systems, I recalled the best formalism about complex system made by soviet/ukrainian late philosopher Avenir Uyemov (actually, he had a whole philosophical school in the days of USSR). Unfortunately, he wrote very little in English, but I've found one of his works by googling. His ternary language due to it's utter genericity covers any systems nicely. So far, I have not found any better coverage in Western philosophy (please, point me if you know). (this is "Plato") And then there is "engineering" / design "Nerd" approach to systems, which experienced quite a hype in Western countries recently, while in it's origin it seems to be being forgotten: TRIZ (it's being blamed to not being scientific (eg, due to some metaphors, which remind physical phenomena, but are not), but I argue - it should not be! It's about systematic and rational approach design and engineering versus Trial-n-Error.)

What are Individuals and Lindies all about?

This Question is Closed

After experimental confirmations carried out with Roman Susi (@rnd0101), the treatment of Individuals and Lindies has stabilized.

• The file ob.txt now provides a sketch and definition of written notations.
• There is discussion, below, that will be consulted in the preparation of stable documentation.
  • First, About Notation
  • Second: About Applicative Interpretation with tables that describe the application rules, as formally codified in obaptheory.txt.
  • Third: About Traces and Lindies discussion how traces result in applicative interpretations and how that can be exploited in symbolic execution and tests that confirm operation of obs used as oMiser scripts.
• Related still-open questions are Question #8, oFrugal Grammar, and Question #12, Learning to Program.
• The exploration of the power (and limitation) of the oMiser system will develop under Question #7, Combinator Representation and Interpretation-Preserving Procedures. This is a forerunner of topics on representation of data structures by encapsulation.

---

In obtheory.txt, all obs, x, such that ob.a(x) = ob.b(x) = x are classed as individuals. ob.NIL is established as such an ob, and it is indicated that there can be any number of additional distinct ones. At the theory, these are distinguished by difference in the lexical forms of the names given to them.

In obaptheory.txt, as part of introducing universal functions obap.ap(p,x) and obap.ev(exp), a number of additional individuals are introduced. I.e., individuals such as obap.A, obap.C, obap.SELF, and obap.EV are identified as distinct primitives along with ob.NIL. In the reference notation for expression of obs in plaintext, these are designated as .A, .C, .SELF, .EV, and .NIL, respectively.

Also, in obaptheory.txt, we learn that there are lindies (short for literal individuals) that are distinct from primitives and symbolized in the theory by notation Ʃs where s is a distinct alphanumeric spelling taken as the identifier of the lindy. In the reference notation, that lindy is simply written s.

Then, in the formulation of the universal function obap.ap in the theory language, Ot, there are some elaborate predicates concerning lindies.