Re: teaching kids functional programming
- From: Pascal Bourguignon <pjb@xxxxxxxxxxxxxxxxx>
- Date: Wed, 22 Nov 2006 21:59:36 +0100
lurker <lurker@xxxxxxxxxx> writes:
(message (Hello 'Mark)
(you :wrote :on '(21 Nov 2006 13:02:04 -0800))
(
MT> One reason functional programming has not become more widespread, is
MT> that it is rarely encountered by our children or teens during their
MT> learning process. Here is an open question for you all. Do you think
MT> that functional programming can be taught with benefit to those of
MT> school age and if so,
yes, and not only functional programming, but prefix notation used in
lisp! reason: it's much more straightforward, so kids won't need to learn
about complex operator precendence rules, they will see how equations are
solved, etc.
This is a bit OT for the thread.
When people add up, don't most of them use a 'partial sum' method (can't
think of a better term).
No.
Lets say you want to sum from 1 to 5.
1+2=3
3+3=6
6+4=10
10+5=15
If you have to sum non-digit numbers,
21
32
43
54
+ 65
----
you first sum the first column of digits (from the right) this way:
5+3+2 = 10
4+1 = 5
so you write 5 and carry 1.
1
21
32
43
54
+ 65
----
5
Second column:
6+4 = 10
5+3+2 = 10
remains 1
so you write 1 and carry 2.
21
21
32
43
54
+ 65
----
15
Third columns, there's only 2, so you write 2:
21
21
32
43
54
+ 65
----
215
Summing from the left to the right is the silliest thing to do.
But how does Lisp calculate something like (+ 1 2 3 4 5)? I can appreciate
the economy of notation, but is there some kind of stack involved?
Lisp does it with an electronic processor, so the question is more
complex. If you want to know, you can have a look at the sources of a
lisp system and compiler or interpreter. You can also try to
disassemble a function summing a list, but in general it'll just call
a library function.
There most certainly is some stack involved, given that it might have
to call subroutines in the general case.
But of course, if you have just this sum, the compiler can do it at
compilation time so you'll get the sum in the binary code.
[658]> (disassemble (compile nil (lambda () (+ 1 2 3 4 5))))
Disassembly of function NIL
(CONST 0) = 15
0 required arguments
0 optional arguments
No rest parameter
No keyword parameters
2 byte-code instructions:
0 (CONST 0) ; 15
1 (SKIP&RET 1)
NIL
[659]> (disassemble (compile nil (lambda (a b c d e) (+ a b c d e))))
Disassembly of function NIL
5 required arguments
0 optional arguments
No rest parameter
No keyword parameters
7 byte-code instructions:
0 (LOAD&PUSH 5)
1 (LOAD&PUSH 5)
2 (LOAD&PUSH 5)
3 (LOAD&PUSH 5)
4 (LOAD&PUSH 5)
5 (CALLSR 5 53) ; +
8 (SKIP&RET 6)
NIL
Or does it use the good old 0.5*n*(n+1) formula?
Of course, when there's a regular sequence...
No, not really! The difference is that we have billions of neurons to
process such a list of numbers in parallel so we can see immediately
that there's a sequence and apply a formula instead of computing the
sum. On the other hand, our lisps only have one processor, so they
better employ it to start adding the numbers, instead of starting to
subtract and divide pairs of them to see if there's a serie... Of
course, this may change in a few years, and when you apply + on a
sizeable list, a lisp implementation may try to first see if there's
some regularity to the data, and apply some distributivity or other
formula to speed up the process. Or it could just spread the data
over the cores, and let each of the add only two numbers...
--
__Pascal Bourguignon__ http://www.informatimago.com/
HANDLE WITH EXTREME CARE: This product contains minute electrically
charged particles moving at velocities in excess of five hundred
million miles per hour.
.
- Follow-Ups:
- Re: teaching kids functional programming
- From: lurker
- Re: teaching kids functional programming
- Prev by Date: Re: tree-depth
- Next by Date: Re: tree-depth
- Previous by thread: any alternative to http://cliki.net ?
- Next by thread: Re: teaching kids functional programming
- Index(es):
Relevant Pages
|
