Re: plists, alists, and hashtables

Re: plists, alists, and hashtables

[Ted Zlatanov]

On Wed, 05 Aug 2015 20:40:21 +0100 Robert Thorpe <rt@robertthorpeconsulting.com> wrote: 

RT> As Pascal mentioned, we only have a very small number of characters left
RT> to use for read syntax.

RT> You can't just consider one proposal alone.  Just because something is
RT> useful doesn't mean that it's useful enough to burn a character or two
RT> for.  It has to be compared to alternatives.

OK, I understand your viewpoint.  My goal is not to burn characters but
to make it easy to create a map in ELisp.

RT> There may be alternatives though.  For example, instead of:
RT> #s(hash-table size 65 test eql rehash-size 1.5 rehash-threshold 0.8 data ())

RT> We could have a shorthand, perhaps #s(h data)

That's all right, but I would probably prefer a Unicode pair of
characters.  In 2015, that's going to inconvenience very few people.

RT> Like Pascal I think alists are generally a good idea.  People who don't
RT> understand the performance implications of them won't understand those
RT> of hash-maps either.  Especially when things are done per key.

RT> In an editor the vast majority of maps are likely to contain only a few
RT> variables.  A few years ago I made a program that examined every Emacs
RT> variable that ended in "alist".  Almost all of them were short.  Only a
RT> handful were long enough to cause performance issues.

I see what you mean. The benefit to the users who use a hypothetical new
map syntax would be mostly code readability, because alists and plists
are not as readable as a true map syntax.  Is that enough to justify it?
If it's not obtrusive and doesn't burn reader characters, I think so.

So as a first cut, maybe «(k1 . v1) (k2 . v2)» and ««(k1 . v1) (k2 .
v2)»» would be a good syntax (equal and eql versions respectively),
simply converted to the appropriate #s(hash-table ...) syntax?

RT> If a hash-map type were used then there could be a bit to signify if
RT> it's *really* a hash.  I've heard that some of the scripting languages
RT> are doing this because they've found what I found; that most maps
RT> contain so few elements that hashing just makes things slower.  But, the
RT> bit would have to be tested before every map operation.

I think the bit check performance penalty would be insignificant, and
that the backend implementation can adapt to use lists for small maps.
In any case, using these would be voluntary, people can still use the
usual alists and plists.

Ted

Re: plists, alists, and hashtables

[Stefan Monnier]

RT> There may be alternatives though.  For example, instead of:
RT> #s(hash-table size 65 test eql rehash-size 1.5 rehash-threshold 0.8 data ())
RT> We could have a shorthand, perhaps #s(h data)

Is it really sufficiently better than the currently supported syntaxes
such as

   #s(hash-table data (a 2 b 3))

or

   ((a . 2) (b . 3))

?  I think it's going to be hard to convince that the few use cases will
be enough to justify all the work.


        Stefan

RE: plists, alists, and hashtables

[Drew Adams]

> So as a first cut, maybe <(k1 . v1) (k2 . v2)> and
> <<(k1 . v1) (k2 . v2)>> would be a good syntax

The last thing we need in Emacs Lisp is to gratuitously hard-code
such syntax.  Half the point of Lisp is to let people define DSLs,
including their syntax.

Unfortunately, in Emacs Lisp we do not (yet) have reader macros.
But that is all the *more* (not less) reason not to hard-code
such syntax restrictions into the definition of Lisp itself.

Working on adding reader macros to Emacs Lisp would be (very!)
helpful.  Hard-coding < and << syntax is not helpful (IMHO).

Re: plists, alists, and hashtables

[Pascal J. Bourguignon]

Ted Zlatanov <tzz@lifelogs.com> writes:

> That's all right, but I would probably prefer a Unicode pair of
> characters.  In 2015, that's going to inconvenience very few people.

Not on GUI, but people using emacs in (virtual) terminals are still
numerous, and there support for unicode, notably fancy characters, is
much more limited. 

Therefore I would advise to implement a unicode syntax only as an
additionnal alternative, not as the main one.


> So as a first cut, maybe «(k1 . v1) (k2 . v2)» and ««(k1 . v1) (k2 .
> v2)»» would be a good syntax (equal and eql versions respectively),
> simply converted to the appropriate #s(hash-table ...) syntax?

I would drop the dot.  And I fail to see a reason to keep the
parentheses too.

In my CL libraries, I have a hashtable function, like list or vector:

    (hashtable :test 'equal :size 1000
               :elements '((k1 v1)
                           (k2 v2)
                           …
                           (kn vn)))  

but we could lighten it, providing two functions similar to list or vector:

    (hash-table-eql k1 v1
                   k2 v2
                   …
                   kn v2)

    (hash-table-equal k1 v1
                      k2 v2
                      …
                      kn v2)

Notice that once you have those functions, you can use:

       #.(hash-table-eql :one 1 :two 2)

in CL, so you don't need a specific syntax, if you have only a few literals.


On Cocoa, the dictionaries can be created with class methods like these
constructor functions, alternating key and values (but finishing the
vararg list with an ugly nil!), and they also provide versions where you
pass two lists, of keys and values (well they reverse the order of value
and key for grammatical reasons, but this is irrelevant). 

So we could also have those functions:

   (make-hash-table-eql   (list k1 k2 k3)
                          (list v1 v2 v3))

   (make-hash-table-equal (list k1 k2 k3)
                          (list v1 v2 v3))


Once you have that, there's very little to be gained by adding a syntax
such as:

                   «k1 v1 k2 v2 k3 v3»

    (hash-table-eql k1 v1 k2 v2 k3 v3)

On the contrary, you introduce an ambiguity:

   (loop repeat 10 collect «k1 v1 k2 v2 k3 v3»)

will this allocate ten hash tables, or is it a list refering ten times
the same hash table?  (Actually this is the questions that renders me
incapable of programming in Ruby or Python, I never know what those
syntaxes do).

Is «k1 v1 k2 v2 k3 v3» a hash table, a vector, a string or what?

At least with:     (hash-table-eql k1 v1 k2 v2 k3 v3)

we see obviously that it's about eql hash-table, and the lisp
constructor pattern is clear.


> RT> If a hash-map type were used then there could be a bit to signify if
> RT> it's *really* a hash.  I've heard that some of the scripting languages
> RT> are doing this because they've found what I found; that most maps
> RT> contain so few elements that hashing just makes things slower.  But, the
> RT> bit would have to be tested before every map operation.
>
> I think the bit check performance penalty would be insignificant, and
> that the backend implementation can adapt to use lists for small maps.
> In any case, using these would be voluntary, people can still use the
> usual alists and plists.

Well, that's another problem :-)

- who knows whether hash-table already implement some kind of adaptative
  data structure or not?  You've checked the C sources?

- so, we wrap a-lists and hash-table in a dictionary abstraction.  Now
  people have the option between a-lists, p-lists or dictionaries, and
  in certain cases, vectors too (I encounter the situation where you
  want actually to maintain a vector and a hash-table in parallel in a
  common abstraction), so they will wrap a new map abstraction over
  those different implementation strategies again?
  https://xkcd.com/927/



You can have a look at ACL2, the theorem prover written over Common
Lisp, using an abstract "subset/superset" of Common Lisp.  There are no
vectors, only lists (I don't remember the situation about hash-tables,
but probably they're not present, and you have to prove them using lists
(a-lists)).  On one hand, the use of a "rudimentary" data structure
like lisp lists allow them to provide a common abstracted API for all
sequence types, along with proven axioms and theorem on their usage, on
the other hand this doesn't prevent a compiler to translate the code
written in ACL2 into lower datastructures like vectors or dictionaries
(once the theorems have been proven) to extract performance, and on a
final hand, or you can just run the code on Common Lisp, and normal
lists will be used (but you know it'll be bug free, since it's proven).

The point here is that lisp lists and sexp provide a way to denote
abstract data structures that could have better performance
characteristics than just the lists it looks like.  It's basically up to
a "compiler" or a macro, to generate the better code from the high level
description.

When you write the lisp form:      (hash-table-eql k1 v1 k2 v2 k3 v3)
you've actually written a list, 
but there is a function named hash-table-eql 
that turns it into a hash-table.

Now, you could also write:         (k1 v1 k2 v2 k3 v3)
and have that be turned into a hash-table,
because you would have written it in the context of a DSL or macro,
that would have proven or assumed it is hash-table data.

In both cases, the sexp notation with no supplementary syntaxes is
enough to denote your high level data structures. 

If you want to cater to the need of the future programmers, perhaps it
would be better to go toward making lisp a more high level programming
language, not adding syntax and specific distinct data structures, but
by having a smarter "eval" engine that is able to prove things about the
denoted data and programs, and to translate it into the most adapted
data structures and algorithms.

It's the same discussion we had about (1+ x) vs (+ 1 x).

1+ is supposedly more efficient (and also, pre-curried, for use with
mapcar).  But one can argue that (+ 1 x) is more general.  I doesn't
matter anymore, because nowdays the compiler will generate the same code
for both.

Similarly, instead of dicussing about #S(hash-table) vs «» vs
#.(hash-table …), it would be better to think about implementing theorem
prover features into a lisp to make it a higher level programming
language, so you don't have to care about what exact low level data
structure or algorithm is used, as long as the system has been able to
prove nice features of your high level description, which can be already
written with plain sexps.

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: plists, alists, and hashtables

[Ted Zlatanov]

On Wed, 05 Aug 2015 16:45:38 -0400 Stefan Monnier <monnier@iro.umontreal.ca> wrote: 

RT> There may be alternatives though.  For example, instead of:
RT> #s(hash-table size 65 test eql rehash-size 1.5 rehash-threshold 0.8 data ())
RT> We could have a shorthand, perhaps #s(h data)
...
SM> ?  I think it's going to be hard to convince that the few use cases will
SM> be enough to justify all the work.

My primary use case is "I want to *express* a map, not a list; I want it to
look like a map, not a list; and I want the reader to actually reject it
if it's not a valid map."  I feel that facilitating that at the ELisp
reader level, with a hashtable backend, would improve ELisp usability.
And maybe ELisp users will like it.

Ted

Re: plists, alists, and hashtables

[Ted Zlatanov]

On Wed, 5 Aug 2015 14:36:50 -0700 (PDT) Drew Adams <drew.adams@oracle.com> wrote: 

>> So as a first cut, maybe <(k1 . v1) (k2 . v2)> and
>> <<(k1 . v1) (k2 . v2)>> would be a good syntax
...
DA> Unfortunately, in Emacs Lisp we do not (yet) have reader macros.
DA> But that is all the *more* (not less) reason not to hard-code
DA> such syntax restrictions into the definition of Lisp itself.

DA> Working on adding reader macros to Emacs Lisp would be (very!)
DA> helpful.  Hard-coding < and << syntax is not helpful (IMHO).

OK, I agree, except that it should be globally enabled, so whatever the
syntax, it can become a standard way to express a map.  That's the
point; I can already use hashtables just fine.  It needs to be accessible.

Can anyone explain to me what's missing in order to implement the reader
macro that translates «xyz» to some version of #s(hash-table ...)?

Ted

How to iterate over properties in a plist?

[Marcin Borkowski]

Hi all,

I need to iterate over all properties in a plist.  Obviously, mapcar (or
mapc, since I need side effects only) is of no use for me.  I can easily
write a plist-mapc function:

--8<---------------cut here---------------start------------->8---
(defun plist-mapc (function plist)
  "Iterate FUNCTION (a two-argument function) over PLIST.  Error
checking is for weenies."
  (when plist
    (funcall function (car plist) (cadr plist))
    (plist-mapc function (cddr plist))))
--8<---------------cut here---------------end--------------->8---

but maybe it's there already?

TIA,

-- 
Marcin Borkowski
http://octd.wmi.amu.edu.pl/en/Marcin_Borkowski
Faculty of Mathematics and Computer Science
Adam Mickiewicz University

Re: How to iterate over properties in a plist?

[Stefan Monnier]

> I need to iterate over all properties in a plist.

First things first: go complain to whoever decided to use a plist
instead of an alist.


        Stefan

Re: How to iterate over properties in a plist?

[Pascal J. Bourguignon]

Marcin Borkowski <mbork@mbork.pl> writes:

> On 2015-08-01, at 00:18, Stefan Monnier <monnier@iro.umontreal.ca> wrote:
>
>>> I need to iterate over all properties in a plist.
>>
>> First things first: go complain to whoever decided to use a plist
>> instead of an alist.
>
> Why?  I did consider both and decided that a plist will be better in my
> use-case.  Reasons: it is short anyway (no more than 3-5 properties at
> most), and I need to change it frequently (i.e., change the values of
> individual properties).  This last operation seems much nicer in
> a plist.  AFAIK, the "canonical" way to change a key-value pair in an
> alist is to push the new one at the beginning.  In my case, the list
> will grow quickly.

You can use mutation on a-lists, and you can push new values on p-lists
too.

There's no difference between a-lists and p-list:
- in both cases, you need to traverse two cons to check the next key.
- you have the same number of memory accesses for all the operations.

It's really only a matter of taste.

Plus, p-list can be used to pass &key arguments to functions.

(defun* f (&key a b c)
  (list a b c))

(apply (function f) '(:a 1 :c 2))
--> (1 nil 2)

and also with destructuring-bind:

   (destructuring-bind (&key a b c) '(:a 1 :c 2)
      (list a b c))
   --> (1 nil 2)

You cannot do that with a-lists, there's no way to define an argument
taking and destructuring an a-list cons cell.

So if you ever have to use the contents of your dictionary as flat arguments
to a function, you will prefer a p-list.

(But of course, you can also write your function as taking a single
a-list or a single p-list, and query the parameter instead of
destructuring it into separate parameters).


Otherwise getf use eql to compare keys, &key accepts only symbols, while
assoc* (assoc in Common Lisp), takes a :test and a :key argument to find
keys.  So if you use those standard lisp functions to process a-lists
and p-list, this may further constraint your choice.

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

plists, alists, and hashtables (was: How to iterate over properties in a plist?)

[Ted Zlatanov]

On Sat, 01 Aug 2015 18:49:38 -0400 Stefan Monnier <monnier@iro.umontreal.ca> wrote: 

SM> - plists need to be "parsed" in order to figure out if an element is a key
SM>   or a value.

That's true, but there's some idea that a plist is "correct" if it can
be parsed. It's also visually easier to parse, I think, especially for
beginners. Also, symbol plists are pretty well ensconced at the C level.

By contrast, alists don't have a strong structure and parsing them is
not simple for beginners. For instance:

(alist-get 'a '((a) (b 1) (c . 2) d)) -> nil
(alist-get 'b '((a) (b 1) (c . 2) d)) -> (1)
(alist-get 'c '((a) (b 1) (c . 2) d)) -> 2
(alist-get 'd '((a) (b 1) (c . 2) d)) -> nil ; no error

The real map type in Emacs Lisp is the hashtable, I think. But because
of historical baggage, we end up discussing the benefits of two list
formats when used as maps. Which feels like discussing which of two
different bicycles is better for carrying 5 people.

For instance, the hashtable keys are unambiguously
(hash-table-keys my-hashtable) and there's no looping or parsing.

I wonder, if hashtables had a better reader syntax (like plists or
alists) and better Customize support, would they see wider use? Or is
the historical baggage in tutorials and existing code too much at this
point?

Ted

Re: plists, alists, and hashtables

[Ted Zlatanov]

On Tue, 4 Aug 2015 10:29:04 +0000 Nicolas Petton <nicolas@petton.fr> wrote: 

NP> On Tue Aug 4 11:15:27 2015 GMT+0100, Ted Zlatanov wrote:
>> The real map type in Emacs Lisp is the hashtable, I think. But because
>> of historical baggage, we end up discussing the benefits of two list
>> formats when used as maps. Which feels like discussing which of two
>> different bicycles is better for carrying 5 people.
>> 
>> For instance, the hashtable keys are unambiguously
>> (hash-table-keys my-hashtable) and there's no looping or parsing.
>> 
>> I wonder, if hashtables had a better reader syntax (like plists or
>> alists) and better Customize support, would they see wider use?

NP> The new map.el library provides a common interface for both hashtables
NP> and alists (as well as other key/value data structures). Maybe that
NP> will make it easier for people to use hashtables?

It's a nice API, but doesn't help with historical baggage (the dozens
of tutorials that use lists as maps; the inertia on the mailing lists;
the already-written code people will copy).  I still think more is
needed like I mentioned to reach a tipping point.

Ted

Re: plists, alists, and hashtables (was: How to iterate over properties in a plist?)

[Rusi]

On Tuesday, August 4, 2015 at 3:45:32 PM UTC+5:30, Ted Zlatanov wrote:
> On Sat, 01 Aug 2015 18:49:38 -0400 Stefan Monnier wrote: 
> 
> SM> - plists need to be "parsed" in order to figure out if an element is a key
> SM>   or a value.
> 
> That's true, but there's some idea that a plist is "correct" if it can
> be parsed. It's also visually easier to parse, I think, especially for
> beginners. Also, symbol plists are pretty well ensconced at the C level.
> 
> By contrast, alists don't have a strong structure and parsing them is
> not simple for beginners. For instance:
> 
> (alist-get 'a '((a) (b 1) (c . 2) d)) -> nil
> (alist-get 'b '((a) (b 1) (c . 2) d)) -> (1)
> (alist-get 'c '((a) (b 1) (c . 2) d)) -> 2
> (alist-get 'd '((a) (b 1) (c . 2) d)) -> nil ; no error
> 
> The real map type in Emacs Lisp is the hashtable, I think. But because
> of historical baggage, we end up discussing the benefits of two list
> formats when used as maps. Which feels like discussing which of two
> different bicycles is better for carrying 5 people.

+1 
Since I always seem to be carrying on about emacs carrying ancient baggge
I did not say it.

50 years ago using association lists to model associations was real neat.

However after perl and python (and awk) and... almost any language invented
in the last 20 years, its rather backward.
The efficiency is one thing
The clumsy syntax is the bigger one (for me)

Re: plists, alists, and hashtables

[Pascal J. Bourguignon]

Rusi <rustompmody@gmail.com> writes:

> However after perl and python (and awk) and... almost any language invented
> in the last 20 years, its rather backward.
> The efficiency is one thing
> The clumsy syntax is the bigger one (for me)

The clumsy syntax is on the part of perl and python and awk and so on.

What you are losing from sight is the fact that:

- a-lists are lists
- p-lists are lists
- lists are sequences
- lists are cons cells or nil

therefore any operator working on cons cells, on sequences, on lists,
can also work on p-lists and on a-lists.

Therefore you don't need any specific syntax to work with a-lists,
because they are just normal lisp symbolic expressions, and you can use
the whole of lisp to process them however you want.  You are not
restricted to a sterotyped straighjacket syntax to process exclusively
dictionaries, maps or whatever they have in those lesser languages.

Ignoring unicode, because no human can identify every glyphs of the
billions you could compose in unicode and reproduce them without
hesitation, and removing the characters already used for some lisp
syntax '"#():`,@;.\?[]  and those that are normal constituents and used
in existing symbol names &+-*/%<=>, that leaves only 8 characters for
new syntaxes !$^_{|}~

Unfortunately there are many more than 8 datastructures for which you
could want a specific syntax. 

Therefore your requirement is impossible.  There's no reason to
allocate, eg. {} to some kind of maps over some other that I could
prefer for my programs.


On the other hand, if emacs lisp had readtables and reader macros like
Common Lisp (or improved, like named readtables), we could introduce
local syntaxes for specific packages.  You could even make use of some
specific unicode characters that you can type non-clumsily on your
keyboard (but only YOU could do that, since other people would have
other keyboard layout and it would be anything from very clumsy (C-x 8
RET what's this fucking character name again? RET) to impossible to
type.  So thanks for that non-clumsy syntax of yours.  

Give me sexps anytime!

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: plists, alists, and hashtables

[Ted Zlatanov]

On Wed, 05 Aug 2015 08:12:22 +0200 "Pascal J. Bourguignon" <pjb@informatimago.com> wrote: 

PJB> What you are losing from sight is the fact that:

PJB> - a-lists are lists
PJB> - p-lists are lists
PJB> - lists are sequences
PJB> - lists are cons cells or nil

PJB> therefore any operator working on cons cells, on sequences, on lists,
PJB> can also work on p-lists and on a-lists.

Yes, I think the implicit advantage of everything being a list is well
understood amongst us.  But so is the disadvantage of treating
everything as a list.  The question is whether hashtables, an existing
ELisp map data type, could become more popular.

PJB> Unfortunately there are many more than 8 datastructures for which you
PJB> could want a specific syntax. 

You have to be specific about why we'd discuss or want these 8 data
structures, since the discussion was only about hashtables.

My original question was actually:
> I wonder, if hashtables had a better reader syntax (like plists or
> alists) and better Customize support, would they see wider use? Or is
> the historical baggage in tutorials and existing code too much at this
> point?

Hashtables in Emacs Lisp already have a read syntax, in fact: see
(info "(elisp) Hash Tables")

So maybe if that syntax could be a little less clumsy without breaking
the rest of ELisp, that would help?

For instance, `#s(hash-table)' will evaluate to an empty hashtable
already.  But typically you want to control the other parameters, so
this is what `make-hash-table' returns:

#s(hash-table size 65 test eql rehash-size 1.5 rehash-threshold 0.8 data ())

How do we make an easy syntax for that? I see only two major variations
of maps in ELisp; using `eql' or `equal' for keys. I can imagine some
unlikely cases where you'd want other equality comparisons for the keys,
like numeric equality, but I think over 95% of the cases will be covered
by just those two variations.

For instance, and this is just an example:

{{(a . b)}} ; hashtable with test `eql' mapping a to b
{(a . b)}   ; hashtable with test `equal' mapping a to b

And finally, if you could Customize hashtables, would that make it
easier to support them as first-class variables in packages? I think
so...

Ted

Re: plists, alists, and hashtables

[Rusi]

On Wednesday, August 5, 2015 at 3:17:44 PM UTC+5:30, Ted Zlatanov wrote:
> On Wed, 05 Aug 2015 08:12:22 +0200 "Pascal J. Bourguignon"  wrote: 
> 
> PJB> What you are losing from sight is the fact that:
> 
> PJB> - a-lists are lists
> PJB> - p-lists are lists
> PJB> - lists are sequences


And lists (if you were to think mathematically) are sequences
And sequences are maps; in more detail:
A finite sequence over τ 𝒮(τ) is a function  {1..n} → τ
An infinite sequence over τ 𝒮(τ) is a function  ℕ → τ

On the other side, a hash-table is just a map from keys to values
(with algorithmic/storage-layout mixed up as is usually done by low-level
programmers)

In short a map is the fundamental data structure.

Alternate Existence Proof: Lua has only one data structure -- the table -- which
does the job of both lists and hashes

Re: plists, alists, and hashtables

[Stefan Monnier]

> In short a map is the fundamental data structure.

Beware: there are maps and then there are maps.
E.g. Javascript's objects are maps (typically thought of as being
implemented as some kind of hash-tables), yet Javascript also comes with
hash-tables.

More importantly, mathematical maps are persistent, whereas your
apparently favorite implementation (the hash-table) is not persistent,
contrary to (e.g.) alists.


        Stefan

Re: plists, alists, and hashtables

[Rusi]

On Friday, August 7, 2015 at 12:50:20 AM UTC+5:30, Stefan Monnier wrote:
> > In short a map is the fundamental data structure.¹
> 
> Beware: there are maps and then there are maps.
> E.g. Javascript's objects are maps (typically thought of as being
> implemented as some kind of hash-tables), yet Javascript also comes with
> hash-tables.

Thats the whole point
Python: Zen on python makes a big todo about namespaces because they work 
uniformly and nicely for objects, classes, modules... All of which are
dictionaries ie maps
Lua: Only one collection data structure -- the table.
Tables made without explicit keys just use 1,2,3 etc ie normal lists with
the expected convenient lists syntax. Brings me to...
SQL: All of sql hangs around relations. May be called 'relation' but they
are invariably key → tuple maps

Finally a more 'fundamentalist' viewpoint:

Programmers write functions as their most primary activity
If they are algorithmic they are the functions that all programmers daily use
If they are just looked-up they are 'data-maps' -- for which a hash-table is 
a typical² data structure

IOW functions-as-code and functions-as-data are a primary dual
-----------
¹ No attribution line...Assuming you are quoting me....
² If 90% of all maps/associations are smaller than 10-15, then a linear lookup 
would be clearly a win over more fancy (Pascal's point I think). My point is 
more that the *idea* of a map needs to be fundamental not the details of *implementation*

Re: plists, alists, and hashtables

[Pascal J. Bourguignon]

Ted Zlatanov <tzz@lifelogs.com> writes:

> On Wed, 05 Aug 2015 08:12:22 +0200 "Pascal J. Bourguignon" <pjb@informatimago.com> wrote: 
>
> PJB> What you are losing from sight is the fact that:
>
> PJB> - a-lists are lists
> PJB> - p-lists are lists
> PJB> - lists are sequences
> PJB> - lists are cons cells or nil
>
> PJB> therefore any operator working on cons cells, on sequences, on lists,
> PJB> can also work on p-lists and on a-lists.
>
> Yes, I think the implicit advantage of everything being a list is well
> understood amongst us.  But so is the disadvantage of treating
> everything as a list.  The question is whether hashtables, an existing
> ELisp map data type, could become more popular.

Why?
How would that be good?

Seriously, hash-tables have a lot of drawbacks.
They use much more memory,
they are much slower (on small dictionaries),
they are much restrictive on the possible key equivalence function.

The only advantage they have, is on speed of access in big dictionaries.

But even when you need a O(1) access on a big dictionary, you will find
you keep converting between hash-table and lists or vectors, of only to
sort the entries out to present them to the user!


If you achieved your goal of having unwashed masses use hash-tables
instead of a-list/p-lists, the only result you'd attain would be to slow
down emacs.  Run your own benchmark.  On my computer, I notice that
until the size of the dictionary reaches 20-30, a-lists are performing
better than hash-table. (And even, I call assoc on set, while for
a-list it is customary to just do acons, so inserting or reseting
entries would be even much faster). 



------------------------------------------------------------------------
;;; -*- mode:emacs-lisp;lexical-binding:t;coding:utf-8 -*-
(setf lexical-binding t)

(defun make-hash-table-dictionary ()
  (let ((table (make-hash-table)))
    (lambda (m &optional k v)
      (ecase m
        (get (gethash k table))
        (del (remhash k table))
        (set (setf (gethash k table) v))
        (key (let ((keys '()))
               (maphash (lambda (k v)
                          (declare (ignore v))
                          (push k keys))
                        table)
               keys))))))

(defun make-a-list-dictionary ()
  (let ((table '()))
    (lambda (m &optional k v)
      (ecase m
        (get (cdr (assoc k table)))
        (del (let ((prev-entry (loop
                                 for cell on (cons nil table)
                                 until (eql k (cadr cell))
                                 finally (return cell))))
               (when prev-entry
                 (setf (cdr prev-entry) (cddr prev-entry)))
               (setf table (cdr prev-entry))))
        (set (let ((entry (assoc k table)))
               (if entry
                   (setf (cdr entry) v)
                   (setf table (acons k v table)))))
        (key (mapcar (function car) table))))))

(defun make-null-dictionary ()
  (lambda (m &optional k v)
    (declare (ignore k v))
    (ecase m
      ((get del set key) nil))))



(defun dict-get (dict k)   (funcall dict 'get k))
(defun dict-del (dict k)   (funcall dict 'del k))
(defun dict-set (dict k v) (funcall dict 'set k v))
(defun dict-key (dict)     (funcall dict 'key))


(defun get-internal-real-time ()
  (destructuring-bind (high low microsec &rest ignored) (current-time)
    (declare (ignore ignored))
    (+ (* high 65536.0) low (* 1e-6 microsec))))

(defmacro chrono (&rest body)
  "Returns the time it took to evaluate the body expressions (in an implict progn)."
  (let ((start (gensym))
        (result (gensym)))
    `(let* ((,start  (get-internal-real-time))
            (,result (progn ,@body)) )
       (- (get-internal-real-time) ,start))))

(defun generate-keys (size)
  (loop repeat size
        collect (gensym)))

(defun generate-values (size)
  (loop repeat size
        with max = (* size 1000)
        collect (random size)))

(defun benchmark (constructor size repeat)
  (let* ((dicts            '())
         (keys             (generate-keys size))
         (values           (generate-values size))
         (constructor-time (chrono (setf dicts (loop repeat repeat
                                                     collect (funcall constructor)))))
         (fill-time        (chrono (mapc (lambda (dict)
                                           (loop for k in keys for v in values
                                                 do (dict-set dict k v)))
                                         dicts)))
         (key-time-full    (chrono (mapc (function dict-key) dicts)))
         (get-time-full    (chrono (mapc (lambda (dict)
                                           (loop for k in keys for v in values
                                                 collect (eql v (dict-get dict k))))
                                         dicts)))
         (del-time         (chrono (mapc (lambda (dict)
                                           (loop for k in keys for v in values
                                                 for i from 0
                                                 when (oddp i)
                                                   do (dict-del dict k)))
                                         dicts)))
         (key-time-part    (chrono (mapc (function dict-key) dicts)))
         (get-time-part    (chrono (mapc (lambda (dict)
                                           (loop for k in keys for v in values
                                                 for i from 0
                                                 if (oddp i)
                                                   collect (null (dict-get dict k))
                                                 else
                                                   collect (eql v (dict-get dict k))))
                                         dicts))))
    (let ((count (float repeat)))
      (list :constructor-time (/ constructor-time count)
            :fill-time        (/ fill-time        count)
            :key-time-full    (/ key-time-full    count)
            :get-time-full    (/ get-time-full    count)
            :del-time         (/ del-time         count)
            :key-time-part    (/ key-time-part    count)
            :get-time-part    (/ get-time-part    count)))))

(defun benchmark-all ()
  (loop with repeat = 100
        for size in '(1 2 3 4 5 6 7 8 9 10 15 20 25 30 35 40 50 60 70 80 90 100)
        collect (loop
                  with null-case = (benchmark 'make-null-dictionary size repeat)
                  for constructor in '(make-a-list-dictionary make-hash-table-dictionary)
                  collect (list* constructor size
                                 (mapcar* (lambda (v b)
                                            (if (numberp v)
                                                (- v b)
                                                v))
                                          (benchmark constructor size repeat)
                                          null-case)))))

;; (benchmark-all)
------------------------------------------------------------------------

> PJB> Unfortunately there are many more than 8 datastructures for which you
> PJB> could want a specific syntax. 
>
> You have to be specific about why we'd discuss or want these 8 data
> structures, since the discussion was only about hashtables.

Nonetheless, this argument is the reason why the print/read syntax for
hash-tables is:

> #s(hash-table size 65 test eql rehash-size 1.5 rehash-threshold 0.8 data ())

This extends easily to any other data structure for which you'd want a
literal representation.

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: plists, alists, and hashtables

[Ted Zlatanov]

On Wed, 05 Aug 2015 19:24:31 +0200 "Pascal J. Bourguignon" <pjb@informatimago.com> wrote: 

PJB> Ted Zlatanov <tzz@lifelogs.com> writes:
>> Yes, I think the implicit advantage of everything being a list is well
>> understood amongst us.  But so is the disadvantage of treating
>> everything as a list.  The question is whether hashtables, an existing
>> ELisp map data type, could become more popular.

PJB> Why?

To have a true native map data type.

PJB> How would that be good?

Because a true native map data type avoids the complexity of lists in
many cases.

PJB> Seriously, hash-tables have a lot of drawbacks.
PJB> They use much more memory,
PJB> they are much slower (on small dictionaries),

I think these details are easily optimized at the C level. Clearly an
alist is better as the *backend* hashtable implementation for up to 10,
possibly up to 100 entries (depending on caching, pipelining, hashing
function, and other factors). But the frontend presentation is what I'm
concerned about. I think a better reader syntax for hashtables would
make them easier to write and read in code and would error out if they
are malformed. That's an improvement over alists and plists I think.

PJB> they are much restrictive on the possible key equivalence function.

Like I said, 95% of the cases only need eql and equal. For the rest,
users can use `make-hash-table' directly instead of through the shortcut
syntax.

PJB> The only advantage they have, is on speed of access in big dictionaries.

PJB> But even when you need a O(1) access on a big dictionary, you will find
PJB> you keep converting between hash-table and lists or vectors, of only to
PJB> sort the entries out to present them to the user!

That's no different than looping over alists and plists to collect and
sort the entries, is it?

PJB> If you achieved your goal of having unwashed masses use hash-tables

"unhashed masses"? :)

PJB> instead of a-list/p-lists, the only result you'd attain would be to
PJB> slow down emacs. Run your own benchmark. On my computer, I notice
PJB> that until the size of the dictionary reaches 20-30, a-lists are
PJB> performing better than hash-table. (And even, I call assoc on set,
PJB> while for a-list it is customary to just do acons, so inserting or
PJB> reseting entries would be even much faster).

Absolutely, but I mentioned already that this is easily fixed on the
back end. I think it's clear that while hashtables *can* scale, alists
and plists *can't* because their backend and frontend are the same.
Hashtables are only accessible through an API, their backend is
hidden.

PJB> Nonetheless, this argument is the reason why the print/read syntax for
PJB> hash-tables is:

>> #s(hash-table size 65 test eql rehash-size 1.5 rehash-threshold 0.8 data ())

PJB> This extends easily to any other data structure for which you'd want a
PJB> literal representation.

OK, but still, I'm not interested in heaps, trees, graphs, skip lists,
or other data structures.  I'm interested in improving the accessibility
and popularity of hashtables in order to avoid the complexity and
ambiguity of alists and plists when dealing with maps.

Ted

Re: plists, alists, and hashtables

[Barry Margolin]

In article <87oailbn8t.fsf@lifelogs.com>,
 Ted Zlatanov <tzz@lifelogs.com> wrote:

> I think these details are easily optimized at the C level. Clearly an
> alist is better as the *backend* hashtable implementation for up to 10,
> possibly up to 100 entries (depending on caching, pipelining, hashing
> function, and other factors). But the frontend presentation is what I'm
> concerned about. I think a better reader syntax for hashtables would
> make them easier to write and read in code and would error out if they
> are malformed. That's an improvement over alists and plists I think.

IIRC, at one time Symbolics had an implementation of Common Lisp 
hashtables that chose different internal representations depending on 
various attributes of the table, like the current size and equivalence 
function.

But I think they got rid of this because there were bugs that occurred 
as a result of the table changing reps on the fly, and I guess they 
discovered that it didn't really buy that much in performance. For 
instance, the break-even point for alists is probably pretty low, and 
hash tables tended to be used for large tables.

Of course, that was before languages like Perl, PHP, and Javascript 
popularized the idea of using small hash tables to implement structures.

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

Re: plists, alists, and hashtables

[Robert Thorpe]

Ted Zlatanov <tzz@lifelogs.com> writes:

> PJB> This extends easily to any other data structure for which you'd want a
> PJB> literal representation.
>
> OK, but still, I'm not interested in heaps, trees, graphs, skip lists,
> or other data structures.  I'm interested in improving the accessibility
> and popularity of hashtables in order to avoid the complexity and
> ambiguity of alists and plists when dealing with maps.

As Pascal mentioned, we only have a very small number of characters left
to use for read syntax.

You can't just consider one proposal alone.  Just because something is
useful doesn't mean that it's useful enough to burn a character or two
for.  It has to be compared to alternatives.

There may be alternatives though.  For example, instead of:
#s(hash-table size 65 test eql rehash-size 1.5 rehash-threshold 0.8 data ())

We could have a shorthand, perhaps #s(h data) .

Like Pascal I think alists are generally a good idea.  People who don't
understand the performance implications of them won't understand those
of hash-maps either.  Especially when things are done per key.

In an editor the vast majority of maps are likely to contain only a few
variables.  A few years ago I made a program that examined every Emacs
variable that ended in "alist".  Almost all of them were short.  Only a
handful were long enough to cause performance issues.

If a hash-map type were used then there could be a bit to signify if
it's *really* a hash.  I've heard that some of the scripting languages
are doing this because they've found what I found; that most maps
contain so few elements that hashing just makes things slower.  But, the
bit would have to be tested before every map operation.

BR,
Robert Thorpe

Re: plists, alists, and hashtables

[Pascal J. Bourguignon]

Ted Zlatanov <tzz@lifelogs.com> writes:

> I think these details are easily optimized at the C level. Clearly an
> alist is better as the *backend* hashtable implementation for up to 10,
> possibly up to 100 entries (depending on caching, pipelining, hashing
> function, and other factors). But the frontend presentation is what I'm
> concerned about. 

DUH!  What did I just do to write the benchmark?

So you're not discussing about hash-tables, but about how to provide
high level abstractions.  Well DUH, just program them! functions,
macros.

> I think a better reader syntax for hashtables would
> make them easier to write and read in code and would error out if they
> are malformed. That's an improvement over alists and plists I think.

And yes, if you had readtables and reader macros, also a reader macro.

Don't ask for a dictionary abtraction.  Ask for readtables and reader
macros!  So that you may implement your own syntax for your own
abstractions!



>
> PJB> The only advantage they have, is on speed of access in big dictionaries.
>
> PJB> But even when you need a O(1) access on a big dictionary, you will find
> PJB> you keep converting between hash-table and lists or vectors, of only to
> PJB> sort the entries out to present them to the user!
>
> That's no different than looping over alists and plists to collect and
> sort the entries, is it?

Well, for small dictionaries, (about 8 entries), it's still faster to
copy the keys from a-lists than from a hash-table.


> PJB> instead of a-list/p-lists, the only result you'd attain would be to
> PJB> slow down emacs. Run your own benchmark. On my computer, I notice
> PJB> that until the size of the dictionary reaches 20-30, a-lists are
> PJB> performing better than hash-table. (And even, I call assoc on set,
> PJB> while for a-list it is customary to just do acons, so inserting or
> PJB> reseting entries would be even much faster).
>
> Absolutely, but I mentioned already that this is easily fixed on the
> back end. I think it's clear that while hashtables *can* scale, alists
> and plists *can't* because their backend and frontend are the same.
> Hashtables are only accessible through an API, their backend is
> hidden.

Yes, you're asking about an abstraction and a nice API and syntax for
it.  

I'm saying ok, implement it, lisp is good for that. (It could be better
with reader macros).

I'm also saying, beware anyways, because even with adaptative data
structures abstracted away, you will aways have some (usage) complexity
coming up, from the fact that your abstract operations will have some
overhead and some time and space complexity that may not be what is the
best in some specific cases.



(let ((sizes '()))
 (mapatoms (lambda (s)
             (when (boundp s)
               (let ((table (symbol-value s)))
                 (when (hash-table-p table)
                   (push (hash-table-count table) sizes))))))
  (sort sizes '<))

Here are the results on three different emacs instances doing different
things: CL develoment with slime, erc, gnus:

--> (0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 3 4 4 5 15 18 19 23 23 28 36 54 108 252 253 366 709 978 1013)
--> (0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 4 4 5 8 19 19 22 23 23 28 54 108 252 253 366 604 752 871 894 978)
--> (0 0 0 0 0 0 0 0 0 0 1 2 4 4 4 5 9 19 19 23 23 26 28 30 54 108 252 253 366 562 752 894 978 1638)

(length '(0 0 0 0 0 0 0 0 0 0 0))                    --> 11
(length '(1 2 4 4 4 5 9))                            -->  7
(length '(19 19 23 23 26 28 30))                     -->  7             
(length '(54 108 252 253 366 562 752 894 978 1638))  --> 10

So about half of those hash-table are too small, and should have been
implemented as a-lists, one quarter is around the break even, and only
one quarter should definitelhy be hash-tables.

You could improve this, by implementing a better data walker, here we
only look at the hash-tables directly bounds to variables.


-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: plists, alists, and hashtables

[Ted Zlatanov]

On Wed, 05 Aug 2015 23:11:41 +0200 "Pascal J. Bourguignon" <pjb@informatimago.com> wrote: 

PJB> Ted Zlatanov <tzz@lifelogs.com> writes:
>> I think these details are easily optimized at the C level. Clearly an
>> alist is better as the *backend* hashtable implementation for up to 10,
>> possibly up to 100 entries (depending on caching, pipelining, hashing
>> function, and other factors). But the frontend presentation is what I'm
>> concerned about. 

PJB> So you're not discussing about hash-tables, but about how to provide
PJB> high level abstractions.  Well DUH, just program them! functions,
PJB> macros.

I was trying to say the best way today to provide the map abstraction
seems to be to use hashtables and to improve them for small sizes on the
backend, rather than try to hack around them.

PJB> And yes, if you had readtables and reader macros, also a reader macro.

PJB> Don't ask for a dictionary abtraction.  Ask for readtables and reader
PJB> macros!  So that you may implement your own syntax for your own
PJB> abstractions!

Sure, though I wasn't asking for either of those, I was wondering if
they would become popular enough that people would migrate to them.  The
actual implementation may require reader macros and other tools, which
will happen on emacs-devel I assume.

PJB> Yes, you're asking about an abstraction and a nice API and syntax for
PJB> it.

PJB> I'm saying ok, implement it, lisp is good for that. (It could be better
PJB> with reader macros).

Cool, thanks for agreeing on this.  I think it would be nice too.  I'll
bring it up on emacs-devel next.

PJB> I'm also saying, beware anyways, because even with adaptative data
PJB> structures abstracted away, you will aways have some (usage) complexity
PJB> coming up, from the fact that your abstract operations will have some
PJB> overhead and some time and space complexity that may not be what is the
PJB> best in some specific cases.

Of course, but that's something we (maybe) learn in basic data
structures courses.

On Wed, 05 Aug 2015 23:41:03 +0200 "Pascal J. Bourguignon" <pjb@informatimago.com> wrote: 

PJB> Ted Zlatanov <tzz@lifelogs.com> writes:

>> That's all right, but I would probably prefer a Unicode pair of
>> characters.  In 2015, that's going to inconvenience very few people.

PJB> Not on GUI, but people using emacs in (virtual) terminals are still
PJB> numerous, and there support for unicode, notably fancy characters, is
PJB> much more limited.

PJB> Therefore I would advise to implement a unicode syntax only as an
PJB> additionnal alternative, not as the main one.

Good point, though I think « and » specifically, being very widely used,
will be all right.

>> So as a first cut, maybe «(k1 . v1) (k2 . v2)» and ««(k1 . v1) (k2 .
>> v2)»» would be a good syntax (equal and eql versions respectively),
>> simply converted to the appropriate #s(hash-table ...) syntax?

PJB> I would drop the dot.  And I fail to see a reason to keep the
PJB> parentheses too.

Visually, you'd end up with a mess then.  This has to be readable in
the source code, not just to a machine.

PJB> When you write the lisp form:      (hash-table-eql k1 v1 k2 v2 k3 v3)
PJB> you've actually written a list, 
PJB> but there is a function named hash-table-eql 
PJB> that turns it into a hash-table.

PJB> Now, you could also write:         (k1 v1 k2 v2 k3 v3)
PJB> and have that be turned into a hash-table,
PJB> because you would have written it in the context of a DSL or macro,
PJB> that would have proven or assumed it is hash-table data.

PJB> In both cases, the sexp notation with no supplementary syntaxes is
PJB> enough to denote your high level data structures. 

OK, it's possible, but that's a terrible syntax. Maps should *look*
different from lists and their keys and values, in particular, should be
easily distinguished from each other.

PJB> If you want to cater to the need of the future programmers, perhaps it
PJB> would be better to go toward making lisp a more high level programming
PJB> language, not adding syntax and specific distinct data structures, but
PJB> by having a smarter "eval" engine that is able to prove things about the
PJB> denoted data and programs, and to translate it into the most adapted
PJB> data structures and algorithms.
...
PJB> Similarly, instead of dicussing about #S(hash-table) vs «» vs
PJB> #.(hash-table …), it would be better to think about implementing theorem
PJB> prover features into a lisp to make it a higher level programming
PJB> language, so you don't have to care about what exact low level data
PJB> structure or algorithm is used, as long as the system has been able to
PJB> prove nice features of your high level description, which can be already
PJB> written with plain sexps.

I'll put that on my TODO list, sure :)

Ted

Re: plists, alists, and hashtables

[Pascal J. Bourguignon]

Ted Zlatanov <tzz@lifelogs.com> writes:

> OK, it's possible, but that's a terrible syntax. Maps should *look*
> different from lists and their keys and values, in particular, should be
> easily distinguished from each other.

Why?

The whole point of lisp, is to recognize that things don't need to look
different at all, that you get much more mileage by using a uniform
syntax for everything: (operator argument argument…)
Or in the case of plain data: (type attribute attribute).
which is the same in the case of (BOA) constructors:

    (vector 1 2 3)
    (list 'thx 1138)
    (point 10.3 12.4 'red)


I've been advocating for readtable and reader macros as a mean for _end_
_user_ extension, not because I support adding syntaxes to lisp.
Additionnal syntaxes can be useful, and should only be used, for end
users and DSL implementing a domain with pre-existing _extensive_ use of
that syntax.

For example, if you were programming a physics simulation, with a lot of
differential mathematical equations that you'd copy from books, you
might implement a DSL for infix mathematical expressions with all kinds
of reader macro to be able to transcribe the printed formular as closely
as possible (just to avoid bugs in the transcription, that will be performed
by your DSL reader macros and macros).    But even in this case, for new
code, you would be strongly advised to use lisp sexps, cf. sicm.
http://mitpress.mit.edu/sites/default/files/titles/content/sicm/book.html
https://www.youtube.com/watch?v=arMH5GjBwUQ


Notice that if you quote an expression using strange reader macros, you
will see what lisp expression it actually represent, and you can use
that instead.


For example, I have a reader macro that lets me write Objective-C FFI
calls in Common Lisp:

    [NSDictionary dictionary]
    --> #<ns-dictionary [uninitialized] (#x30BC10)>

If I wanted to avoid this reader macro, I could quote it, to see what it
reads as:

    '[NSDictionary dictionary]
    --> (objc:send ns:ns-dictionary 'dictionary)

    (objc:send ns:ns-dictionary 'dictionary)
    --> #<ns-dictionary [uninitialized] (#x30BC10)>

(in this case, I usually don't want to get out of the DSL, since it
implies a strong dependency on Objective-C frameworks, I just restrict
the use of the #\[ reader macro to low level system modules, not
spreading them all around the program).



But maps are not something out of this lisp world.  They existed from
the start as a-list, then p-list and then hash-tables.  They are a basic
data structure perfectly integrated to an algorithmic programming
language, and don't constitute a different, Domain Specific Language.

For this reason, they should use the usual lisp sexps.  Also:

 « Ceci est une chaîne de caractères ! »
 » Dies ist ein String « 

Therefore « and » are very confusing characters to choose for maps.


If you want some "syntax", could instead use → (but again, it's also a
heavily overloaded character).

  →(k1 v1
    k2 v2
    k3 v3)

which would read as:

  '→(k1 v1
     k2 v2
     k3 v3)
  --> #s(hash-table size 65 test eql rehash-size 1.5 
                    rehash-threshold 0.8
                    data (k1 v1 k2 v2 k3 v3))


Then you could define a printer for hash-tables to print them as 

  →(k1 v1
    k2 v2
    k3 v3)

Then you will have to patch all the editors in the world (not only
emacs, people also use vim, textmate, eclipse, notepad, etc to edit
lisp), to teach them about this → that is not inside the parentheses…

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

RE: plists, alists, and hashtables

[Drew Adams]

> I've been advocating for readtable and reader macros as a mean for _end_
> _user_ extension, not because I support adding syntaxes to lisp.

Yes, precisely.

> Additionnal syntaxes can be useful, and should only be used,
> for end users and DSL implementing a domain with pre-existing
          ^^^^^     ^^^
> _extensive_ use of that syntax.

Yes.  What other languages must do at language-design time, Lisp
users can do with Lisp code - at language-design time for a DSL.

My guess is that those not getting this have never used or heard of
something like the Common Lisp reader, where you-the-programmer can
define reader macros and pretty much create the syntax - whatever
syntax - you want.

We Lisp _users_ can make good use of syntax-defining constructs.
But Lisp itself does not need any syntactic embellishment, which
would in fact work against its nature.

> But maps are not something out[side] of this lisp world.  They
> existed from the start as a-list, then p-list and then hash-tables.
> They are a basic data structure perfectly integrated to an
> algorithmic programming language, and don't constitute a different,
> Domain Specific Language. For this reason, they should use the usual
> lisp sexps.

A good example.  But the same can be said for *any* construct, not just
maps.  We should not add special syntax to Lisp to support any construct.

We should not, and we should not need to.  The need that is not yet met
in Emacs Lisp is to give users themselves ways to define syntax.  Emacs
Lisp could really benefit from having a Common Lisp-like reader (in
particular, `set-macro-character' or similar).

Re: plists, alists, and hashtables

[Ted Zlatanov]

On Thu, 06 Aug 2015 20:46:09 +0200 "Pascal J. Bourguignon" <pjb@informatimago.com> wrote: 

PJB> Ted Zlatanov <tzz@lifelogs.com> writes:

>> OK, it's possible, but that's a terrible syntax. Maps should *look*
>> different from lists and their keys and values, in particular, should be
>> easily distinguished from each other.

PJB> Why?

Because I don't want to look at (a b c d e f g h) and count until I find
that g is a key and h is a value.  That's dumb and leads to mistakes.

PJB> Additionnal syntaxes can be useful, and should only be used, for end
PJB> users and DSL implementing a domain with pre-existing _extensive_ use of
PJB> that syntax.

My claim, I guess, is that general ELisp programming involves an
extensive use of maps, so it could use a syntax for it.

I am not making any philosophical claims about the essence of Lisp.

PJB> But maps are not something out of this lisp world.  They existed from
PJB> the start as a-list, then p-list and then hash-tables.  They are a basic
PJB> data structure perfectly integrated to an algorithmic programming
PJB> language, and don't constitute a different, Domain Specific Language.

I've given examples of why lists, in my opinion, don't make a good read
syntax for maps.  If that's not enough to convince people, then it's not
a good idea.

PJB> Therefore « and » are very confusing characters to choose for maps.

OK, that's fine.  I really don't want to care about the choice of markers.
It's completely irrelevant to me.  It could be "Pascal" on the left and
"Bourguignon" on the right, with "J" as the cell separator.

PJB> Then you will have to patch all the editors in the world (not only
PJB> emacs, people also use vim, textmate, eclipse, notepad, etc to edit
PJB> lisp), to teach them about this → that is not inside the parentheses…

Yup. I agree that adoption will be painful and slow, but it has to start
somewhere.

Ted

Re: plists, alists, and hashtables

[Pascal J. Bourguignon]

Ted Zlatanov <tzz@lifelogs.com> writes:

> On Thu, 06 Aug 2015 20:46:09 +0200 "Pascal J. Bourguignon" <pjb@informatimago.com> wrote: 
>
> PJB> Ted Zlatanov <tzz@lifelogs.com> writes:
>
>>> OK, it's possible, but that's a terrible syntax. Maps should *look*
>>> different from lists and their keys and values, in particular, should be
>>> easily distinguished from each other.
>
> PJB> Why?
>
> Because I don't want to look at (a b c d e f g h) and count until I find
> that g is a key and h is a value.  That's dumb and leads to mistakes.

But you never have  (a b c d e f g h).
You either have:    (:a b :c d :e f :g h)
or you have:        (a b
                     c d
                     e f
                     g h)

Really, it is quite rare that the form and type of the keys be the same
as for the values, so even when written on one line, there's no
confusion.

The only case where you would have the same form, is for an actual
dictionary to translate words, or a map used to represent a discrete
numeric function.

(defvar *increment[4]* (dictionary 0 1 1 2 2 3 3 0))
(defvar *localize* (dictionary "hello" "bonjour" "bus" "car" "car" "voiture" "hide" "cache" "cache" "cachette"))

could be confusing, but not:

(defvar *increment[4]* (dictionary 0 1
                                   1 2
                                   2 3
                                   3 0))

(defvar *localize* (dictionary "hello" "bonjour"
                               "bus" "car"
                               "car" "voiture"
                               "hide" "cache"
                               "cache" "cachette"))

 
> PJB> Additionnal syntaxes can be useful, and should only be used, for end
> PJB> users and DSL implementing a domain with pre-existing _extensive_ use of
> PJB> that syntax.
>
> My claim, I guess, is that general ELisp programming involves an
> extensive use of maps, so it could use a syntax for it.
>
> I am not making any philosophical claims about the essence of Lisp.

Well, as mentionned before, if you abstract away a given type of maps:

- you may hide the costs, and that would lead to bad results,

- you would impose one kind of data structure usage (mutable hash or
  immutable a-list or mutable a-lists or llrb-trees? etc)

- or if you don't and make it adaptative, we observe that there's
  actually very little gain obtained, (because it takes time to convert
  the data structures, and therefore it's hard to amortize that cost).


And therefore the general conclusion is that it's not such a good idea
to abstract away a higher level notion.

Ie. the programmers must have the choice between hash-table and a-list
or something else.

If you don't believe that, you can always implement a library to provide
a common API over various dictionaries. I did just that in CL:

https://gitlab.com/com-informatimago/com-informatimago/blob/master/common-lisp/cesarum/dictionary.lisp
(sorry, I've not written the automatic adaptative code yet).

Let me just say that this is not the API I reach first when I write lisp
code.  Just use a-lists or hash-tables directly, depending on the
circumstances determined at program-writting time.



> PJB> But maps are not something out of this lisp world.  They existed from
> PJB> the start as a-list, then p-list and then hash-tables.  They are a basic
> PJB> data structure perfectly integrated to an algorithmic programming
> PJB> language, and don't constitute a different, Domain Specific Language.
>
> I've given examples of why lists, in my opinion, don't make a good read
> syntax for maps.  If that's not enough to convince people, then it's not
> a good idea.

Notice that as mentionned before, the question here is whether that
should be included into the emacs lisp language, or whether that should
be defined as a user library.

As a user library nobody will say that it's a bad idea and that it
cannot have its usage in some program.

What we reject, is the idea that it should be included in the emacs lisp
language.

And this is why we feel the lack of reader macros, since that would
clearly allow you to write a new syntax in a user library, instead of
having to beg it from the emacs lisp language itself.



-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: plists, alists, and hashtables

[Stefan Monnier]

BTW, hash-tables are currently used very little in Elisp.
Several packages still use obarrays instead.  So a good first step might
be to go and change those packages to use hash-tables instead
of obarrays.


        Stefan

RE: plists, alists, and hashtables

[Drew Adams]

> if emacs lisp had readtables and reader macros like Common Lisp
> (or improved, like named readtables), we could introduce local
> syntaxes for specific packages.  You could even make use of some
> specific unicode characters that you can type non-clumsily on your
> keyboard...

+1

Re: plists, alists, and hashtables

[Stefan Monnier]

> (alist-get 'a '((a) (b 1) (c . 2) d)) -> nil
> (alist-get 'b '((a) (b 1) (c . 2) d)) -> (1)
> (alist-get 'c '((a) (b 1) (c . 2) d)) -> 2

These are all consistent since your list is really

   ((a . nil) (b . (1)) (c . 2) d)

> (alist-get 'd '((a) (b 1) (c . 2) d)) -> nil ; no error

Just like Javascript, Elisp often errs on "don't signal an error" when
it bumps into something that's of the wrong type.  I don't like it very
much, but it has its advantages as well.

> The real map type in Emacs Lisp is the hashtable, I think.

I think that's a bias you get from other languages.

> For instance, the hashtable keys are unambiguously
> (hash-table-keys my-hashtable) and there's no looping or parsing.

For instance, the alist's keys are unambiguously (mapcar #'car my-alist) 
and there's no looping or parsing.

Also known as:

   For instance, the plist's keys are unambiguously (plist-keys my-plist)
   and there's no looping or parsing.

[ And no, please don't go and add plist-keys to subr-x.el.  ]

> However after perl and python (and awk) and... almost any language invented
> in the last 20 years, its rather backward.
> The efficiency is one thing

The efficiency argument is far from clear, since the cut-off point is
not too far from 100 last time I checked (IOW alist-get is faster than
gethash for tables of less than a hundred elements).  That was a while
ago, so it may be worth re-benchmarking it.  Also, I'd welcome patches
which optimize hash-tables for smaller sizes.

In any case, other than a vague complaint about Elisp being different
from your favorite language, I don't know precisely how to interpret
this thread.

More specifically, I highly doubt that a special «k1 v1 k2 v2 ...»
syntax for hash-tables would make much difference compared to
(hash-table k1 v1 k2 v2 ...) which you can get today with a very simple
`hash-table' macro.  I mean, you'd still have to say (gethash k m),
whereas you'd probably want something like m.k, etc...
For better or for worse, Elisp is not Python.


        Stefan

Re: plists, alists, and hashtables

[Pascal J. Bourguignon]

Stefan Monnier <monnier@iro.umontreal.ca> writes:
> More specifically, I highly doubt that a special «k1 v1 k2 v2 ...»
> syntax for hash-tables would make much difference compared to
> (hash-table k1 v1 k2 v2 ...) which you can get today with a very simple
> `hash-table' macro.  I mean, you'd still have to say (gethash k m),
> whereas you'd probably want something like m.k, etc...
> For better or for worse, Elisp is not Python.

I would like that while elisp lacks reader macros, you can still do a
lot of things (with a pinch of kludgery) with macros.

For example, you could write something like:

 (with-my-syntax
    (let ((h «k1 v1 k2 v2 k3 v3»))
       h.k4:=44
       print (list h.k1 h.k2)))

Notice that the lisp reader will read as symbols things that you'd wish
to be separate tokens:

(flatten '(with-my-syntax
            (let ((h «k1 v1 k2 v2 k3 v3»))
               h.k4:=44
               print (list h.k1 h.k2))))
--> (with-my-syntax let h «k1 v1 k2 v2 k3 v3» h\.k4:=44 print list h\.k1
            h\.k2)

Nonethelss, your with-my-syntax macro can parse those symbols, and
reconstitute a normal sexp:

(macroexpand ' (with-my-syntax
                  (let ((h «k1 v1 k2 v2 k3 v3»))
                     h.k4:=44
                     print (list h.k1 h.k2))))
--> (let ((h (hash-table 'k1 'v1 'k2 'v2 'k3 'v3)))
       (setf (gethash 'k4 h) 44)
       (print (list (gethash 'k1 h) (gethash 'k2 h))))


So you can still be happy.

The only constraint is that you cannot have an unbalanced sexp in the
body of your macro (parentheses, double-quote strings, vector brackets,
etc).

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: plists, alists, and hashtables

[Ted Zlatanov]

On Thu, 06 Aug 2015 15:12:54 -0400 Stefan Monnier <monnier@iro.umontreal.ca> wrote: 

>> (alist-get 'd '((a) (b 1) (c . 2) d)) -> nil ; no error

SM> Just like Javascript, Elisp often errs on "don't signal an error" when
SM> it bumps into something that's of the wrong type.  I don't like it very
SM> much, but it has its advantages as well.

Sure, absolutely.  I'm trying to say that a better read syntax for maps
could avoid that altogether by making it impossible to specify something
like the alist above.

>> For instance, the hashtable keys are unambiguously
>> (hash-table-keys my-hashtable) and there's no looping or parsing.

SM> For instance, the alist's keys are unambiguously (mapcar #'car my-alist) 
SM> and there's no looping or parsing.

(mapcar #'car '((a) (b 1) (c . 2) d))
-> Debugger entered--Lisp error: (wrong-type-argument listp d)

...and that's just a simple edge case.

So you have to do

(delq nil (mapcar #'car-safe '((a) (b 1) (c . 2) d)))

When the backend implementation is also the frontend, as with alists,
you have to go through the whole alist to collect the keys. That's the
access-time looping and parsing I mean. By contrast, the hashtable
implementation (whether it does it now or not) can keep the list of keys
and update it only when the data is modified.  At access time, the keys
are instantly available.

SM> [ And no, please don't go and add plist-keys to subr-x.el.  ]

Heh, no, `loop' works well enough for me :)

SM> More specifically, I highly doubt that a special «k1 v1 k2 v2 ...»
SM> syntax for hash-tables would make much difference compared to
SM> (hash-table k1 v1 k2 v2 ...) which you can get today with a very simple
SM> `hash-table' macro.  I mean, you'd still have to say (gethash k m),
SM> whereas you'd probably want something like m.k, etc...

Maybe the macro is good enough, but I think the keys and values have to
be clearly separated from each other and from other cells to make it
visually useful.  The key for me is that I'm not looking to make
hashtables themselves more prominent, but to give ELisp users a way to
read and write maps more clearly and in a way that maps more closely to
a true map data type (which I thought the hashtable was).

The second part of my question was whether Customize support for
hashtables would make them more approachable and useful.

SM> More importantly, mathematical maps are persistent, whereas your
SM> apparently favorite implementation (the hash-table) is not persistent,
SM> contrary to (e.g.) alists.

I am not sure what you mean.  Perhaps it's a problem with the
terminology.  Could you explain?

Ted

RE: plists, alists, and hashtables

[Drew Adams]

> The second part of my question was whether Customize support for
> hashtables would make them more approachable and useful.

So the argument is that Customize is more user friendly for a
programmer than are the Lisp hashtable functions?  I'm surprised. ;-)

Re: plists, alists, and hashtables

[Ted Zlatanov]

On Thu, 6 Aug 2015 14:10:20 -0700 (PDT) Drew Adams <drew.adams@oracle.com> wrote: 

>> The second part of my question was whether Customize support for
>> hashtables would make them more approachable and useful.

DA> So the argument is that Customize is more user friendly for a
DA> programmer than are the Lisp hashtable functions?  I'm surprised. ;-)

I mean that packages would have hashtable variables and let end users
Customize them directly, like they can Customize the `alist' and `plist'
types currently.

Ted

Re: plists, alists, and hashtables

[Stefan Monnier]

> Sure, absolutely.  I'm trying to say that a better read syntax for maps
> could avoid that altogether by making it impossible to specify something
> like the alist above.

You can't "make it impossible".
So, IIUC you want to signal errors for invalid maps.

> (mapcar #'car '((a) (b 1) (c . 2) d))
> -> Debugger entered--Lisp error: (wrong-type-argument listp d)
> ...and that's just a simple edge case.

So, now you don't want to signal errors for invalid maps?
Make up your mind.

> So you have to do
> (delq nil (mapcar #'car-safe '((a) (b 1) (c . 2) d)))

No: ((a) (b 1) (c . 2) d) is an invalid map, and it's perfectly OK (tho
not mandatory either) to signal an error when faced with such a thing.

> When the backend implementation is also the frontend, as with alists,
> you have to go through the whole alist to collect the keys. That's the
> access-time looping and parsing I mean. By contrast, the hashtable
> implementation (whether it does it now or not) can keep the list of keys
> and update it only when the data is modified.  At access time, the keys
> are instantly available.

Reality check: Have you looked at the definition of hash-table-keys?
Better yet: have you looked at how often hash-table-keys is used?
The efficiency of map-keys is largely irrelevant.

SM> More importantly, mathematical maps are persistent, whereas your
SM> apparently favorite implementation (the hash-table) is not persistent,
SM> contrary to (e.g.) alists.
> I am not sure what you mean.  Perhaps it's a problem with the
> terminology.  Could you explain?

alists can be functional, whereas hash-tables are by nature imperative.
For example,

   (cons (cons k v) m)

returns a new alist with a new mapping from "k" to "v" without changing
the map "m".  Whereas after

   (puthash k v m)

"m" has necessarily been modified.


        Stefan

Re: plists, alists, and hashtables

[Ted Zlatanov]

On Thu, 06 Aug 2015 17:31:29 -0400 Stefan Monnier <monnier@iro.umontreal.ca> wrote: 

SM> So, IIUC you want to signal errors for invalid maps.

That's what I meant, yes.  The syntax to specify an invalid map would be
invalid at the reader level and generate an error when the source code
is parsed.

>> (mapcar #'car '((a) (b 1) (c . 2) d))
-> Debugger entered--Lisp error: (wrong-type-argument listp d)
>> ...and that's just a simple edge case.

SM> So, now you don't want to signal errors for invalid maps?
SM> Make up your mind.

I am showing how extracting the keys of an alist can generate *runtime*
errors, when the alist has already been read in.  Which makes actual
maps more appealing, I thought, because they could avoid that problem at
the reader level.

SM> Reality check: Have you looked at the definition of hash-table-keys?
SM> Better yet: have you looked at how often hash-table-keys is used?
SM> The efficiency of map-keys is largely irrelevant.

Right. I agree. My point was different: there is no "keys" function for
alists and plists.  Keys in those two formats are a convention.

SM> More importantly, mathematical maps are persistent, whereas your
SM> apparently favorite implementation (the hash-table) is not persistent,
SM> contrary to (e.g.) alists.
>> I am not sure what you mean.  Perhaps it's a problem with the
>> terminology.  Could you explain?

SM> alists can be functional, whereas hash-tables are by nature imperative.
SM> For example,

SM>    (cons (cons k v) m)

SM> returns a new alist with a new mapping from "k" to "v" without changing
SM> the map "m".  Whereas after

SM>    (puthash k v m)

SM> "m" has necessarily been modified.

I certainly see the advantages of appending instead of modifying in
place. I think that's an artifact of the current hashtable API, not a
fundamental property of maps or hashtables. Would it be useful if, in
addition to the reader syntax, "maps" (backed by hashtables or something
else) were made cons-able as you describe? Or is that fundamentally
impossible in your opinion?

Ted

Re: plists, alists, and hashtables

[Pascal J. Bourguignon]

Ted Zlatanov <tzz@lifelogs.com> writes:

> Right. I agree. My point was different: there is no "keys" function for
> alists and plists.  Keys in those two formats are a convention.

Also, there's rassoc!

    (let ((alist '((:one . 1) (:two . 2) (:three . 3))))
       (list (cdr (assoc  :two alist))
             (car (rassoc 1 alist))))
    --> (2 :one)

Do that with a hash-table!!!

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: plists, alists, and hashtables

[Stefan Monnier]

> I am showing how extracting the keys of an alist can generate *runtime*
> errors, when the alist has already been read in.  Which makes actual
> maps more appealing, I thought, because they could avoid that problem at
> the reader level.

I'd estimate that it would catch 0.05% of the errors a bit earlier, yes.

> Right. I agree. My point was different: there is no "keys" function for
> alists and plists.

(mapcar #'car ...) *is* the "keys" function for alists.  You could
define it as `alist-keys', or use `map-keys' from map.el for that.
The only reason why it's never been defined so far is because (mapcar
#'car ...) is quite sufficient since extracting the list/set of keys of
a map is a rare operation.

> Keys in those two formats are a convention.

Yes but one you can rely on.

I think what you're getting at is that (core) Lisp is somewhat
"untyped", so alists/plists can't be distinguished from other data built
using cons-cells: only the user knows whether that cons cells is meant
to be an alist or a plist or something else.

> I certainly see the advantages of appending instead of modifying in
> place.  I think that's an artifact of the current hashtable API, not a
> fundamental property of maps or hashtables.

There are persistent hash-tables, indeed, but they typically use some
kind of tree/trie rather than one big hashing array.


        Stefan

Re: plists, alists, and hashtables

[Pascal J. Bourguignon]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> I think what you're getting at is that (core) Lisp is somewhat
> "untyped", so alists/plists can't be distinguished from other data built
> using cons-cells: only the user knows whether that cons cells is meant
> to be an alist or a plist or something else.

This is a strawman argument.

You can always wrap a-lists into a tagged type (a structure), and only
touch it thru checked functions.  This is what my dictionary abstraction
does.  Therefore you can prove that your a-list will never be
ill-formed.

This is useless, it's still more practical to use plain a-list, and not
for the syntax, but for the very reason that you can process a plain
a-list as if it wasn't an a-list and break the a-list invariant.


If your programming process require a formal approach where you have the
computer check your invariants, then be sure to wrap your a-lists in a
structure and a functional abstraction that let you control it.

Otherwise, you can use a-list directly, and syntactic suggar won't help,
but on the contrary detract you from writing good code.

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: plists, alists, and hashtables

[Stefan Monnier]

>> I think what you're getting at is that (core) Lisp is somewhat
>> "untyped", so alists/plists can't be distinguished from other data built
>> using cons-cells: only the user knows whether that cons cells is meant
>> to be an alist or a plist or something else.
> This is a strawman argument.

No: it's not an argument at all, it's a simple statement of fact.


        Stefan

Re: plists, alists, and hashtables

[Rusi]

On Saturday, August 8, 2015 at 7:12:07 PM UTC+5:30, Stefan Monnier wrote:
> >> I think what you're getting at is that (core) Lisp is somewhat
> >> "untyped", so alists/plists can't be distinguished from other data built
> >> using cons-cells: only the user knows whether that cons cells is meant
> >> to be an alist or a plist or something else.
> > This is a strawman argument.
> 
> No: it's not an argument at all, it's a simple statement of fact.

What is arguable is the 'somewhat' :-)

Re: plists, alists, and hashtables

[Pascal J. Bourguignon]

Ted Zlatanov <tzz@lifelogs.com> writes:

> So you have to do
>
> (delq nil (mapcar #'car-safe '((a) (b 1) (c . 2) d)))
>
> When the backend implementation is also the frontend, as with alists,
> you have to go through the whole alist to collect the keys. That's the
> access-time looping and parsing I mean. By contrast, the hashtable
> implementation (whether it does it now or not) can keep the list of keys
> and update it only when the data is modified.  At access time, the keys
> are instantly available.

Only they are NOT instantly available.  First it has to compute the hash
value, then it has to compute a division to find the modulo, and finally
it still has to walk a list or an array when there are collisions.

All this takes time, so much time that it's faster to walk 100 cons
cells and perform 50 comparisons of the keys in an a-list, that doing
all that in a hash-table!  Benchmarks prove it!

Now, I should mention that emacs lisp is an implementation where the
difference is the biggest.

In clisp (similar to emacs lisp, compiles to a bytecode VM), the
break-even point is at 35 entries, and in other CL implementations
compiling to native code, the break-even point is at 5 or 6 entries.

That means that there's room to optimize hash-tables in emacs lisp.

Nonetheless, there's an incompressible minimum break-even of half a
dozen, and most dictionaries ARE that small.
 


> Maybe the macro is good enough, but I think the keys and values have to
> be clearly separated from each other and from other cells to make it
> visually useful.  

I understand that, and I cannot advise more strongly that you add
newlines and indent your data to clearly show it.

         (hash-table  k1      v1
                      kkkk2   v2
                      k3      vvvvvv3)

(use M-x align-cols)

Notice that often keys are keywords:

         (hash-table  :k1      v1
                      :kkkk2   v2
                      :k3      vvvvvv3)

and emacs fontifies them nicely.


Also, I would admit that using parentheses around the entries could help
editing the data structure, since that allows adding or removing entries
easily with a structural editor like emacs+paredit.

        (mhash-table  (k1      v1)
                      (kkkk2   v2)
                      (k3      vvvvvv3))

It works well enough for a macro (eg. let), but for a function it is a
real bother:

        (fhash-table  '(k1      v1)
                      (list 'kkkk2  (+ 3 4))
                      (list 'k3     (f 'k3)))

Therefore I wouldn't advise to use anything more complex than a even
number of arguments,  alternating keys and values, to a function
constructor.



> The key for me is that I'm not looking to make
> hashtables themselves more prominent, but to give ELisp users a way to
> read and write maps more clearly and in a way that maps more closely to
> a true map data type (which I thought the hashtable was).
>
> The second part of my question was whether Customize support for
> hashtables would make them more approachable and useful.

This could definitely help.


> SM> More importantly, mathematical maps are persistent, whereas your
> SM> apparently favorite implementation (the hash-table) is not persistent,
> SM> contrary to (e.g.) alists.
>
> I am not sure what you mean.  Perhaps it's a problem with the
> terminology.  Could you explain?

SM means immutable.

And indeed, contrarily to the benchmark code I presented earlier, the
natural usage of a-lists is:

Is a key present?    (assoc key alist)            ; O(n)
 
Value for the key:   (cdr (assoc key alist))      ; O(n)

Add a key/value:     (acons key value alist)      ; O(1)

Remove a key:        now, if you use the "Is a key present?" above, 
                     you will need:

                     (remove key alist :key 'car) ; O(n)

                     otherwise (ie. when no value can be nil)
                     you can just do:

                     (acons key nil alist)        ; O(1)

The a-lists are therefore not mutated, and can be shared as the tail of
several variablt a-lists.

(defvar *defaults*   '((:move . walk) (:eat . swallow)))
(defvar *bird*       (acons :move 'fly *defaults*))
(defvar *mouse*      (acons :eat 'chew *defaults*))
(defvar *dead-mouse* (acons :move nil *mouse*))

(list *dead-mouse* *mouse* *bird* *defaults*)
--> (((:move) . #1=((:eat . chew) . #2=((:move . walk) (:eat . swallow))))
     #1# 
     ((:move . fly) . #2#)
     #2#)

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: plists, alists, and hashtables

[Ted Zlatanov]

On Fri, 07 Aug 2015 02:08:58 +0200 "Pascal J. Bourguignon" <pjb@informatimago.com> wrote: 
 
PJB> Ted Zlatanov <tzz@lifelogs.com> writes:
>> Maybe the macro is good enough, but I think the keys and values have to
>> be clearly separated from each other and from other cells to make it
>> visually useful.  

PJB> I understand that, and I cannot advise more strongly that you add
PJB> newlines and indent your data to clearly show it.

PJB>          (hash-table  k1      v1
PJB>                       kkkk2   v2
PJB>                       k3      vvvvvv3)

I don't think it's good to force the programmer to reformat their code
because the syntax doesn't do the right thing.

PJB> Also, I would admit that using parentheses around the entries could help
PJB> editing the data structure, since that allows adding or removing entries
PJB> easily with a structural editor like emacs+paredit.

PJB>         (mhash-table  (k1      v1)
PJB>                       (kkkk2   v2)
PJB>                       (k3      vvvvvv3))

PJB> It works well enough for a macro (eg. let), but for a function it is a
PJB> real bother

I think that's good enough in the `let' format, as a macro. The
syntactic shortcut of creating keys without a cell with a null value is
nice too. Can we agree that this is a good syntax and move back to
discussing Unicode markers again? :)

>> The second part of my question was whether Customize support for
>> hashtables would make them more approachable and useful.

PJB> This could definitely help.

OK, I'm glad you agree.  Maybe that discrete work would be generally
helpful regardless of the rest of this discussion.

PJB> Well, as mentionned before, if you abstract away a given type of maps:

PJB> - you may hide the costs, and that would lead to bad results,

PJB> - you would impose one kind of data structure usage (mutable hash or
PJB>   immutable a-list or mutable a-lists or llrb-trees? etc)

PJB> - or if you don't and make it adaptative, we observe that there's
PJB>   actually very little gain obtained, (because it takes time to convert
PJB>   the data structures, and therefore it's hard to amortize that cost).

I see your point.  It connects with Stefan's point about cons-ing alists
and plists because they're persistent.  Thank you for stating it well.

PJB> If you don't believe that, you can always implement a library to provide
PJB> a common API over various dictionaries. I did just that in CL:

PJB> https://gitlab.com/com-informatimago/com-informatimago/blob/master/common-lisp/cesarum/dictionary.lisp
PJB> (sorry, I've not written the automatic adaptative code yet).

PJB> Let me just say that this is not the API I reach first when I write lisp
PJB> code.  Just use a-lists or hash-tables directly, depending on the
PJB> circumstances determined at program-writting time.

OK, and your experience confirms the answer to my question.  This is
very helpful to countermand my intuition, which is perhaps guided too
much by the other languages I use.

PJB> Notice that as mentionned before, the question here is whether that
PJB> should be included into the emacs lisp language, or whether that should
PJB> be defined as a user library.

PJB> As a user library nobody will say that it's a bad idea and that it
PJB> cannot have its usage in some program.

Yup, I understand.  I'll look into making it.

PJB> And this is why we feel the lack of reader macros, since that would
PJB> clearly allow you to write a new syntax in a user library, instead of
PJB> having to beg it from the emacs lisp language itself.

Is this work already planned?

How much of it must be done to accomplish what I want, a library that
lets me say `{ "k1": "v1" }' (giving JSON syntax as an example) and
translates it to the correct #s(hash-table ...) serialization?

Together with the Customize support for hashtables, I think we can agree
these would be nice usability improvements.

Stefan also mentioned there could be performance optimizations for
hashtables themselves.  I think that's a good direction too.

Ted

Re: plists, alists, and hashtables

[Pascal J. Bourguignon]

Ted Zlatanov <tzz@lifelogs.com> writes:

> On Fri, 07 Aug 2015 02:08:58 +0200 "Pascal J. Bourguignon" <pjb@informatimago.com> wrote: 
>  
> PJB> Ted Zlatanov <tzz@lifelogs.com> writes:
>>> Maybe the macro is good enough, but I think the keys and values have to
>>> be clearly separated from each other and from other cells to make it
>>> visually useful.  
>
> PJB> I understand that, and I cannot advise more strongly that you add
> PJB> newlines and indent your data to clearly show it.
>
> PJB>          (hash-table  k1      v1
> PJB>                       kkkk2   v2
> PJB>                       k3      vvvvvv3)
>
> I don't think it's good to force the programmer to reformat their code
> because the syntax doesn't do the right thing.

But for a function, I'm saying it's more practical.

> PJB> Also, I would admit that using parentheses around the entries could help
> PJB> editing the data structure, since that allows adding or removing entries
> PJB> easily with a structural editor like emacs+paredit.
>
> PJB>         (mhash-table  (k1      v1)
> PJB>                       (kkkk2   v2)
> PJB>                       (k3      vvvvvv3))
>
> PJB> It works well enough for a macro (eg. let), but for a function it is a
> PJB> real bother
>
> I think that's good enough in the `let' format, as a macro. The
> syntactic shortcut of creating keys without a cell with a null value is
> nice too. Can we agree that this is a good syntax and move back to
> discussing Unicode markers again? :)

For a macro, ok.


> PJB> And this is why we feel the lack of reader macros, since that would
> PJB> clearly allow you to write a new syntax in a user library, instead of
> PJB> having to beg it from the emacs lisp language itself.
>
> Is this work already planned?

Well, once emacs got to git, I cloned it to do that, add CL packages and
reader macros to emacs.  But unfortunately I've not worked on it since.

But I'm planing a take over :-)  I'm writing a C parser in CL, so that I
may read the C sources of CL, and then translate them into maintainable
CL.  Then I will be able to compile a CL GNU emacs core, that would be
100% bug-for-bug compatible with GNU emacs, and on which you could run
all the .el (and even .elc) you'd want.

But since the core would be written in CL, I could now provide features
found in CL and in CL implementations, such as FFI, threads, packages,
readtables, etc, by merely providing access to the underlying CL API.

Basically, in GNU emacs, buffer-substring-no-properties is a C function.
In CL GNU emacs, buffer-substring-no-properties would be a Common Lisp
function, named by a CL symbol emacs:buffer-substring-no-properties.

You could write CL code in some CL package my-lib:process-buffer that
could call those core emacs functions.

For the emacs lisp functions more work will be needed, because from the
automatic translations we would just get an emacs lisp VM (and the
interpreter), working in a separate metalinguistic level.  Even if we
used CL symbols for the emacs lisp symbols, we couldn't funcall them
from CL, since there would be no CL function defined by emacs lisp
defun.  

And similarly, the readtable feature and CL package feature in emacs
lisp will have to be hacked similarly as well in CL GNU emacs than in
GNU emacs, but the difference is that then I'll be able to rely on the
underlying CL to implement them for emacs lisp. Basically, I'll have to
gut out some emacs lisp parts (eg. the emacs lisp reader), and implement
it as a Common Lisp readtable.  Then emacs lisp symbols will be CL
symbols and the package:symbol syntax will be available in emacs lisp to
call CL.  Then modifications to the interpreter and VM will allow
calling emacs lisp functions from CL, and we'll be set.


> How much of it must be done to accomplish what I want, a library that
> lets me say `{ "k1": "v1" }' (giving JSON syntax as an example) and
> translates it to the correct #s(hash-table ...) serialization?

Very little, since it's already implemented:

M-x package-install RET json RET
(require 'json) C-x C-e
{"k1":"v1"} C-a C-u M-: json-read RET
--> ((k1 . "v1"))


So: 

   (defmacro json-quote (string)
      (with-temp-buffer
        (insert string)
        (goto-char 0)
        `',(json-read)))

  (json-quote "{\"k1\":\"v1\"}") ; same problem as with regexp, 
                                 ; no reader macros to simplify this.
  --> ((k1 . "v1"))


> Together with the Customize support for hashtables, I think we can agree
> these would be nice usability improvements.
>
> Stefan also mentioned there could be performance optimizations for
> hashtables themselves.  I think that's a good direction too.
>
> Ted

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: plists, alists, and hashtables

[Ted Zlatanov]

On Fri, 07 Aug 2015 09:53:05 +0200 "Pascal J. Bourguignon" <pjb@informatimago.com> wrote: 

PJB> And this is why we feel the lack of reader macros, since that would
PJB> clearly allow you to write a new syntax in a user library, instead of
PJB> having to beg it from the emacs lisp language itself.
>> 
>> Is this work already planned?

PJB> Well, once emacs got to git, I cloned it to do that, add CL packages and
PJB> reader macros to emacs.  But unfortunately I've not worked on it since.

PJB> But I'm planing a take over :-)  I'm writing a C parser in CL, so that I
PJB> may read the C sources of CL, and then translate them into maintainable
PJB> CL.  Then I will be able to compile a CL GNU emacs core, that would be
PJB> 100% bug-for-bug compatible with GNU emacs, and on which you could run
PJB> all the .el (and even .elc) you'd want.

PJB> But since the core would be written in CL, I could now provide features
PJB> found in CL and in CL implementations, such as FFI, threads, packages,
PJB> readtables, etc, by merely providing access to the underlying CL API.

Let me rephrase my question: is the work of reader macros already
planned for the Emacs core as an incremental feature?  I'm not saying
your project is not valuable, but it seems a bit far in the future.

Ted

Re: plists, alists, and hashtables

[Pascal J. Bourguignon]

Ted Zlatanov <tzz@lifelogs.com> writes:

> On Fri, 07 Aug 2015 09:53:05 +0200 "Pascal J. Bourguignon" <pjb@informatimago.com> wrote: 
>
> PJB> And this is why we feel the lack of reader macros, since that would
> PJB> clearly allow you to write a new syntax in a user library, instead of
> PJB> having to beg it from the emacs lisp language itself.
>>> 
>>> Is this work already planned?
>
> PJB> Well, once emacs got to git, I cloned it to do that, add CL packages and
> PJB> reader macros to emacs.  But unfortunately I've not worked on it since.
>
> PJB> But I'm planing a take over :-)  I'm writing a C parser in CL, so that I
> PJB> may read the C sources of CL, and then translate them into maintainable
> PJB> CL.  Then I will be able to compile a CL GNU emacs core, that would be
> PJB> 100% bug-for-bug compatible with GNU emacs, and on which you could run
> PJB> all the .el (and even .elc) you'd want.
>
> PJB> But since the core would be written in CL, I could now provide features
> PJB> found in CL and in CL implementations, such as FFI, threads, packages,
> PJB> readtables, etc, by merely providing access to the underlying CL API.
>
> Let me rephrase my question: is the work of reader macros already
> planned for the Emacs core as an incremental feature?  I'm not saying
> your project is not valuable, but it seems a bit far in the future.

AFAIK, not by the emacs maintainers.
But this is free software, you are free to do it yourself!


-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: plists, alists, and hashtables

[Ted Zlatanov]

On Fri, 07 Aug 2015 12:35:01 -0400 Stefan Monnier <monnier@iro.umontreal.ca> wrote: 

>> Let me rephrase my question: is the work of reader macros already
>> planned for the Emacs core as an incremental feature?

SM> Check the emacs-devel mailing-list.  It was discussed not very long ago
SM> (a year or two, maybe?).

I think you maybe mean this?

https://lists.gnu.org/archive/html/emacs-devel/2015-01/msg00618.html

Started with "[PATCH] Clojure-like syntactic sugar for an anonymous function literal"

I don't see an actual decision regarding reader macros, just a lot of
discussion.  Should I start a new thread?  Or did you mean a different thread?

On Fri, 07 Aug 2015 12:32:28 -0400 Stefan Monnier <monnier@iro.umontreal.ca> wrote: 

SM> I think what you're getting at is that (core) Lisp is somewhat
SM> "untyped", so alists/plists can't be distinguished from other data built
SM> using cons-cells: only the user knows whether that cons cells is meant
SM> to be an alist or a plist or something else.

Yes, thank you for stating it clearly.  Pascal summarized why trying to
hack around that is not a great idea.

Ted

Re: plists, alists, and hashtables

[Stefan Monnier]

SM> Check the emacs-devel mailing-list.  It was discussed not very long ago
SM> (a year or two, maybe?).
> I think you maybe mean this?
> https://lists.gnu.org/archive/html/emacs-devel/2015-01/msg00618.html
> Started with "[PATCH] Clojure-like syntactic sugar for an anonymous
> function literal"

Yes.

> I don't see an actual decision regarding reader macros, just a lot of
> discussion.  Should I start a new thread?  Or did you mean
> a different thread?

There was no real decision, I just pointed out that support in the
tooling makes CL-style reader macros rather undesirable: they're
too powerful.


        Stefan

Re: plists, alists, and hashtables

[Pascal J. Bourguignon]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> SM> Check the emacs-devel mailing-list.  It was discussed not very long ago
> SM> (a year or two, maybe?).
>> I think you maybe mean this?
>> https://lists.gnu.org/archive/html/emacs-devel/2015-01/msg00618.html
>> Started with "[PATCH] Clojure-like syntactic sugar for an anonymous
>> function literal"
>
> Yes.
>
>> I don't see an actual decision regarding reader macros, just a lot of
>> discussion.  Should I start a new thread?  Or did you mean
>> a different thread?
>
> There was no real decision, I just pointed out that support in the
> tooling makes CL-style reader macros rather undesirable: they're
> too powerful.

In the context of emacs, one could have a declarative definition of
reader macros; basically just an attributed grammar.  Then it can be
used to define the reader macro parser, the formatter, and the
structured editing function.  Just like in the synthesizer editor.

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

Re: plists, alists, and hashtables

[Stefan Monnier]

> Let me rephrase my question: is the work of reader macros already
> planned for the Emacs core as an incremental feature?

Check the emacs-devel mailing-list.  It was discussed not very long ago
(a year or two, maybe?).


        Stefan