Combinator Representation and Interpretation-Preserving Procedures

[orcmid]

Combinator Representation and Interpretation-Preserving Procedures

[rnd0101]

Just a check on understanding. Represented here means can be implemented , that is, computations can be done with them? Also, it means, that combinators are not first-class in miser but composed of some number of building blocks.

I do not like macros (Python lacks them for good), but one powerful feature seems to be missing from miser, and I guess it's not even in the frugal-1: named reusable entities.

For example, even with assembler language I can call routines by some names to reuse or I can put makefiles to different files and call by name. This is very powerful organizational technique, which is outside of scope for miser (this is fine), but does it mean it's up to implementation and computation environment or are there some blueprints that way? For example, obs "global" identity can become and issue I see.

I believe in technical systems evolving in a more or less predictable way (ref to TRIZ here again), and in computing especially sub/supersystems are usually very fast to appear. So I tend to think on 2-3 supersystems' layers habitually (sometimes hard to stay inside a box).

But the question was very practical: if I want to play with combinators in my playground, is there any standard way to call and reuse them at frugal-1 level or should I just invent something to go forward?

[orcmid]

@rnd0101 Just a check on understanding. Represented here means can be implemented , that is, computations can be done with them?
Representation is a bit broader than that. In this context there is a weird relationship between representation and interpretation. My technical usage is that the act of representation is arriving at an expression that achieves a particular interpretation in some context. This is broader than the technical use of applicative interpretation with respect to oMiser, as in Question #2.

For the inquiry into combinator representation, the idea is finding obs having computational interpretations that satisfy essential characteristics of combinators.

The diagram expresses the pattern I am offering for representation/interpretation. We will see how a chosen interpretation as combinators fits into that picture. There is more discussion of this under the topic "Computation as Performance" on the Facebook-page sketch I've been working on.

@rnd0101 Also, it means, that combinators are not first-class in miser but composed of some number of building blocks.

That's correct. Combinators are not first-class in oMiser. The only first-class entities in oMiser are obs.

My hypothesis is that taking/providing combinators as first-class is a mistake. My concern, as a theoretical matter, is that the Church-Rosser condition is a negative result. How that matters, and where it impacts oMiser, remains to be explored in a definitive manner.

[orcmid]

@rnd0101 I do not like macros (Python lacks them for good), but one powerful feature seems to be missing from miser, and I guess it's not even in the frugal-1: named reusable entities.

That's correct about oMiser. There is no storage and identification of reusable assets. If you look at "The Software Project" diagram and description, it should be clear that oFrugal has that task.

My thinking at the moment has been inspired by the SML/NJ REPL where the same problem is addressed.

Update Based on recent experience of @rnd0101 in attempting a REPL, as reported in comments below, I have expanded (1-7, here) for what is intended as the eventual complete Read-Eval-Print operation of oFrugal.

Update 2018-02-09 with further adjustments to an intended concrete syntax.

1. Statements always begin on a fresh line and continue until there is an ending ";". The use of "\" for escapes follows the rules used by the SML REPL. The prompt should indicate when the reader is expecting more input to complete a multi-line "statement."

2. Statement include "file-reference;" is for loading an oFrugal text-notation script. The loaded file can have all of (1-6).

3. (* ... *) for comments, because they allow nested comments and an easy way to block out code when testing.

4. Statement ob-exp yields, as an ob, the result of evaluation of the ob-exp. The result is presented as an ob-exp Canonical Ob form that, if entered as a statement, evaluates to the identical canonical ob. The input ob-exp text can contain bound-oFrugal references that will be expanded as stipulated in (6, below).

5. Statement ob ^name = ob-exp yields immediate evaluation of ob-exp as in (4), binding the resulting ob to the binding name ^name. The name part must be alphanumeric and can begin with a digit. The binding does not exist until the statement is completed. Any ^name references in the ob-exp text refers to the most recent prior binding to ^name. It is an error for there to be no such binding in effect.

6. ^name is the notation used, anywhere in an ob-exp for immediate in-place substitution of the named ob, all during evaluation of the ob-exp.

7. It is desirable that statement sequence

ob ^name = ob-exp;
^name;

yield the same output ob-exp text form as that for the single statement

ob-exp

NOTE Keep in mind we are at 0.0.n in the early definition of oMiser and oFrugal software. Breaking changes must be considered likely. That's why mockups are exploratory and not the yet-to-be-introduced mainline source-code and its development/deployment. Experiments at this preliminary level is priceless and the willingness of such early exploration earns much appreciation and gratitude.

[rnd0101]

Interesting, that now that I have implemented interactive frugal shell (with auto-completion and saving history), I see that certain things are a matter of taste. For example, I am using "forlindies", not just plain text (this probably comes from my irritation of languages such as bash shell, where commands are not quite hygienically intermingled with variables.

So for example if I were to design it, I't simply used plain identifiers for variables:

x = .A :: .B  (* not evaluated, structural alias *)
y = x :: .C  (* not evaluated *)
z := x :: .NIL (* evaluated *)
y  (* evaluated *)

And used them also without any additional syntax.

For multilines I'd just added open "(" and the line can continue as long as there is no closing ")".

Right now I've added cS and cK to miser module - so they can be used as .cS and .cK in the shell. Less typing.

[rnd0101]

Said that, there is good idea in APL (IIRC) - workspace. The whole workspace can be stored/loaded.

And APL has )command syntax (or is it from some other language?)

[rnd0101]

My concern, as a theoretical matter, is that the Church-Rosser condition is a negative result. How that matters, and where it impacts oMiser, remains to be explored in a definitive manner.

So oMiser is not confluent? I have noticed, that when I forget to enclose combinator S, it is evaluated to some shorter form, which does not work as expected. Is it that my frugal/miser implementation still somewhat buggy or true behavior?

[rnd0101]

I've found one surprising result:

oMiser> (.D ("x" `("y" "z")) ("x" ("y" "z"))) ("eq" "neq")
INPUT: ((.D :: (("x" :: `(("y" :: "z"))) :: ("x" :: ("y" :: "z")))) :: ("eq" :: "neq"))
ev (.SELF) (.ARG) ("x") -> "x"
ev (.SELF) (.ARG) (`(("y" :: "z"))) -> ("y" :: "z")
ap ("x") (("y" :: "z")) -> ("x" :: ("y" :: "z"))
ev (.SELF) (.ARG) (("x" :: `(("y" :: "z")))) -> ("x" :: ("y" :: "z"))
ev (.SELF) (.ARG) ("x") -> "x"
ev (.SELF) (.ARG) ("y") -> "y"
ev (.SELF) (.ARG) ("z") -> "z"
ap ("y") ("z") -> ("y" :: "z")
ev (.SELF) (.ARG) (("y" :: "z")) -> ("y" :: "z")
ap ("x") (("y" :: "z")) -> ("x" :: ("y" :: "z"))
ev (.SELF) (.ARG) (("x" :: ("y" :: "z"))) -> ("x" :: ("y" :: "z"))
ev (.SELF) (.ARG) ((.D :: (("x" :: `(("y" :: "z"))) :: ("x" :: ("y" :: "z"))))) -> .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" :: `(("y" :: "z"))) :: ("x" :: ("y" :: "z")))) :: ("eq" :: "neq"))) -> "eq"

OUTPUT: "eq"

Does this match the proper comparison semantics or is it a defect in my miser implementation that enclosure does not affect comparison?

Update: I guess, I am not using precedence axiom.

[rnd0101]

And another one also bothers me:

oMiser> ((.A .D .B) "x" "x") ("eq" "neq")
INPUT: (((.A :: (.D :: .B)) :: ("x" :: "x")) :: ("eq" :: "neq"))

OUTPUT: .B

oMiser> .A .D .B
INPUT: (.A :: (.D :: .B))

OUTPUT: .D

oMiser> (.D "x" "x") ("eq" "neq")
INPUT: ((.D :: ("x" :: "x")) :: ("eq" :: "neq"))

OUTPUT: "eq"

It is surprising, that something is evaluated to .D, but that .D does not work in the same fashion as direct .D..?

These are some other calculations with constructions from above:

oMiser> ((`.A .D .B) "x" "x") 
INPUT: ((`(.A) :: (.D :: .B)) :: ("x" :: "x"))

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

oMiser> (.D :: (`(("x" :: "x")) :: .ARG))
INPUT: (.D :: (`(("x" :: "x")) :: .ARG))

OUTPUT: .B

oMiser> (.D :: (`(("x" :: "x")) :: .ARG)) ("eq" "neq")
INPUT: ((.D :: (`(("x" :: "x")) :: .ARG)) :: ("eq" :: "neq"))

OUTPUT: "neq"  (* we've got a negation! *)

oMiser> 

Unless it's some bug in my implementation, this may be a sign of pair's ev going too deep. For me this means, that it is hard to rely on denotational semantics where semantics of the whole is composition of said semantics of the parts. That is, breaks compositionality.

[orcmid]

Does this match the proper comparison semantics or is it a defect in my miser implementation that enclosure does not affect comparison?

I think you are running into a pure-lindy-trace problem and some application-ordering matters also. When using lindies as application operator scripts, it is important to avoid premature determination of a pure-lindy-trace.

oMiser> (.D ("x" `("y" "z")) ("x" ("y" "z"))) ("eq" "neq")

Here, the ("x" ‵("y" "z")) will eval to ap("x", "y" :: "z") = x" :: "y" :: "z"= eval(("x" ("y" "z")))

So the unexpected result, "eq" is correct. Enclosures do matter in comparison, but you have to watch for cases where eval(‵x) = eval(x), as when x is any singleton. In the above example, the pure-lindy-trace rule also kicked in on ap("x", "y" :: "z") for both sides of the comparison.

Given all of that, I think the way to get what you want, is with

oMiser> (.D ‵("x" ‵("y" "z")) ‵("x" ("y" "z"))) ("eq" "neq")

using literal operands to the comparison and avoiding any automatic trace creation when it is the ob you want to use, not its applicative interpretation.

[rnd0101]

That last of course gives the result, but raises the question of how miser can process complex ob structures of lindies?

One more strange case, related:

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

OUTPUT: .A

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

OUTPUT: .B

comparison depends on which operand has more enclosures.

[orcmid]

It is surprising, that something is evaluated to .D, but that .D does not work in the same fashion as direct .D?

Let's take it apart.

oMiser> (.D "x" "x") ("eq" "neq")

produces the expected and correct result.

oMiser> .A .D .B

evaluates as ob.a(eval(.D .B)) = ob.a(.D ‵.B .ARG) = .D

oMiser> ((.A .D .B) "x" "x") ("eq" "neq")

has a few problems.

First, as a practice I would use ‵("eq" "neq") to have that be taken as the ob, and not the applicative-interpretation. Always quote the surround of what you want to be taken as data in further evaluation. Don't rely on the pure-lindy-trace rule when an applicative expression is not intended.

Secondly, (.A .D .B) "x" "x") should eval as (.A (.D .B))( "x"( "x"))) = ap(.D, "x" :: "x").

Ahah!

So the above application produces .D :: ‵("x" :: "x") :: .ARG and that applied to "eq" :: "neq" is going to produce .B because "x" :: "x" is not equal to "eq" :: "neq".

[orcmid]

comparison depends on which operand has more enclosures.

oMiser> .D (````"x") (```"x")
INPUT: (.D :: (`(`(`(`("x")))) :: `(`(`("x")))))

There's something I don't understand about this. It looks like a parsing problem. There's an extra "(" in front of the first "x". The matching ")" is beyond the second "x".

Oh! This is failing to detect the special form eval(.D :: x :: y) immediately as ob.d(eval(x), eval(y)). The same rule should also apply for eval(.C :: x :: y) = ob.c(eval(x), eval(y)).

This seems to have worked properly in your evaluation of ap(ap(ap(cS,x),y),z) so I am not clear what happened. Oh, wait. I understand. You are using the functional sugaring, so it is interpreted as .D(...).

Try .D (````"x") :: (```"x") or fall back to pure-applicative notation, (.D (````"x")) (```"x") which should work properly. I have no idea about the difference based on order of the operands.

Note. Without adding an infix "=" another way to handle the pure applicative approach is by writing .D(x,y) or .D(x) y which both evaluate the same as (.D x) y). I don't think I got into that in describing the applicative-expression sugaring. Having an infix "=" just like the infix "::" is probably a good idea. Precedence rules will have to keep things tidy. More thought required.

[orcmid]

I promise things should not get any messier. You have found all of the idiosyncrasies, as far as I can tell.

[orcmid]

I do not like macros (Python lacks them for good),

I don't know a better term. These are little "source"-level plug-in that are of partial scripts useful in writing common idioms that will arise. Let's revisit this question when there are some of those.

[orcmid]

Thank you for this effort. It is showing me places where the informal description needs more care. Also, I see some speed-bumps that need to be resolved by the care taken to specify the REPL functions, the input syntax, and the two-stage read-then-eval arrangement. I'll provide more over where we have been discussing that.

[rnd0101]

What I've tried to convey with this example

oMiser> ((.A .D .B) "x" "x") ("eq" "neq")

is that I assumed the (.A .D .B) thing evaluates to .D, so the result should be equivalent to the (.D "x" "x") ("eq" "neq") , because it's in the brackets. The analysis of ".D :: ‵("x" :: "x") :: .ARG and that applied to "eq" :: "neq" is going to produce .B" is correct, my point is it very surprising to a programmer, because usually (I do not go into cases found by Rudolf Carnap here) one can substitute evaluated term with the result. For example, imaging 2 + 3 x 5 is not equal to 2 + 15: This raises a question: is 2 + 15 equal to 17?

Of course, I understand, that sometimes evaluation needs to be guarded from happening (that is what is my understanding of backtick, which is QUOTE in LISP, if I remember correctly.). But I do not understand how can I introduce expression, which produces .D into expression, so it will work?

Again, I do not know how faithful my Python implementation is.

[rnd0101]

I've changed implementation of equality in my Python's miser, introducing "state": pairs and enclosures are represented in state as tuples of subelements states, primitives and lindies' state is their name. Python automatically compares such structures, so hopefully this is desired comparison semantics for miser.

Revisiting the above with more minimal examples:

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

OUTPUT: .A

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

OUTPUT: .A

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

OUTPUT: .A

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

OUTPUT: .A

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

OUTPUT: .B

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

OUTPUT: .A

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

OUTPUT: .B

Now the picture is clear: both operands are evaluated, so single tick cant be distinguished from a lindy.
(introducing state also gives a way to quickly pickle / unpickle obs to storage in Python, eg, to save / restore workspace)

[rnd0101]

I think, the equivalence of single quotations is understandable and is not an issue. I will open new issue for the .A .D .B case, as I think it's important.

Here: #10