Lambda the Ultimate

The latest version of PLT Scheme, version 4.0, has just been released. It's got tons of new goodies, so I recommend that anyone interested in Scheme and/or functional programming check it out here.

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.

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]

I am reading Hutton's book, programming in Haskell, and got stumped by a question. redefine map f using foldr. Since foldr is described as replacing (:) in a list with some provided operator it seemed it shouldn't be too hard.
foldr requires two components a what to do on empty list and the operator.

So I tried this:

> folmap :: (a -> b) -> [a] -> [b]
> folmap f = foldr (:.f) []

My reasoning is that you apply the : operator after f on every value in the list. (Though I may not understand the (.) I was thinking that if f = (a ->b) and g = (b -> c) then g.f would be g performed after f (or g.f is f followed by g).

Any advice??

The blue calculus has been mentioned here before, but I'm having trouble figuring out what kind of category arises from it. Terms in Blue are objects and reduction rules are morphisms.

This is kind of odd, since the typical view of the lambda calculus has types as objects and reduction-rule-equivalence-classes of terms as morphisms. Since the blue calculus isn't confluent, that approach doesn't really work.

Given a category T of types and type-preserving maps, you can type the blue calculus with a functor F:Blue->T; this functor is defined recursively using type inference rules. The original paper only considered the case where T is a discrete category.

This paper on how pi calculus is a cartesian closed double category might be relevant, but I haven't been able to understand it yet. It's not even clear to me what the objects, horizontal and vertical morphisms are.

Can anyone help?

As a fairly ubiquitous platform with access to a staggering array of libraries the Java Virtual Machine is a popular choice for language runtime. But the JVM can be one of the hardest VMs to target since it is so tied to Java's semantics *cough*tail calls*cough*.

The Da Vinci Machine Multi Language VM project is attempting to address these challenges by extending the JVM to support language constructs not found in Java. As part of this effort they're having a summit:

The 2008 JVM Language Summit is an open technical collaboration among language designers, compiler writers, tool builders, runtime engineers, and VM architects.

We will share our experiences as creators of programming languages for the JVM, and of the JVM itself.

The invitation closes with

Space is limited. Bring your own language!

PS: Also worth mentioning is that if you are targeting the JVM or thinking of targeting the JVM there's a Google group just for you.

Mark your calendars for Friday, July 11, 2008 to Monday, July 14,
2008: the dates for the eleventh annual ICFP Programming Contest.

The ICFP Programming Contest is one of the most advanced and
prestigious programming contests, as well as being a chance to show
off your programming skills, your favorite languages and tools, and
your ability to work as a team. The contest is affiliated with the
International Conference on Functional Programming. Teams consisting
of one or more participants, from any part of the world, using any
programming language, may enter.

The specific task will be announced when the contest begins. In the
meantime, watch the Web site for more information:

http://icfpcontest.org/

Please direct any questions to Tim Sheard at sheard@cs.pdx.edu.

-Tim Chevalier, on behalf of the 2008 contest organizers
(programming language devotees at Portland State University and
the University of Chicago)

Many Programming Languages Can Be Extended Upon Somewhat Easily. Such As Python, Or Lua. As Well As Language Bridges Between Languages, Python And Lua Can Be Bridged Together With Lunatic-Python, Which Allows You To Invoke The Python Interpreter From Within Lua And The Lua Interpreter Inside Of Python. Anyway I Was Wondering If Anybody Here Is Familiar With The Superset Of C, Cilk.It Is Intended For Massive Parallelism In C Programs.I Was Wondering If Somebody Could Help Me Develop Wrappers For:

• Swig
,
• Flex
,
• Bison
,
• Cilk
,
• ImageMagick
,
• Nyquist
• FFLL
,
• Tesseract OCR
, And
• Evolving Objects

For A Nice Little Collection Of Systems For Use In A New Programming Languages Or Extensions To Existing Ones, Extreme Programming I Will Call This Brainiac And Have Already Been Working On This For A While, However I Am A Beginner And Not Yet Have Enough Code For A Release, Other Than For A Collection Of Utilities.

I was reading up on Scala and noticed that classes and value bindings have different namespaces. This got me thinking about how different languages treat classes. As an extreme case, consider Smalltalk vs. C++.

I Googled for papers like crazy, but turned up nothing. There's just too much cruft involving keywords like "first class classes" and like queries.

Are there any good comparative studies/overviews of the treatment of classes in different object oriented languages and the implications/trade offs/etc. of these different treatments?

Any manifestos promoting one or another treatment would be great as well.

Thanks much!

Scott

Hi, was wondering if someone could explain more in detail about "combinatory logic" in a simplistic way. I am not a programmer, I do 3-D animation and I fell into Lambda Calculi while reading I believe an article about a video games that mentioned something about functional progaming. Anyway I started getting an interested in Lambda Calculi and I found a lot of articles about it online. It took me a while to understand it but when I did, the concept around it seemed rather easy. Now I'm trying to learn how combinatory logic works, but there isn't as much material on it as there is with Lambda Calculi. Usually it is lumped into a Lambda Calculi article without much dedication to it. Or I find it talked about in a programing languages such as "unlambda" but as I am not a programming, so I get confused. I started to "get" Lambda Calculi, when I started learning how Church numbers work, and saw examples of how to do simple arthritic like adding and multiplying. So far I can't find anything like this with combinatory logic, can someone show examples of how to make numbers with combinatory logic and to do something like add or multiply with it? This would be a great help.