Weblogs Forum - Language Purity and Dirty and Clean Functions

Articles |
News |
Weblogs |
Books |
Forums

Artima Forums | Articles | Weblogs | Java Answers | News

Sponsored Link •

Weblogs Forum
Language Purity and Dirty and Clean Functions

46 replies on 4 pages. Most recent reply: Jul 11, 2006 5:10 AM by Emil Cristian Alexandrescu

Welcome Guest
Sign In

Back to Topic List

Reply to this Topic

Search Forum

Threaded View


Previous Topic		Next Topic

Flat View: This topic has 46 replies on 4 pages [ 1 2 3 4 | » ]

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Language Purity and Dirty and Clean Functions (View in Weblogs)

Posted: Jun 26, 2006 8:10 AM

Summary
The myth of functional language "purity" and marking side-effects in a programming language.

Many people talk about "pure" functional languages, where "pure" seems to be a synonym for "good". There are two traits commonly associated with the definition of a pure functional language:

functions can not have side-effects
a function called with any given arguments will always return the same value.

The programming Haskell for example is often referred to as a pure language because a function call with side-effects must be done only in the context of a monad. I believe that this is simply semantic hand-waving.

The need of monads illustrates the simple fact that in order to have substantitve practical applications, a programming language must allow a program to interact with the environment during its execution (e.g. file-system, devices, clock, etc.). This implies that any non-trivial programming language must allow side-effects.

All of that said, it is much easier to reason about and manipulate (read: optimize) programs and sub-programs which don't have side-effects.

So the purity of a language is an impractical notion from a software development standpoint, however the idea of understanding and localizing side-effects (e.g. using monads) is nonetheless a very important and useful idea.

Where am I going with this? Well I believe that language designers can take a lesson from Haskell by isolating and labelling side-effects. Taking a far more simplistic approach than using monads, the approach I am exploring using later versions of Cat, is to label functions as "clean" and "dirty" depending on whether they have side-effects or not. This makes optimization much easier.

Any thoughts on the subject?

Kay Schluehr

Posts: 302
Nickname: schluehk
Registered: Jan, 2005

Re: Language Purity and Dirty and Clean Functions

Posted: Jun 26, 2006 8:24 AM

A pro pos Dirty and Clean:

http://www.cs.ru.nl/~clean/

Jules Jacobs

Posts: 119
Nickname: jules2
Registered: Mar, 2006

Re: Language Purity and Dirty and Clean Functions

Posted: Jun 26, 2006 9:27 AM

I think you can let the compiler decide whether a function is clear or dirty for most procedures. The simple recursive definition: a procedure is clean if it calls only clean procedures. You define the cleanness of primitives to provide a base case.

There is a problem with stack based languages: what does "clean" mean? Does it mean that a procedure will always return stack B if given stack C as input?

sqr = dup *

This procedure is "clean", because it's an homomorphism (that's what it's called, right?) between an input stack and an output stack:

4 3 2 sqr => 4 3 4

Always.

But readfile, for example isn't clean.

The problem is that "clean" doesn't mean much:

Foolang:

function sqr()
{
  $result = $input * $input
}

$input = 4
sqr();
// $result = 16

This function is as clean as sqr = dup *. It reads and changes globals, but it is clean, because given that the variables are the same, this function will result in the same new values, always.

So Cat's sqr: stack-a => stack-b
Foolang's sqr: environment-a => environment-b

I think you need a special definition of "clean" for Cat.

Michael Feathers

Posts: 448
Nickname: mfeathers
Registered: Jul, 2003

Re: Language Purity and Dirty and Clean Functions

Posted: Jun 26, 2006 1:27 PM

I like Betrand Meyer's Command/Query Separation Principle.

Short form: If it returns a value assume it's clean. If it's not, introduce the code author to the 'Command/Query Separation Principle.'

Don't know how this applies to stack-based languages either.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Language Purity and Dirty and Clean Functions

Posted: Jun 26, 2006 9:30 PM

I agree with what you are saying. My own solution is to provide Value types that can change their value but have value semantics (equals, hashCode, toString based on the value of fields and not the object's address):

http://pec.dev.java.net/nonav/compile/javadoc/pec/compile/value/package-summary.html

Companion Immutable types (your pure types):

http://pec.dev.java.net/nonav/compile/javadoc/pec/compile/immutable/package-summary.html

and a standardized way of converting between the two:

http://pec.dev.java.net/nonav/compile/javadoc/pec/compile/immutable/ImmutableValueConversions.html

This nicely compartmentalizes the Immutable and Value types and provides a method of converting by copying to prevent aliasing of the Immutable. The above reference for Immutable (the middle URL above) discussed the design of these types further.

Cleo Saulnier

Posts: 77
Nickname: vorlath
Registered: Dec, 2005

Re: Language Purity and Dirty and Clean Functions

Posted: Jun 26, 2006 10:56 PM

Christopher: I wish you posted more and I wish there were more places I could find people talking about actively implementing languages. You're the only one I see talk about these things.

AK aside... every time I read "pure" language, I keep thinking about RNG's. And I keep thinking that if you replaced static (persistant across calls) data as a parameter INSTEAD (and no static data), would this not be equivalent? The problem being that after a while, you'd have a whole lot of parameters being passed. Or would we?

I'm not one to defend OO and I originally thought that OO wasn't pure (outside I/O). And I may be off my rocker (many have told me as much)... and I've just thought of this now... but couldn't the instance (object) be considered as an implied parameter (which it is) and ALSO a return value of a method? And if so, then aren't globals the same? Apart from I/O, where is the boundary on "pure"? Or is the fact that objects and globals aren't specified in the parameters and return values the point? Is "pure" purely a human readability thing? Can I not look at globals as parameters passed to all my functions and likewise for objects to all its methods? I think this has been discussed already tho.

So where do you define "clean" and "dirty" other than I/O? Or is defining I/O functions as "dirty" enough?

I think a more practical approach is defining what level of coupling a function has. Is it completely pure and doesn't modify anything outside the function and no static variables? Is it object level pure where it doesn't modify anything except its own instance (not parameters or anything)? Then you have to ask if the parameters are mutable or not in both cases. Then you have functions that access globals.

Doesn't C++ work this way by stating 'const' on parameters and methods themselves and applying the mutable keyword on certain members? How many people use it? Maybe that's the better question.

Cheers!

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Language Purity and Dirty and Clean Functions

Posted: Jun 26, 2006 11:43 PM

As a follow up to my original post I should explain something that I omitted - IE my previous post was poorly written :(

For a pure method you need Immutable objects else you cannot guarantee that the function won't store state in one of its arguments. So using my Imutable design: a pure method resides in an immutable object (so its reciever, hidden this, argument is Immutable), accepts only Immutable arguments, and only calls other pure methods.

IE it not sufficient to say that a pure method only calls other pure methods, you also need to say that all of its arguments are Immutable, and that it is in an Immutable class.

Jules Jacobs

Posts: 119
Nickname: jules2
Registered: Mar, 2006

Re: Language Purity and Dirty and Clean Functions

Posted: Jun 27, 2006 2:00 AM

I think we're talking about a language where everything is a procedure. So assignment is a procedure too. In this language, a procedure *is* clean if it only calls other clean procedures. What I'm saying is that in a language where all functions are from one stack to another, clean doesn't have the same meaning as in Haskell, for example.

Dave Hinton

Posts: 42
Nickname: catbells
Registered: Oct, 2003

Re: Language Purity and Dirty and Clean Functions

Posted: Jun 27, 2006 4:56 AM

You want functions marked as clean or dirty? Excellent. Is map clean or dirty?

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: Language Purity and Dirty and Clean Functions

Posted: Jun 27, 2006 6:17 AM

> Many people talk about "pure" functional languages, where
> "pure" seems to be a synonym for "good".

What's the foundation for this stance? I assume there must be some sort of theory or argument behind it.

Achilleas Margaritis

Posts: 674
Nickname: achilleas
Registered: Feb, 2005

Re: Language Purity and Dirty and Clean Functions

Posted: Jun 27, 2006 6:36 AM

I apologise for playing the devil's advocate, but in my opinion there are certain things that need to be said about FP.

The so called 'cleaness' of a language from side effects does not offer any practical benefits in real coding environments. Everybody is saying how pure functional programming is so much better, but I disagree, and I have a lot of reasons to:

1) the so-called "side effects" are there nevertheless, even if one codes in a pure functional language. While in imperative languages an erroneous side effect is immediately visible at its creation point, in FP the side effect is activated in a much different context and therefore it is a much harder error to find.

For example, let's say the following imperative code is an error:


object1 = data.get("foo");
list1.add(object1);

It is an error because 'object1' is not the proper object to add to the list.

Let's reproduce the effect in some pseudo-FP:


local
    let object1 = map data findObject
in
    object1 :: list1
end

In this purely functional example, 'object1' is added in a list. There is no side effect error, but the program enters an invalid state.

In FP, this sort of error is very hard to detect by a programmer, because the effect of using 'object1' may come much later, usually at a top-level loop which is a monad that manipulates state.

2) it is a myth that 'order of operations' does not matter in pure functional languages. In order to validate an algorithm in ones mind, even if there is no assignment in it, the correct order of operations must be respected. The cause always comes before the effect, and one has to take that into account.

3) The phrase "pure FP programs are easier to reason about" is a catch-all phrase that I have heard many times...but what does it mean? are programs easier to reason from the perspective of the programmer or the compiler? and does the ease come from the type system or from the purity? I do not believe pure FP programs are easier to reason about. Take Haskell, for example, and remove its purity, i.e. allow assignment...then apply SSA to the compiler and the result is the same.

4) "Pure programs are easier to optimize". Yet no purely written program can reach the overall performance of C/C++. Isn't C/C++ supposed to be more difficult to optimize?

I think the importance of pure functional programming languages is overestimated. They are good from an academic point of view, or for bridging together already written components, but not for anything else. And before someone posts a list of 'successful real world projects written with Haskell', I would like to explain myself: there are programs which are mainly computations and transformations, like compilers, CVS systems, etc, and there are programs which are event-driven state machines with a lot of state in it. Pure FP programmers have a very great difficulty for doing the latter style of programs...it's not entirely undoable, but one has to twist his/her brain around the concepts. Since programming is more about commodity and less about science, pure FPs will never catch on.

Ultimately, the constraint for proving a program as correct is nature itself: no language can solve the halting problem (even if the language is a purely FP one), and therefore correctness of a program is always subject to the programmer's ability to run the program in his/her head.

And something else I would like to add about functional programming: the one and only characteristic that makes functional programming different from imperative programming is the "side effects not allowed" principle. Take that way, and all other features of functional programming languages can happily exist within an imperative language. Therefore languages should not be divided into 'functional' and 'imperative', but rather to 'pure' and 'dirty', i.e. the ones that allow side effects and the ones that do not allow side effects.

Programmers need other kinds of facilities in order to speed up development and increase correctness. Instead of twisting our brains around monads, we need imperative languages that allow better abstractions to exist and less things to type...

Joe Cheng

Posts: 65
Nickname: jcheng
Registered: Oct, 2002

Re: Language Purity and Dirty and Clean Functions

Posted: Jun 27, 2006 10:37 AM

> 3) The phrase "pure FP programs are easier to reason
> about" is a catch-all phrase that I have heard many
> times...but what does it mean? are programs easier to
> reason from the perspective of the programmer or the
> compiler? and does the ease come from the type system or
> from the purity? I do not believe pure FP programs are
> easier to reason about. Take Haskell, for example, and
> remove its purity, i.e. allow assignment...then apply SSA
> to the compiler and the result is the same.

I think they are easier for math majors to reason about ;)

> 4) "Pure programs are easier to optimize". Yet no purely
> written program can reach the overall performance of
> C/C++. Isn't C/C++ supposed to be more difficult to
> optimize?

What if the pure program gets automatic memoization at runtime, for example? The naive fibonacci algorithm would run in O(1) with automatic memoization. While C/C++ is relatively good at translating source code into efficient machine code, doesn't pure FP allow classes of automatic program-wide transformations/optimizations that aren't possible with C/C++?

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: Language Purity and Dirty and Clean Functions

Posted: Jun 27, 2006 10:47 AM

> 4) "Pure programs are easier to optimize". Yet no purely
> written program can reach the overall performance of
> C/C++. Isn't C/C++ supposed to be more difficult to
> optimize?

Assuming that your assertion is true it's not an argument for saying that FP is not easier to optimize. AFAICT, you cannot solve certain problems efficiently with FP at the language level. The inefficient solution can be highly optimized and still be less efficient than the C/C++ solution.

It's kind of like buying something at an overpriced store because you have a coupon. You save 15% on something that costs 100% more than it does at another store.

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: Language Purity and Dirty and Clean Functions

Posted: Jun 27, 2006 10:56 AM

> What if the pure program gets automatic memoization at
> runtime, for example? The naive fibonacci algorithm would
> run in O(1) with automatic memoization.

You mean O(n), or are you saying that the memoization would be presisted forever?

Isaac Gouy

Posts: 527
Nickname: igouy
Registered: Jul, 2003

Re: Language Purity and Dirty and Clean Functions

Posted: Jun 27, 2006 11:34 AM

Christopher Diggins wrote Taking a far more simplistic approach than using monads, the approach I am exploring using later versions of Cat, is to label functions as "clean" and "dirty" depending on whether they have side-effects or not. This makes optimization much easier.

Kay Schluehr wasn't just making a pun.

In some sense the Clean programming languages allows function parameters to be labelled clean or dirty - more correctly it allows function parameter types to be labelled unique.

"Assume that we are able to guarantee that the reference count of the file argument of fwritec is always exactly one. We say that such an argument is unique. Now, when we apply fwritec to such a unique file we can observe the following. Semantically we should produce a new file. But we know that no other expression can refer to the old file: only fwritec has a reference to it. So, why not reuse the old file passed as argument to fwritec to construct the new file? In other words: when old file is unique it can simply be updated destructively by fwritec to produce the new file in the intended efficient and safe way."

Section 4.3 Uniqueness types, "Functional Programming in Clean" http://www.cs.ru.nl/~clean/contents/Clean_Book/clean_book.html

And the old '92 - '94 papers http://www.cs.ru.nl/st/Onderzoek/Publicaties/publicaties.html

Flat View: This topic has 46 replies on 4 pages [ 1 2 3 4 | » ]

Previous Topic

Next Topic