Quantcast

Maximum PC

It is currently Thu Apr 17, 2014 11:29 pm

All times are UTC - 8 hours




Post new topic Reply to topic  [ 10 posts ] 
Author Message
 Post subject: Imperative and functional programming example
PostPosted: Sun May 27, 2012 10:29 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
The following is based on the Haversine formula task on Rossetta Code. The Haversine formula is used to find the distance between two points on a sphere using latitudes and longitudes. Let's start with the imperative code; Below are the C and Java versions of the code.
Code:
//C version
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define R 6371
#define TO_RAD (3.1415926536 / 180)
double dist(double th1, double ph1, double th2, double ph2)
{
   double dx, dy, dz;
   ph1 -= ph2;
   ph1 *= TO_RAD, th1 *= TO_RAD, th2 *= TO_RAD;

   dz = sin(th1) - sin(th2);
   dx = cos(ph1) * cos(th1) - cos(th2);
   dy = sin(ph1) * cos(th1);
   return asin(sqrt(dx * dx + dy * dy + dz * dz) / 2) * 2 * R;
}

int main()
{
   double d = dist(36.12, -86.67, 33.94, -118.4);
   /* Americans don't know kilometers */
   printf("dist: %.1f km (%.1f mi.)\n", d, d / 1.609344);

   return 0;
}

//Java
public class Haversine {
    public static final double R = 6372.8; // In kilometers
    public static double haversine(double lat1, double lon1, double lat2, double lon2) {
        double dLat = Math.toRadians(lat2 - lat1);
        double dLon = Math.toRadians(lon2 - lon1);
        lat1 = Math.toRadians(lat1);
        lat2 = Math.toRadians(lat2);

        double a = Math.sin(dLat / 2) * Math.sin(dLat / 2) + Math.sin(dLon / 2) * Math.sin(dLon / 2) * Math.cos(lat1) * Math.cos(lat2);
        double c = 2 * Math.asin(Math.sqrt(a));
        return R * c;
    }
    public static void main(String[] args) {
        System.out.println(haversine(36.12, -86.67, 33.94, -118.40));
    }
}

If you haven't already, you should probably spend a minute looking at the formula on Wikipedia. It is pretty clear that the C and Java authors chose quite different approaches to implementing the details of the formula. If you removed the meta-info, many developers might not recognize that the functions perform the same calculation. However, I don't want to focus on the micro-details of the implementations. In both cases, the task is accomplished by a single function which converts individual parameters from degrees to radians. Both versions are pretty straight-forward implementations that I suspect a first year CS student could follow without much difficulty.

Let's take a look at the Haskell implementation.
Code:
--Haskell implementation
import Text.Printf

-- The haversine of an angle.
hsin t = let u = sin (t/2) in u*u

-- The distance between two points, given by latitude and longtitude, on a
-- circle.  The points are specified in radians.
distRad radius (lat1, lng1) (lat2, lng2) =
  let hlat = hsin (lat2 - lat1)
      hlng = hsin (lng2 - lng1)
      root = sqrt (hlat + cos lat1 * cos lat2 * hlng)
  in 2 * radius * asin (min 1.0 root)

-- The distance between two points, given by latitude and longtitude, on a
-- circle.  The points are specified in degrees.
distDeg radius p1 p2 = distRad radius (deg2rad p1) (deg2rad p2)
  where deg2rad (t, u) = (d2r t, d2r u)
        d2r t = t * pi / 180

-- The approximate distance, in kilometers, between two points on Earth.  The
-- latitude and longtitude are assumed to be in degrees.
earthDist = distDeg 6372.8

main = do
  let bna = (36.12,  -86.67)
      lax = (33.94, -118.40)
      dst = earthDist bna lax :: Double
  printf "The distance between BNA and LAX is about %0.f km.\n" dst

This author has implemented the task using more of a functional programming style. Even if you're unable to follow the actual details, you can clearly see the task broken into several functions: hsin, distRad, distDeg and deg2rad. Personally, I think this approach to implementing the task is much clearer. The bottom-up design approach has resulted in smaller, more orthogonal, functions that can easily be reused in other programming tasks.

Below, I've translated both the C and Haskell versions to Common Lisp. My hope is that seeing the different approaches side-by-side will help demonstrate the differences. Please note that I've made some minor changes that reflect 'Lisp style'.
Code:
;;A fairly straight-forward C to CL translation
;;instead of dx*dx, I squared using the expt function
(let ((R 6371)
      (TO_RAD (/ pi 180)))
  (defun dist (th1 ph1 th2 ph2)
    (setf ph1 (* (- ph1 ph2) TO_RAD)
     th1 (* th1 TO_RAD)
     th2 (* th2 TO_RAD))
    (let ((dx (- (* (cos ph1) (cos th1)) (cos th2)))
     (dy (* (sin ph1) (cos th1)))
     (dz (- (sin th1) (sin th2))))
      (* 2 R (asin (/ (sqrt (+ (expt dx 2) (expt dy 2) (expt dz 2))) 2))))))

;;A functional programming version of the program based on the Haskell code
(let ((earth-radius 6372.8)
      (rad-conv (/ pi 180)))
  (defun deg->rad (x) (* x rad-conv))
  (defun haversine (x) (expt (sin (/ x 2)) 2))
  (defun dist-rad (lat1 lng1 lat2 lng2)
    (let* ((hlat (haversine (- lat2 lat1)))
           (hlng (haversine (- lng2 lng1)))
           (root (sqrt (+ hlat (* (cos lat1) (cos lat2) hlng)))))
      (* 2 earth-radius (asin root))))
  (defun dist-deg (lat1 lng1 lat2 lng2)
    (apply #'dist-rad (mapcar #'deg->rad (list lat1 lng1 lat2 lng2)))))

CL-USER> (format t "The distance between BNA and LAX is about ~$ km.~%" (dist-deg 36.12 -86.67 33.94 -118.40))
The distance between BNA and LAX is about 2887.26 km.

Personally, I think that the functional programming approach is much better. Now, I do believe that the C version, for example, could be implemented in this style, but I don't think it would be as easy to follow the code. Perhaps someone else might want to try implementing it in this manner. I might spend some time tomorrow writing functional programming implementations in C# and Java using higher-order functions. Just for kicks, I might also implement the task in R.

For anyone wondering about the dist-deg function, I convert the args from degrees to radians using the mapcar functions, which returns a list, then use the apply function to call the dist-rad function. This is pretty straight-forward programming in Lisp, but I suspect it might not be something that a first year CS student would follow (outside of a top school).


Top
  Profile  
 
 Post subject: Re: Imperative and functional programming example
PostPosted: Sun May 27, 2012 11:17 pm 
Clawhammer
Clawhammer

Joined: Sun Jun 18, 2006 7:37 pm
Posts: 4545
Like any tool a person has, it depends on what you're doing. A functional language sounds like it's good for doing computational work, but not for say, controlling an embedded system where knowing the state of the system is very handy to figure out how to respond to something.


Top
  Profile  
 
 Post subject: Re: Imperative and functional programming example
PostPosted: Mon May 28, 2012 9:57 pm 
Team Member Top 50
Team Member Top 50

Joined: Sat Jun 25, 2005 11:04 am
Posts: 1026
Code:
//C version
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

const double PI = 3.1415926536;
double degToRad(double theta)
{
   return theta * PI / 180;
}

double haversin(double theta)
{
   return (1 - cos(theta)) / 2;
}

double distDeg(double lat1, double lon1, double lat2, double lon2, double r)
{
   lat1 = degToRad(lat1);   lat2 = degToRad(lat2);
   lon1 = degToRad(lon1);   lon2 = degToRad(lon2);
   return 2*r*asin(sqrt(haversin(lat2-lat1)+cos(lat1)*cos(lat2)*haversin(lon2-lon1)));
}

int main()
{
   double d = distDeg(36.12, -86.67, 33.94, -118.4, 6371.0);
   printf("dist: %.1f km (%.1f mi.)\n", d, d / 1.609344);

   return 0;
}


Top
  Profile  
 
 Post subject: Re: Imperative and functional programming example
PostPosted: Tue May 29, 2012 3:04 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
LatiosXT wrote:
Like any tool a person has, it depends on what you're doing. A functional language sounds like it's good for doing computational work, but not for say, controlling an embedded system where knowing the state of the system is very handy to figure out how to respond to something.

Perhaps you're not grasping this tool correctly? =)
(defun pun (intended) 'haha)

Personally, I believe there is quite a bit of empirical evidence suggesting that both functional programming style and FPLs are very well suited for many types embedded applications. A small sample:
1) Erlang was developed to run telephone switch software, which requires extremely high reliability and parallelism. To be fair, Erlang is more than just functional; For example, it was heavily influenced by Prolog, which is a logic programming language.
2) Guess what language your Roomba robot is running. Yep, Lisp.
3) The ICFP programming contest has had many contests which simulate what in the real-world would be an embedded environment.
4) Keep in mind that several of these functional programming languages have compilers which can emit C code partially for this very reason.
5) Certain ASIC/FPGA systems would seem to be well suited to functional programming, which tends to make concurrent programming much easier.

Did you have any specific examples in mind that you don't think would work well using a FPL?


Top
  Profile  
 
 Post subject: Re: Imperative and functional programming example
PostPosted: Tue May 29, 2012 3:14 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
mag wrote:
Code:
//C version
double distDeg(double lat1, double lon1, double lat2, double lon2, double r)
{
   lat1 = degToRad(lat1);   lat2 = degToRad(lat2);
   lon1 = degToRad(lon1);   lon2 = degToRad(lon2);
   return 2*r*asin(sqrt(haversin(lat2-lat1)+cos(lat1)*cos(lat2)*haversin(lon2-lon1)));
}

Why didn't you go ahead and implement separate functions for distDeg and distRad?
I noticed that you changed r, the radius of the earth, to a function parameter. This is probably a good idea if you're going to create a completely generic design, but the implementation should then include additional functions which don't require the user to constantly provide the earth's radius, which will be a huge source of errors in a real-world setting.


Top
  Profile  
 
 Post subject: Re: Imperative and functional programming example
PostPosted: Tue May 29, 2012 6:12 pm 
Clawhammer
Clawhammer

Joined: Sun Jun 18, 2006 7:37 pm
Posts: 4545
Aha...

Functional programming as a whole, is a good idea and in fact this is how I basically code my software, in C. At least, when programming at the actual application layer of the part. Which basically is once I get that done, porting code in theory is writing the drivers for the new board, which in our current schema of organization is one file.

Functional programming languages however, I don't seem to find appropriate for use in embedded applications that are very basic. Most of the stuff I work with has less than 16KB of RAM with very strict timing requirements (the last thing I had to work on must be ready in under a millisecond). Which down there, the only appropriate language (because nobody has yet made an optimized enough compiler, or nobody cares because of gcc) is C lest I go into assembly territory. Considering how high level FPL's look, I don't seem them useful in my line of work because I can see to support them, I need overhead which eats into my memory budget.


Top
  Profile  
 
 Post subject: Re: Imperative and functional programming example
PostPosted: Tue May 29, 2012 9:01 pm 
Team Member Top 50
Team Member Top 50

Joined: Sat Jun 25, 2005 11:04 am
Posts: 1026
Gadget wrote:
Why didn't you go ahead and implement separate functions for distDeg and distRad?

It was late and I was lazy.

Gadget wrote:
I noticed that you changed r, the radius of the earth, to a function parameter. This is probably a good idea if you're going to create a completely generic design, but the implementation should then include additional functions which don't require the user to constantly provide the earth's radius, which will be a huge source of errors in a real-world setting.

Agreed. Two other options are to use a default value (if the language supports it) or use a variable (like below).

Code:
//C version
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

double degToRad(double theta)
{
   const double PI = acos(-1);
   return theta * PI / 180;
}

double haversin(double theta)
{
   return (1 - cos(theta)) / 2;
}

double distRad(double lat1, double lon1, double lat2, double lon2, double r)
{
   return 2*r*asin(sqrt(haversin(lat2-lat1)+cos(lat1)*cos(lat2)*haversin(lon2-lon1)));
}

double distDeg(double lat1, double lon1, double lat2, double lon2, double r)
{
   return distRad(degToRad(lat1), degToRad(lon1), degToRad(lat2), degToRad(lon2), r);
}

int main()
{
   const double earthRad = 6371;
   double d = distDeg(36.12, -86.67, 33.94, -118.4, earthRad);
   printf("dist: %.1f km (%.1f mi.)\n", d, d / 1.609344);

   return 0;
}


Top
  Profile  
 
 Post subject: Re: Imperative and functional programming example
PostPosted: Wed May 30, 2012 1:31 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
LatiosXT wrote:
...the only appropriate language (because nobody has yet made an optimized enough compiler, or nobody cares because of gcc) is C lest I go into assembly territory.

I think that you came close to hitting the nail on the head with gcc. Many board manufacturers only provide a C based development environment for their products. I think this is largely due to the free nature of gcc and that a large number of teams use primarily C. However, there are other development environments available (including Basic which I always thought was strange). Having worked in a defense dept environment, I know that Ada has been used on a large number of embedded systems projects with very stringent timing and reliability constraints, and I doubt that Ada is more efficient than the average FPL. In a more ideal world, C wouldn't be the predominate choice due primarily to cost and ease of hiring constraints.

LatiosXT wrote:
Considering how high level FPL's look, I don't seem them useful in my line of work because I can see to support them, I need overhead which eats into my memory budget.

I suspect that a lot of the high level features available in FPLs actually compile into pretty efficient code. For example, (apply #'fn (list args)) should compile into nearly, if not exactly, the same object code as (fn args). If a language like C is able to gain additional efficiency, it probably has more to do with things like simpler data type systems and memory allocation. At least these are two things that Lisp programmers start doing manually when they need to squeeze more performance from a system.

Here is a link to a paper that compares Java, C++ and Lisp which Peter Norvig discusses on his website. Keep in mind this study was conducted in 1999, so Java programs have likely become much faster relative to CL and C++ since this was published. You'll find that languages like Lisp, on average, do use more memory. However, the benefits in average speed and development time seem to far exceeded the other two languages.


Top
  Profile  
 
 Post subject: Re: Imperative and functional programming example
PostPosted: Wed May 30, 2012 1:44 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
mag wrote:
Gadget wrote:
Why didn't you go ahead and implement separate functions for distDeg and distRad?

It was late and I was lazy.

I'll say... =)

mag wrote:
Agreed. Two other options are to use a default value (if the language supports it) or use a variable (like below).

Personally, I think that you should override the function or define it (in C). You're still asking for trouble by having someone use the wrong value. Default value support does make a lot of this copy/paste code unnecessary.
Code:
//...
double distRad(double lat1, double lon1, double lat2, double lon2, double r)
{
   return 2*r*asin(sqrt(haversin(lat2-lat1)+cos(lat1)*cos(lat2)*haversin(lon2-lon1)));
}
//I almost put the func defs in the wrong order... =)
double distRad(double lat1, double lon1, double lat2, double lon2)
{
   distRad(lat1,lon1,lat2,lon2,6371.0);
}
//...


Top
  Profile  
 
 Post subject: Re: Imperative and functional programming example
PostPosted: Tue Jun 05, 2012 4:22 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
One of the things that I didn't like about the original C code comes up quite frequently when working with mathematical formulas. Here is the original code...
Code:
//C version...
double dist(double th1, double ph1, double th2, double ph2) {  //shortened to save space...
   ph1 -= ph2;
   ph1 *= TO_RAD, th1 *= TO_RAD, th2 *= TO_RAD;
   double dz = sin(th1) - sin(th2), dx = cos(ph1) * cos(th1) - cos(th2), dy = sin(ph1) * cos(th1);
   return asin(sqrt(dx * dx + dy * dy + dz * dz) / 2) * 2 * R;
}
//CL Version...
(let ((R 6371)
      (TO_RAD (/ pi 180)))
  (defun dist (th1 ph1 th2 ph2)
    (setf ph1 (* (- ph1 ph2) TO_RAD)
     th1 (* th1 TO_RAD)
     th2 (* th2 TO_RAD))
    (let ((dx (- (* (cos ph1) (cos th1)) (cos th2)))
     (dy (* (sin ph1) (cos th1)))
     (dz (- (sin th1) (sin th2))))
      (* 2 R (asin (/ (sqrt (+ (expt dx 2) (expt dy 2) (expt dz 2))) 2))))))

Basically, I want to change this line... ph1 *= TO_RAD, th1 *= TO_RAD, th2 *= TO_RAD;
...because the *= is so repetitive, but keep in mind that I need to assign the values to ph1,th1 and th2 because the dx,dy,dz assignments don't follow a simple pattern (ie something like (mapcar #'deg->rad (list (- ph1 ph2) th1 th2)) won't work because it returns a list which would make the next section of code even uglier than the current section). In essence, the problem is that I have assignments which are easily 'vectorised' to borrow R lingo, but I don't want to use a vector or list in the next section. I come across this pattern all the time!

I really want to write something like... [ph1,th1,th2] *= TO_RAD ...which is Matlab inspired, but I can't do this in most programming languages. Even R, for example, despite otherwise good vector support/operations, doesn't support multiple variable assignment (although I did see a really kludgey user implementation) nor the *= operation (w/o using operator overloading). Of course, the *= TO_RAD operation is less clear than simply creating a function deg2rad and calling it with a vector, but I still lack the ability to do multiple variable assignment.

A few different approaches are possible in CL. One approach is to modify the original deg->rad function or create a second function, multiple-deg->rad, that accepts any number of arguments and returns multiple values. These individual values could then be bound using the multiple-value-bind form (see code below). I do like some aspects of this approach. It is easy to follow what is going on. However, I don't really like implementing a second function unless I'm sure that it will be useful in other applications (and I believe implementing the second function is a cleaner, more functional design approach).
Code:
CL-USER> (defun multiple-deg->rad (&rest args) (apply #'values (mapcar #'deg->rad args)))
CL-USER> (defun foo (th1 ph1 th2 ph2)
        (multiple-value-bind (ph1 th1 th2)
          (multiple-deg->rad (- ph1 ph2) th1 th2)
            (let ((dx (...))
                 ... )))

Another approach is to use the destructuring-bind form, which is a bit overkill and can handle far more complex destructuring cases, to pull apart and bind the values to the variables. This approach is even more straight-forward than the previous approach.
Code:
(let ((R 6371)
      (rad-conv (/ pi 180)))
  (defun deg->rad (x) (* x rad-conv))
  (defun dist (th1 ph1 th2 ph2)
    (destructuring-bind (ph1 th1 th2)             ;The values from the deg->rad call (below) 
   (mapcar #'deg->rad (list (- ph1 ph2) th1 th2)) ;are bound to ph1 th1 th1 (above)
    (let ((dx ...

A minor complaint would be having to manually place the args in a list [ie (list (- ph1 ph2) th1 th2)]. It also seems a bit less appealing than the *= version because I have to type the vars in the call and then again in the binding form. While a *= macro can be written to add this operator to the language easily enough [(defmacro *= (v expr) `(setf ,v (* ,v ,expr)))], I lose the original 'vectorised' approach that is more appealing. If I started to see this vector/binding pattern appear multiple times, I could write a macro that expands into the binding form above. I have done so here to keep my macro writing chops in practice more than anything else.
Code:
;;This is what I need the macro to expand into...
(destructuring-bind (ph1 th1 th2)
  (mapcar #'deg->rad (list ph1 th1 th2)) ;The original ph1 - ph2 will need to be done prior to the macro call

;;If you haven't done this type of programming before, be careful, it can FRY YOUR BRAIN!  =)
;;This macro binds to args the value returned by the function fn
(defmacro bind-args ((fn &rest args) &body body)
  `(destructuring-bind (,@args) (mapcar ,fn (list ,@args))
    ,@body))

;;A sample expansion... notice that BIND-ARGS expands into the code that we wanted
CL-USER> (setf ph1 0 th1 1 th2 2)
2
CL-USER> (macroexpand-1 '(bind-args (#'deg->rad ph1 th1 th2)
           (values ph1 th1 th2)))
(DESTRUCTURING-BIND (PH1 TH1 TH2) (MAPCAR #'DEG->RAD (LIST PH1 TH1 TH2))
  (VALUES PH1 TH1 TH2))  ;Just a sample body... the dx dy dz code would go here now

;;Test output...
CL-USER> (bind-args (#'deg->rad ph1 th1 th2)
          (values ph1 th1 th2))
0.0L0
0.017453292519943295769L0
0.034906585039886591538L0
CL-USER>


* I could have written the macro so that (decf ph1 ph2) could appear in the macro call, but it would complicate the macro code quite a bit and probably make it impossible for someone not familiar with this type of programming to follow, so I elected for the simpler version here.


Top
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 10 posts ] 

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group