Thank you so much for your detailed explanation.
On Sat, Apr 27, 2019 at 10:46 AM Joh-Tob Schäg <johtob...@gmail.com> wrote:
> Lisp is language where expression are executed in order. Since lisp code
> is expressed in data, we need something that has a way of expression of
> express ordering.
> That is possible in a dictionary too. Let's imagine the code:
> {fak => {1 => {1 => N}, {2=>{1=>if, 2=>{1 => =, 2=> N, 3=>0}, 3=>1,
> 4=>{1=> *, 2=> N ,3=> {1=>fib, 2=>{1=>dec,2=>N}}}}}}}
> I think we would need 9 independent hash tables to store simplest of
> programs i could come up with. Of course another grammar would be choose
> which leads to flatter hierarchies but that is a point which i can not
> elaborate further here.
>
I was thinking along the lines of transforming a list -> (A B C) into {1 A,
2 B, 3 C} where the ordering simply transforms into an ordered key. Or
transforming a dictionary {K1 : V1, K2: V2} into a list as (K1 V1 K2 V2).
Which in my mind would translate into 1 list transforms into 1 dictionary
or the other way.
> I doubt that dictionaries would more efficient. This idea may stem from a
> confusion about O(x). The big O notation talks about asymptotic time
> complexity as how do they compare when the number of elements gets
> infinite. Many problems of humans including computing are decidedly finite,
> maybe even "small". Algorithms with worse BigO might be better for many all
> practical use cases.
>
> Furthermore a person stating that dicts are a more efficient has probably
> a) never used one in the way i stated above
> b) has never looked at the assembly for both
> c) is unaware of the cache hierarchy
>
>
Efficiency was only a "potential" possibility I was suggesting but I
totally get what you are saying and I don't believe that O(1) promise of
hashtable is a free of caveats.
> I invite you to reflect your idea bearing these in mind.
> Furthermore hash table (how you would often implement a dict) does not
> "really" have an access time of 0(1) it has a best case O(N/m) where N is
> the number of elements and M the number of buckets The O(1) like behaviour
> is achieved by doing a rehashing in to a larger hash table which is a
> N*O(n/m) effort.
> Furthermore many operations possible with lists are not trivially possible
> with dicts that replace lists.
> Nesting as seen above is one of them.
> Operations which require a complete rehash of the hash table are:
> - inserting an element anywhere
> - removing an element anywhere
>
> Furthermore as seen above access time of any element in a hash table is
> proportional to: O(N/M)
> Access time in a list is proportional to: O(N-K) where the Nth element is
> the one we want to get and the Kth is element we know and use a an
> entrypoint to gollow the list.
> Getting the next element in a list is there for O(1) while in a hash table
> it is O(N/M) with an additional overhead for calculating the hash table.
> If you have an strict ordering of execution (as you might want as a
> programmer) a list gives you fast access to the next piece of code. A hash
> table would give you access to all elements equally slow.
>
> Additionally hash tables are when used as above way more space inefficient
> than linked lists. That means fewer information fits in the cache ->
> slower. For the performance of the Hash tables it is important that things
> are equally distributed over all buckets. This is done by using a hash that
> places them "without pattern". (In hash table theory the ideal hash table
> uses a random oracle to generate the hashes, which is random number
> generator that gives you an random number for a never seen before item or
> the number from last time if the item is already known)
> This kills the cache and all speculative execution schemes used to speed
> up modern processors.
>
Would I be right if I summarize the above as - operational efficiency the
reason List is chosen as the data structure for LISP? And it doesn't hurt
that it is also the simpler of the two :)
>
> I invite you to program a lisp interpreter in lua with the addressing
> scheme above. Lua has only hash tables as data structure. You can see if
> you are faster. I guess you are not. Even if you run a LuaJIT which
> compiles stuff done and is quiet competitive speed wise.
>
>
No thanks :) .. PicoLisp is my final language!
>
>
>
>
>
> On Sat, 27 Apr 2019 at 17:26, C K Kashyap <ckkash...@gmail.com> wrote:
>
>> Hi Alex et al,
>> I've wondered about this question for a bit. Why should list be the
>> fundamental data type? Should it not be a dictionary? Dictionary is
>> essentially a function - mapping a domain to a range.
>>
>> Is it that list could be built more easily with cons cell as the building
>> block? Is it like list and dictionary are like the universal gates nand and
>> nor - one is preferred because of the nature of the material being used? I
>> use the universal gates example here because I was fascinated by the idea
>> that I could represent a dictionary in a list (although less efficient) and
>> a list in a dictionary (potentially improving the efficiency).
>>
>> Regards,
>> Kashyap
>>
>
