Lambda the Ultimate

Abstract: In object-oriented languages, it is easy to extend data by defining new classes, but it is difficult to add new functions. In functional languages, the situation is reversed: adding new functions poses no problems, but extending data (adding new data constructors) requires modifying existing code. The problem of supporting both directions of extensibility is known as the expression problem. We present open data types and open functions as a lightweight solution to the expression problem in the Haskell language. The idea is that constructors of open data types, and equations of open functions can appear scattered throughout a program. In particular, they may reside in different modules. The intended semantics is as follows: the program should behave as if the data types and functions were closed, defined in one place. The order of function equations is determined by best-fit pattern matching, where a specific pattern takes precedence over an unspecific one. We show that our solution is applicable to the expression problem, generic programming, and exceptions. We sketch two implementations. A simple one, derived from the semantics, and one based on mutually recursive modules that permits separate compilation.

We all love the Language vs. IDE flame-fests. But I'd like to be a little more constructive and try to see what kind of tools people actually use. The concrete question I'd like you to answer is:

What editor or IDE are you using when programming?

Please also say a few words about why you use your particular editor and any particular functionality that you like and which help you in your everyday programming.

The answer will of course be influenced by what language you are using. And that's totally fine.

In a similar vein to John Carter's recent submission, here's an attempt to attack the complexity problem: Out of the tar pit

Abstract: Complexity is the single major difficulty in the successful development of large-scale software systems. Following Brooks we distinguish accidental from essential difficuly but disagree with his premise that most complexity remaining in contemporary systems is essential. We identify common causes of complexity and discuss general approaches which can be taken to eliminate them where they are accidental in nature. To make things more concrete we then give an outline for a potential complexity-minimizing approach based on functional programming and Codd’s relational model of data.

They basically advocate minimising mutable state, moving any mutable state that remains into relations, and specifying the behaviour (i.e. manipulation of relational data) in a declarative/logical/purely-functional language.

Pros: the first half of the paper is a reasonable review of the types and causes of complexity in software.

Cons: lack of any implementation, other than a Scheme prototype of the relational bits, I think (see footnote 25). No source code. Lack of detail about interfacing with external systems.

Here's a link to Ben Moseley's FRP page, where you can find the paper, plus presentation slides and a discussion group.

This must be well-know amongst functional programming researchers, but I kind of stumbled upon it by accident when studying Joy.

Consider the following program to count even numbers:

define count_evens = [2 mod 0 neq] filter 0 [inc] reduce

So for those new to Joy, every program/function takes it parameter on the stack, and pushes its results onto the stack.

Here is a brief explanation of the operators:

2 = push the value two onto the stack
[] = push the contents onto the stack without evaluating them
mod = modulo
inc = increment the top item of the stack
neq = not equals

The program I showed takes a list on the stack, filters the list for only even numbers, and then counts them using a reduce function.

Assuming you are following me so far, this program can be rewritten as follows (caveat: I'm doing this off the top of my head so I could have made a mistake in syntax):

  def count_evens_1 = 0 [2 mod 0 eq [inc] [] if] reduce

What I've done here is eliminate the unneccessary filter operation and "folded" it (pun intended) into the reduce operation.

My observation when working with Joy is that this optimization is trivial to automate.

So my question to the group is: is this a well known optimization, and if so, is it as easily applied in other functional languages?

For those whose curiosity has been piqued, I'm researching the viability of using a Joy dialect as an intermediate language.

A lot of embedded systems programmers use C and C++ to develop very large and complex pieces of software. Often these people are never introduced to higher-level constructs or improvements to languages to make that software more reliable. I recently wrote an article that attempts to introduce some ideas from different languages to show their benefits. The article is available as:

Patterns of Integer Usage

The article was written for those who rarely look past C/C++/C# as implementation languages (certainly not this crowd). However, I would appreciate any criticisms or critiques this community may offer.

After years of effort, Graham Nelson has released version 7 of the Inform language. Inform is the language created by Infocom for the construction of interactive fiction games, such as the legendary Zork series. This latest edition of the language is notable in that it is based on a subset of English, and reads like natural-language descriptions. For example:

The LNER Mallard is a steam locomotive. The Mallard is 4-6-2.
A steam locomotive can be watered or unwatered. A locomotive is usually watered.
A man called Peter is in the Atrium. North of the Atrium is the Hall of Greek Vases.
Brightness is a kind of value. The brightnesses are guttering, weak, radiant and blazing.

These declarations create not only the terms used, but the relations between the terms. Conditions can later be tested using the domain-specific terms thus created (if the cat is on the mat...).

Recently many javascript libraries have started molding javascript to become more functional: Prototype provides map/filter functions for javascript arrays. jquery is providing 'chained' methods where every method of an object returns the updated object.

Phill Wadler is bringing us Links, a whole programming language for the web.

Automatic Generation of Intelligent JavaScript Programs for Handling Input Forms in HTML Documents by Tetsuya Suzuki and Takehiro Tokuda is an interesting paper about using constraint solving for web forms.

Is there any other such work being done to imporve actual web applications built every day. Are there other ideas which could help developers and users?

The Edge "World Question Center asks the thought provoking, but overly general for this forum, question "WHAT DO YOU BELIEVE IS TRUE EVEN THOUGH YOU CANNOT PROVE IT?"

So let's tailor it a little for LtU...

What do you believe about Programming Languages (that you can't prove (yet))?

Can anyone tell me which functional languages support a non-order-specific fold, and what the name of those operations are? I read somewhere that sometimes reduce is non-order specific, but other places claims it is the same as foldl. Clearly it depends on the languages, but I don't trust those source, so I thought I'd ask my favourite group of egg-heads. :-)

It seems that specifying left or right folds when the function being used is associative is over-specifying the solution to a problem. In other words you are solving a more specific problem than stated. Commonplace in imperative code, but it should be more easily avoided in functional code. Perhaps this is moot because it might be an "easy" problem for compilers to figure out if a "clean" function (e.g. pure functional) is associative and/or commutative based on the primitives.

I am studying the problem of optimizing / parallelizing pure functional code. So any good pointers to basic primers on the internet would be much appreciated. I am particularly interested in those common-knowledge optimizations of functional code. I don't have time to purchase any books, so online references would be most appreciated. It would be cool to gather a compendium of functional optimization tips and tricks on this thread, but that might be hoping for too much.

Thanks in advance.

E.g. in Common Lisp you can do:

(defun flatten (list)
  (cond
    ((null list) list)
    ((atom list) (list list))
    (t (append (flatten (first list))
               (flatten (rest list))))))
(trace flatten)
(flatten '(a (b c) d))

0 FLATTEN > ...
  >> LIST : (A (B C) D)
  1 FLATTEN > ...
    >> LIST : A
  1 FLATTEN < ...
    << VALUE-0 : (A)
  1 FLATTEN > ...
    >> LIST : ((B C) D)
    2 FLATTEN > ...
      >> LIST : (B C)
      3 FLATTEN > ...
        >> LIST : B
      3 FLATTEN < ...
        << VALUE-0 : (B)
      3 FLATTEN > ...
        >> LIST : (C)
        4 FLATTEN > ...
          >> LIST : C
        4 FLATTEN < ...
          << VALUE-0 : (C)
        4 FLATTEN > ...
          >> LIST : NIL
        4 FLATTEN < ...
          << VALUE-0 : NIL
      3 FLATTEN < ...
        << VALUE-0 : (C)
    2 FLATTEN < ...
      << VALUE-0 : (B C)
    2 FLATTEN > ...
      >> LIST : (D)
      3 FLATTEN > ...
        >> LIST : D
      3 FLATTEN < ...
        << VALUE-0 : (D)
      3 FLATTEN > ...
        >> LIST : NIL
      3 FLATTEN < ...
        << VALUE-0 : NIL
    2 FLATTEN < ...
      << VALUE-0 : (D)
  1 FLATTEN < ...
    << VALUE-0 : (B C D)
0 FLATTEN < ...
  << VALUE-0 : (A B C D)
(A B C D)

(FLATTEN (A (B C) D) (A B C D)
  (FLATTEN A (A))
  (FLATTEN ((B C) D) (B C D)
    (FLATTEN (B C) (B C)
      (FLATTEN B (B))
      (FLATTEN (C) (C)
        (FLATTEN C (C))  ; X
        (FLATTEN NIL NIL)))
    (FLATTEN (D) (D)
      (FLATTEN D (D))
      (FLATTEN NIL NIL))))

(FLATTEN (A (B C) D)
  (FLATTEN ((B C) D)
    (FLATTEN (B C)
      (FLATTEN (C)
        (FLATTEN C)))))  ; X