Re: [clean-list] GRS vs LTRS
Dear Vag, Vag wrote: To put in the nutshell, my point is that dag rewriting is better than graph rewriting as `base' of pure functional programming languages without manual proofs. Better in the sense easier to reason about: I agree. Better in the sense we do not need cycles: strongly disagree. There are algorithms that only have a reasonable complexity/efficiency due to a cycle. Without cycles we would need a more complex algorithm to mimic the effect. Cycles are nor used every day, but they do occur in real programs (not just Hamming numbers). Consider a compiler that translates statements to machine instructions. This compilers yields the statements as well as the actual address for all labels used (in a tuple or record). These positions are feed to the compiler in order to generate the correct jumps. You can do this very elegantly with a cycle. If you cannot make this cycle you will probably need a two stage solution. Best, Pieter ___ clean-list mailing list clean-list@science.ru.nl http://mailman.science.ru.nl/mailman/listinfo/clean-list
Re: [clean-list] GRS vs LTRS
To put in the nutshell, my point is that dag rewriting is better than graph rewriting as `base' of pure functional programming languages without manual proofs. ___ clean-list mailing list clean-list@science.ru.nl http://mailman.science.ru.nl/mailman/listinfo/clean-list
Re: [clean-list] GRS vs LTRS
Vag wrote: Universality vs Versatility --- Notice that people use PLs not for expressing any computable function but for solving real world problems that end users face with. I have been programming for nearly 30 years, solving all sorts of problems, most have been real world problems and being able to express any computable function comes in very handy in solving these real world problems. My business has been to provide solutions to these end users because they have had no way of working out how to do the tasks required because they could not express the computable functions they required. Other people with the same length or more of years may have different opinions. Vag, all languages are used to express ideas and concepts. They are a method of communication. In the case of programming languages, they are a method of communicating with a machine as well as communicating with people about what you are trying to achieve. Turing equivalency is a absolute PL power, utmost physically reachable limit. It may be interesting for physicians and philosophers, but has nothing to do with programmer job or maybe even computer scientist job. Not having a Turing complete programming language is a real pain in the neck when trying to solve may real world problems. It forces one to have to go outside the programming language at hand and use another tool (programming language) to add the facilities missing - example would be the common SQL use for common database activities. Let call PL _suitable_ for problem domain if any needed job can be completed in reasonable time using tolerable means. Let call PL _versatile_ if it suitable for _most_ (and most popular) problem domains. A programming language suitable for a problem domain allows you to solve the problem without having to jump through hoops to get simple tasks done let alone complex ones. Versatile languages is obviously much less powerful than Turing-equivalent ones. It may be easily seen on personal experience, source code analysis and experience of Flow Based Programming. Versatile languages should be Turing complete but also focussed on the problem domain at hand. No glimpses at PLs -- It is very important fact that PL X may be adequately evaluated by people if and only if that people has mature knowledge of basic programming techniques in X. Very often difficulties and hitches with implementing one or another familiar trick on new programming language characterizes not that language but lack of solid programming techniques equipment. I suspect that many hypothetic languages was underestimated and mistakingly rejected with their imaginable weakness associated with turing incompleteness just because familiar languages are turing complete. Disagree - anything that one can do in one Turing complete programming language you can do in another. But if the programming language is not Turing complete, there will be many activities that one cannot ever do without making it Turing complete or allowing the programmer to escape to another programming language to do the activity in question. Useful things can be done with languages that are not Turing complete but outside that you are stuck on the reef hard and fast. Programmers Do Not Tie Knots I have a clingy impression that cycles in data structures are almost not used even in programming pearls, not to mention common practice. Is it for my personal ignorance, or for juvenility of functional programming techniques panoply, or its intrinsic attribute (so it never be widely used)? Cycles in data structures or code are used in just about every state machine. Every computer depends on cycles in data to do effective tasks. Can somebody suggest any ways to analyse source code that able to perform queries of this sort on given large code base with relatively small programming efforts? Then we will have certain and heavily justified answer with strong evidence. Engieneering is Restricting --- Engineering is about simplification of the problem at hand. Making a model that works. Sometimes it is about restrictions. Each added feature increases PL expressiveness and make typical program patterns concise but it also brings in ways to do mistakes, add paths to confusion, hoicks learning curve and drastically complicates automated reasoning. Fully automated reasoning (AR) is very important because without it tools never be scalable and robust (take, for instance, CLEAN type system: ask CLEAN programmer, what if (s)he required to do manual proof of type correctness each time?). We must take into consideration not currently existing AR tools but future ones too (CLEAN supposed to will lasting for many years, isn't it? So ARs for CLEAN programs definitely will come into being, and by the way, we already have SPARKLE). I'll put a comment for discussion that adding restrictions to
Re: [clean-list] GRS vs LTRS
The compiler probably already converts recursive lets/wheres to non-recursive lets/wheres internally if this is possible. But I don't think that this will solve you problem. Recursive function definitions are just as powerful as recursive lets. Also, data structures and functions are interchangeable. Therefore, as long as you permit any kind of recursion, you will always have this issue. Any Turing-complete (or equivalent to lambda calculus) language will have nontermination issues. If you do want guaranteed termination, you will have to use a less powerful (or strongly normalizing) system, which cannot express all computable functions. That is why recursion (and recursive lets or similar and semantically equivalent language constructs) are important. I hope this gives you a general idea about why removing recursive lets/wheres won't be enough to prevent nontermination. Can you explain more about the specific issue you are trying to resolve? kind regards, Arjen Vag wrote: Why CLEAN is based on GRS instead of LTRS? Recursive let seems to be not so useful, but cyclic links in data makes automatic reasoning very hard and gives another evil source of nontermination. Maybe it is worth to add a compiler option to deny recursive lets (and wheres) per module and convert them internally to let-befores? ___ clean-list mailing list clean-list@science.ru.nl http://mailman.science.ru.nl/mailman/listinfo/clean-list ___ clean-list mailing list clean-list@science.ru.nl http://mailman.science.ru.nl/mailman/listinfo/clean-list
Re: [clean-list] GRS vs LTRS
Universality vs Versatility --- Notice that people use PLs not for expressing any computable function but for solving real world problems that end users face with. Turing equivalency is a absolute PL power, utmost physically reachable limit. It may be interesting for physicians and philosophers, but has nothing to do with programmer job or maybe even computer scientist job. Let call PL _suitable_ for problem domain if any needed job can be completed in reasonable time using tolerable means. Let call PL _versatile_ if it suitable for _most_ (and most popular) problem domains. Versatile languages is obviously much less powerful than Turing-equivalent ones. It may be easily seen on personal experience, source code analysis and experience of Flow Based Programming. No glimpses at PLs -- It is very important fact that PL X may be adequately evaluated by people if and only if that people has mature knowledge of basic programming techniques in X. Very often difficulties and hitches with implementing one or another familiar trick on new programming language characterizes not that language but lack of solid programming techniques equipment. I suspect that many hypothetic languages was underestimated and mistakingly rejected with their imaginable weakness associated with turing incompleteness just because familiar languages are turing complete. Programmers Do Not Tie Knots I have a clingy impression that cycles in data structures are almost not used even in programming pearls, not to mention common practice. Is it for my personal ignorance, or for juvenility of functional programming techniques panoply, or its intrinsic attribute (so it never be widely used)? Can somebody suggest any ways to analyse source code that able to perform queries of this sort on given large code base with relatively small programming efforts? Then we will have certain and heavily justified answer with strong evidence. Engieneering is Restricting --- Each added feature increases PL expressiveness and make typical program patterns concise but it also brings in ways to do mistakes, add paths to confusion, hoicks learning curve and drastically complicates automated reasoning. Fully automated reasoning (AR) is very important because without it tools never be scalable and robust (take, for instance, CLEAN type system: ask CLEAN programmer, what if (s)he required to do manual proof of type correctness each time?). We must take into consideration not currently existing AR tools but future ones too (CLEAN supposed to will lasting for many years, isn't it? So ARs for CLEAN programs definitely will come into being, and by the way, we already have SPARKLE). More restrictions means more tools, broader application, less errors. Almost all programs I ever seen may be implemented in functional programming language with automatic totality checking using techniques like mentioned in Total Functional Programming by David Turner and Ensuring Streams Flow by Alastair Telford and David Turner. As first step to bring growing CLEAN code base close to future standards it will be excellent to ban cyclic data structures so programmers can be sure they are not accidentally let one creep in. Later (when code base become large) this may become much more expensive. So we get two CLEAN sub languages -- fully powered one for rare careful system programming and one for robust application programming using ARs. ___ clean-list mailing list clean-list@science.ru.nl http://mailman.science.ru.nl/mailman/listinfo/clean-list
