I am a CL newbie (probably about 3 months old), so please be
gentle. :) I have read/skimmed through some of the interesting parts
of "The Little Schemer", "Practical Common Lisp", and "OnLisp", so
there's quite a way to go yet...
Here's a newbie question (skip to the bottom if you are not
interested).
As practice (I learn best by doing while reading), I tried to
implement some small "hello world" type applications, and am currently
working on an AST transformer. This is basically a program transformer
that sits behind the typical compiler/parse compiler (I arbitrarily
chose Antlr) and transforms your program tree, so for example, I hope
to translate from Java to Python as an initial goal. I recently had the
following in my code:
First, some example inputs:
sub-tree might look like:
("method" "StringParser" (("String" "s") ("boolean" "y")))
but for now, we restrict our attention to the sub-set of trees that
has no sublists, for example
("method" "method-Name" "type" "one-parameter")
tokens in this case might look like:
("method" name type param)
new-tree might look like:
("method" name param)
; Takes a set rules -- tokens to match to a syntax tree, and the form
of
; the new tree, to use to transform that tree. Returns the function
that does
; the transformation.
(defmacro create-rule (tokens new-tree)
#'(lambda (sub-tree)
(apply-rule tokens sub-tree new-tree)))
; Applies the transformation from "sub-tree" to "new-tree", given that
; it matches the token order specified by "tokens"
(defmacro apply-rule (tokens sub-tree new-tree)
`(let ,(params-list tokens sub-tree)
,(cons 'list new-tree)))
apply-rule might be used as follows:
(apply-rule
("method" name type param)
("method" "method-Name" "type" "one-parameter")
("method" name param))
or as follows:
; Swap order of some tokens
(apply-rule
("kkk" h i j)
("kkk" "aaa" "bbb" "ccc")
("kkk-transformed" j i h))
Changing the tree from
("kkk" "aaa" "bbb" "ccc")
to
("kkk-transformed" "ccc" "bbb" "aaa")
Side-note:
params-list is a function that takes tokens and sub-tree and returns
the form that "let" requires for variable binding.
Inputs to params-list:
tokens -> ("kkk" h i j)
sub-tree -> ("kkk" "aaa" "bbb" "ccc")
Output:
((h "aaa")
(i "bbb")
(j "ccc"))
There's no surprises here with the macro. However, as some of you
might see straight away, create-rule doesn't compile:
CAR: TOKENS is not a list [Condition of type SIMPLE-TYPE-ERROR]
This, it seems, is because macro-expansion time occurs before runtime,
and at that time, we don't know what the subtree is yet. I can see a
few work-arounds for this, (maybe we shouldn't do macros with variable
binding, but use a hash-table for processing the token and
sub-tree). However, it was what I wanted to write, and I feel, is more
natural. I would appreciate any further insights in this area - ways
to work around this, or maybe more elegant ways to do this. Note that I
will be expanding this function in the future (for example, to recurse
on sub-lists etc), so it has to be "elegant" and "not a hack" (hard to
define,
I know)
It's quite amazing really, I started with 50 odd lines of code (and
many examples of tree structures), and manage over time to
reduce/re-phrase my initial problem to the trivial 6 lines above
(granted, it doesn't recurse, it doesn't even work, but the spirit of
the solution is there, sort of). This is what exploration is like I
guess. Nothing like Java or my other ex-favourite languages...
;;; ------------------------------------------
This leads to also to another more fundamental question:
Is there any way we can do macro-expansion at runtime (Of course, I
may be wrong in assuming that this always happens before compile time,
no?)? This naturally leads to first class macros, and I wonder if it is
possible to do this within the present common lisp language... and what
it might involve. I think Paul Graham's Arc is gonna be doing
something like this...
If we have first class macros, what can we do? What sort of powers
will we get (I cannot fathom this)?
Well, sorry for the long post, but I gave you the choice of skipping
the
boring bits, and just read the last speculative bit. Thanks for your
time, and may cons be with you.
Cheers.
On 2005-12-21, senator <···············@gmail.com> wrote:
> I have read/skimmed through some of the interesting parts of "The
> Little Schemer", "Practical Common Lisp", and "OnLisp", so there's
> quite a way to go yet...
> [...]
> ; Takes a set rules -- tokens to match to a syntax tree, and the form of
> ; the new tree, to use to transform that tree. Returns the function that does
> ; the transformation.
What you are doing is called "pattern matching" and there are books,
tutorials, etc. that cover the implementation in detail. I think "On
Lisp" includes an implementation of a simple pattern matcher, as does
SICP. Check out Lecture 4a here:
http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/
"senator" <···············@gmail.com> writes:
> This, it seems, is because macro-expansion time occurs before runtime,
> and at that time, we don't know what the subtree is yet.
This is a big clue you don't need a macro here. A function would be enough.
(defun apply-rule (tokens sub-tree new-tree)
(let ((bindings (params-list tokens sub-tree)))
(mapcar (lambda (k) (cdr (assoc k bindings))) (cdr new-tree))))
(defun create-rule (tokens new-tree)
(lambda (sub-tree)
(apply-rule tokens sub-tree new-tree)))
> Side-note:
> params-list is a function that takes tokens and sub-tree and returns
> the form that "let" requires for variable binding.
> Inputs to params-list:
> tokens -> ("kkk" h i j)
> sub-tree -> ("kkk" "aaa" "bbb" "ccc")
> Output:
> ((h "aaa")
> (i "bbb")
> (j "ccc"))
It's shorter to just give us this params-list function than
paraphrase. I don't understand why you do that...
(defun params-list (tokens sub-tree)
(mapcar (funtion list) (cdr tokens) (cdr sub-tree)))
But actually, we don't need LET bindings, so I'll use CONS, since I
used (CDR (ASSOC ...)) above:
(defun params-list (tokens sub-tree)
(mapcar (function cons) (cdr tokens) (cdr sub-tree)))
Then:
(apply-rule
'("method" name type param)
'("method" "method-Name" "type" "one-parameter")
'("method" name param))
--> ("method-Name" "one-parameter")
and:
(create-rule
'("method" name type param)
'("method" name param))
--> #<FUNCTION :LAMBDA (SUB-TREE) (APPLY-RULE TOKENS SUB-TREE NEW-TREE)>
(funcall (create-rule
'("method" name type param)
'("method" name param))
'("method" "method-Name" "type" "one-parameter"))
("method-Name" "one-parameter")
Now, if what you needed was to generate optimized functions (because
otherwise, I don't see the need for an anonymous function here
either), You could just write this:
(defun create-rule (tokens new-tree)
(compile nil (eval `(lambda (sub-tree)
(destructuring-bind ,(cdr tokens) (cdr sub-tree)
(declare (ignorable ,@(cdr tokens)))
(list ,@(cdr new-tree)))))))
CREATE-RULE
[61]> (create-rule
'("method" name type param)
'("method" name param))
#<COMPILED-FUNCTION NIL> ;
NIL ;
NIL
[62]> (funcall (create-rule
'("method" name type param)
'("method" name param))
'("method" "method-Name" "type" "one-parameter"))
("method-Name" "one-parameter")
The optimizing is in the use of DESTRUCTURING-BIND and LIST, which can
be optimized out by the lisp compiler. It should be O(n) instead of
O(n�) for ASSOC.
> ;;; ------------------------------------------
>
> This leads to also to another more fundamental question:
>
> Is there any way we can do macro-expansion at runtime (Of course, I
> may be wrong in assuming that this always happens before compile time,
> no?)? This naturally leads to first class macros, and I wonder if it is
> possible to do this within the present common lisp language... and what
> it might involve. I think Paul Graham's Arc is gonna be doing
> something like this...
You can use MACROEXPAND and MACROEXPAND-1, but the problem of the
lexical scopes remains: you don't have them anymore at runtime!
> If we have first class macros, what can we do? What sort of powers
> will we get (I cannot fathom this)?
Macros are nothing more than functions taking a sexp as input and
giving a sexp aas output. You don't need to declare this kind of
function as macros for your own sexp->sexp functions. You only need
to declare such a function as macro when you want the _*LISP*_
compiler to ue them to generate your _program_, not your _data_.
A compiler (a translator) is a meta program: it's data is program too.
But when you translate Java to Python, these programs are purely data
for the lisp system. Only your translator is program. So you don't
need macros to transform Java to Python. You only need macros if you
want to transform Lisp to Lisp. (High level Lisp to low level Lisp).
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we. -- Georges W. Bush
Pascal Bourguignon wrote:
> "senator" <···············@gmail.com> writes:
> > This, it seems, is because macro-expansion time occurs before runtime,
> > and at that time, we don't know what the subtree is yet.
>
> This is a big clue you don't need a macro here. A function would be enough.
>
> (defun apply-rule (tokens sub-tree new-tree)
> (let ((bindings (params-list tokens sub-tree)))
> (mapcar (lambda (k) (cdr (assoc k bindings))) (cdr new-tree))))
Yes, that is what I had in mind with the hash-tables, though a simple
associative list is good enough here (better, since it's shorter).
> > Side-note:
> > params-list is a function that takes tokens and sub-tree and returns
> > the form that "let" requires for variable binding.
> > Inputs to params-list:
> > tokens -> ("kkk" h i j)
> > sub-tree -> ("kkk" "aaa" "bbb" "ccc")
> > Output:
> > ((h "aaa")
> > (i "bbb")
> > (j "ccc"))
>
> It's shorter to just give us this params-list function than
> paraphrase. I don't understand why you do that...
I was trying to avoid clutter. Here you go, in all its full ugliness:
By the way, what's the more aesthetic way to indent multi-line
comments? With deep indents, sometimes, my comment looks like: (hope
the indents show up ok)
(blah blah blah (blah blah blah (defun blah ()
"comment here
here
here
and here"
func body)....)
Or is this just incompetence on my part (what Slime function can I use
here?)? Anyway, back to the function:
(defun params-list (tokens subtree)
"Returns a list of tokens matched to subtree.
Strings in tokens are ignored (assumed to match
subtree). Eg: Given tokens = ('match' a b c),
and subtree = ('match' 'hello' 'bye' (inside))
the list ((a 'hello') (b 'bye') (c '(inside)))
is returned. Note that ' is used to denote a
string quote (except for the lone quote for (inside))"
(cond ((null tokens)
'())
((stringp (car tokens))
(params-list (cdr tokens) (cdr subtree)))
(t (cons (list (car tokens) (if (consp (car subtree))
(list 'quote (car subtree))
(car subtree)))
(params-list (cdr tokens) (cdr subtree))))))
There's a couple of other things in there I thought wouldn't be
relevant to the discussion. This looks reasonable for now(not the best
I'm sure), but it will quite likely be modified/deleted as I play
around a bit more. There's sub-lists to consider, and who knows what
else (I'm still exploring the tree syntax from my front-end).
> Then:
>
> (apply-rule
> '("method" name type param)
> '("method" "method-Name" "type" "one-parameter")
> '("method" name param))
> --> ("method-Name" "one-parameter")
Yeah, this works too, and I think I played around like this at one
stage... I wanted macro at first as syntactic sugar (get rid of the
quotes as in set <-> setq). This later got bastardised into the form I
presented before.
**snip**
> Now, if what you needed was to generate optimized functions (because
> otherwise, I don't see the need for an anonymous function here
> either), You could just write this:
>
> (defun create-rule (tokens new-tree)
> (compile nil (eval `(lambda (sub-tree)
> (destructuring-bind ,(cdr tokens) (cdr sub-tree)
> (declare (ignorable ,@(cdr tokens)))
> (list ,@(cdr new-tree)))))))
> CREATE-RULE
> [61]> (create-rule
> '("method" name type param)
> '("method" name param))
> #<COMPILED-FUNCTION NIL> ;
> NIL ;
> NIL
> [62]> (funcall (create-rule
> '("method" name type param)
> '("method" name param))
> '("method" "method-Name" "type" "one-parameter"))
> ("method-Name" "one-parameter")
Now this looks interesting. At this stage (initial exploration), I
won't worry about speed just yet (I'm writing code more often, and that
is taking me much much longer than program compilation/execution
time...). What's with the eval? I've heard all the lore about it's
"badness", but have yet to understand why yet (I'll get there someday,
it's somewhere on my reading list (so many books, so little time...)).
> The optimizing is in the use of DESTRUCTURING-BIND and LIST, which can
> be optimized out by the lisp compiler. It should be O(n) instead of
> O(n²) for ASSOC.
Where is this specified? CLtL? Or does the Hyperspec have anything
about the standard compiler?
>
> You can use MACROEXPAND and MACROEXPAND-1, but the problem of the
> lexical scopes remains: you don't have them anymore at runtime!
>
>
> > If we have first class macros, what can we do? What sort of powers
> > will we get (I cannot fathom this)?
>
> Macros are nothing more than functions taking a sexp as input and
> giving a sexp aas output. You don't need to declare this kind of
> function as macros for your own sexp->sexp functions. You only need
> to declare such a function as macro when you want the _*LISP*_
> compiler to ue them to generate your _program_, not your _data_.
I just might need macros. For now, there doesn't seem to be any reason
other than syntactic "beauty", but I think as I move on to extended
rule forms (EBNF maybe...) or something more, this could start to
require more firepower...
> A compiler (a translator) is a meta program: it's data is program too.
> But when you translate Java to Python, these programs are purely data
> for the lisp system. Only your translator is program. So you don't
> need macros to transform Java to Python. You only need macros if you
> want to transform Lisp to Lisp. (High level Lisp to low level Lisp).
There's an initial stage where I read in the tree-transformation rules
-- I'm still playing with that. This seems similar to the next level
down, where we write the lexical analyser + parser using regexps and
EBNF. The EBNF feeds into the compiler-compiler, which generates (eg C)
code for doing the actual work. Perhaps this could probably happen here
too. Tree-transformation rules in, lisp code out.... I'm an Electrical
Engineer, not Computer Science, so I have no prior experience here
aside from reading some texts. Anyway, I have jumped the gun with that
previous question, so I'll head back to my exploration, and try to
reinvent the wheel, fire, and the arch.
And thanks Adrian,
> What you are doing is called "pattern matching" and there are
> books, tutorials, etc. that cover the implementation in
> detail. I think "On Lisp" includes an implementation of a
> simple pattern matcher, as does SICP. Check out Lecture 4a
> here:
> http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/
I'm at about Chptr 2 :(, so I'll be there soon :). Hopefully, I'll have
something working by the time I read about it, hehe.
Cool stuff, all this.
"senator" <···············@gmail.com> writes:
> By the way, what's the more aesthetic way to indent multi-line
> comments? With deep indents, sometimes, my comment looks like: (hope
> the indents show up ok)
>
> (blah blah blah (blah blah blah (defun blah ()
> "comment here
> here
> here
> and here"
> func body)....)
> Or is this just incompetence on my part (what Slime function can I use
> here?)? Anyway, back to the function:
I write my comment strings like this:
(DEFUN DICHOTOMY (VECTOR VALUE COMPARE &KEY
(START 0) (END (LENGTH VECTOR))
(KEY (FUNCTION IDENTITY)))
"
PRE: entry is the element to be searched in the table.
(<= start end)
RETURN: (values found index order)
POST: (<= start index end)
+-------------------+----------+-------+----------+----------------+
| Case | found | index | order | Error |
+-------------------+----------+-------+----------+----------------+
| x < a[min] | FALSE | min | less | 0 |
| a[i] < x < a[i+1] | FALSE | i | greater | 0 |
| x = a[i] | TRUE | i | equal | 0 |
| a[max] < x | FALSE | max | greater | 0 |
+-------------------+----------+-------+----------+----------------+
"
...)
I use as key:
PRE precondition
POST postcondition
RETURN returned values
DO informal description of the procedure
NOTE something to notice
SEE ALSO references to other functions that might be interesting
URL an url to some specification or documentation
{paramname} description of the parameter {paramname}.
etc.
Well, in CL I should probably turn the PRE and POST into declarations:
(declaration pre post)
(defun ... (...)
"...")
(declare (pre {precondition})
(post {postcondition})
...)
...)
In any case, I assume in theory that the comment strings will be
processed before being presented to the programmer by the IDE. :-)
You could put HTML in them, and expect your IDE to do
(render-html *gui-window* (documentation 'your-function 'function))
(render-html *lynx* (documentation 'your-function 'function))
>> (apply-rule
>> '("method" name type param)
>> '("method" "method-Name" "type" "one-parameter")
>> '("method" name param))
>> --> ("method-Name" "one-parameter")
>
> Yeah, this works too, and I think I played around like this at one
> stage... I wanted macro at first as syntactic sugar (get rid of the
> quotes as in set <-> setq). This later got bastardised into the form I
> presented before.
Note that you don't generally write the quotes, because you have the
lists in variables!
(apply-rule old-pattern expression new-pattern)
If you have to declare a lot of rules, you can always write a
_defining_ macro, for example:
(defmacro defrule (name old-pattern new-pattern ...)
`(progn
(setf (gethash ',name *rules*)
(create-rule old-pattern new-pattern))
...
',name))
> **snip**
>
>> Now, if what you needed was to generate optimized functions (because
>> otherwise, I don't see the need for an anonymous function here
>> either), You could just write this:
>>
>> (defun create-rule (tokens new-tree)
>> (compile nil (eval `(lambda (sub-tree)
>> (destructuring-bind ,(cdr tokens) (cdr sub-tree)
>> (declare (ignorable ,@(cdr tokens)))
>> (list ,@(cdr new-tree)))))))
> [...]
> What's with the eval? I've heard all the lore about it's
> "badness", but have yet to understand why yet (I'll get there someday,
> it's somewhere on my reading list (so many books, so little time...)).
You're right, I forgot that COMPILE can take a lambda expression as
well as a function. I should have written:
(compile nil `(lambda (sub-tree)
(destructuring-bind ,(cdr tokens) (cdr sub-tree)
(declare (ignorable ,@(cdr tokens)))
(list ,@(cdr new-tree)))))
>> The optimizing is in the use of DESTRUCTURING-BIND and LIST, which can
>> be optimized out by the lisp compiler. It should be O(n) instead of
>> O(n�) for ASSOC.
>
> Where is this specified? CLtL? Or does the Hyperspec have anything
> about the standard compiler?
Yes, there's a "minimal compilation" that is specified, but otherwise
nothing is specified about the compiler. It can even be non existent.
This is just what I'd expect when I choose a compiler-based
implementation vs. an interpreter=based one.
--
__Pascal Bourguignon__ http://www.informatimago.com/
"You cannot really appreciate Dilbert unless you read it in the
original Klingon"