Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

SICP is Under Attack

vedantk.tumblr.com

Post reply on HN
Print view View original

131–140 of 207 posts

Re: SICP is Under Attack

#131

Post by cousin_it »

davidhollander wrote: post #73

> Beautiful. I guess beauty is in the eye of the beholder. A simpler way to analyze this problem is noticing the f(n-3) term implies your function has to memorize up to 3 previous results. Then just use the coefficients from the formula to cycle the next result into memory. Using algebra and generating new coefficients as per the OP's solution is unnecessary. function f(n) if n

Nice! Also your solution makes it easy to move on to a logarithmic time solution: going from (a,b,c) to (b,c,3a+2b+c) is a linear transformation which can be expressed as a 3x3 matrix, therefore iterating it n times is equivalent to raising that matrix to the nth power, which can be done in log(n) time using square and multiply [1]. Disregard programming, study math!

In fact the exact same reasoning can be used to derive the closed form expression for the Fibonacci numbers [2], which are defined by a recurrence relation similar to the one in the OP. You raise the corresponding 2x2 matrix to the nth power by going to the eigenbasis where the matrix becomes diagonal, raising the values on the diagonal (which turn out to be the golden ratio (phi) and -1/phi) to the nth power, then changing the basis back.

[1] http://en.wikipedia.org/wiki/Exponentiation_by_squaring

[2] http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...

Re: SICP is Under Attack

#134

Post by AgentConundrum »

eliben wrote: post #113
AgentConundrum wrote: post #22

Earlier quoted context omitted.

> Also the point of SICP being language agnostic is fairly false. I remember reading a bit of Eli Bendersky's SICP blog posts[1], where he started with the premise that he was going to work through SICP using Common Lisp rather than Scheme. I think that lasted through about half of the first chapter before he moved back to Scheme because he found it too hard to handle the differences between the two - I don't remembe…

When I started the project, I preferred CL over Scheme. Later, however, I had some experience with PLT Scheme and really liked the programming environment, so I decided to give it a try. I figured that using both languages will help me understand the differences between them better. It was not some serious limitation of CL, in any case.

Thanks for clarifying, Eli.

As I said in my update, I was apparently badly misremembering a comment on your blog regarding the use of CL.

You've actually inspired me to take up a similar SICP reading/blogging project, though I'm hesitant for two reasons. First is the concern over the depth of the material. I don't have a CS degree and I'm mathematically out of shape (and I never even did a calculus class), so I'm concerned about making it to a certain point and then completely failing to be able to continue on. Second is a concern about copyright and plagiarism. I've never been clear where the line is with regards to the sort of summarizing knowledge of a whole book, since paraphrasing is still plagiarism AFAIK. Less of an issue with SICP, I'm sure, since you ended up with a signed copy, but I'm a very risk-averse individual and like to know exactly where I stand before attempting such a thing.

I'm sure that your blog will be a great resource for me when I do my version of your project, so I'd like to thank you in advance for having blazed the trail for me.

Re: SICP is Under Attack

#135

Post by omaranto »

For those who haven't read SICP: don't get the impression that it only deals with very easy stuff like the example in the post about turning a recursive definition into an iterative one. It actually touches on many of the bet ideas in CS. This post could have easily chosen a more interesting example.

Re: SICP is Under Attack

#136

Post by absconditus »

bartwe wrote: post #127
absconditus wrote: post #107

Earlier quoted context omitted.

So basically you and 90% of your colleagues hate computer science. You want a vocational education in software development, which is something different.

Who offers a vocational education at an university level? Not everybody who is smart wants to be an academic.

What does your comment have to do with what I wrote? No one is denying that many people really want a vocational education. No one is claiming that smart people should want to be academics. The point is that what people want is not computer science. Civil engineers do not enroll in physics programs and then complain that their physics professors are not teaching them anything about practical bridge construction.

Re: SICP is Under Attack

#137

Post by colanderman »

yoklov wrote: post #102
colanderman wrote: post #85

Earlier quoted context omitted.

I looked at it and thought, "easy, I'll just rewrite the Scheme function in Mercury and tell the compiler to memoize the function." Of course, obviously the point of the exercise is to encourage thinking about how a computer actually performs computations, which is in a linear, imperative fashion. In that case, why use Scheme in the first place? Its syntax and semantics encourage exactly the opposite style of program…

The point of Scheme isn't to provide you with a given feature like memoization, its to provide you with the tools so you can do it yourself. SICP covers memoization at the end chapter 3.3.3 ( http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-22.html... ): (define (memoize f) (let ((table (make-table))) (lambda (x) (let ((previously-computed-result (lookup x table))) (or previously-computed-result (let ((result (f…

The same could be said of any Turing-complete language (though I'll admit Scheme's macro system gives it a leg up when it comes to implementing new features.) But given that Scheme's syntax encourages thinking in terms of mathematical recursion, it seems silly that (a) I can't write something so simple as the Fibonacci function by using its traditional mathematical recursive definition, and that (b) SICP encourages the use of Scheme to solve problems which require thinking in terms of iteration and mutation -- this is a pedagogical faux pas.

Re: SICP is Under Attack

#138

Post by pzb »

jackpirate wrote: post #76
BlackJack wrote: post #52

Earlier quoted context omitted.

I agree that a programmer doesn't need a degree in CS, but to have a CS degree doesn't mean you're a programmer. A topic earlier showed that 26 of the ACM Turing Award winners had degrees in mathematics, and a lot of the theoretical CS is math anyways. If a student in college wants to acquire a CS degree, they should be exposed to fundamental ideas in CS, not just what they'll need to be a professional programmer.

A topic earlier showed that 26 of the ACM Turing Award winners had degrees in mathematics The field of computer science didn't exist when they went to college. They invented it, hence the awards.

This is really the root of the problem. Computer science/programming is immature as a profession. There are not clear, broadly accepted rules for what roles exist and what requirements there are for one to fill the role.

Looking at building houses (just the construction side, not the mechanical systems), we have: - Architect - Structural Engineer - Architectural Technologist - Carpenter plus construction employees not officially certified. Each of these has a specific test, both written and practical (apprenticeship), and specific roles in the building process.

In software, we have no standardized tests, so companies substitute "BSCS" for "Software Engineer" in the requirements. And there is only ever one role officially defined; there is no separate "Software Programmer". Internally every companies has "Software Engineer I", "Software Engineer II", etc however this is rarely exposed in job postings and requirements and is never standard between companies.

The software industry could solve all this hand-wringing by creating a set of standardized roles, testing to create Certificates of Qualification for each, and getting HR departments to require these. And it would be possible, even with an established industry. Canada has added several new Professionals over the last decade, working with the existing industry to define the job, requirements, and build a phase-in plan that allowed the industry to continue operating.

Re: SICP is Under Attack

#139

Post by d0m »

absconditus wrote: post #107
d0m wrote: post #43

Earlier quoted context omitted.

It's not "what the school wants to teach" but more "what the student needs to know at the end of the semester". I love SICP -- for me it was a revelation which opened a new world, and is still my favorite book -- but not everyone is like that. 90% of my colleague in my university would hate that book.. (As they hated the dragon book and anything less practical). So, as they say, "Hate the game, not the gamers". What…

So basically you and 90% of your colleagues hate computer science. You want a vocational education in software development, which is something different.

No, I said SICP was by far my favorite book. I already knew how to program before joining the university.. my goal there was to go deeper than what I already knew.

However, the big majority of my colleagues there didn't want that. They really enjoyed "Design patterns", "C++".. but hated anything potentially more abstract (Like compilers, Algorithm). Note that I'm talking about software engineering.. and not about computer science, which is really different imo (as engineer might have a more practical mind).

Re: SICP is Under Attack

#140

Post by gswang »

absconditus wrote: post #108
gswang wrote: post #78

Whoa, stop. There's a lot of issues in this article. First of all, Berkeley is NOT getting rid of SICP and SICP ideas. This is flat out untrue. I'm a recent instructor for the course, and I've spoken to several TA's about this course. Below is a rough summary of what we've discussed. This should not be construed as the "official line", but take from it what you will. First, Berkeley are not getting rid of SICP. ‎For…

I find it pretty disappointing that SICP is considered too tough for matriculants of a top CS program. Perhaps you should consider enrolling fewer students and raising standards.

I'm haven't said that, so please don't insult my students by saying that. My argument for it being a capstone stems not at all from that it's too hard. We can not, should not require our students to be putting in the amount of time necessary, in my opinion 40hrs/week, to completely 100% understand this material as a freshman. In my mind, completely understanding it is required for the 'enlightenment' that many like about SICP, but this is not true for many other courses. By putting it in Python, students can learn many useful skills along the way.

Furthermore, I'm arguing that all things being equal, the time is better spent as a senior when you might be able to get the same points for a much lower time commitment.

And, please, remember that this is just one class in a curriculum of CS courses. There is a lot of effort being put in by dozens of professors to graduate the best and brightest, which we do.

Post reply on HN