Principles and Laws of Problem Solving in SequenceL: Software Engineering using a Declarative Language
From CS Colloquium
Tuesday, 26 Feb, 2008, 12:15, CS Conf Room
Daniel E. Cooke, Department of Computer Science, Texas Tech University
Synopsis
According to S.P. Jones, one of the developers of Haskell, "Any language large enough to be useful is dauntingly complex." An opposing view was given 27 years ago in C.A.R. Hoare’s Turing Award lecture, “The price of reliability is the pursuit of the utmost simplicity.” It is interesting that Hoare’s view was probably the predominating view when he stated it. In the intervening years we have seen growth in Object-Oriented Programming and dauntingly complicated desktop systems, perhaps leading to Jones’ quote in 2002.
We posit that, as it pertains to computer languages, Jones’ quote may be the most widely held today. Much of the Computer Science community is vested in research to help organize the complexity of the dauntingly complex languages we use to organize the complexity of problem solving. Many Computer Scientists have adopted the view that complicated tools are needed to solve complicated problems. This does not imply that Computer Scientists, in general, do not seek simple solutions. Our comments are focused on the languages used. Although there are advantages to the current problem-solving environments there remains a need to develop simpler tools, especially simpler languages.
We claim the trouble with existing tools is the gap or distance between the mental model of a user and the requirements and the distance between the requirements and the program. To contend with these gaps Computer Scientists have spent decades developing model-based approaches to programming. However, the gaps between most of the modeling languages and the resulting programs remain deep and wide and complicated by the complexity of the modeling languages, themselves. Consequently, trust in the quality of a synthesis tool is compromised. Furthermore, many of the modeling languages are so complicated that the distance from the mental model of the solution and the modeling language representation is also remote.
If we accept Hoare’s claim – that simplicity is the key to the development of trusted software, then what is the key to simplicity? We claim that languages must be small and concise. SequenceL, the language we have developed, can be reduced to roughly 9 grammar rules. You can carry the language around in your head – you don’t need reference materials that impede problem solution. You don’t need to remember how operators specific to the language work, and all operators appeal to one’s intuition.
Equally important is that the semantics of the language must be very simple. Apart from implementing operators, SequenceL possesses only two simple computational laws (the Consume-Simplify-Produce and the Normalize-Transpose). All features of the language are producible from these semantics. Not only does this simplify the development of assurances concerning the synthesis of codes, there are no operators that require special definitions (like the maps and zips of Haskell). This all leads to a major requirement for trusted software development – that problem solutions are transparent – that a problem solution can be seen, at a glance, to do what you want. We claim that compactness, transparency, and verifiability are key to Hoare’s vision of simplicity. In this paper we will focus on transparency and the underlying computational laws of SequenceL.
Bio
Daniel E. Cooke, Ph.D.
Daniel Cooke obtained his Ph.D. in Computer Science in 1986 from the University of Texas at Arlington. Since 1986 he has worked in the Advanced Technology Department of General Dynamics; as an Assistant Professor at Texas Christian University; and as an Assistant, Associate, and Full Professor/Chair at the University of Texas at El Paso. Since 1999, Dr. Cooke has served as Professor and Chair of the Computer Science Department at Texas Tech University and, since 2001, also as the Director of the Center for Advanced Intelligent Systems. In 2000 Cooke was borrowed from Texas Tech University to serve as the founding Manager of NASA’s Intelligent Systems Program. He established the technical content of the program, authored the initial solicitation, funded the initial 90 research projects, navigated the program from formulation to implementation, and established the program office at NASA Ames Research Center in Mountain View, California where he was a member of the Center Director’s executive staff. In 2001, Cooke received the NASA Ames Research Center Information Sciences Award for leadership in establishing a Model Strategic Research Initiative for NASA. In 2002, he received the NASA Exceptional Achievement Medal and the NASA Group Award, for Contributions to the CICT program.
Dr. Cooke has published more than 80 technical papers in the areas of computer language design and software engineering. He has served as PI or Co-PI on research grants totaling more than $12 million, edited many journal special issues, published a book on Computer Language Design, edited a book on Computer Aided Software Engineering, and served as chair or vice-chair for 15 international conferences or workshops. He currently serves as the Software Engineering Area Editor for IEEE Computer and the Formal Methods Area Editor of the International Journal of Software Engineering and Knowledge Engineering.
Dr. Cooke has been an American Electronics Association Fellow, a MacIntosh-Murchison Faculty Fellow, and held the MacIntosh-Murchison Chair in Engineering at U.T. El Paso. In 1996 he was the recipient of the University of Texas at El Paso's Distinguished Achievement in Research Award.
