Practical frugal shell issues and possible solutions

[rnd0101]

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?

[orcmid]

Question Closed

There is some historical material here with regard to motivation and the introduction of lambda.x and rec.p by definition. However, the topic is better carried on, now, in Question #8 and #14 materials.

---

@rnd0101 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?

A fundamental purpose of oMiser is providing a model of computation that is grounded a particular way and that is at a primitive level where combinators and lambda-expressions are representable rather than taken as given.

The division is intentional. It will raise problems that we might find not worth solving. I want to pursue this course until it is clear that there is no good way to extend to higher levels from this base. Pursuing the original Question #7 topic will introduce some of the concerns that arise in achieving higher-level representations.

We're also not trying to define the Scheme language, the point of that Stack Exchange question. (I also think that question discussion omits exceptions/continuations, although they might not be intrinsic to Scheme. In the SICP book, they show it in a constructed interpreter, but I don't know about in Scheme Language itself.)

[rnd0101]

Yes, sure, I see no problems with oMiser representing combinators or lambdas, but there still is a slight chance recursion will be problematic in practice with just SELF at disposal.

[orcmid]

@rnd0101 there still is a slight chance recursion will be problematic in practice with just SELF at disposal.

Yes.

The use of obap.ev(p, x,exp) accomplished two things.

The first is providing the single applicative operand to the exp eval without using "variables." We can say that x holds the obap.ARG binding applicable in the eval of exp in the current applicative operation.

The second is providing the single applicative operator (script) to the exp eval by having p hold the obap.SELF binding that apples in the current applicative operation.

One might think of (p,x) [better, symbolically, [p,x]) as the environment of the exp eval for the current applicative operation.

Having p accessible in this way essentially accomplishes the Y combinator implicitly for every applicative-operation evaluation.

In this manner, the least fixed-point is no longer by hand-waving at the combinatory logic level. Instead, the termination of recursion is accomplished by conditional execution of branch conditions that arrive at the end result or continue in a recursive reduction step toward the eventual result.

It is the obap.EV that initiates evaluation of a chosen case after the correct code to continue with has been selected in the evaluation of the obap.EV operand. We might say that obap.EV is the applicative counterpart of goto: an ob derived as data is next interpreted as part of the script. That is demonstrated by the has script and especially its hasX partial evaluation that makes the recursion more evident.

There is a difficulty with regard to the representation of mutually-recursive procedures. I noticed that when sketching a demonstrating that obap.ap(p,x) could be simulated by a script oU that actually implements obap.ap(p,x) by obap.ap(obap.ap(obap.ap(oU),p),x), and oU is non-trivial -- can't be the identity combinator. In the particular case, there is a way of unwinding the mutually-recursive obap.ap and obap.ev specifications such that all recursions are in obap.ev only and obap.ap is defined to rely on obap.ev. obap.apint is also adjusted to involve no recursive dependencies.

I am not worried about a general mutually-recursive solution at this point. It is possible to arrange a form of explicit Y where each of the mutually-recursive functions receives the other functions as some form of initial operand. That's messy but can be done. The hard part is getting partial evaluations so that this passing doesn't have to happen interminably each time there is application of one from within another. I haven't figured out the ceremony for that.

It would certainly be easier if there was more environment than the default [p,x]. I want to avoid that for oMiser and, instead, demonstrate the contortions required before solving the problem with a higher-level of Miser. I think there are computational-complexity insights to be found in this.

PS: The reason there are to be lambda.x and rec.p is that rec has the function served in LISP by the LABEL form. lambda abstracts operand x mentions to obap.ARG binding references, rec abstracts the p mentions to obap.SELF binding references.

[orcmid]

There are some additional motivational matters covered here, but no remaining question. This too will be referenced from Question #8 and Question #14 with respect to motivational aspects of the level of oMiser abstraction, how lambda-expressions are expected to work, and some open topics in that area (such as mutually-recursive procedures)..