way to convert everything to a list?
budden
I wrote a "listify" generic.
http://paste.lisp.org/display/72614
It converts everything to a list. Especially interesting is to convert
clos objects to lists to be able to compare their hierarchies. If
object references are circular, listify should work (unless you write
method which itself loops).
I'm sure this is not new. Where is the full and hairy implementation
of that?
jos...@corporate-world.lisp.de
> Hi!
> I wrote a "listify" generic.
>
> http://paste.lisp.org/display/72614
>
> It converts everything to a list. Especially interesting is to convert
> clos objects to lists to be able to compare their hierarchies. If
> object references are circular, listify should work (unless you write
> method which itself loops).
Why would you want lists to compare objects?
budden
watch at "nil" as a result of comparison. Default print function for
CLOS objects do not show what I want, but redefining it may be
harmful. So I use (let1 *print-circle* t (print (listify o)) just to
see what's in a box.
2. There is no standard way to check if two CLOS objects are
isomorphic (or maybe I missed something). Why not convert them to
lists?
Tamas K Papp
>> Why would you want lists to compare objects?
> 1. Lists are easy to print. I can see what happens, not only just watch
> at "nil" as a result of comparison. Default print function for CLOS
> objects do not show what I want, but redefining it may be harmful. So I
How is defining a print method harmful?
> 2. There is no standard way to check if two CLOS objects are isomorphic
> (or maybe I missed something). Why not convert them to lists?
That's because there is no "standard way" to define isomorphism or
equality in general. Read, for example,
http://www.nhplace.com/kent/PS/EQUAL.html
Printing things as list doesn't solve anything, and is frankly
pointless. I still don't see what you are trying to do. It seems that
you are attempting to write "general" tools without any particular goal/
application in mind.
Tamas
Alex Mizrahi
TKP> that you are attempting to write "general" tools without any
TKP> particular goal/ application in mind.
moreover, these "general" tools are going to be conceptually broken,
this seems to be an important aspect of budden's ideas.
budden
would loop if *print-circle* is nil.
Contrary to that, listify do not print and hence do not loop. Print is
used everywhere (including debugger)
and if it loops it is really harmful. Listify is only used explicitly
and it is in scope of users abilities to bind
*print-circle* to t while printing result of listify.
> It seems that you are attempting to write "general" tools without any particular goal/
application in mind.
Wrong. It was made for testing of real-world code and it was a
success. Should I spend my precious time fighting against
prejudice?
Thanks for the help :/
Barry Margolin
<cb99b8b8-1b52-4dd5...@z6g2000pre.googlegroups.com>,
budden <budde...@mail.ru> wrote:
> > How is defining a print method harmful?
> Defining print "naturally" (with recursive printing of selected slots)
> would loop if *print-circle* is nil.
> Contrary to that, listify do not print and hence do not loop. Print is
> used everywhere (including debugger)
> and if it loops it is really harmful. Listify is only used explicitly
> and it is in scope of users abilities to bind
> *print-circle* to t while printing result of listify.
Also if the class already has its own print-object method, you would
have to replace this, which impacts normal use of the class.
--
Barry Margolin, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Steven M. Haflich
> In article
> <cb99b8b8-1b52-4dd5...@z6g2000pre.googlegroups.com>,
> budden <budde...@mail.ru> wrote:
>
>>> How is defining a print method harmful?
>> Defining print "naturally" (with recursive printing of selected slots)
>> would loop if *print-circle* is nil.
>> Contrary to that, listify do not print and hence do not loop. Print is
>> used everywhere (including debugger)
>> and if it loops it is really harmful. Listify is only used explicitly
>> and it is in scope of users abilities to bind
>> *print-circle* to t while printing result of listify.
>
> Also if the class already has its own print-object method, you would
> have to replace this, which impacts normal use of the class.
I agree with everyone else that the printing solution to this
equality predicate is a broken solution, and worse, that the
problem itself is not well conceived. However, creating a custom
pprint-dispatch would be a possible alternative to the above
objections to defining print-object methods.
On the definition of equality and structure sharing, one might ponder
whether these two objects should or should not compare as similar:
cl-user(2): '#1=(#1#)
(((((#)))))
cl-user(3): '#1=((#1#))
(((((#)))))
Chuckle.
Stanisław Halik
> On the definition of equality and structure sharing, one might ponder
> whether these two objects should or should not compare as similar:
> cl-user(2): '#1=(#1#)
> (((((#)))))
> cl-user(3): '#1=((#1#))
> (((((#)))))
(= (sxhash '#1=(#1#)) (sxhash '#2=((#2#))))
==> T
(concatenate 'string (lisp-implementation-type) " "
(lisp-implementation-version))
==> "SBCL 1.0.23.66"
:-)
--
You only have power over people so long as you don’t take everything
away from them. But when you’ve robbed a man of everything he’s no longer
in your power — he’s free again. -- Aleksandr Isayevich Solzhenitsyn
Steven M. Haflich
> thus spoke Steven M. Haflich <s...@alum.mit.edu>:
>
>> On the definition of equality and structure sharing, one might ponder
>> whether these two objects should or should not compare as similar:
>> cl-user(2): '#1=(#1#)
>> (((((#)))))
>> cl-user(3): '#1=((#1#))
>> (((((#)))))
>
> (= (sxhash '#1=(#1#)) (sxhash '#2=((#2#))))
> ==> T
> (concatenate 'string (lisp-implementation-type) " "
> (lisp-implementation-version))
> ==> "SBCL 1.0.23.66"
>
> :-)
>
Indeed. sxhash is predicated on one particular notion of
equality, but that notion is not necessarily what might have
been in the mind of the original poster.
To continue the :-) this leads me to wonder about approximately-equal
predicates, and whether they can be applied to hashing. For example,
I have sometimes defined approx-equal numerical predicates some of
which might return true for (approx-equal 3.1415926 3.1415927) which
is useful to compare results where calculation errors blur the notion
of equality.
The design question: How to design a hashtable around the notion of
approximate equality, such that gethash on two numeric values that
are not equal but which are approx-equal would alway return the same
entry. The loose screw is that while 3.1415916 might be approx-equal
to both 3.1415915 and 3.1415927, it might not be true that 3.1415915
and 3.1415927 are approx-equal to each other, and don't represent the
same hash value.
I haven't thought very deeply about this yet, and intend to preserve
that blessed state.
Tamas K Papp
> To continue the :-) this leads me to wonder about approximately-equal
> predicates, and whether they can be applied to hashing. For example, I
> have sometimes defined approx-equal numerical predicates some of which
> might return true for (approx-equal 3.1415926 3.1415927) which is useful
> to compare results where calculation errors blur the notion of equality.
>
> The design question: How to design a hashtable around the notion of
> approximate equality, such that gethash on two numeric values that are
> not equal but which are approx-equal would alway return the same entry.
> The loose screw is that while 3.1415916 might be approx-equal to both
> 3.1415915 and 3.1415927, it might not be true that 3.1415915 and
> 3.1415927 are approx-equal to each other, and don't represent the same
> hash value.
I don't understand: "approximately equal" is not a transitive relation
and thus not a good concept for a hash table.
If I had a bunch of numbers and wanted to return those which are
approximately equal (ie within some distance, say epsilon in absolute
value) to a particular value y, I would do the following: bin them
with some affine function, eg
(lambda (x)
(floor x bin-width))
and simply use the bin as the key for the hash table, with the value
as a list of numbers in this bin. Then for a particular y, I would
retrieve the numbers in the same bin and the neighboring bins, and
filter out those which are actually within epsilon of y. The
"optimal" value of bin-width depends on your application, but since
hash tables are quite efficient it won't make a whole lot of
difference, so I would just make it some small multiple of epsilon.
HTH,
Tamas
Steven M. Haflich
> I don't understand: "approximately equal" is not a transitive relation
> and thus not a good concept for a hash table.
Thanks. This is a very good summary of the underlying issue.
What a hash table does is to map "equal" keys onto values. This has
nothing to do with the idea that hashing generates a pseudo-random
bucket in which to look for the value for a particular key. A hash
table maps each equality-distinct key onto a particular value,
independent of whether multiple keys map to the same bucket. Typical
hash table strategies first determine a bucket, and then look for
precise equality check among the keys that have mapped into that bucket.
> If I had a bunch of numbers and wanted to return those which are
> approximately equal (ie within some distance, say epsilon in absolute
> value) to a particular value y, I would do the following: bin them
> with some affine function, eg
>
> (lambda (x)
> (floor x bin-width))
But under this particular function, 41.9999 hashes to a different value
than 42.0001. I am trying to think about something quite different,
where any two keys within some delta of each other would map to the same
hash value. For example, with a delta of 0.5 the keys 41.8 and 42.2
would hash to the same value slot, and keys 42.1 and 42.5 would also map
to the the same value slot. But 41.8 and 42.5 would store separate values.
I think there might be rare utility for this weird notion of hashing.
What are the implementation efficiency issues? Anyone have any ideas?
How might the key hysteresis behavior bite the programmer?
> and simply use the bin as the key for the hash table, with the value
> as a list of numbers in this bin. Then for a particular y, I would
> retrieve the numbers in the same bin and the neighboring bins, and
> filter out those which are actually within epsilon of y. The
> "optimal" value of bin-width depends on your application, but since
> hash tables are quite efficient it won't make a whole lot of
> difference, so I would just make it some small multiple of epsilon.
Yes, something like this would implement the desired behavior. We should
speculate whether this behavior would have any useful semantics, and any
predictably non-hysteresis behavior.
Hysteresis: It seems to me that the hash table would have to remember
every key stored into it that is not shadowed on both sides by an
adjacent value, so that it can return the correct value when queried.
Consider with a delta of 0.5:
(setf (gethash 42.0 ht) :one)
(setf (gethash 42.3 ht) :two)
(setf (gethash 42.6 ht) :three)
Now:
(gethash 41.9 ht) => :two
(gethash 41.6 ht) => :one
(gethash 42.7 ht) => :three
Is this kind of hash table useful?
budden
I see that discussions goes out of topic. The idea of converting
everything to a list is just for:
i) visualization of clos objects net (there are reasons not to use
print for that).
ii) debugging. I had some "reference" net of objects and wanted to be
sure that my new net of objects is equivalent in some
sence to the reference one. The simplest equivalence is equal and the
simplest way to do that is to do that visually. It can also be done
with
printing-to-strings both trees in a listified form with *print-circle*
bound to t and comparing results. This looks like equal comparison,
but it is
better: equal would just loop if there are circular reference chains.
Yes, my method do not cover all possible cases of equivalence
definition. But making
something universal was not my intention.
Statement that what I did is pointless is wrong. I created a tool
which helped me to solve real-world task and saved me a significant
amount of
time.
Just in case I missed something I'm interested in other ways to
compare the nets of objects for the purpose of debugging and visualise
differences.
My initial question is still open too. Is there any prior art or my
approach is new? I dislike writing everything by myself, I prefer to
use
other's work. This approach is very lispy and evident and I don't
believe I was the first to do this.
I also have to note that some of those who criticised me:
i) didn't understand my intention which was stated explicitly at my
second post
ii) didn't try to find any use for listifying (it could also be
serialization of graphs).
iii) wasted their time writing pointless critics instead of trying to
understand my rationale and/or creating and sharing useful code
iv) wasted my time reading. Instead of reading pointless critics, I
could write and share some more useful code.
v) didn't do nothing new and useful
I suggest to hold a topic. The question in my topic was not "is
listifying pointless". It
was just: "where is the better library for listifying". If you think
that listifying is pointless, it is you personal opinion and
it does not interest me at all. If you can not add anything useful to
the topic, it is better to keep out.
> I don't understand: "approximately equal" is not a transitive relation and thus not a good concept for a hash table.
Yes. In context of the topic, we might use approximate equality for
testing. Say, we modify some number-crunching code. It can be modified
in a way that
numeric results are not reproduced verbatim. If we believe that old
method was correct, we can use approx-equal for testing if new method
is correct. We map old and
new code on some test cases and then compare results (e.g. lists) with
approx-equal. If we are to compare some converging sequences of
number, we might also want
to estimate some other mutual properties of results. E.g. we might
compare convergence speed.
Madhu
* "Steven M. Haflich" <g5_5l.9988$D32....@flpi146.ffdc.sbc.com> :
Wrote on Sun, 28 Dec 2008 22:31:34 -0800:
[snip]
I have encountered the need for this sort of "Associative Memory" when
dealing with `scatter codes' in GA, where you want to map a region of
the state space around a given point to the same value.
Another application I encountered is in computing [astrological] aspects
and transits from the ephemeris of planets.
Interesting aspects are specific angular distances between planets and
cusps or between planets themselves -- 30 degrees, 45, 60, 72,
etc. Stanadrd astrology prescribes complicating rules specifying what
the fuzz is when computing aspects.
The simpler problem: `given the positions of the planets and house cusps
in a chart [or two charts] find the interesting aspects [or transits]',
can be solved easily by 2 loops.
Now if you want to search for the specific times at which certain
aspects or transits occured, with experimentally refinable notions of
fuzz, and wish to do it efficiently, the hash table structure you
outline is helpful.
--
Madhu
Jerome Baum
> But under this particular function, 41.9999 hashes to a different
> value than 42.0001. I am trying to think about something quite
> different, where any two keys within some delta of each other would
> map to the same hash value. For example, with a delta of 0.5 the keys
> 41.8 and 42.2 would hash to the same value slot, and keys 42.1 and
> 42.5 would also map to the the same value slot. But 41.8 and 42.5
> would store separate values.
See, one issue here would be that 42.2 must then have the same
key as 42.4 and as 42.6 and as 42.8 -- all numbers would have the
same key. That is if you were to strictly follow this simple
rule.
A more effective rule is thus needed. I think a sort of "raster"
of number buckets may be effective, at twice the amount of
memory, as follows:
1. (floor n)
2. (floor (+ n 0.5))
> I think there might be rare utility for this weird notion of
> hashing. What are the implementation efficiency issues? Anyone have
> any ideas? How might the key hysteresis behavior bite the programmer?
>
> Is this kind of hash table useful?
One thing I think of immediately: Self-organizing maps. Having to
find the best matching unit would be an application to this sort
of hash table (though no doubt there are even better methods --
anybody?).
- Jerome
Jerome Baum
> I see that discussions goes out of topic.
You must be new here.
- Jerome
Pascal J. Bourguignon
> "Steven M. Haflich" <s...@alum.mit.edu> writes:
>
>> But under this particular function, 41.9999 hashes to a different
>> value than 42.0001. I am trying to think about something quite
>> different, where any two keys within some delta of each other would
>> map to the same hash value. For example, with a delta of 0.5 the keys
>> 41.8 and 42.2 would hash to the same value slot, and keys 42.1 and
>> 42.5 would also map to the the same value slot. But 41.8 and 42.5
>> would store separate values.
>
> See, one issue here would be that 42.2 must then have the same
> key as 42.4 and as 42.6 and as 42.8 -- all numbers would have the
> same key. That is if you were to strictly follow this simple
> rule.
>
> A more effective rule is thus needed. I think a sort of "raster"
> of number buckets may be effective, at twice the amount of
> memory, as follows:
>
> 1. (floor n)
> 2. (floor (+ n 0.5))
I fail to see how that would help with my numbers
(1.2 42.2 2.98e8 4.3210987e12 6.011e23 3.1415e31).
--
__Pascal Bourguignon__
Jerome Baum
> Jerome Baum <em...@jeromebaum.com> writes:
>> A more effective rule is thus needed. I think a sort of "raster"
>> of number buckets may be effective, at twice the amount of
>> memory, as follows:
>>
>> 1. (floor n)
>> 2. (floor (+ n 0.5))
>
> I fail to see how that would help with my numbers
> (1.2 42.2 2.98e8 4.3210987e12 6.011e23 3.1415e31).
Consider the context. I was quoting a statement where an epsilon
of 0.5 was discussed. In that context it is indeed helpful as we
need to consider the two buckets into which the number then falls
for comparison (a similar method to one suggested previously,
requiring three buckets to be considered but at half the memory
usage of my method).
- Jerome