local variables don't cause side effects 
Author Message
 local variables don't cause side effects

Quote:



>>>if the compiler or interpreter knows that the arguments are integers, then
>>>this is the best optimization and it would be fine, if the system could do
>>>it automatically, perhaps with an integrated math CAS system for symbolic
>>>calculation.

>>It's not worth the effort. It would take more effort to teach compilers
>>to apply the right transformations, than simply to write down the
>>simpler algorithm.

> It depends -- you only have to teach the compiler once,
 > whereas the
> algorithm will be human optomized many many times, by many different
> people.

That's the usual argument, but it doesn't transfer to this specific
situation.

Let me elaborate.

First, the question is: What is it that we teach the compiler? How to
optimize this particular function, or how to optimize an entire class of
similar functions?

In the latter case, I simply contend that automatic proof generation,
identification of interesting function classes, judging the relative
merit of conflicting optimization goals and other related topics aren't
researched well enough to give conclusive answers here.

In the former case, we see that the algorithm must be known (and
considered important) by the compiler writers. Since these are (usually)
closely working with the writers of the standard libraries, they can
just tell the library guys: "Hey, this function is important enough that
we start thinking about optimizing it specially, please try to find a
better algorithm, that's probably more effective than when we let the
compiler optimize it".
In other words, it's simpler to write down the better algorithm than to
teach the compiler how to transform the bad algorithm to the better one...

Regards,
Jo



Wed, 28 Dec 2005 07:44:33 GMT  
 local variables don't cause side effects

Quote:

> It strikes me that the thing about #1 that will cause consternation in some
> people isn't functions; it's recursion.

> Probably it's been a long time since anyone here hard a hard time thinking
> about recursion, but it's a real sticking point in teaching programming.
> I don't think loops with variables produce the same level of difficulty.

Hmm.  That's very interesting.

I remember a lecturer of mine who remarked that he believed that recursion
was more natural, intuitive idea than iteration.  But since most teaching,
textbooks and beginners texts treat iteration as a lower-level concept, it
usually took a post-beginner programmer some effort to 'unlearn' a little
to feel compfortable with recursion.

I still don't know which I think of recursion or iteration to be the more
intuitive concept.

-Tez



Wed, 28 Dec 2005 10:26:38 GMT  
 local variables don't cause side effects

Quote:



> >>For one example, in an implicitly parallelizing compiler, a call to a
> >>purely functional function can be handed off to another thread; if
> >>many such calls exist in a region of code with no intermingled
> >>side-effects, then N calls can be handed off to N independent CPU's ...

> > I find this possibility fascinating.

> Don't hold your breath: home users have little if any use for that.

Everyone keeps telling me that, but I don't believe it. A simple example
(maybe metaphor would be a better word) of the benefits of parallelism in
home hardware: my living room ceiling has 6 lightfixtures in it. When a
bulb burns out, I don't care. When I'm down to three or so, I replace
a bunch of them. Substitute disk drives for bulbs in the above and
you've got an excellent reason for home users to want to use clustering.

You could argue that that's just a distributed file system, but I'd claim
a distributed file system is a clustering application. Clustering is about
more than just sharing computation; it's about sharing all machine
resources. And there's also the reliability that comes with massive
redundancy.

And I'm sure there are plenty of home applications we haven't thought
of yet that only become practical when the home has 2 or 3 orders of
magnitude more computing power than it does now. Or 5 or 6.

Quote:
> That's just a side note. The *real* problem is that handing off
> computations to a different processor often entails more work than just
> stacking the call. Compilers may try to predict which calls should be
> parallelized and which shouldn't, but mispredictions in that area will
> quickly eat up the advantages gained here.

Yes.

Quote:
> Besides, you usually don't have N processors, you have at most two.
> Maybe four, in the next five years or so - but I wouldn't bet on that.

I like to think in terms of 10^2 - 10^4 processors. But in the enterprise,
that number could be order 10^5 or even 10^6. I'm more talking about how
many CPUs you have in a building, not in a box. The right level to be
thinking at has always been at the box, but now it's time to think in
terms of the building, or maybe the campus. It's time to think outside
the box. (Sorry, couldn't resist.)

Marshall



Wed, 28 Dec 2005 10:39:44 GMT  
 local variables don't cause side effects

Quote:


> > There are people who find incarnation #1 obscure - "functions!  Now I
> > won't be able to follow which value goes to which argument and how!
> > This is all Greek to me."

> It strikes me that the thing about #1 that will cause consternation in some
> people isn't functions; it's recursion.

Yes, five minutes after I posted that, I realized it was not so much
functions as recursion that scared that category of programmers.

Quote:
> Probably it's been a long time since anyone here hard a hard time thinking
> about recursion, but it's a real sticking point in teaching programming.
> I don't think loops with variables produce the same level of difficulty.

There are several ways of teaching programming.  One way teaches how
to execute a program.  Another way teaches how to solve a problem.

Looping with variables is very easy to execute by hand.  Recursion
with parameters is harder to execute by hand, especially when the
human is not told about tail-call shortcuts.  Most programming courses
spend all their time on how to execute if-then-else, how to execute a
while loop, and how to execute recursive calls.  Therefore looping must
look simpler than recursion.

Recursion is more handy in solving problems.  To add up 10 numbers,
you just have to know how to add up 9 numbers and how to account for
the 10th.  To find a number in a sorted array of size 16, you just
have to know how to find a number in a sorted array of size 8 and how
to decide which 8.  Solving a problem by divide-and-conquer or
reduction is a natural instinct, and we do that all the time, inside
or outside programming.  In contrast, to solve a problem by looping,
the approach is either trial-and-error (which ironically is itself a
loop:

0:  clue := empty
1:  P := "while ? do ?"
2:  repeat
3:    P := genetic mutation of P using clue
4:    r := result of executing P 1 time, 2 times, "many" times
5:    d := difference between r and expectation/specification
6:    (* as a result there is always a bug when P is executed 0 times *)
7:    clue := clue U some conjectures made from d
8:  until d is empty
9:  return P

) which is tedious, error-prone, and seldom convergent; or refinement
rules based on loop invariants, which is Greek to most people.
Writing a working loop is swim-or-sink in education and dark magic in
practice.

Unfortunately as an artifact of teaching programming by execution and
not problem solving, students do not think of divide-and-conquer when
writing a recursion, but rather waste time worrying about how the
program will be executed, cornering themselves into resorting to the
above trial-and-error method, of which step 4 becomes much harder
indeed.  So writing a working recursion looks more dark magic due to
misguidance.



Wed, 28 Dec 2005 12:33:45 GMT  
 local variables don't cause side effects

Quote:

> The one thing that I've been missing for two years now is that nobody
> has yet shown a convincing example of this:
> How to write code that
> a) is (possibly heavily) imperative
> b) has a purely functional interface
> c) allows the compiler to infer (b) even in the presence of (a).

I implemented the shuffling algorithm discussed in Knuth's TAOCP v2
using the ST monad in Haskell.  It goes like this:

Parameter: list (immutable)
Return value: shuffled list (immutable)

so the interface is purely functional.

Implementation:
  Make an ST monad that does these:
    Transfer the input list into a mutable array
    Do all the random swapping as in Knuth's description
    Return the array as a list
  Run the monad

I think it fits all your requirements.

The papers on the ST monad also contain similar examples.  The
classical one is the depth-first search algorithm (input tree, output
list of nodes in depth-first order) using an internal mutable array to
remember visited nodes.



Wed, 28 Dec 2005 12:50:03 GMT  
 local variables don't cause side effects

Quote:

> In other words, it's simpler to write down the better algorithm than
> to teach the compiler how to transform the bad algorithm to the better
> one...

Sounds like: It's simpler to write down the assembler code instead of
writing a compiler for a high level language :-)

--

http://www.frank-buss.de, http://www.it4-systems.de



Wed, 28 Dec 2005 16:03:11 GMT  
 local variables don't cause side effects

Quote:


>> An equivalent point is that you can program in the imperative style in
>> Haskell provided that you use the Monad library which is still under
>> research and development.

>> And the difference is?

>That Haskell monads aren't under research anymore?

>I'm sure that there's a lot of reasearch underway concerning monads, but
>I'd be rather surprised if there were no usable, useful stable subset of
>the monad library.

There is indeed usable, useful, stable support for Monads -- all that
you need for writing programs in the imperative style -- in Haskell 98.

--

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.



Thu, 29 Dec 2005 01:13:47 GMT  
 local variables don't cause side effects

Quote:

> I still don't know which I think of recursion or iteration to be the more
> intuitive concept.

I'm not 100% decided either, but I'm leaning towards iteration as being the
simpler.

It strikes me that this question would be amenable to a modest amount of
congitive experimentation on non-programmers.

Marshall



Thu, 29 Dec 2005 02:06:59 GMT  
 local variables don't cause side effects

Quote:
>>>>> Marshall Spight wrote (on Fri, 11 Jul 2003 at 16:20):

    > Probably it's been a long time since anyone here had a hard
    > time thinking about recursion, but it's a real sticking point in
    > teaching programming.  I don't think loops with variables
    > produce the same level of difficulty.

Well, I've still a hard time thinking about recursion, after about
thirty years.  What about well-founded recursion versus co-recursion
(catamorphisms versus apomorphisms)?  What about guarded recursion
and infinite data structures? etc etc ....

At the level of teaching/learning, my impression (fwiw) is that many
people can find "recursion" extremely baffling, while others just
immediately get it, at least at a basic level.  Except for extremely
stupid or extremely _bright_ students, scarcely anyone has problems
with iteration (with loop variables).  So I agree with your last
sentence.

I speculate that it is the idea of "defining a thing in terms of
itself" which baffles people -- as perhaps it ought to.

Peter Hancock



Thu, 29 Dec 2005 03:26:32 GMT  
 local variables don't cause side effects

Quote:


>>In other words, it's simpler to write down the better algorithm than
>>to teach the compiler how to transform the bad algorithm to the better
>>one...

> Sounds like: It's simpler to write down the assembler code instead of
> writing a compiler for a high level language :-)

You snipped the most relevant part of my post:
 >>That's the usual argument, but it doesn't transfer to this specific
 >>situation.

I'd be interested to read why you disagree. This would also help me
reduce the amount of nonsense in my postings :-)

Regards,
Jo



Thu, 29 Dec 2005 04:48:05 GMT  
 local variables don't cause side effects

Quote:


>>I still don't know which I think of recursion or iteration to be the more
>>intuitive concept.

> I'm not 100% decided either, but I'm leaning towards iteration as being the
> simpler.

> It strikes me that this question would be amenable to a modest amount of
> congitive experimentation on non-programmers.

Which concept is easier to teach is an interesting question, but it
would be misleading unless we also got another question answered: which
concept takes longer to learn so that people can use it.
More concretely: Does anybody still remember how long it took him to be
on the watchout for fencepost errors in iterations? Are there similar
standard things to look for in recursion? (Off the top of my head I
remember accidentally writing nonterminating indirect recursion. Are
there other traps?)

Regards,
Jo



Thu, 29 Dec 2005 04:56:13 GMT  
 local variables don't cause side effects

Quote:

> I implemented the shuffling algorithm discussed in Knuth's TAOCP v2
> using the ST monad in Haskell.  It goes like this:

> Parameter: list (immutable)
> Return value: shuffled list (immutable)

> so the interface is purely functional.

OK.

Quote:
> Implementation:
>   Make an ST monad that does these:
>     Transfer the input list into a mutable array
>     Do all the random swapping as in Knuth's description
>     Return the array as a list
>   Run the monad

> I think it fits all your requirements.

Agreed.

I got probably misdirected by the consensus that there's no way to get
rid of the IO monad.
Which leads me to my next questions:
1. Why is it possible to run the ST monad and get a functional result,
but impossible to run the IO monad and get a functional result?
2. Is this difference a specialty of IO, or a specialty of ST?
3. Does running ST use workarounds like unsafePerformIO (which
essentially means that the compiler doesn't really infer that there's no
side effect, it just assumes that the ST implementation is correct)?

Regards,
Jo



Thu, 29 Dec 2005 05:05:05 GMT  
 local variables don't cause side effects

Quote:




>>>>For one example, in an implicitly parallelizing compiler, a call to a
>>>>purely functional function can be handed off to another thread; if
>>>>many such calls exist in a region of code with no intermingled
>>>>side-effects, then N calls can be handed off to N independent CPU's ...

>>>I find this possibility fascinating.

>>Don't hold your breath: home users have little if any use for that.

> Everyone keeps telling me that, but I don't believe it. A simple example
> (maybe metaphor would be a better word) of the benefits of parallelism in
> home hardware: my living room ceiling has 6 lightfixtures in it. When a
> bulb burns out, I don't care. When I'm down to three or so, I replace
> a bunch of them. Substitute disk drives for bulbs in the above and
> you've got an excellent reason for home users to want to use clustering.

There are several relevant differences here:
Lightbulbs are cheap. Harddisks are, by comparison, very expensive
(several 100$ vs. a few dozen cent).
It's easy to arrange the cabling so that lightbulbs are indeed
redundant. It's difficult and expensive to have redundant harddisks (you
need a RAID controller, which is still above 100$ if you want something
that works, and besides, there's still a single point of failure in the
controller itself - and getting redundant RAID controllers to work is
something that I wouldn't even try. I *could* imagine a redundant
cabling system for lightbulbs, without too much cost overhead.)

What's good is, to a large extent, a matter of cost/performance issues.

Let me give an example: Graphics coprocessors.
It all started with the special-purpose "blitter" chips in Amiga and
Atari ST computers.
Then CPUs got faster, got better bit manipulation instructions, and the
blitters died.
Then we had "graphics accelerator cards". Again, we had faster CPUs, and
we had more and larger fonts, so it wasn't *that* much of an advantage
to have the processor on the graphics card do all the font rendering on
its own - but they survived. Actually this is mostly due to the fact
that graphics needs a lot of memory bandwidth, and that this commodity
has lagged behind other commodities like CPU power. (CPU caches and L2
caches are there just because memory is so slow, not because processor
manufacturers like complicated and error-prone cache coherence protocols...)
Today, we have 3D cards. With hardwired on-board memory with (surprise!)
  *huge* memory bandwidth.
As soon as main memory catches up on bandwidth, the 3D cards will disappear.

Moral: Abstract considerations like OS structure and the usefulness of
clustering are far more sensitive to concrete pricing than would expect
at first sight.

In the case of clustering, the main problem would be the lack of cheap,
generally available short-range high-speed connections between computers
in a cluster.
Serial ATA is a step in that direction. I doubt that it's enough, and I
don't expect serial links to be up to the load of serious clustering for
the next few years. (Which is why I t expect that clustering will take
at least five years. There was a tiny litte bit of substance behind that
number *g*.)

Quote:
> You could argue that that's just a distributed file system, but I'd claim
> a distributed file system is a clustering application.

I'd agree with that claim.
It's a somewhat simple clustering application, of course - but it
already shows all the symptoms of clustering. The worst problem with
distributed file systems is the unreliability of the interconnections,
immediately followed by the (comparatively) low bandwidth of the
interconnections.
There are interesting technology around that solve at least the
bandwidth problem (serial storage bus or something), but these seem to
be too expensive to work in a home environment.

And if bandwidth is too low even for storage technology, I don't think
it will work for the higher demands of CPU-bound computations, which
further restricts the general usefulness of clustering...

Quote:
> And I'm sure there are plenty of home applications we haven't thought
> of yet that only become practical when the home has 2 or 3 orders of
> magnitude more computing power than it does now. Or 5 or 6.

Even faster framerates for ego shooters? (Just kidding)

But I don't think that lack of CPU power is a real problem. The only
serious (i.e. non-{*filter*}) application that I can think of would be
speech and image recognition. Clustering might help a bit with image
recognition, provided that the image can be split into pieces that can
be processed separately (I'm not very hopeful on that account). For
speech recognition, I see little or no gains in splitting up - there's
too much back-and-forth referencing going on in that.
All of this under the assumption that inter-box data transmission offers
at least an order of magnitude less bandwidth than intra-box data
transmission. SMP would be a different story.

Quote:
>>Besides, you usually don't have N processors, you have at most two.
>>Maybe four, in the next five years or so - but I wouldn't bet on that.

> I like to think in terms of 10^2 - 10^4 processors. But in the enterprise,
> that number could be order 10^5 or even 10^6. I'm more talking about how
> many CPUs you have in a building, not in a box. The right level to be
> thinking at has always been at the box, but now it's time to think in
> terms of the building, or maybe the campus. It's time to think outside
> the box. (Sorry, couldn't resist.)

Well, right - but "outside the box" means "less bandwidth". In other
words, you can't parallelize applications that require lots of
intra-application bandwidth. At least not that way.

Regards,
Jo



Thu, 29 Dec 2005 05:50:39 GMT  
 local variables don't cause side effects

Quote:

>At the level of teaching/learning, my impression (fwiw) is that many
>people can find "recursion" extremely baffling, while others just
>immediately get it, at least at a basic level.  Except for extremely
>stupid or extremely _bright_ students, scarcely anyone has problems
>with iteration (with loop variables).  So I agree with your last
>sentence.

We're getting off-topic here, but anyways.

I have heard this point so often by so many people, but I simply can't
beleive that. If students feel more comfortable with iteration than
recursion, than that has probably to do with how they were pre-trained.
And I don't just mean those who already programmed in high-school. What
are the kind of people going into CS or disciplines where they have to use
typical programming languages? As far as I can tell, these tend to be
people with some affection or ability in science and math.  Mathematics,
at the high-school level(!), rarely deals with induction proofs or
induction principles. They do however deal with tons of iterative
concepts, the most common probably the sum-notation. As a result, it seems
to me, they like iteration more because they have been using it over and
over again.  Does this mean that iteration is 'simpler' than 'recursion'?
I think that this is at least a dangerous conclusion.

Circumstantial evidence to the contrary comes from linguists who, in
Europe at least, often work with Prolog. They claim that prolog is
particularly easy for their students to understand and they testify that
those already familiar with common programming languages tend to have more
difficulties.  Prolog, like FPs, is recursive in nature and does not use
imperative loops. You're not going to tell me that arts students are
intrinsically more intelligent in the nature of recursion.

I conjecture that an early introduction of inductive reasoning in
high-school math would massively increase the tolerance for recursive
programming.

Regards,

        Simon



Thu, 29 Dec 2005 05:52:33 GMT  
 local variables don't cause side effects

Quote:


>> Incarnation #2:
>> triangle n = n * (n + 1) / 2

> You're beside the point.
> The discussion is about optimizing a given algorithm, not about
> replacing an algorithm with an entirely different one.

Right.  I just wanted to point out that a better example might be
chosen of algorithms to optimize.  Oh, and I enjoy being an occasional
smart-ass.

--
Aaron Denney
-><-



Thu, 29 Dec 2005 06:07:01 GMT  
 
 [ 83 post ]  Go to page: [1] [2] [3] [4] [5] [6]

 Relevant Pages 
 

 
Powered by phpBB® Forum Software