raganwald
Friday, April 20, 2007
  Recursion
In a certain University’s Computer Science program, you have a choice between following a “Theoretical Computer Science” track and a “Computer Engineering” track. The theoretical track starts with Scheme, moves into ML and Haskell, and drops into languages like Joy along the way for constructing certain proofs.

The practical track is a fairly standard JavaSchools approach, starting with Java, moving smoothly into Java with generics, and finishing with a big XML bang.

Most students entering the program have no trouble selecting the best track for themselves. The vast majority take the engineering course, mostly motivated by the promise of being sent into the bowels of BigCo on work terms. They pack into cavernous lecture halls and memorize design patterns, then spend days typing up verbose “Hello World” programs on their Dell laptops. The highly nerd-oriented remainder tend to jump into the theory track. They’re the ones reading “Good Math, Bad Math” over WiFi on their MacBooks.

A lonely few don’t know quite what to do. They might want to start a company, they might want to become consultants, and they enjoy a little recreational computing. They’re the ones who read raganwald, as a matter of fact. To help them out, the administration has constructed a little aptitude test.

They are placed in a testing hall, and each applicant is given two numbered envelopes. They are told that each envelope contains instructions. They are to follow them as best they can. The proctor calls out “Open the first envelope,” and they get started.

Inside is a piece of paper torn into large shards. The paper has writing on it, but you can’t read the instructions without piecing the paper back together. The students busy themselves with the puzzle, and in a few minutes almost all have fit the pieces back together and can read the single sentence on the page: “open the second envelope and follow its instructions.”

Well, this is a time limited examination and they immediately open the second envelope. Inside is a single sheet of paper with writing on it. And do you know what? Most of the applicants follow its instructions: they write their name and student number on the back of the paper and hand it into the proctor. These students are immediately sent into the Computer Engineering track, where they go on to be fine members of our profession: intelligent and practical.

A few, however, open the second envelope and their eyes light up immediately. Without pausing, they tear the page into strips, reducing it to a problem they have already solved!

The proctor guides these students gently from the room, and they are marked down for Theoretical Computer Science.

And we got Sheena
 

Comments on “Recursion:
So the point was that the theory people don't follow instructions? I'm not sure why the theory people would rip of the paper again.
 
Paul:

Oh dear, maybe it is neither funny nor obvious... My bad!

I don't want to become one of "those people" who explain their own jokes and then laugh at the punch line...

I will say that the theory people were following the instructions, in a way that they might say is simpler and more elegant than the engineering people.

FWIW, it's a very old joke. The version I heard involves boiling water...
 
Well, maybe I didn't get it because I'm a computer informations systems major which at my college is the major where you learn things like databases and web programming and the CS majors learn the lower level activities. My major sounds like what the engineering majors would take. Don't know though. Although my school still teaches a lot of stuff in C and C++ even for my major. Nothing is in Java that I'm aware of.
 
I'm a computer informations systems major which at my college is the major where you learn things like databases and web programming and the CS majors learn the lower level activities.

I think... I think... I think that both databases and "lower level activities" are both engineering activities.

But maybe I misunderstand what you mean when you say "lower level activities."

Where would I go in your school to learn about the Y Combinator, Category Theory, or Hypergame?
 
@Paul: Functional programming (or any sort of programming, I suppose) is about taking a large problem and reducing it to a bunch of little parts you've already solved. Then you combine those little solutions to arrive at a solution for the original problem.

The theory people look at the paper and realize they've already solved the problem of piecing together torn bits of paper. They can tear the paper up and hand it in to the proctor thinking they have the correct answer because they've already solved that particular problem.

There's a pun - tearing paper could be seen as "reducing it" - and it's ironic that if they were to apply their previous solution, they'll have simply returned to the larger problem of filling out their contact info.
 
Err...what about someone who opened the first envelope, and thought "f***, this is stupid. I will just open up the second envelope and see what that says" ;)
 
what about someone who opened the first envelope, and thought "f***, this is stupid. I will just open up the second envelope and see what that says"

MBA!
 
I think the two groups should have been reversed. The group that tore the second paper were implementing a design pattern; the group that followed the instructions clearly understand currying.
 
I majored in CS at Dartmouth College, which has always insisted that theoreticians should know how to program, and that practical programmers should know how to write proofs. This has always seemed an admirable balance to me.

The heart of Dartmouth's practical programming track is CS 23, a group project class with professor-assigned groups and shifting project requirements. It's an admirable simulation of the real world, and students who survive it make great programming interns.

But over the years, I've come appreciate the theory classes most of all. I love to tackle hard problems: computer vision, robotics, search. And this is where all the skills of theoretical CS pay off: writing proofs, grokking mathematics, and all that supposedly impractical stuff.

Math may be hard, but it's also ridiculously useful.
 
I would have never properly "reduced" the problem (though I've always wished I could).
I'm a corporate code monkey who never even had any higher math. I do constantly seek and learn, but some things are just too time consuming (I'll never again have time to go back and get the math and when I tried some self teaching it seemed no less time consuming).
So this is my dilemma; should I forge ahead as an interminably incomplete programmer or start my own janitorial business?
 




<< Home
Reg Braithwaite


Recent Writing
Homoiconic Technical Writing / raganwald.posterous.com

Books
What I‘ve Learned From Failure / Kestrels, Quirky Birds, and Hopeless Egocentricity

Share
rewrite_rails / andand / unfold.rb / string_to_proc.rb / dsl_and_let.rb / comprehension.rb / lazy_lists.rb

Beauty
IS-STRICTLY-EQUIVALENT-TO-A / Spaghetti-Western Coding / Golf is a good program spoiled / Programming conventions as signals / Not all functions should be object methods

The Not So Big Software Design / Writing programs for people to read / Why Why Functional Programming Matters Matters / But Y would I want to do a thing like this?

Work
The single most important thing you must do to improve your programming career / The Naïve Approach to Hiring People / No Disrespect / Take control of your interview / Three tips for getting a job through a recruiter / My favourite interview question

Management
Exception Handling in Software Development / What if powerful languages and idioms only work for small teams? / Bricks / Which theory fits the evidence? / Still failing, still learning / What I’ve learned from failure

Notation
The unary ampersand in Ruby / (1..100).inject(&:+) / The challenge of teaching yourself a programming language / The significance of the meta-circular interpreter / Block-Structured Javascript / Haskell, Ruby and Infinity / Closures and Higher-Order Functions

Opinion
Why Apple is more expensive than Amazon / Why we are the biggest obstacles to our own growth / Is software the documentation of business process mistakes? / We have lost control of the apparatus / What I’ve Learned From Sales I, II, III

Whimsey
The Narcissism of Small Code Differences / Billy Martin’s Technique for Managing his Manager / Three stories about The Tao / Programming Language Stories / Why You Need a Degree to Work For BigCo

History
06/04 / 07/04 / 08/04 / 09/04 / 10/04 / 11/04 / 12/04 / 01/05 / 02/05 / 03/05 / 04/05 / 06/05 / 07/05 / 08/05 / 09/05 / 10/05 / 11/05 / 01/06 / 02/06 / 03/06 / 04/06 / 05/06 / 06/06 / 07/06 / 08/06 / 09/06 / 10/06 / 11/06 / 12/06 / 01/07 / 02/07 / 03/07 / 04/07 / 05/07 / 06/07 / 07/07 / 08/07 / 09/07 / 10/07 / 11/07 / 12/07 / 01/08 / 02/08 / 03/08 / 04/08 / 05/08 / 06/08 / 07/08 /