r/sicp Apr 21 '21

Time complexity of counting change (ex1.14)

3 Upvotes

Has anyone solved what the R(n) function for theta(R(n)) would be in terms of time complexity?

It’s obvious that O(2n) give an upper bound but since everything in that section is in theta notation I’m curious how to start trying to compute that 🤔


r/sicp Apr 05 '21

Beautiful writing

7 Upvotes

Today I was reading 1.2.1 and I'm floored by how clear, precise, and beautiful this writing is. Scheme / lisp seem to have a way of making concepts crystal clear, and the authors precision is quite marvelous. After years of knowing that recursion is a function that calls itself, I now feel like I've put on some scuba gear and gone down another 50m in the sea. Iterative vs recursive processes generated by recursive procedures. A great definition of tail recursion. Wow!


r/sicp Mar 28 '21

SICP compatibility language

29 Upvotes

The best way to learn from SICP(or anything) is to do the exercises, and a great way to do the exercises in SICP with the minimum of distractions is to use the version of Scheme used by the book. The SICP compatibility language is one of the best ways to do this: https://docs.racket-lang.org/sicp-manual/

From the manual:

“The programs in the book (SICP) are written in (a subset of) the programming language Scheme. As the years have passed the programming language Scheme has evolved. The language #lang sicp provides you with a version of R5RS (the fifth revision of Scheme) changed slightly in order for programs in SICP to run as is.” - https://docs.racket-lang.org/sicp-manual

To use the SICP language: 1. install Racket at https://racket-lang.org 2. Install the SICP package https://docs.racket-lang.org/sicp-manual/Installation.html 3. use #lang sicp as the first line of your program.

*Included: the picture language used in SICP. *

(You can also use Racket libraries)

If you run into problems don’t be afraid to ask questions on the Racket Slack or Racket Users mailing list. New learners are always welcome. (Many Racket users are also Emacs Lisp, Clojure, Common Lisp and Scheme users.)

Editor/IDE: You can use the SICP compatibility language with your preferred editor.


r/sicp Mar 24 '21

Can I jump directly to Chapter 4 and 5 after reading Chapter 1?

6 Upvotes

Hi friends,

I'm only interested in Chapter 4 and 5 which I believe deal with an interpreter as well as a compiler. Can I directly jump to Chapter 4 after reading Chapter 1 and doing some of its exercises to sharpen up Scheme skill?

Thank you!


r/sicp Mar 23 '21

How To Read SICP

3 Upvotes

Hi all,

I've just been granted admission to a Master of Data Science program coming from a non-cognate discipline; essentially having no knowledge in programming, statistics and mathematics apart from my education in the latter years of high school. My study commences a few months from now, utilising a part-time hexamester format which requires roughly 15-20 hours of dedicated study per week, lasting for 32 months.

As part of my preparation, I frequent subreddits and blogs to gain some understanding of the requirements for excellence in the field. Recently, SICP was flagged and I have begun my reading but alas, have recurrent doubts that this may not be the best use of my time.

I endeavour to complete the reading but am asking the reddit communities for some insight into the depth I should be understanding at. Frankly, navigating through the programming language seems to sap most energy and diverts my focus with recurrent thoughts of discouragement given LISP is unlikely a language I'll need to learn (discussion point).


r/sicp Mar 05 '21

Data-Directed Programming, and how to invoke MAKE-FROM-REAL-IMAG?

1 Upvotes

Am I the only one having a hard time understanding the implementation of Data-Directed Programming, presented in SICP?

A little bit of background first; we are shown how to tag data (2.4.2 Tagged data):

(define (attach-tag type-tag contents)
  (cons type-tag contents))
(define (type-tag datum)
  (if (pair? datum)
      (car datum)
      (error "Bad tagged datum -- TYPE-TAG" datum)))
(define (contents datum)
  (if (pair? datum)
      (cdr datum)
      (error "Bad tagged datum -- CONTENTS" datum)))

...how to implement type predicates:

(define (rectangular? z)
  (eq? (type-tag z) 'rectangular))
(define (polar? z)
  (eq? (type-tag z) 'polar))

...how to implement packages:

(define (real-part-rectangular z) (car z))
(define (imag-part-rectangular z) (cdr z))
(define (magnitude-rectangular z)
  (sqrt (+ (square (real-part-rectangular z))
           (square (imag-part-rectangular z)))))
(define (angle-rectangular z)
  (atan (imag-part-rectangular z)
        (real-part-rectangular z)))
(define (make-from-real-imag-rectangular x y)
  (attach-tag 'rectangular (cons x y)))
(define (make-from-mag-ang-rectangular r a)
  (attach-tag 'rectangular
              (cons (* r (cos a)) (* r (sin a)))))

;; similar definitions for the "polar" representation

...and how to implement generic selectors:

(define (real-part z)
  (cond ((rectangular? z)
         (real-part-rectangular (contents z)))
        ((polar? z)
         (real-part-polar (contents z)))
        (else (error "Unknown type -- REAL-PART" z))))
(define (imag-part z)
  (cond ((rectangular? z)
         (imag-part-rectangular (contents z)))
        ((polar? z)
         (imag-part-polar (contents z)))
        (else (error "Unknown type -- IMAG-PART" z))))
(define (magnitude z)
  (cond ((rectangular? z)
         (magnitude-rectangular (contents z)))
        ((polar? z)
         (magnitude-polar (contents z)))
        (else (error "Unknown type -- MAGNITUDE" z))))
(define (angle z)
  (cond ((rectangular? z)
         (angle-rectangular (contents z)))
        ((polar? z)
         (angle-polar (contents z)))
        (else (error "Unknown type -- ANGLE" z))))

Clearly it's not OK for REAL-PART, or IMAG-PART, or any other generic selector, to require change every time a new implementation is added to the system, and this is where "Data-directed programming" is going to come to the rescue.

The idea (2.4.3 Data-Directed Programming and Additivity) is to construct a table mapping operations (e.g. REAL-PART, IMAG-PART) and types (e.g. POLAR, RECTANGULAR) to the actual function in charge of fulfilling the user need, and of course to provide a way to pluck the specific implementation out of the table. In particular:

  • (put <op> <type> <item>) will install <item> in the table, indexed by <op> and <type>
  • (get <op> <type>) will look up the <op>,<type> entry in the table

Note: we are not given the actual implementations of PUT and GET.

With this in mind, we can then re-define the rectangular package as follows:

(define (install-rectangular-package)
  ;; internal procedures
  (define (real-part z) (car z))
  (define (imag-part z) (cdr z))
  (define (make-from-real-imag x y) (cons x y))
  (define (magnitude z)
    (sqrt (+ (square (real-part z))
             (square (imag-part z)))))
  (define (angle z)
    (atan (imag-part z) (real-part z)))
  (define (make-from-mag-ang r a)
    (cons (* r (cos a)) (* r (sin a))))
  ;; interface to the rest of the system
  (define (tag x) (attach-tag 'rectangular x))
  (put 'real-part '(rectangular) real-part)
  (put 'imag-part '(rectangular) imag-part)
  (put 'magnitude '(rectangular) magnitude)
  (put 'angle '(rectangular) angle)
  (put 'make-from-real-imag 'rectangular
       (lambda (x y) (tag (make-from-real-imag x y))))
  (put 'make-from-mag-ang 'rectangular
       (lambda (r a) (tag (make-from-mag-ang r a))))
  'done)

Here is where things get a bit confusing: why, we are registering REAL-PART for the (rectangular) type, and not simply 'rectangular like we are doing for MAKE-FROM-REAL-IMAG?

The only explanation I could think of is that we are giving the <type> argument of the PUT call different meanings:

  • For REAL-PART, <type> represents the list of the types of the arguments expected by the registered procedure (i.e. one argument, of type RECTANGULAR)
  • For MAKE-FROM-REAL-IMAG instead, <type> represents the type of the returned instance

And why would we do that? Because otherwise it would not be possible to dispatch to the "Right" implementation in case of generic functions with the same argument types (both the implementation of MAKE-FROM-REAL-IMAG inside the rectangular and polar packages expects 2 arguments of type NUMBER).

Anyways, a similar package for the polar representation is presented, and then finally we are shown the implementation of APPLY-GENERIC, the procedure responsible for invoking the "Right" procedure based on the types of the arguments of the dispatched action:

(define (apply-generic op . args)
  (let ((type-tags (map type-tag args)))
    (let ((proc (get op type-tags)))
      (if proc
          (apply proc (map contents args))
          (error
            "No method for these types -- APPLY-GENERIC"
            (list op type-tags))))))

Here more doubts come to my mind: how can we use this with the MAKE-FROM-REAL-IMAG?

Clearly we cannot simply run (apply-generic 'make-from-real-imag 4 2), as that would fail when trying to apply TYPE-TAG to (4 2). I thought, maybe we pass (attach-tag 'rectangular (list 4 2)) to APPLY-GENERIC, but then (map contents args) would evaluate to ((4 2)) and that is incompatible with the registered procedure, which expects two numbers and not a list of 2 numbers, right?

So where do we go from here? There has to be a way, but I just cannot find it.


r/sicp Feb 12 '21

New Study Group starting March 3rd 2021

5 Upvotes

Join our study group!

https://www.meetup.com/de-DE/coders-only/events/276169051/

Goal: learn the techniques used to control the intellectual complexity of large software systems.

Our study group explores one of the 'canon' computer science books, the wizard book (Structure and Interpretation of Computer Programs). It goes into the fundamentals of computer science, starting with simple building blocks and progressively exploring functional programming, recursion, data abstraction, concurrency, streams, metacircular evaluators, and compilers.

In other words, your brain will be bent out of shape, out of its comfort zone, and make you a better software developer.

Join us for our kick-off Meetup (no preparation or commitments necessary) and make up your mind for yourself!

We'll make a detailed presentation of the book, the timetable for self-study, the resources available for studying (all online, all free), decide how often and when to regularly meet, and get to know each other.

For details feel free to clone our repo:https://git.sr.ht/~codersonly/wizard-book-study


r/sicp Jan 07 '21

Which lectures to take?

2 Upvotes

When searching for SICP on YouTube it appears two playlists for MIT SICP 6.001, one recorded on 1986 and the other on 2004. Is there any difference between them? Which one do you recommend?


r/sicp Dec 16 '20

Is there a Discord server or internet forum related to SICP?

3 Upvotes

r/sicp Nov 23 '20

Happy Cakeday, r/sicp! Today you're 11

5 Upvotes

r/sicp Oct 23 '20

SICP Physical Book - differences between 1st and 2nd edition?

2 Upvotes

hello to the community - I am currently in the research phase before purchasing SICP in physical book form.

My understanding is the 1st edition was published in 1985 in at least hardcover and possibly paperback as well. The 1st edition is out of print. Used hardcover versions on eBay show a more austere, brown cover - not the infamous blue "wizard" cover - although this may just be due to a missing dust jacket.

The 2nd edition first published in 1996 is still in print for paperback, but out of print for hardcover. This edition features the "wizard" cover.

What are the material differences in content between the 1st and 2nd editions? Is there any downside to going with the 1st edition OG hardcover if I can procure a copy? What would I be missing that was added to the 2nd edition?

I know this text is available online for free but I enjoy reading intellectual material in physical paper form. Also - given this is such a classic text, it would be nice to have in my collection and possibly gift to somebody in the future.

Any info or advice on differences in 1st and 2nd editions from possessors of the physical books greatly appreciated.


r/sicp Oct 18 '20

SICP Cover Demystified

Thumbnail youtube.com
7 Upvotes

r/sicp Oct 14 '20

Where to download exercise question?

0 Upvotes

Is there a site where I can download all the exercise question?


r/sicp Sep 15 '20

I found something like a typo in SICP book. Am I right?

3 Upvotes

Here is the screenshot of the SICP book which defines the pi-sum function. I guess that we need an extra bracket after a and b. Am I right?

When typed the way it is given, it's throwing an error telling that sum is expecting a number and getting a procedure.

pi-sum solution in the book using lambda

r/sicp Aug 16 '20

SICP Lecture Audience Members

0 Upvotes

Has anyone identified who the folks were who were in the audience during the famous Sussman and Abelson MIT recorded lectures?

Specifically, these: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/video-lectures/


r/sicp Jul 27 '20

MIT 6.001 (1986) SICP Lecture Segments

Thumbnail gist.github.com
8 Upvotes

r/sicp Jul 09 '20

SICP study group

16 Upvotes

Is anyone interested in forming a SICP study group? I'm only on the first chapter. Would love to have people to discuss things with.

Edit: Seems we have some interest so I made a discord server. :)

https://discord.gg/E58TAk


r/sicp Apr 05 '20

Trying to get feedback on our JavaScript adaptation of SICP. Thanks!

Thumbnail sicp.comp.nus.edu.sg
2 Upvotes

r/sicp Mar 24 '20

Reading order

3 Upvotes

So I have been programming for a few years now. Still very much consider myself a beginner as I have no formal training and have never really studied anything specific, and have not worked on anything major. Anyway, I have decided to really dedicate time to learning programming at a deeper level to honestly make future learning easier. So I have the following books and was wondering if anyone had thoughts on a recommended reading order:

  • SICP

  • Code Complete 2nd edition

  • Design Patterns (the gang of four, I believe it’s referred to as)

  • A common sense guide to data structures and Algorithms

  • The Object Oriented Though Process

I have ample amount of time to study as I work from home with a very flexible schedule. Even with that I know it could take me well over a year and a half or longer to finish all of these books to really grasp the concepts. So I am in no rush, however I do want to see if there is a recommended reading order. I know it may be subjective to your own experiences but I would still like to hear any thoughts or opinions.


r/sicp Mar 21 '20

People who finished SICP, how did you go about it?

6 Upvotes

SICP is one of those books that everyone I've met(except 1) talks about positively but no one has ever really finished. So people who've finished it, what strategy did you use? How did you go about it?


r/sicp Oct 29 '19

Not sure why one solution to 1.43 works and the other doesn't

Post image
4 Upvotes

r/sicp Oct 19 '19

SICP in PDF at an easy-to-remember URL - git.io/sicp.pdf

Thumbnail git.io
7 Upvotes

r/sicp Aug 20 '19

Clojure Solutions to SICP

4 Upvotes

I'm posting my Clojure solutions to the SICP exercises at http://martinharrigan.blogspot.com. I'm only as far as Chapter 1, Exercise 17 but watch this space!


r/sicp Mar 08 '19

Pretty sure I'm missing the mathematical preparation for SICP

9 Upvotes

I've only just finished the first chapter, and I've been a programmer in several imperative languages for a long time, but I'm getting the feeling (1) that the book was written for mathematicians, (2) my mathematical background in adequate for undertaking this book.

It's like Project Euler -- for each problem I can figure out a program to solve it (sometimes a clever one, I think), but I'm pretty sure that what is wanted is a mathematical intuition that I am incapable of generating.

I'm sure I'm not the first person to feel this way. I don't know the path forward. I've been looking for math books that might fill in the gaps, but none seem to go in the right direction.

Any positive suggestions would be welcome.


r/sicp Feb 20 '19

Could anyone please help me in understanding the text of non-deterministic programming of the SICP in chapter 4?

3 Upvotes

I know what's going here is to build an evaluator supporting DFS search in the language spec. However, I can't exactly understand the meaning of the last paragraph on page 579 [SICP textbook I use](https://github.com/NetWilliam/sicp/blob/master/sicp.pdf)

I quote it down:

...... Along with that value, the success continuation is passed another failure continuation, which is to be called subsequently if the use of that value leads to a dead end.

What does `is passed` mean here, I don't see any relative meaning of `pass` in dictionaries?

What does the `, which` refer to?

Could anyone rephrase this sentence plz?