Home > Archive > Scheme > January 2006 > SICP Chapter 2, Footnote 3
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
SICP Chapter 2, Footnote 3
|
|
|
| I don't get part of it. The part I don't get has / / around it,
followed by a link to an image of what I think is happening internally
and an explanation of how my internal conception doesn't match the
footnote.
The text:
" Another way to define the selectors and constructor is
(define make-rat cons)
(define numer car)
(define denom cdr)
....Definining selectors and constructors this way is efficient. Instead
of make-rat calling cons, make-rat is cons, so there is only one
procedure called, not two, when make-rate is called. /On the other
hand, doing this defeats debugging aids that trace procedure calls or
put breakpoints on procedure calls. You may want to watch make-rat
being called, but you certainly don't want to watch every call to
cons/.
The part in / / doesn't make sense to me because this won't be a
problem unless you define trace in a really stupid way (sorry: let me
pad this down: "there may be other ways to define trace which are not
considered in this footnote")
My internal conception of what happens when you define one procedure as
another, and trace one of them:
http://www.sundrystuff.net/temp/pointing-to-stuff.png
As you can see, trace would be attached to the procedure name that
points to the data and not the data itself. My understanding of the
footnote seems to imply that trace would get attached to the data, and
I just don't understand why trace would be implemented in that way
(attached to the data), at least not as default behavior - maybe with
some flag toggled, but not by default.
----
I tested the trace in UCB Scheme to see which model it follows, and it
seems to follow my diagram, if you go:
(define foo cons)
(trace foo)
(foo 'a '(b c)) ; this is traced
(cons 'a '(b c)) ; this is not
I also noticed that the explicit trace macro isn't supported in other
implementations, like DrScheme; I don't know DrScheme well enough to
know if there is a way to indicate that only a particular procedure
gets traced, and if so, which model it follows (the footnote model or
the UCB Scheme model). That might be an interesting research point for
anyone who knows DrScheme better.
| |
| Max Hailperin 2006-01-22, 10:00 pm |
| "H." <hbe123@gmail.com> writes:
> ... there may be other ways to define trace which are not
> considered in this footnote...
Correct.
....
> As you can see, trace would be attached to the procedure name that
> points to the data and not the data itself. My understanding of the
> footnote seems to imply that trace would get attached to the data, and
> I just don't understand why trace would be implemented in that way
> (attached to the data), at least not as default behavior - maybe with
> some flag toggled, but not by default....
Among other things, tracing by mutating the actual procedure object,
rather than by changing the name binding to refer to a different
procedure object, is the traditional approach in compiled language
implementations. This includes non-Scheme systems, such as using gdb
to debug a compiled C program. Once a compiler gets done with a
program, a call to procedure foo does not generally involve looking up
the symbol "foo" in an symbol table or environment. Instead, it just
involves jumping to whatever address contains the first instruction of
the compiled code of he procedure. As such, if you want to trace that
procedure, the debugger replaces the first instruction. (There are
fancier approaches that don't involve modifying the code, such as
setting a special CPU "watchpoint" register to trap attempts to
execute from that address. The effect is the same, though: the trace
is on the code address, not the name.) -max
| |
|
|
> Once a compiler gets done with a
> program, a call to procedure foo does not generally involve looking up
> the symbol "foo" in an symbol table or environment. Instead, it just
> involves jumping to whatever address contains the first instruction of
> the compiled code of he procedure.
This definitely seems more efficient for running a program, but I
thought that debugging tools would purposefully be less efficient in
order to be more powerful. ( Alas -- I should take a compilers class so
that I have a clue and am not just spouting stuff out at the novice
level. Next year this time maybe.)
> As such, if you want to trace that
> procedure, the debugger replaces the first instruction. (There are
> fancier approaches that don't involve modifying the code, such as
> setting a special CPU "watchpoint" register to trap attempts to
> execute from that address. The effect is the same, though: the trace
> is on the code address, not the name.)
But to me, it seems like comparing apples to oranges, in that C (as far
as I understand the language), one can't throw around procedure data in
the same way that it's possible to do in Scheme.
For instance, I didn't think you could define a procedure/function:
void printFoo()
{
printf("foo");
}
and then assign this data to another procedure:
showMeTheFoo = printFoo;
I could imagine going:
void showMeTheFoo()
{
printFoo();
}
but this seems like another thing. So would there actually be an
apples-to-apples comparable situation in C?
| |
| Lauri Alanko 2006-01-22, 10:00 pm |
| In article <1137971747.672637.300120@g44g2000cwa.googlegroups.com>,
H. <hbe123@gmail.com> wrote:
> For instance, I didn't think you could define a procedure/function:
>
> void printFoo()
> {
> printf("foo");
> }
>
> and then assign this data to another procedure:
>
> showMeTheFoo = printFoo;
Certainly you can. C has function pointers:
void (*showMeTheFoo)() = printFoo;
What you can't do in C is creating inner functions that capture local
variables. So the number of functions in a C program is always fixed
at compile time.
Regarding your original question, note that a procedure can well be
called without using its name directly.
(define (foo callback)
.... (callback) ...)
(define (my-func) ...)
(trace my-func)
(foo my-func)
If we want to see all the places where my-func is called, the tracing
must also be activated from inside foo. This is much easier to
accomplish if the my-func _procedure_ is specially tagged instead of
the variable that is bound to it.
Lauri
| |
|
|
> Regarding your original question, note that a procedure can well be
> called without using its name directly.
>
> (define (foo callback)
> .... (callback) ...)
>
> (define (my-func) ...)
> (trace my-func)
> (foo my-func)
>
> If we want to see all the places where my-func is called, the tracing
> must also be activated from inside foo. This is much easier to
> accomplish if the my-func _procedure_ is specially tagged instead of
> the variable that is bound to it.
That's a good point. I tested that explicitly in UCB Scheme after
reading your post and would guess that it's doing something more
sophisticated and harder to implement since it behaves as I expect and
want it to..
(define combine cons)
(define (dummy-test fn val1 val2)
(fn val1 (fn val2 '())))
STk>(trace combine)
okay
STk>(dummy-test cons 1 2)
(1 2)
STk>(dummy-test combine 1 2)
[4 lines of trace output]
(1 2)
The SICP footnote may not have been accounting for these types of
implementations. I'm glad, however, that UCB Scheme works in this
fashion; it makes my life easier. :-)
| |
| Max Hailperin 2006-01-22, 10:00 pm |
| "H." <hbe123@gmail.com> writes:
>
> That's a good point. I tested that explicitly in UCB Scheme after
> reading your post and would guess that it's doing something more
> sophisticated and harder to implement since it behaves as I expect and
> want it to..
>
> (define combine cons)
> (define (dummy-test fn val1 val2)
> (fn val1 (fn val2 '())))
>
> STk>(trace combine)
> okay
> STk>(dummy-test cons 1 2)
> (1 2)
> STk>(dummy-test combine 1 2)
> [4 lines of trace output]
> (1 2)
>
> The SICP footnote may not have been accounting for these types of
> implementations. I'm glad, however, that UCB Scheme works in this
> fashion; it makes my life easier. :-)
No, this doesn't require anything sophisticated or hard to implement.
(In fact, the hypothetical special tagging of the variable would be
the sophisticated or hard to implement option.)
All that is needed is for trace to be a macro such that
(trace combine)
expands into something like
(set! combine (make-traced-version-of combine))
Then when you pass combine into dummy-test, you are passing in the
traced version. (I leave the definition of make-traced-version-of as
an exercise. It can be a perfectly garden variety Scheme procedure.)
A case where the approach of having trace mutate a procedure would
produce quite different results would be
(define combine cons)
(define procedures (list combine cons))
(trace combine)
(map (lambda (proc n) (proc n 2))
procedures
'(0 1))
In this example, the version where trace is a macro, as shown above,
would produce no tracing output at all, because after (trace combine)
is done, combine is not evaluated at all, so the new procedure (the
traced version) is never used.
By contrast, the version where trace is a special procedure that
mutates other procedures would produce two sets of tracing output,
once showing the consing (a.k.a. combining) of 0 and 2, the other
showing the consing of 1 and 2.
What many people would like to have is one set of tracing output,
showing the combining of 0 and 2 but not the consing of 1 and 2. As
explained above, neither of the two tracing approaches will achieve
this. But if you change the definition of combine to
(define combine (lambda (x y) (cons x y)))
then the procedure-mutating trace will produce the single set of
tracing output, whereas the macro version will still produce no
output. -max
| |
|
|
> No, this doesn't require anything sophisticated or hard to implement.
> (In fact, the hypothetical special tagging of the variable would be
> the sophisticated or hard to implement option.)
I thought that the example I gave was indicative of some kind of
tagging of the variable name, otherwise every call to both cons and
combine would lead to trace output, but instead, only the one which was
being explicitly traced was showing trace output.
How would my example behave differently if there were "hypothetical
special tagging of the variable"?
| |
| Max Hailperin 2006-01-23, 3:58 am |
| "H." <hbe123@gmail.com> writes:
>
> I thought that the example I gave was indicative of some kind of
> tagging of the variable name, otherwise every call to both cons and
> combine would lead to trace output, but instead, only the one which was
> being explicitly traced was showing trace output.
That phenomenon is explained more simply, as I indicated. Executing
(set! combine (make-traced-version-of combine))
leads to combine being a name for a different procedure than it was a
name for before, and so in particular a different procedure than
cons.
(Incidentally, this macro expansion may be a bit misleading. The
make-traced-version-of procedure would be able to create a procedure
that writes some tracing output on invocation and return, but that
output wouldn't be able to contain the name of the traced procedure,
at least not without going outside R5RS. A better expansion would be
(set! combine (make-traced-version-of combine 'combine))
so that make-traced-version-of has the name available.)
> How would my example behave differently if there were "hypothetical
> special tagging of the variable"?
Wouldn't you then be getting tracing output from (combine 1 2) but not
from (dummy-test combine 1 2)? -max
|
|
|
|
|