Iteration vs. Recursion

[Sathyaish]

Can every problem that has an iterative solution also be expressed in
terms of a recursive solution?

I tried one example, and am in the process of trying out more examples,
increasing their complexity as I go. Here's a simple one I tried out:

#include<stdio.h>
/* To compare the the time and space cost of iteration against
recursion*/

const int SOME_CONST = 10;
void ifoo();
void rfoo(int, int, int);
int main(void)
{
ifoo();
rfoo(0, 0, 5);
printf("\n");
return 0;
}

void ifoo()
{
int i = 0, x = 0, y = 5;
for(; i < SOME_CONST; i++)
{
x += y;
printf("%d\t%d\t%d\t\n", i, x, y);
}
}
void rfoo(int i, int x, int y)
{
x += y;
printf("\n%d\t%d\t%d", i, x, y);

if (i < SOME_CONST - 1)
rfoo(++i, x, y);
}
I noted the following:

a. While iteration is linear in time and constant in space, recursion
is exponential in space.

b. Iteration preserves state, recursion does not.

[Richard Heathfield]

Sathyaish said:

Can every problem that has an iterative solution also be expressed in
terms of a recursive solution?
Yes. Iteration and recursion are just two different ways of saying "if we're
not finished yet, let's do it some more". Recursion is one way of
implementing iteration. Iteration is one way of implementing recursion.

I noted the following:

a. While iteration is linear in time and constant in space, recursion
is exponential in space.
Not necessarily. It depends what you're doing and how you're doing it.
b. Iteration preserves state, recursion does not.

It certainly /can/, if that is what is required.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Alan]

Sathyaish wrote:

Can every problem that has an iterative solution also be expressed in
terms of a recursive solution?
Matter of basic meaning of the two words.
I tried one example, and am in the process of trying out more examples,
increasing their complexity as I go. Here's a simple one I tried out:
You can not test a hypothesis merely by increasing the complexity.

#include<stdio.h>
/* To compare the the time and space cost of iteration against
recursion*/

const int SOME_CONST = 10;
void ifoo();
void rfoo(int, int, int);
int main(void)
{
ifoo();
rfoo(0, 0, 5);
printf("\n");
return 0;
}

void ifoo()
{
int i = 0, x = 0, y = 5;
for(; i < SOME_CONST; i++)
{
x += y;
printf("%d\t%d\t%d\t\n", i, x, y);
}
}
void rfoo(int i, int x, int y)
{
x += y;
printf("\n%d\t%d\t%d", i, x, y);

if (i < SOME_CONST - 1)
rfoo(++i, x, y);
}

You have shown an example of an iteration and an example of recursion. Just
because the latter performs the same as the former does not mean that EVERY
iteration can be expressed as a recursion.

The following is an iteration that cannot be expressed as a recursion

printf("%d", rand());
printf("%d", rand());
printf("%d", rand());
printf("%d", rand());
printf("%d", rand());
....

I noted the following:

a. While iteration is linear in time and constant in space, recursion
is exponential in space.

In what way? What do you mean by space? Computer memory? This statement
would seem to be meaningless.

An iterated process would not necessarily be linear in time on a
multitasking computer - which most are these days.

I think you are getting lost over a simple matter.

b. Iteration preserves state, recursion does not.

State of what? Recursion will preserve a return value. In the stack frame
of each iteration of a recursive function is preserved the "state" of the
function at that time. This would not be "exponential".

Try to simplify by going to the basic meaning of the two words -

"Iterate: repeat, state repeatedly (Latin: iterum - again)"

Iteration is a process that is repeated a number of times without
necessarily returning to anything.
Loops are iterative processes. But iteration is not necessarily confined
to loops - vide my example above.

"Recursion: the act or an instance of returning (Latin: recurrere - run
again)" Concise Oxford Dictionary.

Recursion is a process that calls itself, ie. returns to itself.
A "function" that calls itself is recursion.

The definition of the words show they are NOT synonymous - ie. things may be
repeated without necessarily involving any idea of "returning".

Simple!

Was it really necessary to cross post??

Alan

[Torben Ægidius Mogensen]

"Sathyaish" <sa*******@gmail.com> writes:

Can every problem that has an iterative solution also be expressed in
terms of a recursive solution?
Yes. The converse is true only if you allow extra variables (of
unbounded size) to be introduced, essentially emulating a recursion
stack.
I tried one example, and am in the process of trying out more examples,
increasing their complexity as I go. Here's a simple one I tried out:

#include<stdio.h>
/* To compare the the time and space cost of iteration against
recursion*/

const int SOME_CONST = 10;
void ifoo();
void rfoo(int, int, int);
int main(void)
{
ifoo();
rfoo(0, 0, 5);
printf("\n");
return 0;
}

void ifoo()
{
int i = 0, x = 0, y = 5;
for(; i < SOME_CONST; i++)
{
x += y;
printf("%d\t%d\t%d\t\n", i, x, y);
}
}
void rfoo(int i, int x, int y)
{
x += y;
printf("\n%d\t%d\t%d", i, x, y);

if (i < SOME_CONST - 1)
rfoo(++i, x, y);
}
I noted the following:

a. While iteration is linear in time and constant in space, recursion
is exponential in space.
How did you arive at that conclusion? Your rfoo function will in C
use space linear in the number of recursice calls, but even that is
only because your C compiler doesn't do tail-recursion optimisation
(which any sensible compiler will), which would make the above run in
constant space.
b. Iteration preserves state, recursion does not.

On the contrary: Iteration works by transforming state while recursion
can work by creating new local values (while preserving the global
state). That is the essense of value-oriented (functional)
programming: You never destructively overwrite values, you just create
new ones and reuse the space for the old ones only when they are
guarateed not to be used anymore.

Torben

[Richard Heathfield]

[clc restored]

Alan said:

The following is an iteration that cannot be expressed as a recursion

printf("%d", rand());
printf("%d", rand());
printf("%d", rand());
printf("%d", rand());
printf("%d", rand());
....

void pewtinace(int i) /* Please Explain Why This Is Not A Counter-Example */
{
if(i > 0)
{
pewtinace(i - 1);
printf("%d", rand());
}
}

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[amaldev.manuel]

> I noted the following:

a. While iteration is linear in time and constant in space, recursion
is exponential in space.

b. Iteration preserves state, recursion does not.

certainly not in the case of backtracking algorithms.

[Julian V. Noble]

Sathyaish wrote:

Can every problem that has an iterative solution also be expressed in
terms of a recursive solution?

[ snipped ]
I noted the following:

a. While iteration is linear in time and constant in space, recursion
is exponential in space.

Two remarks:

1. You can read all about recursion in my Computing Prescriptions
column in Computing in Science and Engineering (May/June 2003,
pp. 76-81 (a color version may be found at

http://galileo.phys.virginia.edu/cla...l01/Cprogs.htm
2. Assuming recursion employs a stack, the growth of memory usage
with problem size is logarithmic, not exponential, unless you
are using recursion in a foolish context (to compute Fibonacci
numbers or the like).
--
Julian V. Noble
Professor Emeritus of Physics
University of Virginia

[Torben Ægidius Mogensen]

"Julian V. Noble" <jv*@virginia.edu> writes:

Two remarks:

1. You can read all about recursion in my Computing Prescriptions
column in Computing in Science and Engineering (May/June 2003,
pp. 76-81 (a color version may be found at

http://galileo.phys.virginia.edu/cla...l01/Cprogs.htm
Hardly _all_ about recursion. :-)
2. Assuming recursion employs a stack, the growth of memory usage
with problem size is logarithmic, not exponential, unless you
are using recursion in a foolish context (to compute Fibonacci
numbers or the like).

That is a very imprecise statement. The largest number of stack
frames that are active at any one point can be anywhere between
constant to linear in the total number of recursive calls, but the
number of recursive calls does not need to be linear in the problem
size (as measured by the input size). For example, the recursive
solution to The Towers of Hanoi for N disks uses 2^N-1 calls but stack
depth only N. Additionally, the size of each stack frame may depend
on the input size, so the total space used can be larger than linear
in the number of calls.

Torben

[SM Ryan]

# Sathyaish said:
#
# Can every problem that has an iterative solution also be expressed in
# terms of a recursive solution?

Iterative constructions can be easily transformed into recursive ones.
Some recursive constructs cannot be transformed into iterative without
additional variables to simulate the stack.

--
SM Ryan http://www.rawbw.com/~wyrmwif/
We found a loophole; they can't keep us out anymore.

[raxitsheth]

I noted the following:

a. While iteration is linear in time and constant in space, recursion
is exponential in space.

b. Iteration preserves state, recursion does not.

Missing Basic Stuff,
Question why it would require more time (then linear)?
why required more space ? (coz to preserve the state on stake )

Simple ex. fibonacci

fib(1) = fib(2) = 1
fib(n) = fib(n-1)+fib(n-2), if n>2

for fib(6)=fib(5)+fib(4)=[fib(4)+fib(3)] + [fib(3)+fib(2)] =-........
the basic thing is that fib(3) is calculated two times above.
Normally (not always) recursive one is slow(compare to linear) and/or
would require (more space) because
1. repeated computation done. (as in ex. fib(3) called twice,
2. and same result is stored more than once.

Before using recursive fun. Estimate how much space/time it would take
extra, ?
that is the best way to decide recursive is usable in particular case
or not ?

--
Raxit Sheth

[Richard Heathfield]

ra********@gmail.com said:

Simple ex. fibonacci

fib(1) = fib(2) = 1
fib(n) = fib(n-1)+fib(n-2), if n>2

for fib(6)=fib(5)+fib(4)=[fib(4)+fib(3)] + [fib(3)+fib(2)] =-........
the basic thing is that fib(3) is calculated two times above.
Normally (not always) recursive one is slow(compare to linear) and/or
would require (more space) because
1. repeated computation done. (as in ex. fib(3) called twice,
2. and same result is stored more than once.

Exercise for the reader: write an iterative version of fib() that is even
less efficient than the recursive version explained above, and use it to
prove that iteration is slow (compared to recursion) and would require more
space.

Exercise for the undergraduate student (or bright 12-year-old): write a
version that calculates fib() without iterating or recursing, thus proving
that both iteration and recursion require unnecessary amounts of space and
time.

Exercise for the post-graduate student: make the non-iterative non-recursive
version less efficient than the least efficient of the versions so far
discussed, thus proving that both iteration and recursion are massively
superior to O(1) techniques.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Alf P. Steinbach]

* Richard Heathfield:

ra********@gmail.com said:

Simple ex. fibonacci

fib(1) = fib(2) = 1
fib(n) = fib(n-1)+fib(n-2), if n>2

for fib(6)=fib(5)+fib(4)=[fib(4)+fib(3)] + [fib(3)+fib(2)] =-........
the basic thing is that fib(3) is calculated two times above.
Normally (not always) recursive one is slow(compare to linear) and/or
would require (more space) because
1. repeated computation done. (as in ex. fib(3) called twice,
2. and same result is stored more than once.

Exercise for the reader: write an iterative version of fib() that is even
less efficient than the recursive version explained above, and use it to
prove that iteration is slow (compared to recursion) and would require more
space.

Exercise for the undergraduate student (or bright 12-year-old): write a
version that calculates fib() without iterating or recursing, thus proving
that both iteration and recursion require unnecessary amounts of space and
time.

Exercise for the post-graduate student: make the non-iterative non-recursive
version less efficient than the least efficient of the versions so far
discussed, thus proving that both iteration and recursion are massively
superior to O(1) techniques.

The last one stumps me.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Torben Ægidius Mogensen]

ra********@gmail.com writes:

I noted the following:

a. While iteration is linear in time and constant in space, recursion
is exponential in space.

b. Iteration preserves state, recursion does not.

Missing Basic Stuff,
Question why it would require more time (then linear)?
why required more space ? (coz to preserve the state on stake )

Simple ex. fibonacci

fib(1) = fib(2) = 1
fib(n) = fib(n-1)+fib(n-2), if n>2

for fib(6)=fib(5)+fib(4)=[fib(4)+fib(3)] + [fib(3)+fib(2)] =-........
the basic thing is that fib(3) is calculated two times above.
Normally (not always) recursive one is slow(compare to linear) and/or
would require (more space) because
1. repeated computation done. (as in ex. fib(3) called twice,
2. and same result is stored more than once.

Before using recursive fun. Estimate how much space/time it would take
extra, ?
that is the best way to decide recursive is usable in particular case
or not ?

As Richard Heathfield said, this is not a question of recursion versus
iteration, but a question of using different algorithms. You are not
the only one making this mistake, though. I remember a special issue
of BYTE magazine from 1988 on benchmarks, where the author of an
article on Pascal benchmarks used the naive fibonacci function above
as a benchmark for function calls. The author then thought it would
be neat to compare the running time to a non-recursive implementation
and was flabbergasted by the large difference, concluding that
function calls must be very expensive indeed.

If your iterative fibonacci is

a := 0;
b := 1;
for i:=0 to n do begin
t := a;
a := b;
b := t+b
end;
writeln(b)

then the recursive version you should compare with is:

fib n = fib1 (n,0,1)

fib1 (0,a,b) = b
fib1 (n,a,b) = fib1 (n-1,b,a+b)

which is simpler than the above (it doesn't need the temporary
variable t) and equally fast (assuming a sensible compiler).

Both of the above use O(n) steps to calculate fibonacci of n. The
recursive function below uses O(log(n)) steps. Try writing this
without recursion.

fibo n = fst (h n)

h 0 = (1,0)
h n | even n = (a^2+b^2,b*(2*a-b)) where (a,b) = h (n`div`2)
h n | odd n = (a*(2*b+a),a^2+b^2) where (a,b) = h (n`div`2)

Note: It will be slower than the simple fib for small n.

Richard also hinted at an O(1) fibonacci function. He probably meant
(phi^n - (1-phi)^n)/sqrt(5), where phi = (sqrt(5)+1)/2. This is,
however, a bit misleading, as this is only O(1) if you can do
arbitrary precision arithmetic in constant time, which is a bit
doubtful. This is also to a lesser extent true for the simpler
versions, as the linear time is assuming that arithmetic operations on
arbitrary-size integers can be done in constant time.

Torben

[Jonathan Bartlett]

You might be interested in an article I wrote for IBM DeveloperWorks on
recursive programming:

http://www-128.ibm.com/developerwork.../l-recurs.html

Jon
----
Learn to program using Linux assembly language
http://www.cafeshops.com/bartlettpublish.8640017

[Julian V. Noble]

Jonathan Bartlett wrote:

You might be interested in an article I wrote for IBM DeveloperWorks on
recursive programming:

http://www-128.ibm.com/developerwork.../l-recurs.html

Jon
----
Learn to program using Linux assembly language
http://www.cafeshops.com/bartlettpublish.8640017

Nice article. I sent feedback. I don't agree that you should
keep variables constant throughout a program. That's what a
CONSTANT is for.

--
Julian V. Noble
Professor Emeritus of Physics
University of Virginia

[James Dow Allen]

Richard Heathfield wrote:

Exercise for the post-graduate student: make the non-iterative non-recursive
version less efficient than the least efficient of the versions so far
discussed, ...

Not overly impressed with Comp Sci doctorates, eh?

James

[Richard Heathfield]

James Dow Allen said:

Richard Heathfield wrote:

Exercise for the post-graduate student: make the non-iterative
non-recursive version less efficient than the least efficient of the
versions so far discussed, ...

Not overly impressed with Comp Sci doctorates, eh?

When you've had to teach 'em to program, you don't tend to be too impressed
by the bits of paper that said they already could.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[blmblm]

In article <n4******************************@bt.com>,
Richard Heathfield <in*****@invalid.invalid> wrote:

James Dow Allen said:

Richard Heathfield wrote:

Exercise for the post-graduate student: make the non-iterative
non-recursive version less efficient than the least efficient of the
versions so far discussed, ...

Not overly impressed with Comp Sci doctorates, eh?

When you've had to teach 'em to program, you don't tend to be too impressed
by the bits of paper that said they already could.

Point taken, but ....

Do PhD programs in CS even claim to be producing good programmers?
I mean, I can easily imagine legitimate dissertation research that
involves no programming at all, and while you could argue that the
degree program should include a breadth requirement that includes
programming skills, hm .... No, I don't think I would (argue that,
beyond a minimal level that I suspect would still leave the person
in a state in which you would have to "teach 'em to program").

--
| B. L. Massingill
| ObDisclaimer: I don't speak for my employers; they return the favor.

[Richard Heathfield]

bl****@myrealbox.com said:

In article <n4******************************@bt.com>,
Richard Heathfield <in*****@invalid.invalid> wrote:

When you've had to teach 'em to program, you don't tend to be too
impressed by the bits of paper that said they already could.

Point taken, but ....

Do PhD programs in CS even claim to be producing good programmers?

If CS grads at least knew a bit of CS, that would be a start. :-)

(I accept that my sample set is probably statistically insignificant, but
they were *all* useless, and 100% is 100% in anybody's language!)

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Ben Pfaff]

bl****@myrealbox.com writes:

Do PhD programs in CS even claim to be producing good programmers?

That's not a claim here at Stanford, as far as I know.
--
Ben Pfaff
email: bl*@cs.stanford.edu
web: http://benpfaff.org

[blmblm]

In article <Iv******************************@bt.com>,
Richard Heathfield <in*****@invalid.invalid> wrote:

bl****@myrealbox.com said:

In article <n4******************************@bt.com>,
Richard Heathfield <in*****@invalid.invalid> wrote:

When you've had to teach 'em to program, you don't tend to be too
impressed by the bits of paper that said they already could.

Point taken, but ....

Do PhD programs in CS even claim to be producing good programmers?

If CS grads at least knew a bit of CS, that would be a start. :-)

(I accept that my sample set is probably statistically insignificant, but
they were *all* useless, and 100% is 100% in anybody's language!)

They're useless for your purposes, and they don't know any CS either?
That would *really* be a sad commentary on those bits of paper.

War stories of their uselessness appreciated, too, especially
if your comment extends to people with undergrad CS degrees.
I teach undergrad CS, and while I don't think every last one of our
graduates should be a good fit in a programming job, still, *some*
of them should be.

--
| B. L. Massingill
| ObDisclaimer: I don't speak for my employers; they return the favor.

[Richard Heathfield]

bl****@myrealbox.com said:

War stories of their uselessness appreciated, too, especially
if your comment extends to people with undergrad CS degrees.
I teach undergrad CS, and while I don't think every last one of our
graduates should be a good fit in a programming job, still, *some*
of them should be.

I'm sure your crop is better than average, as they have you to teach them.
And of course I know there are plenty of bright CS bunnies out there
generally. It's just that I hardly ever seem to run into them myself -
except here on Usenet, of course.

Maybe the bright ones are bright enough to know to avoid me. :-)

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[blmblm]

In article <4p******************************@bt.com>,
Richard Heathfield <in*****@invalid.invalid> wrote:

bl****@myrealbox.com said:

War stories of their uselessness appreciated, too, especially
if your comment extends to people with undergrad CS degrees.
I teach undergrad CS, and while I don't think every last one of our
graduates should be a good fit in a programming job, still, *some*
of them should be.
I'm sure your crop is better than average, as they have you to teach them.

Actually I think they are a bit better than average, though I doubt
I can claim much if any of the credit for that -- we get some pretty
bright ones coming in. Some of them, by the time they graduate,
are pretty competent programmers, by the standards of an academic
anyway. Others -- well, we sometimes wonder how they managed to
forget so much of what they presumably learned in order to pass the
introductory programming classes. And don't get me started on the
range of mathematical backgrounds/skills ....

Possibly, though, I wasn't clear -- I wasn't so much claiming that
we *do* turn out a few who might be useful (though I hope that's
true) as saying that we *should* turn out a few such, and asking
for stories that would make it clearer what to avoid.
And of course I know there are plenty of bright CS bunnies out there
generally. It's just that I hardly ever seem to run into them myself -
except here on Usenet, of course.

Maybe the bright ones are bright enough to know to avoid me. :-)

Anything's possible, but I'd claim that the bright ones are smart
enough to recognize the value of hanging around someone knowledgeable
if irascible.

--
| B. L. Massingill
| ObDisclaimer: I don't speak for my employers; they return the favor.

[Richard Heathfield]

bl****@myrealbox.com said:

Possibly, though, I wasn't clear -- I wasn't so much claiming that
we *do* turn out a few who might be useful (though I hope that's
true) as saying that we *should* turn out a few such, and asking
for stories that would make it clearer what to avoid.

Well, for starters, either teach them how to program or tell them not to
apply for programming jobs. :-)

Seriously, it's not my place to teach you how to teach. But IF IT WERE, then
I'd suggest the following:

Make sure they have a thorough understanding of an abstract machine, to the
extent that they can write non-trivial machine code programs in it. An
8-bit machine will be fine - 256 bytes of RAM ought to be enough for
anybody. 16 bits if you're feeling astoundingly generous. Make sure it has
a weird character collating sequence. I mean /really/ weird. (But keep '0'
through '9' contiguous and ascending.) If you're feeling really pleasant,
make it a two-byte machine with 11-bit bytes! Let them learn the meaning of
the word "architecture" (or "agriculture", as we read in clc recently!).

Set one of the really bright ones to write the machine code interpreter in
something like C or C++; then make sure it works, fix it if need be, and
use it forever afterwards for students to test their machine code programs
on. Then get someone else bright to write an assembler and debugger for it.

You're now in a position to teach programming at the dirty end - so make
sure they all understand about stacks and heaps and how memory works and
procedure calls, and so on ad nauseam. (Make sure they write enough machine
code programs to get the idea, before you let them graduate to assembly
language.)

This doesn't have to be hugely in-depth, but I am sick and tired of teaching
people what a pointer is, when they ought to KNOW what a pointer is. "Look,
you want this function to update the pointer, right? So you ought to be
passing a pointer-to-the-pointer into the function" + blank look = recipe
for a police caution.

Then, once they know all that, teach them programming from the clean end.
:-) High level, in other words. You should find that they pick it up rather
easily, because they understand what's going on underneath.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Charles Richmond]

bl****@myrealbox.com wrote:

In article <n4******************************@bt.com>,
Richard Heathfield <in*****@invalid.invalid> wrote:

James Dow Allen said:

Richard Heathfield wrote:
Exercise for the post-graduate student: make the non-iterative
non-recursive version less efficient than the least efficient of the
versions so far discussed, ...

Not overly impressed with Comp Sci doctorates, eh?

When you've had to teach 'em to program, you don't tend to be too impressed
by the bits of paper that said they already could.

Point taken, but ....

Do PhD programs in CS even claim to be producing good programmers?
I mean, I can easily imagine legitimate dissertation research that
involves no programming at all, and while you could argue that the
degree program should include a breadth requirement that includes
programming skills, hm .... No, I don't think I would (argue that,
beyond a minimal level that I suspect would still leave the person
in a state in which you would have to "teach 'em to program").

This reminds me of this math professor that a friend and I took
numerical analysis from in college. This sadistic prof did *not*
provide the students with computer accounts. Instead, you had to
"play" the computer and do all the iterative calculations by hand.
This required a *lot* of writing and created quite a pile of notebook
paper.

ISTM that using the computer is part of the point of such a course.

Fortunately, I had the good sense to drop the class...

--
+----------------------------------------------------------------+
| Charles and Francis Richmond richmond at plano dot net |
+----------------------------------------------------------------+

[Jonathan Bartlett]

> Nice article. I sent feedback. I don't agree that you should

keep variables constant throughout a program. That's what a
CONSTANT is for.

Constants don't work for such a thing. Constants must be (1) global and
(2) known at compile-time.

The point is not "constancy" as much as "single assignment only". There
is a subtle difference. A variable can get a new value, but only if it
is a new instance of that variable (i.e. from a new activation record).
Single assignment allows you to keep better control over your loops.
That way, at all times the derivation of any variable is easily
determinable.

Jon
----
Learn to program using Linux assembly language
http://www.cafeshops.com/bartlettpublish.8640017

[Jonathan Bartlett]

> You're now in a position to teach programming at the dirty end - so make

sure they all understand about stacks and heaps and how memory works and
procedure calls, and so on ad nauseam. (Make sure they write enough machine
code programs to get the idea, before you let them graduate to assembly
language.)

This doesn't have to be hugely in-depth, but I am sick and tired of teaching
people what a pointer is, when they ought to KNOW what a pointer is. "Look,
you want this function to update the pointer, right? So you ought to be
passing a pointer-to-the-pointer into the function" + blank look = recipe
for a police caution.

Wow. This sounds exactly like what my book was intended to teach. This
is a shameless plug, but since you essentially stated the purpose and
outline of my book I thought it might be appropriate:

Programming from the Ground Up
http://www.cafeshops.com/bartlettpublish.8640017

It doesn't do machine code, but it covers a lot. However, when I teach
intro to programming at the local junior college, I have a "Machine
Language Game" to teach people how the computer works. I have a 16x16
board representing RAM, a whiteboard segmented into registers, a
one-line card for the display, and a stack of papers which tell how to
execute different command codes. I have one student be the data bus,
one student be the ALU, and one student be the instruction handler, and
one student be the graphics card. The instruction handler tells the
data bus to grab the next instruction. The data bus reads it from RAM
and comes back with the instruction and the next two bytes. The
instruction handler then looks up the first number in the instruction
code manual, and does what the manual says. The ALU does what the
instruction handler says, and the graphics card just watches some memory
and updates his output whenever it changes, based on the ASCII codes.

It really helps students figure out how the computer really works
underneath.

Jon

[Bradley K. Sherman]

In article <44********@news.tulsaconnect.com>,
Jonathan Bartlett <jo*****@eskimo.com> wrote:

code manual, and does what the manual says. The ALU does what the
instruction handler says, and the graphics card just watches some memory
and updates his output whenever it changes, based on the ASCII codes.

It really helps students figure out how the computer really works
underneath.

Which is why students should be learning C not Java in High School
AP courses.

--bks

[Andrew Poelstra]

On 2006-05-11, Bradley K. Sherman <bk*@panix.com> wrote:

In article <44********@news.tulsaconnect.com>,
Jonathan Bartlett <jo*****@eskimo.com> wrote:

code manual, and does what the manual says. The ALU does what the
instruction handler says, and the graphics card just watches some memory
and updates his output whenever it changes, based on the ASCII codes.

It really helps students figure out how the computer really works
underneath.

Which is why students should be learning C not Java in High School
AP courses.

Java? In my school they teach VB. *shudder* I had to transfer to a digital
graphics course and learn Flash to avoid that. And according to the
curriculum, the most advanced topic they reached was array manipulation. In
a /grade 12/ cs course.

I have never seen anyone who learned how to program in school; good
programmers are the ones who read books.

[Andrew Poelstra]

On 2006-05-11, Richard Heathfield <in*****@invalid.invalid> wrote:

Make sure they have a thorough understanding of an abstract machine, to the
extent that they can write non-trivial machine code programs in it. An
8-bit machine will be fine - 256 bytes of RAM ought to be enough for
anybody. 16 bits if you're feeling astoundingly generous. Make sure it has
a weird character collating sequence. I mean /really/ weird. (But keep '0'
through '9' contiguous and ascending.) If you're feeling really pleasant,
make it a two-byte machine with 11-bit bytes! Let them learn the meaning of
the word "architecture" (or "agriculture", as we read in clc recently!).
One weeks in clc is enough to figure that out. I personally think that no
computer programming class should have machines built in the past 15 years.
No, make that 20. Learning to code on a 8086 will teach people the meaning
of portability.
You're now in a position to teach programming at the dirty end - so make
sure they all understand about stacks and heaps and how memory works and
procedure calls, and so on ad nauseam. (Make sure they write enough machine
code programs to get the idea, before you let them graduate to assembly
language.) I agree entirely. Any decent programmer should have some idea of how to
write machine code, or at least understand how it works in principle.
This doesn't have to be hugely in-depth, but I am sick and tired of teaching
people what a pointer is, when they ought to KNOW what a pointer is. "Look,
you want this function to update the pointer, right? So you ought to be
passing a pointer-to-the-pointer into the function" + blank look = recipe
for a police caution.

I spent a year working entirely in x86 assembler. I have never, ever, had
a problem figuring pointers out since. Machine language probably isn't
necessary.

Of course, if you are going to teach them Java, you might as well explain
that fairies memorize the contents of your variables so that you don't need
memory.

[CBFalconer]

Richard Heathfield wrote:

bl****@myrealbox.com said:

Possibly, though, I wasn't clear -- I wasn't so much claiming that
we *do* turn out a few who might be useful (though I hope that's
true) as saying that we *should* turn out a few such, and asking
for stories that would make it clearer what to avoid.

Well, for starters, either teach them how to program or tell them
not to apply for programming jobs. :-)

Seriously, it's not my place to teach you how to teach. But IF IT
WERE, then I'd suggest the following:

Make sure they have a thorough understanding of an abstract machine, to the
extent that they can write non-trivial machine code programs in it. An
8-bit machine will be fine - 256 bytes of RAM ought to be enough for
anybody. 16 bits if you're feeling astoundingly generous. Make sure it has
a weird character collating sequence. I mean /really/ weird. (But keep '0'
through '9' contiguous and ascending.) If you're feeling really pleasant,
make it a two-byte machine with 11-bit bytes! Let them learn the meaning of
the word "architecture" (or "agriculture", as we read in clc recently!).

Set one of the really bright ones to write the machine code interpreter in
something like C or C++; then make sure it works, fix it if need be, and
use it forever afterwards for students to test their machine code programs
on. Then get someone else bright to write an assembler and debugger for it.

You're now in a position to teach programming at the dirty end - so make
sure they all understand about stacks and heaps and how memory works and
procedure calls, and so on ad nauseam. (Make sure they write enough machine
code programs to get the idea, before you let them graduate to assembly
language.)

This doesn't have to be hugely in-depth, but I am sick and tired of teaching
people what a pointer is, when they ought to KNOW what a pointer is. "Look,
you want this function to update the pointer, right? So you ought to be
passing a pointer-to-the-pointer into the function" + blank look = recipe
for a police caution.

Then, once they know all that, teach them programming from the clean end.
:-) High level, in other words. You should find that they pick it up rather
easily, because they understand what's going on underneath.

But you would clutter their pristine young minds with all this
detail, when all they need to know is the abstract properties of an
operation! Something like teaching the basic definitions of a
limit (difference arbitrarily small as things approach arbitrarily
near, or we can find an epsilon such that, etc.) to budding
mathematicians. Or even that hot gases expand and urge pistons or
other things to move to budding automotive engineers.

In all seriousness though, the fundamental teaching problem is when
and where to draw the line between detail and abstraction, and
persuade the student to choose the appropriate view. The lack
today of simple but complete systems, such as were built around the
8080, is a drawback. A stack is a detail, automatic storage is an
abstraction.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>

[Ben Pfaff]

Richard Heathfield <in*****@invalid.invalid> writes:

bl****@myrealbox.com said:

In article <n4******************************@bt.com>,
Richard Heathfield <in*****@invalid.invalid> wrote:

When you've had to teach 'em to program, you don't tend to be too
impressed by the bits of paper that said they already could.

Point taken, but ....

Do PhD programs in CS even claim to be producing good programmers?

If CS grads at least knew a bit of CS, that would be a start. :-)

I know some excellent computer scientists who are not
programmers. It is not what they do. Their papers read like
math papers. I could never do what they do, and I wouldn't try
to claim that I could.

For their part, I suspect that they wouldn't claim they are good
programmers either, at least not in languages like C. Perhaps
that's the real problem: people who claim to be what they are
not. But I wouldn't criticize computer scientists for not being
programmers, as long as they don't claim to be.
--
Bite me! said C.

[Richard Heathfield]

Ben Pfaff said:

I know some excellent computer scientists who are not
programmers. It is not what they do. Their papers read like
math papers. I could never do what they do, and I wouldn't try
to claim that I could.

I take your point, but those people aren't applying for programming jobs,
so, for the purposes of the current discussion, they don't count. :-)

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Keith Thompson]

Ben Pfaff <bl*@cs.stanford.edu> writes:
[...]

I know some excellent computer scientists who are not
programmers. It is not what they do. Their papers read like
math papers. I could never do what they do, and I wouldn't try
to claim that I could.

For their part, I suspect that they wouldn't claim they are good
programmers either, at least not in languages like C. Perhaps
that's the real problem: people who claim to be what they are
not. But I wouldn't criticize computer scientists for not being
programmers, as long as they don't claim to be.

It reminds me of an Edsger Dijkstra quotation: "Computer science is no
more about computers than astronomy is about telescopes."

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[birarai]

Take a look at www.monsterSDLC.com

[Richard Heathfield]

birarai said:

Take a look at www.monsterSDLC.com

....and you'll see a cartoon of an owl with a beach-ball stuck on his nose.
How is this relevant to our discussion of iteration vs recursion?

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[David Lightstone]

"CBFalconer" <cb********@yahoo.com> wrote in message
news:44***************@yahoo.com...

Richard Heathfield wrote:

bl****@myrealbox.com said:

Possibly, though, I wasn't clear -- I wasn't so much claiming that
we *do* turn out a few who might be useful (though I hope that's
true) as saying that we *should* turn out a few such, and asking
for stories that would make it clearer what to avoid.
Well, for starters, either teach them how to program or tell them
not to apply for programming jobs. :-)

Seriously, it's not my place to teach you how to teach. But IF IT
WERE, then I'd suggest the following:

Make sure they have a thorough understanding of an abstract machine, to
the
extent that they can write non-trivial machine code programs in it. An
8-bit machine will be fine - 256 bytes of RAM ought to be enough for
anybody. 16 bits if you're feeling astoundingly generous. Make sure it
has
a weird character collating sequence. I mean /really/ weird. (But keep
'0'
through '9' contiguous and ascending.) If you're feeling really pleasant,
make it a two-byte machine with 11-bit bytes! Let them learn the meaning
of
the word "architecture" (or "agriculture", as we read in clc recently!).

Set one of the really bright ones to write the machine code interpreter
in
something like C or C++; then make sure it works, fix it if need be, and
use it forever afterwards for students to test their machine code
programs
on. Then get someone else bright to write an assembler and debugger for
it.

You're now in a position to teach programming at the dirty end - so make
sure they all understand about stacks and heaps and how memory works and
procedure calls, and so on ad nauseam. (Make sure they write enough
machine
code programs to get the idea, before you let them graduate to assembly
language.)

This doesn't have to be hugely in-depth, but I am sick and tired of
teaching
people what a pointer is, when they ought to KNOW what a pointer is.
"Look,
you want this function to update the pointer, right? So you ought to be
passing a pointer-to-the-pointer into the function" + blank look = recipe
for a police caution.

Then, once they know all that, teach them programming from the clean end.
:-) High level, in other words. You should find that they pick it up
rather
easily, because they understand what's going on underneath.

But you would clutter their pristine young minds with all this
detail, when all they need to know is the abstract properties of an
operation! Something like teaching the basic definitions of a
limit (difference arbitrarily small as things approach arbitrarily
near, or we can find an epsilon such that, etc.) to budding
mathematicians. Or even that hot gases expand and urge pistons or
other things to move to budding automotive engineers.

In all seriousness though, the fundamental teaching problem is when
and where to draw the line between detail and abstraction, and
persuade the student to choose the appropriate view.

I thought Parnas resolved that circa the development innovation
modularization / incapsulation / data hiding.
Is a whole new bunch of programmers (and I know you are not one of them)
rediscovering the square wheel?

The lack
today of simple but complete systems, such as were built around the
8080, is a drawback. A stack is a detail, automatic storage is an
abstraction.
I do not consider that necessary to learn about systems. Laszlos's book
System View of the World will be adequate


--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>

[SM Ryan]

Apparently it is okay to go off topic if you are in the Elect.

"David Lightstone" <da*********************@prodigy.net> wrote:
#
# "CBFalconer" <cb********@yahoo.com> wrote in message
# news:44***************@yahoo.com...
# > Richard Heathfield wrote:
# >> bl****@myrealbox.com said:
# >>
# >>> Possibly, though, I wasn't clear -- I wasn't so much claiming that
# >>> we *do* turn out a few who might be useful (though I hope that's
# >>> true) as saying that we *should* turn out a few such, and asking
# >>> for stories that would make it clearer what to avoid.
# >>
# >> Well, for starters, either teach them how to program or tell them
# >> not to apply for programming jobs. :-)
# >>
# >> Seriously, it's not my place to teach you how to teach. But IF IT
# >> WERE, then I'd suggest the following:
# >>
# >> Make sure they have a thorough understanding of an abstract machine, to
# >> the
# >> extent that they can write non-trivial machine code programs in it. An
# >> 8-bit machine will be fine - 256 bytes of RAM ought to be enough for
# >> anybody. 16 bits if you're feeling astoundingly generous. Make sure it
# >> has
# >> a weird character collating sequence. I mean /really/ weird. (But keep
# >> '0'
# >> through '9' contiguous and ascending.) If you're feeling really pleasant,
# >> make it a two-byte machine with 11-bit bytes! Let them learn the meaning
# >> of
# >> the word "architecture" (or "agriculture", as we read in clc recently!).
# >>
# >> Set one of the really bright ones to write the machine code interpreter
# >> in
# >> something like C or C++; then make sure it works, fix it if need be, and
# >> use it forever afterwards for students to test their machine code
# >> programs
# >> on. Then get someone else bright to write an assembler and debugger for
# >> it.
# >>
# >> You're now in a position to teach programming at the dirty end - so make
# >> sure they all understand about stacks and heaps and how memory works and
# >> procedure calls, and so on ad nauseam. (Make sure they write enough
# >> machine
# >> code programs to get the idea, before you let them graduate to assembly
# >> language.)
# >>
# >> This doesn't have to be hugely in-depth, but I am sick and tired of
# >> teaching
# >> people what a pointer is, when they ought to KNOW what a pointer is.
# >> "Look,
# >> you want this function to update the pointer, right? So you ought to be
# >> passing a pointer-to-the-pointer into the function" + blank look = recipe
# >> for a police caution.
# >>
# >> Then, once they know all that, teach them programming from the clean end.
# >> :-) High level, in other words. You should find that they pick it up
# >> rather
# >> easily, because they understand what's going on underneath.
# >
# > But you would clutter their pristine young minds with all this
# > detail, when all they need to know is the abstract properties of an
# > operation! Something like teaching the basic definitions of a
# > limit (difference arbitrarily small as things approach arbitrarily
# > near, or we can find an epsilon such that, etc.) to budding
# > mathematicians. Or even that hot gases expand and urge pistons or
# > other things to move to budding automotive engineers.
# >
# > In all seriousness though, the fundamental teaching problem is when
# > and where to draw the line between detail and abstraction, and
# > persuade the student to choose the appropriate view.
#
# I thought Parnas resolved that circa the development innovation
# modularization / incapsulation / data hiding.
# Is a whole new bunch of programmers (and I know you are not one of them)
# rediscovering the square wheel?
#
#
# >The lack
# > today of simple but complete systems, such as were built around the
# > 8080, is a drawback. A stack is a detail, automatic storage is an
# > abstraction.
#
# I do not consider that necessary to learn about systems. Laszlos's book
# System View of the World will be adequate
#
#
# >
# > --
# > "If you want to post a followup via groups.google.com, don't use
# > the broken "Reply" link at the bottom of the article. Click on
# > "show options" at the top of the article, then click on the
# > "Reply" at the bottom of the article headers." - Keith Thompson
# > More details at: <http://cfaj.freeshell.org/google/>
# > Also see <http://www.safalra.com/special/googlegroupsreply/>
# >
# >
#
#
#
#

--
SM Ryan http://www.rawbw.com/~wyrmwif/
What kind of convenience store do you run here?

[Richard Heathfield]

SM Ryan said:

Apparently it is okay to go off topic if you are in the Elect.

(a) The discussion is on-topic in, perhaps, three (maybe four) of the five
newsgroups that are carrying it, so I think your complaint is, to a certain
degree at least, rather misplaced.

(b) As somebody famous (Kaz?) once said, writing good, solid,
well-researched, interesting, helpful, *topical* articles for a newsgroup
is like putting florins (or dimes) in the bank - and indulging in off-topic
discussion is like taking out guineas (or dollars). Long-serving,
prolifically helpful, high-quality (and unpaid!) regulars earn a certain
(but by no means unlimited) amount of tolerance with regard to topicality.

(c) TINC.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Ben Pfaff]

SM Ryan <wy*****@tango-sierra-oscar-foxtrot-tango.fake.org> writes:

Apparently it is okay to go off topic if you are in the Elect.

Apparently it is okay to quote 100 lines to top-post a snarky comment?
--
Ben Pfaff
email: bl*@cs.stanford.edu
web: http://benpfaff.org

[David Lightstone]

"SM Ryan" <wy*****@tango-sierra-oscar-foxtrot-tango.fake.org> wrote in
message news:12*************@corp.supernews.com...

Apparently it is okay to go off topic if you are in the Elect.


What topic? You read the subject line, you read the content and decide for
yourself if there is a correlation.

Perhaps I should have retitled the subject when I made my post. Perhaps the
author of the post to which I responded should have retitled it.
Either way it did not occur.

What to title the subject of this post. Can't decide. Perhaps - "a decision
criteria for determining when it might be wise to consider changing the
subject of the newsgroup posting" no that is just to long

"David Lightstone" <da*********************@prodigy.net> wrote:
#
# "CBFalconer" <cb********@yahoo.com> wrote in message
# news:44***************@yahoo.com...
# > Richard Heathfield wrote:
# >> bl****@myrealbox.com said:
# >>
# >>> Possibly, though, I wasn't clear -- I wasn't so much claiming that
# >>> we *do* turn out a few who might be useful (though I hope that's
# >>> true) as saying that we *should* turn out a few such, and asking
# >>> for stories that would make it clearer what to avoid.
# >>
# >> Well, for starters, either teach them how to program or tell them
# >> not to apply for programming jobs. :-)
# >>
# >> Seriously, it's not my place to teach you how to teach. But IF IT
# >> WERE, then I'd suggest the following:
# >>
# >> Make sure they have a thorough understanding of an abstract machine,
to
# >> the
# >> extent that they can write non-trivial machine code programs in it.
An
# >> 8-bit machine will be fine - 256 bytes of RAM ought to be enough for
# >> anybody. 16 bits if you're feeling astoundingly generous. Make sure
it
# >> has
# >> a weird character collating sequence. I mean /really/ weird. (But
keep
# >> '0'
# >> through '9' contiguous and ascending.) If you're feeling really
pleasant,
# >> make it a two-byte machine with 11-bit bytes! Let them learn the
meaning
# >> of
# >> the word "architecture" (or "agriculture", as we read in clc
recently!).
# >>
# >> Set one of the really bright ones to write the machine code
interpreter
# >> in
# >> something like C or C++; then make sure it works, fix it if need be,
and
# >> use it forever afterwards for students to test their machine code
# >> programs
# >> on. Then get someone else bright to write an assembler and debugger
for
# >> it.
# >>
# >> You're now in a position to teach programming at the dirty end - so
make
# >> sure they all understand about stacks and heaps and how memory works
and
# >> procedure calls, and so on ad nauseam. (Make sure they write enough
# >> machine
# >> code programs to get the idea, before you let them graduate to
assembly
# >> language.)
# >>
# >> This doesn't have to be hugely in-depth, but I am sick and tired of
# >> teaching
# >> people what a pointer is, when they ought to KNOW what a pointer is.
# >> "Look,
# >> you want this function to update the pointer, right? So you ought to
be
# >> passing a pointer-to-the-pointer into the function" + blank look =
recipe
# >> for a police caution.
# >>
# >> Then, once they know all that, teach them programming from the clean
end.
# >> :-) High level, in other words. You should find that they pick it up
# >> rather
# >> easily, because they understand what's going on underneath.
# >
# > But you would clutter their pristine young minds with all this
# > detail, when all they need to know is the abstract properties of an
# > operation! Something like teaching the basic definitions of a
# > limit (difference arbitrarily small as things approach arbitrarily
# > near, or we can find an epsilon such that, etc.) to budding
# > mathematicians. Or even that hot gases expand and urge pistons or
# > other things to move to budding automotive engineers.
# >
# > In all seriousness though, the fundamental teaching problem is when
# > and where to draw the line between detail and abstraction, and
# > persuade the student to choose the appropriate view.
#
# I thought Parnas resolved that circa the development innovation
# modularization / incapsulation / data hiding.
# Is a whole new bunch of programmers (and I know you are not one of them)
# rediscovering the square wheel?
#
#
# >The lack
# > today of simple but complete systems, such as were built around the
# > 8080, is a drawback. A stack is a detail, automatic storage is an
# > abstraction.
#
# I do not consider that necessary to learn about systems. Laszlos's book
# System View of the World will be adequate
#
#
# >
# > --
# > "If you want to post a followup via groups.google.com, don't use
# > the broken "Reply" link at the bottom of the article. Click on
# > "show options" at the top of the article, then click on the
# > "Reply" at the bottom of the article headers." - Keith Thompson
# > More details at: <http://cfaj.freeshell.org/google/>
# > Also see <http://www.safalra.com/special/googlegroupsreply/>
# >
# >
#
#
#
#

--
SM Ryan http://www.rawbw.com/~wyrmwif/
What kind of convenience store do you run here?

[CBFalconer]

Richard Heathfield wrote:

SM Ryan said:

Apparently it is okay to go off topic if you are in the Elect.

(a) The discussion is on-topic in, perhaps, three (maybe four) of
the five newsgroups that are carrying it, so I think your complaint
is, to a certain degree at least, rather misplaced.

I was shocked, shocked I tell you, to see Ryan and his fouled up
quotation markers together with top-posting appear on
comp.programming. I thought I had him plonked everywhere.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>

[blmblm]

In article <rK********************@bt.com>,
Richard Heathfield <in*****@invalid.invalid> wrote:

bl****@myrealbox.com said:

Possibly, though, I wasn't clear -- I wasn't so much claiming that
we *do* turn out a few who might be useful (though I hope that's
true) as saying that we *should* turn out a few such, and asking
for stories that would make it clearer what to avoid.
Well, for starters, either teach them how to program or tell them not to
apply for programming jobs. :-)

You know, my initial reaction to this was "excellent advice!" --
but one of the advantages (?) of putting off a reply is that there's
time for second thoughts ....

We do get some students who just plain don't like programming
(difficult though that may be for some of us to imagine :-) ).
These students are apt to get discouraged and drop out of CS early
on, because the introductory courses are almost 100% programming.
The ones that stick around, though .... They almost certainly
should be encouraged to find some career path that doesn't involve
programming, even as an entry-level job.

But for the ones who do enjoy programming enough to do it for a
living, at least for a few years, I don't know. I'm not sure we
*can* teach them to program -- we can teach them some rudimentary
skills, but the only way they can become good programmers is to
actually program, and our ability to make them do that is limited
given that we also want to teach them "basic principles" (i.e.,
given them a framework of basic knowledge on which they can hang the
technical details they'll learn in later years). I don't think we
should skimp on the "basic principles" stuff, because that's what
I think we do well, better than the workplace. But the result is
that only the ones who enjoy programming enough to do side projects
really graduate with more than rudimentary programming skills. I'm
not sure we can fix that.
Seriously, it's not my place to teach you how to teach. But IF IT WERE, then
I'd suggest the following:
Oh, no need to be so diplomatic -- I asked, right? though if you
want to say it's not your *responsibility* to teach me/us how to
teach, well, yeah ....

However. You may or may not know that how to teach beginning
programming is a topic of perennial debate among people who do it for
a living. In the most recent ACM report on undergraduate curricula
(2001, linked from http://www.acm.org/education/curricula.html),
six, count 'em six, approaches are listed. Something rather like
what you describe is one of them ("hardware first").
Make sure they have a thorough understanding of an abstract machine, to the
extent that they can write non-trivial machine code programs in it.
[ snip ]

I like your thinking here. I'm a little biased, maybe -- the first
CS course I took was introductory programming using Fortran, and
though I did well I didn't feel like I understood much, and it wasn't
until I took another course in assembly-language programming (IBM
360 ALC -- that probably dates me, right?) that I started to think
"oh, I get it now ...."
Then, once they know all that, teach them programming from the clean end.
:-) High level, in other words. You should find that they pick it up rather
easily, because they understand what's going on underneath.

Yeah .... And if you don't teach this kind of thing at some point,
I'm inclined to think that on some level the students will never
really understand what they're doing. Then again, one of my
colleagues, a fairly bright guy, claims that by doing this you're
locking them into how things are done now and making it less likely
that they can come up with fresh perspectives, and the right way
to start is with something much more abstract. (He likes J, which
is more or less a descendant of APL.) I don't know. More in responses
to other posts in this thread.

Anyway, a "thank you!" to you and everyone who replied to my question.
It's all being filed for reference next time we argue about curriculum
revisions. :-)

--
| B. L. Massingill
| ObDisclaimer: I don't speak for my employers; they return the favor.

[blmblm]

In article <44********@news.tulsaconnect.com>,
Jonathan Bartlett <jo*****@eskimo.com> wrote:

[ snip ]

However, when I teach
intro to programming at the local junior college, I have a "Machine
Language Game" to teach people how the computer works. I have a 16x16
board representing RAM, a whiteboard segmented into registers, a
one-line card for the display, and a stack of papers which tell how to
execute different command codes. I have one student be the data bus,
one student be the ALU, and one student be the instruction handler, and
one student be the graphics card. The instruction handler tells the
data bus to grab the next instruction. The data bus reads it from RAM
and comes back with the instruction and the next two bytes. The
instruction handler then looks up the first number in the instruction
code manual, and does what the manual says. The ALU does what the
instruction handler says, and the graphics card just watches some memory
and updates his output whenever it changes, based on the ASCII codes.

It really helps students figure out how the computer really works
underneath.

Cool idea. And you say this works well in practice? Hm ....

--
| B. L. Massingill
| ObDisclaimer: I don't speak for my employers; they return the favor.

[blmblm]

In article <44***************@yahoo.com>,
CBFalconer <cb********@maineline.net> wrote:

[ snip ]

In all seriousness though, the fundamental teaching problem is when
and where to draw the line between detail and abstraction, and
persuade the student to choose the appropriate view. The lack
today of simple but complete systems, such as were built around the
8080, is a drawback. A stack is a detail, automatic storage is an
abstraction.

Exactly.

Too much focus on details, too early, carries the risk of creating
the impression that whatever detailed system you teach is the only
possible one. I'm not thinking of a really great example of what I
have in mind here -- something along the lines of "if all you know
is Windows, the idea of a powerful command line is unimaginable",
or equivalently, "if all you know is CLIs, the idea of a system with
menus and icons is unimaginable". Starting out with a more abstract
view supposedly avoids this "lock the students into a too-limited
mental model". Can MIT really be totally wrong to start 'em out
in Scheme? (If they're still doing that.)

Then again, too much focus on abstractions carries the risk that they
never really understand .... I think this is especially a risk for
the less-bright students, who aren't very good at abstractions and
when forced to deal with them are apt to just get confused and ....
I wonder if this is the origin of that (bad) approach to writing
code that seems to consist of trying things at random until something
seems to work.

--
| B. L. Massingill
| ObDisclaimer: I don't speak for my employers; they return the favor.

[David Lightstone]

<bl****@myrealbox.com> wrote in message
news:4c*************@individual.net...

In article <44********@news.tulsaconnect.com>,
Jonathan Bartlett <jo*****@eskimo.com> wrote:

[ snip ]

However, when I teach
intro to programming at the local junior college, I have a "Machine
Language Game" to teach people how the computer works. I have a 16x16
board representing RAM, a whiteboard segmented into registers, a
one-line card for the display, and a stack of papers which tell how to
execute different command codes. I have one student be the data bus,
one student be the ALU, and one student be the instruction handler, and
one student be the graphics card. The instruction handler tells the
data bus to grab the next instruction. The data bus reads it from RAM
and comes back with the instruction and the next two bytes. The
instruction handler then looks up the first number in the instruction
code manual, and does what the manual says. The ALU does what the
instruction handler says, and the graphics card just watches some memory
and updates his output whenever it changes, based on the ASCII codes.

It really helps students figure out how the computer really works
underneath.
Cool idea. And you say this works well in practice? Hm ...

I would say that it will work quite well.

When I learned programming (cerca 1967), the technique was called "desk
checking". The difference being that we did it at the level of the FORTRAN
instruction, rather than the machine instruction.

For those not familiar with the era, batch processing was the norm.
Turnaround time was measured in days, not seconds. It has to compile
correctly the first time. It has to execute correctly the first time.
otherwise you loose several days
..
--
| B. L. Massingill
| ObDisclaimer: I don't speak for my employers; they return the favor.

[Torben Ægidius Mogensen]

Ben Pfaff <bl*@cs.stanford.edu> writes:

Richard Heathfield <in*****@invalid.invalid> writes:

bl****@myrealbox.com said:

In article <n4******************************@bt.com>,
Richard Heathfield <in*****@invalid.invalid> wrote:

When you've had to teach 'em to program, you don't tend to be too
impressed by the bits of paper that said they already could.

Point taken, but ....

Do PhD programs in CS even claim to be producing good programmers?
If CS grads at least knew a bit of CS, that would be a start. :-)

I know some excellent computer scientists who are not
programmers. It is not what they do. Their papers read like
math papers. I could never do what they do, and I wouldn't try
to claim that I could.

Mathematicians are nearly always good programmers -- if you can
structure a proof of a complex mathematical statement, you can program
also. They might find C++ obstruse and complicated (who doesn't?),
but give them a good functional programming language, and they will
out-program most so-called "programmers".
For their part, I suspect that they wouldn't claim they are good
programmers either, at least not in languages like C. Perhaps
that's the real problem: people who claim to be what they are
not. But I wouldn't criticize computer scientists for not being
programmers, as long as they don't claim to be.

Indeed. I would rather criticise someone who calls himself a
programmer and who isn't able to program a sub-quadratic sorting
algorithm without having to consult a textbook (or use a library
routine).

Torben

[Jonathan Bartlett]

It really helps students figure out how the computer really works
underneath.

Cool idea. And you say this works well in practice? Hm ....

I had an adult Walmart stocking clerk who had attended my class by
mistake (she was supposed to be in the "how to use MS Word class" decide
to stay and learn to program... and did every bit as good a job as the
kid who played around with Linux in the offtime.

Because of the game/simulation, she felt she could actually understand
how it all worked together.

Jon

[Andrew Poelstra]

On 2006-05-15, Jonathan Bartlett <jo*****@eskimo.com> wrote:

It really helps students figure out how the computer really works
underneath.

Cool idea. And you say this works well in practice? Hm ....

I had an adult Walmart stocking clerk who had attended my class by
mistake (she was supposed to be in the "how to use MS Word class" decide
to stay and learn to program... and did every bit as good a job as the
kid who played around with Linux in the offtime.

In general, if she herself decided to stay and learn how to code, she'd
be motivated enough to do a good job. Just a thought.
Because of the game/simulation, she felt she could actually understand
how it all worked together.

That would likely be the main reason that she was motivated. I think I
will steal your idea and use it to teach my class. Thanks!

[Keith Thompson]

to*****@app-4.diku.dk (Torben Ægidius Mogensen) writes:
[...]

Indeed. I would rather criticise someone who calls himself a
programmer and who isn't able to program a sub-quadratic sorting
algorithm without having to consult a textbook (or use a library
routine).

I would criticize any programmer who *bothers* to implement a
sub-quadratic sorting algorithm without consulting a textbook or using
a library routine.

I can write a Quicksort function if I have to -- but I don't have to.
And if I tried it without consulting any references, it's likely the
resulting function would have some (probably subtle) bugs.

I don't remember where I read this, but I seem to recall that there
was a gap of a decade or so between the first implementation of a
binary search algorithm, and the first *correct* implementation of a
binary search algorithm.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.