Hi,
Maybe one reason is will it be complicated to do garbage collection on a hash
table? In theory its possible but maybe it will be a bit tedious compare to
linked list data struct.
BR,
geo
> On Apr 28, 2019, at 3:24 AM, C K Kashyap <ckkash...@gmail.com> wrote:
>
> 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
