Re: The power of Lists

[Keith Wright <kwright@xxxxxxxxxxxxxxxxxx>]

> From: =?ISO-8859-1?Q?Jens_Axel_S=F8gaard?= <jensaxel@xxxxxxxxxxxx>
> Cc: srfi-72@xxxxxxxxxxxxxxxxx
> 
> Hi Keith,
> 
> > If it were done with some procedural macro system that represents
> > syntax as a special type, it could not have been tested on lists
> > of symbols, it would have been full of syntax->list and
> > list->syntax conversions in non-obvious places, and I just don't
> > think it would have been so much fun that I would have stayed up
> > half the night working on it, or finished it before morning.
> 
> I liked your example so much I decided to put in the conversions.

I'm glad you liked it.  Can I ask what you converted it to?
I mean, I can see what you did, but is it MzScheme, Chez, ...?

I knew by the time I finished typing that paragraph that I was
overstating the case, but out of perversity I hit send anyway.

I reserve the right to say whether I am having fun, but
in fact, given two isomorphic types and the two functions to
convert between them, it can't be too much harder to write
the program to use one vs. the other.

The real problem, if there is one, comes in making or using
library procedures where you are not allowed to modify the source
code, but want the same procedure to work in either case.

If eveything is represented as a list then procedures can
be parameterized by operations on elements only.  If the
lists are complicated and the elements are simple, then that
is a big win.  For example, the parser can be changed from
symbol lists to syntax by changing nothing but the function
that assigns weights to the operators, without changing 
the source of the parser at all!

This particular example is near the limits of its usefulness,
because there is not an infinite supply of things people
want to put into lists of infix expressions and parse into
Lisp syntax.  But you could imagine that someone thinks of
a new kind of identifier, perhaps with more debugging info
attached, or appropriate to an extended language, and wants
to reuse the parser for that.

For a better example I should have found a way to use more
library procedures like |list|, |map|, and |append|, but
standard Scheme doesn't have all that many list library
procedures, and I didn't want to have to invent a lot of
them just to show how much trouble it is.

> The first change is that the table isn't syntax, but a list.
> You defined the table as
> 
>      (define table (syntax ((:= . 8)(or . 7) (and . 6)
>                             (< . 5) (= . 4)(+ . 3)(* . 2))))
> 
> although it is only the identifiers are syntax-objects in
> this context. (Btw - that's an example of "breaking the abstraction")

Yes, I felt a bit guilty writing that, but it was already the
most boring part, and the SRFI reference implementation does not
accept the #' abbreviation for |syntax|.

> The assocations from identifiers to weights can be written
> directly as:
> 
> (define table `((,#':= . 8) (,#'or . 7) (,#'and . 6)
>                  (,#'< . 5)  (,#'= . 4)  (,#'+ . 3) (,#'* . 2)))

so I would say (quasiquote (((unquote (syntax :=)) . 8) ((unquote...
  ;; sick of typing this, 
  ;; enough for an example

> Since your version uses list? and pair? to check whether a
> subexpression is a compound expression, we need stx-list?
> and stx-pair? when checking for compund subexpressions.

So the real question is: What do you gain by having isomorphic
types with all the operations repeated with different names,
and how many times are you willing to do everything over
from the beginning when somebody thinks of a "new" kind
of list which is not a list, but is rather a stack, a queue,
a bill of materials, a star catalog, ...

In the past the rumor had been floating about that syntax could
_not_ be represented as the lists it appears to be, because
hygienic macro expansion required a lot of information at the
internal nodes.  But now, until somebody finds the bug, it
seems that Dr. van Tonder has shown that is not true.
Lists of identifiers suffice, provided only that the identifiers
are smart enough.

A lot of people still seem wedded to the idea that the internal
nodes need a lot of information attached in order to support
debugging, so I would like to ask the further question:
What do you need to know about a piece of syntax that is not
covered by its shape as a parenthesized list of identifiers
and everything there is to know about the identifiers?

For example, if I am told that division by zero happened,
and that the occurrence of / that called for that division
came from this location in that file and the arguments were
such and such, does that not pretty much exhaust the issue?
Will someone demand to know more about the occult properties
of the parentheses that attach that / to those arguments?

Thank you for your interest.

-- 
     -- Keith Wright

Programmer in Chief, Free Computer Shop
 ---  Food, Shelter, Source code.  ---