Structure and Interpretation of Computer Programs (SICP) is a classic textbook for learning how to program. The language used in the book is Scheme, a dialect of Lisp.

learn more… | top users | synonyms

7
votes
2answers
348 views

My first accumulators

Notes I'm working my way through SICP, and as I got very confused by the section on folds, I decided to try to implement foldr in scheme and javascript to understand how it works differently with ...
0
votes
0answers
31 views

How can I solve SICP 2.4 in C++11 [migrated]

This exercise ask for implement cons, car and cdr functions using only lambda functions. ...
1
vote
0answers
137 views

SICP ex. 2.42 “eight queens puzzle”

The problem can be found online here. In short, we're given the following function definition, that will recursively generate all the possible solutions for the "eight-queen-problem". ...
7
votes
2answers
156 views

Write a procedure stream-limit that finds

From SICP: Exercise 3.64. Write a procedure stream-limit that takes as arguments a stream and a number (the tolerance). It should examine the stream until it finds two successive elements ...
1
vote
0answers
139 views

Write a definition of a semaphore in terms of test-and-set! operations

From SICP: Exercise 3.47. A semaphore (of size n) is a generalization of a mutex. Like a mutex, a semaphore supports acquire and release operations, but it is more general in that up to n ...
1
vote
0answers
143 views

Write a definition of a semaphore in terms of mutexes

From SICP: Exercise 3.47. A semaphore (of size n) is a generalization of a mutex. Like a mutex, a semaphore supports acquire and release operations, but it is more general in that up to n ...
3
votes
0answers
117 views

Representing a queue as a procedure with local state

From SICP: Exercise 3.22. Instead of representing a queue as a pair of pointers, we can build a queue as a procedure with local state. The local state will consist of pointers to the ...
4
votes
1answer
182 views

Examine a list for cycles

From SICP: Exercise 3.18. Write a procedure that examines a list and determines whether it contains a cycle, that is, whether a program that tried to find the end of the list by taking ...
1
vote
0answers
252 views

[SICP ex. 3.17] correctly count the number of pairs in an irregular list structure

From SICP: For background, here is exercise 3.16: Exercise 3.16. Ben Bitdiddle decides to write a procedure to count the number of pairs in any list structure. ...
1
vote
1answer
200 views

[SICP ex. 3.8] order of evaluation of function arguments

From SICP: Exercise 3.8. When we defined the evaluation model in section 1.1.3, we said that the first step in evaluating an expression is to evaluate its subexpressions. But we never ...
1
vote
0answers
128 views

[SICP ex. 2.84] coercion of arguments using successive raising

From SICP: Exercise 2.84. Using the raise operation of exercise 2.83, modify the apply-generic procedure so that it coerces its arguments to have the same type by the method of successive ...
1
vote
0answers
275 views

(scheme [SICP ex. 2.82] coercion with multiple arguments

From SICP: Exercise 2.82. Show how to generalize apply-generic to handle coercion in the general case of multiple arguments. One strategy is to attempt to coerce all the arguments to the ...
2
votes
1answer
515 views

Huffman encoding successive-merge function [SICP ex. 2.69]

From SICP: Exercise 2.69. The following procedure takes as its argument a list of symbol-frequency pairs (where no symbol appears in more than one pair) and generates a Huffman encoding ...
1
vote
1answer
511 views

Encode-symbol for Huffman tree

From the text: Exercise 2.68. The encode procedure takes as arguments a message and a tree and produces the list of bits that gives the encoded message. ...
2
votes
1answer
265 views

Search on a binary tree

From SICP: Exercise 2.66. Implement the lookup procedure for the case where the set of records is structured as a binary tree, ordered by the numerical values of the keys. I wrote the ...
2
votes
0answers
749 views

Union-set intersection-set for a binary-tree implementation of sets [SICP ex. 2.65]

From SICP: Exercise 2.65. Use the results of exercises 2.63 and 2.64 to give (n) implementations of union-set and intersection-set for sets implemented as (balanced) binary trees.41 I ...
1
vote
1answer
272 views

Union-set for ordered representation

From SICP: Exercise 2.62. Give a (n) implementation of union-set for sets represented as ordered lists. I wrote this answer: ...
1
vote
1answer
165 views

(scheme) [SICP ex. 2.61] adjoin-set for an ordered set representation

From SICP: Exercise 2.61. Give an implementation of adjoin-set using the ordered representation. By analogy with element-of-set? show how to take advantage of the ordering to produce a ...
4
votes
1answer
165 views

Set representation allowing duplicates

From SICP: Exercise 2.60. We specified that a set would be represented as a list with no duplicates. Now suppose we allow duplicates. For instance, the set {1,2,3} could be represented as ...
1
vote
1answer
588 views

Union-set operation for unordered-list representation of sets

One way to represent a set is as a list of its elements in which no element appears more than once. The empty set is represented by the empty list. In this representation, element-of-set? ...
1
vote
0answers
282 views

Standard Algebraic Derivative Calculator [SICP ex. 2.58 part b]

I had some difficulty with this problem, so I'm sure there is a better way. Here is the question from SICP: Exercise 2.58. Suppose we want to modify the differentiation program so that it ...
3
votes
1answer
199 views

Extend sums and products functions

Exercise 2.57. Extend the differentiation program to handle sums and products of arbitrary numbers of (two or more) terms. Then the last example above could be expressed as ...
0
votes
1answer
100 views

Extending basic differentiator to handle more kinds of expressions

Exercise 2.56. Show how to extend the basic differentiator to handle more kinds of expressions. For instance, implement the differentiation rule by adding a new clause to the deriv ...
0
votes
1answer
401 views

(Scheme) [SICP ex. 2.54] Define equal?

Exercise 2.54. Two lists are said to be equal? if they contain equal elements arranged in the same order. For example, ...
1
vote
1answer
141 views

Adding, subtracting, and multiplying a vector by a scalar

Exercise 2.46. A two-dimensional vector v running from the origin to a point can be represented as a pair consisting of an x-coordinate and a y-coordinate. Implement a data abstraction ...
1
vote
1answer
142 views

(Scheme ) [SICP ex. 2.45] Write a general purpose “split” function {for SICP's imaginary language}

From SICP 2.2.4: The textbook has already defined a function (right-split ...) as follows: ...
4
votes
3answers
610 views

Eight-queens puzzle

Figure 2.8: A solution to the eight-queens puzzle. The ``eight-queens puzzle'' asks how to place eight queens on a chessboard so that no queen is in check from any other (i.e., no two ...
6
votes
3answers
710 views

Find all distinct triples less than N that sum to S

Exercise 2.41. Write a procedure to find all ordered triples of distinct positive integers i, j, and k less than or equal to a given integer n that sum to a given integer s. ...
0
votes
1answer
134 views

(Scheme) [SICP ex. 2.40] unique-pairs

From the section called Nested Mappings Exercise 2.40. Define a procedure unique-pairs that, given an integer n, generates the sequence of pairs (i,j) with 1< j< i< n. Use ...
3
votes
2answers
643 views

(scheme) [sicp ex. 2.39] reverse in terms of fold-right and fold-left

Exercise 2.39. Complete the following definitions of reverse (exercise 2.18) in terms of fold-right and fold-left from exercise 2.38: ...
2
votes
1answer
2k views

(Scheme) [SICP ex. 2.37 Matrix Multiplication

Exercise 2.37. Suppose we represent vectors v = (vi) as sequences of numbers, and matrices m = (mij) as sequences of vectors (the rows of the matrix). For example, the matrix is ...
2
votes
1answer
287 views

(Scheme) [SICP ex. 2.35] Redefine count-leaves as an accumulation

Exercise 2.35. Redefine count-leaves from section 2.2.2 as an accumulation: ...
2
votes
1answer
739 views

(Scheme) [SICP ex. 2.31] abstract tree-map function

Exercise 2.31. Abstract your answer to exercise 2.30 to produce a procedure tree-map with the property that square-tree could be defined as ...
1
vote
1answer
183 views

Square-tree using maps and recursion

Define a procedure square-tree analogous to the square-list procedure of exercise 2.21. That is, square-list should behave as follows: ...
0
votes
1answer
378 views

(scheme) [SICP ex. 2.27] deep-reverse

Exercise 2.27. Modify your reverse procedure of exercise 2.18 to produce a deep-reverse procedure that takes a list as argument and returns as its value the list with its elements ...
0
votes
2answers
919 views

A definition of for-each

Exercise 2.23. The procedure for-each is similar to map. It takes as arguments a procedure and a list of elements. However, rather than forming a list of the results, for-each just ...
1
vote
2answers
653 views

Filter a list of integers by parity (SICP ex. 2.20)

Exercise 2.20. The procedures +, *, and list take arbitrary numbers of arguments. One way to define such procedures is to use define with dotted-tail notation. In a procedure definition, ...
1
vote
2answers
1k views

(scheme) [SICP ex. 2.18] Design a procedure to reverse a list

SICP exercise 2.18 asks the following: Exercise 2.18. Define a procedure reverse that takes a list as argument and returns a list of the same elements in reverse order: ...
1
vote
1answer
155 views

A more efficient mul-interval

From 2.11 Exercise 2.11. In passing, Ben also cryptically comments: ``By testing the signs of the endpoints of the intervals, it is possible to break mul-interval into nine cases, only ...
1
vote
1answer
192 views

Interval Subtraction

From the Extended Exercise beginning in section 2.1.4, you can find exercise 2.8: Exercise 2.8. Using reasoning analogous to Alyssa's, describe how the difference of two intervals may be ...
1
vote
1answer
529 views

Church Numerals - implement one, two, and addition

Given the following exercise: Exercise 2.6. In case representing pairs as procedures wasn't mind-boggling enough, consider that, in a language that can manipulate procedures, we can get ...
0
votes
1answer
227 views

(Scheme) [SICP ex. 2.5] Represent pairs of nonnegative integers using 2^a * 3^b

Given the following exercise: Exercise 2.5. Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair a and b as the ...
1
vote
1answer
304 views

(Scheme) [SICP ex. 2.2] Midpoint of a segment

From SICP: Exercise 2.2. Consider the problem of representing line segments in a plane. Each segment is represented as a pair of points: a starting point and an ending point. Define a ...
1
vote
1answer
261 views

(Scheme) [SICP ex. 2.1] Make a version of make-rat that handles positive and negative arguments

Given the following task from SICP Exercise 2.1. Define a better version of make-rat that handles both positive and negative arguments. Make-rat should normalize the sign so that if the ...
1
vote
1answer
161 views

(Scheme) [SICP ex. 1.38] Compute e usine Euler's expansion

Given the following task: Exercise 1.38. In 1737, the Swiss mathematician Leonhard Euler published a memoir De Fractionibus Continuis, which included a continued fraction expansion for e ...
0
votes
2answers
573 views

(scheme) [SICP ex. 1.37] Infinite Continued Fraction - iterative and recursive

Given the following exercise: Exercise 1.37. a. An infinite continued fraction is an expression of the form As an example, one can show that the infinite continued fraction expansion ...
0
votes
3answers
779 views

(Scheme) [SICP ex. 1.33] Filtered-Accumulate

Given the following task: Exercise 1.33. You can obtain an even more general version of accumulate (exercise 1.32) by introducing the notion of a filter on the terms to be combined. That ...
0
votes
1answer
560 views

(Scheme) [SICP ex. 1.32] Show that Sum and Product are both examples of Accumulation

Given this task: Exercise 1.32. a. Show that sum and product (exercise 1.31) are both special cases of a still more general notion called accumulate that combines a collection of terms, ...
0
votes
1answer
667 views

(Scheme) [SICP ex. 1.29] Integral using Simpson's Rule

As an answer to this problem: Exercise 1.29. Simpson's Rule is a more accurate method of numerical integration than the method illustrated above. Using Simpson's Rule, the integral of a ...
0
votes
1answer
495 views

[SICP ex. 1.30] Iterative Sum

Given the following recursive definition of sum: (define (sum term a next b) (if (> a b) 0 (+ (term a) (sum term (next a) next b)))) ...