I have trolled in google for information about Code Walkers,
and have found some source code.
I would like some theoretical info. about Code Walkers:
1.) How are they implemented.
2.) What do they do. (What kinds of Transformations.)
3.) Are they posible to do in ANSI CL.
4.) If they can't be done in ANSI CL what features does
ANSI CL lack.
5.) Info. about Reflexion & Introspection. I'm curious about
these because I feel that these are powerful programming
paradigms that I have found little info. on.
Are there any books about how to write Code Walkers, in general? in
Lisp/Scheme?
What branch of Comp. Sci. would they fall under: Compilers, Semantics,
Logic., Formal Languages.
Why I am intrested is because I have heard people on this group say that
many intresting things: continuations, backtracking, etc.
require a Code Walker but I have not be able to find into
about writing Code Walkers for Lisp programmers.
I am a Senior in Comp. Sci. & have not heard about Code Walkers in any Comp.
Sci. class I took.
I am curious about what they are; Are they general to CS or Lisp specific.
Is there any algorithms or psudocode that shows how a Code Walker works. I'd
like to be able to make my own--however, I can't find any info. about the
theory of a Code Walker.
I want to know the Theory first; So, when I look at the source code I can
understand what it is trying to do, and make modifications or debug it to
run in my Lisp.
Thanks.
From: Thien-Thi Nguyen
Subject: Re: Code Walker Info. needed (not found on Google)
Date:
Message-ID: <7g8ytcwj1x.fsf@gnufans.net>
"Franz Kafka" writes:
> What branch of Comp. Sci. would they fall under: Compilers, Semantics,
> Logic., Formal Languages.
probably "basics", since walking code is similar to walking data
(actually it's even simpler in some practical respects), and walking
data is one of the very first things people either get hung up on or get
through quickly.
it would be simpler, instead of researching the slangish term "code
walker", to read up a little on "iteration vs recursion" debates. then
you can summarize your findings and post on a website somewhere and fill
in that gap in google...
thi
"Thien-Thi Nguyen" <···@glug.org> wrote in message
···················@gnufans.net...
> "Franz Kafka" writes:
>
> > What branch of Comp. Sci. would they fall under: Compilers, Semantics,
> > Logic., Formal Languages.
>
> probably "basics", since walking code is similar to walking data
> (actually it's even simpler in some practical respects), and walking
> data is one of the very first things people either get hung up on or get
> through quickly.
>
> it would be simpler, instead of researching the slangish term "code
> walker", to read up a little on "iteration vs recursion" debates. then
> you can summarize your findings and post on a website somewhere and fill
> in that gap in google...
>
> thi
I looked for iteration vs. recursion but I couldn't figure out from
there how a "code walker" allows ANSI CL to implement call/cc
like Graham said it could.
Nor could I find any info. about how to add call/cc and/or backtracking
into ANSI CL, or how to transform recursive Lisp funcs. into Iterative ones.
I found that standard discussions:
1.) Recursion is easier to debug.
2.) Iteration is faster.
3.) Some problems only have Recursive solution.
I'd like to find out more about Code Translation--how Lisp
could rewrite Lisp. There is very little info. about how this
works on the INet, how it could be implemented in ANSI CL.
There were a few code walkers on Google, but little info.
about how they work or pseudocode that shows what
a code walker does.
I'd also like some info. about the Reflexive/Introspective features
of Lisp. I have been using Lisp for years, learned it on my own; I
have fould it refered to only in same advanced books. I am looking
for a tutorial about this part of Lisp.
Please help me I've been trolling on Net but have not found much info.
Please give me a list of Books that talk about this part of Lisp. (I have no
Scheme allegries.)
LiSP in Small Pieces was good--I want more about Code Transformations(which
is what Code Walking is about), Reflexion/Introspection, Lisp implemented in
Lisp.
I'd rather read a book about these topics--than just read source code.
Thanks.
"Franz Kafka" <Symbolics _ XL1201 _ Sebek _ Budo _ Kafka @ hotmail . com> writes:
> I looked for iteration vs. recursion but I couldn't figure out from
> there how a "code walker" allows ANSI CL to implement call/cc
> like Graham said it could.
>
> Nor could I find any info. about how to add call/cc and/or backtracking
> into ANSI CL, or how to transform recursive Lisp funcs. into Iterative ones.
Well, you can read about Screamer, a system by Jeffrey Mark Siskind.
This does what you are interested in, namely using a code walker to
transform Lisp code into code which can do roughly the equivalent of
call/cc. It does this by doing CPS tranformation on code. A paper
that explains this somewhat is SCREAMING YELLOW ZONKERS. If you got
through LISP IN SMALL PIECES you should find this paper illuminating.
Anyone interested in "non-deterministic" programming in Lisp should at
least look at Screamer. It is a system that is written the way people
claim lisp systems ought to be written. It takes lisp and extends it
on the language level. It does it in a fairly transparent way using
the introspective capabilities of lisp. It is a good example of what
you can do with a code walker. It also allows constraint-based
programming.
--
Fred Gilham gilham @ csl . sri . com
King Christ, this world is all aleak, / And life preservers there are none,
And waves that only He may walk / Who dared to call Himself a man.
-- e. e. cummings, from Jehovah Buried, Satan Dead
From: Drew McDermott
Subject: Re: Code Walker Info. needed (not found on Google)
Date:
Message-ID: <b9oooq$ac4$1@news.wss.yale.edu>
Franz Kafka wrote:
> I looked for iteration vs. recursion but I couldn't figure out from
> there how a "code walker" allows ANSI CL to implement call/cc
> like Graham said it could.
...
> I'd like to find out more about Code Translation--how Lisp
> could rewrite Lisp. There is very little info. about how this
> works on the INet, how it could be implemented in ANSI CL.
>
> There were a few code walkers on Google, but little info.
> about how they work or pseudocode that shows what
> a code walker does.
>
A code walker is a program that traverses ("walks through") the syntax
tree for another program, collecting data or transforming it in some
way. You can have a code walker for any language for which you have a
way to create syntax trees. It's particularly easy in Lisp because
code is S-expressions (after it's read), and S-expressions _are_ the
syntax trees for Lisp.
If you understand traversing trees recursively, then code walking is
just a special case, a bit more complex than walking the average tree.
The biggest complexity is the need to take variable bindings into
account. For example, if you want your code walker to find all the
free variables in a piece of code, it should be smart enough to tell
that the free variables in
(let ((x (* y (+ y 1))))
(/ x
(let ((y (- y)))
(* y (+ y 1)))))
are (y), because all the occurrences of x are bound, but some
occurrences of y are free.
To handle variable bindings (and other similar issues, which vary from
application to application), your code walker must keep track of the
special actions to be taken on constructs such as 'let'. It might
store the actions in a hash table; (gethash 'let walker-table*) would
return a function for walking through a 'let' expression.
Now, what does this have to do with implementing call/cc or other
complex extensions to Lisp? Sometimes you have an extension that
can't be implemented as a function or macro. And sometimes it occurs
to you that if you could transform the _entire program_ that contains
occurrences of this extension, then you could get it to work. So you
define a macro defun-with-E, where E is the extension, such that
(defun-with-E fun (--params--) --body--)
first transforms the body (and maybe the params) by doing a fancy code
walk, and then defines a function (call it fun-E) that probably has
slightly different calling conventions from the original fun. For
example, if you've made all functions backtrackable, you might require
every function to take a backtrack stack as its last argument; this
becomes an extra argument to every function.
Since you've been careful to use fun only in other functions defined
with defun-with-E, all of this hair can be rendered invisible by
having the code walker convert all occurrences of
(fun --args--)
to
(fun-E --args-- --invisible-stuff--)
e.g.,
(fun-E --args-- backtrack-stack)
or whatever the new calling conventions for fun-E are.
The times when you actually need to write such a revised 'defun' are
vanishingly small, but it has been used to good effect on occasion.
An example is McAllester and Siskind's Screamer, a nondeterministic
Lisp.
> I'd also like some info. about the Reflexive/Introspective features
> of Lisp. I have been using Lisp for years, learned it on my own; I
> have fould it refered to only in same advanced books. I am looking
> for a tutorial about this part of Lisp.
I suppose this refers to things like being able to ask a class what
its slots are. As far as code walking is concerned, there's no
reliable reflection facility that's relevant here. You can't, in
general, ask a function for its source code. Usually you find source
code in files; no "introspection" there.
Someone else may know more about this reflection stuff, or be less
skeptical of it than I am.
-- Drew McDermott
Drew McDermott <··················@at.yale.dot.edu> writes:
> You can't, in general, ask a function for its source code. Usually
> you find source code in files; no "introspection" there.
You can, sort of, with FUNCTION-LAMBDA-EXPRESSION. It doesn't have to
answer, though.
Regards
Henrik
On Mon, 12 May 2003 16:57:06 GMT, "Franz Kafka" <Symbolics _ XL1201 _ Sebek
_ Budo _ Kafka @ hotmail . com> wrote:
> I'd like to find out more about Code Translation--how Lisp
> could rewrite Lisp. There is very little info. about how this
Have a look, for example, at:
A Hacker's Introduction to Partial Evaluation
http://www.lisp-p.org/htdocs/peval/peval.cgi
Paolo
--
Paolo Amoroso <·······@mclink.it>
Paolo Amoroso <·······@mclink.it> writes:
> Have a look, for example, at:
>
> A Hacker's Introduction to Partial Evaluation
> http://www.lisp-p.org/htdocs/peval/peval.cgi
Paolo,
This is interesting! Thanks a lot for posting it. I have been
playing with the code, translating it into Common Lisp and having fun
in the process.
--
Fred Gilham ······@csl.sri.com
Perhaps the greatest damage the American system of education has done
to its children is to teach them that their opinions are relevant
simply because they are their opinions.
On Mon, 12 May 2003 01:47:54 GMT, "Franz Kafka" <Symbolics _ XL1201 _ Sebek
_ Budo _ Kafka @ hotmail . com> wrote:
> Is there any algorithms or psudocode that shows how a Code Walker works. I'd
> like to be able to make my own--however, I can't find any info. about the
> theory of a Code Walker.
This paper by Richard Waters is a good starting point:
Macroexpand-All: An Example of a Simple Lisp Code Walker (in "Some Useful
Lisp Algorithms: Part 2")
http://www.merl.com/reports/TR93-17/
The PCL CLOS implementation comes with another code walker you can study.
See the CMUCL or SBCL sources. You can easily pick up the basics even
without a formal treatment of the topic, and the PCL code walker source
comes with useful comments.
Paolo
--
Paolo Amoroso <·······@mclink.it>
"Paolo Amoroso" <·······@mclink.it> wrote in message
·································@4ax.com...
> On Mon, 12 May 2003 01:47:54 GMT, "Franz Kafka" <Symbolics _ XL1201 _
Sebek
> _ Budo _ Kafka @ hotmail . com> wrote:
>
> > Is there any algorithms or psudocode that shows how a Code Walker works.
I'd
> > like to be able to make my own--however, I can't find any info. about
the
> > theory of a Code Walker.
>
> This paper by Richard Waters is a good starting point:
>
> Macroexpand-All: An Example of a Simple Lisp Code Walker (in "Some
Useful
> Lisp Algorithms: Part 2")
> http://www.merl.com/reports/TR93-17/
>
> The PCL CLOS implementation comes with another code walker you can study.
> See the CMUCL or SBCL sources. You can easily pick up the basics even
> without a formal treatment of the topic, and the PCL code walker source
> comes with useful comments.
>
>
> Paolo
> --
> Paolo Amoroso <·······@mclink.it>
I read the Water's paper--it is intresting, and claims to run
in CLtL2. Now I have to reread 'On Lisp', and LiSP, and
maybe even PAIP.
I'm going 2 be busy for a few nights.
Instead of macroexpanding the code--I am going to
have to add an extra param.
Since functions are Lists this should not prove 2 difficult.
I might also check out Screamer :) I think it has everything,
call/cc, prolog, constraints that I need, I hope it does--because
it says it will take a couple of hours to compile.
I'll wait until I get LispWorks ;) I've heard that it's good, and
has a reasonable Licence too.