Reflection and quotation

[Francois-Rene Rideau]

Dear Tunespeople,

being back from short vacations, I'd like to reply to Brian's original
message about quotation.

On Wed, Aug 16, 2000 at 10:21:16PM -0700, RE01 Rice Brian T. EM2 wrote:
> I'd like to discuss an interesting aspect of Tunes that previously had not
> explicitly occurred to me. That is reflection on the quotation function of a
> language.
A very important topic indeed.
Quoting is about the fundamental question in a reflective system:
what are the limits of an object? what are the limits of the system?
what is to be explicit? what is to be implicit?

In LISP, depending on what you need to preserve through kwoting,
you have lots of variants of (write), or just (lambda (x) `',x).
Perl strings and regexp have the quotemeta function for that.

As far a theory goes, a very insightful account of the subject is made in
Jean Goubault's papers about his computational interpretation of the S4
modal logic in terms of an lambda-eval-quote calculus, where naturally
appear QUOTE, EVAL, KWOTE, QUASIQUOTE, UNQUOTE.
Each plays its role, and the "quoting mechanism" is not complete
if deprived of any one of them. Even then, you only have basic support
for a one-minded quoting mechanism.

@TechReport{GoubaultJ:S4,
	Author={Jean Goubault},
	Title={{O}n {C}omputational {I}nterpretations
		of the {M}odal {L}ogic {S4}},
	Institution={University of Karlsruhe},
	Year={1996},
	Note={\myurl{http://hypatia.dcs.qmw.ac.uk/data/G/GoubaultJ/S4/}}
}

QUOTE is the syntactic meta-operator (or source code constructor)
that embeds source code into representation of source code
(a monomorphism from source code into data values).
It is evaluated at parse/compile-time, not run-time.

EVAL is a base-level operator from values that are valid source code
into values that coincides with external metatheoretic evaluation,
i.e. EVAL is a function (not a special form) such that its application to
(QUOTE ~X) is same as evaluation of ~X, for any source text ~X.
Things actually get more complex with context, i.e., with state
at the meta-level. Only purely combinatorial languages
like Church's combinatory logic, unlambda, Joy, and more suches,
needn't such meta-state. In categorical such pure combinatorial language,
EVAL is a value the application of which is an endomorphism of
the value space that coincides with external evaluation.

KWOTE is a base-level operator that yields a valid source code for a given
object, such that for any value X, (EVAL (KWOTE X)) = X.

QUASIQUOTE and UNQUOTE are syntactic meta-operators to build
partial expressions, higher-order expression builders, etc.


Jean Goubault's work, beyond the technical issue of confluence
that constitutes the academic aspect of the papers, shows
the expressive importance of QUASIQUOTE and UNQUOTE.
Without such a mechanism, QUOTE/KWOTE and EVAL would be but
boxing and unboxing; it would be impossible to dynamically build
any interesting expression; QUASIQUOTE and UNQUOTE allow
for non-trivial use of source code.

However, I think that we can and must go beyond the insight that JG brings:
conversely, there needs be a mechanism to deconstruct source expressions,
whether made by QUOTE, KWOTE, QUASIQUOTE, or whatever,
or else, the only thing you can do with source code
is EVALuate it within a `(context ,[]);
that is, you end up with write-only metaprogramming,
whence you must resort to roll your own ad-hoc source code encoding
on front of QUOTE'd text for manipulation using source code as argument.

LISP solves the problem by standardizing on source expressions as CONS-lists,
that you can arbitrarily construct and deconstruct,
so you can build QUASIQUOTE, UNQUOTE, and source deconstructors
from lower-level primitives.
The downside is said low-levelness, which might (or not) get in the way,
depending on what you're trying to do.
In any case, let's say that SEXP as CONS-lists are sometimes not adapted
to source-code representation (they don't track line-numbers/origin/foo
for debugging/reverse analysis purpose; they are sometimes not fit for
optimized domain-specific representations; etc).
Absence of KWOTE in modern LISPs (well, some CL allow to write
not only circular structures, but also functions)
means that even then, the last step of a metaprogram (running)
is also write-only.

I feel that the "right abstraction level" would be to standardize
on QUASIQUOTE/UNQUOTE/QUOTE so as to construct code
_and_ to have have pattern-matching of quasiquoted patterns
for deconstruction of source code.


> As a preliminary survey, I'd like to know if any of you all know
> of languages (experimental or otherwise) that have interesting forms of
> quotation, or even possible a notion of quotation which can be dynamically
> modified.

m4 can dynamically change quote characters,
but has no kwote function, which is particularly horrible
since its evaluation mechanism will dynamically parse function definitions
with whatever quote character is current, so that in practice, you may not
lightly mix functions defined with different quote sets.
Lexical quasiquotation is also hell to achieve since you never know
how many times a given text will be parsed, and will have a hell of a time
making dynamic computations on strings that include quote characters
(it is nonetheless possible).
AFAIK, only REBOL is braindead enough to dynamically parse function text
like m4 does!

LISP with macros and reader macros,
FORTH with input buffer access from IMMEDIATE words,
have mechanisms not just for arbitrary user-defined quoting
(as opposed to kwoting), but also for syntactical extension
and general metaprogramming at compile time;
plus compile time can be dynamic.
But code inspection, while possible (INSPECT) SEE
has no standardized result in any way.

FORTRAN with Hollerith-strings, Shells, Perl, and more, with <<,
all have mechanisms for quoting arbitrary text into strings,
which can in term be used to transform source code into a crude
representation of it in a constant (well ok, logarithmic) number
of character insertions at two places. Shells and Perl can arbitrarily
manipulate such strings and eval them. I've done much too much
metaprogramming with zsh myself.


Quoting is all about building a way to name an object that will be
understood in a different context that doesn't share all the knowledge
of the current context. It is a form of reification.

Obviously, deeply related to the notion of quotation is that of what
context is preserved in such reification: what parts of the system state
are to be considered implicit, external, and what parts of the system state
are to be considered explicit, internal, that require visible reification.

"Quoting" so as to communicate with an interactive debugger on same host
is not the same as "quoting" so as to communicate with another equal node
on a distributed system, which is not the same as serializing for use on
an unknown untrusted and untrusting host external to the system.
Modalities of quoting can get hairier if you're developing meta^n-tools
with complex sharing of knowledge or lack thereof between various systems
and metasystems (e.g. building a dynamic banking system with
trust-preserving protocols that involves various embedded computers
in terminals, cards, etc).


> Basically, if we consider EVAL = UNQUOTE o APPLY as a basic equation
I'm not quite sure what you mean.
The only correct base-level equation I know about quotation is:
	(EVAL (KWOTE X)) = X
As for the meta-level equations (looking inside the quoted text),
they are but the denotational semantics for EVAL
as expressed in terms of the quote-compatible source structure, e.g.:
	(EVAL (CONS X Y)) = (APPLY (EVAL X) (MAP EVAL Y))
(the above equations, for the sake of simplificity,
assume the context of a pure functional 1-LISP with a total KWOTE function).
Maybe we can have just EVAL = UNQUOTE, as is suggested
by Jean Goubault's paper.


In another message dated 2000-08-16, Brian also said:
> Or orthogonally-persistent memoizaion of functions. ;)
> Yes, I'm trying to drive this point home for you and many other Tunesers.
> This should really be spelled out more clearly in the online Tunes
> documentation (HINT, HINT).

Go ahead. You have CVS access, don't you?


Yours freely,

[ François-René ÐVB Rideau | Reflection&Cybernethics | http://fare.tunes.org ]
[  TUNES project for a Free Reflective Computing System  | http://tunes.org  ]
-- Question authority!
-- Yeah, says who?