Tag Archives: functional programming

Computer Science as a scholarly discipline.

Google Scholar tells me that “Why Functional Programming Matters” was published in 1989 and has been cited over 1000 times. Here’s a quote.

 Recall that a complete functional program is just a function from its input to its output. If f and g are such programs, then (g. f ) is a program that, when applied to its input, computes

g(f input)

The program f computes its output, which is used as the input to program g. This might be implemented conventionally by storing the output from f in a temporary file. The problem with this is that the temporary file might occupy so much memory that it is impractical to glue the programs together in this way. Functional languages provide a solution to this problem. The two programs f and g are run together in strict synchronization. Program f is started only when g tries to read some input, and runs only for long enough to deliver the output g is trying to read. Then f is suspended and g is run until it tries to read another input. As an added bonus, if g terminates without reading all of f ’s output, then f is aborted. Program f can even be a nonterminating program, producing an infinite amount of output, since it will be terminated forcibly as soon as g is finished. This allows termination conditions to be separated from loop bodies — a powerful modularization. Since this method of evaluation runs f as little as possible, it is called “lazy evaluation”. It makes it practical to modularize a program as a generator that constructs a large number of possible answers, and a selector that chooses the appropriate one.

From Dennis Ritchie’s 1972  UNIX paper:

An extension of the standard I/O notion is used to direct output from one command to the input of another. A sequence of commands separated by vertical bars causes the Shell to execute all the commands simultaneously and to arrange that the standard output of each command be delivered to the standard input of the next command in the sequence. Thus in the command line

ls | pr –2 | opr

ls lists the names of the files in the current directory; its output is passed to pr, which paginates its input with dated headings. The argument “–2” means double column. Likewise the output from pr is input to opr. This command spools its input onto a file for off-line printing

Back to “Why functional programming matters”

We have described lazy evaluation in the context of functional languages, but surely so useful a feature should be added to nonfunctional languages — or should it? Can lazy evaluation and side-effects coexist? Unfortunately, they cannot: Adding lazy evaluation to an imperative notation is not actually impossible, but the combination would make the programmer’s life harder, rather than easier. Because lazy evaluation’s power depends on the programmer giving up any direct control over the order in which the parts of a program are executed, it would make programming with side effects rather difficult, because predicting in what order —or even whether— they might take place would require knowing a lot about the context in which they are embedded. Such global interdependence would defeat the very modularity that —in functional languages— lazy evaluation is designed to enhance.




Current reading

Wadler’s influential “monads” paper for Haskell. It seems like a classic case of making something simple sound profound and mysterious.  And companion paper by Hughes on “why functional programming matters” . See also some comments above.

McCarthy’s original LISP paper.  Just terrible. He made a serious error picking Lambda calculus as a base notation.

A problem FSMLabs detected with GPS on London LD4 datacenter has been fixed. 

Dennis Ritchie and Albert Meyer on classification of recursive functions. I wish I could find a full copy of this.

The SEC Consolidated Audit is pushing clock sync requirements, but needs improvement.

The most successful functional language – Mathematica.

A critique of Haskell

A Haskell project at Facebook.

Some real engineering: the gcc optimizers.

Categories as algebra: An essential ingredient in the theory of monoids (via @joelvanderwerf )

Flash file system.