Re: [racket-users] Re: hashcons
On Mon, 14 Sep 2020 at 14:18, Hendrik Boom 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?`. -- 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+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/CAM8fPiS0moqzAfDUdtH5aBx337Mt-TrWQkZ8EQro5HHWJtkEKg%40mail.gmail.com.
Re: [racket-users] Re: hashcons
On Mon, Sep 14, 2020 at 01:11:34AM -0700, Tony Garnock-Jones wrote: > 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. I would, ideally, only use hashcons on those cons-cells which had themselves been hashconsed, so eq? would suffice. -- 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+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/20200914121810.vsbo56odmxf7r4f6%40topoi.pooq.com.
Re: [racket-users] Re: hashcons
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 -- 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+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/8de04262-e1c3-44b4-83a0-1a0c637e3f47n%40googlegroups.com.
Re: [racket-users] Re: hashcons
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+unsubscr...@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. -- 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+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/20200912224106.dretb2jnz6rtf3yc%40topoi.pooq.com.
[racket-users] Re: hashcons
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. 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+unsubscr...@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.
