Maximum PC

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.

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.

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'.

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).

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?

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.

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.

It was late and I was lazy.


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

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.


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.

I'll say... =)


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.

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...

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).

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.

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.


* 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.