[virtmach] lambda

Ewald Pfau ehp@ear.co.at
Thu, 09 Dec 1999 00:33:06 +0100

David Rush <kumo@bellsouth.net> wrote:

dr> Ceri Storey <cez@nomorespam.freeserve.co.uk> writes:

> in a bytecode based VM, is it possible to have a lambda opcode? (as
> scheme/lisp/lambda calculus) woud it be a case of pushing a pre
> comipled function onto the stack (from a vector of constants, as in
> emacs) or can you create one from the nomal 'stream' of instructions?
> (i apologise for the pointless question, and for apologising. [stack
> overflow from exessive recursion])

dr> Others may disagree, but I don't think so. At least not in the way
dr> that you have phrased the question (Although Forth machines in
dr> particular probably *can*, compiler interaction is strange and
dr> wonderful in their world). The problem is that identifying a string
dr> of instructions as a well-formed function is a non-trivial task; it
dr> may even be undecidable. Really only the compiler knows where the
dr> function boundaries lie, and it got it's knowledge from the program
dr> source code, written by a human.

Forth seems nicely represented here. Let me first assume VM to be
something like the realisation of a 'behaviour of an intended
architecture disregarding physical representation' (and forgive me if my
English has a bit of a 'Germish' grammar...). Now what from Forth can be
offered, as a strength related to VMs, this is: to come up with such
architectures in a double sense already.

For both, a behaviour of groups of elements is more or less strictly the
result of the sequence of those elements [1]. For one, in byte code
machines and in 'classical' implementations, this reads: there is an
address interpreter or a byte-code interpreter. For another: when
presented human readable source text, there is an input stream

So when regarding VM implementations from Forth, one will meet first of
all those distinct two layers. Now when introducing late-bound
calculation this is to be understood in two directions: Having a text
interpreter, one may feed expressions immediately to it. In that this is
really trivial, it has no own name in Forth ( - trivial when
disregarding details, mainly like error recovery and the scope of
validity of names of procedures).

When not having a text interpreter, as is more typical for a VM
environment, if text interpretation is not an option for the (governing)
address or byte-code interpreter, so there is a back-door open: Parts of
code typically are representable by 'execution tokens', which is values
representing a run-time behaviour. Late bound calculation is achieved by
feeding such values, so those are acted upon as needed (Forth terms:
EXECUTE or CATCH, by the latter a frame for error recovery is
established first).

Notation in Forth is achieved by using the Forth word "' <name>" ("tick
of name"), so such an execution token is available when writing sources.
An underlying assumption is to be taken care of as well, so execution
tokens, which are kept as bare values, will not loose their property of
representing a behaviour, through-out any compilation processes which
may follow.

E.g. one may set-up in different parts of an application's sources, for
one, a scanning mechanism which represents members of a list, and, for
another, methods to be applied to the members thus found. There is no
difference in wording, if such methods solely represent algorithms and
some result is to be requested, or if it refers to changing some
objects' status.

dr> OTOH, in a VM I built fairly recently, functions were first class
dr> objects and I had a generalized 'apply' operator that took a number
dr> of arguments off the stack and created a closure based on the
dr> function argument. The closure would then be executed. The cool
dr> thing was that the value of a closure whose arguments were
dr> underdetermined was itself (closures were implementationally
dr> identical objects to functions with a different life-cycle).

Let me guess this has a representation in both of the above schemes:
either a sequence of tokens, or a piece of source code which is
'evaluated'. The main point remains: execution is vectorized, be it via
a string (so there is a text interpreter in between) or be it via a
sequence of tokens.

dr> So I got partial application of functions with very little effort;
dr> could create functions on the fly from other functions without
dr> having tremendous compiler support. If this is what you're looking
dr> for from a 'lambda' operation then I'd say, yes it can be done.
dr> YMMV.

Hmm.. could need some connotational expansion of term as well: how is
'lambda calculus' related to representation of objects? There is an
ancient paper of Backus lying around - following that one I would assume
that it is immediate results which are meant. But we have since then
some 'double-plussed' featuritis in between, so maybe I missed

[1] this is possible, after the unterlying post-fix notational
convention allows for to by-pass completely the necessities of
syntax-bound algebraic notation.