On Sunday, July 31, 2016 at 7:07:45 AM UTC+5:30, Gregory Ewing wrote: > Michael Torrie wrote: > > Python would have been alright to teach "programming," but to > > teach the actual theory of programming languages (lambda calculus, lists > > as a foundation unit for all other data structures) > > I wouldn't say that "lists as a foundation unit for all other > data structures" is (or should be) part of the fundamental theory > of programming languages. > > It seems to me that Python's notions of sequences and mappings > are much more general and elegant theoretical elements to build > on.
A key component of a fundamental theory of computation is the idea of a universal data structure. For a turing machine its the tape that can carry data or another TM to make a UTM (UNIVERSAL turing machine) For a von Neumann machine its the memory that is impartial to whether its holding data or code (as against Harvard architecture) https://en.wikipedia.org/wiki/Harvard_architecture#Contrast_with_von_Neumann_architectures For Gödel's theorem it is humonguous integers which can ‘carry’ plain ol’ integers or theorems, proofs and effectively ‘the whole world’ via the Gödel-numbering: https://en.wikipedia.org/wiki/G%C3%B6del_numbering At the other end of the spectrum is Lisp whose S-expression is likewise universal and can be effectively used for carrying the whole theory much more elegantly than Turing more elegantly than Gödel: http://www.diku.dk/~neil/comp2book2007/book-whole.pdf From a software engineering pov, yes one can encode any data structure as arbitrary length integers. It works as data structure but its a horrible. This is the Gödel approach By cutting up the humonguous number into small squares on a tape, Turing’s approach is more tractable. Its still clumsy because it requires parsing. Structure the tape as a tree and this nuisance vanishes. This Lisp/S-exp/Neil-Jones cleanest of all solutions is like everything else in our field least known. Of course one could argue that mapping is somehow more universal than list. [I have often pondered this question] ie one can represent [a,b,c] as {0:a, 1:b, 2:c} Still, whatever is chosen, one needs one single data structure (or more correctly data type) to carry the whole world. Lists PLUS Mappings will not do [Note I am not talking software engineering but requirements for a complete theory] -- https://mail.python.org/mailman/listinfo/python-list
