Home > Archive > Lisp > April 2004 > Re: functional purity
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Re: functional purity
|
|
| Joe Marshall 2004-04-14, 10:42 am |
| Duane Rettig <duane@franz.com> writes:
> Ilya Sher <dont_mail_me@example.com> writes:
>
> You're assuming (or perhaps you've heard somewhere) that there is
> a "dirty" style and a "pure" style. There isn't.
There is a style known as `pure functional'.
| |
| Michael Livshin 2004-04-14, 12:42 pm |
| Joe Marshall <jrm@ccs.neu.edu> writes:
> Duane Rettig <duane@franz.com> writes:
>
>
>
> There is a style known as `pure functional'.
but is there purely functional hardware?
--
I'm a Lisp variable -- bind me!
| |
| Duane Rettig 2004-04-14, 1:43 pm |
| Joe Marshall <jrm@ccs.neu.edu> writes:
> Duane Rettig <duane@franz.com> writes:
>
>
>
> There is a style known as `pure functional'.
Of course. But it looks like the poster has no idea what it is,
and is just spouting words that were heard somewhere.
I know someone else joked about my attempt to get into the mind
of this person, but it was truly an honest attempt to help. Whenever
I try to help someone gain some understanding, I find that it wastes
much less time to find out where the person is coming from, and to
take it from there, than to just make assumptions and then have to
backtrack because those assumptions were wrong. It is now clear
that in this forum at least, this person is not interested in
revealing the bases for these questions, and for this reason I
cannot be of help.
--
Duane Rettig duane@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
| |
| Ilya Sher 2004-04-14, 1:44 pm |
| Michael Livshin wrote:
> Joe Marshall <jrm@ccs.neu.edu> writes:
>
>
>
>
> but is there purely functional hardware?
>
Wouldn't that require infinite memory?
Hmm... how do we implement PC (program counter)
that is not overwritten on "inc" command ?
| |
| Frode Vatvedt Fjeld 2004-04-14, 1:44 pm |
| Michael Livshin <usenet@cmm.kakpryg.net> writes:
> but is there purely functional hardware?
Of course: combinatorial circuits.
--
Frode Vatvedt Fjeld
| |
| Ilya Sher 2004-04-14, 1:44 pm |
| Duane Rettig wrote:
> Joe Marshall <jrm@ccs.neu.edu> writes:
>
>
>
>
> Of course. But it looks like the poster has no idea what it is,
> and is just spouting words that were heard somewhere.
I know in general.
I would summ it up as (correct if wrong):
A function have no side effects and returns
always the same results for same input.
It have many positive consequeneces which I don't really know
in depth but one of them is that you can cache results (assuming
it worth (cpu cycles saved) and is bearable (not consuming too
much memory))
Any additional links to reading about this issue
(electronic format,not books) will be helpful.
>
> I know someone else joked about my attempt to get into the mind
> of this person, but it was truly an honest attempt to help. Whenever
> I try to help someone gain some understanding, I find that it wastes
> much less time to find out where the person is coming from, and to
> take it from there, than to just make assumptions and then have to
> backtrack because those assumptions were wrong. It is now clear
> that in this forum at least, this person is not interested in
> revealing the bases for these questions, and for this reason I
> cannot be of help.
>
Sorry for wrong impression.
I'm just s ing something like "perfect code" for
the problem. I want to learn by examples of really
good code. Sorry, what I think it is.
| |
|
| Ilya Sher wrote:
> Duane Rettig wrote:
>
>
> I know in general.
> I would summ it up as (correct if wrong):
>
> A function have no side effects and returns
> always the same results for same input.
> It have many positive consequeneces which I don't really know
> in depth but one of them is that you can cache results (assuming
> it worth (cpu cycles saved) and is bearable (not consuming too
> much memory))
>
> Any additional links to reading about this issue
> (electronic format,not books) will be helpful.
>
> Sorry for wrong impression.
> I'm just sing something like "perfect code" for
> the problem. I want to learn by examples of really
> good code. Sorry, what I think it is.
A few places to start reading about pure-functional programming are:
http://www.md.chalmers.se/~rjmh/Papers/whyfp.html
http://www.haskell.org/
http://www.cs.oberlin.edu/classes/d...ombinators.html
Folks have raised some valid questions about whether anyone should care
about pure functional programming. The best reply I know of is that pure
functional programming is fun, an interesting intellectual exercise, a
fun problem. As well, some stuff that comes out of trying to do it is
beautiful. I think the thing that makes me like pure-functional
languages and associated stuff is approximately the same thing that made
me like abstract algebras when I was in college.
Also, one can admire the long distance that pure-functional folks have
come in compiler development in roughly the same way one can admire the
very clever developments that Lisp compiler writers have made over the
years in order to get Lisp compilers that compete well with languages
like C. The best functional-language compilers produce results that are
pretty close to the best Lisp or C compilers, a result that is
impressive, considering how much slower naive implementations of
pure-functional languages are even than naive implementations of Lisp.
| |
| Simon Adameit 2004-04-14, 2:48 pm |
| On Wed, 14 Apr 2004 20:48:36 +0300, Ilya Sher wrote:
> Duane Rettig wrote:
>
> A function have no side effects and returns
> always the same results for same input.
That is exactly what most "dirty" examples showed to you here do.
For example the one by Edi Weitz:
(defun copy-matrix (matrix)
(mapcar #'copy-list matrix))
(defun xchg-rows* (matrix n m)
(xchg-rows (copy-matrix matrix) n m))
It will return a copy of the original matrix that has the rows exchanged.
Just like a purely functional solution would construct such a matrix by
recursing over the original one.
Why does it matter how the result is constructed as long as the behavior
of the function is still "functional"?
| |
| Simon Adameit 2004-04-14, 2:48 pm |
| On Wed, 14 Apr 2004 19:24:04 +0200, Simon Adameit wrote:
[color=darkred]
I'm sorry for wrong quoting. It was of course Ilya Sher who wrote that.
| |
| Duane Rettig 2004-04-14, 2:49 pm |
| Ilya Sher <dont_mail_me@example.com> writes:
> Duane Rettig wrote:
>
>
>
> I know in general.
> I would summ it up as (correct if wrong):
>
> A function have no side effects and returns
> always the same results for same input.
> It have many positive consequeneces which I don't really know
> in depth but one of them is that you can cache results (assuming
> it worth (cpu cycles saved) and is bearable (not consuming too
> much memory))
OK, this does help me to understand where you're coming from.
One other requirement for a pure-function is that it be a solution
for a purely functional problem. See below for more on this.
> Any additional links to reading about this issue
> (electronic format,not books) will be helpful.
>
> Sorry for wrong impression.
> I'm just sing something like "perfect code" for
> the problem. I want to learn by examples of really
> good code. Sorry, what I think it is.
The perfect code for a problem is the code that solves the
problem. In this case I mean "perfect" as in "complete" or
"being or performing as intended", and not as "without blemish".
In your original request, you wanted a way to exchange rows in a
matrix. But in this article you added that you preferred to do
this without consuming too much memory. My contention is that
this is not the right problem for a functional solution, because
a purely functional solution will necessarily cons a new matrix
at least the first time for each set of arguments, and if the
function is not memoized it will cons for every invocation. If
you disturb the original matrix, that's a side-effect, and thus
not purely functional (it has the dual spoiler of pure-functional
of not being side-effect free and also not being repeatable,
though if it is the same two rows that are being swapped I
suppose you could say that it is cyclic :-).
Whether or not you desire a pure-functional solution really
depends on your requiremnents. Many programmers start out by
saying "I don't care about consing" or "I don't care about
speed", but in the end the requirement is very much there; it
usually turns out to be a question of degree. A little consing
and/or slowness is tolerable for the sake of purity, especially if
that purity translates into better maintainability of the code,
but if it becomes so slow as to make you wonder why you did the
solution in this particular language, you will either switch
languages or care more about speed or consing the next time around.
--
Duane Rettig duane@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
| |
| Ilya Sher 2004-04-14, 3:37 pm |
| Simon Adameit wrote:
> Why does it matter how the result is constructed as long as the behavior
> of the function is still "functional"?
Learning purposes.
Intellectual game.
Good feeling about the code.
| |
| Ilya Sher 2004-04-14, 3:37 pm |
| Duane Rettig wrote:
[snip]
>
> The perfect code for a problem is the code that solves the
> problem. In this case I mean "perfect" as in "complete" or
> "being or performing as intended", and not as "without blemish".
>
> In your original request, you wanted a way to exchange rows in a
> matrix.
> But in this article you added that you preferred to do
> this without consuming too much memory.
Maybe I was not clear enough. I asked for functional solution
despite this fact:
####
I would like to see "pure" code for now.
Yes, even if it conses too much and therefore
eats CPU and memory.
####
> My contention is that
> this is not the right problem for a functional solution, because
> a purely functional solution will necessarily cons a new matrix
> at least the first time for each set of arguments, and if the
> function is not memoized it will cons for every invocation. If
> you disturb the original matrix, that's a side-effect, and thus
> not purely functional (it has the dual spoiler of pure-functional
> of not being side-effect free and also not being repeatable,
> though if it is the same two rows that are being swapped I
> suppose you could say that it is cyclic :-).
>
> Whether or not you desire a pure-functional solution really
> depends on your requiremnents.
Agreed but I don't have real-life requirements at
this stage of learning.
> Many programmers start out by
> saying "I don't care about consing" or "I don't care about
> speed", but in the end the requirement is very much there; it
> usually turns out to be a question of degree.
Agreed.
> A little consing
> and/or slowness is tolerable for the sake of purity, especially if
> that purity translates into better maintainability of the code,
> but if it becomes so slow as to make you wonder why you did the
> solution in this particular language, you will either switch
> languages or care more about speed or consing the next time around.
>
| |
| Thomas F. Burdick 2004-04-14, 4:34 pm |
| Ilya Sher <dont_mail_me@example.com> writes:
> Duane Rettig wrote:
> [snip]
>
>
> Maybe I was not clear enough. I asked for functional solution
> despite this fact:
> ####
> I would like to see "pure" code for now.
> Yes, even if it conses too much and therefore
> eats CPU and memory.
> ####
Butting in here because I'm avoiding work and silly things like this
can be fun on occasion... how about this:
(defun swap-elements (list x y)
(labels ((worker (list x y x-elt)
(cond
((null list) nil)
((zerop x) (cons (nth y list)
(worker (cdr list) (1- x) (1- y) (car list))))
((zerop y) (cons x-elt
(worker (cdr list) (1- x) (1- y) x-elt)))
(t (cons (car list)
(worker (cdr list) (1- x) (1- y) x-elt))))))
(if (<= x y)
(worker list x y nil)
(worker list y x nil))))
At worst it traverses the list twice, and only uses stack space linear
to the length of the list. Stack space is just memory, after all.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
| |
| Joe Marshall 2004-04-14, 4:34 pm |
| Ilya Sher <dont_mail_me@example.com> writes:
> I know in general.
> I would summ it up as (correct if wrong):
>
> A function have no side effects and returns
> always the same results for same input.
> It have many positive consequeneces which I don't really know
> in depth but one of them is that you can cache results (assuming
> it worth (cpu cycles saved) and is bearable (not consuming too
> much memory))
The primary advantage of pure functions is that they compose nicely.
| |
| Camm Maguire 2004-04-14, 6:36 pm |
| Greetings! Just wondering if it is possible to have a lisp compiler
setting triggering warning or failure for non-functional code. Also
wondering whether this has already been achieved anywhere.
Take care,
Joe Marshall <jrm@ccs.neu.edu> writes:
> Ilya Sher <dont_mail_me@example.com> writes:
>
>
> The primary advantage of pure functions is that they compose nicely.
--
Camm Maguire camm@enhanced.com
========================================
==================================
"The earth is but one country, and mankind its citizens." -- Baha'u'llah
| |
| John Thingstad 2004-04-14, 8:34 pm |
| On Wed, 14 Apr 2004 19:33:14 +0300, Ilya Sher <dont_mail_me@example.com>
wrote:
> Michael Livshin wrote:
> Wouldn't that require infinite memory?
> Hmm... how do we implement PC (program counter)
> that is not overwritten on "inc" command ?
You seem to misundestand.
All algebra on integers is done modulo some max number.
(Bignum confuses the issue.)
But the fact that all numbers are representated a mod b
does not determine wether it is functional or not.
Pure functional algorithms have the big advantage that
they are easy to reason over. (Mathematically)
It allows a tecnique called proof by generator induction.
In particluar it is much easier to see the loop invariants in a
recursive definition. It helps to have tried to proove algorithms
mathematically to fully appiciate the difference.
(Procedural programming can be handled by Hoare logic.)
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
| |
| David Steuber 2004-04-14, 11:32 pm |
| Camm Maguire <camm@enhanced.com> writes:
> Greetings! Just wondering if it is possible to have a lisp compiler
> setting triggering warning or failure for non-functional code. Also
> wondering whether this has already been achieved anywhere.
Are you talking about "unreachable code" or "dead code"? Or are you
talking about something else?
I've seen some sort of dead code removal message from the SBCL
compiler, but it didn't mention what that code was. At least I think
I did.
--
I wouldn't mind the rat race so much if it wasn't for all the damn cats.
| |
| William Bland 2004-04-15, 12:32 am |
| On Wed, 14 Apr 2004 22:50:41 -0400, David Steuber wrote:
> Camm Maguire <camm@enhanced.com> writes:
>
>
> Are you talking about "unreachable code" or "dead code"? Or are you
> talking about something else?
>
> I've seen some sort of dead code removal message from the SBCL
> compiler, but it didn't mention what that code was. At least I think
> I did.
I think the OP was talking about detection of code with side-effects.
It should be very easy to do: Have a list of primitives that have
side effects, and then to check if a given function has side effects
you just recursively check each function that it calls, until either
you find a primitive with side effects, or you exhaust the tree and
have proved that the function has no side effects.
Having said it's easy, I've never seen it implemented in any Lisp
I've used so maybe there are hidden details (or maybe they're not
so hidden and I'm just wrong).
Cheers,
Bill.
--
Dr. William Bland www.abstractnonsense.com
Computer Programmer awksedgrep (Yahoo IM)
Any sufficiently advanced Emacs user is indistinguishable from magic
| |
| Ilya Sher 2004-04-15, 2:32 am |
| John Thingstad wrote:
> On Wed, 14 Apr 2004 19:33:14 +0300, Ilya Sher <dont_mail_me@example.com>
> wrote:
>
>
>
> You seem to misundestand.
> All algebra on integers is done modulo some max number.
> (Bignum confuses the issue.)
I was thinking about all the consing here, not math.
> But the fact that all numbers are representated a mod b
> does not determine wether it is functional or not.
> Pure functional algorithms have the big advantage that
> they are easy to reason over. (Mathematically)
> It allows a tecnique called proof by generator induction.
Added to "to_learn". ;)
> In particluar it is much easier to see the loop invariants in a
> recursive definition. It helps to have tried to proove algorithms
> mathematically to fully appiciate the difference.
> (Procedural programming can be handled by Hoare logic.)
| |
| Ilya Sher 2004-04-15, 2:32 am |
| Thomas F. Burdick wrote:
> Ilya Sher <dont_mail_me@example.com> writes:
>
>
>
>
> Butting in here because I'm avoiding work and silly things like this
> can be fun on occasion... how about this:
>
> (defun swap-elements (list x y)
> (labels ((worker (list x y x-elt)
> (cond
> ((null list) nil)
> ((zerop x) (cons (nth y list)
> (worker (cdr list) (1- x) (1- y) (car list))))
> ((zerop y) (cons x-elt
> (worker (cdr list) (1- x) (1- y) x-elt)))
> (t (cons (car list)
> (worker (cdr list) (1- x) (1- y) x-elt))))))
> (if (<= x y)
> (worker list x y nil)
> (worker list y x nil))))
>
> At worst it traverses the list twice, and only uses stack space linear
> to the length of the list. Stack space is just memory, after all.
>
Seems nice.
Thanks.
Patch ;)
((zerop y) (cons x-elt
- (worker (cdr list) (1- x) (1- y) x-elt)))
+ (worker (cdr list) (1- x) (1- y) nil)))
Will save memory I guess (not that I care but passing
something that won't be used ...)
| |
| Thomas F. Burdick 2004-04-15, 5:42 pm |
| Ilya Sher <dont_mail_me@example.com> writes:
> ((zerop y) (cons x-elt
> - (worker (cdr list) (1- x) (1- y) x-elt)))
> + (worker (cdr list) (1- x) (1- y) nil)))
>
> Will save memory I guess (not that I care but passing
> something that won't be used ...)
Nope, you're still passing a lisp object on the stack. Although, now
that you mention it, the recursion should stop there, since it doesn't
need to copy the rest of the list:
(defun swap-elements (list x y)
(labels ((worker (list x y x-elt)
(cond
((null list) nil)
((zerop x) (cons (nth y list)
(worker (cdr list) (1- x) (1- y) (car list))))
((zerop y) (cons x-elt (cdr list)))
(t (cons (car list)
(worker (cdr list) (1- x) (1- y) x-elt))))))
(if (<= x y)
(worker list x y nil)
(worker list y x nil))))
The worst case is still the same, but now the best case is significantly better.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
| |
| Camm Maguire 2004-04-15, 6:38 pm |
| Greetings!
William Bland <news@abstractnonsense.com> writes:
> On Wed, 14 Apr 2004 22:50:41 -0400, David Steuber wrote:
>
>
> I think the OP was talking about detection of code with side-effects.
> It should be very easy to do: Have a list of primitives that have
> side effects, and then to check if a given function has side effects
> you just recursively check each function that it calls, until either
> you find a primitive with side effects, or you exhaust the tree and
> have proved that the function has no side effects.
>
Yes, and this is what I was thinking of as a solution too. Would
appear helpful in determining thread safe code. GCL has some
rudimentary ability to make use of side-effect info in optimizing
functions, but doesn't calculate this info to my understanding.
Take care,
> Having said it's easy, I've never seen it implemented in any Lisp
> I've used so maybe there are hidden details (or maybe they're not
> so hidden and I'm just wrong).
>
> Cheers,
> Bill.
> --
> Dr. William Bland www.abstractnonsense.com
> Computer Programmer awksedgrep (Yahoo IM)
> Any sufficiently advanced Emacs user is indistinguishable from magic
>
--
Camm Maguire camm@enhanced.com
========================================
==================================
"The earth is but one country, and mankind its citizens." -- Baha'u'llah
| |
| Alan Crowe 2004-04-15, 7:34 pm |
| Thomas F. Burdick butted in
> silly things like this
> can be fun on occasion...
(defun swap-elements (list x y)
(labels ((worker (list x y x-elt)
(cond
((null list) nil)
((zerop x) (cons (nth y list)
(worker (cdr list) (1- x) (1- y) (car list))))
((zerop y) (cons x-elt
(worker (cdr list) (1- x) (1- y) x-elt)))
(t (cons (car list)
(worker (cdr list) (1- x) (1- y) x-elt))))))
(if (<= x y)
(worker list x y nil)
(worker list y x nil))))
> At worst it traverses the list twice,...
That is beautiful code. It has a sparkling, gem like
quality.
I've laboured to eliminate the duplicate list traversal
implicit in the use of nth, and have come up with this ugly
beasty, that processes on both the flood and the ebb of the
recursion.
(defun swap-elements (list first-index second-index)
(labels ((worker (list first-index second-index carry-down)
(if (zerop second-index)
(values (cons carry-down (cdr list))
(car list))
(multiple-value-bind (ascending-list carry-up)
(worker (cdr list)
(- first-index 1)
(- second-index 1)
(if (zerop first-index)
(car list)
carry-down))
(if (zerop first-index)
(cons carry-up ascending-list)
(values (cons (car list) ascending-list)
carry-up))))))
(if (<= first-index second-index)
(worker list first-index second-index nil)
(worker list second-index first-index nil))))
Alan Crowe
Edinburgh
Scotland
| |
|
|
| Ilya Sher 2004-04-16, 8:40 am |
| Alan Crowe wrote:
> Thomas F. Burdick butted in
>
>
>
> (defun swap-elements (list x y)
> (labels ((worker (list x y x-elt)
> (cond
> ((null list) nil)
> ((zerop x) (cons (nth y list)
> (worker (cdr list) (1- x) (1- y) (car list))))
> ((zerop y) (cons x-elt
> (worker (cdr list) (1- x) (1- y) x-elt)))
> (t (cons (car list)
> (worker (cdr list) (1- x) (1- y) x-elt))))))
> (if (<= x y)
> (worker list x y nil)
> (worker list y x nil))))
>
>
>
>
> That is beautiful code. It has a sparkling, gem like
> quality.
That is what I was looking for ;)
>
> I've laboured to eliminate the duplicate list traversal
> implicit in the use of nth, and have come up with this ugly
> beasty, that processes on both the flood and the ebb of the
> recursion.
>
> (defun swap-elements (list first-index second-index)
> (labels ((worker (list first-index second-index carry-down)
> (if (zerop second-index)
> (values (cons carry-down (cdr list))
> (car list))
> (multiple-value-bind (ascending-list carry-up)
> (worker (cdr list)
> (- first-index 1)
> (- second-index 1)
> (if (zerop first-index)
> (car list)
> carry-down))
> (if (zerop first-index)
> (cons carry-up ascending-list)
> (values (cons (car list) ascending-list)
> carry-up))))))
> (if (<= first-index second-index)
> (worker list first-index second-index nil)
> (worker list second-index first-index nil))))
>
> Alan Crowe
> Edinburgh
> Scotland
>
>
Looks complicated :(
| |
| Bruce Hoult 2004-04-17, 2:31 am |
| In article <pan.2004.04.15.03.37.17.429733@abstractnonsense.com>,
William Bland <news@abstractnonsense.com> wrote:
> I think the OP was talking about detection of code with side-effects.
> It should be very easy to do: Have a list of primitives that have
> side effects, and then to check if a given function has side effects
> you just recursively check each function that it calls, until either
> you find a primitive with side effects, or you exhaust the tree and
> have proved that the function has no side effects.
Except that doesn't really tell you what you want to know. It's much
more important that things have pure functional interfaces than that
they have pure functional implementations. A good compiler for a pure
functional language will turn lots of your mutation-free code into code
that uses mutation under the hood. With not such a good compiler, you
can do it yourself.
There's nothing at all wrong with consing up a list in the "wrong" order
and then calling nreverse on it before returning it. The interface is
pure functional, even though the implementation isn't.
-- Bruce
| |
| Tim Bradshaw 2004-04-17, 5:32 pm |
| * William Bland wrote:
> I think the OP was talking about detection of code with side-effects.
> It should be very easy to do: Have a list of primitives that have
> side effects, and then to check if a given function has side effects
> you just recursively check each function that it calls, until either
> you find a primitive with side effects, or you exhaust the tree and
> have proved that the function has no side effects.
It's not easy to do. Consider something like this:
(defun grovel-list (fun l &optional (comparator nil comparatorp))
(loop for e in l
when (funcall fun e) collect e into results
finally (return (if comparatorp
(sort results comparator)
results))))
This is a side-effect-free function, but its implementation has one
explicit call to a non-side-effect-free function (SORT) and the
expansion of LOOP is probably a mass of side-effects.
--tim
| |
| William Bland 2004-04-17, 5:32 pm |
| On Sat, 17 Apr 2004 19:35:15 +0100, Tim Bradshaw wrote:
> * William Bland wrote:
>
>
> It's not easy to do. Consider something like this:
>
> (defun grovel-list (fun l &optional (comparator nil comparatorp))
> (loop for e in l
> when (funcall fun e) collect e into results
> finally (return (if comparatorp
> (sort results comparator)
> results))))
>
> This is a side-effect-free function, but its implementation has one
> explicit call to a non-side-effect-free function (SORT) and the
> expansion of LOOP is probably a mass of side-effects.
>
> --tim
Ah, I see, thanks for pointing this out - I should have thought
about it a bit harder. I suppose to do this properly then, you
would need a fairly sophisticated approach using an automated
theorem prover or something. It probably wouldn't be worth the
effort.
Cheers,
Bill.
--
Dr. William Bland www.abstractnonsense.com
Computer Programmer awksedgrep (Yahoo IM)
Any sufficiently advanced Emacs user is indistinguishable from magic
| |
| Rahul Jain 2004-04-17, 10:32 pm |
| Ilya Sher <dont_mail_me@example.com> writes:
> A function have no side effects and returns
> always the same results for same input.
How do you define "same"? Is (list 1 2) the same as (list 1 2)? (The
answer, in the normal way I've seen the word "same" used in the context
of Lisp, is "no", since the two lists are not EQ.)
--
Rahul Jain
rjain@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
| |
| Rahul Jain 2004-04-17, 10:32 pm |
| Ilya Sher <dont_mail_me@example.com> writes:
> Looks complicated :(
But it's the ideal implementation when you're demanding functional
purity.
--
Rahul Jain
rjain@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
| |
| Joe Marshall 2004-04-20, 9:42 am |
| Rahul Jain <rjain@nyct.net> writes:
> Ilya Sher <dont_mail_me@example.com> writes:
>
>
> How do you define "same"?
For a functional language, a reasonable definition of `same' is
`functionally equivalent'.
> Is (list 1 2) the same as (list 1 2)? (The answer, in the normal
> way I've seen the word "same" used in the context of Lisp, is "no",
> since the two lists are not EQ.)
The answer is `maybe'. They aren't EQ obviously, but they are EQUAL.
If you use eschew side effects, then EQUAL should be a sufficient
comparison.
| |
| EL Henry 2004-04-25, 2:31 am |
| Ilya Sher <dont_mail_me@example.com> wrote in message news:<newscache$xn66wh$uq8$1@lnews.actcom.co.il>...[color=darkred]
> Duane Rettig wrote:
>
> I know in general.
> I would summ it up as (correct if wrong):
>
> A function have no side effects and returns
> always the same results for same input.
> It have many positive consequeneces which I don't really know
> in depth but one of them is that you can cache results (assuming
> it worth (cpu cycles saved) and is bearable (not consuming too
> much memory))
>
> Any additional links to reading about this issue
> (electronic format,not books) will be helpful.
Hi Ilya --
There's something called "the Leibniz principle": you use in
mathematics all the time: whenever you apply the same function to two
equivalent terms, the result is also equivalent; for instance:
x^2 = x*x
which you know to be true.
If you were to apply a function to both terms of this equivalence,
the result would also retain the equivalence relation between terms.
f(x^2) = f(x*x)
You know this from high school math.
When you program in imperative style, say
y:= f(x);
while b(y) do
y := g(y);
z := h(y)
it might be that attributing g(y) to y breaks the principle above
(for instance, through side effect in a subroutine called by g). It
becomes much harder to garantee the integrity of the equivalence
relation when you go back to the main loop (for example).
When you program in functional style you would change the code
snippet above (actually, you wouldn't even write it) to something that
relied upon induction. The correctness of the code could be proved
mathematically by induction. That particular "school" claims that it
is a better way to program, because you can prove correctness like you
prove a theorem (there are other approaches to "proving program
correctness as if they were theorems", like the "school" of
Hoare/Djikstra/Gries/etc.).
IMHO, the literature on ML (or Haskell there are more books on ML,
though). On Lisp touches on these issues in a deeper way than Ansi
Common Lisp (Paul Graham).
HTH
Cheers
Henry
|
|
|
|
|