Re: plists, alists, and hashtables

[Ted Zlatanov <tzz@lifelogs.com>]

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