hashcons

[Hendrik Boom]

Is there a way to run Racket so that every immuable cons is made with
a hashcons operation; i.e. it makes a new cons scel only if there
isn't already one in memory somewhere with the same car and cdr
values?

-- hendrik

[jackh...@gmail.com]

Not automatically, but you can make your own wrapper function around cons that interns them using a weak hash table and then you can use that wrapper function everywhere.

[Hendrik Boom]

On Sat, Sep 12, 2020 at 01:23:24PM -0700, jackh...@gmail.com wrote:
> Not automatically, but you can make your own wrapper function around cons
> that interns them using a weak hash table and then you can use that wrapper
> function everywhere.

True, but that would require rewriting list, and quasiquote, ans
others like that to use the hashcons.

Not impossible.

-- hendrik

>
> On Thursday, September 10, 2020 at 7:34:37 PM UTC-7 hen...@topoi.pooq.com
> wrote:
>
> > Is there a way to run Racket so that every immuable cons is made with
> > a hashcons operation; i.e. it makes a new cons scel only if there
> > isn't already one in memory somewhere with the same car and cdr
> > values?
> >
> > -- hendrik
> >
>

> --
> You received this message because you are subscribed to the Google Groups "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/7ed721c9-4ed2-47eb-b8bb-a30a1ed9125fn%40googlegroups.com.

[Tony Garnock-Jones]

On Sunday, September 13, 2020 at 12:41:15 AM UTC+2 hen...@topoi.pooq.com wrote:

True, but that would require rewriting list, and quasiquote, ans
others like that to use the hashcons.

Not impossible.

One potentially useful trick is to write a function `canonicalize` which deeply traverses the structure of its argument, rebuilding it if necessary to produce the canonical representative for each piece of substructure. Then you can `(canonicalize (map f xs))` without having to rewrite `map`, and it takes (asymptotically) the same time as it would if you did alter `map`.

Another thing to watch out for is that hashconsing via `equal?` can be quite expensive for things like hash tables. I used hashconsing extensively in the first implementation of Syndicate and ended up having to implement my own treaps to get good asymptotic performance with a hashconsed dictionary structure.

Cheers,

  Tony

 

[Hendrik Boom]

I would, ideally, only use hashcons on those cons-cells which had themselves
been hashconsed, so eq? would suffice.

-- hendrik

[Tony Garnock-Jones]

On Mon, 14 Sep 2020 at 14:18, Hendrik Boom <hen...@topoi.pooq.com> wrote:

I would, ideally, only use hashcons on those cons-cells which had themselves
been hashconsed, so eq? would suffice.

The challenge is checking to see whether a new allocation is required. Checking `eq?` of the cdr suffices, but seldom is `eq?` appropriate for the car, assuming you want `(eq? (hashcons (set) '()) (hashcons (set) '()))` and similar to hold. Canonicalize looks, roughly, like

(define (canonicalize c)

  (match c

    [(cons a d) (if (cell-exists-in-weak-table-with-car-and-cdr? a d) ;; (X)

                    (extract-and-return-existing-cell a d)

                    (intern-and-return-cons-of a (canonicalize d)))]

    [_ c]))

 

The line marked (X) will usually want to compare `a` with `equal?` and `d` with `eq?`.