Subject: [clisp-list] Re: New, from-scratch implementation of backquote.

From: "Hoehle, Joerg-Cyril" <[email-masked]>
Date: Mon Mar 17 02:50:23 2003

Kaz Kylheku wrote:
> The job of expansion, rather, is moved
>into the macro itself.  So we now have a thick macro, but a thin reader
>macro rather than the other way around.

If it's in a macro (instead of read-time), it makes me wonder whether it can also insert into a vector:

[51]> `#(1 2 ,(list 2 3) 3)
#(1 2 (2 3) 3)

Normally, using macros instead of reader stuff only allows code transformations in places that get evaluated (i.e. forms, e.g. not inside a (declare #) expression). You'd have to guess somehow that the #() which is being read is not a literal array. Do you provide for this?

Regards,
	Jorg Hohle.

---

From: Kaz Kylheku <[email-masked]>
Date: Mon Mar 17 11:12:07 2003

> [51]> `#(1 2 ,(list 2 3) 3)

Yes. This will turn into the code

 (backquote #(1 2 (unquote (list 2 3))))

The macro will note that the argument form is a vector and generate
code which performs the backquote expansion on the list, and then
converts the result to a vector. The latest otpimized version will
in fact turn it, I think, into:

 (apply #'vector '(1 2 (2 3) 3))

Which reminds me that I should add some optimization for reducing
a constant list to a constant vector; we should be spitting out
the literal object:

  #(1 2 (2 3) 3)

> Normally, using macros instead of reader stuff only allows code
> transformations in places that get evaluated (i.e. forms, e.g. not
> inside a (declare #) expression).

I don't think backquote is required to work in (declare ...)
expressions, because the code which a backquote generates has no way to
execute. That is, if you expand the equivalent code  by hand, it still
won't work:

   ;; can't do this
   (declare (list 'optimize (list 'speed speed) (list 'safety safety)))

   ;; so don't expect this
   (declare `(optimize (speed ,speed) (safety ,safety)))

Note that the existing implementation of backquote in CLISP is a still
a macro, albeit a trivial one. All it does is regurgitate the second
argument, because the structure of a backquote expression is:

   (SYSTEM::BACKQUOTE PRETTY-PRINT-FORM EXPANDED-FORM)

The macro simply returns the EXPANDED-FORM which was computed at read
time. But evaluation is still required for it to do that.

The one advantage of this approach is that the expanded form is *there*
whether you evaluate or not, so if you inspect the program source code
as an object, you will find it---provided that the source code was
produced by the reader, or else care was otherwise taken to add 
the second argument representing a correct backquote expansion of
the first.

> You'd have to guess somehow that the
> #() which is being read is not a literal array. Do you provide for
> this?

I don't follow, because #() *is* a literal array. Maybe you are
thinking of the array notation #A?  No, this is one bug which I will
probably not worry about. That is, I do not distinguish between #(1 2
3) and #1A(1 2 3) (one dimensional array).

So in fact unquoting will work over #1A array notation:

  `#1A(1 ,@'(2 3) 4) ;; wee!

We can think of this as an extension which is not forbidden by the
spec according to my interpretation.

All we know in the macro is that we have some argument which is a
vector object. We don't know whether it came from the notation  #(...)
or whether it came from #1A(...) but we know it's one of these
two---unless someone constructed the backquote source code
programmatically, using something like:

   (list 'system::backquote (vector 1 
                                    (list 'system::unquote 'a) 
                                    2))

   ==> `#(1 ,A 2)

when this is EVAL'ed, the backquote macro will think that the vector
came from a #(...) notation, and treat the embedded unquote as
expected. This is an extension of behavior to backquote, which is
specified purely in terms of reader actions. 

This is a feature: we want the backquote notation to have a
list-based target language such that we can write code which writes
that language.

In stock CLISP, this fails: if we EVAL the result of the above list
construction, we get NIL. Why? Because the second parameter to the
backquote, the expanded form, is missing. The macro does nothing;
expecting a reader to have produced the expansion.

But the pretty printer tells you a nice white lie by showing the object
as a backquote notation.

---

From: Sam Steingold <[email-masked]>
Date: Mon Mar 17 14:03:32 2003

> * In message <[email-masked]>
> * On the subject of "Re: New, from-scratch implementation of backquote."
> * Sent on Mon, 17 Mar 2003 11:10:12 -0800 (PST)
> * Honorable Kaz Kylheku <[email-masked]> writes:
>
> That is, I do not distinguish between #(1 2 3) and #1A(1 2 3) (one
> dimensional array).
> 

<http://www.lisp.org/HyperSpec/Body/sec_2-4-6.html>:

* `basic is the same as 'basic, that is, (quote basic), for any
  expression basic that is not a list or a general vector.

...

* #(x1 x2 x3 ... xn) may be interpreted to mean (apply #'vector `(x1 x2
   x3 ... xn)).

#1A is not mentioned.  I suggest raising this on c.l.l.

personally, I would rather signal an error here, like CMUCL and
unpatched CLISP (ACL? LW?) do because

 - when you write a literal, your would write #() anyway, so the simple
   user does not lose

 - when you generate the form, you should make sure that the dim is 1
   anyway, so you can use #() just as well

 - when the user sees that `#1A(1 2 ,a 4) works but `#2A((1 2) (,a 4))
   does not, the user would be rightfully surprised; he will also think
   that `#2A(,a ,b) should work when a and b are sequences of the same
   length &c &c...

-- 
Sam Steingold (http://www.podval.org/~sds) running RedHat8 GNU/Linux
<http://www.camera.org> <http://www.iris.org.il> <http://www.memri.org/>
<http://www.mideasttruth.com/> <http://www.palestine-central.com/links.html>
Who is General Failure and why is he reading my hard disk?

---

From: Kaz Kylheku <[email-masked]>
Date: Tue Mar 18 12:50:20 2003

>    that `#2A(,a ,b) should work when a and b are sequences of the same

Okay, how about dividing the work into three milestones.

Basically I have taken care of most of the first milestone already:
optimization, proper i18n-able error messages using TEXT macro,
system builds itself cleanly. What's left is beating up the backquote
with lots of nasty test cases.

In the second milstone, I can put in rudimentary support for 
backquoting over multi-dimensional arrays. This means that no special
reader is used. A form like

  #2A((,@x ,y) (,z))

will basically be read to produce the object.

  #2A(((SYSTEM::SPLICE X) (SPLICE Y) ((SPLICE Z))))

This will be supported in a straightforward way. The algorithm is:
walk the leaf row vectors of the array and perform the backquote
substitution on them in the straightforward way. Then spin these
expanded row expressions into a big MAKE-ARRAY constructor call.

Conceptually, this is like distributing the ` operator into the rows,
in other words:

  `#nA( .. ( ... (...) (...) (...) ... ) ... )

will be treated something like:

   #nA(... ( ... `(...) `(...) `(...) ... ) ...)

except that evaluation of the unquotes within `(...) is arranged. This
means that syntax like #2A(,@form) will not work, because the unquote
is at the wrong level; the form must have the required shape for a
two-dimensional array, and the unquotes must appear in the innermost
lists only.

In the third milestone, we can work in unrestricted unquoting, such as:

   (let ((rows '((1 2) (3 4) (5 6))))
     `#2A(,@rows)) ;; splice in all the rows.

   ==> #2A((1 2) (3 4) (5 6))

This, of course, requires cooperation from the #A reader macro. In
fact, it will probably be necessary for the backquote implementation
to temporarily overrides the read table with its own reader.  

I think there is value in being able to do unquoting over arrays,
even if it's not portable.

For instance, suppose you want to make a rank 3 matrix with some
non-zero eigenvalues on the diagonal, and zeros elsewhere:

  (let ((e1 3) (e2 4) (e3 5))
    `#2A((,e1   0   0) 
	 (  0 ,e2   0)
	 (  0   0 ,e3)))
 
   ==> #2A((3 0 0) (0 4 0) (0 0 5))

This elementary substitution is possible just with milestone 2
unquoting support.

---

From: Sam Steingold <[email-masked]>
Date: Wed Mar 19 09:02:25 2003

> * In message <[email-masked]>
> * Sent on Tue, 18 Mar 2003 12:48:34 -0800 (PST)

let us stop here!!!

BTW, did you try some profiling?
E.g., try
(times (compile-file "compiler.lisp"))
with stock backquote and with your version.

> backquoting over multi-dimensional arrays.

this will explicitly contradict the spec, be of dubious value and
require your work which can be used elsewhere.

What I was saying in my original message was that `#1A(... , ...)
should __NOT__ work!

OTOH, you are free to code whatever you fancy, and I will be delighted
to put #A/backquote in - as an option, e.g., when
CUSTOM:*BACKQUOTE-SUPPORT-NON-VECTOR-ARRAYS* is non-NIL.

-- 
Sam Steingold (http://www.podval.org/~sds) running RedHat8 GNU/Linux
<http://www.camera.org> <http://www.iris.org.il> <http://www.memri.org/>
<http://www.mideasttruth.com/> <http://www.palestine-central.com/links.html>
MS Windows: error: the operation completed successfully.

---

From: Kaz Kylheku <[email-masked]>
Date: Thu Mar 20 08:03:08 2003

> > with lots of nasty test cases.

I have a temporary home page for this mini-project now.

http://users.footprints.net/~kaz/clisp-backquote-patch.html

The current status is that we have an backquote implementation that
seems to be reliable, and puts out good code.

The destructive splicing syntax is supported in earnest, using
translations to NCONC.

All error messages are in TEXT macros, but some new text will require
translation into foreign languages.

> with stock backquote and with your version.

Not yet, but will do. I think that the backquote puts out pretty good
code now, comparable with the original implementation.  It's very
similar, in fact, except that in some cases it outputs nested code,
like:

   (cons 'a (cons 'b (append a (append b c))))

where the original implementation would put out:

   (list* 'a 'b (append a b c))

Profiling under CLISP shows that even for making a list of two cons
cells, one call to list* with three arguments is slightly faster than
two calls to cons, so this reduction appears worthwhile, and can be
done by a trivial cleanup pass.

I'm not too worried about the reader or macro-expansion speed, since
normally a backquote is expanded just once, but the generated code may,
in some contexts, be executed countless times, so it should be good.

So what is left:

- disabling `#1A... expansion.
- i18n (need help with that, deferred)
- complex test cases
- profiling