Lambda the Ultimate

The ACM Curriculum board has re-opened the 2001 design for review. Although ACM is a US-based organization, the curriculum is not only influential at the middle tier of US colleges and universities, but it is also taken seriously by many evolving and developing educational institutions overseas. In recent years, the study of non-OO PLs, and of other key PL topics such as type systems, has grown increasingly marginal in the undergraduate CS curriculum. In particular, the study of functional programming is not included in the ACM CS2001 core. We may now have an opening to make a small change in this situation.

The ACM Curriculum board has agreed to consider a proposal on including FP as an equal to OOP (10 "hours" each) in the standard curriculum. This was the most concrete outcome of the PLC workshop at Harvard two weeks ago. The proposal was drafted by Stuart Reges, Shriram Krishnamurthi, and Matthias Felleisen and was endorsed unanimously by the workshop attendees and by the SIGPLAN Executive Committee. It proceeds on the premise that inclusion of FP in the core curriculum is the most important single thing that the PL community can do for CS education. In particular, this will help prepare students for a properly designed though possibly optional PL course or courses.

Please consider contributing comments to the web site. A simple "Yes, I think this is a great idea" will be helpful. A short explanation is even better.

There is now a long list of comments supporting this proposal. However, we have very few comments from people in industry, so comments from the many non-academics on LtU would be particularly helpful. Examples of how FP has helped you would, I think, be particularly persuasive.

The web site is http://wiki.acm.org/cs2001/index.php?title=SIGPLAN_Proposal. Unfortunately, you must be an ACM member to view or submit comments.

[Edit: This is important enough that I am promoting this item to the front page even though the link is only accessible with an ACM account. The issue itself can be debated in the comments, and hopefully at some point an open mirror of the ACM discussion will be created. -- Ehud]

In taking a graduate class in theoretical computer science, I developed a question that was never answered in a way that I felt comfortable with accepting, and now I can't stop thinking about it.

We discussed that most computer languages are Turing complete, but did not discuss why that is necessary. When I asked, I got an answer of the type: because there are problems only solvable by Turing complete languages. Yet, I feel no examples coming immediately to mind. Pushdown-automata or stacks are always decidable, and there is an enormous amount of problems that can be solved using them. Also, very many practical problems can be solved in the form of a graph. Yet, many other problems can be solved with primitive recursion which is also decidable.

So, I still feel like I am missing something; what are the practical benefits of making a language Turing complete? Or to ask another side of the question: what practical benefits would be lost by not being Turing complete?

Any help on this one, I would tremendously appreciate.