On Wed, Apr 17, 2013 at 5:40 PM, Mark Janssen <dreamingforw...@gmail.com> wrote: > Rercursion the "bedrock" of language-design. I don't think so. From > what I know, a well-defined language ends at its symbols. It makes no > use of "infinities".
>From what I know, you can't have a Turing-complete language without some form of recursion. So yeah, it's pretty damn important in language design. >> You cannot hope to define an infinite object such as the python >> language (there are an infinite number of python programs) with a >> finite specification > > You've committed two grave sins in C.S.: You've just committed the grave sin of being needlessly hyperbolic. > Conflating a programming > language ("an infinite object such as python language") with a program > written in that language ("there are an infinite number of python > programs"). These two are entirely separate (at least anything > implemented on a real computer). Mathematically, a language (e.g. a programming language) is a set of well-formed strings (i.e. programs) constructed from the symbols of an alphabet (i.e. tokens). For most languages, this set is infinite; saying "the Python language is infinite" is equivalent to saying "there are an infinite number of Python programs". > Further, you've made a silly > description of python "an infinite object such as the python > language". A programming language that is well defined has complete, > finite, specification. The fact that there are an endless number of > programs that can be made from such is irrelevant to the language > itself. A finite, non-recursive grammar can only hope to accept a finite number of strings. To have an infinite language, the defining grammar must then be either infinite (not practical) or recursive. > Well now you're getting to the root of the confusion and what I'm > arguing within the C.S. community: there must be clear distinction > between lambda calculii and programming languages rooted in actual > hardware implementations. While, traditionally, the field has not > made much of a distinction, in practice the computational architecture > is different. One of these has a connection to reality and the other > not as much ;^). > In any case, talking about the mathematical realm *as a realm of > Platonic thought* is irrelevant to the discussion of program spaces > where *things actually get done*. Of course it's relevant. Without theory we would not have big-Oh notation or efficient data structures or regular expressions or context-free grammars; languages like Python would be harder to invent. I'm sure one could come up with a myriad other examples, but that's enough for me. -- http://mail.python.org/mailman/listinfo/python-list