Enough BS - Any functional programmer that could tell me ...
Eugene Dragoev
http://www.haskell.org/aboutHaskell.html
Is this the best and shortest code for quick C sort?
I am very interested in exploring FP (especially Erlang) but examples
like this one are not very convincing.
Is there any real use of functional languages aside from the Ericsson's
ATM switch, Emacs and AutoLisp.
Could Erlang be useful for medium size projects? What would be the
benefits of using Erlang in distributed programs vs Corba.
Give me some good arguments - I am willing to listen.
Eugene
==========================
Quicksort in Haskell
qsort [] = []
qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
where
elts_lt_x = [y | y <- xs, y < x]
elts_greq_x = [y | y <- xs, y >= x]
Quicksort in C
qsort( a, lo, hi ) int a[], hi, lo;
{
int h, l, p, t;
if (lo < hi) {
l = lo;
h = hi;
p = a[hi];
do {
while (l < h) & (a[i] <= p) do
l = l+1;
while (h > l) & (a[h] >= p) do
h = h-1;
if (l < h) {
t = a[l];
a[l] = a[h];
a[h] = t;
} while (l < h);
t = a[l];
a[l] = a[hi];
a[hi] = t;
qsort( a, lo, l-1 );
qsort( a, l+1, hi );
}
}
Jerzy Karczmarczuk
>
> How many errors are there in the C program that is shown in:
>
> http://www.haskell.org/aboutHaskell.html
>
> Is this the best and shortest code for quick C sort?
Mmmmmm!
Yes, whoever wrote this page "based on a paper by SPJ" should
correct it, when I tried to advertize Haskell to some of my colleagues,
they laughed, and made some acrimonious remarks about the "C"
knowledge of the author. Bad while syntax, confusion between & and &&,
l replaced by unknown i, unclosed "if" block...
But after corrections it works. This is one of the shortest, but
*NOT THE BEST* quicksort code. (I suspect it is the code you might
find in Sedgewick book on algorithms). Too many comparisons, and no
protection against the worst case. And of course restricted to int
arrays, and the recursion is too deep.
But, what is worse, comparing a random-access-array algorithm with a
list-processing procedure is methodologically almost meaningless,
unless everything is *very well* commented. I would even say that it
is harmful.
==
> Is there any real use of functional languages aside from the Ericsson's
> ATM switch, Emacs and AutoLisp.
I *love* the term "real use"...
Suppose that terabytes of pedagogical examples might be qualified as
"unreal"...
The image processing package GIMP is scripted in Scheme, Schemers INC.
sell a 3d modelling package written in Scheme, Guile is progressing,
several applications written in Elk may be found, there is a nice
project
named Curl: a Web navigator which formats dynamic, animated pages,
and where HTML is replaced by a Scheme-like language (tough; tagging
and scripting put together makes it even less readable than the code in
TeX...)
You won't wait long for the first serious applications of H/Direct. (Now
CAML people are working on similar things as well).
Clean people - apparently - made (and perhaps even sold) some
interesting
applications in Clean.
Well, I am not competent at all to give good answers to such questions,
but such worries, some other doubts raised here about monads, etc.
remind me a little one conference on geometrical methods in technical
sciences, where one Top Fellow kept asking several times the same
question: "How much money was produced last year by fibre bundles
or differential forms?"
Jerzy Karczmarczuk
Caen, France.
Ooops, I almost forgot to include my Highly Ideologic .sig file. Here
you are the current version
+++++++++++++++++++++++++++++++++++++++++++++
+ Confucius might have said: +
+ "It should be obvious for all of you, +
+ that what is obvious for some +
+ need not be obvious for the others" +
+++++++++++++++++++++++++++++++++++++++++++++
Andrew Koenig
Eugene Dragoev <eug...@istar.ca> wrote:
> How many errors are there in the C program that is shown in:
> http://www.haskell.org/aboutHaskell.html
> Is this the best and shortest code for quick C sort?
An observation that might be more interesting is that the
Haskell version of quicksort is terrible! The trouble is that
it uses the first element as its pivot, which means that if
you give it a list that is already sorted, it will run in
quadratic time.
--
Andrew Koenig
a...@research.att.com
http://www.research.att.com/info/ark
Adam P. Jenkins
http://www.cs.bell-labs.com/~wadler/realworld/
Also, wasn't one of the major web search engines written in Lisp?
Also though, if you're seriously interested in examining functional
programming, I think it's silly to judge it solely on how popular it
has become. By that criterion, MS Windows is the best OS in the
world. Obviously other factors contribute to popularity than
technical superiority. So, really you should read up on functional
programming, and then try writing some programs applying the
functional paradigm. That will give you a better feel for its
potential than just looking for usage statistics.
Adam
Eugene Dragoev <eug...@istar.ca> writes:
> How many errors are there in the C program that is shown in:
>
> http://www.haskell.org/aboutHaskell.html
>
> Is this the best and shortest code for quick C sort?
>
> I am very interested in exploring FP (especially Erlang) but examples
> like this one are not very convincing.
>
> Is there any real use of functional languages aside from the Ericsson's
> ATM switch, Emacs and AutoLisp.
>
> Could Erlang be useful for medium size projects? What would be the
> benefits of using Erlang in distributed programs vs Corba.
>
> Give me some good arguments - I am willing to listen.
--
Adam P. Jenkins
ajen...@netway.com
Adam P. Jenkins
> In article <370464C4...@istar.ca>,
>
> Eugene Dragoev <eug...@istar.ca> wrote:
>
> > http://www.haskell.org/aboutHaskell.html
>
> > Is this the best and shortest code for quick C sort?
>
> Haskell version of quicksort is terrible! The trouble is that
> it uses the first element as its pivot, which means that if
> you give it a list that is already sorted, it will run in
> quadratic time.
The C version has the same problem, only it picks the last element as
the pivot instead of the first. So in this regard it's a fair
comparison. Still though, this is comparing sorting a list in
haskell with sorting an array in C so it's not really the same thing.
Craig Dickson
>Still though, this is comparing sorting a list in
>haskell with sorting an array in C so it's not really the same thing.
Well, consider that C lacks a primitive data type for lists. It isn't
uncommon in C to dynamically allocate an array, fill in the data, and then
sort it; in fact, the standard C library's quicksort routine requires that
the data to be sorted be in an array (or referenceable from an array of
pointers, depending how you write the comparator function). In Haskell, one
often uses lists for things that might be done with arrays in C. Because of
this, I'd say it's fair to the natural idioms of both languages to compare
a C array sort to a Haskell list sort.
It is much more disturbing that both the C and Haskell examples given were
so dreadful.
Craig
Eugene Dragoev
I am trying to learn Erlang and I don't think MS Windows is the best OS - I
use FreeBSD 25% of the time.
But FL advocates should provide better examples that show the advantages of
FL.
I am interested in Erlang since this language looks like a good complement to
Java in certain systems.
I would love to hear about some test that compare the performance of Erlang
to that of Java in an area that Erlang is supposed to be "fast". Web Servers
for example.
Regards,
Eugene
pat...@c837917-a.potlnd1.or.home.com
: I would love to hear about some test that compare the performance of Erlang
: to that of Java in an area that Erlang is supposed to be "fast". Web Servers
: for example.
I do not have a reference, but somewhere on the net there is a
comparison of Java and Erlang. One of the claims, IIRC, is that Erlang
processes and its garbage collector are in some ways more efficient
than Java threads and its GC. One reason supporting this is that
Erlang uses a GC per process while Java has a single GC that collects
all threads. Anther reason could be that Erlang potentially has lower
synchronization requirements since there are more limits on how shared
data can be modified concurrently.
Of course the theory also depends on the specific implementations. I
have no real evidence comparing any two implementations.
Another aspect of this debate is that it does not necessarily matter
how fast Erlang is compared to anything else so long as Erlang is fast
enough to meet the requirements of the applications that are
implemented in Erlang. I am more interested in this point than in any
general comparisons.
--
Patrick D. Logan mailto:patric...@home.com
"I have a mind like a steel... uh... thingy."
George Russell
>Is there any real use of functional languages aside from the
>Ericsson's ATM switch, Emacs and AutoLisp.
(http://www.netmeg.net/faq/science/math/numerical-analysis/faq/)
devotes most of its section on Fast Fourier Transform code
to FFTW, the so-called Fastest Fourier Transform in the West.
While the code you download for this is in C, according to the paper
on FFTWs home page "A Fast Fourier Transform Compiler",
the code in FFTWs inner loop (and 95% of the total code) is
automatically generated by an Objective CAML program, genfft,
which spots special cases.
Claes Wikstrom
Eugene Dragoev <eug...@istar.ca> writes:
> Could Erlang be useful for medium size projects? What would be the
> benefits of using Erlang in distributed programs vs Corba.
>
> Give me some good arguments - I am willing to listen.
I would say that the main difference between designing an distributed
application in Erlang as opposed to a corba solution is the lack
of interface descriptions in the erlang case.
The good thing about this is that It is much easier to change the
application, that is, it is easier to use rapid prototyping since
if we need to pick up a data structure or read some data at a remote
computer we just call a function to do it. In the case of Corba we have
to go back to our interface description and possibly rethink the interfaces
of one or several objects, add that to out IDL description, recompile the
IDL's, relink the applications with the newly generated stug functions ...
The bad thing about this is that all the Object people don't get any
nice pictures with clouds having interfaces to draw on the whiteboards.
Interfaces are good in order to understand a system, however it is
a pain to have to explicitly define *all* interfaces at compile time.
/klacke
Matteo Frigo
> Eugene Dragoev wrote:
> While the code you download for this is in C, according to the paper
> on FFTWs home page "A Fast Fourier Transform Compiler",
> the code in FFTWs inner loop (and 95% of the total code) is
> automatically generated by an Objective CAML program, genfft,
> which spots special cases.
[I am the author of the paper.]
Hi. I just want to remark that genfft is distributed with FFTW (see
http://theory.lcs.mit.edu/~fftw)---this fact is not clear from your
post.
It is true that FFTW is distributed with generated C code that covers
Fourier transforms of the most commonly used sizes (multiples of small
primes such as 2, 3, 5, 7, 11, and 13). In the past, however, some
users of FFTW needed transforms of special sizes, and were able to run
genfft themselves to generate code for their needs. For example, one
user needed a real (as opposed to complex) Fourier transform of size
513 = 19 * 27 for image processing, and he generated the code he
needed.
Incidentally, genfft is almost completely functional (i.e.,
side-effect free). It uses side-effects for storing the command-line
arguments and other minor things like that. The bulk of the code is
written in monadic style.
Regards,
Matteo Frigo
Torbjorn Tornkvist
> Is there any real use of functional languages aside from the Ericsson's
> ATM switch, Emacs and AutoLisp.
At last years CEBIT fair, Ericsson had about 7 different
products developed in Erlang (I've got no idea what
the status was this year though...).
> Could Erlang be useful for medium size projects?
Yes, Erlang could be very useful indeed. Of course it
depends on what you want to do, but Erlang is very
mature and stable; so from that point of view it would
not give you any troubles.
> What would be the
> benefits of using Erlang in distributed programs vs Corba.
Not quite sure what benefits you would get from using Corba.
The Erlang distribution is in itself very powerful which has
been exploited in at least one Ericsson product (where Erlang
is running on a cluster of up to 70 Win-NT boxes). However,
I know that one (big) Ericsson product is making heavy use of
the Erlang-Corba support where they use IDL to specify all the
interfaces between the various system components.
Cheers /Tobbe
Wolfgang Grieskamp
> The good thing about this is that It is much easier to change the
> application, that is, it is easier to use rapid prototyping since
> if we need to pick up a data structure or read some data at a remote
> computer we just call a function to do it. In the case of Corba we have
> to go back to our interface description and possibly rethink the interfaces
> of one or several objects, add that to out IDL description, recompile the
> IDL's, relink the applications with the newly generated stug functions ...
I think you are right, but this hasn't to do with the benefits of FP
(Erlang or whatsover). Corba/IDL adds complexity through its
multi-lingual setting. The simplicity of a mono-lingual universal
framework has been supported by non-functional languages for a long
time (recently Java, formerly Smalltalk, LISP, ...). The advantages of
modern FP are not originally located here.
Regards
Wolfgang
Ulf Wiger
Hmm,
I meant to post this yesterday, but it went out as a mail reply
instead. I'll give it another try:
>>>>> "Eugene" == Eugene Dragoev <eug...@istar.ca> writes:
Eugene> Could Erlang be useful for medium size projects?
Yes! Erlang is great for small-to-medium size projects. What was not
quite as obvious, but has been demonstrated in practice is that
Erlang is also great for large projects.
The main reason, I think, why Erlang works well in large projects,
is that lead times are greatly reduced (compared to traditional 3GL
approaches). It is easy to write stubs, simulators, prototypes, and
test rigs. This means that developer teams can work against real
APIs instead of developing against vaporware, which often happens
in large C++ projects (you specify interfaces first so that other
teams will have something to work against, then you try to implement
them while other teams write code against your specs.)
Also, since Erlang lends itself well to iterative and/or incremental
development, you can run development with better control of timelines
(you get something working quickly, and then watch it mature.)
BTW, my take on project sizes:
small: 1-5 programmers
medium: 10-20 -"-
large: 30-100 -"-
bloated: 100+
Eugene> Could Erlang be useful for medium size projects? What would
Eugene> be the benefits of using Erlang in distributed programs vs
Eugene> Corba.
Erlang vs. Corba:
----------------
To begin with, there is a Corba component for Erlang. It is quite
good, but you won't find many Erlang programmers who opt for Corba
instead of native Erlang when they develop distributed programs.
There are many reasons for this:
- Erlang is dynamically typed, so there is no need for interface
stubs. This makes it extremely convenient to write distributed
software.
- Erlang has built-in monitoring functions, such as processs links,
and node supervision. These work perfectly in a distributed
environment, and are fully integrated into the language.
- The Erlang middleware OTP (Open Telecom Platform) has built-in
support for distribution of applications.
I believe the main benefit of Corba is that you can specify
language-independent interfaces. If you don't know what's going to
be sitting on the other side of an interface, Corba is great. If
you know that it's going to be Erlang-to-Erlang communication,
using native Erlang distribution gives you better control, less
specification overhead, more flexibility, and better performance
than Corba.
--
Ulf Wiger, Chief Designer AXD 301
Ericsson Telecom AB tfn: +46 8 719 81 95
Varuvägen 9, Älvsjö mob: +46 70 519 81 95
S-126 25 Stockholm, Sweden fax: +46 8 719 43 44
Mark Naumann
>
> The main reason, I think, why Erlang works well in large projects,
> is that lead times are greatly reduced (compared to traditional 3GL
> approaches). It is easy to write stubs, simulators, prototypes, and
> test rigs. This means that developer teams can work against real
> APIs instead of developing against vaporware, which often happens
> in large C++ projects (you specify interfaces first so that other
> teams will have something to work against, then you try to implement
> them while other teams write code against your specs.)
>
> Also, since Erlang lends itself well to iterative and/or incremental
> development, you can run development with better control of timelines
> (you get something working quickly, and then watch it mature.)
I'm missing something... This argument can be used for any language. Define
the interfaces first, write stubs, add more complete behavior over time. This
is done all the time when writing operating system drivers for new chips.
The functional vs imperitive argument that makes most sense to me is that, for
a given problem, there are (probably) fewer lines of code in a functional
language and there are no control flow statements (Haskell vs C), so
programmer productivity *should be* higher. What I fail to understand is the
performance implications of using a functional language. (e.g. Random
insertion deletion of an element from a finite list and having no-side effects
seems like a very big penalty. How would one do this in a functional
language, or are there functional programming design rules that guide the
programmer down a different path toward a different type of very efficient
solution.)
When is the right time to use a functional language, when is the right time to
use C? From what I've read, an operating system would not be written in
Haskell, it would be too slow. But some application programs are excellent
candidates for a functional language. What is the criteria used to answer the
"which language for this problem?" question and coming up with "a functional
language!"
Since a functional language provides a higher level abstraction, the
programmer has less control over the performance of the final result. If we
consider C/C++ to be a high-level assembly language, the programmer must know
about memory management, CPU architecture, etc to get good performance. The
programmer has explicit control over things that affect performance. A C
programmer can write functionally correct code that has very good or very poor
performance, depending on the algorithms used. The algorithms are well
studied, and if the programmer knows what the data looks like and how it is
used, he can select the "right" algorithm. He might even change algorithms on
the fly, based on run-time monitoring.
But in a functional language, are there documented design rules for writing
high performance applications? Where can functional programmers look to learn
about this aspect?
Mark
Ketil Z Malde
> What I fail to understand is the performance implications of using a
> functional language. (e.g. Random insertion deletion of an element
> from a finite list and having no-side effects seems like a very big
> penalty.
Yep, in principle. What you do is cross your fingers and hope the
compiler is smart enough to figure out that it can do destructive
updates. An advantage to Haskell et al. is - allegedly - that
compilers more easily can do subtle tricks of optimization. Side
effects can be very harmful to modern CPUs, or so I'm told.
> When is the right time to use a functional language, when is the
> right time to use C? From what I've read, an operating system would
> not be written in Haskell, it would be too slow.
I would not be so bombastic. All right, I am at best a dabbler and
dilletante when it comes to FP, but my feeling is that using FP gives
me a better overview and focuses on the algorithms, rather than on
microoptimization. C++ programmers can worry about the overhead of
virtual functions all they like, but if that means they're overlooking
a superior algorithm (say O(n log n) instead of O(n^2)) solution, all
the tweaking and compliler switches in the world isn't going to help
them.
-kzm
--
If I haven't seen further, it is by standing in the footprints of giants
Graham Matthews
> What I fail to understand is the performance implications of using a
> functional language. (e.g. Random insertion deletion of an element
> from a finite list and having no-side effects seems like a very big
> penalty.
: An advantage to Haskell et al. is - allegedly - that
: compilers more easily can do subtle tricks of optimization. Side
: effects can be very harmful to modern CPUs, or so I'm told.
Yep that's the theory. But what's the practice, the reality?
Ketil Z Malde (ke...@ii.uib.no) wrote:
: but my feeling is that using FP gives
: me a better overview and focuses on the algorithms, rather than on
: microoptimization. C++ programmers can worry about the overhead of
: virtual functions all they like, but if that means they're overlooking
: a superior algorithm (say O(n log n) instead of O(n^2)) solution, all
: the tweaking and compliler switches in the world isn't going to help
: them.
Again that's the theory (that FP languages let you concentrate on the
algorithm rather than micro-optimisations). But what is the practice,
the reality? My experience with C is that although I could micro-optimise
things, I often didn't, and instead spent my time looking for better
algorithms.
graham
--
As you grow up and leave the playground
where you kissed your prince and found your frog
Remember the jester that showed you tears
the script for tears
Craig Brozefsky
> Ketil Z Malde (ke...@ii.uib.no) wrote:
> : An advantage to Haskell et al. is - allegedly - that
> : compilers more easily can do subtle tricks of optimization. Side
> : effects can be very harmful to modern CPUs, or so I'm told.
>
> Yep that's the theory. But what's the practice, the reality?
Depends on what implementation you are using. The Ocaml
implementation seems fine to me, although I am not schooled in all of
it's details. It is also not a pure functional language.
CMUCL has a nice compiler, Python, which is at least 10 years old I
think, and optimizes very well. With type declarations it can
produce floating point code as fast or faster than C in many
situations. It is actively maintained.
Stalin is a scheme compiler which I beleive does some advances static
analysis. I know that it produces very fast code in many situations.
So it's definetly in practice that functional languages come with some
advanced omptimizing compilers.
--
Craig Brozefsky <cr...@red-bean.com>
Less matter, more form! - Bruno Schulz
ignazz, I am truly korrupted by yore sinful tzourceware. -jb
Ketil Z Malde
> : An advantage to Haskell et al. is - allegedly - that
> : compilers more easily can do subtle tricks of optimization. Side
> : effects can be very harmful to modern CPUs, or so I'm told.
> Yep that's the theory. But what's the practice, the reality?
I don't write compilers, so I don't know first hand. Of course, C
and Fortran compilers do a lot of fancy stuff too, but comparing a
Haskell compiler from a handful of guys at some university to a C
compiler which usually has lots of man years put into it, and which is
considered one of the most important system parts by just about
everybody, from the chip maker to the OS designers - well, that might
not be entirely fair. That e.g. Haskell or OCAML achieve C-like
performance is very impressive, and as I understand, they do in quite
a few cases.
> Again that's the theory (that FP languages let you concentrate on the
> algorithm rather than micro-optimisations).
It may be the theory, but I was talking from (although limited)
experience.
Ulf Wiger
Mark> I'm missing something... This argument can be used for any
Mark> language. Define the interfaces first, write stubs, add more
Mark> complete behavior over time. This is done all the time when
Mark> writing operating system drivers for new chips.
Yes, there aren't that many different ways of going about writing
good software. The point is that Erlang *promotes* this way of working.
Certainly, good C++ programmers do basically the same thing, but only
after learning the hard way that you can't write software the way
C++ inspires you to in the beginning.
Mark> What I fail to understand is
Mark> the performance implications of using a functional
Mark> language. (e.g. Random insertion deletion of an element from a
Mark> finite list and having no-side effects seems like a very big
Mark> penalty. How would one do this in a functional language, or
Mark> are there functional programming design rules that guide the
Mark> programmer down a different path toward a different type of
Mark> very efficient solution.)
There is no general answer to that question. You have to pick a class
of applications, then compare specific language implementations.
If you want to develop a telecom or datacom switch, Erlang is great;
if you're programming fourier transforms, I wouldn't suggest Erlang.
Mark> Since a functional language provides a higher level
Mark> abstraction, the programmer has less control over the
Mark> performance of the final result.
Not necessarily true. If the application is very complex, you won't
be able to control performance with a low-level language, because
you can't handle the complexity.
A language which raises the abstraction level may actually help
you with performance.
Mark> But in a functional language, are there documented design
Mark> rules for writing high performance applications?
Absolutely! You must have performance design rules regardless of
which language you choose.
/Uffe
Mark Naumann
Do you know of any specific URLs or publication references?
Mark