[stack] Re: Some thoughts on Object Cat

--- In [email protected], "Christopher Diggins"
<cdiggins@...> wrote:
>
> Hi Manfrred,
> 
> > > I solved the "dup apply" (or "dup i", god I hate using "i" to mean
> > > application) problem by reintroducing "self" types.
> >
> > In Joy at least, the i combinator does not mean application. Joy is a
> > concatenative language, not an applicative language.
> >
> > The applicative
> > languages are the lambda calculus and the combinatory calculus,
> > together with their descendents ­ just about all programming languages
> > descend from the lambda calculus. All applicative languages have an
> > apply operation: apply this function to those arguments, but
mostly there
> > is no explicit symbol for that operation. Joy does not have such an
> > operation neither explicit nor implicit.
> 
> Joy does not have an "implicit" apply operation, but "i" most
> definitely is the explicit "apply" operation, if we are to consider
> expressions as functions from stacks to stacks. This is because "i"
> takes a stack-to-stack function off of the stack and applies it to the
> rest of the stack.
> 
> > The i combinator in Joy is pretty much the same as the eval
function in
> > Lisp. It undoes what the the (pseudo-) function quote does.
> 
> That's not quote correct. (eval (quote (1 2 3))) is meaningless in Lisp

Evaluating (eval (quote (1 2 3))) gives precisely the same result as
evaluating (1 2 3) - an error. Consider instead (eval (quote (+ 2 3))),
which yields 5, as expected. In general, evaluating (eval (quote X))
always
gives the same result as evaluating X.

> Anyway, this is where the confusion slips in, you are using the model
> of quotes are expressions, and then quotes are functions. Depending on
> what model you want to use to explain the semantics of Joy, it makes a
> big difference. If you continued throughout with the understanding
> that a quote is a function I think it would be quite clear, that
> "dequoting" is really applying the function to the stack.
> 
> > In Lisp this
> > is true about expressions X (which denote objects):
> >
> > > (eval(quote(X)) = X
> >
> > And in Joy this is true about expressions X (which denote
> > stack-to-stack functions)
> >
> > > [X] i = X
> >
> > so the i combinator undoes what the quotation brackets do.
> 
> Another way of understanding what is happening is that you are
> applying the stack-to-stack transform function to the stack.

Well said. I think Joy can be viewed as purely concatenative - as the
composition of functions, or as applicative - a series of unary functions
from stacks to stacks that will be applied in order. The former is
probably
preferable when reasoning about the language. But realistically it is
implemented as an applicative language.

> > Lisp¹s eval
> > and Joy¹s i are sometimes called dequotation operators.
> 
> This is the jargon of the Lisp programmer though, and is not
> represenative of the actual mathematics being performed. Using the
> term "dequotation" is distracting, because it implies something that
> is happening differently than function application. My point is that
> you can't say "X is a function from a stack to stack", but then say we
> "eval it". This is because "eval" has no well-defined sense in
> mathematics when it comes to functions.

Here are my thoughts about "apply" vs "eval". Consider just operands and
operators. In lisp, eval and apply behave like this:

(eval operand)     -> operand
(eval (f a1 a2))   -> (apply f '(a1 a2))
(apply f '(a1 a2)) -> (f (eval a1) (eval a2))

But with a global stack instead of parameters and everything being a
function, we get:

(eval f)  -> (apply f stack)
(apply f) -> (f stack)

Since everything is a function, eval always invokes apply and apply always
applies the function to the global stack. There is no longer any real
difference between their roles. Instead, evaluating a sequence of
expressions becomes much more important.

In lisp, you can "compose" functions by concatenating them in a global
scope
or within a 'begin' expression. This does compose the side effects of the
functions, but it is not very useful in lisp because the result that the
sequence produces is just the result of the last expression. But if
instead
functions only produced side-effects on a stack and did not return
results,
this would become true composition.

So I would say that, describing concatenative languages in terms of lisp,
'eval' and 'apply' are unified, but the procedure that 'i' corresponds
to is really an improved version of 'eval-sequence' (as SICP calls it)
that
applies a sequence of functions onto a stack.

> > But they are
> > quite different from application. (Many books on Lisp have an example
> > program which is a Lisp interpreter written in Lisp. The two principal
> > parts are eval and apply ‹ and they are very different.)
> >
> > All other Joy combinators are variations on the eval-theme. Some
> > enterprising Lisp programmer might write variations on the eval-theme
> > in Lisp ­ at least for those combinators that do not depend on Joy¹s
> > stack semantics. One example would be a map-eval, quite different
> > from the (second order) map function which many books will give as
> > examples.
> >
> > - Manfred
> 
> - Christopher Diggins
>

Justin