Lambda the Ultimate

In the form above, the side-effects are nicely contained, but presumably there's a closure with a mutable value in it somewhere behind the scenes? Is there a "pure" way to accomplish the same separation?

Another "impure" aspect of Lisp is modifying data structures in place, e.g. the list operations SORT and NCONC can trash their inputs while producing their output. I don't like these functions and their common usage one bit. They introduce non-local issues: "am I allowed to modify my arguments?" and "what if someone modifies the value I return?" I think this makes Lisp a low-level language by Alan Perlis's definition.

My thought for the day is that the nice thing about "purity" is keeping things locally understandable, and that anything else that does this is interesting too.

I'd guess that some clever guy could do the same thing with Monads

I worked it out top down, starting with what I wanted to see at the top level, using a fold (not essential, any old loop would do), with the accumulating parameter being a monad-like value m, i.e. a procedure which accumulates the desired state:

(require (lib "1.ss" "srfi")) ; for fold (PLT Scheme)

; data structure for result type: ((even ...)(odd ...))
(define (make-evens+odds evens odds) (list evens odds))
(define get-evens car)
(define get-odds cadr)

(define (even-and-odds numbers)
  ((fold (lambda (n m)
           (bind
            m
            (if (even? n)
                (evens n)
                (odds n))))
         (lambda (x) x)
         numbers)
   (make-evens+odds '() '())))

(define (evens val)
  (lambda (evens+odds)
    (make-evens+odds (cons val (get-evens evens+odds)) (get-odds evens+odds))))

(define (odds val)
  (lambda (evens+odds)
    (make-evens+odds (get-evens evens+odds) (cons val (get-odds evens+odds)))))

(define (bind m f)
  (lambda (x)
    (m (f x))))

That's it - now it can be tested:

(even-and-odds '(7 2 3 8 9 10 12 14 13 17 6 5))
  =>
((2 8 10 12 14 6) (7 3 9 13 17 5))

Of course I would really write this function as:

(defun evens-and-odds (numbers)
  (values (remove-if-not #'evenp numbers)
          (remove-if-not #'oddp numbers)))

(define (evens-and-odds numbers)
  (partition even? numbers))

P.S. I agree with this:

My thought for the day is that the nice thing about "purity" is keeping things locally understandable, and that anything else that does this is interesting too.

Side effects that don't affect the ability to reason about the program outside of the place where they're used are fine.

Side effects that don't affect the ability to reason about the program outside of the place where they're used are fine.

I wonder whether the difference between "harmful" and "harmless" side-effects could be said to correspond to the difference in Haskell between one-way and two-way monads (that is, monads you can "escape" from). The work done in a two-way monad could presumably be done by impure methods without contaminating the rest of the program, whereas the work done in a one-way monad could not be done by impure methods without "destroying the functional properties of the non-monadic portions of the program" (Jeff Newbern, All about Monads).

Actually I'm not convinced that's always true - surely you could scatter printfs liberally around a "pure" program without destroying referential transparency (unless you consider the state of the console to be part of the return value)?

Actually I'm not convinced that's always true - surely you could scatter printfs liberally around a "pure" program without destroying referential transparency (unless you consider the state of the console to be part of the return value)?

Think about common-subexpression elimination -- if you have code like:

let val x = printf "foo"
    val y = printf "foo"
    val z = printf "foo"
in
  (x, y, z)
end

And the compiler, thinking that CSE is legal, "optimizes" it to:

let val x = printf "foo" 
    val y = x
    val z = x
in
  (x,y,z)
end

then the meaning of your program changes, all because the compiler assumed purity when it wasn't so. So just scattering printfs around a pure program won't necessarily give the results you expect -- you might not even be getting the output you thought you were, which is a problem for debugging. :)

I admit I hadn't thought of that (being generally ignorant of compiler techniques, I didn't know it was there to be thought of). The case I was thinking of, though, was one in which a "pure" function obtains a value from an "impure" function, where the impurity of the impure function doesn't affect the purity of the pure function.

In the case of two-way monads, the fact that you can recover the value from the monad implies that there isn't any left-over threaded state for the caller to worry about - in other words, the side-effects simulated by (or threaded through) the monad are local (and hence would not be contaminating even if they were real).

In the case of one-way monads, the fact that you can't recover the value from the monad implies that there may be non-local side-effects - so the caller is obliged to "take up the thread", so to speak.

If you want to write output to the console in Haskell you have to enter the IO monad, which is a one-way monad. The question is whether output written to the console is really a side-effect from the point of view of the rest of the program, or whether it can be thought of as an "out of band" side-effect (for the sake of argument, let STDOUT be piped to /dev/null: whatever goes in there no longer matters).

It should be possible to indicate to a compiler that a section of code contains side-effects, so that CSE is not legal there, but that the side-effects are localized so that other code that calls it remains pure and can legally be optimized in this way.

It should be possible to indicate to a compiler that a section of code contains side-effects, so that CSE is not legal there, but that the side-effects are localized so that other code that calls it remains pure and can legally be optimized in this way.

Two things:

1. Side-effects always introduce ordering but a "pure" language may evaluate expression in any order (specially the lazy ones).

2. How can we distinguish "harmless" and "harmful" side-effects? Someone could pipe stdout to a shell-like process which and writing "print_line ('rm ' ++ file_name)" wouldn't be so "harmless".

-----
Hidden side-effects are evil, support separation of Church and state ;-)

We can manage local side-effects with imperative code simulation (e.g. state monads) or with help of the type-system (e.g. unique types).

There are lots of interesting research related to this in the areas of "type and effect systems", "region inference" and "effect masking". Some papers aren't about local side-effects but they describe techniques that (IIUC) could be used to solve this problem.