Account Options

  1. Sign in
The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Google Groups Home
« Groups Home
Message from discussion local variables don't cause side effects
The group you are posting to is a Usenet group. Messages posted to this group will make your email address visible to anyone on the Internet.
Your reply message has not been sent.
Your post was successful
 
From:
To:
Cc:
Followup To:
Add Cc | Add Followup-to | Edit Subject
Subject:
Validation:
For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon. Listen and type the numbers you hear
 
Albert Lai  
View profile  
 More options Jul 12 2003, 12:50 am
Newsgroups: comp.lang.functional
From: Albert Lai <tre...@vex.net>
Date: 12 Jul 2003 00:33:45 -0400
Local: Sat, Jul 12 2003 12:33 am
Subject: Re: local variables don't cause side effects

"Marshall Spight" <mspi...@dnai.com> writes:
> "Albert Lai" <tre...@vex.net> wrote in message news:4uznjm1dim.fsf@vex.net...
> > 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.

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


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.