Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Ludovic Courtès]

Jan Nieuwenhuizen <janneke@gnu.org> skribis:

> (use-modules (srfi srfi-10))
>
> (define-reader-ctor 'hash
>        (lambda elems
>          (let ((table (make-hash-table)))
>            (for-each (lambda (elem)
>                        (apply hash-set! table elem))
>                      elems)
>            table)))

In this example, you want the reader extension to be available at
compile time, and not necessarily at run time.  However, by writing the
code as is, the reader extension is available only at run time, hence
the error.

To require evaluation of the ‘define-reader-ctor’ form at compile time,
change the code to (info "(guile) Eval When"):

--8<---------------cut here---------------start------------->8---
(eval-when (expand)
  (define-reader-ctor 'hash
    (lambda elems
      (let ((table (make-hash-table)))
        (for-each (lambda (elem)
                    (apply hash-set! table elem))
                  elems)
        table))))
--8<---------------cut here---------------end--------------->8---

Now, you’ll get this error:

--8<---------------cut here---------------start------------->8---
$ guile ~/tmp/hash.scm
;;; note: auto-compilation is enabled, set GUILE_AUTO_COMPILE=0
;;;       or pass the --no-auto-compile argument to disable.
;;; compiling /home/ludo/tmp/hash.scm
;;; WARNING: compilation of /home/ludo/tmp/hash.scm failed:
;;; ERROR: build-constant-store: unrecognized object #<hash-table 187ecc0 3/31>
cat
--8<---------------cut here---------------end--------------->8---

The problem here is that the reader extension above returns (at compile
time) a hash table.  However, a hash table as such cannot appear in
source code text, hence the error.

Instead, you’d want the reader extension to return source code that
constructs the hash table.  First, a macro:

--8<---------------cut here---------------start------------->8---
(define-syntax build-hash-table
  (syntax-rules ()
    ((_ table (key value) rest ...)
     (begin
       (hash-set! table key value)
       (build-hash-table table rest ...)))
    ((_ table)
     table)))

(define-syntax-rule (hash-table (key value) ...)
  (let ((table (make-hash-table)))
    (build-hash-table table (key value) ...)))
--8<---------------cut here---------------end--------------->8---

With that macro, we get:

--8<---------------cut here---------------start------------->8---
scheme@(guile-user)> ,expand (hash-table ("a" 1) ("b" 2) ("c" 3))
$2 = (let ((table (make-hash-table)))
  (hash-set! table "a" 1)
  (begin
    (hash-set! table "b" 2)
    (begin (hash-set! table "c" 3) table)))
--8<---------------cut here---------------end--------------->8---

Now, if in addition you want #, syntax for that, you can write:

--8<---------------cut here---------------start------------->8---
(eval-when (expand)
  (define-reader-ctor 'hash
    (lambda elems
      `(hash-table ,@elems))))

(define (animal->family animal)
  (hash-ref #,(hash ("tiger" "cat")
                    ("lion"  "cat")
                    ("wolf"  "dog"))
            animal))

(display (animal->family "lion"))
(newline)
--8<---------------cut here---------------end--------------->8---

But I’m not sure the #, extension is worthwhile here.

HTH,
Ludo’.

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Jan Nieuwenhuizen]

[-- Attachment #1: Type: text/plain, Size: 1037 bytes --]

Ludovic Courtès writes:

Hi,

> In this example, you want the reader extension to be available at
> compile time, and not necessarily at run time.  However, by writing the
> code as is, the reader extension is available only at run time, hence
> the error.

Alright, that makes sense when you think about it...

> To require evaluation of the ‘define-reader-ctor’ form at compile time,
> change the code to (info "(guile) Eval When"):

Wow, many thanks!  This works for me; would it be nice to have some of
this more explicitly in the srfi-10 manual?

This is great, I am using this now for easy communication with json
and therefore I also want to pretty-print hash tables this way.

For now, I copied (ice-9 pretty-print) and applied the patch below,
I did not find a way to hook into, or just override, the inner (wr)
procedure.

How do I get pretty-print to produce non-opaque hash tables using this
#, hash read syntax than to copy all of (ice-9 pretty-print) or carry
this diff?

Greetings, Jan


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Have-pretty-print-write-non-opaque-srfi-10-hash-hash.patch --]
[-- Type: text/x-diff, Size: 1047 bytes --]

From 16768de55f4f2c79bf38af93ca907772c71a603a Mon Sep 17 00:00:00 2001
From: Jan Nieuwenhuizen <janneke@gnu.org>
Date: Thu, 31 Jul 2014 08:19:17 +0200
Subject: [PATCH] Have pretty-print write non-opaque srfi-10 #,(hash hash
 tables.

	* module/ice-9/pretty-print.scm (generic-write): write hash tables
        in srfi-10 hash-comma read syntax.
---
 module/ice-9/pretty-print.scm | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/module/ice-9/pretty-print.scm b/module/ice-9/pretty-print.scm
index 007061f..a5a590d 100644
--- a/module/ice-9/pretty-print.scm
+++ b/module/ice-9/pretty-print.scm
@@ -64,6 +64,8 @@
       (match obj
         (((or 'quote 'quasiquote 'unquote 'unquote-splicing) body)
          (wr body (out (read-macro-prefix obj) col)))
+        ((? hash-table?) (wr (cons 'hash (hash-map->list list obj)) 
+                             (out "#," col)))
         ((head . (rest ...))
          ;; A proper list: do our own list printing so as to catch read
          ;; macros that appear in the middle of the list.
-- 
1.9.1


[-- Attachment #3: Type: text/plain, Size: 154 bytes --]


-- 
Jan Nieuwenhuizen <janneke@gnu.org> | GNU LilyPond http://lilypond.org
Freelance IT http://JoyofSource.com | Avatar®  http://AvatarAcademy.nl  

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Neil Jerram]

On 2014-07-30 23:27, Jan Nieuwenhuizen wrote:
> Ludovic Courtès writes:
> 
> Hi,
> 
>> In this example, you want the reader extension to be available at
>> compile time, and not necessarily at run time.  However, by writing 
>> the
>> code as is, the reader extension is available only at run time, hence
>> the error.
> 
> Alright, that makes sense when you think about it...
> 
>> To require evaluation of the ‘define-reader-ctor’ form at compile 
>> time,
>> change the code to (info "(guile) Eval When"):
> 
> Wow, many thanks!  This works for me; would it be nice to have some of
> this more explicitly in the srfi-10 manual?

This same problem just came up in another thread, too (look for 
"ossaulib").  In that case the thing that needed to be enclosed in an 
'eval-when' form was adding a directory to the load path.

I wonder about possibly having some magic that would automatically match 
certain top-level forms and evaluate them at compile time.  The case for 
this for 'define-reader-ctor' feels quite strong.  For the load path 
case, it feels too hacky to try to recognize patterns like '(set! 
%load-path (append %load-path ...))', but perhaps OK if we defined an 
'add-to-load-path' procedure and applied the magic to that.

What do you think?  Would that be too magical?

Regards,
      Neil

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Taylan Ulrich Bayirli/Kammer]

Neil Jerram <neil@ossau.homelinux.net> writes:

> I wonder about possibly having some magic that would automatically
> match certain top-level forms and evaluate them at compile time.  The
> case for this for 'define-reader-ctor' feels quite strong.  For the
> load path case, it feels too hacky to try to recognize patterns like
> (set! %load-path (append %load-path ...))', but perhaps OK if we
> defined an 'add-to-load-path' procedure and applied the magic to that.

We already have an 'add-to-load-path' syntax.  That way it doesn't need
any special magic since it can just expand to an `eval-when' usage but
apparently for some reason it doesn't do that at the moment (2.0.11):

scheme@(guile-user)> ,expand (add-to-load-path "foo")
(set! (@@ (guile) %load-path)
      ((@@ (guile) cons) "foo" (@@ (guile) %load-path)))

Taylan

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Neil Jerram]

On 2014-08-14 11:27, Taylan Ulrich Bayirli/Kammer wrote:
> Neil Jerram <neil@ossau.homelinux.net> writes:
> 
>> I wonder about possibly having some magic that would automatically
>> match certain top-level forms and evaluate them at compile time.  The
>> case for this for 'define-reader-ctor' feels quite strong.  For the
>> load path case, it feels too hacky to try to recognize patterns like
>> (set! %load-path (append %load-path ...))', but perhaps OK if we
>> defined an 'add-to-load-path' procedure and applied the magic to that.

> We already have an 'add-to-load-path' syntax.  That way it doesn't need
> any special magic since it can just expand to an `eval-when' usage

Ah, good, thanks for pointing that out.

> but
> apparently for some reason it doesn't do that at the moment (2.0.11):
> 
> scheme@(guile-user)> ,expand (add-to-load-path "foo")
> (set! (@@ (guile) %load-path)
>       ((@@ (guile) cons) "foo" (@@ (guile) %load-path)))
> 
> Taylan

I'm not sure what that demonstrates.  add-to-load-path _does_ appear to 
work for me as hoped (and documented) when used in a situation like that 
of the recent ossaulib thread - i.e. where a top level script wants to 
extend the load path and then load modules from there:

-----------ctest.scm------------
(define-module (ctest)
   #:export (square))

(define (square x) (* x x))
-----------ctest.scm------------

-----------ctst.scm------------
(add-to-load-path "/home/neil")
(use-modules (ctest))
(display (square 5))
(newline)
-----------ctst.scm------------


neil@nj-debian-7:~$ guile -s ctst.scm
;;; note: auto-compilation is enabled, set GUILE_AUTO_COMPILE=0
;;;       or pass the --no-auto-compile argument to disable.
;;; compiling /home/neil/ctst.scm
;;; compiling /home/neil/ctest.scm
;;; compiled 
/home/neil/.cache/guile/ccache/2.0-LE-8-2.0/home/neil/ctest.scm.go
;;; compiled 
/home/neil/.cache/guile/ccache/2.0-LE-8-2.0/home/neil/ctst.scm.go
25

Regards,
      Neil

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Taylan Ulrich Bayirli/Kammer]

Neil Jerram <neil@ossau.homelinux.net> writes:

> I'm not sure what that demonstrates.  add-to-load-path _does_ appear
> to work for me as hoped (and documented) when used in a situation like
> that of the recent ossaulib thread - i.e. where a top level script
> wants to extend the load path and then load modules from there:

Never mind, 'eval-when' is a macro too of course so ',expand' makes it
"disappear."

Taylan

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Ludovic Courtès]

Neil Jerram <neil@ossau.homelinux.net> skribis:

> I wonder about possibly having some magic that would automatically
> match certain top-level forms and evaluate them at compile time.  The
> case for this for 'define-reader-ctor' feels quite strong.  For the
> load path case, it feels too hacky to try to recognize patterns like
> (set! %load-path (append %load-path ...))', but perhaps OK if we
> defined an 'add-to-load-path' procedure and applied the magic to that.
>
> What do you think?  Would that be too magical?

Yes, I think so.  :-)

Separation of concerns means that the compiler does not have to know
about SRFI-10 or any other library, but instead just provides
‘eval-when’ as a mechanism to express what we want in such cases.

Thanks,
Ludo’.

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Ludovic Courtès]

Jan Nieuwenhuizen <janneke@gnu.org> skribis:

> How do I get pretty-print to produce non-opaque hash tables using this
> #, hash read syntax than to copy all of (ice-9 pretty-print) or carry
> this diff?

The problem is that SRFI-10 itself does not specify an external
representation for hash tables, nor does Guile.  Thus this patch cannot
be applied.

Another problem is that (ice-9 pretty-print) is not extensible.  It
would be ideal if one could extend it with new pretty-printing methods.
Would you like to work on such a generic mechanism?

Ideally ‘pretty-print’ would have an extra keyword parameter that would
allow users to pass a list of predicate/printer pairs.  There could be a
‘pretty-printer-method’ procedure (rather than ‘cons’) to construct such
a pair.

Thanks,
Ludo’.

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Jan Nieuwenhuizen]

Ludovic Courtès writes:

> The problem is that SRFI-10 itself does not specify an external
> representation for hash tables, nor does Guile.  Thus this patch cannot
> be applied.

Yes, I understand that...Still, "wouldn't it be nice" if Scheme/Guile
had something that javascript has, in JSON hash tables are "simply"

   {"key0": value, "key1": value}

and although that's in some way much uncooler and restricted and set-in
stone wrt Scheme readers and SRFI-10...you *are* able to stream and
communicate objects over ascii/utf-8, unlike #,(hash ...

Here we are with a unimaginable cool srfi-10 reader extension, but we
cannot really use it to communicate.

> Another problem is that (ice-9 pretty-print) is not extensible.  It
> would be ideal if one could extend it with new pretty-printing methods.
> Would you like to work on such a generic mechanism?

Yes, for now I agree that seems to be the only and most pragmatic
solution.  I would like to look into that.

> Ideally ‘pretty-print’ would have an extra keyword parameter that would
> allow users to pass a list of predicate/printer pairs.  There could be a
> ‘pretty-printer-method’ procedure (rather than ‘cons’) to construct such
> a pair.

That sounds nice.  I will look into it.  Thanks for the suggestions!

Greetings, Jan

-- 
Jan Nieuwenhuizen <janneke@gnu.org> | GNU LilyPond http://lilypond.org
Freelance IT http://JoyofSource.com | Avatar®  http://AvatarAcademy.nl  

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Marko Rauhamaa]

Jan Nieuwenhuizen <janneke@gnu.org>:

> Still, "wouldn't it be nice" if Scheme/Guile had something that
> javascript has, in JSON hash tables are "simply"
>
>    {"key0": value, "key1": value}

You mean, like,

   (hash-map->list cons mytable)


Marko

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Jan Nieuwenhuizen]

Marko Rauhamaa writes:

>>    {"key0": value, "key1": value}
>
> You mean, like,
>
>    (hash-map->list cons mytable)

No; when fed to `read', that produces a list, right?  Lists, in JSON
would be represented as arrays

   [value0, value1 ..., valuen]

*that* we can communicate using pretty-print and read.

I mean an standardized, ascii/utf-8 non-opaque (#<hash table xyz>)
representation of hash tables, something like

    #,(hash (key0 value0) .. (keyn valuen))

that upon `read', produces a hash table.

Greetings,
Jan

-- 
Jan Nieuwenhuizen <janneke@gnu.org> | GNU LilyPond http://lilypond.org
Freelance IT http://JoyofSource.com | Avatar®  http://AvatarAcademy.nl  

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Ludovic Courtès]

Jan Nieuwenhuizen <janneke@gnu.org> skribis:

>     #,(hash (key0 value0) .. (keyn valuen))
>
> that upon `read', produces a hash table.

Just use your own ‘read-hash-table’ instead of ‘read’ and be done with
it, no?  :-)

That’s what I do in similar situations: simple serializer/deserializer
to/from sexps.

Ludo’.

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Marko Rauhamaa]

Jan Nieuwenhuizen <janneke@gnu.org>:

> Marko Rauhamaa writes:
>
>>>    {"key0": value, "key1": value}
>>
>> You mean, like,
>>
>>    (hash-map->list cons mytable)
>
> No; when fed to `read', that produces a list, right?

It produces a mapping in the elegant, classical lisp format: the assoc
list.

A hash table is just an implementation of that mapping. There's barely a
better way to externally represent the mapping than an assoc list.

I can use a hash table, send an assoc list to communicate the mapping to
a peer, who can then decide to store the mapping in an assoc list,
balanced tree, hash table, object database or any other suitable
internal data structure. Forcing the recipient to read in a hash table
would be pointless and, frankly, obnoxious.

> I mean an standardized, ascii/utf-8 non-opaque (#<hash table xyz>)
> representation of hash tables, something like
>
>     #,(hash (key0 value0) .. (keyn valuen))
>
> that upon `read', produces a hash table.

I know what you mean. I just can't imagine much of a practical need for
it.

If you want to use pretty-printing to dump the internal data structures
so you can recreate them later, that wouldn't work anyway. Consider:

   (define b (cons 'x 'x))
   (define a (cons b b))
   (pretty-print a)
   => ((x . x) x . x)
   (define c '((x . x) x . x))
   (eq? (car a) (cdr a))
   => #t
   (eq? (car c) (cdr c))
   => #f


Marko

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Mark H Weaver]

Jan Nieuwenhuizen <janneke@gnu.org> writes:
> I mean an standardized, ascii/utf-8 non-opaque (#<hash table xyz>)
> representation of hash tables, something like
>
>     #,(hash (key0 value0) .. (keyn valuen))
>
> that upon `read', produces a hash table.

This has been proposed several times before, and although it generally
sounds like a nice idea, there are unfortunately several complications:

1. There are at least three different kinds of hash tables in Guile:
   native legacy Guile hash tables, SRFI-69 hash tables, and R6RS hash
   tables.

2. For each of these three kinds of hash tables, they are further
   divided into multiple flavors depending on the equality predicate and
   associated hash function: eq?, eqv?, equal?, and potentially other
   kinds defined by the user.

3. If the equality predicate is eq? or eqv?, then there's no way to
   write a hash table and then read it back in without losing
   information.  For both of these kinds of hash tables, mutable objects
   that produce the same output can either be the same object or
   different objects.

4. Unlike SRFI-69 and R6RS hash tables, native legacy Guile hash tables
   do not keep a record of which equality predicate is used to store
   their elements.  Instead, it is the user's responsibility to use the
   correct accessors (hash-ref, hashq-ref, hashv-ref, hashx-ref)
   mutators, and other procedures.  It is even possible to use both
   hashq-set! and hashv-set! on the same hash table, although it's
   almost certainly a bad idea to do so.  This means that when asked to
   print a native hash table, Guile doesn't have the needed information
   to print what equality predicate the hash table uses.

I should also mention that it would not be enough to allow 'read' to
read hash tables.  To compile a source file containing literal hash
tables, we'd also need to add support to our assembler and loader to
serialize hash tables to .go files and load them back in.

Regarding complication #1, at some point I'd like to at least merge
SRFI-69 and R6RS hash tables into the same underlying data type.  How to
merge those with native Guile hash tables is not obvious because of
complication #4.  One idea is to record the equality predicate in the
hash table, but allow the predicate to be "not yet determined" when a
hash table is created by 'make-hash-table' before its first element is
added.

If that problem was solved, then complication #2 could be handled by
annotating the external representation with the equality predicate.

I see no good solution to complication #3, but I suppose we could
document that information can be lost.

      Mark

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Ludovic Courtès]

Jan Nieuwenhuizen <janneke@gnu.org> skribis:

> Ludovic Courtès writes:
>
>> The problem is that SRFI-10 itself does not specify an external
>> representation for hash tables, nor does Guile.  Thus this patch cannot
>> be applied.
>
> Yes, I understand that...Still, "wouldn't it be nice" if Scheme/Guile
> had something that javascript has, in JSON hash tables are "simply"
>
>    {"key0": value, "key1": value}

Yes, it would.

But the beauty of Scheme is that the language can be extended to support
that, like with the ‘hash-table’ macro suggested at
<http://lists.gnu.org/archive/html/guile-user/2014-07/msg00009.html>.

> and although that's in some way much uncooler and restricted and set-in
> stone wrt Scheme readers and SRFI-10...you *are* able to stream and
> communicate objects over ascii/utf-8, unlike #,(hash ...

If the goal is to serialize/unserialize things, then the best option is
to devise an external representation, say:

  (hash-table (key0 value0) ...)

And then have ‘read-hash-table’ and ‘write-hash-table’ procedures
(rather than pass arbitrary sexps read from the wire to ‘eval’.)

> Here we are with a unimaginable cool srfi-10 reader extension, but we
> cannot really use it to communicate.

SRFI-10 is cool to reduce typing, but I’m not convinced it really helps here.

Ludo’.

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Panicz Maciej Godek]

2014-08-13 21:59 GMT+02:00 Jan Nieuwenhuizen <janneke@gnu.org>:
> Ludovic Courtès writes:
>
>> The problem is that SRFI-10 itself does not specify an external
>> representation for hash tables, nor does Guile.  Thus this patch cannot
>> be applied.
>
> Yes, I understand that...Still, "wouldn't it be nice" if Scheme/Guile
> had something that javascript has, in JSON hash tables are "simply"
>
>    {"key0": value, "key1": value}

I have been thinking about that issue a lot, and concluded that it
wouldn't be "the Scheme way".
Scheme already has a nice representation for associactions, namely the
assoc lists. However, they are a bit problematic, because they are
ordered by nature and hence there's not much one can do with their
linear access time.

The proper solution, I believe, is to provide some means to create
unordered collections (i.e. sets or multisets). Some hints for
constructing such collections were given by Daniel Friedman and
reminded recently (like 10 years ago ;]) in Guy Steele's talk for
Friedman's 60th birthday:
http://www.youtube.com/watch?v=IHP7P_HlcBk

After that, a paper came out which described that idea in greater detail:
http://projects.csail.mit.edu/wiki/pub/JoeNear/FernMonad/frons.pdf

Anyway, I think it would be nice to provide a notation for unordered
collections in Scheme, so that the associations, written as '{(key .
value) ...}, could eventually be optimized and perhaps implemented as
hash tables internally in some cases.

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Marko Rauhamaa]

Panicz Maciej Godek <godek.maciek@gmail.com>:

> Scheme already has a nice representation for associactions, namely the
> assoc lists. However, they are a bit problematic, because they are
> ordered by nature and hence there's not much one can do with their
> linear access time.

When we are talking about the representation of a mapping, it will be a
full content dump, thus O(n) regardless. You don't gain anything by
adding substructure to the assoc list.

When you read in the collection, you can put it in the data structure of
your choice (with alist->hash-table, for example).

Sexps are perfectly suitable to represent any imaginable data.

Circular sexps create funny effects in guile, though. Try inputting

   '(1 . #0#) 

to the (guile-1.8) reader.

Unfortunately, even

   (define a '(1 . #0#))

fails to finish.

Compare this with elisp, which is perfectly happy with:

   (setq a '#0=(1 . #0#))


Marko

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Panicz Maciej Godek]

2014-08-14 11:53 GMT+02:00 Marko Rauhamaa <marko@pacujo.net>:
>> Scheme already has a nice representation for associactions, namely the
>> assoc lists. However, they are a bit problematic, because they are
>> ordered by nature and hence there's not much one can do with their
>> linear access time.
>
> When we are talking about the representation of a mapping, it will be a
> full content dump, thus O(n) regardless. You don't gain anything by
> adding substructure to the assoc list.

We're talking about access time, so in this particular case -- about
assoc-ref and the like; not about printing. And about having an
efficient representation for sets, because obviously sets can be
represented using lists as well, although inefficiently.

> When you read in the collection, you can put it in the data structure of
> your choice (with alist->hash-table, for example).

Of course I can. But that isn't something that I wish to do. It simply
adds another layer of indirection, which is irrelevant to programmer's
intention. Using dictionaries is programmers' daily bread, yet Scheme
has no common way for doing that (unlike Perl, PHP, Python,
JavaScript, Clojure and other popular languages).

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Marko Rauhamaa]

Panicz Maciej Godek <godek.maciek@gmail.com>:

> Using dictionaries is programmers' daily bread, yet Scheme has no
> common way for doing that (unlike Perl, PHP, Python, JavaScript,
> Clojure and other popular languages).

I disagree. S-expressions far surpass whatever the others have to offer.


Marko

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Panicz Maciej Godek]

2014-08-14 12:36 GMT+02:00 Marko Rauhamaa <marko@pacujo.net>:
> Panicz Maciej Godek <godek.maciek@gmail.com>:
>
>> Using dictionaries is programmers' daily bread, yet Scheme has no
>> common way for doing that (unlike Perl, PHP, Python, JavaScript,
>> Clojure and other popular languages).
>
> I disagree. S-expressions far surpass whatever the others have to offer.

You disagree on which point exactly?
- that using dictionaries is programmers' daily bread?
- that Perl, PHP, Python, JavaScript, Clojure and other popular
languages offer a common way for using dictionaries? or
- that Scheme has no common way for using dictionaries?

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Marko Rauhamaa]

Panicz Maciej Godek <godek.maciek@gmail.com>:

>> I disagree. S-expressions far surpass whatever the others have to offer.
>
> You disagree on which point exactly?
> - that using dictionaries is programmers' daily bread?

No, we are talking about the external representation of hash tables. I'm
saying the alist format is sufficient to communicate the abstract
contents of hash tables or any other mapping. You don't need any new
representation format for hash tables -- or I can't think of a use case.


Marko

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Panicz Maciej Godek]

2014-08-14 14:59 GMT+02:00 Marko Rauhamaa <marko@pacujo.net>:
> Panicz Maciej Godek <godek.maciek@gmail.com>:
>
>>> I disagree. S-expressions far surpass whatever the others have to offer.
>>
>> You disagree on which point exactly?
>> - that using dictionaries is programmers' daily bread?
>
> No, we are talking about the external representation of hash tables. I'm
> saying the alist format is sufficient to communicate the abstract
> contents of hash tables or any other mapping. You don't need any new
> representation format for hash tables -- or I can't think of a use case.

I agree that it is sufficient. It's just that it isn't handy.
It's more succinct to write

x = {a : 5, b : 10} ...

or

(let ((x '{(a . 5)(b . 10)}))
  ...)

or

(let ((x '((a . 5)(b . 10))))
  ...)

than

(let ((x (alist->hash-table '((a . 5)(b . 10)))))
  ...)

Also, there's less that you (as a programmer) need to memoize, because
otherwise you'd need to check the documentation if it's
alist->hash-table or alist->hash-map or something else. Furthermore,
using alist->hash-table and hash-table->alist adds no value to your
program -- it's there only to optimize lookups, compared to assoc-ref
and assoc-set!, and essentialy has no impact on the semantics of your
program.

(however, weak hash-tables are an exception, because they represent a
concept that wouldn't otherwise be representable using alists)

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Taylan Ulrich Bayirli/Kammer]

Marko Rauhamaa <marko@pacujo.net> writes:

> Panicz Maciej Godek <godek.maciek@gmail.com>:
>
>> Using dictionaries is programmers' daily bread, yet Scheme has no
>> common way for doing that (unlike Perl, PHP, Python, JavaScript,
>> Clojure and other popular languages).
>
> I disagree. S-expressions far surpass whatever the others have to offer.
>
>
> Marko

To be fair, when your read syntax makes dictionaries explicit, you get
an additional bit of "safety" in your program because if you receive a
dictionary where a list was expected then the list-ref will error and
make the problem surface, whereas if you get an alist you can list-ref
it and have the program keep running a bit farther (maybe to the end,
producing wrong output).

(I've been bitten by this in PHP once where associative arrays are also
just arrays and some stupid web interface delivered me a single assoc
array where it should have delivered an array with one assoc array in
it.)

On the other hand, if you just implement full validation which walks
your input and turns all expected alists into suitable record types
(think DTD) then it's about equally safe either way I guess.  That is
the ideal long-term solution, validating most of your input as soon as
it's received, and preventing silly mistakes like typos in alist keys
because instead you use accessor procedures on records.

All in all, having to use alists for hash tables can be an annoyance
when you don't use eager input validation; it forces you to use extra
alist->hash-table and hash-table->alist calls where you could otherwise
just read and write an object if all it contains is lists, vectors, and
hash tables, and it can cause some bugs to remain hidden for longer.

Taylan

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Marko Rauhamaa]

Taylan Ulrich Bayirli/Kammer <taylanbayirli@gmail.com>:

> To be fair, when your read syntax makes dictionaries explicit, you get
> an additional bit of "safety" [...]
> (I've been bitten by this [...]
>
> On the other hand, if you just implement full validation [...]

Yes, validation is a much more generic issue that can be used for all
kinds of bounds-checks and interrelationships.

On the other hand, I wouldn't put too much emphasis into validation (as
in, none at all). For example, I have customized emacs with all kinds of
lisp data structures. None of those data structures are validated by the
respective emacs modules; they are simply obeyed. Typos create errors
and misbehaviors -- so I must fix them, simple as that.

> All in all, having to use alists for hash tables can be an annoyance
> when you don't use eager input validation; it forces you to use extra
> alist->hash-table and hash-table->alist calls where you could
> otherwise just read and write an object if all it contains is lists,
> vectors, and hash tables, and it can cause some bugs to remain hidden
> for longer.

A hash table is an optimized, internal lookup object. It is not a
meaningful representation format. An AVL tree and a hash table should
have identical external representations in almost all cases. Thus, my
implementation would have to make the translation on input anyway.


Marko


PS Speaking of AVL trees, my AVL tree implementation is bitten by the
apparent lack of a numeric object identifier in guile. Python has the
id() function that can be used to sort interned objects effectively. In
guile, I have to use

   (lambda (sym1 sym2)
     (string< (symbol->string sym1)
              (symbol->string sym2)))

instead of something like:

   (lambda (sym1 sym2)
     (< (id sym1)
        (id sym2)))

or even:

   below?

(in analogy with eq?).


Marko

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Taylan Ulrich Bayirli/Kammer]

Marko Rauhamaa <marko@pacujo.net> writes:

> A hash table is an optimized, internal lookup object. It is not a
> meaningful representation format. An AVL tree and a hash table should
> have identical external representations in almost all cases. Thus, my
> implementation would have to make the translation on input anyway.

If your program cares about specialized data structures like that then
yes, but often one just wants a generic "dictionary" type with O(1)
lookup, whatever the details.

Though when I think of it, often I would be fine with O(n) too and could
use alists in my code to begin with.  As I said, I just think it's a
minor annoyance, not having a "go to" dictionary type that covers 90% of
use cases and can be serialized as well.

Typos in keys is a bigger problem; having the compiler tell me I
mistyped the name of an accessor is much better than having an exception
thrown somewhere, sometime, and having to debug a little until I find
out it was just a typo!  Hence input-time validation is generally the
way to go IMO.  (Or maybe the relative difficulty of debugging
Objective-C, the language I have to use at work, is making me biased.)

> PS Speaking of AVL trees, my AVL tree implementation is bitten by the
> apparent lack of a numeric object identifier in guile. Python has the
> id() function that can be used to sort interned objects effectively.

There is (pointer-address (object-pointer <obj>)) if that helps.
(Nonstandard Scheme of course.)

Taylan

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Marko Rauhamaa]

Taylan Ulrich Bayirli/Kammer <taylanbayirli@gmail.com>:

> Though when I think of it, often I would be fine with O(n) too and could
> use alists in my code to begin with.

Yes. In my recent tests, I found (assq-ref) was twice as fast as
(hashq-ref) when there were 100 entries even when I made the hash table
quite large (1000 entries IIRC).

> There is (pointer-address (object-pointer <obj>)) if that helps.
> (Nonstandard Scheme of course.)

Thanks for the tip. Unfortunately, I couldn't locate those on my guile
installation.


Marko

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Taylan Ulrich Bayirli/Kammer]

Marko Rauhamaa <marko@pacujo.net> writes:

> Yes. In my recent tests, I found (assq-ref) was twice as fast as
> (hashq-ref) when there were 100 entries even when I made the hash
> table quite large (1000 entries IIRC).

Do you mean the averages?  For me, accessing the *first* entry of an
alist already seems to be almost as slow as accessing any entry of a
hash table, and accessing the 100th about thrice as slow.

> I couldn't locate those on my guile installation.

They're in (system foreign).

You can hit 'i' in GNU Info to find a variable or other keyword, though
I just had to notice that the intro node on the FFI, "(guile) Foreign
Function Interface", doesn't mention (system foreign).  Our manual seems
to generally lack in telling the user what module needs to be loaded for
what...

Taylan

Re: cannot compile: srfi-10 define-reader-ctor 'hash '#,(

[Marko Rauhamaa]

Taylan Ulrich Bayirli/Kammer <taylanbayirli@gmail.com>:

> Marko Rauhamaa <marko@pacujo.net> writes:
>
>> Yes. In my recent tests, I found (assq-ref) was twice as fast as
>> (hashq-ref) when there were 100 entries even when I made the hash
>> table quite large (1000 entries IIRC).
>
> Do you mean the averages?

I was looking for the 50th entry.

> For me, accessing the *first* entry of an alist already seems to be
> almost as slow as accessing any entry of a hash table, and accessing
> the 100th about thrice as slow.

Ok. I ran the test again, with a couple of parameter settings this time
round:

   ===================================================
   Data Structure    # Entries   Look-up Duration (µs)
   ===================================================
   hash-table           2000           0.37
   alist                2000           5.88
   AVL tree             2000          15.65
   hash-table            100           0.35
   alist                 100           0.31
   AVL tree              100          11.09
   ===================================================

The entry that was looked up was the middle element. The lookup was
performed 1,000,000 times. The AVL tree was wholly implemented in
scheme.

So the alist wasn't "twice as fast". Must have been with fewer entries.


Marko