The Official RDrama Computer Science Reading Group
My dear !codecels, hello and welcome to the first meeting of RDrama's Computer Science Reading Group! Here's the idea - we (read: I) pick a computer science textbook, then post a list of sections and exercises from that textbook each week. In the thread, feel free ask questions, post solutions, and bully people for asking stupid questions or posting stupid solutions. If you don't want to read along, I'll post the complete exercises in the OP, so you can solve them without needing to read the book.
SICP
The book I'm starting with is 'the Structure and Interpretation of Computer Programs' (abbreviated SICP). It's a software engineering textbook written by Gerald Jay Sussman and Hal Abelson from MIT. The book builds programming from the ground up: starting with a very simple dialect of Scheme and growing it into a language with lazy evaluation, object-orientation and a self-hosting compiler. It's a fun book: the exercises are hands-on and interesting, the writing is informative without being droll, and both the book itself and a corresponding lecture series (complete with a 80s synth rendition of 'Also Sprach Zarathustra') are available for free online.
Languages
The book uses (a small subset of) Scheme as its primary language, but feel free to try using a different language. The book's dialect of scheme is available through Racket, but most lisps will work with only minor changes. Other dynamically-typed, garbage-collected languages with higher-order functions will also not require much hacking: there is an edition written in JavaScript 
, as well as a partial adaptation to python 
. High-level, statically typed languages might also work: Java/Kotlin/C# 
seem doable, but I don't know those languages well. Strongly typed languages like Haskell will require some real hacks, and I'd avoid doing it in C, C++ or Rust.
Exercises
The book is split into five chapters:
- Building Abstractions with Procedures
- Building Abstractions with Data
- Modularity, Objects and State
- Metalinguistic Abstraction
- Computing with Register Machines
This week, I'll be posting exercises from the first chapter. The chapter is pretty easy for those familiar with programming already, so I just want to get it out of the way. Here are the selected exercises:
Exercise 1.8
Newton's method for cube roots is based on the fact that if
yis an approximation to the cube root ofx, then a better approximation is given by the value(x/y² + 2y) / 3. Use this formula to implement a cube-root procedure which is wrong by at most0.01.
Exercise 1.12
The following pattern of numbers is called Pascal's Triangle.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...
The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it. Write a procedure that computes elements of Pascal's triangle.
Exercise 1.18
Devise a procedure generates an iterative process for multiplying two integers in terms of adding, doubling, and halving and uses a logarithmic number of steps.
Exercise 1.31
Write a procedure called
productthat returns the product of the values of a function at points over a given range (product(l, r,step,f) = f(l) * f(l+step) * f(l + 2 * step) * ... * f(r)). Show how to definefactorialin terms ofproduct. Also use product to compute approximations to using the formulaπ/4 = (2 * 4 * 4 * 6 * 6 * 8 ...) / (3 * 3 * 5 * 5 * 7 * 7 ...)
Exercise 1.43
If
fis a numerical function andnis a positive integer, then we can form thenth repeated application off, which is defined to be the function whose value atxisf(f(...(f(x))...)). For example, iffis the functionx → x + 1, then thenth repeated application offis the functionx → x + n. Iffis the operation of squaring a number, then thenth repeated application offis the function that raises its argument to the2 * nth power. Write a procedure that takes as inputs a procedure that computesfand a positive integernand returns the procedure that computes thenth repeated application of f. Your procedure should be able to be used as follows:repeated(square,2)(5) = 625
Have fun! 
Jump in the discussion.
No email address required.
SICP for GNU Info
https://pomf2.lain.la/f/h2scvw9t.info
Jump in the discussion.
No email address required.
More options
Context