The Artima Developer Community
Sponsored Link

Weblogs Forum
Language Purity and Dirty and Clean Functions

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

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 46 replies on 4 pages [ « | 1 2 3 4 | » ]
Max Lybbert

Posts: 314
Nickname: mlybbert
Registered: Apr, 2005

Off the cuff Posted: Jun 27, 2006 4:06 PM
Reply to this message Reply
Advertisement
/* 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?
*/

I'm not really a fan of functional languages or functional programming. However, I'm a fan of quite a few other programming styles, including functional Perl ( http://www.opensourcetutorials.com/tutorials/Server-Side-Coding/Perl/functional-programming/page1.html for instance). Really, whenever I see this phrase applied to a particular pattern or programming style, I take it to mean "easier to reason about in cases X, Y, and Z."

For instance, I think it's easier to understand:

my %signal_handler = ('QUIT' => \&do_quit, 'SUSPEND' => \&do_suspend, ...);
$signal_handler{$sig_to_process};


Than just about any functionally-equivalent C or C++ code. But that doesn't mean I think Perl is easier to understand or reason about than C or C++ in every case.

/* 4) "Pure programs are easier to optimize". Yet no purely written program can reach the overall performance of C/C++.
*/

OCaml (which isn't a pure language) is rumored to be faster than C++ at least. However, I believe this statement is shorthand for "easier to optimize in cases X, Y, and Z." Most famously when it's possible to parralelize the calls ( http://www.sidhe.org/~dan/blog/archives/000438.html ).

Max Lybbert

Posts: 314
Nickname: mlybbert
Registered: Apr, 2005

Re: Off the cuff Posted: Jun 27, 2006 4:22 PM
Reply to this message Reply
I wrote "whenever I see this phrase (X programs are easier to reason about) applied to a particular pattern or programming style, I take it to mean easier to reason about in cases X, Y, and Z.'"

A better link for that would have been page 5 of my Functional Perl link ( http://www.opensourcetutorials.com/tutorials/Server-Side-Coding/Perl/functional-programming/page5.html ), which has a list of times where a functional programming style is a bad thing in Perl, and when it's a good thing.

Isaac Gouy

Posts: 527
Nickname: igouy
Registered: Jul, 2003

Re: Language Purity and Dirty and Clean Functions Posted: Jun 27, 2006 5:29 PM
Reply to this message Reply
Achilleas Margaritis wrote
> 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?

Over decades, a great deal of effort has gone into optimizing C/C++ implementations. Maybe less effort has gone into optimizing other language implementations. Even if we really demonstrated that "no purely written program can reach the overall performance of C/C++" it could still be true that "Pure programs are easier to optimize".

I wonder what that is supposed to mean - "no purely written program can reach the overall performance of C/C++"? Last time we measured, this purely written program was faster than a C program...

http://shootout.alioth.debian.org/gp4sandbox/benchmark.php?test=recursive&lang=all

Isaac Gouy

Posts: 527
Nickname: igouy
Registered: Jul, 2003

Re: Language Purity and Dirty and Clean Functions Posted: Jun 27, 2006 6:53 PM
Reply to this message Reply
Achilleas Margaritis wrote
> 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.

Assuming it wasn't a rhetorical question:
"A very important property for reasoning about and analysing functional programs is referential transparency: functions always return the same result when called with the same arguments. Referential transparency makes it possible to reason about the evaluation of a program by substituting an application of a function with arguments by the functions definition in which for each argument in the definition uniformly the corresponding argument of the application is substituted. This principle of uniform substitution, which is familiar from high school mathematics, is vital for reasoning about functional programs."

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

Graham Lea

Posts: 3
Nickname: grlea
Registered: Nov, 2003

Re: Language Purity and Dirty and Clean Functions Posted: Jun 27, 2006 9:44 PM
Reply to this message Reply
>label functions as "clean" and "dirty" depending on whether they have side-effects or not

Sounds like 'const' to me. :)

Isaac Gouy

Posts: 527
Nickname: igouy
Registered: Jul, 2003

Purity Posted: Jun 27, 2006 11:24 PM
Reply to this message Reply
Christopher Diggins wrote 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.

Hmmm isn't there just one thing - referential transparency "a function called with any given arguments will always return the same value".

That property couldn't be guaranteed in a language with unrestricted side-effects - the return value could varying with side-effects to some persistent state.

Purely functional programming language is slightly ambiguous, here's the appropriate comp.lang.functional FAQ entry
http://www.cs.nott.ac.uk/~gmh/faq.html#purity

Andy Dent

Posts: 165
Nickname: andydent
Registered: Nov, 2005

Re: Language Purity and Dirty and Clean Functions Posted: Jun 28, 2006 5:32 AM
Reply to this message Reply
> 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.

I don't get this argument, which I've seen many times, but then I don't have a formal CS education.

If I have a function which is passed either a file or a filesystem in a given state and it writes out something then the state of that incoming system has changed.

Say it was passed a file stream, if called immediately again with the same open file stream then it is not being called with the same arguments (unless the state of the stream is readjusted to match the original call).

Likewise, as someone has already pointed out, a c++ member function has an implied argument of a c++ object as its first argument. If the member is called again with that object after the object has had a state change then how can you say the function is being called "with the same arguments"?

I have been trying for a couple of years, as a low-priority activity, to understand more about FP and would really welcome someone pointing me to an explanation of what I'm missing here.

Kay Schluehr

Posts: 302
Nickname: schluehk
Registered: Jan, 2005

Re: Language Purity and Dirty and Clean Functions Posted: Jun 28, 2006 5:34 AM
Reply to this message Reply
> 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?

I think it has something to do with Chris main requirement ( as I understand it ): make state explicit in the type system. One way to make it explicit is to disallow it in the first place and use an additional language construct ( monads or uniqueness types ) and reify state again in this realm. It is quite disputable though whether this "separation of concerns" is worth the effort. When we admit that pure FP is of scientific value, after the problem of design/engineering of such languages is solved, I'm curious about the hypothesis ( instead of ideology and new age babble ). We have now Haskell and Clean to study pure FPs and we might compare their solutions with those of imperative OO or impure FPs like Lisp/OCaml. Maybe it turns out that not state is the problem per se but just certain types of statefull couplings with leaking abstractions?

Achilleas Margaritis

Posts: 674
Nickname: achilleas
Registered: Feb, 2005

Re: Language Purity and Dirty and Clean Functions Posted: Jun 28, 2006 6:26 AM
Reply to this message Reply
> Maybe it turns out that not state is the
> problem per se but just certain types of statefull
> couplings with leaking abstractions?

Exactly! it is not state manipulation that is the problem, but specific problems around state that should be solved.

The removal of state manipulation from a program is like having a finger pain and cutting the finger.

Jules Jacobs

Posts: 119
Nickname: jules2
Registered: Mar, 2006

Re: Language Purity and Dirty and Clean Functions Posted: Jun 28, 2006 6:59 AM
Reply to this message Reply
> 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 you don't want to understand it, but anyway:

Suppose we have this program:

a = [1,2,3]

for i = 0; i < a.length; i++
a[i] = f(a[i])
end

for i = 0; i < a.length; i++
a[i] = g(a[i])
end


This could be optimized to:

a = [1,2,3]

for i = 0; i < a.length; i++
a[i] = g(f(a[i]))
end


But this isn't possible or may not be easy in a language with side effects. You can't be sure that f has a side effect on which g depends.

If you consider the functional equivalent:

a = [1,2,3]
map(map(a, f), g)


where f and g are pure functions, this optimization *is* possible:

a = [1,2,3]
map(a, g . f)


The big problem is that functional programs run slower on regular computers, because instructions on a computer are imperative. Functional languages like Haskell don't work very well on the machines we have.

Cat is different. Cat uses the stack, and each function transforms the stack. Cat could probably be very efficient, because (1) Cat code is pretty close to the machine (imperative) (2) Cat code can be optimized like functional programs:

[1,2,3] [f] map [g] map => [1,2,3] [f g] map

This transformation is not possible unless you can guarantee that f and g are pure. In this case that means that they don't use I/O and they have to pop exactly one element off the stack, and push exactly one back.

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: Optimization Posted: Jun 28, 2006 9:20 AM
Reply to this message Reply
On a side note, there has been some work in JVM to allow stack based allocation (and other optimizations) based on escape analysis.

http://www.research.ibm.com/people/g/gupta/escape.ps

Wouldn't this allow for some of the types of optimizations that are possible with 'pure' calls?

Achilleas Margaritis

Posts: 674
Nickname: achilleas
Registered: Feb, 2005

Re: Language Purity and Dirty and Clean Functions Posted: Jun 28, 2006 10:15 AM
Reply to this message Reply
> > 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 you don't want to understand it, but anyway:
>
> Suppose we have this program:
>
> a = [1,2,3]
>
> for i = 0; i < a.length; i++
> a[i] = f(a[i])
> end
>
> for i = 0; i < a.length; i++
> a[i] = g(a[i])
> end

>
> This could be optimized to:
>
> a = [1,2,3]
>
> for i = 0; i < a.length; i++
> a[i] = g(f(a[i]))
> end

>
> But this isn't possible or may not be easy in a language
> with side effects. You can't be sure that f has a side
> effect on which g depends.
>
> If you consider the functional equivalent:
>
> a = [1,2,3]
> map(map(a, f), g)

>
> where f and g are pure functions, this optimization *is*
> possible:
>
> a = [1,2,3]
> map(a, g . f)

>
> The big problem is that functional programs run slower on
> regular computers, because instructions on a computer are
> imperative. Functional languages like Haskell don't work
> very well on the machines we have.

But it is easy to optimize those away even on an imperative language, provided that F and G do not have assignment statements. A compiler could infer the 'pure' attribute when compiling a function, save it along the symbol file and later use it for optimizations.

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: Language Purity and Dirty and Clean Functions Posted: Jun 28, 2006 10:26 AM
Reply to this message Reply
> But it is easy to optimize those away even on an
> imperative language, provided that F and G do not have
> assignment statements. A compiler could infer the 'pure'
> attribute when compiling a function, save it along the
> symbol file and later use it for optimizations.

With escape analysis you can even optimize when F and G do have assignments as long as the side-effects do not 'escape'.

Isaac Gouy

Posts: 527
Nickname: igouy
Registered: Jul, 2003

Re: Language Purity and Dirty and Clean Functions Posted: Jun 28, 2006 11:51 AM
Reply to this message Reply
Kay Schluehr wrote It is quite disputable though whether this "separation of concerns" is worth the effort.

One comparison
"Comparing Proofs about I/O in Three Programming Paradigms"
http://citeseer.ist.psu.edu/butterfield01comparing.html

Kay Schluehr

Posts: 302
Nickname: schluehk
Registered: Jan, 2005

Re: Language Purity and Dirty and Clean Functions Posted: Jun 28, 2006 1:22 PM
Reply to this message Reply
This is a very strange article. What does it demonstrate at the end? That proofs about imperative I/O is possible ( hard, harder the hardest? ) or that proofs in denotational semantics are cumbersome in general? The authors ask questions but they don't seem to draw any conclusions from their use of particular techniques and don't discuss their relevance in the broader context of reliability.

Flat View: This topic has 46 replies on 4 pages [ « | 1  2  3  4 | » ]
Topic: Language Purity and Dirty and Clean Functions Previous Topic   Next Topic Topic: Recursion in a Stack Based Language


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us