Is the Functional Paradigm suitable for Math Heavy problems?
Shinji Ikari
languages for implementing solutions to problems heavy in mathematics.
Obviously you can produce solutions in any turing-complete language,
but I am wondering if functional languages are any more, or less,
suitable than, say, the OO or imperative paradigms. What are people
experiences in this area?
Thanks.
Feuer
Functional languages are quite good for mathematics. However, they
will likely not perform as well as Fortran in the most performance-
critical applications.
David
Joachim Durchholz
> I am wondering what people think of the suitability of functional
> languages for implementing solutions to problems heavy in
> mathematics.
It depends on whether you're doing symbolic or numeric mathematics.
These are entirely different application areas.
Regards,
Jo
Darius
This is where someone says Sisal.
Albert Lai
> I am wondering what people think of the suitability of functional
> languages for implementing solutions to problems heavy in mathematics.
Here is a problem heavy in mathematics: Given an industrial (like,
Intel) numerical algorithm running on a known floating point format
and precision, how do you prove, without boring yourself to death,
that it attains a certain accuracy? (And the aforementioned company
does want a rigorous and formal proof because it is not going to let
yet another floating-point embarrasment happen.)
Here is a solution: develop a real number theory and a floating point
theory in a theorem checker/prover such as HOL Lite, and furthermore
develop decision procedures for some of the boring or recurring
questions in these theories; then write your proofs in this
environment. See John Harrison's home page at
http://www.cl.cam.ac.uk/users/jrh/
Many suitable theorem checkers/provers like HOL Lite are implemented
in functional languages; they furthermore allow you to develop your
own theories and decision procedures in the same functional languages.
That is what I call good mathematics done with good computing.
Mathematics != Number crunching
Shinji Ikari
> This is where someone says Sisal.
I found some mention of Sisal on the web, but unfortunately it appears
dead. It seemed to have a brief second-life life on Sourceforge but
still appears terminal. It looked very promising though.
Shinji Ikari
Thanks David. I was less concerned about performance and more
interested in the effectiveness of describing mathematical problems
using a language.
Daniel C. Wang
{stuff deleted}
> Thanks David. I was less concerned about performance and more
> interested in the effectiveness of describing mathematical problems
> using a language.
What is wrong with Matlab or Mathematica then? Good libraries and a big
user community will probably trump any benefits with respect to
languages. Is this a specific well defined problem or a general query?
Shinji Ikari
Thanks for the reply Daniel,
> What is wrong with Matlab or Mathematica then?
Nothing at all, except for the price maybe :) I was just curious
about functional languages in general and their suitability in
relation to other paradigms. I know Mathematica supports multiple
paradigms and its claimed strength is in some sort of term-rewriting
(I don't use Mathematica so I don't really know, but there must be
some aspects of the language that make it very suitable for
mathematics).
> Is this a specific well defined problem or a general query?
Just a general query. In a broader sense I was curious about what
aspects of a language or programming paradigm make it more or less
suitable for problems heavy in mathematics.
So, to extend the question a little, what aspects of a language or
paradigm make it highly suitable for doing mathematics?
Daniel C. Wang
{stuff deleted}
> aspects of a language or programming paradigm make it more or less
> suitable for problems heavy in mathematics.
>
> So, to extend the question a little, what aspects of a language or
> paradigm make it highly suitable for doing mathematics?
I think, it depends as someone else has mentioned what you mean by
mathematics. There are the purely symbolic kind of mathematics, and
others which are heavily numerical in nature.
In the end it's all about the libraries. BTW there are GPL versions of
Mathlab i.e. Ocatve. If you are doing statistical modeling I'd recommend R.
http://www.r-project.org
http://www.octave.org
I don't know if there is a good free replacement for Mathematica.
Personally, I think it's completely wrong headed to be asking "Is this
language good for my app?" You should understand the application first
and build the language around it. Rather than trying to fit mathematics
into a paradigm, one should define the appropriate mathematical paradigm.
Shinji Ikari
> Shinji Ikari wrote:
> {stuff deleted}
> > Just a general query. In a broader sense I was curious about what
> > aspects of a language or programming paradigm make it more or less
> > suitable for problems heavy in mathematics.
> >
> > So, to extend the question a little, what aspects of a language or
> > paradigm make it highly suitable for doing mathematics?
>
> I think, it depends as someone else has mentioned what you mean by
> mathematics. There are the purely symbolic kind of mathematics, and
> others which are heavily numerical in nature.
Good point. Sorry if I am being a little vague and not defining a
specific mathematical problem. I was just hoping some people here had
some thoughts or experience on the intersection of programming
languages and mathematics, with particular emphasis on the functional
paradigm (hence the reason it was posted to this group).
So, to focus back in on the question, consider two aspects of
mathematics mentioned previously;
1. symbolic algebra and,
2. numerical computation
What aspects of a language or paradigm make it particularly relevant
to each of these areas? For example, I've heard term and graph
rewriting are good for symbolic algebra. To what extent is this true?
Are there better concepts that would deal better with symbolic
algebra? How suitable is the functional paradigm in this area? And
the same thing for numerical computation, what aspects of a language
lead to an effective language for this area of mathematics?
thanks
Darius
shi...@swirve.com (Shinji Ikari) wrote:
[only replying to c.l.f]
> "Daniel C. Wang" <danw...@hotmail.com> wrote in message
> news:<bslp6t$cu463$1...@ID-216221.news.uni-berlin.de>...
> > Shinji Ikari wrote:
> > {stuff deleted}
> > > Just a general query. In a broader sense I was curious about what
> > > aspects of a language or programming paradigm make it more or less
> > > suitable for problems heavy in mathematics.
> > >
> > > So, to extend the question a little, what aspects of a language or
> > > paradigm make it highly suitable for doing mathematics?
> >
> > I think, it depends as someone else has mentioned what you mean by
> > mathematics. There are the purely symbolic kind of mathematics, and
> > others which are heavily numerical in nature.
>
> Good point. Sorry if I am being a little vague and not defining a
> specific mathematical problem. I was just hoping some people here had
> some thoughts or experience on the intersection of programming
> languages and mathematics, with particular emphasis on the functional
> paradigm (hence the reason it was posted to this group).
Jerzy Karczmarczuk has several papers that exploit lazy functional
programming creating solutions with impressive clarity, conciseness and
ease. It also illustrates one benefit of functional programming,
specifically lazy functional programming in this case, namely that the
programs often are quite similar to, almost/even transliterations of,
their specifications.
Joachim Durchholz
> So, to focus back in on the question, consider two aspects of
> mathematics mentioned previously;
>
> 1. symbolic algebra and,
> 2. numerical computation
>
> What aspects of a language or paradigm make it particularly relevant
> to each of these areas?
For (1), it's expressiveness and abstraction facilities.
(Expressiveness: the ability to express a lot of semantics with little
code. Not to be confused with terseness, which means writing lots of
code with a low keystroke count.)
(Abstraction: the ability to write code that operates at a higher
semantic level, using lower-level code but not letting lower-level
aspects "leak" through to the high level. It's an ideal that's at odds
with other aspects like memory and time efficiency; the best
approximations that I have seen were in functional programming
languages. Java is mediocre in this respect, C is bad, C++ is abysmal.)
For (2), it's a restricted expressivity. This might seem paradoxical at
first sight, but the more restricted the things that one can do are, the
easier it is for the compiler to analyse the sources and generate
efficient machine code for it.
Of course, abstraction and expressiveness benefit any programming
endeavour, so we have a strong tension between language qualities.
> For example, I've heard term and graph
> rewriting are good for symbolic algebra. To what extent is this true?
Term and graph rewriting are equivalent in this context, because terms
are represented as trees. (Technically, they turn into graphs as soon as
branch points are merged because they represent the same value, but
logically, they remain trees.)
Graph rewriting is transforming the graph into a better form at runtime.
"Better" usually meaning "smaller", thought that's not necessarily
always the case.
Graph rewriting is a common implementation technique for a specific
class of programming languages (lazily-evaluating functional languages).
There are arguments that lazy evaluation is good for symbolic math, but
I think the verdict isn't conclusive yet.
Most certainly the graph rewriting that happens inside the
implementation mechanism of the programming language is not directly
applicable to the kind of term transformations that are needed for
symbolic math. This is the same kind of short-circuit thinking that
leads people to believe that OO programming is good because real-world
objects map directly into computer objects (there's just enough truth in
that to make this legend immortal, but the real strengths of OO lie
elsewhere).
> Are there better concepts that would deal better with symbolic
> algebra?
Not really.
You need to build a "language for doing symbolic algebra" on top of any
existing language. Such a language may take several forms: it may look
similar to a functional programming language (that's what Mathematica
and other "programs for doing math" do), or it may be just a library
that defines data types representing mathematical objects, and routines
that manipulate them.
For Mathematica-style math packages, the programming language is
irrelevant to the end user. I suspect that most programs of this style
are written in C++ or Java, for no better reason than the availability
of programmers who can write programs in these languages.
For math libraries, the language becomes relevant, but any qualities
that make the language suitable will make it suitable for application
programming in general. Which are expressiveness and abstraction :-)
> How suitable is the functional paradigm in this area?
It's a generally suitable paradigm.
> And
> the same thing for numerical computation, what aspects of a language
> lead to an effective language for this area of mathematics?
As I said elsewhere, it's a language that's easy enough to analyze for
the compiler. (That's one of the reasons that keep Fortran alive: it
would be possible to use C instead of Fortran, but Fortran is far easier
to optimize, and those writing numeric programs value speed over
convenience.)
There's another important factor: the availability of high-quality
numeric libraries. There aren't many, and most can be traced back to
really ancient times - writing a good numeric library is hard. (I think
that's because one needs to be good in two very different areas:
analysis, and programming. Being good at programming is more like being
good at discrete mathematics.)
Regards,
Jo
Shinji Ikari
> programming creating solutions with impressive clarity, conciseness and
> ease. It also illustrates one benefit of functional programming,
> specifically lazy functional programming in this case, namely that the
> programs often are quite similar to, almost/even transliterations of,
> their specifications.
>
> http://users.info.unicaen.fr/~karczma/arpap/
Beautiful!! Thanks for the link, that's exactly the sort of stuff I
have been looking for.
His conclusion from "Scientific Computation and Functional
Programming" is interesting:
"The path from a textbook describing the general idea, to a debugged
program may be very long. The symbolic packages might also generate
some abominable code which should never be shown to students, because
they laugh loudly at it, as noted by the authors of [13].
...
We don't claim that lazy functional techniques should replace highly
optimized imperative codes in contexts where the efficiency is
primordial, but even then they might be selectively used to check the
correctness of the final programs: lazy code is so short that it is
difficult to introduce obscure bugs! We are convinced that lazy
languages provide an adequate computing tool for a theoretical
physicist who prefers elegance over a brutal force."
Neelakantan Krishnaswami
>
> Jerzy Karczmarczuk has several papers that exploit lazy functional
> programming creating solutions with impressive clarity, conciseness and
> ease. It also illustrates one benefit of functional programming,
> specifically lazy functional programming in this case, namely that the
> programs often are quite similar to, almost/even transliterations of,
> their specifications. <http://users.info.unicaen.fr/~karczma/arpap/>
I really, really like those papers.
Also, Gerald Sussman and Jack Wisdom wrote a book, _The Structure and
Interpretation of Classical Mechanics_, in which they re-develop
classical mechanics (ie, Lagrangian and Hamiltonian methods) using
Scheme. Their basic motivation was to offer a presentation that didn't
use the traditional, amibiguous notation for partial derivatives (in
which the distinction between functions and the values of functions at
a particular point are often blurred), and they enforced this by using
a mathematical notation that could be directly translated into Scheme
expressions: <http://mitpress.mit.edu/SICM/>
--
Neel Krishnaswami
ne...@cs.cmu.edu
Hendrik-Jan Agterkamp
> In article <20031228065845....@hotpop.com>, Darius wrote:
>>
>> Jerzy Karczmarczuk has several papers that exploit lazy functional
>> programming creating solutions with impressive clarity, conciseness and
>> ease. It also illustrates one benefit of functional programming,
>> specifically lazy functional programming in this case, namely that the
>> programs often are quite similar to, almost/even transliterations of,
>> their specifications. <http://users.info.unicaen.fr/~karczma/arpap/>
>
> I really, really like those papers.
Onother paper you might dig is
"Some Lattice-based Scientific Problems, Expressed in Haskell" by
D.B. Carpenter. It has a fine example on how to use 'scanf' I'm
not sure whether this is available on line though :-( I think it
got published in JFP.
Hendrik
Neelakantan Krishnaswami
>
> Onother paper you might dig is
>
> "Some Lattice-based Scientific Problems, Expressed in Haskell" by
> D.B. Carpenter. It has a fine example on how to use 'scanf' I'm
> not sure whether this is available on line though :-( I think it
> got published in JFP.
It seems to be on Citeseer:
<http://citeseer.nj.nec.com/157672.html>
Thanks for the reference!
--
Neel Krishnaswami
ne...@cs.cmu.edu
Brian Hurt
That's actually debatable. See:
http://citeseer.nj.nec.com/goncalves95cache.html
I would argue that with cache misses at 100-350 clock cycles each or
more, that the prime determinate of a program's speed is it's cache
friendliness. How long your program takes to run is more function of
how many cache misses it has than of how many instructions it
executes.
There is also the productivity of the programmer to consider. It's
not a myth that the same programmer is more productive in your average
functional language than in your average procedural or OO language.
For the same amount of work your functional programmer could implement
a much more complex algorithm- for example, using a quadtree
representation of a sparse matrix rather than the less efficient list
of lists or array of arrays.
Brian
Shinji Ikari
Thanks for taking the time to write such a detailed reply. Its given
me alot to think about and I really appreciate the effort.
Joachim Durchholz <joachim....@web.de> wrote in message
....
Graham Matthews
news:<3FED1C07...@his.com>...
> > Shinji Ikari wrote:
> > >
> > > I am wondering what people think of the suitability of functional
> > > languages for implementing solutions to problems heavy in mathematics.
> > > Obviously you can produce solutions in any turing-complete language,
> > > but I am wondering if functional languages are any more, or less,
> > > suitable than, say, the OO or imperative paradigms. What are people
> > > experiences in this area?
> >
> > Functional languages are quite good for mathematics. However, they
> > will likely not perform as well as Fortran in the most performance-
> > critical applications.
This isn't necessarily true. Sisal shows that functional languages can be
very fast, as fast as Fortran, in a wide variety of applications.
Strangely enough I think functional lanuages are more suited to the
number crunching part of mathematics, than to the symbolic processing
part. Pattern matching makes simple symbolic math easy to do in a
functional language. But for more complex applications you need to
carefully share and cache simplified expressions. and thats hard to do
transparently without resorting to some imperative hacks (at least
locally).
graham
Daniel C. Wang
{stuff deleted}
> Strangely enough I think functional lanuages are more suited to the
> number crunching part of mathematics, than to the symbolic processing
> part. Pattern matching makes simple symbolic math easy to do in a
> functional language. But for more complex applications you need to
> carefully share and cache simplified expressions. and thats hard to do
> transparently without resorting to some imperative hacks (at least
> locally).
Monads
http://www.fftw.org/pldi99.pdf
or perhaps that's what you mean by "imperative hacks".
Daniel C. Wang
{stuff deleted}
> This isn't necessarily true. Sisal shows that functional languages can be
> very fast, as fast as Fortran, in a wide variety of applications.
>
Oh as the FFTW approach shows, just because you can't beat the Fortran
compiler for raw numerical performance, doesn't mean you can't generate
the Fortran program you would have to normally write from a higher-level
spec. written in a functional programming language.
Graham Matthews
Well not exactly. The problem with monads for simplification
problems is that if I want to say memoise one single function
I have to wrap it, and everything that calls it in a monad. That's
very unnatural (compared to what can be done imperatively
in this situation).
graham
Ivan Boldyrev
There is also Single-Assignment C (http://www.sac.org, AFAIR) which is
proclaimed as Sisal successor.
But it seems to be closed-source :(
--
Ivan Boldyrev
Sorry my terrible English, my native language is Lisp!
Vasile Rotaru
>
> There is also Single-Assignment C (http://www.sac.org, AFAIR) which is
> proclaimed as Sisal successor.
>
bas
Ketil Malde
> I am wondering what people think of the suitability of functional
> languages for implementing solutions to problems heavy in mathematics.
What kind of mathematics? And what kind of suitability? For
numerical computation, it's hard to beat Fortran's performance, but
for modelling more algebraic mathematics, a functional language may be
better. IME, working with a functional language fits better with a
"mathematical mindset", but that doesn't automatically mean it's more
suited for doing math.
-kzm
--
If I haven't seen further, it is by standing in the footprints of giants
Jerzy Karczmarczuk
Graham Matthews dialogue with "Daniel C. Wang":
>>>Strangely enough I think functional languages are more suited to the
>>>number crunching part of mathematics, than to the symbolic processing
>>>part. Pattern matching makes simple symbolic math easy to do in a
>>>functional language. But for more complex applications you need to
>>>carefully share and cache simplified expressions. and thats hard to do
>>>transparently without resorting to some imperative hacks (at least
>>>locally).
>>
>>Monads
>>
>>http://www.fftw.org/pldi99.pdf
>>
>>or perhaps that's what you mean by "imperative hacks".
>
> Well not exactly. The problem with monads for simplification
> problems is that if I want to say memoise one single function
> I have to wrap it, and everything that calls it in a monad. That's
> very unnatural (compared to what can be done imperatively
> in this situation).
Several observations.
1. Pattern matching as we know it in Haskell/ML, or in a fuller form in
Prolog (unification) is *not so good* for symbolic math, beyond a
very, very superficial level.
You see, the problem is that syntactic filtering is a *structural*
analysis, good for implementing some recursive algorithms, etc.,
without encumbering the program with many 'case' or cascading
conditional constructs. But it won't help you in any semantic analysis
of your data, for example the equivalence between various expanded
or not polynomial forms. Or to discover the equivalences between
several trigonometric polynomials, permitting thus their simplification.
2. Still, the semantics is coded into the structure, so languages with rich
data types, with type classes, or object-oriented, are naturally suitable
for symbolic manipulations. Just look in what direction this realm evolves,
with domains/categories and whatever, in Magma or in MuPAD. Or what has
happened to Axiom.
Looking at the algorithms in GAP or MaCauley it is easy to see that they
can be coded in much more compact and elegant form using functional
techniques with higher order functions etc., than with standard imperative
loops and re-assignments. I disagree with the observation that functional
languages are more suited to hard numerics than to processing of complex
structures.
Sergey Mechveliani wrote a nice - at least quite inspiring - computer
algebra package in Haskell.
3. There is *plenty* of space for the application of co-recursive algorithms.
Laziness, if you wish.
You can't imagine - unless you have some experience with practical theore-
tical physics (i e. *doing* some computations in formal physics rather
than speculating about them) -
how many formal constructions can be casted into the form of lazy streams/
trees and more complex graphs. All the theories of perturbations for example.
Usually what you get is an *open* recursive equation satisfied by some
infinite series. The lazy formulation can give you in 15 lines the equivalent
of some pages of imperative coding...
4. ... But you might discover that the complexity of a non-optimized lazy code
is exponential or worse. Yes, Graham Matthews is right underlying the
importance of caching and sharing.
My favourite example is the perturbational solution of the Schrödinger
equation for a non-linear oscillator. Energy is an infinite series in
the coupling constant. The formula for it involves also the modified wave
functions, defined as series as well, and whose definitions involve the
energy. When I taught such stuff, I discovered that students can get as
far as the second term, perhaps third if they work for two days. The lazy
corecursive formula giving ALL terms can be written on a few lines, and
coded in Haskell in a few minutes. And then the program spends a horrible
amount of time on the third and higher terms, because of the memory clogging
by the unevaluated, repeatedly generated thunks.
Worse than the Fibonacci disgraceful benchmark...
But now, *I disagree* that some imperative hacks seem more "transparent" or
more suitable.
Memoization is something easily implementable in functional languages. You
define a lazy dictionary of associations (or just a list if the arguments
of memoized functions are natural numbers), and you call all your functions
through the dictionary, which is passed along. The result is sufficiently
efficient, and elegant. You get 10 or more terms for your oscillator before
the final explosion (because the series is badly divergent, the terms grow
factorially themselves...)
5. Moreover, usually there is no need for a particular sequencing of the
operations, the monadic stuff doesn't seem to improve anything. On the
contrary, the whole code is as 'purely functional' as it can be. If in
a memoizing dictionary you happen to store not the actual data but some
thunks, doesn't matter, the call by need protocol will instantiate every-
thing when you really look at it.
6. Unfortunately all this seems not very digestible when you see such coding
for the first time... You see, pedagogically it is easy to speak about
symbolic manupulations, the standard computer algebra, where you process
some data structures, polynomials, trig series, etc.
Lazy functional Way of Life permits you to process your *functions*, opaque,
compiled objects whose structure has nothing symbolic, but which are
equipped with very exquisite combinatorics for composition, plugging-in,
iteration, mapping, etc. All this requires a good deal of patience.
Bonne Année/Szczesliwego Nowego Roku.
Jerzy Karczmarczuk
Lex Spoon
>> will likely not perform as well as Fortran in the most performance-
>> critical applications.
>
> That's actually debatable. See:
> http://citeseer.nj.nec.com/goncalves95cache.html
>
> I would argue that with cache misses at 100-350 clock cycles each or
> more, that the prime determinate of a program's speed is it's cache
> friendliness. How long your program takes to run is more function of
> how many cache misses it has than of how many instructions it
> executes.
That argument fails if all of your memory is cache. :) Some people
blow millions in order to get the fastest possible results....
-Lex
Graham Matthews
> > problems is that if I want to say memoise one single function
> > I have to wrap it, and everything that calls it in a monad. That's
> > very unnatural (compared to what can be done imperatively
> > in this situation).
>
> Several observations.
>
> 1. Pattern matching as we know it in Haskell/ML, or in a fuller form in
> Prolog (unification) is *not so good* for symbolic math, beyond a
> very, very superficial level.
> You see, the problem is that syntactic filtering is a *structural*
> analysis, good for implementing some recursive algorithms, etc.,
> without encumbering the program with many 'case' or cascading
> conditional constructs. But it won't help you in any semantic analysis
Sure, I didn't mean that pattern matching gives you anything near the
notions of semantic equivalence you need in symbolic math. I just meant
it's a very convenient tool for analysing syntax trees.
Jerzy Karczmarczuk <kar...@info.unicaen.fr> wrote:
> Looking at the algorithms in GAP or MaCauley it is easy to see that they
> can be coded in much more compact and elegant form using functional
> techniques with higher order functions etc., than with standard
> imperative
Elegance isn't the only criterion for such algorithms.
Jerzy Karczmarczuk <kar...@info.unicaen.fr> wrote:
> Memoization is something easily implementable in functional languages.
> You
> define a lazy dictionary of associations (or just a list if the arguments
> of memoized functions are natural numbers), and you call all your
> functions
> through the dictionary, which is passed along. The result is sufficiently
> efficient, and elegant. You get 10 or more terms for your oscillator
> before
> the final explosion (because the series is badly divergent, the terms
> grow
> factorially themselves...)
This only works if you can predict at the start what expressions you will
be required to memoize. It isn't going to help one bit in general
symbolic expression simplification (where you might not for example know
the number of variables).
graham
Ketil Malde
>> I would argue that with cache misses at 100-350 clock cycles each or
>> more, that the prime determinate of a program's speed is it's cache
>> friendliness.
> That argument fails if all of your memory is cache. :) Some people
> blow millions in order to get the fastest possible results....
And the more millions you blow, the deeper is the cache hierarchy.
Are you aware of any modern computer (outside of wrist watches or
remote controls and the like) that doesn't have a hierarchical memory?
Hung Jung Lu
> Lex Spoon <l...@cc.gatech.edu> writes:
>
> > That argument fails if all of your memory is cache. :) Some people
> > blow millions in order to get the fastest possible results....
>
> And the more millions you blow, the deeper is the cache hierarchy.
> Are you aware of any modern computer (outside of wrist watches or
> remote controls and the like) that doesn't have a hierarchical memory?
>
Which brings me to the memory issue. Functional languages seem to
require more memory. To give a simple example, consider the
calculation of n! (n factorial). In imperative languages, the memory
usage is constant, independent of n. In functional languages, memory
usage increases with n. Unless something special is done, n! means n
recursive calls, which piles up the calling stack. (If you cache the
result, sure, it's faster, but RAM usage problem stays.)
The original poster talked about "math heavy" problems. In numerical
methods involving matrices, people really go out of their ways to
reduce/re-use/recycle RAM memory slots. Special numerical methods have
been devised to circumvent memory constraints. It's not unusual to use
megabtyes or gigabytes for matrix operations. In functional approach,
if one is not careful, I think memory usage can really get out of
control. For instance, all spreadsheet programmers I know sooner or
later are hit with memory problems, and instead of using functional
programming (spreadsheet formulas) they all have to switch to
imperative programming (macros/modules) at some point.
So my impression is: sure, functional programming can be used for
numerical problems, as long as your problem is small enough to fit
below the constraints of memory usage. For heavy linear algebra
operations or problem involving large tables and many
successive/intermediate operations, functional languages may not be
very suitable. In imperative languages the state variables are there
for you to see, and you know what you are dealing with. In functional
languages, the memory usage toll is hidden inside the cache and
calling stacks. For matrix problems, one single extra copy of the
matrix often means you have a dead program. It's not just matter of
millions $, given the nature of the problem, if you are not careful
enough, even trillion or quadrillion $ won't be enough: many problems
in linear algebra are easily n^2, n^3, n^4, etc. by nature. Memory
usage IS something you do have to care about.
Hung Jung
Brandon J. Van Every
> > 2. numerical computation
>
> first sight, but the more restricted the things that one can do are, the
> easier it is for the compiler to analyse the sources and generate
> efficient machine code for it.
Yes, but does anyone actually write decent compilers in the real world?
I've done low-level ASM code for 11 years... rarely have I seen a compiler
that was any good at it. The DEC Alpha compiler was the exception. Anyways
this is imperative stuff, for mainstream languages like C and C++, so pretty
much the "natural fit" to the task of optimizing the CPU instruction stream.
Those compilers mostly suck, so pardon my cynicism that you're going to get
anywhere layering functional constructs on top of the basic problem?
--
Cheers, www.indiegamedesign.com
Brandon Van Every Seattle, WA
"We live in a world of very bright people building
crappy software with total shit for tools and process."
- Ed Mckenzie
Mark Carroll
Hung Jung Lu <hungj...@yahoo.com> wrote:
(snip)
>require more memory. To give a simple example, consider the
>calculation of n! (n factorial). In imperative languages, the memory
>usage is constant, independent of n. In functional languages, memory
>usage increases with n. Unless something special is done, n! means n
>recursive calls, which piles up the calling stack. (If you cache the
Every decent functional language compiler will optimize the recursion
out of factorial so that it works like the imperative version if you
compile with optimization enabled. "something special" is most
certainly done, quite routinely.
-- Mark
Thant Tessman
Some languages even require it in their specifications.
-thant
Darius
Mark Carroll <ma...@chiark.greenend.org.uk> wrote:
The "something special" isn't even special. For example, if you were to
take the reduction rules of the call-by-value lambda-calculus as an
operational semantics, (the accumulator version of) factorial has no
memory build up. There is no inherent reason to build up stack nor do
most functional languages do so (as Mark says). In fact, without
tail-call optimization certain programming styles become impractical and
it necessitates contorting your code to fit a fixed set of iterative
primitives (usually accompanied with the unnecessary use of mutable
state).
Joachim Durchholz
>>For [numerical computation], it's a restricted expressivity. This might seem paradoxical at
>>first sight, but the more restricted the things that one can do are, the
>>easier it is for the compiler to analyse the sources and generate
>>efficient machine code for it.
>
> Yes, but does anyone actually write decent compilers in the real world?
> I've done low-level ASM code for 11 years... rarely have I seen a compiler
> that was any good at it.
I haven't looked into ASM for years, so I can only repeat what I have
read elsewhere: that current-day compilers are quite good at generating
decent machine code. For whatever definition of "quite good". (You might
want to direct this kind of question to comp.compilers.)
Anyway, optimization isn't just generating good ASM code, it's also
stuff like loop unrolling, common subexpression elimination, etc.
C and C++ are notoriously hard to optimize this, since it's often very
difficult to trace which pointer may refer to what array. Fortran
compilers have a far easier job since Fortran programs don't use
pointers, they use indexes (at least that used to be true for older
Fortran code, and I'm pretty sure that all the numeric libraries are
still written in that style).
> The DEC Alpha compiler was the exception. Anyways
> this is imperative stuff, for mainstream languages like C and C++, so pretty
> much the "natural fit" to the task of optimizing the CPU instruction stream.
Not really. C was "just right" for the CPUs of the 70ies, but nowadays
it overspecifies so many things that it's getting plain difficult to
write even a decent compiler for it.
IOW it may be possible to write a compiler that does a decent job of
utilizing the register set, but the C definition imposes so many
constraints on instruction ordering that it's a challenge to keep all
the pipelines of the CPU busy. (And that's just one of the code
generation problems in C. Again, I recommend asking in comp.compilers.)
> Those compilers mostly suck, so pardon my cynicism that you're going to get
> anywhere layering functional constructs on top of the basic problem?
Sort of.
Functional languages have two advantages:
1) Imperative programs impose a strict rule on the order in which things
get executed. Most of these ordering constraints are accidental, only a
few are essential, but those that are essential must be observed. It's
quite hard for a compiler to find out which ordering is essential and
which isn't (as witnessed by the huge body of literature on array and
matrix loop optimization). Functional languages impose very little
ordering, and almost all of that ordering is essential, so the compiler
can merrily unroll loops, eliminate common subexpressions, and do all
other kinds of code transformations. (Be warned: this kind of
optimization is far less common than one would expect. The compiler
that's generally considered to generate the fastest code - that for
OCaml - doesn't do much code transformation, it just generates good ASM.
Or at least we were so told on the newsgroup. Still, since functional
languages tend to have a far simpler semantics than imperative ones,
it's less work to get the compiler right, so there's more time for doing
a good code generation backend *g*)
2) Functional languages are extremely good at abstraction, far better
than imperative ones. (<detour> It's possible to write your own looping
constructs, and these are still ordinary functions, no "macro
expansion", "meta facilities" or whatever required. You can write
various styles of iterators, or what you want - and everything is still
"just functions". This is one of the main reasons why functional
languages tend to have a simpler semantics than imperative ones.
</detour>) Of course, highly abstract code is difficult to optimize, but
even in a functional language, you can write quite down-to-earth,
let-me-control-every-single-bit code. It's the programmer's choice
whether some piece of code should be concrete or abstract, so the
library designer can always adapt the trade-off between speed and
flexibility. I think this benefit is the more important one: one can
have fast (and inflexible) code where speed matters, and abstract (and
easily-used) library routines where flexibility is important.
Of course, to be of any use, the standard numeric libraries would need
to be rewritten in a functional language, and I'm not going to hold my
breath for that to happen. Those Fortran libraries are Good Enough After
All...
Regards,
Jo
--
Currently looking for a new job.
Joachim Durchholz
> Which brings me to the memory issue. Functional languages seem to
> require more memory. To give a simple example, consider the
> calculation of n! (n factorial). In imperative languages, the memory
> usage is constant, independent of n. In functional languages, memory
> usage increases with n. Unless something special is done, n! means n
> recursive calls, which piles up the calling stack. (If you cache the
> result, sure, it's faster, but RAM usage problem stays.)
As Mark and others have pointed out, n! isn't really a problem - every
decent compiler does tail-call optimization, and the problem goes away.
> The original poster talked about "math heavy" problems. In numerical
> methods involving matrices, people really go out of their ways to
> reduce/re-use/recycle RAM memory slots.
Now that is indeed a place where functional languages aren't quite there
yet.
However, I think the problem of determining which cells of a matrix cell
can be recycled for the next incarnation of a recursive function is just
as difficult (or easy) as doing code rearrangement on matrix
calculations in an imperative compilers. The data-flow analysis looks
very similar to me, so I think that the algorithms used in
imperative-language compilers should be transferrable to
functional-language ones. Functional languages usually don't employ the
algorithms at this time because functional languages aren't widely used
in heavy number-crunching (kind of chicken-and-egg problem here I think).
> Special numerical methods have
> been devised to circumvent memory constraints. It's not unusual to use
> megabtyes or gigabytes for matrix operations. In functional approach,
> if one is not careful, I think memory usage can really get out of
> control.
Not really.
You need to know what you're doing, but it's no more difficult than
taking care not to reallocate another gigabyte of matrices as local data.
> For instance, all spreadsheet programmers I know sooner or
> later are hit with memory problems, and instead of using functional
> programming (spreadsheet formulas) they all have to switch to
> imperative programming (macros/modules) at some point.
That has many causes. Some of them include:
* Spreadsheets are inherently imperative. You hit F9, and the
spreadsheet does a recalculation - if it were functional, no
recalculation were ever necessary.
* In a functional language, taking a copy of any data is always
efficient: just create another reference to it. Since the data is never
modified, sharing is always safe. In a spreadsheet, copying a cell will
always take up memory.
* The formula language of a spreadsheet is usually far too braindead to
do any real programming in it, and the macro language is imperative - so
there's no serious functional programming going on in a spreadsheet anyway.
> In imperative languages the state variables are there
> for you to see, and you know what you are dealing with. In functional
> languages, the memory usage toll is hidden inside the cache and
> calling stacks.
In a functional language, the state variables are in the parameters of
some recursive functions, so they are even more explicit than in an
imperative language. (Actually this makes functional programmers avoid
state, which often leads to far smaller, more elegant and more efficient
algorithms. Though efficiency is often difficult to compare, since
functional programs tend to have different trade-offs than imperative
ones - not because the technology is different, but because functional
programming languages encourage a different style.)
> For matrix problems, one single extra copy of the
> matrix often means you have a dead program.
Sure - but not in a functional language. You can copy the matrix as
often as you want, that's just another cell :-)
Of course, having lots of slightly different matrixes will kill a
functional program just as an imperative one.
How to go about combining matrices into a new matrix in a functional
languages:
There're a library routine, let's call it matrix_combine.
It takes some matrices as input, and returns the new matrix as an output.
It also takes a "worker" function as a parameter: it is given all the
input matrices, a row and a column value, and it's supposed to compute
the value for the corresponding result matrix.
The library routine will allocate the result matrix, run the worker
function over all the elements of that matrix, and be done. No needless
intermediate matrices!
Since FPLs have a rather regular semantics, the compiler can take the
definition of the worker function, look which computations are
independent of row/column numbers, and lift them out of matrix_combine
(this kind of transformation is safe if you don't have to worry about
pointers, or about mutable data - the publication keywords for the topic
include "equational reasoning" and "referential transparency").
If the compiler is really smart, it may even know that the row and
column numbers are processed in ascending order and reuse computations
from previous rows/columns, just as Fortran compilers do.
If the compiler is really really smart, it can even infer that one of
the input matrices isn't used after the result has been produced, and
that the input matrix elements are no more needed after a given point in
calculation, so it may infer that it can place the result matrix at the
same storage location as the input matrix. Again, that's just the same
kind of optimization that an excellent Fortran compiler could do, but
it's easier in a functional language than in Fortran since the compiler
doesn't have to worry about rogue index increments, early abortion of
for loops, programmer-imposed aliasing due to Common blocks, and similar
niceties.
I don't say that functional language compilers are already there. I just
see how it could be done, with less work than has been invested in
Fortran compilers over the years.
Richard Fateman
like C or Fortran is the need to recognizing aliases: two or
more different ways of accessing the same value. E.g. calls
by reference, equivalence statements, pointer-following.
A major issue for writing good assembler is that you are
presumably doing this because absolute efficiency is important.
But then you have to write different assembler code to be optimal for
computers that (nominally) have the same architecture but
have different performance, including different numbers of
arithmetic units, cache sizes, pipeline depth, etc.
The compiler writers supposedly have studied these things in
the best cases. Even in the 1960's, different models of the IBM S/360
had different "better" code sequences for things as simple as
moving 32 bits from one place in memory to another.
I think this message is cross-posted to too many newsgroups.
Where did it start?
Graham Matthews
> Which brings me to the memory issue. Functional languages seem to
> require more memory. To give a simple example, consider the
> calculation of n! (n factorial). In imperative languages, the memory
> usage is constant, independent of n. In functional languages, memory
> usage increases with n.
n! can be computed in contant space. Either do tail call optimisation or
program using a loop a la Sisal.
graham
Graham Matthews
> Hung Jung Lu wrote:
> > Which brings me to the memory issue. Functional languages seem to
> > require more memory. To give a simple example, consider the
> > calculation of n! (n factorial). In imperative languages, the memory
> > usage is constant, independent of n. In functional languages, memory
> > usage increases with n. Unless something special is done, n! means n
> > recursive calls, which piles up the calling stack. (If you cache the
> > result, sure, it's faster, but RAM usage problem stays.)
>
> As Mark and others have pointed out, n! isn't really a problem - every
> decent compiler does tail-call optimization, and the problem goes away.
I don't think this has anything to do with tail call optimisation.
You can simply write a loop to compute n!. As long as you have single
assignment semantics it's functional and will run exactly like an
imperative program.
graham
Albert Lai
> Which brings me to the memory issue. Functional languages seem to
> require more memory. To give a simple example, consider the
> calculation of n! (n factorial). In imperative languages, the memory
> usage is constant, independent of n. In functional languages, memory
> usage increases with n. Unless something special is done, n! means n
> recursive calls, which piles up the calling stack. (If you cache the
> result, sure, it's faster, but RAM usage problem stays.)
I am afraid this comparison is rigged by maliciously comparing two
non-equivalent programs; one of the programs is designed to save
memory, and the saving is then sneakily credited to the language.
So why don't I rig it my way too? Besides, I provide actual code!
In Java:
int f(int n) { return n==0 ? 1 : f(n-1)*n; }
This will clutter up the stack.
In SML:
fun f n = let fun g p n = if n=0 then p else g (p*n) (n-1) in g 1 n end
This will not clutter up the stack.
And just to debunk a 30-year-old myth:
In C:
int g(int p, int n) { return n==0 ? p : g(p*n, n-1); }
int f(int n) { return g(1,n); }
This will not clutter up the stack if compiled with gcc -O2.
What gcc -O2 can do, I have a problem calling it "something
special". (It is not like I ask for -O9.) Therefore if an SML compiler
does a similar optimization, it is not a "special" optimization or
rocket science either.
You may now say that the "special thing" I do is the introduction of
the auxiliary function g, and you say that based on a
while-loop-ridden program in your mind:
int f1(int n) { int p=1; while (n!=0) {p*=n; n-=1;} return p; }
Your while-loop is my g; your local variable p is my p. My SML and C
versions are faithful translations of f1, where every loop is
mechanically translated to a local function, and every local variable
becomes a parameter of the local functions. No rigging here. The
Java version, though, is obviously rigged.
Robert A Duff
> Mark Carroll wrote:
> > Every decent functional language compiler will optimize the recursion
> > out of factorial so that it works like the imperative version if you
> > compile with optimization enabled. "something special" is most
> > certainly done, quite routinely.
>
> Some languages even require it in their specifications.
Some languages require tail-call elimination. But the simple
straightforward recursive code for factorial is *not* tail recursive.
Do compilers really eliminate *that* recursion? And which languages
*require* it?
Of course, you can *make* factorial tail-recursive, but it somewhat
obscures the code, IMHO, if you have to do that by hand.
- Bob
Darius
Well, this is the thing. Most imperative languages provide no option
-but- this and always by hand.
Anyways, presumably Hung was talking about the accumulator version of
factorial, otherwise it's a comparison between apples and oranges. An
imperative version that work the "same way" would also build up stack.
Hung Jung Lu
>
> The "something special" isn't even special. For example, if you were to
> take the reduction rules of the call-by-value lambda-calculus as an
> operational semantics, (the accumulator version of) factorial has no
> memory build up.
The keywords are in "(the accumulator version of)". Come on, people.
Give me a break.
Don't tell me that for Fibonacci series you'll also re-write the
function in matrix form so you can fit it into "the accumulator
version of".
It's like sweeping a problem under the rug. I was saying that
recursive calls in functional languages increase usage of memory as
compare to imperative loops, and you guys are saying that: "OK, let me
rewrite and do some trick and let me compile this particular
functional program 'optimally' into equivalent of an imperative loop
and there will be no memory problem." Give me a break. We already knew
that there is no memory problem in imperative programming! Are you
guys really acknowledging that functional programming is great so long
as you tweak it to the point that imperative programming is actually
used? I hope that's not what you are saying.
Let's face it. For GENERAL functional programming, recursive calls
will and DO increase memory usage. For simple problems you may be
lucky to re-arrange your problem into "the accumulator version of".
For more complex problem, you may not be lucky.
regards,
Hung Jung
Lauri Alanko
> The keywords are in "(the accumulator version of)". Come on, people.
> Give me a break.
Your argument seems to be that when programs are written in a
non-optimal fashion, then they are non-optimal. That is a tautology.
What you call "sweeping the problem under the rug" is actually a
demonstration that the problem _can_ be dealt with while still remaining
within the realm of functional programming. Yes, writing programs
tail-recursively requires some work. Are you claiming that this work is
significantly more than you'd require when writing a similarly
functioning program in an imperative language? Or are you claiming that
a tail-recursive program has lost the benefits of functional style? I
think both statements are false, but I won't say more on this until I
hear what your claim actually is.
> Let's face it. For GENERAL functional programming, recursive calls
> will and DO increase memory usage. For simple problems you may be
> lucky to re-arrange your problem into "the accumulator version of".
> For more complex problem, you may not be lucky.
If you can write the program to run in constant space in an imperative
language, you can also write it to run in constant space in a functional
one.
There is another, somewhat related issue, that you haven't mentioned: in
an imperative language, you can destructively modify a single data
structure all the time, whereas in a purely functional language you have
to construct new data structures. However, this is an _efficiency_
issue, since garbage collection will reclaim the old data structures.
Still, memory usage stays constant.
Lauri Alanko
l...@iki.fi
Darius
hungj...@yahoo.com (Hung Jung Lu) wrote:
> Darius <dda...@hotpop.com> wrote in message
> news:<20040109172148....@hotpop.com>...
> >
> > The "something special" isn't even special. For example, if you
> > were to take the reduction rules of the call-by-value
> > lambda-calculus as an operational semantics, (the accumulator
> > version of) factorial has no memory build up.
>
> The keywords are in "(the accumulator version of)". Come on, people.
> Give me a break.
Well, I was assuming you were attempting to make a valid point.
To start, last time I checked,
int factorial(int n) { return n == 0 ? 1 : n * factorial(n-1); }
was a valid C(++) program. It builds up stack too. So what is you're
point? The above program would be the straightest translation of the
definition of factorial into C. What you mean I need to write it using
an accumulator variable to not build up stack?!
> Don't tell me that for Fibonacci series you'll also re-write the
> function in matrix form so you can fit it into "the accumulator
> version of".
Don't tell me that for Fibonacci series you'll also re-write the
function using a for-loop and mutable state just to fit it into "the
accumulator variable version of".
> It's like sweeping a problem under the rug. I was saying that
> recursive calls in functional languages increase usage of memory as
> compare to imperative loops
Not if they are tail-recursive. If they aren't then they use no more
stack than recursive calls in imperative languages. You can only build
in so many imperative loops, with tail-call optimization you don't need
to build in -any-.
As I said (in a different reply) that imperative loops are already "an
accumulator version of". If you have major issues with having to
rewrite to "the accumulator version of" then you -definitely- DON'T want
to use an imperative language, because you have much less choice in the
matter there, recursive calls will likely hurt more when you don't want
"the accumulator version of", and you don't get to decide which
"accumulator version of" loops are built-in unless you write the
language yourself.
If somehow calling "the accumulator version of" a for-loop makes it
better then fine below is a (simple) for-loop (for Haskell). I could
make it as flexible as C's, but that's overkill for my purpose. Instead
I'll use a simpler thing that fits the problem instead of a
one-size-fits-most construct. This higher-order function also nicely
captures (a case of) accumulator iteration, so people reading the code
will immediately be able to see and understand the idiom being used
(after the first time the see it) without having to reverse-engineer the
intent. Of course, there are benefits to the author too; the
boilerplate for the idiom can be written once and optimizations to it
will help all uses.
forAcc start stop init body = loop start init
where loop i acc | i > stop = acc
| otherwise = loop (i+1) $! body i acc
factorial 0 = 1
factorial n | n > 0 = forAcc 1 n 1 (*)
This function takes constant stack space.
> Let's face it. For GENERAL functional programming, recursive calls
> will and DO increase memory usage.
What's "GENERAL functional programming"? Transforming to use an
accumulator is a general technique. And no, recursive calls -may-
increase memory usage and the only time they -have to- is when you'd
need a stack -anyways-.
> For simple problems you may be
> lucky to re-arrange your problem into "the accumulator version of".
> For more complex problem, you may not be lucky.
If it's not possible to rearrange it into "the accumulator version of"
or similar, then you -definitely- won't be able to do it without
building up stack in a non-tail-call optimizing language (typical of
most imperative languages).
Jesper Louis Andersen
>
> It's like sweeping a problem under the rug. I was saying that
> recursive calls in functional languages increase usage of memory as
This catched me. When I write functional programs, memory usage is rarely a
problem. And if I think my program uses too much memory you could profile for
space usage. This gives you the exact hot-spots for rewriting your program into
tail recursive versions of those hot-spots.
You are right that writing an imperative loop will take less memory than a
recursive call. And then what? There are already people that has showed that
a rather trivial rewrite can eliminate the stack usage. I cannot see why this
question matters at all, given the above.
I also fail to see why the discussion of whether this rewrite is uglier,
prettier, more effective, less using stackspace or whatnot is important. If
you are writing programs for practical use, then either the space problem
does not matter at all which implies there is no reason to think about it, or
the space problem matters, which implies that you will have to find the
problematic spots and rewrite them. Consider the problem being equal to that
of optimizing for performance. And this is almost always easier in a functional
setting in my opinion.
--
Jesper
Andreas Eder
> Don't tell me that for Fibonacci series you'll also re-write the
> function in matrix form so you can fit it into "the accumulator
> version of".
No, the reason is, that then you have a version of Fibonacci whose
runtime is only O(log n), instead of linear, or exponential as the
trivial implementation is.
'Andreas
--
Wherever I lay my .emacs, there's my $HOME.
Joachim Durchholz
> Of course, you can *make* factorial tail-recursive, but it somewhat
> obscures the code, IMHO, if you have to do that by hand.
Which is why all functional languages should by now have functions like
"fold" which will take care of such recursion (and, as an aside bonus,
express things in a far more direct fashion):
fac n = fold (*) 1 [1..n]
meaning: "fac n is what you get if you take the value 1, the list of all
integers between 1 and n, and insert the * operator between them".
Behind the scenes, it's far more efficient than that, it's not going to
construct the sequence explicitly, it's doing things in a tail-recursive
manner, and generally keeping all the gory details from the programmer.
OK, the above contains several white lies:
* The list will be optimized away only if the language does lazy
evaluation, and the compiler is smart enough to notice the optimization
opportunity. Languages where this isn't true usually use a "generator"
instead of a list at that point.
* I'm not sure that the [1..n] syntax is correct in any language.
* At least in Haskell, "fold" is really named "foldl". Or "foldr" if you
want 1 * (2 * (3 * ... * n)...)) instead of (...((1 * 2) * 3) * ... * n.
Adrian Hey
> Darius <dda...@hotpop.com> wrote in message
> news:<20040109172148....@hotpop.com>...
>>
>> The "something special" isn't even special. For example, if you were to
>> take the reduction rules of the call-by-value lambda-calculus as an
>> operational semantics, (the accumulator version of) factorial has no
>> memory build up.
>
> The keywords are in "(the accumulator version of)". Come on, people.
> Give me a break.
I don't think you deserve one. If you don't understand the implementation
or proper use of FPL's (and it seems you don't) you should avoid such
generalised assertions and try to be more precise about what it is you
think is wrong with FPL's, and maybe ask a few polite questions.
> Don't tell me that for Fibonacci series you'll also re-write the
> function in matrix form so you can fit it into "the accumulator
> version of".
OK
> It's like sweeping a problem under the rug. I was saying that
> recursive calls in functional languages increase usage of memory as
> compare to imperative loops,
Actually it was rather unclear whether you were saying they increase
memory consumption or just stack consumption. If it's the stack
you're talking about this is absolutely not true. For heap the
situation is far more complex, but it is certainly not generally
true that use of recursion in functional programs causes an "increase
usage of (heap) memory".
> and you guys are saying that: "OK, let me
> rewrite and do some trick and let me compile this particular
> functional program 'optimally' into equivalent of an imperative loop
> and there will be no memory problem."
Tail recursion often is relatively awkward (by FP's usual standards of
elegance). But even so, it is far less awkward than the imperative loop
alternatives you seem to be advocating. Furthermore, at least FPL's
give you the choice, whereas awkward is the only option available in
imperative languages.
> Give me a break.
Another one already?
> We already knew
> that there is no memory problem in imperative programming!
We did? I have to admit I didn't know that before you told me.
> Are you
> guys really acknowledging that functional programming is great so long
> as you tweak it to the point that imperative programming is actually
> used? I hope that's not what you are saying.
Indeed, that is not what we are saying. Tail recursion does subsume
common imperative loop constructs, but it does much more too.
> Let's face it. For GENERAL functional programming, recursive calls
> will and DO increase memory usage.
Why should we face it when it clearly isn't true, at least as far
as stack consumption is concerned. Now if you're talking about
memory consumption in general then I think it would be fair to say
that lack of destructive assignment and mutable state will almost
always result in increased heap burn rate in an FPL. But this does
not mean it "uses more memory" (it means it causes more frequent
garbage collection).
But even this is an accident of implementation. There's nothing in
the definitions of FPL's to stop *executables* using destructive
assignment (overwriting allocated storeage). But it seems to be
a rather difficult optimisation in practice so most compilers can't
do a very good job at the moment (if they attempt it at all).
One exception to this might be Clean, but even Clean only manages
this with the aid of programmer supplied uniqueness annotation, so
it's a bit awkward to use.
> For simple problems you may be
> lucky to re-arrange your problem into "the accumulator version of".
> For more complex problem, you may not be lucky.
On the contrary, tail recursion is not only simpler, it's more general
than imperative loops, unless you're prepared to use goto's or very
weird switches.
For simple problems you may be lucky to re-arrange your problem into
"the imperative loop version of". For more complex problem, you may not
be lucky. In these cases you'd better switch to using tail recursion.
Unfortunately doing this with most current imperative language
implementations will waste vast amounts of stack space. What a pity.
Regards
--
Adrian Hey
Tak To
HJL> people. Give me a break.
Lauri Alanko wrote:
LA> Your argument seems to be that when programs are written in a
LA> non-optimal fashion, then they are non-optimal. That is
LA> a tautology.
My reading:
HJL's says that programs written in a natural or typical fashion(*)
in the FP paradigm are non-optimal memory-wise.
(*) specifically, the accumulator version is not typical
And many FPers maintain that there is no such thing as a typical
or natural fashion in FP paradigm, at least as far in the context
of HJL's examples (factorial, fibancci, large matrices etc) are
concerned.
My question is, is there a typical or natural fashion for FP
in general? If not, and one cannot compare the typicals of
the two programming paradigms, what can one compare? (Note
that I am talking about paradigms, not languages.)
Tak
--
----------------------------------------------------------------+-----
Tak To ta...@alum.mit.eduxx
--------------------------------------------------------------------^^
[taode takto ~{LU5B~}] NB: trim the xx to get my real email addr
Tak To
> [...] all spreadsheet programmers I know sooner or
> later are hit with memory problems, and instead of using
> functional programming (spreadsheet formulas) they all have
> to switch to imperative programming (macros/modules) at
> some point.
I can't see how spreadsheet formulas can be considered
FP, given that one cannot create functions or even do
recursion in the formulas. At most one can say is that
they are free of side effects.
Darius
Tak To <ta...@alum.mit.edu.-> wrote:
> hungj...@yahoo.com (Hung Jung Lu) wrote:
> HJL> The keywords are in "(the accumulator version of)". Come on,
> HJL> people. Give me a break.
>
> Lauri Alanko wrote:
> LA> Your argument seems to be that when programs are written in a
> LA> non-optimal fashion, then they are non-optimal. That is
> LA> a tautology.
>
> My reading:
>
> HJL's says that programs written in a natural or typical fashion(*)
> in the FP paradigm are non-optimal memory-wise.
What is "natural" is problem dependent (or perhaps dependent on the
presentation of the problem). If I say write a program that calculates
fib n where fib n is defined as fib n = if n < 2 then n else fib (n-1) +
fib (n-2). The most natural solution in any language (supporting
recursion) would be the recursive algorithm. You are not going to tell
me that,
int fib(int n) {
int u = 0, v = 1;
for(;n>1;--n) {
int tmp = u + v;
u = v;
v = tmp;
}
return u;
}
is the more natural C solution than,
int fib(int n) { return n < 2 ? n : fib(n-1) + fib(n-2); }
nor is it anymore "typical" than an accumulator version written in a
functional language. Another way of expressing fib n is as the 'u'
value after the nth transition of the following transition system,
u <- v
v <- u + v
with initial contents u = 0, v = 1. This is the algorithm that the
first C solution uses. Probably the most natural and direct
implementation of that for Haskell would be,
fib n = fst (iterate (\(u,v) -> (v,u+v)) (0,1) !! n)
this runs in constant space* though it isn't all that efficient.
Another solution that's slightly less literal but more likely to be
given in response to the above is**,
fib n = transition n 0 1
where transition 0 u v = u
transition i u v = transition (i - 1) v (u + v)
Of course, neither of these is the most efficient way of calculating fib
n; the most (and more) efficient form(s) are(were) not a function of the
paradigm we are using but of the brain-sweat we put out.
> (*) specifically, the accumulator version is not typical
Sure it is. In a language that provides only tail-recursion to express
iteration, then understanding when and how to use it is a fundamental
part of learning and using the language.
> And many FPers maintain that there is no such thing as a typical
> or natural fashion in FP paradigm, at least as far in the context
> of HJL's examples (factorial, fibancci, large matrices etc) are
> concerned.
>
> My question is, is there a typical or natural fashion for FP
> in general?
Yes. Using tail-recursion to express iteration is both typical and
natural for FP. When the algorithm is not iterative using a (non-tail)
recursive solution is both typical and natural for FP -and- for most
imperative languages.
Finally, even if I assume that tail-recursion is "unnatural" it's still
often more "natural" than the imperative solution, so I still don't see
much to the argument. Is the argument that unnatural solutions are
more "typical" or even considered "natural" in imperative languages? If
so I heartily agree, what better advertisement for FP?
* Given a single strictness annotation: v `seq` (v,u+v)
** A notable thing is that this program could easily be -calculated-
from the first and the result of that calculation (suitably abstracted)
can be captured in a HOF.
Albert Lai
> It's like sweeping a problem under the rug. I was saying that
> recursive calls in functional languages increase usage of memory as
> compare to imperative loops, and you guys are saying that: "OK, let me
> rewrite and do some trick and let me compile this particular
> functional program 'optimally' into equivalent of an imperative loop
> and there will be no memory problem." Give me a break. We already knew
> that there is no memory problem in imperative programming! Are you
> guys really acknowledging that functional programming is great so long
> as you tweak it to the point that imperative programming is actually
> used? I hope that's not what you are saying.
>
> Let's face it. For GENERAL functional programming, recursive calls
> will and DO increase memory usage. For simple problems you may be
> lucky to re-arrange your problem into "the accumulator version of".
> For more complex problem, you may not be lucky.
If you want to discuss more complex problems, then let me invite you
to try your hands at a slight more complex task than factorial.
An input binary tree with string labels on [internal] nodes is given
in the form of a data structure, i.e., in SML as
datatype tree = nada | node of {label:string, left:tree, right:tree};
or in C++ as
struct tree { string label; tree *left, *right };
/* The NULL pointer will stand for nada. */
Write a program that takes such a binary tree and prints out the
string labels of its [internal] nodes in in-order.
(ObOnTopic: this is a simplification of typical tasks in math-heavy
problems alike, e.g., printing out an expression in a symbolic math
package, or refining mesh granularity in an adaptive numerical
algorithm.)
I can write an SML solution that needs as much memory space as the
depth of the tree, in the form of stack; and as much steps as the
number of nodes and nada's in the tree. Yes it is recursive, and
I won't bother to write a tail-call or loop version.
I challenge you to write an imperative solution that runs in just as
many steps. Will it sweep the stack problem under the rug (by
consuming memory elsewhere so you can claim "I use no stack")? Is
imperative programming great as long as you tweak it to the point that
functional programming is actually used?
Brandon J. Van Every
"Joachim Durchholz" <joachim....@web.de> wrote in message news:btndq2
>
> I haven't looked into ASM for years, so I can only repeat what I have
> read elsewhere: that current-day compilers are quite good at generating
> decent machine code.
That mantra has enough wiggle room in it to get out of anything. Define
"decent." Decent to run MS-Word?
> For whatever definition of "quite good". (You might
> want to direct this kind of question to comp.compilers.)
I did actually. No surprises there.
> Anyway, optimization isn't just generating good ASM code, it's also
> stuff like loop unrolling, common subexpression elimination, etc.
> C and C++ are notoriously hard to optimize this, since it's often very
> difficult to trace which pointer may refer to what array. Fortran
> compilers have a far easier job since Fortran programs don't use
> pointers, they use indexes (at least that used to be true for older
> Fortran code, and I'm pretty sure that all the numeric libraries are
> still written in that style).
Yes, some languages have more burdens than others. The simpler the
programming model, the easier to optimize.
> > The DEC Alpha compiler was the exception. Anyways
> > this is imperative stuff, for mainstream languages like C and C++, so
pretty
> > much the "natural fit" to the task of optimizing the CPU instruction
stream.
>
> Not really.
I suppose I didn't state my point clearly. CPU instruction streams are
fundamentally imperative. That is my point. I don't care about C or C++,
that's a sideshow. The point is, functional programming is inherently a
layer of complication on top of the imperative machine architecture.
> Still, since functional
> languages tend to have a far simpler semantics than imperative ones,
> it's less work to get the compiler right, so there's more time for doing
> a good code generation backend *g*)
This is all theory. Look at what happens in industrial practice. Nothing
much.
--
Cheers, www.indiegamedesign.com
Brandon Van Every Seattle, WA
20% of the world is real.
80% is gobbledygook we make up inside our own heads.
Joachim Durchholz
> "Joachim Durchholz" <joachim....@web.de> wrote:
>
>> I haven't looked into ASM for years, so I can only repeat what I
>> have read elsewhere: that current-day compilers are quite good at
>> generating decent machine code.
>
> That mantra has enough wiggle room in it to get out of anything.
> Define "decent." Decent to run MS-Word?
"Decent" in the sense that writing faster code in ASM requires expert
knowledge (i.e. real experience, as opposed to just knowing the
instruction set, register structure, and memory model).
>> Anyway, optimization isn't just generating good ASM code, it's also
>> stuff like loop unrolling, common subexpression elimination, etc.
>> C and C++ are notoriously hard to optimize this, since it's often
>> very difficult to trace which pointer may refer to what array.
>> Fortran compilers have a far easier job since Fortran programs
>> don't use pointers, they use indexes (at least that used to be true
>> for older Fortran code, and I'm pretty sure that all the numeric
>> libraries are still written in that style).
>
> Yes, some languages have more burdens than others. The simpler the
> programming model, the easier to optimize.
Then you should like functional languages :-)
>>> The DEC Alpha compiler was the exception. Anyways this is
>>> imperative stuff, for mainstream languages like C and C++, so
>>> pretty much the "natural fit" to the task of optimizing the CPU
>>> instruction stream.
>
>> Not really.
>
> I suppose I didn't state my point clearly. CPU instruction streams
> are fundamentally imperative. That is my point.
Well... er... no, your point was clear enough.
My point, however, is that modern languages are quite far from CPUs in
other ways. The hoops that a compiler is expected to jump through are
many, and having to translate the stuff from functional to imperative is
just another hoop (and a quite easy one: the techniques aren't very
difficult - actually OCaml, the language and implementation that's
commonly considered to be "the fastest functional language around",
doesn't use many compiler tricks, just a solid backend).
And before you say "OCaml may be the fastest functional language around,
but it doesn't beat C": OCaml actually has beaten C in several ICFP
contests. (See below for more on ICFP.)
> The point is, functional programming is inherently a layer of
> complication on top of the imperative machine architecture.
It's a step further away, but it's quite far from being a complication!
Functional languages have a far, far simpler semantics than their
imperative counterparts. (That's one of the reasons why optimizing them
is easier.)
>> Still, since functional languages tend to have a far simpler
>> semantics than imperative ones, it's less work to get the compiler
>> right, so there's more time for doing a good code generation
>> backend *g*)
>
> This is all theory. Look at what happens in industrial practice.
> Nothing much.
Ever looked at the ICFP contest results? 36 hours time, same task for
everybody, and everybody gets to choose his favorite language.
Most contests ended up with OCaml winning or among the first three places.
More interesting: Participants are encouraged to publish a log of their
activities. Teams using an imperative language usually work on the base
algorithm until the very last minute. Teams using a functional language
usually have a working program in very little time (I have seen
everything between 6 and 24 hours), after which they start implementing
optimizations.
I don't think that this is theory.
Joachim Durchholz
> I can't see how spreadsheet formulas can be considered FP, given that
> one cannot create functions or even do recursion in the formulas. At
> most one can say is that they are free of side effects.
And even that isn't true, at least not in the general case...
Joachim Durchholz
> HJL's says that programs written in a natural or typical fashion(*)
> in the FP paradigm are non-optimal memory-wise.
This is partly true, partly wrong.
Considering mini examples like fac and fib, there is no real difference.
Particularly, the argument that "because functional languages must
recurse to do loops, so they will have a stack build-up" is intuitive
and dead wrong: anything that was a loop will be a tail call in an FPL,
and will henceforth be optimized. The resulting machine code will follow
exactly the same patterns, regardless of whether the language was
imperative or functional.
Considering small programs (such as Unix filters and such), functional
languages are at a disadvantage.
You can't overwrite nothing. Whenever you just change a record field in
an imperative language, the functional language has to create another
record, and copy all the old data (except for the changed field, for
which it takes the new value). After that, it will most likely have to
garbage collect the old record, so we get not only much more copying, we
also have a higher garbage collection overhead.
Programming style does work against the problem. FPL records tend to be
far smaller than imperative ones, simply because there is no incentive
to aggregate as much data as possible into each record. Personally, I
find those smaller-grained objects are usually the better, more
maintenance-friendly design, but that's just my personal view.
That all being said, small FPL programs tend to be slower than their
imperative counterparts. Fortunately, such programs usually don't have
to be fast anymore.
When it comes to large programs, the imperative version will have to
copy lots of data, just to avoid inadvertently modifying shared data.
Functional languages don't need to copy that data.
I'm not sure how much of an issue that is, but I do see large imperative
systems becoming dog slow (look at Windows, Word, OpenOffice, or the
last multi-person-year project written at your company), and that "copy
things just in case they are shared" is one of the reasons. Functional
code will never copy data unless that's absolutely necessary, so it
should be at an advantage when systems become really large.
The problem, as with all claims for large software, is that it's very
difficult to collect evidence for or against it.
Darius
Joachim Durchholz <joachim....@web.de> wrote:
> > The point is, functional programming is inherently a layer of
> > complication on top of the imperative machine architecture.
>
> It's a step further away, but it's quite far from being a
> complication! Functional languages have a far, far simpler semantics
> than their imperative counterparts. (That's one of the reasons why
> optimizing them is easier.)
Just to add in the usual response: For wider definitions of "machine",
i.e. parallel, distributed, global computing, functional languages
appear to be closer to the "machine architecture". The typical
obligatory reference in this case is Sisal. However, it is dormant if
not dead, but someone else also pointed out Single Assignment C
recently (www.sac-home.org).
Vasile Rotaru
>> I suppose I didn't state my point clearly. CPU instruction streams are
>> fundamentally imperative. That is my point.
>
> Well... er... no, your point was clear enough. My point, however, is
> that modern languages are quite far from CPUs in other ways. The hoops
> that a compiler is expected to jump through are many, and having to
> translate the stuff from functional to imperative is just another hoop
> (and a quite easy one: the techniques aren't very difficult - actually
> OCaml, the language and implementation that's commonly considered to be
> "the fastest functional language around", doesn't use many compiler
> tricks, just a solid backend). And before you say "OCaml may be the
> fastest functional language around, but it doesn't beat C": OCaml
> actually has beaten C in several ICFP contests. (See below for more on
> ICFP.)
>
>
I'm sure about Haskell, but AFAIK, Ocaml (and most schemes) uses "boxed
types", that is some bits of the machine word are used for flags. So,
unless I miss something,the simple arithmetic in Ocaml will be inevitably
slower. (unbox, do the math, box again). OTOH Ocaml has lighter calling
conventions (than C), and is more aggresively inlining. (There is some
work also, on making an Ocaml compiler which uses unboxed types, but this
is far from finished).
But this is just a side note. There seems to be two main sides in this
topic. One that sustains that expert imperative code will be always faster
than expert functional code, and the one which sustains that expert
functional code is as fast as its imperative counterpart, but is easier to
write, understand and optimize.
As for me, given the choice, I'll prefer Ocaml to C for almost
everything, except for the simplest alghorithms.
Rgds, vasha
Hung Jung Lu
>
> My reading:
>
> HJL's says that programs written in a natural or typical fashion(*)
> in the FP paradigm are non-optimal memory-wise.
>
> (*) specifically, the accumulator version is not typical
>
> And many FPers maintain that there is no such thing as a typical
> or natural fashion in FP paradigm, at least as far in the context
> of HJL's examples (factorial, fibancci, large matrices etc) are
> concerned.
>
> My question is, is there a typical or natural fashion for FP
> in general? If not, and one cannot compare the typicals of
> the two programming paradigms, what can one compare? (Note
> that I am talking about paradigms, not languages.)
>
That's a point. It's like talking about solving a problem in momentum
space or in coordinate space (in quantum mechanics or Fourier
transform). At the end of the day, they are equivalent. You can always
tweak one to the point looking like the other.
In functional approach, I can even pass the entire RAM as argument in
recursive calling, and/or also pass the step number as argument, and I
will ended up, guess what, with a imperative program. It looks like an
imperative program, it smells like an imperative program. It is an
imperative program. Similarly, I can write functional programs with
imperative languages. They are just like Fourier transforms of each
other. But if you insist on calling an imperative program written in
functional language as a functional program (keeping states stored as
arguments passed in recursive calls), there is nothing I can do about
it.
In imperative languages, (especially the old fashion way using loops
instead of recursion) you are telling the computer what to do.
Therefore, at any given step, you are keeping track on memory usage,
by default. This is a feature. Whether it's a good or bad feature,
it's another story. It's a good feature when your problem is memory
sensitive.
In functional language, you by default do not think about memory
usage. This is a feature. Whether it's good or bad feature, it's
another story. For many problems, not worrying about memory usage
allows you to focus on the mathematical problem. I used to do plenty
of symbolic calculations. It's great when you don't need to think
about memory allocation. Of course, it's only when you are hit with
memory constraints that you start to do optimizations.
----------------------------------------
For memory-sensitive programs, in particular things like EISPACK,
LINPACK, or Intel's MKL (Math Kernel Library), which are commonly used
in linear algebra problems, you may try to write equivalent versions
functionally, using tail-call optimization and all. It's probably a
good academic exercise. But in the real world, people will stick with
imperative programming for these memory-sensitive programs. I just
don't see how people will ever switch seriously into functional
languages for memory-sensitive math libraries. To borrow a joke that
someone once mentioned, it's like doing your laundry with a
dishwasher. There is no doubt it works, but the question is: "why
would you want to do that?"
Hung Jung
Darius
Darius <dda...@hotpop.com> wrote:
> On Sun, 11 Jan 2004 13:51:58 -0500
> Tak To <ta...@alum.mit.edu.-> wrote:
> > And many FPers maintain that there is no such thing as a typical
> > or natural fashion in FP paradigm, at least as far in the context
> > of HJL's examples (factorial, fibancci, large matrices etc) are
> > concerned.
> >
> > My question is, is there a typical or natural fashion for FP
> > in general?
>
> Yes. Using tail-recursion to express iteration is both typical and
> natural for FP. When the algorithm is not iterative using a
> (non-tail) recursive solution is both typical and natural for FP -and-
> for most imperative languages.
Actually, I'll amend this. The -preferred- solution is to use
combinators to handle any iteration or recursion, e.g. foldl, foldr,
unfoldr, until, iterate, map etc. These generally give higher-level
code as objects are manipulated en masse as single conceptual units
rather than "collections". Of course, -these- are implemented
(tail-)recursively and languages with tail-call optimization and
higher-order constructs accept that there is no "best" basis for
recursion combinators, so other general-purpose, domain-specific,
application-specific, or even module-specific combinators are built
constantly.
Joachim Durchholz
> In functional language, you by default do not think about memory
> usage.
Sorry, this is nonsense. Functional programmers do think about memory
usage - else they wouldn't care about tail call optimization.
Even the converse (that you do think about memory in an imperative
language) isn't true. Few programmers have a details idea of the memory
usage incurred if they call a subroutine. Look at the memory bloat of
commonly used C++ or Java programs... as soon as code size transcends a
given limit (several dozen person-years?), the memory requirements start
to grow with every iteration of the software.
Canonical examples: word processors, http browsers, http servers,
spreadsheets - all are memory hogs, all keep getting larger with every
revision, and all are written in imperative languages. It will be
interesting to see how large functional programs will fare in comparison
- functional http servers that I have seen are in the "lean and mean"
category, and while they didn't offer the full feature set of their
imperative relatives, they still had quite a substantial feature set.
I think it's easier to say that, in functional languages, the memory
issues to consider are more uniform and easier to think about. I mean
that I don't have to worry about sharing when laying out my data
structures, which means there's one design constraint less to consider.
Hung Jung Lu
> Hung Jung Lu wrote:
> > In functional language, you by default do not think about memory
> > usage.
>
> Sorry, this is nonsense. Functional programmers do think about memory
> usage - else they wouldn't care about tail call optimization.
>
I said BY DEFAULT. You must have skip those two words. Functional
programmers do worry about memory usage, that's why they have to come
up with tail-call optimization. That does not sound like DEFAULT to
me. That sounds to me as the default was not good enough so they had
to find a way to do implement variables/states and imperative
programming in a functional language.
I have already said that if you consider an imperative program written
in a functional programming language to be a functional program, there
is nothing I can do about that. Tail-call optimization (meaning
re-using the same memory slot, or what you would call "accumulator")
is imperative programming. It's stateful. It's using variables. What
you call the "accumulator" is nothing but a variable in imperative
programming.
What do you call a memory slot that contains values that you can
assign to? It's a variable. It's a state. It's imperative programming.
If it looks like a duck, walks like a duck, quacks like a duck, smells
like a duck, IT'S A DUCK.
------------------
I am not criticizing functional programming in general. It's great for
many math problems. In fact, for many of these problems, the growing
stack is the virtue of functional programming: the language is making
your life easier as a programmer. It recurses for your benefit. But
not to realize that when you do tail-call optimization you are
effectively using variables/states and doing imperative programming,
that's beyond me.
regards,
Hung Jung
Marcin 'Qrczak' Kowalczyk
> I'm sure about Haskell, but AFAIK, Ocaml (and most schemes) uses "boxed
> types", that is some bits of the machine word are used for flags. So,
> unless I miss something,the simple arithmetic in Ocaml will be inevitably
> slower. (unbox, do the math, box again).
OCaml uses a single tag bit to box immediate values, which include ints
and constants with the same representation as ints (which are
indstinguishable at runtime).
Many common arithmetic operations can be thus done directly on boxed
representations. Addition, subtraction, multiplication by a constant,
bitwise "and" and "or", comparisons, indexing of an array - all can be
done with at most an extra adjustment by a constant.
It gets worse for floats or nativeints, which in general must be allocated
on the heap. In simple cases OCaml manages to works on their unboxed
representations.
OCaml doesn't do any overflow checks for arithmetic, and array bounds
checks can be turned on or off.
In GHC all standard values are pointers to heap-allocated objects (or
statically allocated objects peraps), because of laziness - all types must
allow for the possibility of the value not being computed yet. There are
also GHC-specific unboxed types of varying sizes which are used internally
to implement these types. They are somewhat second-class types: ordinary
type variables can't be instantiated to them and they are always evaluated.
The optimizer tries hard to rearrange the code to manipulate these unboxed
values directly when possible. It's much more sophisticated than OCaml's,
but also has a harder task - because of laziness, because of monadic I/O,
because of overloading, and possibly other issues which would be slow when
implemented naively. When GHC succeeds with unboxed values, they correspond
directly to C ints and doubles.
The Int type also doesn't do overflow checks. Array access is checked but
arrays are rare in Haskell. There is a type Integer whose representation
uses GMP for numbers which can't be represented in a machine word. Because
there are two possible representations, Integers are not passed unboxed.
--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Matthias Blume
> Tail-call optimization (meaning re-using the same memory slot, or
> what you would call "accumulator") is imperative programming.
You obviously don't even know what you are talking about.
"Accumulator" refers to a programming technique that can turn non-tail
recursion into tail recursion. Tail-call optimization, on the other
hand, is a technique employed by *compilers* to implement the latter
efficiently. Accumulators have absolutely nothing to do with
imperative programming. There is no state, there are no assignments.
It is all about where the recursive calls are in your purely
functional program.
> It's stateful. It's using variables. What you call the "accumulator"
> is nothing but a variable in imperative programming.
This is true (at best) only if leveled at "tail-call optimization",
i.e., something that the compiler does. Tail recursion is *not*
imperative, there are no assignments, and no variables that could
possibly be assigned to. (But, yes, the compiler might represent
those immutable variables using mutable memory cells or registers.
But that is not the point.)
> But not to realize that when you do tail-call optimization you are
> effectively using variables/states and doing imperative programming,
> that's beyond me.
Again, tail-call optimization is something that the compiler does, not
the programmer. The programmer just has to make sure that there are
tail calls to be optimized. At the level of the programming
language's semantics *there is no state*. Of course, there is state
on a real machine, but that is always true and has nothing to do with
the issue at hand.
Not to realize this, that's beyond me.
Vasile Rotaru
> On Mon, 12 Jan 2004 09:10:27 +0100, Vasile Rotaru wrote:
>
>> I'm sure about Haskell, but AFAIK, Ocaml (and most schemes) uses
>> "boxed
>> types", that is some bits of the machine word are used for flags. So,
>> unless I miss something,the simple arithmetic in Ocaml will be
>> inevitably slower. (unbox, do the math, box again).
>
> OCaml uses a single tag bit to box immediate values, which include ints
> and constants with the same representation as ints (which are
> indstinguishable at runtime).
>
> Many common arithmetic operations can be thus done directly on boxed
> representations. Addition, subtraction, multiplication by a constant,
> bitwise "and" and "or", comparisons, indexing of an array - all can be
> done with at most an extra adjustment by a constant.
>
>
Yep. IIRC, the integers has the lowest bit set and (x + y) is done
as (x + y - 1), (x - y) as (x - y + 1) and so on.. So it is much less
costly than my post was suggesting.
> It gets worse for floats or nativeints, which in general must be
> allocated on the heap. In simple cases OCaml manages to works on their
> unboxed representations.
I knew Ocaml is a great language ;)
> OCaml doesn't do any overflow checks for arithmetic, and array bounds
> checks can be turned on or off.
>
>
There was recently a thread in Ocaml mailing list about some code
running faster with array bounds turned on than off
Rdgs. vasha
Brian Hurt
> Ketil Malde <ke...@ii.uib.no> wrote in message news:<egsmipp...@sefirot.ii.uib.no>...
> > Lex Spoon <l...@cc.gatech.edu> writes:
> >
> > > That argument fails if all of your memory is cache. :) Some people
> > > blow millions in order to get the fastest possible results....
> >
> > And the more millions you blow, the deeper is the cache hierarchy.
> > Are you aware of any modern computer (outside of wrist watches or
> > remote controls and the like) that doesn't have a hierarchical memory?
> >
>
> Which brings me to the memory issue. Functional languages seem to
> require more memory. To give a simple example, consider the
> calculation of n! (n factorial). In imperative languages, the memory
> usage is constant, independent of n. In functional languages, memory
> usage increases with n. Unless something special is done, n! means n
> recursive calls, which piles up the calling stack. (If you cache the
> result, sure, it's faster, but RAM usage problem stays.)
This is not true. A constant-memory purely-functional implementation
of n! in Ocaml:
let fact n =
let rec loop i s =
if (i < n) then
loop (i +. 1) (s *. i)
else
s
in
loop 0. 1.
;;
Functional programs *allocate* memory a heck of a lot faster than
imperitive programs, but that memory becomes garbage at an equally
fast rate, meaning overall memory usage is constant.
>
> The original poster talked about "math heavy" problems. In numerical
> methods involving matrices, people really go out of their ways to
> reduce/re-use/recycle RAM memory slots. Special numerical methods have
> been devised to circumvent memory constraints. It's not unusual to use
> megabtyes or gigabytes for matrix operations. In functional approach,
> if one is not careful, I think memory usage can really get out of
> control. For instance, all spreadsheet programmers I know sooner or
> later are hit with memory problems, and instead of using functional
> programming (spreadsheet formulas) they all have to switch to
> imperative programming (macros/modules) at some point.
I can't speak to spreadsheet programming- it's not something I do a
lot of. I suspect that part of the problem is that space for
intermediate calculations can't be reused in spreadsheets. Once you
use space C-12 for one intermediate calculation, you can't reuse it
for another calculation, nor can the spreadsheet throw it away, as it
has to display it. This is not a problem with functional programming
languages like Ocaml and Haskell.
I can almost quote chapter and verse of what you're thinking of- just
about every discussion of (for example) LU decomposition includes the
standard tricks for doing it in place. Now, go read this paper:
http://citeseer.nj.nec.com/bodin94cache.html
The highest performing algorithms for dense matrix operations actually
approach the functional- you recursively copy sub-portions of the
matrix into newly allocated buffers and then operate on the copies.
Now, consider the case where you have a sparse matrix- that the most
efficient data structure is not a two dimensional array...
Joachim Durchholz
> I am not criticizing functional programming in general. It's great for
> many math problems.
This is just the same kind of logic as assuming that OO languages are
great for simulation.
Yes, functional languages are suitable for mathematics. But that's just
a small part of what FPLs are good for.
I left the rest of your post snipped and unanswered because it seems
that no amount of arguing will make you check your assumptions. Doing
otherwise would have been a waste of my, your, and any readers' time.
I can recommend Paul Hudak's "The Haskell School of Expression". It will
clear up most of the basic misunderstandings, and I'll be glad to answer
any questions that remain after you have read it.
Hung Jung Lu
>
> Again, tail-call optimization is something that the compiler does, not
> the programmer. The programmer just has to make sure that there are
> tail calls to be optimized. At the level of the programming
> language's semantics *there is no state*. Of course, there is state
> on a real machine, but that is always true and has nothing to do with
> the issue at hand.
>
That much everyone knows and agrees upon.
"Tail-call optimization is something that the compiler does", sure.
But you have to re-write your program in order to be able to take
advantage of TCO (Tail-Call Optmization). Let us see it with one case.
Take the Finabonacci example. The functional version will take you
just a few seconds to write. Now try to write it in the "accumulator"
version. Better, try the general Fibonacci case:
f[n] = f[n-7] + f[n-13],
the functional version takes a few seconds to write (give yourself
some trivial initial conditions.) Have a stopwatch and time yourself
how much longer it takes you to write the "accumulator" version so
that you can use TCO. And why stop there, write next the program:
f[n] = f[n-k] + f[n-m]
for any given k, m (with initial conditions filled by k, m in
analytical way.)
Done? Now, every bad word that you can say about imperative
programming (harder to write, harder to debug, usage of
states/variables) you have in front of your eyes. Do you call your
"accumulator" version the DEFAULT FUNCTIONAL VERSION? I don't. I call
the one-liner, non-accumulator version that you can write in a few
seconds the DEFAULT FUNCTIONAL VERSION. Your accumulator version,
(sorry to point out again to you,) walks, looks, smells, and quacks
like an IMPERATIVE VERSION. Now, if you do not even turn on the TCO
optimization to make it really imperative, you are beyond any cure.
(Why bother writing a much more complicated program only to have more
memory problems than before? Masochism?)
There is no free lunch. It's not like you turn on the TCO switch and a
functional program will automatically be stack finite. No way Jose.
You, the human programmer, is the one that has to sweat through
writing the "accumulator/imperative" version.
The mistake I have seen here is that people tend to assume that
re-writing the "accumulator" version is a triviality, and that TCO
will come to save you in memory usage. No way Jose. When you write the
"accumulator" version, your originally pretty and elegant functional
program is trashed and your program is now NO EASIER to write than in
an imperative language. That's what I mean by asking why you'd insist
in doing your laundry with a dishwasher machine. If you want to write
an imperative program, use an imperative language.
If you recall the original topic at all, I was talking about memory
usage in "math heavy" programs. Almost by tautology, a re-used memory
slot means a variable/state and you are force into imperative
programming style (the "accumulator" version, not the original
one-liner functional version). Turning on the TCO optimization won't
save you memory, at all, unless you are the one that has sweat through
re-writing the program to use it. And in doing so, you are doing all
the bad thing that FPer disdain about IP.
So, coming back to the original poster's question: Is functional
programming good for math heavy problems? Maybe. But you may walk into
a dangerous minefield when memory is a concern, And if memory is
definitely a concern, it's probably easier just to use an imperative
language. Do your laundry with a laundry machine, not a dishwasher.
Similary, do your dishes with a dishwasher, not a laundry machine.
regards,
Hung Jung
Tak To
TT> My question is, is there a typical or natural fashion for FP
TT> in general? If not, and one cannot compare the typicals of
TT> the two programming paradigms, what can one compare? (Note
TT> that I am talking about paradigms, not languages.)
Darius wrote:
Da> Using tail-recursion to express iteration is both typical and
Da> natural for FP. When the algorithm is not iterative using a
Da> (non-tail) recursive solution is both typical and natural for
Da> FP -and- for most imperative languages.
By the same token, tail-recursion should be typical and natural
for imperative languages as well.
Btw, it isn't clear if you are talking about languages or
paradigms.
In any case, it seems what you are saying is that since what
is typical and natural depends on the specific problem for both
paradigms, that is really nothing "in general" to compare about.
Tak To
> FPL records tend to be
> far smaller than imperative ones, simply because there is no incentive
> to aggregate as much data as possible into each record. Personally, I
> find those smaller-grained objects are usually the better, more
> maintenance-friendly design, but that's just my personal view.
Btw, smaller chunks implies higher linkage overhead. A linked list
of N integers uses (N-1)*sizeof(pointer) more bytes than a contiguous
array. Flexibility costs time and memory.
> When it comes to large programs, the imperative version will have to
> copy lots of data, just to avoid inadvertently modifying shared data.
> Functional languages don't need to copy that data.
See above.
Lauri Alanko
[On a tail-recursive fibonacci function:]
> Done? Now, every bad word that you can say about imperative
> programming (harder to write, harder to debug, usage of
> states/variables) you have in front of your eyes.
Harder to write, yes. Harder to debug, not really, since a decent
implementation will retain (some) TCO'd stack frames when debugging. And
there is _no_ state at the language level.
Clearly you haven't heard nearly _every_ bad word about imperative
programming...
> Do you call your "accumulator" version the DEFAULT FUNCTIONAL VERSION?
> I don't. I call the one-liner, non-accumulator version that you can
> write in a few seconds the DEFAULT FUNCTIONAL VERSION.
You are free to call it whatever you like. The fact is, however, that
the tail-recursive version is the one that any seasoned functional
programmer will write by _default_ unless it is known that the function
will only be called with very small arguments.
Your "default" version is admittedly the one that is the easiest to
write and understand. One of the great things about FP is that such
beautiful programs _can_ also be expressed when efficiency is not an
issue. But the easiest version is rarely the most efficient. This holds
in _all_ programming, not just FP.
> There is no free lunch. It's not like you turn on the TCO switch and a
> functional program will automatically be stack finite. No way Jose.
You can transform any program into continuation passing style and thus
make it tail-recursive. Then it won't need any stack at all. Of course
CPS just trades heap for stack, and to transform a non-tail-recursive
program into a tail-recursive one with actually lower space requirements
requires human reasoning, in this case applying knowledge about the
algebraic properties of arithmetic operations.
> You, the human programmer, is the one that has to sweat through
> writing the "accumulator/imperative" version.
Indeed. No one has claimed that writing efficient code is completely
effortless.
> The mistake I have seen here is that people tend to assume that
> re-writing the "accumulator" version is a triviality, and that TCO
> will come to save you in memory usage. No way Jose.
It is more trivial than converting to imperative style where there are
only loops and no TCO. No one has claimed that FP is panacea. Only that
it has certain advantages over imperative style.
> When you write the "accumulator" version, your originally pretty and
> elegant functional program is trashed and your program is now NO
> EASIER to write than in an imperative language.
What is this claim based upon? All imperative control structures are
fairly straightforward to express using tail calls. However, expressing
arbitrary tail calls in constant space in an imperative language
requires the use of trampolines or other hairy gadgets.
> If you recall the original topic at all, I was talking about memory
> usage in "math heavy" programs. Almost by tautology, a re-used memory
> slot means a variable/state
This is where you have a deep confusion between the semantics of the
language and its implementation.
> and you are force into imperative programming style (the "accumulator"
> version, not the original one-liner functional version). Turning on
> the TCO optimization won't save you memory, at all, unless you are the
> one that has sweat through re-writing the program to use it. And in
> doing so, you are doing all the bad thing that FPer disdain about IP.
No. Please spend some time learning exactly what the bad things about IP
actually _are_. You might begin with the concept of "state".
Lauri Alanko
l...@iki.fi
Ketil Malde
> Tail-call optimization (meaning re-using the same memory slot, or
> what you would call "accumulator") is imperative programming. It's
> stateful. It's using variables. What you call the "accumulator" is
> nothing but a variable in imperative programming.
So, in your point of view, the programming paradigm is a feature of
the set of compiler optimizations? A given program is functional as
long as I don't compile it with -O, but compiled with optimization,
it's imperative?
Why do you think this a useful distinction?
And aren't all languages "imperative", since they are eventually
turned into machine code, which works by modifying state?
-kzm
--
If I haven't seen further, it is by standing in the footprints of giants
Darius
hungj...@yahoo.com (Hung Jung Lu) wrote:
> your program is now NO EASIER to write than in
> an imperative language.
You have it backwards. The program is NO -HARDER- to write than in an
imperative language. Worse case scenario, using monads, in a pure
language, or true mutable state etc,in an impure language, I could write
it -exactly- as it would be written in an imperative language.
You've argued that an optimal functional program takes more effort than
a non-optimal one, but no one disagrees with that. To make any point
you have to show that the optimal functional program takes more effort
and is less maintainable than the optimal (or equivalent) imperative
program, otherwise one should -still- use a functional language. With
statements like the following, you simply sound ridiculous.
> Now, every bad word that you can say about imperative
> programming (harder to write, harder to debug, usage of
> states/variables)
Imperative programming gives me all this and more! Wow, I should jump
right in now*. (And as Lauri said this is hardly "every" bad word that
one can say.)
> The mistake I have seen here is that people tend to assume that
> re-writing the "accumulator" version is a triviality,
But re-writing to a for-loop with an accumulator is trivial... ?
> "accumulator" version, your originally pretty and elegant functional
> program is trashed and
Another great benefit of imperative programming: -All- my programs can
be ugly, inelegant, and "trashed"!
* Actually, functional programmers seem to be the (much) more
"multi-lingual"/multi-paradigm group out of the two. I know that -I've-
certainly done more imperative programming than functional.
Jerzy Karczmarczuk
> ...write next the program:
>
> f[n] = f[n-k] + f[n-m]
>
> for any given k, m (with initial conditions filled by k, m in
> analytical way.)
>
> Done? Now, every bad word that you can say about imperative
> programming (harder to write, harder to debug, usage of
> states/variables) you have in front of your eyes. Do you call your
> "accumulator" version the DEFAULT FUNCTIONAL VERSION? I don't. I call
> the one-liner, non-accumulator version that you can write in a few
> seconds the DEFAULT FUNCTIONAL VERSION. Your accumulator version,
> (sorry to point out again to you,) walks, looks, smells, and quacks
> like an IMPERATIVE VERSION.
Aha.
Now I know.
According to Monsieur Hung Jung Lu a DEFAULT functional programmer
is a brainless idiot, who *must* write by default inefficient programs.
Statelessness, lack of side-effects, etc., all this is irrelevant, what
count as DEFAULT according to HJL is the most trivial implementation of
recurrent mathematical formulae.
> Do your laundry with a laundry machine, not a dishwasher.
> Similary, do your dishes with a dishwasher, not a laundry machine.
Thank you generously for your advice, seriously. I will.
Now my turn to give you an advice:
Please learn how to distinguish laundry from dishes.
Jerzy Karczmarczuk
Tomasz Zielonka
>
> Take the Finabonacci example. The functional version will take you
> just a few seconds to write. Now try to write it in the "accumulator"
> version. Better, try the general Fibonacci case:
>
> f[n] = f[n-7] + f[n-13],
>
> the functional version takes a few seconds to write (give yourself
> some trivial initial conditions.) Have a stopwatch and time yourself
> how much longer it takes you to write the "accumulator" version so
> that you can use TCO. And why stop there, write next the program:
>
> f[n] = f[n-k] + f[n-m]
>
> for any given k, m (with initial conditions filled by k, m in
> analytical way.)
Here is my solution in Haskell.
f :: Num n => [n] -> Int -> Int -> Int -> n
f init k m n = foldl' seq 0 (take (n+1) xs)
where
ilen = length init
xs = init ++ zipWith (+) (drop (ilen - k) xs) (drop (ilen - m) xs)
It took me about 4 minutes to write.
It doesn't use accumulators.
It uses infinite list, but works in constant space.
Time complexity is O(n).
(Assuming that you use machine word Ints, not unbounded Integers)
I admit that because of non-strict nature of Haskell I had to make one
workaround:
foldl' seq 0 (take (n+1) xs)
instead of simply
xs !! n
But it's non-strictness that allows me to express this function in such
a nice way.
You can get traditional fibonacci function with
fib n = f [0,1] 2 1 n
Now I would like to see your default imperative solution for this
problem.
> Done? Now, every bad word that you can say about imperative
> programming (harder to write, harder to debug, usage of
> states/variables) you have in front of your eyes.
O yes, I really don't want to write it this harder way :)
> Your accumulator version, (sorry to point out again to you,) walks,
> looks, smells, and quacks like an IMPERATIVE VERSION.
Some comments about imperativeness of TCO...
Tail call optimisation is quite different from typical imperative loops
and assignments. First - it gives you freedom to 'tail call' any
function, not just looping in one place. This way you can easily express
State Machines in FP. Some parser generators are using this technique.
The second thing is something that most imperative languages don't give
you - parallel assignment. With TCO you can emulate it. Parallel
assignments allow to express some algorithms more clearly. For example
in OCaml I would write fib as:
let fib =
let rec fib_acc a b n =
if n == 0 then
a
else
fib_acc b (a+b) (n-1)
in
fib_acc 0 1
In typical imperative language you will have to think for a moment how
to properly do
(a, b) := (b, a + b)
You can't just do
a = b; b = a + b
or
b = a + b; a = b
The third thing is something that you constantly neglect. TCO fits well
in functional semantics. Your program is still functional, referentially
transparent and amenable to equational reasoning.
> There is no free lunch. It's not like you turn on the TCO switch and a
> functional program will automatically be stack finite. No way Jose.
Oh dear, and I thought all my programs will fit in one byte of memory...
> The mistake I have seen here is that people tend to assume that
> re-writing the "accumulator" version is a triviality, and that TCO
> will come to save you in memory usage. No way Jose. When you write the
> "accumulator" version, your originally pretty and elegant functional
> program is trashed and your program is now NO EASIER to write than in
> an imperative language.
If "accumulator" version is difficult, ugly, inelegent - don't write it
this way!
> That's what I mean by asking why you'd insist in doing your laundry
> with a dishwasher machine. If you want to write an imperative program,
> use an imperative language.
OK, but if I can choose my imperative language, I choose Haskell :)
Regards,
Tomasz
--
.signature: Too many levels of symbolic links
Adrian Hey
> Darius wrote:
> Da> Using tail-recursion to express iteration is both typical and
> Da> natural for FP. When the algorithm is not iterative using a
> Da> (non-tail) recursive solution is both typical and natural for
> Da> FP -and- for most imperative languages.
>
> By the same token, tail-recursion should be typical and natural
> for imperative languages as well.
It should be, but unfortunately it isn't because very few (I.E non that I'm
aware of*) imperative languages mandate tail call (last call) optimisation.
There's nothing to stop programmers using tail recursion despite this, but
it will use more stack space than traditional loops.
BTW, the reason it's hard for imperative language compilers to do this
safely is that it requires the callers stack frame to be deallocated
before calling (jumping to) the last callee. If the last callee makes use of
pointer references to the callers stack frame this will break the program.
*Actually the proposed c-- does do this, but it requires explicit annotation
IIRC, it's not done by default.
Regards
--
Adrian Hey
Jerzy Karczmarczuk
who wrote:
>>write next the program:
>>
>>f[n] = f[n-k] + f[n-m]
>>
>>for any given k, m (with initial conditions filled by k, m in
>>analytical way.)
>
>
> Here is my solution in Haskell.
>
> f :: Num n => [n] -> Int -> Int -> Int -> n
> f init k m n = foldl' seq 0 (take (n+1) xs)
> where
> ilen = length init
> xs = init ++ zipWith (+) (drop (ilen - k) xs) (drop (ilen - m) xs)
>
> It took me about 4 minutes to write.
...
>
> I admit that because of non-strict nature of Haskell I had to make one
> workaround:
...
********************************************
I don't like too much 'abstract', 'academic' examples. Let's play with
something more concrete.
The Karplus-Strong algorithm which generates the sound of a plucked
string (base of guitar, harpsichord, etc. simulation).
You must construct a long table which will hold the entire played wave
pattern. An initial segment of length k (dependent on the frequency of
the sound) is filled with random noise. Then you apply a recurrent itera-
tive formula:
s[n] = 1/2 ( s[n-k] + s[n-k+1] )
(The wildly oscillating values average out, and the sound gets rid almost
immediately of the spurious high frequencies; what remains is mainly the
wave whose period is of the order of k (and its multiples)).
The iterative solution is not so difficult, but the advantage of 'default'
lazy streaming approach to such problems is that you *have a sound process
as an object*. Here is the sketched solution in Clean or Haskell:
karstrong freq = s where
s = take (toInt (SamplRatio/freq)) noise ++
0.5 *> (s <+> (tl s))
(x *>) = map (x *)
(<+>)= zipWith (+)
Here noise is an infinite list of random values, constructed as a two-liner,
from a basic random generator (seed transformer), and SamplRatio is a global
constant, say 21000.0 . This is my way to Default Functional Programming...
Jerzy Karczmarczuk
Brandon J. Van Every
No I haven't. Having found http://www.dtek.chalmers.se/groups/icfpcontest/,
I will take a gander.
--
Cheers, www.indiegamedesign.com
Brandon Van Every Seattle, WA
"Desperation is the motherfucker of Invention." - Robert Prestridge
Matthias Blume
> Turning on the TCO optimization won't
> save you memory, at all, unless you are the one that has sweat through
> re-writing the program to use it. And in doing so, you are doing all
> the bad thing that FPer disdain about IP.
You clearly don't even know what "FPer disdain about IP".
> So, coming back to the original poster's question: Is functional
> programming good for math heavy problems? Maybe. But you may walk into
> a dangerous minefield when memory is a concern,
In your stupid fibonacci example (fibonacci is always the most stupid
example that people can come up with when they talk about FP, the
second most stupid being factorial), it is not even the memory
problem. The problem there is really time complexity, with the
accumulator version having linear complexity (in the magnitude of the
argument) whereas your so-called "default" functional version is
exponential and therefore completely impractical.
In the case of fibonacci or factorial, the imperative version is
actually fine because many decent compilers will internally turn it
into its functional (accumulator) equivalent. In the real world,
people's programs don't consist of fibonacci and factorial, and the
particular kinds of problems you see simply don't exist there.
And one more thing: With a bit of practice, writing a tail-recursive
version of a function, where possible, is no big deal and comes
completely naturally. It has very little in common with writing an
imperative program. The result is usually still far easier to analyze
and maintain.
Hung Jung Lu
> >
> > f[n] = f[n-k] + f[n-m]
> >
>
>
> f :: Num n => [n] -> Int -> Int -> Int -> n
> f init k m n = foldl' seq 0 (take (n+1) xs)
> where
> ilen = length init
> xs = init ++ zipWith (+) (drop (ilen - k) xs) (drop (ilen - m) xs)
>
Where are your input values? Here is my solution in Python:
(n, k, m) = (1000, 7, 11)
buf = range(m) # initial conditions
for i in xrange(m, n):
result = buf[i%m] = buf[(i-k)%m] + buf[(i-m)%m]
A fully working program. Which gives
result=34273081452658094466349545061643234. Which I cut and pasted as
soon as I finish writing the program.
> O yes, I really don't want to write it this harder way :)
You have written a program that doesn't even run and give a result. In
what sense does it improve/differ over my imperative version?
>
> In typical imperative language you will have to think for a moment how
> to properly do
>
> (a, b) := (b, a + b)
>
> You can't just do
> a = b; b = a + b
> or
> b = a + b; a = b
Oh yeah? What about
result, prev = 1, 0
for i in xrange(2, 100):
result, prev = result+prev, result
? It runs and give result=218922995834555169026. What's your point?
> The third thing is something that you constantly neglect. TCO fits well
> in functional semantics. Your program is still functional, referentially
> transparent and amenable to equational reasoning.
No question about that. Everyone knows. But if you look at your
general Fibonacci and my program, tell me that they don't look alike
in complexity and structure. If you pause to think why it's not
one-liner like "fib n = f [0,1] 2 1 n", it's because you were aiming
towards re-using memory. If you are given a functional language,
that's what you would do. But the original poster was/is not forced to
use functional languages.
> Oh dear, and I thought all my programs will fit in one byte of memory...
You may laugh at it all you want, but that's precisely Intel's MKL
(Math Kernel Library) people do. They optimize down to machine bit
level. Why? Because they know other people depend on them.
> If "accumulator" version is difficult, ugly, inelegent - don't write it
> this way!
True, but it saves memory. That's what imperative programmer do all
the time.
> OK, but if I can choose my imperative language, I choose Haskell :)
And keep dreaming that one day MKL/BLAS/EISPACK/LAPACK/LINPACK will be
written in a functional language. We were talking about math heavy
problems, remember?
C/C++ have outlived my wildest expectations. Unless microprocessors
change fundamentally, these language may continue to enjoy longevity.
I know there is a niche of FPer. I also know that people are working
on reversible computing, both on hardware and software side. But in
the real world, there has been no break-throughs to change the way how
people program. Sad but true.
Hung Jung
Tomasz Zielonka
> Tomasz Zielonka <t.zie...@zodiac.mimuw.edu.pl> wrote in message news:<slrnc07ggf.e...@zodiac.mimuw.edu.pl>...
>> >
>> > f[n] = f[n-k] + f[n-m]
>> >
>>
>> Here is my solution in Haskell.
>>
>> f :: Num n => [n] -> Int -> Int -> Int -> n
>> f init k m n = foldl' seq 0 (take (n+1) xs)
>> where
>> ilen = length init
>> xs = init ++ zipWith (+) (drop (ilen - k) xs) (drop (ilen - m) xs)
>>
>
> Where are your input values? Here is my solution in Python:
You said for _any_ given n, k, m. I thought you asked for a generic
solution. For your n,k,m and initial conditions:
let (n,k,m) = (1000,7,11) in
f [0 .. fromIntegral (max k m) - 1] k m n
> (n, k, m) = (1000, 7, 11)
> buf = range(m) # initial conditions
> for i in xrange(m, n):
Shouldn't it be
for i in xrange(m, n+1):
?
> result = buf[i%m] = buf[(i-k)%m] + buf[(i-m)%m]
If you switch k and m values your program stops working. You didn't say
that m >= k.
> A fully working program. Which gives
> result=34273081452658094466349545061643234. Which I cut and pasted as
> soon as I finish writing the program.
Shouldn't it rather be 37069509526581508880182715902878625 ?
>> O yes, I really don't want to write it this harder way :)
>
> You have written a program that doesn't even run and give a result. In
> what sense does it improve/differ over my imperative version?
In that it's correct and contains less hidden assumptions? :)
> result, prev = 1, 0
> for i in xrange(2, 100):
> result, prev = result+prev, result
> ? It runs and give result=218922995834555169026. What's your point?
I don't consider Python to be a typical imperative programming language.
You don't have that in C, C++, Pascal and Java, do you?
(Well, in C++ you can probably use some 'tie' mechanism to emulate it.)
> Hung Jung
Best regards,
Tom
Graham Matthews
> programming good for math heavy problems? Maybe. But you may walk into
> a dangerous minefield when memory is a concern, And if memory is
> definitely a concern, it's probably easier just to use an imperative
> language. Do your laundry with a laundry machine, not a dishwasher.
> Similary, do your dishes with a dishwasher, not a laundry machine.
All this stuff about tail-call optimisation is a total red-herring. Here
is factoral written in the purely functional language Sisal,
factorial(n:integer) =
initially
fact = 1
in for i = 1 to n do
new fact = fact * i
returns fact;
No tail call optimisation needed. Totally natural Sisal etc etc.
Oh yeah and it runs in the same time and space as any imperative
program for factorial.
This whole argument about functional languages and memory is
total nonsense. It's based on the assumptions that
functional => recursion => stack space
None of these implications are correct.
graham
Joachim Durchholz
> This whole argument about functional languages and memory is
> total nonsense. It's based on the assumptions that
>
> functional => recursion => stack space
>
> None of these implications are correct.
The "functional => recursion" implication is correct, in a sense:
Everything that looks iterative will have to be implemented using a
recursion somewhere. So, from a library writer's perspective, the
implication is correct.
From an application programmer's perspective, there isn't much
noticeable recursion going on. When he needs to iterate over a
collection he'll simply call the appropriate function (which does all
the recursion for him), so there's no explicit recursion in 90% of
application code.
I find it a bit unfortunate that most courses on functional programming
begin with a heavy dosage of recursion and try to teach a "recursive
mindset". I think that a mindset of "map inputs to outputs" would be
more appropriate. (Of course, recursion will have to be tackled sooner
or later, but /starting/ with recursion seems to be a sure way to place
functional programming as something fit for the ivory tower in the
students' minds...)
Darius
Joachim Durchholz <joachim....@web.de> wrote:
> Graham Matthews wrote:
> > This whole argument about functional languages and memory is
> > total nonsense. It's based on the assumptions that
> >
> > functional => recursion => stack space
> >
> > None of these implications are correct.
>
> The "functional => recursion" implication is correct, in a sense:
> Everything that looks iterative will have to be implemented using a
> recursion somewhere.
Why? It's perfectly reasonable to provide iterative combinators as
primitives. Nothing requires a functional language to have recursion at
all. (Which isn't to say it (and HOFs and TCO) hasn't become a
characteristic of functional languages.)
Garry Hodgson
> Tomasz Zielonka <t.zie...@zodiac.mimuw.edu.pl> wrote in message news:<slrnc07ggf.e...@zodiac.mimuw.edu.pl>...
<haskell version omitted>
> You have written a program that doesn't even run and give a result. In
> what sense does it improve/differ over my imperative version?
you seem to be trying exceptionally hard not to understand anything
anyone is saying to you.
----
Garry Hodgson, Technology Consultant, AT&T Labs
Be happy for this moment.
This moment is your life.
Albert Lai
> When it comes to large programs, the imperative version will have to
> copy lots of data, just to avoid inadvertently modifying shared
> data. Functional languages don't need to copy that data.
This is particularly important in backtracking algorithms, e.g.,
searching through part of a game tree, where you must save the
original state for backtracking. An imperative coding must contain
one explicit statement for the copying and another for the change; a
functional coding contains just one expression, and both copying and
changing are done. While both codings may run at the same speed, the
imperative coding is more error-prone --- you will forget to copy at
one place when you write it the first time, and inductively every time
you add features to the code you will also forget to copy at one
place.
Fergus Henderson
>Hung Jung Lu wrote:
>
>There's nothing in
>the definitions of FPL's to stop *executables* using destructive
>assignment (overwriting allocated storeage). But it seems to be
>a rather difficult optimisation in practice so most compilers can't
>do a very good job at the moment (if they attempt it at all).
>
>One exception to this might be Clean, but even Clean only manages
>this with the aid of programmer supplied uniqueness annotation, so
>it's a bit awkward to use.
Clean supports type inference, including inference of uniqueness annotations.
So it doesn't necessarily require any programmer supplied uniqueness
annotations.
--
Fergus Henderson <f...@cs.mu.oz.au> | "I have always known that the pursuit
The University of Melbourne | of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.
Jerzy Karczmarczuk
> All this stuff about tail-call optimisation is a total red-herring. Here
> is factoral written in the purely functional language Sisal,
>
> factorial(n:integer) =
> initially
> fact = 1
> in for i = 1 to n do
> new fact = fact * i
> returns fact;
>
> No tail call optimisation needed. Totally natural Sisal etc etc.
>
> Oh yeah and it runs in the same time and space as any imperative
> program for factorial.
No, not a red herring. This is a useful and frequent technique. But not
unique for people writing *serious* functional programs.
Matthias Blume:
> And one more thing: With a bit of practice, writing a tail-recursive
> version of a function, where possible, is no big deal and comes
> completely naturally. It has very little in common with writing an
> imperative program. The result is usually still far easier to analyze
> and maintain.
And one *more* thing. Serious and decent functional NON TAIL RECURSIVE
algorithms are also possible. In lazy languages the incremental generation
of lazy streams provides an alternative, the co-recursion replaces the
iteration, a stream emulates a process. Let's take again this silly
factorial example [apologies to Matthias...], and construct
fact = fc 1 1 where fc n f = f : fc (n+1) (f*n)
As you see, this is a non-tail-recursive algorithm for fc. It replaces
the body of the Sisal loop. (:) in a sense plays the role of "new".
But the execution of this construction is extremely cheap, in fact it
does almost nothing thanks to the non-strictness. The instantiated list
fact=[1,1,2,6,24,120, ...] will be generated when used.
Now if you need *just* n-th term of this stream, you execute a loop
with a variable i going from 0 to n (or from n to zero) which should be
tail-recursive. Something like (nth n fact), where
nth i (x:xs) |i==0 = x
|otherwise = nth (i-1) xs
as all of you know. This replaces the loop "for i= ...". Now, in a program
where one needs to process sequantially them factorials, there won't be
any such independent loops, the processing stage will *include* the
iteration of fact, and - probably - its construction will not be global,
but local, dismissing all the values already seen and processed, so there
is no memory clogging by the stream chunks.
But Maestro Hung Jung says:
> And keep dreaming that one day MKL/BLAS/EISPACK/LAPACK/LINPACK will be
> written in a functional language. We were talking about math heavy
> problems ...
Which means that he reduces the heavy math to the usage of standard style
of coding, huge matrices, etc. This is partly misleading. The issue is
delicate, one should often get to the *sources* of the problem, and
prepare its algorithmisation differently. If a scientific problem is first
casted into an imperative number-crunching algorithm with matrices etc.,
with random indexing, with loops and all that stuff, then of course
the application of functional techniques becomes difficult. But if the
original problem is *formulated* differently, one may do things much
better. I did myself some quite exotic examples...
Oh, anyway. Hung Jung says:
> C/C++ have outlived my wildest expectations. Unless microprocessors
> change fundamentally, these language may continue to enjoy longevity.
> I know there is a niche of FPer. I also know that people are working
> on reversible computing, both on hardware and software side. But in
> the real world, there has been no break-throughs to change the way how
> people program. Sad but true.
and this discourages me from following this thread. First, the world
changes, and even my friends physicists make a bit different use of Fortran
than 15 years ago. Then, I wonder... what Hung Jung is doing on this
newsgroup? Is he here just because he loves empty discussions?
Jerzy Karczmarczuk
Joachim Durchholz
> Joachim Durchholz <joachim....@web.de> wrote:
>
>> Graham Matthews wrote:
>>
>>> This whole argument about functional languages and memory is
>>> total nonsense. It's based on the assumptions that
>>>
>>> functional => recursion => stack space
>>>
>>> None of these implications are correct.
>>
>> The "functional => recursion" implication is correct, in a sense:
>> Everything that looks iterative will have to be implemented using a
>> recursion somewhere.
>
> Why? It's perfectly reasonable to provide iterative combinators as
> primitives.
Not sure how this is going to work with user-defined collection data types.
Besides, iterators tend to be over-specialized. Recursion is "more
primitive", i.e. it's easier to adapt the libraries if a new idea comes
up. And to adapt the compilers' optimization strategies if new recursion
patterns become commonplace (say somebody invents a useful way of using
Arrows, with ramifications for all the code that iterates over collections).
> Nothing requires a functional language to have recursion at all.
Agreed on that.
Graham Matthews
> Graham Matthews wrote:
> > This whole argument about functional languages and memory is
> > total nonsense. It's based on the assumptions that
> >
> > functional => recursion => stack space
> >
> > None of these implications are correct.
>
> The "functional => recursion" implication is correct, in a sense:
> Everything that looks iterative will have to be implemented using a
> recursion somewhere.
Err no. That was the point of my Sisal example. Loops can be
functional -- no need for recursion.
graham
Lex Spoon
> Lex Spoon <l...@cc.gatech.edu> writes:
>
>>> I would argue that with cache misses at 100-350 clock cycles each or
>>> more, that the prime determinate of a program's speed is it's cache
>>> friendliness.
>
>> That argument fails if all of your memory is cache. :) Some people
>> blow millions in order to get the fastest possible results....
>
> And the more millions you blow, the deeper is the cache hierarchy.
> Are you aware of any modern computer (outside of wrist watches or
> remote controls and the like) that doesn't have a hierarchical memory?
No, I'm pretty sure that with more money the best strategy is to
enlarge some layers of the hierarchy and thus eliminate the layers
beneath them. As a simple example, it would be laughable to use
disk-based virtual memory on a supercomputer; if you are paying for a
supercomputer then you will simply buy enough memory. As another
example, there's no reason to separate main memory from what what
would be L2 cache on a PC; just have a really big "L2 cache".
Now, I was mistaken about supercomputers having *no* cache, but the
reading I see still suggests that they have much fewer layers than a
workstation, and that locality of reference isn't nearly as important
as it is on a workstation. For example, here's one quote:
http://www.scd.ucar.edu/docs/dataproc/differences.html :
Codes must be optimized for cache efficiency instead of vector
efficiency. Crays use small amounts of expensive, high-speed
memory that allows multiple words to be delivered to the processor
per clock cycle. On a RISC-based computer, user codes must make
efficient use of the data in the caches to perform well. Effective
programming techniques involve keeping important pieces of data in
the cache so they can be reused. This may involve restructuring
loops, avoiding nonunit strides, and tailoring array sizes to
achieve cache efficiency. The idea is to maximize the amount of
work performed on a piece of data once it is touched before moving
on to the next piece of data.
Regarding the particulars, the specs I am seeing online suggest that
Crays have about a 2x-3x difference in cache speed and main memory
speed, much less than the (very roughly) 50x you see on workstations
between L2 and main memory.
-Lex
Joachim Durchholz
> No, I'm pretty sure that with more money the best strategy is to
> enlarge some layers of the hierarchy and thus eliminate the layers
> beneath them.
Agreed, but:
> As a simple example, it would be laughable to use
> disk-based virtual memory on a supercomputer; if you are paying for a
> supercomputer then you will simply buy enough memory.
... even supercomputer have disks. (The file system is the next layer of
hierarchy, after disk-based virtual memory.)
> As another
> example, there's no reason to separate main memory from what what
> would be L2 cache on a PC; just have a really big "L2 cache".
Right.
However, we have already begun to run into distance-induced cache levels
that were not present in prior times.
At GHz frequencies, physical distances matter because impulses travel at
about one third of light speed on copper leads.
At 1 GHz, we have a cycle time of 10e-9 seconds.
Speed of light = 300.000 m/s = 3e5 m.
On copper, this means that an impulse will travel 10e-4 meters, that's
just a single millimeter!
In other words, any memory that's farther than a millimeter away from
the CPU will be one cache level removed from the CPU.
In other words, level-1 cache (on-chip with the CPU) is there to stay.
Whatever the advances in RAM technology will be, some of that RAM will
go to the submillimeter distances that can be achieved on the CPU, and
additional memory will be placed as near as possible to the CPU.
> Now, I was mistaken about supercomputers having *no* cache, but the
> reading I see still suggests that they have much fewer layers than a
> workstation,
Sounds plausible.
Even for "normal" application servers, it can pay off to get rid of all
that disk-based stuff and simply pull the entire database into RAM. The
machine will be faster by orders of magnitude (particularly if you can
replace all that database machinery by some good RAM-based tree
algorithms), and all you have to worry about is to take a snapshot of
the system state every few minuts, and sequentially dump it out to disk
to safeguard against hardware or software failures. (This is good news
for functional languages: taking a snapshot of the system state isn't
more difficult than copying a root pointer. I shudder at the prospect at
writing snapshot software for a Java system...)
Of course, this will work only up to a certain size, e.g. a customer
base of a few thousand people. But memory sizes have been increasing
faster than the total data processed by businesses, so I expect this
window of opportunity to open more in the future. (I'm not sure whether
it will ever reach multinational corporations though... particularly
since the simple snapshotting approach isn't easily transferrable to
multiple distributed servers.)
Ketil Malde
I blatantly stated that:
>> And the more millions you blow, the deeper is the cache hierarchy.
And Lex Spoon <l...@cc.gatech.edu> responded:
> No, I'm pretty sure that with more money the best strategy is to
> enlarge some layers of the hierarchy and thus eliminate the layers
> beneath them.
Perhaps, and certainly you want to enlarge caches, but I don't see
them going away. SGI and HP are using Madisons, which has
three levels of cache on chip, and not two like most desktop CPUs.
IBM's POWER4 has two cores with separate L1 sharing L2 on chip, and
sharing L3 off chip (in MCMs).
In addition to Joachim's point about communication costs, I think
SRAM is simply too expensive, and that for most problems people want
this kind of equipment for, caches get really good hit rates.
> As a simple example, it would be laughable to use
> disk-based virtual memory on a supercomputer
Well, it's laughable to use disk-based virtual memory at all, IMHO;
certainly for any kind of performance-intensive task. The difference
in latency between a 10ms disk seek and a 100ns memory read is five
orders of magnitude. The difference between a 10ns cache and 100ns
memory is only one order of magnitude. And while (see below) the
numbers for solid state probably have improved, disks are mostly
improving in capacity, rather than latency.
> http://www.scd.ucar.edu/docs/dataproc/differences.html :
I know that Crays and other vector processors were done differently.
I'm not aware of any architectures like that being designed for at
least ten years. (Although I may of course be wrong?)
> Regarding the particulars, the specs I am seeing online suggest that
> Crays have about a 2x-3x difference in cache speed and main memory
> speed, much less than the (very roughly) 50x you see on workstations
> between L2 and main memory.
Hmmm....this contradicts my numbers above (but not enough to
invalidate my point, I think). Googling a bit, I found some numbers
for P4 and Athlon: L1 bandwidth ~12Gb/s, L2 ~6Gb/s, Memory ~1Gb/s
(although P4 reads at almost twice that, due to its use of RDRAM).
Okay, I guess this is fairly off-topic? :-)
Remi Vanicat
> Lex Spoon wrote:
>
>> No, I'm pretty sure that with more money the best strategy is to
>> enlarge some layers of the hierarchy and thus eliminate the layers
>> beneath them.
>
> Agreed, but:
>
>> As a simple example, it would be laughable to use
>> disk-based virtual memory on a supercomputer; if you are paying for a
>> supercomputer then you will simply buy enough memory.
>
> ... even supercomputer have disks. (The file system is the next layer
> of hierarchy, after disk-based virtual memory.)
>
> > As another
>> example, there's no reason to separate main memory from what what
>> would be L2 cache on a PC; just have a really big "L2 cache".
>
> Right.
>
> However, we have already begun to run into distance-induced cache
> levels that were not present in prior times.
> At GHz frequencies, physical distances matter because impulses travel
> at about one third of light speed on copper leads.
> At 1 GHz, we have a cycle time of 10e-9 seconds.
> Speed of light = 300.000 m/s = 3e5 m.
it's 300 000 km/s = 3e8 m/s not 300 000 m/s ...
> On copper, this means that an impulse will travel 10e-4 meters, that's
> just a single millimeter!
10e-4m is 0,1 millimeter, and with the correct speed of light, we have
10 centimeter, a lot of room (but not so much).
The rest of the discussion stay true, even with this adjustment.
> In other words, any memory that's farther than a millimeter away from
[...]
--
Rémi Vanicat
Tak To
> Joachim Durchholz <joachim....@web.de> writes:
>>However, we have already begun to run into distance-induced cache
>>levels that were not present in prior times.
>>At GHz frequencies, physical distances matter because impulses travel
>>at about one third of light speed on copper leads.
>>At 1 GHz, we have a cycle time of 10e-9 seconds.
>>Speed of light = 300.000 m/s = 3e5 m.
>
> it's 300 000 km/s = 3e8 m/s not 300 000 m/s ...
>
>>On copper, this means that an impulse will travel 10e-4 meters, that's
>>just a single millimeter!
>
> 10e-4m is 0,1 millimeter, and with the correct speed of light, we have
> 10 centimeter, a lot of room (but not so much).
The propagation of electric signals in copper is only about
2/3 of that of light in vacuum, i.e., about 2e8 m/s.
Joachim Durchholz
> Well, it's laughable to use disk-based virtual memory at all, IMHO;
> certainly for any kind of performance-intensive task.
True.
OTOH there are performance-intensive tasks that are still done in
disk-based ways, e.g. all kinds of data mining. These just take ages to
complete.
Just as sorting was a tape(!)-based application in the 50ies, which was
even more laughable, but still done that way for lack of cheap, fast,
large storage technology. In the 80ies, sorting was a disk-based
application, which is still laughable. Today we sort in RAM, and we
still try to keep all non-key data on disk (it's called index files
which get loaded into RAM, and data tables that are kept on disk as far
as possible).
> The difference
> in latency between a 10ms disk seek and a 100ns memory read is five
> orders of magnitude. The difference between a 10ns cache and 100ns
> memory is only one order of magnitude. And while (see below) the
> numbers for solid state probably have improved, disks are mostly
> improving in capacity, rather than latency.
This used to be true a decade ago, but disks have improved in the past
years - from 3600 RPM to 5000 RPM and above.
(That's mostly consumer disks though - I don't know what's happening in
the high-speed disk industry.)
(And: thanks to everybody for getting those speed-of-light issues
cleared up - I somehow overlooked the k prefix.)
Tomasz Zielonka
> Ketil Malde wrote:
>
>> Well, it's laughable to use disk-based virtual memory at all, IMHO;
>> certainly for any kind of performance-intensive task.
>
> True.
> OTOH there are performance-intensive tasks that are still done in
> disk-based ways, e.g. all kinds of data mining. These just take ages to
> complete.
If you are able to keep the CPU(s) busy with real work, it's fine. But
if most of the time they are waiting because of disk seeks, you're
screwed.
> Just as sorting was a tape(!)-based application in the 50ies, which was
> even more laughable, but still done that way for lack of cheap, fast,
> large storage technology. In the 80ies, sorting was a disk-based
> application, which is still laughable. Today we sort in RAM, and we
Not me. I still find it easier to sort 30 GB of data on disk, than in
memory.
> still try to keep all non-key data on disk (it's called index files
> which get loaded into RAM, and data tables that are kept on disk as far
> as possible).
Separating key from non-key data is not always a good thing to do. If
what you want to do is to iterate over all the data in the sorted order,
you may find that keeping key and non-key together is much better.
> This used to be true a decade ago, but disks have improved in the past
> years - from 3600 RPM to 5000 RPM and above.
The best average seek times are still aroung 8 ms.
By the way, with 7200 RPM it is the time of one full rotation of disks -
sometimes you just have to wait until the data gets under the head.