Re: Function vs. Procedure

*To*: mathgroup at smc.vnet.net*Subject*: [mg37128] Re: [mg37114] Function vs. Procedure*From*: Sseziwa Mukasa <mukasa at jeol.com>*Date*: Sat, 12 Oct 2002 05:04:53 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

On Thursday, October 10, 2002, at 03:20 AM, Steven wrote: > Is there a logically fundamental difference between functional and > procedural programming? What I mean to ask is, can we do exactly the > same > thing with purely functional approaches as we can with purely > procedural > approaches? > There is a fundamental difference, a strictly functional language does not allow destructive assignments to be performed. From this statement alone then it is obvious that there are some things that can be done in a procedural (nowadays people prefer to call them imperative) language that cannot be done in a functional language. On the other hand in imperative languages without pointers to procedures on cannot define a function which takes another function as an argument which functional languages allow. What you are probably really interested in is whether there exist a class of programs in the sense of a transformation on some input set into an output set which can be expressed in only one paradigm. Because nearly all major programming languages (SQL being the glaring exception) can implement a Turing Machine any algorithm which can be performed by a Turing Machine can be performed by any programming language, imperative or functional. So in principle functional and imperative languages are equivalently powerful although in practice it is easier to express some concepts in one paradigm or another. > Is this basically the recursive verses iterative distinction? > No. > Why would one chose one approach over the other? > In software engineering circles there is some evidence that the functional programming paradigm allows for efficient implementation of large programming projects, see http://www.math.chalmers.se/~rjmh/Papers/whyfp.html. Also it is possible to prove a strictly functional program correct because it cannot have side effects (no destructive updates of global states) which caused some excitement in academia but has not been a big selling point in industry. That said, by now you must realize that Mathematica is not a strictly functional language although you can use it as such. Actually Mathematica has a lot in common with LISP which is sometimes lumped together with the functional languages since it admits that programming style but both Mathematica and LISP are not pure (the desirability of purity being left to personal preference). One last advantage of functional programs though (which is related to the fact that they admit correctness proofs) is that it is relatively easy for a compiler/interpreter to optimize a functional program. This is why implicit iteration (Map in Mathematica) tends to outperform imperative style loops (Do, For, While etc.), which have to do a destructive update of the loop counter variable and therefore cannot reorganize a loop since statements in the loop may also destructively update the loop counter. C et al. get around this problem by being closely matched to the hardware. Regards, Ssezi