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 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 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. 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. 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 >
