(let ((foo 'bar))
(symbol-macrolet ((foo (list foo)))
foo))
Leads to infinite regression. Is there a trick I can use so the above
is equivalent to:
(let ((foo 'bar))
(list foo))
The reason for this is that I am modifying Henry Baker's parser as
described in: http://home.pipeline.com/~hbaker1/Prag-Parse.html
I want to be able to generate the same code, but depending on the
surrounding macros, can behave differently.
So a fragment like
(and ...
(when (and (< index end)
(eql (char string index) ',x))
(incf index)
...))
Becomes
(symbol-macrolet ((this (char string index)))
(macrolet ((end? () '(< index end))
(next () '(incf index)))
(and ...
(when (and (end?)
(eql this ',x))
(next))
...)))
If I want to parse sexp instead,
(symbol-macrolet ((this (car index)))
(macrolet ((end? () '(null index))
(next () '(pop index)))
(and ...
(when (and (end?)
(eql this ',x))
(next))
...)))
Do you guys think this is a good use of abstraction? Or do macrolets
obscure too much?
From: Pascal Costanza
Subject: Re: Is there a trick so macrolet can't refer to itself?
Date:
Message-ID: <4klrruFcfohfU1@individual.net>
howard yeh wrote:
> (let ((foo 'bar))
> (symbol-macrolet ((foo (list foo)))
> foo))
>
> Leads to infinite regression. Is there a trick I can use so the above
> is equivalent to:
>
> (let ((foo 'bar))
> (list foo))
No, essentially the outer 'foo must have a different name. You can use a
workaround, though:
(let ((-foo- 'bar)) ;; or some generated name
(symbol-macrolet ((foo -foo-))
...
(symbol-macrolet ((foo (list -foo-)))
foo)))
> The reason for this is that I am modifying Henry Baker's parser as
> described in: http://home.pipeline.com/~hbaker1/Prag-Parse.html
>
> I want to be able to generate the same code, but depending on the
> surrounding macros, can behave differently.
>
> So a fragment like
>
> (and ...
> (when (and (< index end)
> (eql (char string index) ',x))
> (incf index)
> ...))
>
> Becomes
>
> (symbol-macrolet ((this (char string index)))
> (macrolet ((end? () '(< index end))
> (next () '(incf index)))
> (and ...
> (when (and (end?)
> (eql this ',x))
> (next))
> ...)))
>
> If I want to parse sexp instead,
>
> (symbol-macrolet ((this (car index)))
> (macrolet ((end? () '(null index))
> (next () '(pop index)))
> (and ...
> (when (and (end?)
> (eql this ',x))
> (next))
> ...)))
>
> Do you guys think this is a good use of abstraction? Or do macrolets
> obscure too much?
Two responses:
a) The problem above doesn't seem to occur here.
b) It's probably better to model this with functions or even with
generic functions because this would be easier to debug, and it's
unlikely that you get too much runtime overhead. In general, use macros
only when functional abstractions don't work, but only for syntactic
abstractions.
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Pascal Costanza wrote:
> howard yeh wrote:
> > (let ((foo 'bar))
> > (symbol-macrolet ((foo (list foo)))
> > foo))
> >
> > Leads to infinite regression. Is there a trick I can use so the above
> > is equivalent to:
> >
> > (let ((foo 'bar))
> > (list foo))
>
> No, essentially the outer 'foo must have a different name. You can use a
> workaround, though:
>
> (let ((-foo- 'bar)) ;; or some generated name
> (symbol-macrolet ((foo -foo-))
> ...
> (symbol-macrolet ((foo (list -foo-)))
> foo)))
>
> > The reason for this is that I am modifying Henry Baker's parser as
> > described in: http://home.pipeline.com/~hbaker1/Prag-Parse.html
> >
> > I want to be able to generate the same code, but depending on the
> > surrounding macros, can behave differently.
> >
> > So a fragment like
> >
> > (and ...
> > (when (and (< index end)
> > (eql (char string index) ',x))
> > (incf index)
> > ...))
> >
> > Becomes
> >
> > (symbol-macrolet ((this (char string index)))
> > (macrolet ((end? () '(< index end))
> > (next () '(incf index)))
> > (and ...
> > (when (and (end?)
> > (eql this ',x))
> > (next))
> > ...)))
> >
> > If I want to parse sexp instead,
> >
> > (symbol-macrolet ((this (car index)))
> > (macrolet ((end? () '(null index))
> > (next () '(pop index)))
> > (and ...
> > (when (and (end?)
> > (eql this ',x))
> > (next))
> > ...)))
> >
> > Do you guys think this is a good use of abstraction? Or do macrolets
> > obscure too much?
>
> Two responses:
>
> a) The problem above doesn't seem to occur here.
The problem is elsewhere.
> b) It's probably better to model this with functions or even with
> generic functions because this would be easier to debug, and it's
> unlikely that you get too much runtime overhead. In general, use macros
> only when functional abstractions don't work, but only for syntactic
> abstractions.
Ya. I am actually starting from Peter Siebel's code. It's already using
generic functions. In the particular case of Baker's parser, using the
macros allows me to keep most of the code generator functions
the same. For example, to go from lexer to sexp-parser, I only
have to specialize the code generator for the sequence grammar.
(and ...
(when (and ,(end? parser)
(eql ,(this parser) ',x))
,(next parser))
...)
Would you say this is better?
Marcolets ARE hard to debug though =( Do you know a code walker
that can selectively expand a list of macros?
>
> Pascal
>
> --
> My website: http://p-cos.net
> Common Lisp Document Repository: http://cdr.eurolisp.org
> Closer to MOP & ContextL: http://common-lisp.net/project/closer/
From: Pascal Costanza
Subject: Re: Is there a trick so macrolet can't refer to itself?
Date:
Message-ID: <4kmo0nFcgmsqU1@individual.net>
howard yeh wrote:
>> b) It's probably better to model this with functions or even with
>> generic functions because this would be easier to debug, and it's
>> unlikely that you get too much runtime overhead. In general, use macros
>> only when functional abstractions don't work, but only for syntactic
>> abstractions.
>
> Ya. I am actually starting from Peter Siebel's code. It's already using
> generic functions. In the particular case of Baker's parser, using the
> macros allows me to keep most of the code generator functions
> the same. For example, to go from lexer to sexp-parser, I only
> have to specialize the code generator for the sequence grammar.
>
> (and ...
> (when (and ,(end? parser)
> (eql ,(this parser) ',x))
> ,(next parser))
> ...)
>
> Would you say this is better?
What's wrong with something like this?
(defclass parser () ())
(defclass list-parser ()
((elements :accessor list-elements :initarg :elements)))
(defclass vector-parser ()
((elements :accessor vector-elements :initarg :elements)
(index :accessor vector-index :initarg 0)))
(defgeneric current (parser))
(defgeneric end? (parser))
(defgeneric next (parser))
(defmethod current ((parser list-parser))
(first (list-elements parser)))
(defmethod end? ((parser list-parser))
(null (list-elements parser)))
(defmethod next ((parser list-parser))
(pop (list-elements parser)))
(defmethod current ((parser vector-parser))
(svref (vector-elements parser) (vector-index parser)))
(defmethod end? ((parser vector-parser))
(>= (vector-index parser) (length (vector-elements parser))))
(defmethod next ((parser vector-parser))
(incf (vector-index parser)))
...
(and ...
(if (and (end? parser) (eql (current parser) x))
...
(next parser))
...)
> Marcolets ARE hard to debug though =( Do you know a code walker
> that can selectively expand a list of macros?
Nope.
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
> What's wrong with something like this?
>
> (defclass parser () ())
>
> (defclass list-parser ()
> ((elements :accessor list-elements :initarg :elements)))
>
> (defclass vector-parser ()
> ((elements :accessor vector-elements :initarg :elements)
> (index :accessor vector-index :initarg 0)))
>
> (defgeneric current (parser))
> (defgeneric end? (parser))
> (defgeneric next (parser))
>
> (defmethod current ((parser list-parser))
> (first (list-elements parser)))
> (defmethod end? ((parser list-parser))
> (null (list-elements parser)))
> (defmethod next ((parser list-parser))
> (pop (list-elements parser)))
>
> (defmethod current ((parser vector-parser))
> (svref (vector-elements parser) (vector-index parser)))
> (defmethod end? ((parser vector-parser))
> (>= (vector-index parser) (length (vector-elements parser))))
> (defmethod next ((parser vector-parser))
> (incf (vector-index parser)))
>
> ...
> (and ...
> (if (and (end? parser) (eql (current parser) x))
> ...
> (next parser))
> ...)
>
I guess that's good. What do you think of the code described
in the paper? I know it's supposed to be "bad" style.
But it's good in a tortured way.
With modern computing power, Henry Baker's approach
is probably a gratuitous exercise in macro-enabled efficiency,
as the overhead of method dispatching may be ignored.
thanks
From: Pascal Costanza
Subject: Re: Is there a trick so macrolet can't refer to itself?
Date:
Message-ID: <4ko6q2Fd3ia3U1@individual.net>
howard yeh wrote:
>> What's wrong with something like this?
>>
>> (defclass parser () ())
>>
>> (defclass list-parser ()
>> ((elements :accessor list-elements :initarg :elements)))
>>
>> (defclass vector-parser ()
>> ((elements :accessor vector-elements :initarg :elements)
>> (index :accessor vector-index :initarg 0)))
>>
>> (defgeneric current (parser))
>> (defgeneric end? (parser))
>> (defgeneric next (parser))
>>
>> (defmethod current ((parser list-parser))
>> (first (list-elements parser)))
>> (defmethod end? ((parser list-parser))
>> (null (list-elements parser)))
>> (defmethod next ((parser list-parser))
>> (pop (list-elements parser)))
>>
>> (defmethod current ((parser vector-parser))
>> (svref (vector-elements parser) (vector-index parser)))
>> (defmethod end? ((parser vector-parser))
>> (>= (vector-index parser) (length (vector-elements parser))))
>> (defmethod next ((parser vector-parser))
>> (incf (vector-index parser)))
>>
>> ...
>> (and ...
>> (if (and (end? parser) (eql (current parser) x))
>> ...
>> (next parser))
>> ...)
>>
>
> I guess that's good. What do you think of the code described
> in the paper? I know it's supposed to be "bad" style.
> But it's good in a tortured way.
>
> With modern computing power, Henry Baker's approach
> is probably a gratuitous exercise in macro-enabled efficiency,
> as the overhead of method dispatching may be ignored.
I hesitate to judge Henry Baker's coding style because I haven't studied
the paper in detail and don't completely understand its goals. One of
the advantages he mentions is that his abstractions allow for several
different implementations, and maybe that's indeed where macros help in
his case - indeed, syntactic abstractions potentially gives you more
freedom in this respect than functional abstractions. (I am referring to
the third advantage he mentions in his conclusions.)
However, when skimming through his code, I see some macros that could
have been implemented as functions as well, so I am at least skeptical.
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Pascal Costanza <··@p-cos.net> wrote:
+---------------
| I hesitate to judge Henry Baker's coding style because I haven't studied
| the paper in detail and don't completely understand its goals. One of
| the advantages he mentions is that his abstractions allow for several
| different implementations, and maybe that's indeed where macros help in
| his case - indeed, syntactic abstractions potentially gives you more
| freedom in this respect than functional abstractions. (I am referring to
| the third advantage he mentions in his conclusions.)
|
| However, when skimming through his code, I see some macros that could
| have been implemented as functions as well, so I am at least skeptical.
+---------------
Some background context might help...
META-II itself dates back to 1964 (see reference [Schorre64] in Baker's
paper). As Baker said (1991):
The scheme we will describe has been used for at least 27 years,
but is relatively unknown today, because computer science departments
are rightly more interested in teaching theoretically pretty models
like regular and context-free languages, rather than practical
methods that may also be elegant and efficient.
META-II used a BNF-style input format, sort of like YACC but with *both*
the lexer and the syntax-parser/code-generator unified into a single
input specification, unlike the sometimes-awkward Lex/YACC split.
Baker's reader macros & MATCHIT macro allow one to write parsers
that look *very* much like the original META-II style, but entirely
within Lisp! [That is, without having an *external* META-II input file
format that's "compiled" into Lisp source and then loaded into Lisp
to get the lexer/parser/compiler to run.]
The "META" class of compiler-compilers handles most of the common
regular expression forms, is recursive [that is, supports writing
top-down/recursive-descent parsers], and the code is tiny. The parsers
one writes using it are often tiny, too. I used Schorre's "META-II"
back in 1970 on the PDP-10 to write a quick & dirty BLISS compiler
in a single weekend! [It took in BLISS source and output PDP-10
assembler (MACRO-10 source). It was totally unoptimized -- the
generated code was *horribly* inefficient -- but the generated
code ran and gave correct results.]
Unfortunately for those reading Baker's paper, unless you have some
previous exposure to META-II (or the META family) it's hard to
appreciate how closely he's managed to capture the original overall
style -- it's quite amazing!
Of course, if you're not familiar with META, then the heavy use of
reader macros to achieve the resulting terseness of specification
may seem a bit overdone, especially the very large number of reader
macros, which result in something resembling Perl's level of "line
noise"!! One might be tempted to throw all the reader macros away
and use a more "traditional" Lisp style, albeit still with a large
number of macros so as to continue to allow a somewhat "declarative"
coding style. One could certainly do that, although the resulting
grammar specifications might not be nearly as compact as Baker's.
Though the expansion needn't be all *that* bad -- maybe something
similar to the s-expr form of CL-PPCRE, but perhaps with shorter
markers:
$foo ==> (* foo) ; Kleene star (zero or more)
[foo bar] ==> (& foo bar) ; Sequence [a.k.a. PROGN]
{foo bar} ==> (/ foo bar) ; Alternative or union ["pick 1"]
@(digit d) ==> (? (digit d)) ; Satisfies-p [a.k.a. TYPEP]
!(s-expr) ==> (! (s-expr)) ; Emit normal Lisp code
So Baker's first version of PARSE-INTEGER [which is really just
"recognize-integer", he adds the saving of the value later]:
(defun parse-integer (&aux d)
(matchit [{#\+ #\- []} @(digit d) ·@(digit d)]))
could be re-written [still with macros, but no *reader* macros!] as:
(defun parse-integer (&aux d)
(matchit (& (/ #\+ #\- (&))
(? (digit d))
(* (? (digit d))))))
or even expand the MATCHIT macro and the little marker symbols[1]
out completely, though that's starting to get a bit verbose:
(defun parse-integer (&aux d)
(and (or (match #\+) (match #\-) (and))
(match-type digit d)
(not (loop while (match-type digit d)))))
What especially interesting to *me*, at least, is that these sorts
of "lexers" can easily be intermingled with larger, "syntax parser"
elements using top-down/recursive-descent to form full parsers and
code generators. See section "C. CONTEXT-FREE GRAMMARS" in Baker's
paper for a taste of how that works.
Does that address your skepticism somewhat?
-Rob
[1] An earlier draft of this reply used actual named macros
instead of one-character marker symbols, that is, "m&",
"m/", "m?", "m*", etc., but I think MATCHIT can be made
to work [somewhat like LOOP!] with just the bare symbols.
[If not, the prefix "m" could always be put back.]
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
> Though the expansion needn't be all *that* bad -- maybe something
> similar to the s-expr form of CL-PPCRE, but perhaps with shorter
> markers:
>
> $foo ==> (* foo) ; Kleene star (zero or more)
> [foo bar] ==> (& foo bar) ; Sequence [a.k.a. PROGN]
> {foo bar} ==> (/ foo bar) ; Alternative or union ["pick 1"]
> @(digit d) ==> (? (digit d)) ; Satisfies-p [a.k.a. TYPEP]
> !(s-expr) ==> (! (s-expr)) ; Emit normal Lisp code
>
That's what Peter Siebel's interpretation of META is doing. I find
it a more readable specification than Bakers'.
> What especially interesting to *me*, at least, is that these sorts
> of "lexers" can easily be intermingled with larger, "syntax parser"
> elements using top-down/recursive-descent to form full parsers and
> code generators. See section "C. CONTEXT-FREE GRAMMARS" in Baker's
> paper for a taste of how that works.
Siebel's META uses "^" as the return operator to get an annotated
tree parser.
(^ (* "b") #'(lambda (match) (apply #'strcat match)))
Matches ("b" "b" "b"), and returns "bbb".
Over the course of 50 years, why has regexp for sexp never
surfaced (or rather, caught on)? It's certainly easy to write
recursive parser for sexp but it still takes work to define DSLs.
And the parser obsfucates the grammar enough, that a separate
description is necessary. There are list pattern matchers. But even
those with their limited powers are not used very often.
(defun parse-lambda-list (lst)
(match-sexp
;; "^" does capturing.
;; :exp is the entrance grammar... like main()
(:exp ((? &whole (^ :symbol))
(^ (* :symbol))
(? &optional (^ (* :binding)))
(? &key (^ (* :binding)))
(^ (? &allow-other-keys)))
;; "/" is for the alternate grammar
:binding (/ :symbol (:symbol :symbol) (:symbol :symbol :symbol)))
lst
(let ((whole $1)
(required $2)
(optional $3)
(key $4)
(other-keys? $5))
...)))
I am modifying Siebel's META for this purpose. But I am not very good
at it... things like left factoring are still beyond me.
I've heard some legendary lisps of the bygone era had something
called... fsexp?? That can do context-sensitive grammar?? What's the
scoop?
From: Pascal Costanza
Subject: Re: Is there a trick so macrolet can't refer to itself?
Date:
Message-ID: <4kp0phFd04vdU1@individual.net>
Rob Warnock wrote:
>
> Does that address your skepticism somewhat?
>
Yes, it does. Thanks a lot!
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/