Both users and programmers tell computers what to do.
Both need programs that can figure out what the person wants the computer to do. (For the rare programmer who uses machine code directly, I'll consider the CPU to be a hardware program for interpreting machine code.)
Both must phrase their instructions in terms of commands that the computer already knows how to perform.
Is the difference that the instructions given by the programmer are somehow stored, to be replayed later?
Are there any other differences?
Friday, February 29, 2008
Wednesday, February 20, 2008
Helping The Good Programmer
In Helping The Average Programmer, Lawrence Kesteloot argues that creating a language to help good programmers is a waste of time.
The fundamental argument seems to be that because good programmers are statistically insignificant, helping them doesn't do the world much (if any) good.
I think this argument is flawed because it neglects the kind of work being done by good programmers versus average programmers. Most programmers (average, good, and bad) probably spend most of their time working on problems that have already been solved.
However, I suspect that the percentage of good programmers is much higher among those trying to solve new problems and come up with new ways to use computers. If I am correct (and I'm not sure how to prove or disprove it), then that means that helping good programmers helps us all by increasing the rate and quality of invention.
Good programmers make up a very small percentage of all the programmers, and they’re already very efficient, so making them slightly more efficent will have negligable effect on the world.
Average programmers, though, are everywhere. Make them 5% more efficient, or make them create 5% better programs, and you’ve made a huge difference. That’s why Basic (and the whole suite of Microsoft tools like Access) are so great. (Not “great” as in “good programs”, “great” as in “good for the world”.)
The fundamental argument seems to be that because good programmers are statistically insignificant, helping them doesn't do the world much (if any) good.
I think this argument is flawed because it neglects the kind of work being done by good programmers versus average programmers. Most programmers (average, good, and bad) probably spend most of their time working on problems that have already been solved.
However, I suspect that the percentage of good programmers is much higher among those trying to solve new problems and come up with new ways to use computers. If I am correct (and I'm not sure how to prove or disprove it), then that means that helping good programmers helps us all by increasing the rate and quality of invention.
Monday, February 11, 2008
What Y means to me
It's become fashionable recently for people to discuss their views on the Y-Combinator. Here are mine, which I came up with a few years ago while attempting to understand the thing after reading Essentials of Programming Languages and The Why of Y.
I view the Y-Combinator as a combination of two ideas: Self application, and handling the recursion in a different function from the one that does the computation.
I'll start with self application.
To use this function, you pass it a copy of itself. For example, (fib fib 5) => 8.
We can curry this.
Now passing fib a copy of itself creates the Fibonacci function. You could call it with ((fib fib) 5) => 8, or you could do something like (define fibonacci (fib fib)) and then (fibonacci 5) => 8.
The second idea is a way to have the recursion handled by an entirely different function. We define fib like this.
Using this technique, we don't pass fib a copy of itself. We need to give it something special, something that behaves like the result of the call to fib, even though that isn't finished yet. Gee, that sounds like recursion. Let's make a function (let's call it Y!) that calls f with the thing that this function is going to return.
In my mind, I view the "(y f)" here as "the thing I'm about to return."
You may notice an infinite loop here, since y calls itself directly and unconditionally. In order to break the infinite loop, we use something called eta expansion. If a function f takes one argument, then the function f, and the expression (lambda (n) (f n)) both mean the same thing. The difference is that the eta expanded version won't try to figure out what f is until it's time to call it. The dangerous part of this definition of y is the call (y f), so let's eta expand that.
Now the recursion is handled in y. Every time fib calls (lambda (n) ((y f) n)), which is called f inside fib, another call to fib happens.
We can evaluate things like ((y fib) 5) => 8, or we can (define fibonacci (y fib)) and then (fibonacci 5) => 8.
Okay, but that definition of y is directly recursive. Is there a way to get rid of the recursion entirely? Yep. Self application. First, let's change the definition so that it uses an explicit lambda.
And then, let's add the extra parameter for self application.
Notice how (x x) replaces y in the recursive calls.
By combining these two tricks, we are now able to simulate recursion even if we don't have it. Here is a final copy of the code to play with. Notice how it contains no recursive functions in the normal sense. No definitions contain the name that they are defining, yet it is still able to perform a recursive computation.
Paste that into your Scheme interpreter, and you should get out "8".
For a really, really good time, we can take out all of the definitions and do it all with function calls.
Again, paste that into your Scheme interpreter, and you should get out "8".
I view the Y-Combinator as a combination of two ideas: Self application, and handling the recursion in a different function from the one that does the computation.
I'll start with self application.
(define (fib f n)
(cond ((= n 0) 1)
((= n 1) 1)
(else (+ (f f (- n 1)) (f f (- n 2))))))
To use this function, you pass it a copy of itself. For example, (fib fib 5) => 8.
We can curry this.
(define (fib f)
(lambda (n)
(cond ((= n 0) 1)
((= n 1) 1)
(else (+ ((f f) (- n 1)) ((f f) (- n 2)))))))
Now passing fib a copy of itself creates the Fibonacci function. You could call it with ((fib fib) 5) => 8, or you could do something like (define fibonacci (fib fib)) and then (fibonacci 5) => 8.
The second idea is a way to have the recursion handled by an entirely different function. We define fib like this.
(define (fib f)
(lambda (n)
(cond ((= n 0) 1)
((= n 1) 1)
(else (+ (f (- n 1)) (f (- n 2)))))))
Using this technique, we don't pass fib a copy of itself. We need to give it something special, something that behaves like the result of the call to fib, even though that isn't finished yet. Gee, that sounds like recursion. Let's make a function (let's call it Y!) that calls f with the thing that this function is going to return.
(define (y f) (f (y f)))
In my mind, I view the "(y f)" here as "the thing I'm about to return."
You may notice an infinite loop here, since y calls itself directly and unconditionally. In order to break the infinite loop, we use something called eta expansion. If a function f takes one argument, then the function f, and the expression (lambda (n) (f n)) both mean the same thing. The difference is that the eta expanded version won't try to figure out what f is until it's time to call it. The dangerous part of this definition of y is the call (y f), so let's eta expand that.
(define (y f) (f (lambda (n) ((y f) n))))
Now the recursion is handled in y. Every time fib calls (lambda (n) ((y f) n)), which is called f inside fib, another call to fib happens.
We can evaluate things like ((y fib) 5) => 8, or we can (define fibonacci (y fib)) and then (fibonacci 5) => 8.
Okay, but that definition of y is directly recursive. Is there a way to get rid of the recursion entirely? Yep. Self application. First, let's change the definition so that it uses an explicit lambda.
(define y (lambda (f) (f (lambda (n) ((y f) n)))))
And then, let's add the extra parameter for self application.
(define y ((lambda (x) (lambda (f) (f (lambda (n) (((x x) f) n)))))
(lambda (x) (lambda (f) (f (lambda (n) (((x x) f) n)))))))
Notice how (x x) replaces y in the recursive calls.
By combining these two tricks, we are now able to simulate recursion even if we don't have it. Here is a final copy of the code to play with. Notice how it contains no recursive functions in the normal sense. No definitions contain the name that they are defining, yet it is still able to perform a recursive computation.
(define y ((lambda (x) (lambda (f) (f (lambda (n) (((x x) f) n)))))
(lambda (x) (lambda (f) (f (lambda (n) (((x x) f) n)))))))
(define (fib f)
(lambda (n)
(cond ((= n 0) 1)
((= n 1) 1)
(else (+ (f (- n 1)) (f (- n 2)))))))
(define fibonacci (y fib))
(fibonacci 5)
Paste that into your Scheme interpreter, and you should get out "8".
For a really, really good time, we can take out all of the definitions and do it all with function calls.
((((lambda (x) (lambda (f) (f (lambda (n) (((x x) f) n)))))
(lambda (x) (lambda (f) (f (lambda (n) (((x x) f) n))))))
(lambda (f)
(lambda (n)
(cond ((= n 0) 1)
((= n 1) 1)
(else (+ (f (- n 1)) (f (- n 2))))))))
5)
Again, paste that into your Scheme interpreter, and you should get out "8".
Subscribe to:
Posts (Atom)
