Equality, Assignment and The Emperor's New Clothes
bobu...@yahoo.com
"Programming languages should be designed not by piling feature on top
of feature .."
However when I come to deciding if two object are equal I have to learn
about
eq? eqv? equal? and type specific like char=?, string=?, =, ..
Many of these or not easy to understand. In R5RS, three pages or used
just to explain eqv?.
For declaring variables and assigning values to them several constructs
are used
define, let, let*, letrec, named let
They are not easy to understand. To get some feeling for them you must
translate them into underlying lambda expressions which are not so easy
to analyze themeselves.
Now people who wrote R5RS are smart, much smarter than me. How come
that such difficult constructs are allowed for seemingly simple things.
The complexity in assignment and equality test is *not* an a priori
difficulty since they are not that hard to understand in other
languages.
If there are some people reading this who have discussed R5RS, have you
the same feeling as I that this unneccessary complicated, or am I
seeing ghosts in broad daylight?
(I'm not saying that I have any good alternative, but when simple
things in my own work start to get complicated I usually go back to the
foundations themeselves and try to figure out the source of these
difficulties).
Bob
Kjetil S. Matheussen
> In the introduction to R5RS the philosphy behind Scheme is stated
>
> "Programming languages should be designed not by piling feature on top
> of feature .."
>
> However when I come to deciding if two object are equal I have to learn
> about
>
> eq? eqv? equal? and type specific like char=?, string=?, =, ..
>
> Many of these or not easy to understand. In R5RS, three pages or used
> just to explain eqv?.
>
I guess there are performance issues regarding these. You can make an
operator called similar? or something that checks the objects types, and
then choose the appropriate testing-function. common lisp has functions
like that.
> For declaring variables and assigning values to them several constructs
> are used
>
> define, let, let*, letrec, named let
>
I can agree about this. The good thing is, though, that you'll get used
to define, let, let*, letrec, named let, _and letrec*_ after using them,
and in a while you'll probably find your own style you feel
comfortable with.
However, I like some of the ideas for the arc language:
http://www.paulgraham.com/ilc03.html
> They are not easy to understand. To get some feeling for them you must
> translate them into underlying lambda expressions which are not so easy
> to analyze themeselves.
>
Uh, that doesn't sound very easy. At least not to me. :-)
If I were you, I would experiment instead of analyze.
> Now people who wrote R5RS are smart, much smarter than me. How come
> that such difficult constructs are allowed for seemingly simple things.
> The complexity in assignment and equality test is *not* an a priori
> difficulty since they are not that hard to understand in other
> languages.
>
Well, you don't have to understand eqv? at least... Not everyone uses it.
> If there are some people reading this who have discussed R5RS, have you
> the same feeling as I that this unneccessary complicated, or am I
> seeing ghosts in broad daylight?
>
You'll get used to it. :-)
You should look at macros. By using macros you can define the language to
be as convenient and uncomplicated as you want.
> (I'm not saying that I have any good alternative, but when simple
> things in my own work start to get complicated I usually go back to the
> foundations themeselves and try to figure out the source of these
> difficulties).
>
You can also work around them. Find a solution, and in a while you'll
understand the reason for the problem as well.
--
Pascal Bourguignon
You haven't read the paper, whose URL I gave you, in this message:
http://groups.google.com/group/comp.lang.scheme/browse_frm/thread/201fd2d0723731c5/1e468fff53f447ac?lnk=st&q=%22http%3A%2F%2Fwww.nhplace.com%2Fkent%2FPS%2FEQUAL.html%22+group%3Acomp.lang.scheme+author%3APascal+author%3ABourguignon&rnum=1&hl=en#1e468fff53f447ac
have you?
I wonder why I bother...
http://www.nhplace.com/kent/PS/EQUAL.html
--
__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
bobu...@yahoo.com
http://www.nhplace.com/kent/PS/EQUAL.html and
http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-9.html...
I've read the second one but missed the first one. I'm reading it now
:)
Bob
Lauri Alanko
<bobu...@yahoo.com> wrote:
> For declaring variables and assigning values to them several constructs
> are used
>
> define, let, let*, letrec, named let
>
> They are not easy to understand. To get some feeling for them you must
> translate them into underlying lambda expressions which are not so easy
> to analyze themeselves.
No, translation to lambda is only useful for formal reasoning about
the language. Informally, these are pretty simple to grok:
(let ((x1 e1) (x2 e2)) body1 body2)
Evaluate the expressions e1 and e2 in some unspecified order, then
bind their values to the variables x1 and x2 and evaluate body1 and
body2 (in this order) under these bindings, and return the value of
body2.
(let* ((x1 e1) (x2 e2)) body1 body2)
In sequence, evaluate e1, bind its value to x1, then evaluate e2, bind
its value to x2, then evaluate body1 and body2 and return the value of
the latter.
(letrec ((x1 e1) (x2 e2)) body1 body2)
Create new bindings for x1 and x2 (with initially unspecified values),
evaluate e1 and e2 (in some order) and assign their values to x1 and
x2. Then evaluate body1 and body2.
(let loop ((x1 e1) (x2 e2)) body1 body2)
All right, this is easiest to grasp as a transformation:
(letrec ((loop (lambda (x1 x2) body1 body2)))
(loop e1 e2))
I do kind of agree that this is a bit too complicated. Personally, I
think that all of let, let* and letrec could in everyday coding be
replaced by letrec* without any ill effects. But this touches on
evaluation order issues, which is rather a hot topic, so I won't say
more here. :)
Lauri
bobu...@yahoo.com
letrec I've seen. However I have some minor questions.
Lauri Alanko wrote:
> Create new bindings for x1 and x2 (with initially unspecified values),
> evaluate e1 and e2 (in some order) and assign their values to x1 and
> x2. Then evaluate body1 and body2.
What does "Create new bindings for x1 and x2 (with initially
unspecified values)" mean? Does it mean to allocate memory to x1 and
x2.
Does "(in some order)" mean "in an "unspecified order"?
> (letrec ((loop (lambda (x1 x2) body1 body2)))
> (loop e1 e2))
dioesn't seem to follow the required syntax
(letrec ((v1 e1) (v2 e2)) <body>)
??
> replaced by letrec* without any ill effects.
What is letrec* is it some new kind of construct?
bobu...@yahoo.com
with
--- snip ---
"Why is there no generic COPY function?'' Common Lisp programmers often
ask this question.
This glossary entry from dpANS Common Lisp [CL93] provides some useful
background information and a brief rationale for the absence of a
generic COPY function:
copy n.
1. (of a cons C) a fresh cons with the same car and cdr as C.
2. (of a list L) a fresh list with the same elements as L..
(Only the list structure is fresh; the elements are the same.) See the
function copy-list.
3. (of an association list A with elements Ai) a fresh list B
with elements Bi, each of which is nil if Ai is nil, or else a copy of
the cons Ai. See the function copy-alist.
4. (of a tree T) a fresh tree with the same leaves as T. See the
function copy-tree.
5. (of a random state R) a fresh random state that, if used as
an argument to the function random would produce the same series of
``random'' values as R would produce.
6. (of a structure S) a fresh structure that has the same type
as S, and that has slot values, each of which is the same as the
corresponding slot value of S.
(Note that since the difference between a cons, a list, and a tree
is a matter of ``view'' or ``intention,'' there can be no
general-purpose function which, based solely on the type of an object,
can determine which of these distinct meanings is intended. The
distinction rests solely on the basis of the text description within
this document. For example, phrases like ``a copy of the given list''
or ``copy of the list x'' imply the second definition.)
--- snip ---
I've read this four times and I still don't understand it.
An object A is defined in the memory. No matter how complicated the
object A is I can make a copy B of it in some other part of memory
(provided that I don't require that A and B share something). I can do
this for list, for trees for everything, so why is a generic copy
procedure impossible?
In the 6 paragraphs above what does it mean when they say a thing like
"2. (of a list L) a fresh list with the same elements as L.. (Only the
list structure is fresh; the elements are the same.)"
Do they mean that the original list A and the new list B share the
elements? If that's the meaning, then I wouldn't call object B a "copy
of A" but something else. If two Siamese twins share the body but have
different heads I would'nt call the first twin a copy of the other (as
I might say for two one-egg twins).
And what is the meaning of
"Note that since the difference between a cons, a list, and a tree is a
matter of "view'' or "intention,'' there can be no general-purpose
function which, based solely on the type of an object, can determine
which of these distinct meanings is intended."
Is it that a list can be viewed as a list or as a cons or as a tree
and that depending on which "view" you choose the copy procedure should
somehow be different?
(I feel silly asking all these questions, but ..)
Bob
William D Clinger
> However when I come to deciding if two object are equal I have to learn
> about
>
> eq? eqv? equal? and type specific like char=?, string=?, =, ..
The most basic of these is eqv?
The eq? procedure is just a somewhat broken version of eqv?
that some people like to use because it's faster. You can
always use eqv? instead, and I recommend that, especially
to those new to Scheme.
The eqv? procedure tells you whether two values are the same
for all practical purposes, but sometimes you want to know
whether they are the same for some particular purpose, not
for all practical purposes. Thus s1 and s2 might be two
different strings, and this difference would matter if you
were mutating one of them, but you might want to know
whether s1 and s2 happen to contain the same characters
at this moment. The string=? procedure tells you that.
What if you want to know whether two strings contain the
same characters, but you want to regard upper and lower
case characters (e.g. H and h) as the same character?
The string-ci=? procedure tells you that.
The numbers 4 and 4.0 are different in Scheme, because
4 is exact and 4.0 is inexact, so the eqv? predicates says
they aren't the same. You might want to ignore this difference,
however, and ask whether their difference is zero. The =
predicate tells you that.
And so on for most of the other equality predicates. The
equal? predicate is an oddball, however. It tries to guess
what kind of differences might matter to you, and returns
its answer based on its guess. You have to be careful
when using the equal? predicate, not only because it may
guess wrong but also because it may go into an infinite
loop and never return.
I won't claim that Scheme's various equality predicates
were particularly well designed, but it is an inescapable
fact of mathematical reality and human psychology that
no single equality predicate will always correspond to
the distinctions that are important in the programmer's
head. Hence any language will need multiple equality
predicates.
Will
Lauri Alanko
William D Clinger <cesu...@yahoo.com> wrote:
> The eq? procedure is just a somewhat broken version of eqv?
> that some people like to use because it's faster.
Actually, I use it because it's shorter.
Lauri
Ulrich Hobelmann
> The eq? procedure is just a somewhat broken version of eqv?
> that some people like to use because it's faster. You can
> always use eqv? instead, and I recommend that, especially
> to those new to Scheme.
No we don't (the performance is a nice side effect, though). I use eq?
because it's concise and because it shows that I only want to ever
compare symbols or objects for identity.
If I want to compare numbers, I use =. I've NEVER ever used eqv? and in
fact I don't know in what situations you could want to check for object
identity OR for number equality. Those two are totally different and
occur in totally different situations (in my programs at least).
--
The problems of the real world are primarily those you are left with
when you refuse to apply their effective solutions.
Edsger W. Dijkstra
Pascal Bourguignon
> The referenced article http://www.nhplace.com/kent/PS/EQUAL.html begins
> with
>
> --- snip ---
> "Why is there no generic COPY function?'' Common Lisp programmers often
> ask this question.
>
> This glossary entry from dpANS Common Lisp [CL93] provides some useful
> background information and a brief rationale for the absence of a
> generic COPY function:
Just write what is described:
> copy n.
>
> 1. (of a cons C) a fresh cons with the same car and cdr as C.
(define (copy-cons object)
(if (atom? object)
object
(cons (car object) (cdr object))))
> 2. (of a list L) a fresh list with the same elements as L..
> (Only the list structure is fresh; the elements are the same.) See the
> function copy-list.
(define (copy-list object)
(if (null? object)
object
(cons (car object) (copy-list (cdr object)))))
> 3. (of an association list A with elements Ai) a fresh list B
> with elements Bi, each of which is nil if Ai is nil, or else a copy of
> the cons Ai. See the function copy-alist.
(define (atom? object)
(not (pair? object)))
(define (copy-alist object)
(cond
((atom? object) object)
((atom? (car object)) (cons (car object) (copy-alist (cdr object))))
(else (cons (cons (car object) (copy-list (cdr object)))
(copy-alist (cdr object))))))
> 4. (of a tree T) a fresh tree with the same leaves as T. See the
> function copy-tree.
(define (copy-tree object)
(if (atom? object)
object
(cons (copy-tree (car object)) (copy-tree (cdr object)))))
> 5. (of a random state R) a fresh random state that, if used as
> an argument to the function random would produce the same series of
> ``random'' values as R would produce.
> 6. (of a structure S) a fresh structure that has the same type
> as S, and that has slot values, each of which is the same as the
> corresponding slot value of S.
Here is a function that will help us see the effect of the various
copying functions defined above:
(define (compare-conses a b)
(cond ((atom? a) (eq? a b))
((atom? b) #f)
((eq? a b))
(else (cons (compare-conses (car a) (car b))
(compare-conses (cdr a) (cdr b))))))
(define foo '((a . 1) () (b . (2 3 4)) ((c . d) . (5 6 7))))
(map (lambda (copy)
(newline)
(display (car copy))(newline)
(display foo)(newline)
(let ((c ((cdr copy) foo)))
(display c)(newline)
(display (compare-conses foo c)) (newline)))
(list (cons 'copy-cons copy-cons)
(cons 'copy-list copy-list)
(cons 'copy-alist copy-alist)
(cons 'copy-tree copy-tree)))
prints:
COPY-CONS
((A . 1) () (B 2 3 4) ((C . D) 5 6 7))
((A . 1) () (B 2 3 4) ((C . D) 5 6 7))
(#T . #T)
COPY-LIST
((A . 1) () (B 2 3 4) ((C . D) 5 6 7))
((A . 1) () (B 2 3 4) ((C . D) 5 6 7))
(#T #T #T #T . #T)
COPY-ALIST
((A . 1) () (B 2 3 4) ((C . D) 5 6 7))
((A . 1) () (B 2 3 4) ((C . D) 5 6 7))
((#T . #T) #T (#T #T . #T) (#T #T . #T) . #T)
COPY-TREE
((A . 1) () (B 2 3 4) ((C . D) 5 6 7))
((A . 1) () (B 2 3 4) ((C . D) 5 6 7))
((#T . #T) #T (#T #T #T #T . #T) ((#T . #T) #T #T #T . #T) . #T)
1- note how all the copies are displayed equally: the scheme printer
doesn't distinguish them.
2- note how the result of compare-conses is different for each copy
function. A #T means that the subtree is identical, the same.
In the case of copy-cons, only one new cons is allocated.
In the case of copy-list, a new cons for each element in the list
is allocated.
In the case of copy-alist, two new conses for each associations in
the a-list are allocated.
In the case of copy-tree, a new cons for all the conses of the tree
are allocated.
All these copies of conses either refer the same objects in their
car and/or cdr as their originals, or refer new copies of these
objects.
In Common Lisp we could get this output:
COPY-CONS
((#1=(A . 1) . #2=(NIL (B 2 3 4) ((C . D) 5 6 7)))
(#1# . #2#))
(T . T)
COPY-LIST
((#1=(A . 1) NIL #2=(B 2 3 4) #3=((C . D) 5 6 7))
(#1# NIL #2# #3#))
(T T T T . T)
COPY-ALIST
(((A . 1) NIL (B 2 . #1=(3 4)) (#2=(C . D) 5 . #3=(6 7)))
((A . 1) NIL (B 2 . #1#) (#2# 5 . #3#)))
((T . T) T (T T . T) (T T . T) . T)
COPY-TREE
(((A . 1) NIL (B 2 3 4) ((C . D) 5 6 7))
((A . 1) NIL (B 2 3 4) ((C . D) 5 6 7)))
((T . T) T (T T T T . T) ((T . T) T T T . T) . T)
#1= identifies an object number 1
#1# is printed where this very same object number 1 is also present.
(The numbers restart from 1 for each copy function).
Notice how there's no common part (but the atoms) with COPY-TREE,
while all the elements in the list copied by copy-list are also in the
original.
VERY IMPORTANT:
+-------------------------------------------------------------------------+
| (Note that since the difference between a cons, a list, and a tree |
| is a matter of ``view'' or ``intention,'' there can be no |
| general-purpose function which, based solely on the type of an object, |
| can determine which of these distinct meanings is intended. The |
| distinction rests solely on the basis of the text description within |
| this document. For example, phrases like ``a copy of the given list'' |
| or ``copy of the list x'' imply the second definition.) |
+-------------------------------------------------------------------------+
> --- snip ---
>
> I've read this four times and I still don't understand it.
>
> An object A is defined in the memory. No matter how complicated the
> object A is I can make a copy B of it in some other part of memory
> (provided that I don't require that A and B share something). I can do
> this for list, for trees for everything, so why is a generic copy
> procedure impossible?
Because _procedures_ work on data, not on information.
Procedures work mechanically on the _form_ of the data, not on what the data is.
Note how the functions copy-cons, copy-list, copy-alist and copy-tree
above all work on the same type of objects: conses. Why one would you
choose?
Imagine I define an object as cons whose car is a class, and cdr a
list of fields. The method table would be implemented as an a-list of
method names and lambda expressions.
(define account-class '(
; method table:
( (withdraw . (lambda (amount) ...))
(cash-in . (lambda (amount) ...))
...)
; list of instance fields:
( iban currency debit credit owner )
; other class stuff:
...))
(define person-class '( ( (change-address . (lambda (newaddress ...))))
( first-name name country ...)
...))
(define myself (cons person-class
(list "Pascal" "Bourguignon" "Spain")))
(define account-instance (cons account-class
(list "ES01 2345 7890 1234 5678 9012 34"
"EUR" 0 1000.00 myself)))
Now, imagine the bank runs a concurse and I win the first prize which
consists in doubling my accounts, creating new accounts with the same
amounts as my existing accounts. How will then copy the
account-instance object? If you ask the lisp printer, it will only
show lists:
account-instance -->
((((withdraw lambda (amount) |...|) (cash-in lambda (amount) |...|) |...|)
(iban currency debit credit owner) |...|)
"ES01 2345 7890 1234 5678 9012 34" "EUR" 0 1000.0
((((change-address lambda (newaddress |...|))) (first-name name country |...|)
|...|)
"Pascal" "Bourguignon" "Spain"))
Should we copy-tree it? No because they don't clone me! And they
don't clone the class of account, neither the classes of account or of
person. Only "THE account" must be copied, not the structures it
refers like the classes and the person.
Even the strings such as "EUR" don't need to be duplicated. These
strings are constant literals, and there's no need to copy them, both
account can refer the same string object.
Unfortunately, there is no general copy function that would be able to
know what car and what cdr must be copied and what mustn't.
You must design for each kind of object, how to copy it, therefore,
how to compare it.
In the case of an account-instance, we'd have:
(define (copy-account instance)
(cons ; make a new instance
(car instance) ; don't copy the class,
; just keep a reference to the original class
(list (make-new-account-number) ; don't copy the account number,
; but make a new one!
(second (cdr instance)) ; keep a reference to the devise
(third (cdr instance)) ; copy or keep a reference to debit
; it doesn't matter since it's immutable
(fourth (cdr instance)) ; copy or keep a reference to credit
; it doesn't matter since it's immutable
(fifth (cdr instance)) ; keep a reference to the owner
)))
> In the 6 paragraphs above what does it mean when they say a thing like
>
> "2. (of a list L) a fresh list with the same elements as L.. (Only the
> list structure is fresh; the elements are the same.)"
>
> Do they mean that the original list A and the new list B share the
> elements? If that's the meaning, then I wouldn't call object B a "copy
> of A" but something else. If two Siamese twins share the body but have
> different heads I would'nt call the first twin a copy of the other (as
> I might say for two one-egg twins).
That's what we call a shallow-copy. But between a shallow-copy, and a
very-deep-copy, there are all nuances of depth of copy.
> And what is the meaning of
>
> "Note that since the difference between a cons, a list, and a tree is a
> matter of "view'' or "intention,'' there can be no general-purpose
> function which, based solely on the type of an object, can determine
> which of these distinct meanings is intended."
>
> Is it that a list can be viewed as a list or as a cons or as a tree
> and that depending on which "view" you choose the copy procedure should
> somehow be different?
Yes. See the Diagrams: below. The same data:
(define bar '((A . 1) (B 2 3) ((C . D) 5 6)))
is displayed under the form of cons diagrams:
+---+---+
|car|cdr|-->
+---+---+
|
v
after being copied as a cons, a list, an alist, or a tree.
Can you see a difference?
There's none other than what conses are considered to belong to the
data structure.
- only the topleftmost in the case of a CONS,
- only the top row in the case of a LIST,
- only the top row and the first conses referenced by the CAR of the
top row, and their CARs in the case of an A-LIST,
- all the conses in the case of a TREE.
Consider a rock about 0.5 m x 0.5 m x 0.5 m with the top coarsely
flat and horizontal.
What is it?
Could be a meteorite.
Could be some valuable piece of iron mineral.
Could be an anchor: just attach a rope to it and drop it into the lake!
Could be a chair: sit down on it!
Could be a $1,000,000.00 sculpture.
It could be anything you want. What imports is how you consider it.
> (I feel silly asking all these questions, but ..)
They are important questions.
Diagrams:
[344]> (mapc (lambda (f)
(terpri)
(princ (COM.INFORMATIMAGO.COMMON-LISP.CONS-TO-ASCII:DRAW-LIST
(funcall f bar) :title (string f))))
'(identity copy-cons copy-list copy-alist copy-tree))
+-----------------------------------------------------------+
| IDENTITY |
| |
| +---+---+ +---+---+ +---+---+ |
| | * | * |-->| * | * |-->| * |NIL| |
| +---+---+ +---+---+ +---+---+ |
| | | | |
| | | v |
| | | +---+---+ +---+---+ +---+---+ |
| | | | * | * |-->| * | * |-->| * |NIL| |
| | | +---+---+ +---+---+ +---+---+ |
| | | | | | |
| | | | v v |
| | | | +---+ +---+ |
| | | | | 5 | | 6 | |
| | | | +---+ +---+ |
| | | v |
| | | +---+---+ +---+ |
| | | | * | * |-->| D | |
| | | +---+---+ +---+ |
| | | | |
| | | v |
| | | +---+ |
| | | | C | |
| | | +---+ |
| | v |
| | +---+---+ +---+---+ +---+---+ |
| | | * | * |-->| * | * |-->| * |NIL| |
| | +---+---+ +---+---+ +---+---+ |
| | | | | |
| | v v v |
| | +---+ +---+ +---+ |
| | | B | | 2 | | 3 | |
| | +---+ +---+ +---+ |
| v |
| +---+---+ +---+ |
| | * | * |-->| 1 | |
| +---+---+ +---+ |
| | |
| v |
| +---+ |
| | A | |
| +---+ |
+-----------------------------------------------------------+
+-----------------------------------------------------------+
| COPY-CONS |
| |
| +---+---+ +---+---+ +---+---+ |
| | * | * |-->| * | * |-->| * |NIL| |
| +---+---+ +---+---+ +---+---+ |
| | | | |
| | | v |
| | | +---+---+ +---+---+ +---+---+ |
| | | | * | * |-->| * | * |-->| * |NIL| |
| | | +---+---+ +---+---+ +---+---+ |
| | | | | | |
| | | | v v |
| | | | +---+ +---+ |
| | | | | 5 | | 6 | |
| | | | +---+ +---+ |
| | | v |
| | | +---+---+ +---+ |
| | | | * | * |-->| D | |
| | | +---+---+ +---+ |
| | | | |
| | | v |
| | | +---+ |
| | | | C | |
| | | +---+ |
| | v |
| | +---+---+ +---+---+ +---+---+ |
| | | * | * |-->| * | * |-->| * |NIL| |
| | +---+---+ +---+---+ +---+---+ |
| | | | | |
| | v v v |
| | +---+ +---+ +---+ |
| | | B | | 2 | | 3 | |
| | +---+ +---+ +---+ |
| v |
| +---+---+ +---+ |
| | * | * |-->| 1 | |
| +---+---+ +---+ |
| | |
| v |
| +---+ |
| | A | |
| +---+ |
+-----------------------------------------------------------+
+-----------------------------------------------------------+
| COPY-LIST |
| |
| +---+---+ +---+---+ +---+---+ |
| | * | * |-->| * | * |-->| * |NIL| |
| +---+---+ +---+---+ +---+---+ |
| | | | |
| | | v |
| | | +---+---+ +---+---+ +---+---+ |
| | | | * | * |-->| * | * |-->| * |NIL| |
| | | +---+---+ +---+---+ +---+---+ |
| | | | | | |
| | | | v v |
| | | | +---+ +---+ |
| | | | | 5 | | 6 | |
| | | | +---+ +---+ |
| | | v |
| | | +---+---+ +---+ |
| | | | * | * |-->| D | |
| | | +---+---+ +---+ |
| | | | |
| | | v |
| | | +---+ |
| | | | C | |
| | | +---+ |
| | v |
| | +---+---+ +---+---+ +---+---+ |
| | | * | * |-->| * | * |-->| * |NIL| |
| | +---+---+ +---+---+ +---+---+ |
| | | | | |
| | v v v |
| | +---+ +---+ +---+ |
| | | B | | 2 | | 3 | |
| | +---+ +---+ +---+ |
| v |
| +---+---+ +---+ |
| | * | * |-->| 1 | |
| +---+---+ +---+ |
| | |
| v |
| +---+ |
| | A | |
| +---+ |
+-----------------------------------------------------------+
+-----------------------------------------------------------+
| COPY-ALIST |
| |
| +---+---+ +---+---+ +---+---+ |
| | * | * |-->| * | * |-->| * |NIL| |
| +---+---+ +---+---+ +---+---+ |
| | | | |
| | | v |
| | | +---+---+ +---+---+ +---+---+ |
| | | | * | * |-->| * | * |-->| * |NIL| |
| | | +---+---+ +---+---+ +---+---+ |
| | | | | | |
| | | | v v |
| | | | +---+ +---+ |
| | | | | 5 | | 6 | |
| | | | +---+ +---+ |
| | | v |
| | | +---+---+ +---+ |
| | | | * | * |-->| D | |
| | | +---+---+ +---+ |
| | | | |
| | | v |
| | | +---+ |
| | | | C | |
| | | +---+ |
| | v |
| | +---+---+ +---+---+ +---+---+ |
| | | * | * |-->| * | * |-->| * |NIL| |
| | +---+---+ +---+---+ +---+---+ |
| | | | | |
| | v v v |
| | +---+ +---+ +---+ |
| | | B | | 2 | | 3 | |
| | +---+ +---+ +---+ |
| v |
| +---+---+ +---+ |
| | * | * |-->| 1 | |
| +---+---+ +---+ |
| | |
| v |
| +---+ |
| | A | |
| +---+ |
+-----------------------------------------------------------+
+-----------------------------------------------------------+
| COPY-TREE |
| |
| +---+---+ +---+---+ +---+---+ |
| | * | * |-->| * | * |-->| * |NIL| |
| +---+---+ +---+---+ +---+---+ |
| | | | |
| | | v |
| | | +---+---+ +---+---+ +---+---+ |
| | | | * | * |-->| * | * |-->| * |NIL| |
| | | +---+---+ +---+---+ +---+---+ |
| | | | | | |
| | | | v v |
| | | | +---+ +---+ |
| | | | | 5 | | 6 | |
| | | | +---+ +---+ |
| | | v |
| | | +---+---+ +---+ |
| | | | * | * |-->| D | |
| | | +---+---+ +---+ |
| | | | |
| | | v |
| | | +---+ |
| | | | C | |
| | | +---+ |
| | v |
| | +---+---+ +---+---+ +---+---+ |
| | | * | * |-->| * | * |-->| * |NIL| |
| | +---+---+ +---+---+ +---+---+ |
| | | | | |
| | v v v |
| | +---+ +---+ +---+ |
| | | B | | 2 | | 3 | |
| | +---+ +---+ +---+ |
| v |
| +---+---+ +---+ |
| | * | * |-->| 1 | |
| +---+---+ +---+ |
| | |
| v |
| +---+ |
| | A | |
| +---+ |
+-----------------------------------------------------------+
--
__Pascal Bourguignon__ http://www.informatimago.com/
Nobody can fix the economy. Nobody can be trusted with their finger
on the button. Nobody's perfect. VOTE FOR NOBODY.
Pascal Bourguignon
> William D Clinger wrote:
>> The eq? procedure is just a somewhat broken version of eqv?
>> that some people like to use because it's faster. You can
>> always use eqv? instead, and I recommend that, especially
>> to those new to Scheme.
>
> No we don't (the performance is a nice side effect, though). I use
> eq? because it's concise and because it shows that I only want to ever
> compare symbols or objects for identity.
>
> If I want to compare numbers, I use =. I've NEVER ever used eqv? and
> in fact I don't know in what situations you could want to check for
> object identity OR for number equality. Those two are totally
> different and occur in totally different situations (in my programs at
> least).
(assoc-eqv? key '((1 . "one") (deux . "two") (3 . "three") (quatre . "four")))
If you use eq? you don't know if 1 will be found.
If you use = you'll get errors on 'deux.
So you must use eqv? when you mix symbols and numbers.
Perhaps more typical, when matching expressions such as:
(+ (* x 3 y) (* -4 x) 5)
--
__Pascal Bourguignon__ http://www.informatimago.com/
HANDLE WITH EXTREME CARE: This product contains minute electrically
charged particles moving at velocities in excess of five hundred
million miles per hour.
Nils M Holm
> (assoc-eqv? key '((1 . "one") (deux . "two") (3 . "three") (quatre . "four")))
>
> If you use eq? you don't know if 1 will be found.
> If you use = you'll get errors on 'deux.
> So you must use eqv? when you mix symbols and numbers.
What is wrong with using EQUAL? here?
--
Nils M Holm <n m h @ t 3 x . o r g> -- http://www.t3x.org/nmh/
Brian Harvey
>I do kind of agree that this is a bit too complicated. Personally, I
>think that all of let, let* and letrec could in everyday coding be
>replaced by letrec* without any ill effects.
When this thread started, I asked myself that question, and I did come
up with a case in which letrec* wouldn't do the trick:
(define foo
(let ((cons cons)
(car car)
...)
(lambda ...)))
which we routinely use in init files to protect our functions from
redefinition (by student users) of the primitives on which they depend.
I suppose you could have DWIM-LETREC* which would be just like letrec*
except that if a symbol in a value expression is unbound, it would try
evaluating it in the enclosing environment instead. :-) Talk about
piling features on top of features...
Pascal Bourguignon
> Pascal Bourguignon <sp...@mouse-potato.com> wrote:
>> (assoc-eqv? key '((1 . "one") (deux . "two") (3 . "three") (quatre . "four")))
>>
>> If you use eq? you don't know if 1 will be found.
>> If you use = you'll get errors on 'deux.
>> So you must use eqv? when you mix symbols and numbers.
>
> What is wrong with using EQUAL? here?
Of course, you call almost always use blissfully EQUAL?.
But people who choose to use EQ? when they know they're comparing
only symbols, and = when they know they're comparing only numbers, may
want to use EQV? when they know they're comparing only symbols or numbers.
Of course, they could use EQUAL? in all cases.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Wanna go outside.
Oh, no! Help! I got outside!
Let me back inside!
Lauri Alanko
Brian Harvey <b...@cs.berkeley.edu> wrote:
> Lauri Alanko <l...@iki.fi> writes:
> >I do kind of agree that this is a bit too complicated. Personally, I
> >think that all of let, let* and letrec could in everyday coding be
> >replaced by letrec* without any ill effects.
>
> When this thread started, I asked myself that question, and I did come
> up with a case in which letrec* wouldn't do the trick:
>
> (define foo
> (let ((cons cons)
> (car car)
> ...)
> (lambda ...)))
Yes, I did consider this. I judged it not to be a very important case
in practice, since a) it's not a big deal to rename your inner
variables, and b) a good module system will anyway guarantee that your
cons won't be reassigned to something else.
Of course, if you are limited to R5RS _and_ need to ensure that your
code works even with pathological users who modify standard
procedures, then the above practice is justified. Perhaps you are in
this situation, but I still can't quite believe that people in general
bump into this in their "everyday coding".
Lauri
Bruce Lewis
> In the introduction to R5RS the philosphy behind Scheme is stated
>
> "Programming languages should be designed not by piling feature on top
> of feature .."
I think they had a specific scenario or two in mind. Say a language has
two features that one might think could be combined so solve a
particular type of problem. Unfortunately, the features were designed
in a way that doesn't allow them to be combined. Rather than redesign
the basic features of the language so that they can work together,
suppose the language designers create a new feature to solve that same
problem.
Or say a language feature can be used in one context but not another.
The Scheme way of designing the language would be to replace it with
something that could work in either context.
This is all in the context of features that have to be designed into the
language. I don't think it applies to features that can be easily built
on top of existing features. For example, you could easily build the
various number comparators on top of < and boolean operators, but the
langauge includes >, =, <=, >= anyway. I don't see this as violating
the stated philosophy.
> However when I come to deciding if two object are equal I have to learn
> about
>
> eq? eqv? equal? and type specific like char=?, string=?, =, ..
>
> Many of these or not easy to understand. In R5RS, three pages or used
> just to explain eqv?.
R5RS is a good thing to read, but it is written for language
implementors who need to know the details. You could just always use
equal? and be happy for years. You might even find that your Scheme
implementation makes equal? terminate on recursive data structures.
If this terminates in your implementation you could write with equal?
your whole life:
(let ((x (list 'a))) (set-cdr! x x) (equal? x x))
Given how much faster computers are these days, my own feeling is that
equal? should be required to work on recursive structures just as list?
is. Implementors already have to do tortoise and hare for list?, why
not do it for equal? as well. Users /that/ concerned about performance
can write their own equivalence predicates.
For reading others' code, just know that eq? means same-object?. All
those other predicates are there to throw errors if the objects you're
comparing don't have the types you expect. Plus the whole case
sensitivity thing. You can go back and find them when you're doing
something where you get the feeling equal? isn't what you want.
> For declaring variables and assigning values to them several constructs
> are used
>
> define, let, let*, letrec, named let
>
> They are not easy to understand. To get some feeling for them you must
> translate them into underlying lambda expressions which are not so easy
> to analyze themeselves.
No you mustn't. Especially named let can be much better understood from
examples of its usage. Use define for globals and the rest for
limited-scope definitions. Even with the fuzziest idea of what the
various let forms do you can start coding. You can find the right form
with trial and error.
> Now people who wrote R5RS are smart, much smarter than me. How come
> that such difficult constructs are allowed for seemingly simple things.
> The complexity in assignment and equality test is *not* an a priori
> difficulty since they are not that hard to understand in other
> languages.
Or rather, they used to not be. Time was when PHP only had ==, same as
eqv? in Scheme. Then they realized that some objects are equaler than
others and came up with ===, which I believe works like eq? in Scheme.
They're so object-oriented these days that if they haven't already
realized people will want to do == recursively, they soon will, and
we'll have an equivalent of equal?, or maybe == will be made the same as
equal? and some old PHP code will break.
In C you have == being very much like Scheme's eq?, and lots of people
by the results they get when using it on strings. You have to know what
type of data you're comparing and use strcmp(), etc. There's no option
like eqv? to compare two objects without thinking about their types.
In short, equality tests in other languages are just as complicated,
because you still have to think about same-object tests vs type-specific
tests, and about whether you want to compare recursively.
For assignment, there's something you need to understand about the R5RS
authors. Yes, they're very smart. They are also obsessive about
hygiene. Little Johnny is not allowed to touch that variable unless he
knows where it comes from and who else might be touching it. He also
needs to be precise about how his own variables touch each other.
He must use let if his variables get their values from the outside
without depending on each other.
He must use let* if within his set of variables subsequent ones depend
on prior ones.
He must use letrec when defining mutually recursive functions.
Sometimes you can use the wrong let form and get away with it, just
don't let the R5RS authors catch you at it. Especially watch out for
that Will Clinger guy. ;-)
> If there are some people reading this who have discussed R5RS, have you
> the same feeling as I that this unneccessary complicated, or am I
> seeing ghosts in broad daylight?
>
> (I'm not saying that I have any good alternative, but when simple
> things in my own work start to get complicated I usually go back to the
> foundations themeselves and try to figure out the source of these
> difficulties).
More precisely, you try to figure out whether the complexity is inherent
in the problem you're trying to solve, or whether you've manufactured
the complexity yourself as you went along.
I think it's clear that the equivalence complexity is inherent in the
problem. Assignment might be somewhat debatable, but there have been
times when Scheme's hygiene has kept me out of trouble.
--
http://ourdoings.com/ Easily organize and disseminate news and
photos for your family or group.
Brian Harvey
>In the introduction to R5RS the philosphy behind Scheme is stated
>
>"Programming languages should be designed not by piling feature on top
>of feature .."
>
>However when I come to deciding if two object are equal I have to learn
>about
>eq? eqv? equal? and type specific like char=?, string=?, =, ..
>
>are used
>define, let, let*, letrec, named let
People have addressed the specific points about equality testing and local
bindings, but I think it's worth commenting on the general point. That first
sentence in RnRS is my favorite single sentence in all of computer science, so
I'm happy to have an opportunity from time to time to review what it means and
to what extent Scheme is faithful to it.
So, first of all, *primitives don't count.* If, for example, you add
primitives to Scheme to support displaying windows and buttons and scroll bars
on a screen, that isn't "piling features" in the sense of that sentence. (Or,
looking in the other direction, SICP points out that it's not strictly
necessary to have CONS, CAR, CDR in the language, since you can define pairs
just in terms of lambda and procedure calling, but nobody complains or should
complain that Scheme provides pairs as a built-in data type.) What counts is
what *has* to be in the language in order for it to get the job done -- the
syntax, the rules for evaluating expressions, the built-in control structures,
etc.
The canonical example is support for object-oriented programming. When the C
community wanted to do OOP, they had to invent C++, because there was no way a
C programmer (as opposed to a C implementor) could extend the language so that
different classes could use the same name for different methods. But this is
a trivial exercise in Scheme.
So I claim that the question of equality testers, although interesting,
doesn't really call the "piling features" claim into question. As two
(separate and arguing against each other, ironically :-) other posters have
pointed out, both EQV? and EQUAL? are derived "do what I mean" convenience
functions, and it's in the nature of things that there are separate
really-primitive equality testers for different data types and different uses
of them. But convenience functions are a well-established tradition to which
nobody objects in general; otherwise, we wouldn't have LIST and APPEND and
ASSOC and MEMBER in Scheme, since all of these can be defined in terms of
"more-primitive" primitives.
Second, Scheme's basic philosophy allows for derived expression types --
pieces of syntax, not just primitives, that could be rewritten in terms of
other basic syntax. For example, we don't really need both IF and COND;
either could be replaced by the other. These don't count as "piling features"
either, since everyone understands that they're just convenient abbreviations
for other more basic syntax.
So, in a language without lambda, LET would be *essential* syntax, and it
would be really important to get it right. As it is, the whole LET family is
just convenience frills.
Your preferred version of LET does depend on your design philosophy, though.
LETREC* (ironically, the one missing from RnRS for n<6) is the most "do what I
mean": the one that users most often mean. But LET is the most basic: the
one in terms of which it's easiest to define all the others. So if you were
going to pick only one, I think it would be most Schemely to pick LET, since
you can then use macros trivially to put the others in a library.
To close, here's another canonical example of what "piling features" means.
In (I think) pretty much all versions of Lisp other than Scheme, including
Common Lisp, procedures have a separate namespace from other kinds of data.
The advantage of that approach is that you can use things like LIST as formal
parameters; in Scheme you can't say
(define (double list)
(LIST list list))
in which the capitalized LIST refers to the primitive procedure, and the
others to the formal parameter. In Common Lisp that would work. But the cost
of this two-namespace feature is that, although procedures have always been
first-class data in Lisp, you need special notations to use a procedure as a
datum (different notations in different historical eras). Scheme simplifies
all this by having only one namespace, treating procedures exactly like
everything else. That's an example of "removing restrictions."
H.
> either could be replaced by the other.
I thought this too until I read a footnote in SICP this weekend which
seemed to imply that there was an edge case involving non-functional
programming in which they are not mutually exchangeable:
chapter 1, footnote 19:
"A minor difference between if and cond is that the <e> part of each
cond clause may be a sequence of expressions. If the corresponding <p>
is found to be true, the expressions <e> are evaluated in sequence and
the value of the final expression in the sequence is returned as the
value of the cond. In an if expression, however, the <consequent> and
<alternative> must be single expressions."
So, strictly speaking, they do not have a biconditional relationship,
in that
if you use nested ifs, you can always use cond instead. TRUE.
if you use cond, you can always use nested ifs instead. FALSE.
Of course, I'm throwing this out there to verify/negate it. imho, more
exact is: "If doing functional programming, then is and cond are
entirely fungible in their usage. If not doing functional programming,
if a subset of cond, i.e. if --> cond"
Jens Axel Søgaard
> chapter 1, footnote 19:
> "A minor difference between if and cond is that the <e> part of each
> cond clause may be a sequence of expressions. If the corresponding <p>
> is found to be true, the expressions <e> are evaluated in sequence and
> the value of the final expression in the sequence is returned as the
> value of the cond. In an if expression, however, the <consequent> and
> <alternative> must be single expressions."
But that single expression could be a begin.
(if (eq? 1 1)
(begin
(display "Hurray!")
(newline))
(begin
(display "Bummer!")
(newline)))
--
Jens Axel Søgaard
Lauri Alanko
H. <hbe...@gmail.com> wrote:
> So, strictly speaking, they do not have a biconditional relationship,
> in that
> if you use nested ifs, you can always use cond instead. TRUE.
> if you use cond, you can always use nested ifs instead. FALSE.
No. You can define cond using if, provided that you also have begin.
R5RS gives a sample definition that translates
((cond (test result1 result2 ...)
clause1 clause2 ...)
to
(if test
(begin result1 result2 ...)
(cond clause1 clause2 ...)))
And, if you forget about defines (which can be grouped with begin),
begin can also be defined using lambda:
(begin e) => e
(begin e1 e2 ...) => ((lambda (dummy) (begin e2 ...)) e1)
So. If you have lambda and if, you can define cond with them.
Lauri
Anton van Straaten
> I do kind of agree that this is a bit too complicated. Personally, I
> think that all of let, let* and letrec could in everyday coding be
> replaced by letrec* without any ill effects.
Let me introduce another famous Abelson & Sussman quote into this family
of threads: "Programs must be written for people to read, and only
incidentally for machines to execute."
One ill effect of using LETREC* for everything is that dependencies in
code require more effort to determine for human readers of code.
When you see a LET in code, you know that the variables in the LET don't
depend on each other during their initialization. That's useful info,
especially when you're refactoring a program, and it's not necessarily
immediately apparent otherwise.
When you see a LET*, you know that later variables may depend on earlier
variables.
When you see LETREC, you know that variables may depend on each other in
any order, but not during their initialization. (Note that this is true
of standard LETREC even in the presence of guaranteed left-to-right
evaluation.)
When you see LETREC*, you really don't know much about variable
dependencies at all. Few possibilities are excluded, other than the
obviously impossible. The least possible information is communicated to
a human reader of the code.
LETREC* is therefore the worst possible construct you can pick if you
care about people reading your code. From that perspective, it should
only be used when absolutely essential.
As it happens, LETREC* is pretty much never essential, except possibly
as an implementation technique to support inner DEFINEs, which then
naturally suffer from the same issues -- they don't communicate anything
useful about their interdependencies.
> But this touches on
> evaluation order issues, which is rather a hot topic, so I won't say
> more here. :)
Although I agree it "touches" on evaluation order issues, they're not
the real issue here. The distinctions between these four binding
operators would be as important if Scheme had a single fixed evaluation
order.
Anton
Lauri Alanko
Anton van Straaten <an...@appsolutions.com> wrote:
> One ill effect of using LETREC* for everything is that dependencies in
> code require more effort to determine for human readers of code.
> > But this touches on
> > evaluation order issues, which is rather a hot topic, so I won't say
> > more here. :)
>
> Although I agree it "touches" on evaluation order issues, they're not
> the real issue here.
The reason I said this is because the issue is exactly the same:
should we have a language construct that provides less power than it
could simply to express the fact that the extra power is not needed?
In this case, my answer is no because the property to be expressed is
IMHO not particularly interesting, and it can be trivially discovered
with local syntactic analysis if need be.
In the evaluation order case my answer is no because the property
(order-independence of operator and operand expressions) is
undecidable in general and even its run-time checking would be very
expensive.
However, the answer would be yes in a situation where the property is
non-local _and_ checkable at least at run-time. This would be the case
with char=? versus eqv?. Why have char=? since you could just use eqv?
everywhere in its place? Because char=? expresses that the operands
are expected to be characters, and this would not be obvious by just
looking at the code around the call since the operands could come from
anywhere in the program, but the run-time can detect if the property
gets broken.
But all the issues have been hashed through and people have chosen
their camps, so there's really nothing much to say.
Lauri
Anton van Straaten
> The reason I said this is because the issue is exactly the same:
> should we have a language construct that provides less power than it
> could simply to express the fact that the extra power is not needed?
OK, I agree about the commonality there, although I would phrase it as
"Should we have a language construct that provides the precise amount of
power to express the exact requirements of the code, or should we
abandon that precision in favor of fewer, less specific constructs?"
> In this case, my answer is no because the property to be expressed is
> IMHO not particularly interesting, and it can be trivially discovered
> with local syntactic analysis if need be.
I think that needs to be qualified: from what perspective is it not a
particularly interesting property? Certainly, from the perspective of
automated analysis, most of the distinctions in question are not
interesting, because as you say, they can be discovered trivially.
However, that "trivial" effort is measurable for humans: I can give you
ordinary, reasonably well-written code samples where it'll take you at
least a number of seconds to figure out the variable dependencies, and
possibly more. Also, you might even get them wrong at first, in some
cases. That becomes more important when you're dealing with tens or
hundreds of thousands of lines of code, or more, and have to expend that
effort over and over. It can slow down the reading of code, and errors
can lead to misunderstanding the meaning of code.
What seems trivial for the author of some code at the time of writing is
not necessarily so trivial for others looking at the code later. That's
one of the inspirations behind the common ironic inversion of the
Abelson & Sussman quote: "Code is hard to write, so it should be hard to
read". I imagine adding "...therefore we should use LETREC* everywhere"
to the end of that. :)
> In the evaluation order case my answer is no because the property
> (order-independence of operator and operand expressions) is
> undecidable in general and even its run-time checking would be very
> expensive.
I thought you didn't want to get into that discussion? For the record,
run-time checking is easy in practice, but that's not so important to me
anyway: automatically checkable properties aren't the only interesting
kinds of properties.
> However, the answer would be yes in a situation where the property is
> non-local _and_ checkable at least at run-time. This would be the case
> with char=? versus eqv?. Why have char=? since you could just use eqv?
> everywhere in its place? Because char=? expresses that the operands
> are expected to be characters, and this would not be obvious by just
> looking at the code around the call since the operands could come from
> anywhere in the program, but the run-time can detect if the property
> gets broken.
So you're essentially setting a threshold of time required to analyze
code for some property, and above that threshold, expressing the
property explicitly makes sense to you.
I'm saying if it's cheap to make the time to analyze essentially zero,
or at least as low as it can possibly be, that's worthwhile.
Anton
Bruce Lewis
> If this terminates in your implementation you could write with equal?
> your whole life:
>
> (let ((x (list 'a))) (set-cdr! x x) (equal? x x))
Actually I was wrong about that. You can have equal? terminate
immediately if its arguments are the same object.
Here's the right test:
(let ((x (list 'a))
(y (list 'a)))
(set-cdr! x x)
(set-cdr! y y)
(equal? x y))
Both mzscheme and Kawa terminate in the first example I gave but spin on
this one.
Lauri Alanko
In article <VobBf.1383$ur7....@newssvr33.news.prodigy.com>,
Anton van Straaten <an...@appsolutions.com> wrote:
> > In this case, my answer is no because the property to be expressed is
> > IMHO not particularly interesting, and it can be trivially discovered
> > with local syntactic analysis if need be.
>
> I think that needs to be qualified: from what perspective is it not a
> particularly interesting property?
Primarily in the sense that it is purely local: whether an expression
is a LET or a LET* form doesn't tell us anything about its behavior as
a whole, i.e. about the relation of that expression to its context. It
only tells about the relation of its parts to each other. This kind of
information is relevant only for very low-level code manipulation, not
for understanding the structure of the program.
Moreover, the manipulations that this information allows are quite
limited. Apart from being able to reorder the binding clauses (which
is useless if evaluation order isn't fixed), just about the only
useful application I can think of is that in a LET-form you can remove
a binding and be sure that it won't break any other bindings. But in
order to remove a binding you have to make sure that the bound
variable won't appear in the body, and for this you have to do manual
syntactic analysis anyway, so the non-dependency information given by
the LET form buys very little.
So with "not interesting" I mainly mean "not useful often enough".
Here's a somewhat analogous situation: it is often (well, sometimes)
useful to know exactly which variables occur free in a lambda, i.e.
are captured by the closure's environment. This can be discovered
trivially with local syntactic analysis, but it is time-consuming for
humans. Would you then advocate having a variant of a lambda form
where the captured variables are explicitly listed, to make this
information more readily available to the reader of the code?
> So you're essentially setting a threshold of time required to analyze
> code for some property, and above that threshold, expressing the
> property explicitly makes sense to you.
Pretty much, yeah.
> I'm saying if it's cheap to make the time to analyze essentially zero,
> or at least as low as it can possibly be, that's worthwhile.
Another factor is the time required from the writer. If there is a
LET-form, and further changes to the code introduce a dependency
between the bindings, the programmer has to change the LET to a LET*.
If it was originally LET* (or better yet, LETREC*), further changes
are cheaper.
Note that this is argument is not of the same kind as "you shouldn't
write contracts since your contracts may change during development
anyway", since contracts express _non-local_ properties.
And one more threshold is the "usefulness" I mentioned. Even if a
property is very easy to express, it shouldn't be expressed if it
isn't useful to anyone, since then it will only clutter the code. I
think the Gricean maxims of conversation apply also to code as a
vehicle of human communication: in addition to being informative, you
must also be brief and relevant. Just because you can express
something doesn't mean you should.
Lauri
Abdulaziz Ghuloum
> Given how much faster computers are these days, my own feeling is that
> equal? should be required to work on recursive structures just as list?
> is. Implementors already have to do tortoise and hare for list?, why
> not do it for equal? as well. Users /that/ concerned about performance
> can write their own equivalence predicates.
Because toroise and hare does not work for general data-structures.
It only work on lists. If there were a general tortoise and hare, it
would've been in TSPL.
Aziz,,,
Bruce Lewis
> Because toroise and hare does not work for general data-structures.
> It only work on lists. If there were a general tortoise and hare, it
> would've been in TSPL.
If a general data structure is cyclical, any traversal of it will
eventually be in a cycle. Thus the hare will catch the tortoise. If it
isn't cyclical there should be a straightforward traversal where the
hare won't catch the tortoise. Where is the flaw in my reasoning?
Abdulaziz Ghuloum
In a list, the hare and tortoise follow the same path and will
eventually meet if the path is a cycle.
In the general case, say with pairs, the cycles may be in the car or cdr
direction (or both). Which path should the hare take?
I know this is not a proof. Just try implementing it and see if you get
stuck.
Aziz,,,
Pascal Bourguignon
You'll need a big number of hares and tortoises. Everytime there's a
fork, you'll need to fork them.
--
__Pascal Bourguignon__ http://www.informatimago.com/
This universe shipped by weight, not volume. Some expansion may have
occurred during shipment.
Lauri Alanko
Abdulaziz Ghuloum <aghu...@c-s-remove-dashes.indiana.edu> wrote:
> In a list, the hare and tortoise follow the same path and will
> eventually meet if the path is a cycle.
In a tree, the hare and tortoise follow the same traversal order and
will eventually meet if there is a cycle.
> In the general case, say with pairs, the cycles may be in the car or cdr
> direction (or both). Which path should the hare take?
Whichever the traversal order dictates. And the tortoise should take
the same.
> I know this is not a proof. Just try implementing it and see if you get
> stuck.
Here's an ugly quick implementation.
(define (forward path)
(cond ((not (pair? path)) #f)
((pair? (car path)) (cons (caar path) path))
((pair? (cdr path)) (cons (cdadr path) (cddr path)))
(else #f)))
(define (cyclical? x)
(let loop ((hare (forward (list x)))
(tortoise (list x)))
(and hare
(or (eq? (car hare) (car tortoise))
(loop (forward (forward hare)) (forward tortoise))))))
Show me a cell graph where it gets stuck or returns the wrong result.
Lauri
Shiro Kawai
> Here's an ugly quick implementation.
>
> (define (forward path)
> (cond ((not (pair? path)) #f)
> ((pair? (car path)) (cons (caar path) path))
> ((pair? (cdr path)) (cons (cdadr path) (cddr path)))
> (else #f)))
>
> (define (cyclical? x)
> (let loop ((hare (forward (list x)))
> (tortoise (list x)))
> (and hare
> (or (eq? (car hare) (car tortoise))
> (loop (forward (forward hare)) (forward tortoise))))))
>
> Show me a cell graph where it gets stuck or returns the wrong result.
How about this?
(cyclical? '(#1=((#f . #f)) . #1#)) => #t
Lauri Alanko
Shiro Kawai <shiro...@gmail.com> wrote:
> Lauri Alanko wrote:
> > Show me a cell graph where it gets stuck or returns the wrong result.
>
> How about this?
>
> (cyclical? '(#1=((#f . #f)) . #1#)) => #t
Ah, right. So tortoise and hare only detect _sharing_, and only with
lists does sharing imply cycles.
I did have a nagging feeling that it can't be that simple. :)
Lauri
Brian Harvey
> ((pair? (car path)) (cons (caar path) path))
> ((pair? (cdr path)) (cons (cdadr path) (cddr path)))
Part of the point of the two-pointer algorithm is that it doesn't generate
new pairs. Otherwise you could use the
(memq? this-pair already-seen)
approach.
Matthias Blume
> Nils M Holm <before-2...@online.de> writes:
>> Pascal Bourguignon <sp...@mouse-potato.com> wrote:
>>> (assoc-eqv? key '((1 . "one") (deux . "two") (3 . "three") (quatre . "four")))
>>>
>>> If you use eq? you don't know if 1 will be found.
>>> If you use = you'll get errors on 'deux.
>>> So you must use eqv? when you mix symbols and numbers.
>>
>> What is wrong with using EQUAL? here?
>
> Of course, you call almost always use blissfully EQUAL?.
>
> But people who choose to use EQ? when they know they're comparing
> only symbols, and = when they know they're comparing only numbers, may
> want to use EQV? when they know they're comparing only symbols or numbers.
>
> Of course, they could use EQUAL? in all cases.
Of course, most things that are EQUAL? in the lisp/scheme sense aren't
equal at all (in the Leibnitz sense).
Matthias
Radey Shouman
Here's a simple-minded implementation, using a list as a stack:
;; Return #t iff TREE contains a loop followable by CAR or CDR,
;; otherwise return #f.
(define (tree-cyclic? tree)
(define (depth-next stk)
(let ((top (car stk))
(pending (cdr stk)))
(cond ((pair? top) (cons (car top)
(cons (cdr top) pending)))
((pair? pending) pending)
(else '()))))
(let loop ((tortoise (list tree))
(hare (depth-next (list tree))))
(cond ((null? tortoise) #f)
((null? hare) #f)
((eq? (car tortoise) (car hare)) #t)
(else
(loop (depth-next tortoise)
(depth-next (depth-next hare)))))))
Pascal Bourguignon
Yes. You're missing the point. The above result is wrong! The data is
not cyclical, so it should have returned #f.
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
Anton van Straaten
> No, I can't let go either...
I could give it up anytime... if I wanted to.
> This kind of
> information is relevant only for very low-level code manipulation, not
> for understanding the structure of the program.
It's not just for manipulation, it's also for helping to understand
overall meaning without necessarily examining every detail.
> Moreover, the manipulations that this information allows are quite
> limited. Apart from being able to reorder the binding clauses (which
> is useless if evaluation order isn't fixed), just about the only
> useful application I can think of is that in a LET-form you can remove
> a binding and be sure that it won't break any other bindings. But in
> order to remove a binding you have to make sure that the bound
> variable won't appear in the body, and for this you have to do manual
> syntactic analysis anyway, so the non-dependency information given by
> the LET form buys very little.
One refactoring which LET supports, without requiring dependency
analysis, is moving a binding to a higher level, if it's needed outside
the body in which it was originally used.
All three of Scheme's binding constructs tell you where to start looking
for things on which their variables could depend, and they also exclude
other places you might need to look.
> So with "not interesting" I mainly mean "not useful often enough".
>
> Here's a somewhat analogous situation: it is often (well, sometimes)
> useful to know exactly which variables occur free in a lambda, i.e.
> are captured by the closure's environment. This can be discovered
> trivially with local syntactic analysis, but it is time-consuming for
> humans. Would you then advocate having a variant of a lambda form
> where the captured variables are explicitly listed, to make this
> information more readily available to the reader of the code?
I don't see the analogy as being close, because you're suggesting a
construct which includes an additional, potentially long list of
variable names, which has a higher cost of initial use, and a higher
cost of maintenance, whereas all I'm suggesting is choosing the
appropriate keyword out of a small set.
Regarding the rest of your post, it boils down to the same general
disagreement between us. For all the criteria you mention -- time
required from the writer, usefulness, brevity and relevance -- I
consider the cost of using and maintaining the appopriate keywords
negligible, and the benefits to far outweigh that cost. Choosing
properly between LET/LET*/LETREC is a "brief and relevant" way to
document a property that I find useful to have documented.
Another point on which we disagree is "it's not a big deal to rename
your inner variables". Repeating myself from a few weeks ago, I
consider it a big deal to be unnecessarily prevented from using certain
identifier names when the name I want to use would be the one that I
consider the most meaningful, e.g.:
(lambda (x)
(let ((x (foo x)))
...))
The machine distinguishes between same-named identifiers in different
scopes, but humans have a more subtle perspective, and are able to
assign significance both to the commonality signified by the use of the
same name, as well as to the distinction between the referents. You may
think it's not a big deal to have to rename x to "x2" or "x*" above, but
as I see it, that's a dumbing down the language, making it lower level,
reducing the range of expressivity available to humans.
Anton
Bruce Lewis
> You'll need a big number of hares and tortoises. Everytime there's a
> fork, you'll need to fork them.
I don't think this is so different from regular equal?, where something
is retained on the stack or heap with each fork.
(define (naive-equal? o1 o2)
(cond ((eqv? o1 o2) #t)
((and (pair? o1) (pair? o2))
(and (naive-equal? (car o1) (car o2))
(naive-equal? (cdr o1) (cdr o2))))
(else #f)))
To illustrate, here's an implementation of cyclical-equal? that doesn't
work on vectors, but seems to work fine for pairs. (t1) returns true
and (t2) returns false, as it should.
I haven't proven to myself that there exist no two cyclical structures
such that a human would regard them as unequal, but cyclical-equal?
would return #t. In such a structure both tortoises would have to catch
up to both hares at the same time, with every traversed node along the
way being equal.
[The "unused" weirdness is me using a student language in drscheme where
the stepper works in v209, the release in Debian testing. The language
demanded that lambda have at least one argument.]
(define unused #f)
(define make-iteration list)
(define (traversal obj branches)
(make-iteration
obj
(if (pair? obj)
(lambda ( unused)
(traversal (car obj)
(cons (cdr obj) branches)))
(if (pair? branches)
(lambda ( unused)
(traversal (car branches) (cdr branches)))
#f))))
(define element car)
(define next-iteration cadr)
(define (follow-next-iteration iter)
((next-iteration iter) unused))
(define (cyclical-equal? o1 o2)
(if (eqv? o1 o2)
#t
(letrec
((helper
(lambda (hare1 hare2 tortoise1 tortoise2 advance-tortoise)
(cond
((and (not (next-iteration hare1))
(not (next-iteration hare2))
(eqv? (element hare1)
(element hare2)))
#t)
((or (and (not (next-iteration hare1))
(next-iteration hare2))
(and (not (next-iteration hare2))
(next-iteration hare1)))
#f)
((or (not (pair? (element hare1)))
(not (pair? (element hare2))))
(and (eqv? (element hare1)
(element hare2))
(helper-next
hare1 hare2 tortoise1 tortoise2 advance-tortoise)))
((and (eq? (element hare1) (element tortoise1))
(eq? (element hare2) (element tortoise2)))
#t)
(else
(helper-next
hare1 hare2 tortoise1 tortoise2 advance-tortoise)))))
(helper-next
(lambda (hare1 hare2 tortoise1 tortoise2 advance-tortoise)
(helper
(follow-next-iteration hare1)
(follow-next-iteration hare2)
(if advance-tortoise
(follow-next-iteration tortoise1)
tortoise1)
(if advance-tortoise
(follow-next-iteration tortoise2)
tortoise2)
(not advance-tortoise)))))
(helper
(traversal o1 '())
(traversal o2 '())
(traversal (list o1) '())
(traversal (list o2) '())
#t))))
(define (t1)
(let ((x (list 1 2 1 2)))
(set-cdr! (list-tail x 3) x)
(cyclical-equal? x (cddr x))))
(define (t2)
(let ((x (list 1 2 1 2)))
(set-cdr! (list-tail x 3) (cdr x))
(cyclical-equal? x (cddr x))))
Tony Garnock-Jones
> I've read the second one but missed the first one. I'm reading it now
You might also be interested in "Equal Rights for Functional Objects",
by Henry Baker:
http://home.pipeline.com/~hbaker1/ObjectIdentity.html
Cheers,
Tony
Marcin 'Qrczak' Kowalczyk
> One ill effect of using LETREC* for everything is that dependencies in
> code require more effort to determine for human readers of code.
Often no single kind of LET fits perfectly. For example suppose there
are 5 definitions with 2 dependencies:
A = ...
B = ... A ...
C = ...
D = ... C ...
E = ...
and constraints on the evaluation order are the same as the
dependencies (A before B, C before D, otherwise doesn't matter).
We can't write them in Scheme without overspecifying the evaluation
order and the dependencies.
I disagree that the shape of dependencies between local definitions
is so important that they should be marked this way. The goal is not
fully archievable anyway.
--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Anton van Straaten
> Anton van Straaten <an...@appsolutions.com> writes:
>
>
>>One ill effect of using LETREC* for everything is that dependencies in
>>code require more effort to determine for human readers of code.
>
>
> Often no single kind of LET fits perfectly. For example suppose there
> are 5 definitions with 2 dependencies:
> A = ...
> B = ... A ...
> C = ...
> D = ... C ...
> E = ...
> and constraints on the evaluation order are the same as the
> dependencies (A before B, C before D, otherwise doesn't matter).
> We can't write them in Scheme without overspecifying the evaluation
> order and the dependencies.
Unless I've misunderstood you, you can specify this perfectly, as follows:
(let A = ...
C = ...
E = ...
(let B = ... A ...
D = ... C ...
There's no overspecification whatsoever - the degree of specification is
perfectly matched to the problem. This form communicates the
dependencies in a way that LETREC* cannot.
Perhaps your concern is that expressing this as a single LET* would
overspecify the dependencies. But even that would be more communicative
than being required to use LETREC*.
In any case, part of the point of having a set of binding operators is
that you can combine them appropriately to express whatever you need to
express. You might choose to overspecify in some cases, for whatever
reasons, but you're not forced to.
> I disagree that the shape of dependencies between local definitions
> is so important that they should be marked this way. The goal is not
> fully archievable anyway.
Most of the time, the goal is sufficiently achievable to be useful. The
fact that it's possible to write code which obscures dependency
information doesn't detract from that.
Anton
Abdulaziz Ghuloum
> Marcin 'Qrczak' Kowalczyk wrote:
>> Often no single kind of LET fits perfectly. For example suppose there
>> are 5 definitions with 2 dependencies:
>> A = ...
>> B = ... A ...
>> C = ...
>> D = ... C ...
>> E = ...
>> and constraints on the evaluation order are the same as the
>> dependencies (A before B, C before D, otherwise doesn't matter).
>> We can't write them in Scheme without overspecifying the evaluation
>> order and the dependencies.
>
>
> Unless I've misunderstood you, you can specify this perfectly, as follows:
>
> (let A = ...
> C = ...
> E = ...
> (let B = ... A ...
> D = ... C ...
>
> There's no overspecification whatsoever - the degree of specification is
> perfectly matched to the problem. This form communicates the
> dependencies in a way that LETREC* cannot.
You did over-specify that E's value must be computed before B's and D's.
Pushing it to the inner let over-specifies that it must be computed
after A and C.
Aziz,,,
Anton van Straaten
Good point. Accordingly, I'd like to propose a new probabilistic
promise type, which would be used as follows:
(let ((A ...)
(C ...)
(E (compute/probability 0.5 ...)))
(let ((B ... A ...)
(D ... C ...)
(E (compute E)))
This would result in E's value actually being computed in either of the
two places, depending on chance. Ideally, the probabilities would be
driven by the decay of a radioactive isotope.
BTW, note how a LETREC* would mess up this elegant idiom, requiring the
final variable to be renamed to something like E*.
Anyway, I wasn't really trying to suggest that overspecification doesn't
happen, and quite regularly, at that. Marcin's example just tempted me
with a bit too much rope.
But despite the unavoidable imprecision involved, I find that both
writing and reading code that's as precise about dependencies as it can
practically be is more helpful to me as a programmer than using
monolithic, imperative-style, linearly-sequenced definitions.
During the course of this discussion, I've wondered if I'd be happy with
a sophisticated IDE that say, detected and colored dependency regions
automatically (like a less specific version of DrScheme's arrows). But
given such an IDE, and given code like the original:
A = ...
B = ... A ...
C = ...
D = ... C ...
E = ...
...such coloring would simply be messy (alternating stripes for the
first four lines), and I would still find it helpful to arrange the
definitions roughly by dependency.
Anton
Marcin 'Qrczak' Kowalczyk
> Unless I've misunderstood you, you can specify this perfectly, as follows:
>
> (let A = ...
> C = ...
> E = ...
> (let B = ... A ...
> D = ... C ...
>
> There's no overspecification whatsoever
There is: it forces B to be evaluated after C and E, and D to be
evaluated after A and E.
Here is an actual example from my code in Emacs Lisp:
(defun kogut-scan-bracketed (close state)
(let* ((state-here (kogut-state-here))
(state-outside (or state-here state))
(state-inside (kogut-indent-after-opening state-outside))
(state-after-semi state-inside)
(is-after-semi t)
(new-statement nil)
(dont-indent-args nil)
(position-start (point))
(result nil))
...))
All variables happen to be used in the body. There are 4 bindings
which must be made in a specific order, and 5 other bindings which
are independent from them and from one another, and thus in principle
could be interleaved with them arbitrarily. I could at most create
various arbitrary partial overspecifications, by binding those 5
with let put outside or inside the let*, but I didn't bother; there
are already too many indentation levels for my taste.
Anton van Straaten
> Anton van Straaten <an...@appsolutions.com> writes:
>
>
>>Unless I've misunderstood you, you can specify this perfectly, as follows:
>>
>>(let A = ...
>> C = ...
>> E = ...
>> (let B = ... A ...
>> D = ... C ...
>>
>>There's no overspecification whatsoever
>
>
> There is: it forces B to be evaluated after C and E, and D to be
> evaluated after A and E.
Yes, you're right (at least, assuming a conservative compiler and the
presence of side effects).
I've responded about overspecification in my reply to Aziz.
> Here is an actual example from my code in Emacs Lisp:
>
> (defun kogut-scan-bracketed (close state)
> (let* ((state-here (kogut-state-here))
> (state-outside (or state-here state))
> (state-inside (kogut-indent-after-opening state-outside))
> (state-after-semi state-inside)
> (is-after-semi t)
> (new-statement nil)
> (dont-indent-args nil)
> (position-start (point))
> (result nil))
> ...))
>
> All variables happen to be used in the body. There are 4 bindings
> which must be made in a specific order, and 5 other bindings which
> are independent from them and from one another, and thus in principle
> could be interleaved with them arbitrarily. I could at most create
> various arbitrary partial overspecifications, by binding those 5
> with let put outside or inside the let*, but I didn't bother; there
> are already too many indentation levels for my taste.
I don't see much of an issue here: the first four bindings require the
LET*, and the remainder don't, but there's no strong reason to add a
nesting level here. But all this says is that certain binding operators
aren't needed in particular cases, which is to be expected. There's no
concrete basis for generalizing from this, to conclude that other
operators should be eliminated. All that's needed to refute such a
generalization are examples where other binding operators are useful. I
can provide plenty of those, although no doubt we may not agree on their
degree of usefulness.
It's not as though this is the only example of imprecise specifications
in a language. Another example where specifications don't match a
program's precise characteristics is with static type systems, which
inevitably have slack where they're too conservative about the types of
terms. I suppose this is a risky argument to make in the context of
Scheme, but luckily the analogy is not so close that the drawbacks of
static typing also apply to using a variety of binding operators.
Anton