Re: hash of circular list?

--===============1192764225925074657==
Content-Type: multipart/alternative; boundary="0000000000005200c50651fc193d"

--0000000000005200c50651fc193d
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Thanks.  This is an interesting issue.  Although we don't state it
explicitly in the Gauche documentation, default-hash is taken from srfi-128
which explicitly says it is not applicable to circular structures.

It will be intriguing if we can make it work with equal? hash table, as
equal? already covers circular structures.  However, making default-hash
work with equal? over circular structures doesn't seem trivial.  #0=3D(1 .
#0#) and #1=3D(1 1 . #1#) must produce the same hash value.

Next best thing I can do is to raise an error when we detect a circular
structure.  To do it generally, however, we lack the necessary parameter in
the API (each recursive hash call needs to pass the "seen object" table
along).  The cycle may be form across user-defined objects with custom hash
function, so we can't change the API.

We can detect cycles in limited cases (e.g. a cycle involving only pairs)
to catch a trivial mistakes, and let complex case diverge.







On Sat, May 16, 2026 at 10:25=E2=80=AFAM Jens Thiele <[email protected]> wrote=
:

> Hi,
>
> gosh> (use srfi-1)
> gosh> (default-hash (circular-list 1))
> =3D> endless loop
>
> best regards
> jens
>
> PS: maybe slightly related
> "Circular-safe compare"
> https://github.com/shirok/Gauche/issues/1125
>
>
> _______________________________________________
> Gauche-devel mailing list
> [email protected]
> https://lists.sourceforge.net/lists/listinfo/gauche-devel
>

--0000000000005200c50651fc193d
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_default" style=3D"font-size:large">Tha=
nks.=C2=A0 This is an interesting=C2=A0issue.=C2=A0 Although we don&#39;t s=
tate it explicitly in the Gauche documentation, default-hash is taken from =
srfi-128 which explicitly says it is not applicable to circular structures.=
</div><div class=3D"gmail_default" style=3D"font-size:large"><br></div><div=
 class=3D"gmail_default" style=3D"font-size:large">It will be intriguing if=
 we can make it work with equal? hash table, as equal? already=C2=A0covers =
circular structures.=C2=A0 However, making default-hash work with equal? ov=
er circular structures doesn&#39;t seem trivial.=C2=A0 #0=3D(1 . #0#) and #=
1=3D(1 1 . #1#) must produce the same hash value.</div><div class=3D"gmail_=
default" style=3D"font-size:large"><br></div><div class=3D"gmail_default" s=
tyle=3D"font-size:large">Next best thing I can do is to raise an error when=
 we detect a circular structure.=C2=A0 To do it generally, however, we lack=
 the necessary parameter in the API (each recursive hash call needs=C2=A0to=
 pass the &quot;seen object&quot; table along).=C2=A0 The cycle may be form=
 across user-defined objects with custom hash function, so we can&#39;t cha=
nge the API.</div><div class=3D"gmail_default" style=3D"font-size:large"><b=
r></div><div class=3D"gmail_default" style=3D"font-size:large">We can detec=
t cycles in limited cases (e.g. a cycle involving only pairs) to catch a tr=
ivial mistakes, and let complex case diverge.</div><div class=3D"gmail_defa=
ult" style=3D"font-size:large"><br></div><div class=3D"gmail_default" style=
=3D"font-size:large"><br></div><div class=3D"gmail_default" style=3D"font-s=
ize:large"><br></div><div class=3D"gmail_default" style=3D"font-size:large"=
><br></div><div class=3D"gmail_default" style=3D"font-size:large"><br></div=
><div class=3D"gmail_default" style=3D"font-size:large"><br></div></div><br=
><div class=3D"gmail_quote gmail_quote_container"><div dir=3D"ltr" class=3D=
"gmail_attr">On Sat, May 16, 2026 at 10:25=E2=80=AFAM Jens Thiele &lt;<a hr=
ef=3D"mailto:[email protected]">[email protected]</a>&gt; wrote:<br></div><blockq=
uote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1p=
x solid rgb(204,204,204);padding-left:1ex">Hi,<br>
<br>
gosh&gt; (use srfi-1)<br>
gosh&gt; (default-hash (circular-list 1))<br>
=3D&gt; endless loop<br>
<br>
best regards<br>
jens<br>
<br>
PS: maybe slightly related<br>
&quot;Circular-safe compare&quot;<br>
<a href=3D"https://github.com/shirok/Gauche/issues/1125" rel=3D"noreferrer"=
 target=3D"_blank">https://github.com/shirok/Gauche/issues/1125</a><br>
<br>
<br>
_______________________________________________<br>
Gauche-devel mailing list<br>
<a href=3D"mailto:[email protected]" target=3D"_blank">Gau=
[email protected]</a><br>
<a href=3D"https://lists.sourceforge.net/lists/listinfo/gauche-devel" rel=
=3D"noreferrer" target=3D"_blank">https://lists.sourceforge.net/lists/listi=
nfo/gauche-devel</a><br>
</blockquote></div>

--0000000000005200c50651fc193d--


--===============1192764225925074657==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline


--===============1192764225925074657==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

_______________________________________________
Gauche-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/gauche-devel

--===============1192764225925074657==--