hi,
can anyone suggest an efficient way to convert the following
non-referentially transparent code to one which is referentially
transparent:
if (A) {
if (B) { x = 3; }
else { y = 3; }
}
else {
if (C) { z = 3; }
else { a = 3; }
}
my only idea is:
let (x,y,z,a) =
if (A) then if (B) then (3,y,z,a)
else (x,3,z,a)
else if (C) then (x,y,3,a)
else (x,y,z,3)
in the above i assume the variables x,y,z, and a already have
pre-existing values in both cases, and the code merely chooses which of
those four to
change (destructively) or re-assign to '3'.
i can't imagine this is the best way to do such a thing!
thanks in advance.
henry
"hank_rb" <·········@gmail.com> writes:
> hi,
>
> can anyone suggest an efficient way to convert the following
> non-referentially transparent code to one which is referentially
> transparent:
>
> if (A) {
> if (B) { x = 3; }
> else { y = 3; }
> }
>
> else {
> if (C) { z = 3; }
> else { a = 3; }
>
> }
>
> my only idea is:
>
> let (x,y,z,a) =
> if (A) then if (B) then (3,y,z,a)
> else (x,3,z,a)
> else if (C) then (x,y,3,a)
> else (x,y,z,3)
>
> in the above i assume the variables x,y,z, and a already have
> pre-existing values in both cases, and the code merely chooses which of
> those four to
> change (destructively) or re-assign to '3'.
>
> i can't imagine this is the best way to do such a thing!
It's not that bad. What do you find wrong with it?
If you really despite it, you could write it as:
(defmacro cond-let (cond-vars expression &body body)
`(cond
,@(loop
:for (c v) in cond-vars
:collect `(,c (let ((,v ,expressioN)) ,@body)))))
(macroexpand-1
'(cond-let (((and (a) (b)) x)
((and (a) (not (b))) y)
((and (not (a)) (c)) z)
(t a)) 3
(print (list x y z a))))
--> (COND ((AND (A) (B)) (LET ((X 3)) (PRINT (LIST X Y Z A))))
((AND (A) (NOT (B))) (LET ((Y 3)) (PRINT (LIST X Y Z A))))
((AND (NOT (A)) (C)) (LET ((Z 3)) (PRINT (LIST X Y Z A))))
(T (LET ((A 3)) (PRINT (LIST X Y Z A))))) ;
(flet ((a () (oddp (random 2)))
(b () (oddp (random 2)))
(c () (oddp (random 2))))
(let ((x 10) (y 20) (z 30) (a 40))
(cond-let (((and (a) (b)) x)
((and (a) (not (b))) y)
((and (not (a)) (c)) z)
(t a)) 3
(list x y z a))))
--> (3 20 30 40)
--
__Pascal Bourguignon__ http://www.informatimago.com/
In a World without Walls and Fences,
who needs Windows and Gates?
From: Björn Lindberg
Subject: Re: branch and assignment statements translation to functional style
Date:
Message-ID: <4338f68c$1@news.cadence.com>
hank_rb wrote:
> hi,
>
> can anyone suggest an efficient way to convert the following
> non-referentially transparent code to one which is referentially
> transparent:
>
> if (A) {
> if (B) { x = 3; }
> else { y = 3; }
> }
>
> else {
> if (C) { z = 3; }
> else { a = 3; }
>
> }
>
> my only idea is:
>
> let (x,y,z,a) =
> if (A) then if (B) then (3,y,z,a)
> else (x,3,z,a)
> else if (C) then (x,y,3,a)
> else (x,y,z,3)
>
> in the above i assume the variables x,y,z, and a already have
> pre-existing values in both cases, and the code merely chooses which of
> those four to
> change (destructively) or re-assign to '3'.
>
> i can't imagine this is the best way to do such a thing!
Turn it inside out:
(flet ((f (a x y z)
<the part using the variables goes here>))
(if a
(if b
(f a 3 y z)
(f a x 3 z))
(if c
(f a x y 3)
(f 3 x y z))))
Bj�rn
From: Sven-Olof Nystr|m
Subject: Re: branch and assignment statements translation to functional style
Date:
Message-ID: <vpzmpy7nn3.fsf@harpo.it.uu.se>
Bj�rn Lindberg <·····@runa.se> writes:
> hank_rb wrote:
>> hi,
>> can anyone suggest an efficient way to convert the following
>> non-referentially transparent code to one which is referentially
>> transparent:
>> if (A) {
>> if (B) { x = 3; }
>> else { y = 3; }
>> }
>> else {
>> if (C) { z = 3; }
>> else { a = 3; }
>> }
>> my only idea is:
>> let (x,y,z,a) =
>> if (A) then if (B) then (3,y,z,a)
>> else (x,3,z,a)
>> else if (C) then (x,y,3,a)
>> else (x,y,z,3)
>> in the above i assume the variables x,y,z, and a already have
>> pre-existing values in both cases, and the code merely chooses which of
>> those four to
>> change (destructively) or re-assign to '3'.
>> i can't imagine this is the best way to do such a thing!
>
> Turn it inside out:
>
> (flet ((f (a x y z)
> <the part using the variables goes here>))
> (if a
> (if b
> (f a 3 y z)
> (f a x 3 z))
> (if c
> (f a x y 3)
> (f 3 x y z))))
>
What's wrong with
What's wrong with
(multiple-value-bind (x y z a)
(cond
((and a b) (values (3 y z a)))
((and a (not b)) (values (x 3 z a)))
(c (values (x y 3 a)))
(t (values (x y z 3))))
[rest of code inserted here])?
The cond can be replaced by doubly nested ifs, of course.
Actually, I think the first code is quite reasonable, even if one
wants to follow a functional programming style. It is easy to remove
assignments to local variables by a mechanical translation (think SSA)
so for all practical purposes assignments to local variables is
compatible with a functional programming style.
Sven-Olof
--
Sven-Olof Nystrom
Comp Sci Dept, Uppsala University, Box 337, S-751 05 Uppsala SWEDEN
········@csd.uu.se phone: +46 18 471 76 91, fax: +46 18 51 19 25
Sven-Olof Nystr|m <········@harpo.it.uu.se> writes:
> Bj�rn Lindberg <·····@runa.se> writes:
>
> > (flet ((f (a x y z)
> > <the part using the variables goes here>))
> > (if a
> > (if b
> > (f a 3 y z)
> > (f a x 3 z))
> > (if c
> > (f a x y 3)
> > (f 3 x y z))))
>
> What's wrong with
>
> (multiple-value-bind (x y z a)
> (cond
> ((and a b) (values (3 y z a)))
> ((and a (not b)) (values (x 3 z a)))
> (c (values (x y 3 a)))
> (t (values (x y z 3))))
>
> [rest of code inserted here])?
>
> The cond can be replaced by doubly nested ifs, of course.
(as it can in Bjorn's version).
I have a hard time imagining when the m-v-bind formulation would be
clearer. In all likelyhood, in a situation like this where you're
trying to bind four different values, you probably have a prime
candidate for a local function, simply on the grounds of breaking the
problem up into functional pieces. Of course, when everything is
named x y z a b c, it only obscures things.
--
/|_ .-----------------------.
,' .\ / | Free Mumia Abu-Jamal! |
,--' _,' | Abolish the racist |
/ / | death penalty! |
( -. | `-----------------------'
| ) |
(`-. '--.)
`. )----'
thanks to everyone who replied. but all of those solutions involve a
lot of repetition of code and assignments. but, it's an isolated and
contrived example. i'm not sure if it would ever come up for an
experienced functional programmer.
more generally, i want to practice converting procedural algorithms
into a purely functional style in order to understand them. maybe this
isn't such a good idea?
in any case, the original algorithm i want to convert to functional
style is the following, from 'Numerical Recipes: The art of scientific
computing' by Press, Flannery, Teukolsky and Vetterling.
This to me is a particularly challenging one because of the goto
statements. but, even just code with a lot of assignments to global
variables inside nested if clauses seems to give rise to the above
problem. Thomas's suggestion may be the key, but i just don't have
the experience with it.
has anyone tried to do this sort of 'procedural to functional'
conversion exercise? or, if not, is there a good reason not to even
try? i'm curious how someone with a lot of experience in procedural
languages should go about learning to write in a functional style.
thanks in advance!
FUNCTION DBRENT(AX,BX,CX,F,DF,TOL,XMIN)
PARAMETER (ITMAX=100,ZEPS=1.0E-10)
LOGICAL OK1,OK2
A=MIN(AX,CX)
B=MAX(AX,CX)
V=BX
W=V
X=V
E=0.
FX=F(X)
FV=FX
FW=FX
DX=DF(X)
DV=DX
DW=DX
DO ITER=1,ITMAX
XM=0.5*(A+B)
TOL1=TOL*ABS(X)+ZEPS
TOL2=2.*TOL1
IF(ABS(X-XM).LE.(TOL2-.5*(B-A))) GOTO 3
IF(ABS(E).GT.TOL1) THEN
D1=2.*(B-A)
D2=D1
IF(DW.NE.DX) D1=(W-X)*DX/(DX-DW)
IF(DV.NE.DX) D2=(V-X)*DX/(DX-DV)
U1=X+D1
U2=X+D2
OK1=((A-U1)*(U1-B).GT.0.).AND.(DX*D1.LE.0.)
OK2=((A-U2)*(U2-B).GT.0.).AND.(DX*D2.LE.0.)
OLDE=E
E=D
IF(.NOT.(OK1.OR.OK2))THEN
GOTO 1
ELSE IF (OK1.AND.OK2) THEN
IF(ABS(D1).LT.ABS(D2)) THEN
D=D1
ELSE
D=D2
ENDIF
ELSE IF (OK1) THEN
D=D1
ELSE
D=D2
ENDIF
IF(ABS(D).GT.ABS(0.5*OLDE)) GOTO 1
U=X+D
IF(U-A.LT.TOL2 .OR. B-U.LT.TOL2) D-SIGN(TOL1,XM-X)
GOTO 2
ENDIF
1 IF(DX.GE.0.) THEN
E=A-X
ELSE
E=B-X
ENDIF
D=0.5*E
2 IF(ABS(D).GE.TOL1) THEN
U=X+D
FU=F(U)
ELSE
U=X+SIGN(TOL1,D)
FU=F(U)
IF(FU.GT.FX) GOTO 3
ENDIF
DU=DF(U)
IF(FU.LE.FX) THEN
IF(U.GE.X) THEN
A=X
ELSE
B=X
ENDIF
V=W
FV=FW
DV=DW
W=X
FW=FX
DW=DX
X=U
FX=FU
DX=DU
ELSE
IF(U.LT.X) THEN
A=U
ELSE
B=U
ENDIF
IF(FU.LE.FW .OR. W.EQ.X) THEN
V=W
FV=FW
DV=DW
W=U
FW=FU
DW=DU
ELSE IF(FU.LE.FV .OR. V.EQ.X .OR. V.EQ.W) THEN
V=U
FV=FU
DV=DU
ENDIF
ENDIF
CONTINUE
PAUSE 'DBREND exceeded maximum iterations.'
3 XMIN=X
DBRENT=FX
RETURN
END
hank_rb wrote:
>
> in any case, the original algorithm i want to convert to functional
> style is the following, from 'Numerical Recipes: The art of scientific
> computing' by Press, Flannery, Teukolsky and Vetterling.
Ignoring the issue of functional style vs. imperative, Numerical
Recipes has serious drawbacks as a source of numerical algorithms. I
would recommend finding algorithms through the Netlib repository
(www.netlib.org). http://www.netlib.org/misc/gams.html organizes the
library by the numerical problem solved.
In article <························@g44g2000cwa.googlegroups.com>,
"hank_rb" <·········@gmail.com> wrote:
> joseph,
> fabulous. i forwarded this to my friend, who'se used a lot of the
> numerical recipes. thanks!
Could you *please* provide context in your replies. Most of your
responses make little sense because you refer to things like "this" and
we can't see what it is.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
pascal,
>For example, let's start with the gcd algorithm:
thanks for the demonstration of the GCD algorithm. it is clear that
the algorithm can be expressed as is entirely in functional style, and
that when it is expressed in procedural style, the original algorithm
is somewhat obfuscated.
my main question (or challenge) is: can you imagine an algorithm which,
*in its original expression* contains destructive updating, and which
cannot be restated more simply without that destructive updating?
restated, even though math contains no destructive updating, not all
algorithms are conceived entirely in terms of math. is this a fault of
the algorithm, or is there an intrinsic need for destructive updating
in original algorithms, or is that an accident of how procedural
programmers conceive of algorithms in the first place?
in my OP i gave an example from Numerical Recipes called dbrent which
involved a lot of if-else branches and assignments, which i wanted to
convert to functional form. the authors even give a description (which
i couldn't follow) of the original idea, but it seemed to include
destructive updating even in the original description. joe marshall
seemed to suggest that the original idea might be expressible without
destructive updating, but is this true for all ideas?
i'm hoping the answer is yes, because i love the idea that a compiler
could prove some invariant and eliminate assignments based on it,
creating faster code, especially if at the same time it makes clearer
code.
henry
"hank_rb" <·········@gmail.com> writes:
> pascal,
>
>>For example, let's start with the gcd algorithm:
>
> thanks for the demonstration of the GCD algorithm. it is clear that
> the algorithm can be expressed as is entirely in functional style, and
> that when it is expressed in procedural style, the original algorithm
> is somewhat obfuscated.
>
> my main question (or challenge) is: can you imagine an algorithm which,
> *in its original expression* contains destructive updating, and which
> cannot be restated more simply without that destructive updating?
> restated, even though math contains no destructive updating, not all
> algorithms are conceived entirely in terms of math. is this a fault of
> the algorithm, or is there an intrinsic need for destructive updating
> in original algorithms, or is that an accident of how procedural
> programmers conceive of algorithms in the first place?
An algorithm is a mathematical object. There's no destruction in maths.
Even the tape of a Turing machine is a serie of infinite vectors.
But some programs are not algorithms. For example, there are
heuristics, or reactive programs.
> in my OP i gave an example from Numerical Recipes called dbrent which
> involved a lot of if-else branches and assignments, which i wanted to
> convert to functional form. the authors even give a description (which
> i couldn't follow) of the original idea, but it seemed to include
> destructive updating even in the original description. joe marshall
> seemed to suggest that the original idea might be expressible without
> destructive updating, but is this true for all ideas?
The index of the series may be merely the number of instructions
executed up to now.
a=42 a_0 = 42 ; b_0 = indef
b=5550690 a_1 = a_0 = 42 ; b_1 = 5550690
a=b-a a_2 = b_1-a_1 = 5550648 ; b_2 = b_1 = 5550690
b=b-a a_3 = a_2 = 5550648 ; b_3 = b_2 - a_2 = 42
a=a+b a_4 = a_3+b_3 = 5550690 ; b_4 = b_2 = 42
...
So you can easily transform all the assignment into bindings:
(let ((a 42)
(b 5550690))
(let ((a (- b a)))
(let ((b (- b a)))
(let ((a (+ a b)))
...))))
Remains just to transform loops into recursive function calls. It
should be easy, the hard direction being the derecursivation.
> i'm hoping the answer is yes, because i love the idea that a compiler
> could prove some invariant and eliminate assignments based on it,
> creating faster code, especially if at the same time it makes clearer
> code.
Now, the question is, are all these imbricated LETs clearer?
--
"Specifications are for the weak and timid!"
>Now, imagine a language that has GCD and LCM and possibly some
>other functions as elementary instructions, but no basic
>arithmetic operations.
stefan and pascal,
very interesting. i've been thinking about this for several hours
now (some could call it procrastinating...) it seems to me that the
relationship between pure math and most computer languages is somewhat
complex.
pure math has of course no need for memory and no representation
problem, and this is mostly because no numeric computation is done in
pure math. computer algorithms *actually compute specific values*.
suppose we have these ideas in pure math:
f(x) := "the sum over i from 1 to x of i" (idea 1)
f(x) := "1 if x =1, x+f(x-1) otherwise" (idea 2)
f(x) := (x+1) * x/2 (idea 3)
suppose now that we wanted to compute f(1000).
idea 1 it seems to directly suggests destructive updating while
ideas 2 and 3 make it easy to *compute* f(1000) without destructive
updating.
yes, it's true that the original math idea doesn't require any
destruction or reassignment of the dummy variable i or any accumulator
variable. but that's only because the three definitions of f(x) are
not recipes for *computing* f(x). sure, they give us a very good idea
how to compute f(1000). but, idea 1 gives the idea of using
destructive updating. ideas 2 and 3 do not.
of course, this is already the famous example of replacing a for-loop
with looping recursion. but are there other, unlucky situations in
which *the original idea* suggests destructive updating? furthermore,
is this evidence that the original idea is just not stated as simply as
it could be without destructive updating, as idea 1 was not stated as
simply as idea 2?
or that functional and procedural paradigms are in fact complementary
in some cases? i'm hoping the answer is 'yes' and 'yes' :)
put another way, is it a prevailing viewpoint that the use of
destructive updating in an algorithm *always* indicates some sort of
flaw in the original concept?
thanks in advance,
henry
From: Joe Marshall
Subject: Re: branch and assignment statements translation to functional style
Date:
Message-ID: <d5mqukr8.fsf@alum.mit.edu>
"hank_rb" <·········@gmail.com> writes:
>>Now, imagine a language that has GCD and LCM and possibly some
>>other functions as elementary instructions, but no basic
>>arithmetic operations.
>
> stefan and pascal,
I wasn't mentioned, but I'm going to jump in anyway.
> very interesting. i've been thinking about this for several hours
> now (some could call it procrastinating...) it seems to me that the
> relationship between pure math and most computer languages is somewhat
> complex.
Yes. This is what Church, Turing, Godel, Tarski, Scott, etc. (just to
name a few) worked on for many years.
> pure math has of course no need for memory and no representation
> problem, and this is mostly because no numeric computation is done in
> pure math. computer algorithms *actually compute specific values*.
>
> suppose we have these ideas in pure math:
>
> f(x) := "the sum over i from 1 to x of i" (idea 1)
> f(x) := "1 if x =1, x+f(x-1) otherwise" (idea 2)
> f(x) := (x+1) * x/2 (idea 3)
>
> suppose now that we wanted to compute f(1000).
>
> idea 1 it seems to directly suggests destructive updating while
> ideas 2 and 3 make it easy to *compute* f(1000) without destructive
> updating.
None of these suggest destructive updating to me. Go figure.
> of course, this is already the famous example of replacing a for-loop
> with looping recursion. but are there other, unlucky situations in
> which *the original idea* suggests destructive updating?
There are, unfortunately, many algorithms that have been originally
expressed with `destructive updating'. It can be very hard to tease
out a simple recursive formulation of these.
> put another way, is it a prevailing viewpoint that the use of
> destructive updating in an algorithm *always* indicates some sort of
> flaw in the original concept?
I don't think so. As much of an aficionado of functional programming
as I am, I still think that there is a place for imperative
programming. An example that comes to mind is when you have to deal
with the real-world hardware that the computer is constructed from:
you can't just treat the CPU as an infinite time series.
But I have seen several expositions of imperative algorithms recast in
functional style. Almost always they are much shorter and clearer in
functional style. Almost always they are quite slow as well, but it
seems to be that the tweaks one uses to speed up functional programs
(memoization, partial-evaluation, laziness, parallelism) are rather
easy to add and often bring the performance of the functional version
near or even better than the imperative version.
>As much of an aficionado of functional programming
>as I am, I still think that there is a place for imperative
>programming.
>But I have seen several expositions of imperative algorithms recast in
>functional style. Almost always they are much shorter and clearer in
>functional style. Almost always they are quite slow as well, but it
>seems to be that the tweaks one uses to speed up functional programs
>(memoization, partial-evaluation, laziness, parallelism) are rather
>easy to add and often bring the performance of the functional version
>near or even better than the imperative version.
joe,
thanks for this and the papers. i've had a look at them, but not
studied them in any depth. regarding the above quoted text, my initial
foray into functional programming was from c++ to ocaml. it was
pointed out that in the 'great computer language shootout' ocaml
actually was comperable to the running speed of c++ but much more
concisely. unfortunately i saw that many of these were written using
ocaml's imperative features, which casts doubt on the whole idea.
so, i wonder whether the safety and clarity facilitated by functional
programming will be
fast enough for my purposes.
did you start out with procedural programming, and if so, what books or
resources have you found most useful to make the most of functional
programming? in particular, which of these titles would you recommend?
Functional Programming : Practice and Theory by Bruce J. Maclennan
The Functional Approach to Programming by Guy Cousineau, et al
Introduction to Functional Programming (2nd Edition) by Bird, Wadler
Introduction to Functional Programming Systems Using Haskell
Haskell: The Craft of Functional Programming (2nd Edition) by Simon
Thompson
Purely Functional Data Structures by Chris Okasaki
Algorithms : A Functional Programming Approach
Trends In Functional Programming by Stephen Gilmore
thanks in advance,
henry
"hank_rb" <·········@gmail.com> writes:
>>Now, imagine a language that has GCD and LCM and possibly some
>>other functions as elementary instructions, but no basic
>>arithmetic operations.
>
> stefan and pascal,
> very interesting. i've been thinking about this for several hours
> now (some could call it procrastinating...) it seems to me that the
> relationship between pure math and most computer languages is somewhat
> complex.
>
> pure math has of course no need for memory and no representation
> problem, and this is mostly because no numeric computation is done in
> pure math. computer algorithms *actually compute specific values*.
>
> suppose we have these ideas in pure math:
>
> f(x) := "the sum over i from 1 to x of i" (idea 1)
> f(x) := "1 if x =1, x+f(x-1) otherwise" (idea 2)
> f(x) := (x+1) * x/2 (idea 3)
>
> suppose now that we wanted to compute f(1000).
>
> idea 1 it seems to directly suggests destructive updating [...]
Perhaps. But you could look at it as: idea 1 tell us to write:
f(1000)=1+2+3+4+...+1000
and there's no i here.
> [...]
> or that functional and procedural paradigms are in fact complementary
> in some cases? i'm hoping the answer is 'yes' and 'yes' :)
yes and yes.
If only for they're both Turing complete, therefore equivalent.
> put another way, is it a prevailing viewpoint that the use of
> destructive updating in an algorithm *always* indicates some sort of
> flaw in the original concept?
"flaw" may be a big word.
One could say that an algorithm that uses destructive updating is
expressed in a lower-level language than a purely functionnal one.
Since most microprocessors are destructive, (as is their Turing
Machine model, but not Church's Lambda Calculus which is equivalent
and purely functional), an algorithm that uses destructive updating
might embed some "optimizations" more adapted to this kind of
processor, and these "optimizations" may obscure the essence of the
algorithm.
Note also that destructive updating (more exactly: non-reversible
updating) consumes most of the energy in the physical processors. You
can build faster and more energy efficient processors if you make them
reversible, ie "functional". The universe is more like Church's
Calculus than Turing's Machines. At least, it makes you pay less for
functional behavior ;-)
--
"Specifications are for the weak and timid!"
From: Joe Marshall
Subject: Re: branch and assignment statements translation to functional style
Date:
Message-ID: <8xxeuki7.fsf@alum.mit.edu>
Pascal Bourguignon <····@mouse-potato.com> writes:
> Note also that destructive updating (more exactly: non-reversible
> updating) consumes most of the energy in the physical processors.
This is a direct consequence of the second law of thermodynamics.
You could say that computation itself consumes no energy; it is the
act of *erasing* a previously computed value, like the contents of a
memory location, that requires energy and produces heat.
> You can build faster and more energy efficient processors if you
> make them reversible, ie "functional". The universe is more like
> Church's Calculus than Turing's Machines. At least, it makes you
> pay less for functional behavior ;-)
This is such a hack!
In the limiting case, a purely reversible computer can use an
arbitrarily small amount of energy.
···@zedat.fu-berlin.de (Stefan Ram) writes:
> ···@zedat.fu-berlin.de (Stefan Ram) writes:
>>Algorithms are not independent of the language.
>>A language (or machine) gives certain elementary instructions,
>>operations or features and a requirement (problem) requires
>>other instructions, operations or features.
>
> In a language with the basic arithmetic operations as
> elementary instructions, to find the GCD one might use
> Euclid's algorithm.
>
> Now, imagine a language that has GCD and LCM and possibly some
> other functions as elementary instructions, but no basic
> arithmetic operations. In this case, one would just call "GCD"
> to find the GCD, but one could not write Euclid's algorithm.
> Moreover, there would be a new landscape to be explored,
> because now one has to find the algorithm for the normal
> addition in terms of GCD, LCM and possibly some other
> functions.
Well, the only question is whether this language is Turing-complete or not.
--
"You question the worthiness of my code? I should kill you where you
stand!"
From: Joe Marshall
Subject: Re: branch and assignment statements translation to functional style
Date:
Message-ID: <oe6d14z9.fsf@alum.mit.edu>
"hank_rb" <·········@gmail.com> writes:
> more generally, i want to practice converting procedural algorithms
> into a purely functional style in order to understand them. maybe this
> isn't such a good idea?
It *can* be, but it is really hard to do in the general case.
Procedural algorithms are often so mangled that it is virtually
impossible to recognize the original idea that lead to them.
joe,
thanks. i am starting to see the idea. i suppose it makes sense
that this is the case, since if there were a set of simple conversion
rules, it wouldn't really be a paradigm.
henry
"hank_rb" <·········@gmail.com> writes:
> thanks. i am starting to see the idea. i suppose it makes sense
> that this is the case, since if there were a set of simple conversion
> rules, it wouldn't really be a paradigm.
What are you talking about?
If it's to post meaningless sentences you could avoid it at all.
--
__Pascal Bourguignon__ http://www.informatimago.com/
This is a signature virus. Add me to your signature and help me to live
pascal,
okay, i'll try to clarify. here's the original exchange:
henry:
> more generally, i want to practice converting procedural algorithms
> into a purely functional style in order to understand them. maybe this
> isn't such a good idea?
joe marshall:
>It *can* be, but it is really hard to do in the general case.
>Procedural algorithms are often so mangled that it is virtually
>impossible to recognize the original idea that lead to them.
henry:
> thanks. i am starting to see the idea. i suppose it makes sense
> that this is the case, since if there were a set of simple conversion
> rules, it wouldn't really be a paradigm.
pascal:
>What are you talking about?
I'll explain in a little more detail. I am trying to learn the main
ideas behind functional programming coming from a background of c++ and
perl, and no computer science formal training. i thought that it would
be good practice to try to convert some procedural programs into a
purely functional style. i had further hoped that there were a set of
'conversion rules' to do so. but, joe marshall suggests that sometimes
such a conversion is extremely difficult.
joe's statement "Procedural algorithms are often so mangled that it is
virtually
impossible to recognize the original idea that lead to them." was
interesting. 'the original idea' is an algorithm of course. i'm
interested in knowing whether a given idea is expressible in a
functional style, or intrinsically involves destructive updating? my
main goal now is to separate out the destructive updating that arose
out of the habit of converting original ideas into procedural code, and
that which was part of the original idea to begin with.
so i was remarking that, after all, it makes sense that there aren't a
set of simple rules to convert procedural to functional because if
there were, functional programming wouldn't be a new paradigm. the
idea of replacing for loops with looping recursion seemed like such a
rule, but it seemed to stop there.
in any case, i read through the haskell tutorial for C programmers,
suggested by stefan ram:
> For example, read this Haskell tutorial for C programmers:
>http://www.haskell.org/~pairwise/intro/intro.html
and, although it is quite informative, it seems that haskell, being a
purely functional language, would advocate that all ideas should be
expressible without destructive updating. the tutorial doesn't really
ponder the question of when to use one style or another (of course,
because haskell programmers have no choice)... but, since lisp and
ocaml allow both styles, i hoped to get a viewpoint on this question.
(i would post to the ocaml site, but they never respond...)
anyway, for the philosophically inclined, i would be eager to hear a
response. thanks for all the help so far.
henry
"hank_rb" <·········@gmail.com> writes:
> so i was remarking that, after all, it makes sense that there aren't a
> set of simple rules to convert procedural to functional because if
> there were, functional programming wouldn't be a new paradigm. the
> idea of replacing for loops with looping recursion seemed like such a
> rule, but it seemed to stop there.
Actually, there is a simple rule.
In math, there's no state. When you need state, you consider a serie.
v_0=initial_value
v_i+1=f(v_i)
Each serie in an algorithm correspond to a variable in a procedural
program.
Each value in a serie in an algorithm correspond to a binding in a
functional program.
For example, let's start with the gcd algorithm:
v_0 = x
u_0 = y
v_i+1 = if v_i>u_i then v_i-u_i else v_i
u_i+1 = if v_i<u_i then u_i-v_u else u_i
gcd(x,y)=v_k with k = mu i|v_i=u_i
= the smallest i such as v_i=u_i
As you can see, in a mathematical algorithm there's no assignment.
Now, when we implement this procedurally, with state variables, in
addition to the notion of variable we need to add that of loop and
that of control flow:
(defun gcd (x y)
(let ((v x)
(u y))
(loop :while (/= u v)
:do (if (< u v)
(setf v (- v u))
(setf u (- u v)))
:finally (return u))))
But when we implement it functionnaly, we just write directly the idea
of the mathematical algorithm:
(defun gcd (x y)
(labels ((serie (u v)
(cond
((= u v) u)
((< u v) (serie u (- v u)))
((> u v) (serie (- u v) v)))))
(serie x y)))
So the rule is to reconstitute the serie corresponding to each state
variable in the procedural program, and to write back the functional
form.
--
__Pascal Bourguignon__ http://www.informatimago.com/
There is no worse tyranny than to force a man to pay for what he does not
want merely because you think it would be good for him. -- Robert Heinlein
From: Joe Marshall
Subject: Re: branch and assignment statements translation to functional style
Date:
Message-ID: <oe6bwkaa.fsf@alum.mit.edu>
Pascal Bourguignon <····@mouse-potato.com> writes:
> "hank_rb" <·········@gmail.com> writes:
>> so i was remarking that, after all, it makes sense that there aren't a
>> set of simple rules to convert procedural to functional because if
>> there were, functional programming wouldn't be a new paradigm. the
>> idea of replacing for loops with looping recursion seemed like such a
>> rule, but it seemed to stop there.
>
>
> Actually, there is a simple rule.
>
> In math, there's no state. When you need state, you consider a serie.
[serie example elided]
While it is true that you can always just transform a problem this
way, I was thinking of the more difficult problem of finding a good
functional algorithm to replace the imperative one. There are a few
good papers on this:
http://www.csse.monash.edu.au/~lloyd/tildeStrings/Alignment/92.IPL.html
and
@article{ giegerich95comparison,
author = "Robert Giegerich and Stefan Kurtz",
title = "A Comparison of Imperative and Purely Functional Suffix Tree Constructions",
journal = "Science of Computer Programming",
volume = "25",
number = "2-3",
pages = "187-218",
year = "1995",
url = "citeseer.ist.psu.edu/giegerich95comparison.html" }
stefan,
thank you. i read the intro and it was very helpful. (unfortunately
comp.lang.functional doesn't seem to respond to my questions, so i've
since given up. you lisp guys are much more energetic!)
henry
"hank_rb" <·········@gmail.com> writes:
> has anyone tried to do this sort of 'procedural to functional'
> conversion exercise?
Ok, just for the fun, I just tried to convert your "procedure" to a
purely functional form.
Note that DEFUN, LET, LET*, MULTIPLE-VALUE-BIND and LABELS are all
syntactic sugar hiding the fundamental binding and function construct:
LAMBDA. So fundamentaly, we're just writting a bunch of functions
conditionnaly calling functions. LABELS hides some Y operators to
allow to call the functions recursively.
All "progress" is done with function calls. For example, a sequence
of assignments:
(setq a (max ax cx))
(setq v bx)
(setq e 0)
...
translate to:
( (lambda (a v e)
...)
(max ax cx) bx e )
that is, a call to a function taking as arguments named a v e
the expressions (max ax cx) bx e.
The same can be written more nicely as:
(let* ((a (max ax cx))
(v bx)
(e 0.0))
...)
but this is only a macro that generate the above function call for us.
And note how the recursive calls parallel a recursive definition for a
serie:
U_1 = f(itmax,U_0) = (U_0.fx,U_0.x) : (if (< itmax iter) (values fx x) ...)
U_itmax-i = f((i+1),U_itmax-(i+1)) : (iteration (1+ iter) ...)
(If I wasn't so lazy to find out what we're computing I could recover
a name more meaningful than "iteration" for the serie).
(defun dbrent (AX BX CX F DF TOL
&key (ITMAX 100) (ZEPS 1.0E-10))
(labels ((iteration (iter a b v w x e fx fv fw dx dv dw)
(if (< itmax iter)
(progn
(warn "DBREND exceeded maximum iterations.")
(values fx x)) ; dbrent & xmin
(let* ((XM (* 0.5 (+ A B)))
(TOL1 (+ (* TOL (ABS X)) ZEPS))
(TOL2 (* 2.0 TOL1)))
(cond
((<= (abs (- x xm)) (- tol2 (* 0.5 (- b a))))
(values fx x))
((> (abs e) tol1)
(let* ((D1 (if (/= dw dx)
(* (- W X) (/ DX (- DX DW)))
(* 2.0 (- B A))))
(d2 (if (/= dv dx)
(* (- v X) (/ DX (- DX Dv)))
(* 2.0 (- B A))))
(u1 (+ x d1))
(u2 (+ x d2))
(ok1 (and (> (* (- a u1) (- u1 b)) 0)
(<= (* dx d1) 0)))
(ok2 (and (> (* (- a u2) (- u2 b)) 0)
(<= (* dx d2) 0)))
(olde e))
(multiple-value-bind (d e)
(cond
((not (or ok1 ok2))
(if (>= dx 0)
(values (* 0.5 (- a x)) (- a x))
(values (* 0.5 (- b x)) (- b x))))
((and ok1 ok2)
(if (< (abs d1) (abs d2))
(values d1 d)
(values d2 d)))
(ok1 (values d1 d))
(t (values d2 d)))
(if (> (abs d) (abs (* 0.5 olde)))
(if (>= dx 0)
(part2 iter (* 0.5 (- a x)) (- a x)
a b v w x fx fv fw dx dv dw)
(part2 iter (* 0.5 (- b x)) (- b x)
a b v w x fx fv fw dx dv dw))
;;; I don't understand this:
;;; IF(U-A.LT.TOL2 .OR. B-U.LT.TOL2) D-SIGN(TOL1,XM-X)
;;; Has SIGN some side effects?
(let ((u (+ x d)))
(if (or (> (- u a) tol2)
(> (- b u) tol2))
(- d (sign (tol1 (- xm x))))) ; ???
(part2 iter d e
a b v w x fx fv fw dx dv dw))))))
(t
(if (>= dx 0)
(part2 iter (* 0.5 (- a x)) (- a x)
a b v w x fx fv fw dx dv dw)
(part2 iter (* 0.5 (- b x)) (- b x)
a b v w x fx fv fw dx dv dw)))))))
(part2 (iter d e a b v w x fx fv fw dx dv dw)
(let ((fu (aref f u)))
(cond
((>= (abs d) tol1)
(part2.1 iter (+ x d) fu
d e a b v w x fx fv fw dx dv dw))
((> fu fx)
(values fx x))
(t
(part2.1 iter (+ x (sign tol1 d)) fu
d e a b v w x fx fv fw dx dv dw)))))
(part2.1 (iter u fu d e a b v w x fx fv fw dx dv dw)
(let ((du (aref df u)))
(cond
((<= fu fx)
(iteration (1+ iter)
(if (>= u x) x a)
(if (>= u x) b x)
w x u e fu fw fx du dw dx))
((or (<= fu fw) (= w x))
(iteration (1+ iter)
(if (< u x) u a)
(if (< u x) b u)
w u x e fx fw fu dx dw du))
((or (<= fu fv) (= v x) (= v w))
(iteration (1+ iter)
(if (< u x) u a)
(if (< u x) b u)
u w x e fx fu fw dx du dw))
(t
(iteration (1+ iter)
(if (< u x) u a)
(if (< u x) b u)
v w x e fx fv fw dx dv dw))))))
(iteration 1
(MIN AX CX) (MAX AX CX)
bx v v 0.0
(aref f x) (aref f x) (aref f x)
(aref df x) (aref df x) (aref df x))))
(multiple-value-bind (dbrent-result xmin) (dbrent AX BX CX F DF TOL :itmax 200)
(print dbrent-result)
(print xmin))
> FUNCTION DBRENT(AX,BX,CX,F,DF,TOL,XMIN)
>
> PARAMETER (ITMAX=100,ZEPS=1.0E-10)
>
> LOGICAL OK1,OK2
> A=MIN(AX,CX)
> B=MAX(AX,CX)
> V=BX
> W=V
> X=V
> E=0.
> FX=F(X)
> FV=FX
> FW=FX
> DX=DF(X)
> DV=DX
> DW=DX
> DO ITER=1,ITMAX
> XM=0.5*(A+B)
> TOL1=TOL*ABS(X)+ZEPS
> TOL2=2.*TOL1
> IF(ABS(X-XM).LE.(TOL2-.5*(B-A))) GOTO 3
> IF(ABS(E).GT.TOL1) THEN
> D1=2.*(B-A)
> D2=D1
> IF(DW.NE.DX) D1=(W-X)*DX/(DX-DW)
> IF(DV.NE.DX) D2=(V-X)*DX/(DX-DV)
> U1=X+D1
> U2=X+D2
> OK1=((A-U1)*(U1-B).GT.0.).AND.(DX*D1.LE.0.)
> OK2=((A-U2)*(U2-B).GT.0.).AND.(DX*D2.LE.0.)
> OLDE=E
> E=D
> IF(.NOT.(OK1.OR.OK2))THEN
> GOTO 1
> ELSE IF (OK1.AND.OK2) THEN
> IF(ABS(D1).LT.ABS(D2)) THEN
> D=D1
> ELSE
> D=D2
> ENDIF
> ELSE IF (OK1) THEN
> D=D1
> ELSE
> D=D2
> ENDIF
> IF(ABS(D).GT.ABS(0.5*OLDE)) GOTO 1
> U=X+D
> IF(U-A.LT.TOL2 .OR. B-U.LT.TOL2) D-SIGN(TOL1,XM-X)
> GOTO 2
> ENDIF
> 1 IF(DX.GE.0.) THEN
> E=A-X
> ELSE
> E=B-X
> ENDIF
> D=0.5*E
> 2 IF(ABS(D).GE.TOL1) THEN
> U=X+D
> FU=F(U)
> ELSE
> U=X+SIGN(TOL1,D)
> FU=F(U)
> IF(FU.GT.FX) GOTO 3
> ENDIF
> DU=DF(U)
> IF(FU.LE.FX) THEN
> IF(U.GE.X) THEN
> A=X
> ELSE
> B=X
> ENDIF
> V=W
> FV=FW
> DV=DW
> W=X
> FW=FX
> DW=DX
> X=U
> FX=FU
> DX=DU
> ELSE
> IF(U.LT.X) THEN
> A=U
> ELSE
> B=U
> ENDIF
> IF(FU.LE.FW .OR. W.EQ.X) THEN
> V=W
> FV=FW
> DV=DW
> W=U
> FW=FU
> DW=DU
> ELSE IF(FU.LE.FV .OR. V.EQ.X .OR. V.EQ.W) THEN
> V=U
> FV=FU
> DV=DU
> ENDIF
> ENDIF
> CONTINUE
> PAUSE 'DBREND exceeded maximum iterations.'
> 3 XMIN=X
> DBRENT=FX
> RETURN
> END
>
--
__Pascal Bourguignon__ http://www.informatimago.com/