Solving SICP | Hacker News Reader

Solving SICP

lockywolf.wordpress.com

194 pointstodsacerdoti44 comments

Kudos for finishing it. I’ve gone on a similar quest with https://mk12.github.io/sicp, but I’m still on chapter 3. I keep getting distracted by new ways of improving the website rather than making progress in the book.

Great website! Hope you continue with it, love the layout

Wonderful report! So now we know how long it takes to solve all of the problems: 729 hrs.

SICP is hard to work through even if you're just reading but wow, the exercises are on another level! I wonder how it compares to, say, a physics or biology textbook

You can try it yourself with the beautiful 'Structure and Interpretation of Classic Mechanics' from Sussman.

I don't remember exercises, but I expect they are as long as SICP, while maybe there is more emphasis on learning theory more than practicing coding

Is it worth it though? You could build a half-decent base in Factorio in that time.

SICP is a sprawling book. It's been rightly criticised; it is inaccessible without a strong maths and (electronic) engineering background, it's somewhat unfocused, and its code is archaic. But it blew my mind some 20 years ago when I worked through it over many train journeys. A more focused, more accessible book would be objectively better, but I think it would lose something. SICP, with its wild rambling through so many disparate topics, really did leave me feeling that I could make the computer do anything.

the expression / circuit bridge in chapter 5 is timeless imo

Some of the SICP exercises use math and circuits as the "business domain" you are programming about, but you don't need independent knowledge of those topics to write the programs. The requirements are pretty well specified.

I barely survived Calc 3 and have never taken an engineering course. I was fine.

I found some of the exercises in building abstractions with procedures pretty inaccessible with implicit maths knowledge necessary. From building abstractions with data onwards they become well spec'd and straightforward.

That's quite a time investment; about 3 months on a full-time basis.

One detail intrigued me. The author has a PhD in Informatics but "had never used any programmers’ editor other than Notepad++". He credits being able to touch-type for some of his efficiency and went about learning a swathe of tools including Emacs and several diagramming languages. These diagram files and the OrgMode file are a valuable reference in themselves.

There's probably more nuance with 2.29 than is led onto here. The problem appears straightforward and there seems to be simpler solutions out there than the one described in the article.

Did the author overthink it or are the simple solutions not correct?

I think the author may have overthought it, but it kind of depends on comfort with recursion and how focused he was when working on the problem.

If you aren't comfortable with recursion, I can see it taking a while.

It's basically a walk down a binary tree with some extra logic. You have to write two recursive functions, one each for (b) and (c) but they have basically the same structure with different return values. The function for (b) can be used for (c) (not the most efficient, but it does work). (d) requires minor modifications to the functions created in (a)-(c) so you can start with copies of the originals and make the change, I think it's a one symbol change in each function, or maybe two.

I think the author made a typo, and they actually meant to refer to 2.92, not 2.29. The table preceding the part mentioning 2.29 only includes 2.92. And 2.29 doesn't include the text "This is not easy!”, whereas 2.92 does.

That makes a lot more sense. It also matches the times they record for the exercise. For context, 2.92 is:

> Exercise 2.92. By imposing an ordering on variables, extend the polynomial package so that addition and multiplication of polynomials works for polynomials in different variables. (This is not easy!)

2.29 is what I described in my other comment, it's a pair of functions walking a binary tree with conditional logic based on if it's an interior or exterior node, returning either a sum or a true/false value. Which is not hard at all and their time was only 83 minutes. Versus their claimed time of 2400 minutes for 2.92.

Is there a modern SICP book? I tried to go through it once, but immediately got stuck because my math/physics was so rusty that I would have to spend more time researching the background than actually solving the CS puzzle

https://cs.brown.edu/people/sk/ and search for books.

Maybe reading this will help:

https://cseducators.stackexchange.com/questions/7478/which-b...

I'm still trying to decide of Fowler porting Refactoring to Javascript from Java is a good thing or a bad thing, but I'd kind of like to see someone port SICP to Python or maybe Elixir and see how it goes.

Hate to do this but https://chatgpt.com/share/67c78ef6-2418-8000-a40a-59d5b708ba...

Yes, I'm sure given 729 hours it'd come up with something useful.

Think of 1 1/2 hour commute. That is almost 2 years. It's a graduate level text. Way advanced.

I would mention Knuth, but many problems in his books are still yealding PhDs. Way above my grade.

There is a lot of problems I would like to look at hints.

Kudos to your achievement.

Is 'It is' here referring to SICP?

SICP is a graduate level text? That was literally the first CS book I had to buy as an undergrad.

Yeah, it was written for first year students at MIT. Those are definitely more advanced students than at many other universities, but it is written for 1st-2nd year college students in a technical (math, science, engineering) discipline.

There were places that were all too happy to copy MIT as well.

SICP modified for Python exists (I haven't looked at it, so not vouching or commenting) https://wizardforcel.gitbooks.io/sicp-in-python/content/

SICP was ported to JS though I'm not particularly keen on the result. https://sourceacademy.org/sicpjs/

The code is convoluted, in my opinion, because it tries to hue too closely to the Scheme code in the original giving some unnatural looking JS code as a result. For example:

  function member(item, x) {
    return is_null(x)
           ? null
           : item === head(x)
           ? x
           : member(item, tail(x));
  }

There are examples which have even more but that was the first one I came across clicking the TOC randomly. In Scheme it would be expressed something like this:

  (define (member? item set)
    (cond ((null? set) #f)
          ((equal? item (car set)) #t)
          (else (member item (cdr set)))))

While the parens cause some brains to segfault, the structure of this (how each condition ties to each result) is clearer than that JS mess.

I'm convinced someone wrote a (bad) Scheme to JavaScript transpiler to convert the code. It looks like nothing anyone would actually write.

I've seen code like that in production, it's not as strange as you think (pretty common in reactjs codebase). After a while, you just get used to it and read past the weird syntax. It's not really that different from a switch-case or if-else block:

  function member(item, x) {
    return   /* if   */ is_null(x)
           ? /* then */ null
           : /* elif */ item === head(x)
           ? /* then */ x
           : /* else */ member(item, tail(x));
  }

It’s not the language to blame in SICP, if any. Scheme is totally find (and cool).

Extra whitespace to put the `cond` clauses in columns can make it even more clear, for "visual" looking at code, rather than only "verbal":

    (define (member? item set)
      (cond ((null? set)             #f)
            ((equal? item (car set)) #t)
            (else                    (member? item (cdr set)))))

For bonus points, line up the key variable in the clauses, and it's easier to see visually that the `cond` is about that one variable:

    (define (member? item set)
      (cond ((null?       set)       #f)
            ((equal? (car set) item) #t)
            (else                    (member? item (cdr set)))))

Which accidentally also lines up with one of the procedure's arguments, though I didn't intend that one, but you could double down on that:

    (define (member? item      set)
      (cond ((null?            set)  #f)
            ((equal? item (car set)) #t)
            (else                    (member? item (cdr set)))))

This isn't some deep thing; just a little example of how sometimes whitespace, other than just indenting at the beginning of the line, helps to exposure some of the structure visually.

In my humble opinion, a for loop is easier to reason about then recursion. So one of JavaScript's "features" is that it does not have proper recursion support, so you need to break out the recursion into a for loop, or the call stack will eventually become too big.

What do you call "proper recursion support"? I assume it's tail-call optimisation, but I don't think it's a property of Javascript-the-language, but rather a property of the interpreter/compiler? I don't think there's anything inherent to javascript that would prevent V8 to have TCO (and I think it did use to have it) for example.

And in fact I _think_ some engines do have TCO (bun? javascriptcore?), but I could be wrong

ES6 added this: https://262.ecma-international.org/6.0/#sec-tail-position-ca...

So TCO is part of the language standard but not universally implemented. You are correct about the ones that support it.

The authors of the JS version of SICP had a problem: Scheme is expression based and JavaScript is statement based.

When I say Scheme is expression based, I am alluding to the fact that constructs such as `if`, `cond`, `case` etc. are all expressions. Scheme also has several binding constructs (let, letrec, etc) that allows in an expression context to bind the result of a computation in a subexpression. These are all expressions.

The expression version of `if` is in JavaScript called ternary if. A direct translation from Scheme to JavaScript therefore uses ternary if.

But why make a direct translation?

Well, later in the book one writes an interpreter for Scheme. This interpreter shows how the expression based language constructs are implemented. It is therefore necessary that the reader is very familiar with these constructs.

https://sourceacademy.org/sicpjs/

https://htdp.org/

How to design programs (mentioned in the article).

That depends on what you mean by a 'modern SICP book', if you mean a newer book for learning Computer Science (CS), then of course there are many. 'How to Design Programs (HtDP)' would be an example.

If you mean 'SICP but in a language that's more popular nowadays', there's SICP in JavaScript.

If you mean a newer book which teaches CS in Scheme, I don't really know. HtDP uses Racket, which is a spin-off of Scheme, but outside of that I'm not really aware of any books which could be called 'modern'. There's Concrete Abstractions, which I would call 'SICP-lite' as it's a fair bit lighter on the maths, so that would be my first go-to if the maths are a bit intimidating.

I already posted this another time, but I think this book deserve to be more known.

Peter Van Roy, Concepts, Techniques, and Models of Computer Programming, 2004

It uses the language developed in this book (Oz).

The book constructs many of the current programming paradigms, starting from almost nothing, with an emphasis on software design.

See the paradigms poster built http://www.info.ucl.ac.be/people/PVR/paradigmsDIAGRAMeng201....

I Have seriously read about 1/3 of SICP. Seing this level of dedication and actual time required is very reassuring. I found many of the exercises to be be deep, deep rabbit holes where you eventually had to set a time limit for moving on if you have any ambition actually completing the book. The depth seems to increase for every chapter! You could probably spend a lot more time than 729 hours and it would still be both a productive use of time and well worth the investment knowledge-wise.

I think there are better ways to use SICP. In an institutionally educational setting you'd have peers and mentors to help figuring things out, for example.

Going at it alone is a thing for people that are already alienated by waged labour or whatever, and likely not the most efficient way to learn its lessons, thought it might be the only obviously available. Personally I prefer to dip in for a short while once or thrice a year or when I have something I'd like to get better at that I know it teaches.

Still, neat presentation.

This post is a treasure. I have too many itches to scratch and would want to know at least a ballpark figure for the time investment.

One suggestion for the already complete and detailed post: what is the personal/professional gain you get for your time investment? In this case maybe: „program design became clearer after having worked through SICO.“ or „I can discuss design more formally now“ or just „It was interesting and everyone talked about it, so I needed to know“

I would think some parts of the book are more valuable than others. That goes for every book including classics like TAOCP and the compiler dragon book.

It would be interesting to know what parts are pure gold and worth deep study and which parts can be skimmed or consulted as a reference.

I was lucky enough to read it during my studies and to have a teacher that made very good Slides focusing on the most interesting parts.

I think finding someone that guide you through the book allows to go way faster than alone.

Now, while the concepts were extremely illuminating, I think following the book but doing the exercises in haskell is also a nice path. Haskell was another lecture following the one on SICP by the same teacher, and it uses most of the same ideas, sometimes formulated a little differently, but on a more modern language.

I still remember my exam where we received ~6 pages double column of printed lisp, no comments. The code was a compiler, and we needed to change it so that it can jump back in time using call with cc. Difficult to do in 3h and on paper but very fun.

This is an interesting post in its way, but I hate how it's presented. The subject doesn't really call for this impersonation of academic rigor, since it's fundamentally an unscientific, subjective exercise - "How long did I, one particular computer scientist, take to work through this massive and occasionally open-ended task?" That's asking for an introspective essay, not a battery of tables and graphs.

But I think this is a useful critique of SICP, for those trying to teach from it or in particular for those trying to self-study it: it wasn't really designed to be done front-to-back (contrary to the nonsensical justifications given here); it's not a realistic demand of any student, or even necessarily a particularly productive use of their time unless they intended to move into compiler development. Its problem sets occasionally give the illusion that SICP itself will teach you what you need to solve these incredibly difficult problems and perform these incredible accomplishments, which is partially what's responsible for its legendary status. Not recognizing that - and it'd be hard to blame a solo learner for that - can be incredibly discouraging when one finds that they can't do things with the tools SICP has given and blame themselves for not appreciating those tools rather than SICP for asking too much and giving too little.

https://lockywolf.net/2020-10-29_scheme-story.html

Here he shows 2 reviews he gave up on, that he resorted to data because he didn't know how to put it in words.

Reply on news.ycombinator.com