Skip to content
Summary of working through the exercises of the Little Schemer
Racket
Branch: master
Clone or download

readme.org

The Little Schemer

Daniel P. Friedman and Matthias Felleisen

The Little Schemer

Daniel P. Friedman and Matthias Felleisen

A concise review of this is posted on here

I’m reading this book after completing the HTDP. So consider my writings as a review of someone who has had some amount of experience beforehand with Scheme/Lisp and the concepts introduced in the book. Under this light, HTDP felt like a refined version of Little Schemer. This is felt in the way the topics are introduced. TLS introduces topics in a manner leaving a lot of room for thought. It requires figuring out working with the pieces it introduces, whereas, HTDP recipes went a step further in defining the patterns that help you operate with the pieces.

This thinking was further solidified as the commandments increasingly got similar to the design recipes which I found to be much more elaborate and helpful towards devising the recursion patterns. There’s more articulation on the part of authors in HTDP when it comes to prescribing them.

I’m ambivalent about the teaching style in the book. I don’t think I would recommend this as a book for a newbie but that’s where it is seemingly positioned towards. The book has too much and too little hand-holding at times. This unevenness was okay for me having done a fair bit of functional programming but I think it would be bumpy for a newcomer.

Chapter 1: Toys

Chapter 1 is a breezy ride through the primitive constructs atom? null? list? eq? car and cdr

Chapter 2: Do It, Do It Again, and Again, and Again …

Introduces the learner to recursion by using the basic lat? function which checks if a given data structure is entirely composed of atoms. The cond special form is introduced. The check for member? function is introduced and special forms or is introduced in this context.

Chapter 3: Cons The Magnificient

Function to remove an item rember is introduced. The cons function is introduced in this context which is used to build up results in lists. In the rember function, it is used to retain the elements after a check for equality is performed as in the member? function introduced in the previous chapter.

The chapter gets more evolved as it introduces firsts and insertion mechanisms insertR and insertL. These are good exercises in building up an intuition on how to traverse, construct, and destruct lists. This is proceeded by introducing subst function that substitutes a matching atom with another. A variant of this function that does optional substitution is introduced called subst2. Then multiinsertL, multiinsertR, multirember, and multisubst are introduced that does what these functions used to do before but now instead of doing it once, it replaces all the matching atoms.

Chapter 4: Numbers Games

The chapter teaches recursion on numbers. It introduces addition, multiplication, the data structure tuple which contains numbers, and introduces a function for adding elements in a tuple piecewise (tup+). This is followed by defining the comparator operators: <, >, and =. The chapter then gets to defining the more tricky exponentiation and division functions.

length and pick functions are defined that computes the length of a list and picks an element at the given index of the list along with rempick that removes an element at the given length.

A function that removes all the numbers no-nums is introduced.

eqan a function that checks for equality between two atoms is defined. This occur counts the occurrences of an atom in a given list. Finally a one? predicate is defined and it is used to redefine rempick introduced earlier.

Chapter 5: * Oh My Gawd *: It’s Full of Stars

The fifth chapter is a good one. It talks about good software engineering practices. As it gets to the end, it introduces recursive functions that fractally recurses on lists.

rember*, insertR*, occur*, subst*, insertL*, member* are introduced in this style.

leftmost function is introduced that does a recursive seeking for the first atom in a nested list.

Equality checks eqlist and equal are defined. These are neat functions.

This equal function is then used to redefine rember introduced earlier.

Chapter 6: Shadows

This chapter introduces evaluation of number expressions. Functions numbered and value are introduced towards this end. The idea of introducing helper functions is illustrated. Advantages of having helper functions is illustrated with by refactoring a function from infix to prefix order.

Another representation for numbers is also introduced in this chapter and a pitfall of having such a representation is also emphasized.

Chapter 7: Friends and Relations

The idea of a set is introduced in this chapter. set?, makeset, subset?, eqset?, intersect?, intersect, union, intersectall are the different functions introduced for operating on sets.

The idea of pair and build ing them is also introduced.

Using these concepts, the mathematical definition of a function and bijectivity is described.

fun, revrel, fullfun / one-to-one? are the different functions introduced towards this.

Chapter 8: Lambda the Ultimate

This is one of the chapters that has valuable content and novel concepts such as currying and continuations in it. It introduces a way to abstract by using functions as values. Functions that were introduced earlier are curried by abstracting the key functions in them.

rember-f, eq?-c, insertL-f, insertR-f, insert-g, multirember-f, multiremberT are some of them.

It shows how some of the functions such as subst and rember can be seen as a concrete version of abstract functions.

The chapter also helps the learner by showing how to create sensible helper functions that make reading code simpler.

atom-to-function is created to simplify the value function written earlier.

This chapter also introduces continuations which are a heady concept to wrap your head around.

Arithmetic operations are introduced in this chapter. numbered and value functions are introduced to check if an expression is completely composed of numbers and extract their numerical values out of them respectively. These functions are then simplified by introducing helper functions that demarcate the positions of the expressions 1st-sub-exp, 2nd-sub-exp, and operator.

The utility of having expressions designed like this is revealed by showing how to parse an arithmetic expression encoded as an s-expression: (+ 1 3) in place of its normal form: (1 + 3).

The chapter is finished off by showing an alternative representation for numbers instead of numerals using lists. Functions that work for these definitions sero?, edd1, zub1, and an addition operation on them are respectively defined.

A pitfall of this definition is also shown by pointing out that lat? defined previously won’t work with it. After this, continuations are looked at closely.

The idea of creating a lambda function which enables grouping together structures for future access is introduced. It allows for the creation of functions as well as data structures. It is a beautiful idea! The idea is introduced brusquely in the multirember&co function and it finally sets in when working with the multiinsertLR&co. I am not sure what this pedagogical method means for someone who hasn’t had prior exposure to these ideas.

But once you grok this idea, you get a feel for the power of the lambda function. Here it can be used to build up a dictionary (key/value pair) data structure that can pass in an accessor to access the accumulated data. Such as in multiinsertLR&co, you can pass in (lambda (x y z) x) to access the lat and (lambda (x y z) (+ y z)) to get the number of insertions performed.

A spin-off idea popping into my head with this is that the continuations can be passed around to other functions that do entirely different operations, but united in their nature that they can continue from the point the last function left off.

I think I need more examples to ground the idea of continuations. Don’t think the three examples of multirember&co, multiinsertLR&co, evens-only*&co were enough to pin down the idea as all three had different modes of continuing computations. First one accumulated data simply, the second one accumulated data in two different lists and the third one had a continuation points inside the accumulator.

Chapter 9: …and Again, and Again, and Again…

The idea of partial and total functions are introduced in this chapter. Partial functions are those for which the mapping is only determined for certain inputs to the function, for others, the function it keeps recursing on the input. Total functions have a value defined for all of its inputs.

Collatz conjecture, Ackermann function, and the Halting problem are introduced in this chapter. The will-stop function is used to show that the special form define cannot be used for the halting problem, but it can be described fully.

Chapter 10: What is the Value of All This?

This chapter is an attempt at writing a Lisp interpreter in Lisp. The idea of storing the values as a table inside a closure and using it for lookup on application is one of the striking lessons of the chapter. One develops a sense of how a programming language can be bootstrapped by getting acquainted with these ideas. This chapter makes you reflect on the meta-layer mechanisms that you have been using all along to encode the algorithms in the previous chapters. A lot of ideas like shadowing bindings which are reflected in the interpreter as a change in getting the first occurrence of a label are left without mention which I think makes it a bit confusing.

Log II (21)

The aim is to finish the book by the end of this year.

31 December (2)

Done

CLOCK: [2019-12-31 Tue 15:34]--[2019-12-31 Tue 16:04] => 0:30

189

CLOCK: [2019-12-31 Tue 14:48]--[2019-12-31 Tue 15:18] => 0:30

27 December (2)

184

CLOCK: [2019-12-27 Fri 17:22]--[2019-12-27 Fri 17:52] => 0:30

180

CLOCK: [2019-12-27 Fri 16:38]--[2019-12-27 Fri 17:08] => 0:30

26 December (2)

173

CLOCK: [2019-12-26 Thu 21:21]--[2019-12-26 Thu 21:51] => 0:30

164

CLOCK: [2019-12-26 Thu 18:25]--[2019-12-26 Thu 18:55] => 0:30

23 December (1)

155

CLOCK: [2019-12-23 Mon 22:16]--[2019-12-23 Mon 22:46] => 0:30

20 December (1)

152

CLOCK: [2019-12-20 Fri 16:19]--[2019-12-20 Fri 16:49] => 0:30

19 December (3)

147

CLOCK: [2019-12-19 Thu 17:39]--[2019-12-19 Thu 18:09] => 0:30

147

CLOCK: [2019-12-19 Thu 16:32]--[2019-12-19 Thu 17:02] => 0:30

147

CLOCK: [2019-12-19 Thu 15:40]--[2019-12-19 Thu 16:10] => 0:30

18 December (3)

145

CLOCK: [2019-12-18 Wed 18:40]--[2019-12-18 Wed 19:10] => 0:30

144

CLOCK: [2019-12-18 Wed 18:07]--[2019-12-18 Wed 18:37] => 0:30

142

CLOCK: [2019-12-18 Wed 17:31]--[2019-12-18 Wed 18:01] => 0:30

10 December 2019 (3)

140

CLOCK: [2019-12-10 Tue 12:55]--[2019-12-10 Tue 13:25] => 0:30

137

CLOCK: [2019-12-10 Tue 12:21]--[2019-12-10 Tue 12:51] => 0:30

132

CLOCK: [2019-12-10 Tue 10:46]--[2019-12-10 Tue 11:16] => 0:30

9 December 2019 (2)

127

CLOCK: [2019-12-09 Mon 16:34]--[2019-12-09 Mon 17:04] => 0:30

121

CLOCK: [2019-12-09 Mon 15:42]--[2019-12-09 Mon 16:12] => 0:30

6 December 2019 (2)

118

CLOCK: [2019-12-06 Fri 16:02]--[2019-12-06 Fri 16:32] => 0:30

114

CLOCK: [2019-12-06 Fri 15:28]--[2019-12-06 Fri 15:58] => 0:30

5 December 2019 (4)

111

CLOCK: [2019-12-05 Thu 17:48]--[2019-12-05 Thu 18:18] => 0:30

106

CLOCK: [2019-12-05 Thu 17:18]--[2019-12-05 Thu 17:48] => 0:30

95

CLOCK: [2019-12-05 Thu 16:48]--[2019-12-05 Thu 17:18] => 0:30

88

CLOCK: [2019-12-05 Thu 15:00]--[2019-12-05 Thu 15:30] => 0:30

4 December 2019 (1)

81

CLOCK: [2019-12-04 Wed 12:28]--[2019-12-04 Wed 12:58] => 0:30

2 December 2019 (2)

52

CLOCK: [2019-12-02 Mon 14:11]--[2019-12-02 Mon 14:36] => 0:30

31

CLOCK: [2019-12-02 Mon 13:25]--[2019-12-02 Mon 13:55] => 0:30

1 December 2019 (1)

21

CLOCK: [2019-12-01 Sun 19:27]--[2019-12-01 Sun 19:57] => 0:30

Log

Daily

HeadlineTime
Total time7:30
\_ Daily7:30

9 September 2015 (99-100)

Page 100

CLOCK: [2015-09-09 Wed 22:32]--[2015-09-09 Wed 23:02] => 0:30

8 September 2015 - (99)

7 September 2015 - (99)

6 September 2015 - (76 - 99)

Pomodoros Done: 14 Pages: 99 Rate: 99/14 Remaining Pages: 94 Pomodoros Remaining: 13.29

Page 99

CLOCK: [2015-09-06 Sun 19:36]--[2015-09-06 Sun 20:06] => 0:30

Page 92

CLOCK: [2015-09-06 Sun 19:04]--[2015-09-06 Sun 19:34] => 0:30

Page 86

CLOCK: [2015-09-06 Sun 18:28]--[2015-09-06 Sun 18:58] => 0:30

Page 80

CLOCK: [2015-09-06 Sun 17:22]--[2015-09-06 Sun 17:52] => 0:30

5 September 2015 - 3 (45 - 76)

Pomodoros Done: 10 Pages: 76 Rate: 76/10 Remaining Pages: 117 Pomodoros Remaining: 15.39

Page 76

CLOCK: [2015-09-05 Sat 20:32]--[2015-09-05 Sat 21:02] => 0:30

Page 68

CLOCK: [2015-09-05 Sat 19:58]--[2015-09-05 Sat 20:28] => 0:30

Page 57

CLOCK: [2015-09-05 Sat 03:58]--[2015-09-05 Sat 04:28] => 0:30

4 September 2015 - 2 (18 - 45)

Pomodoros Done: 7 Pages: 45 Rate: 45/7 Remaining Pages: 148 Pomodoros Remaining: 23.02

Page 45

CLOCK: [2015-09-04 Fri 22:27]--[2015-09-04 Fri 22:57] => 0:30

Page 34

CLOCK: [2015-09-04 Fri 21:53]--[2015-09-04 Fri 22:23] => 0:30

3 September 2015 - 2 (7 - 18)

Pomodoros Done: 5 Pages: 18 Rate: 18/5 Remaining Pages: 175 Pomodoros Remaining: 48.61

Page 18

CLOCK: [2015-09-03 Thu 15:39]--[2015-09-03 Thu 16:09] => 0:30

Page 11

CLOCK: [2015-09-03 Thu 12:36]--[2015-09-03 Thu 13:06] => 0:30

2 September 2015 - 3 (0 - 7)

Pomodoros Done: 3 Pages: 7 Rate: 7/3 Remaining Pages: 186 Pomodoros Remaining: 79.71

Page 7

CLOCK: [2015-09-02 Wed 19:42]--[2015-09-02 Wed 20:12] => 0:30

Page 3

CLOCK: [2015-09-02 Wed 19:12]--[2015-09-02 Wed 19:42] => 0:30

Front Matter

CLOCK: [2015-09-02 Wed 18:33]--[2015-09-02 Wed 19:03] => 0:30

Chapterwise

  • Frontmatter - 2
  • Chapter 1: Toys - 2.5
  • Chapter 2: Do It, Do It Again, and Again, and Again … - 1
  • Chapter 3: Cons the Magnificent - 3
  • Chapter 4: Numbers Games - 2.5
  • Chapter 5: * Oh My Gawd *: It’s Full of Stars - 2.5
  • Chapter 6: Shadows - 0.5
  • Chapter 7: Friends and Relations
  • Chapter 8: Lambda the Ultimate
  • Chapter 9: … and Again, and Again, and Again, …
  • Chapter 10: What is the Value of All of This?
  • Intermission

Estimate

<2019-12-10 Tue 16:36> At most this is going to take 10-15 pomodoros more. Meaning it takes something like 40 pomodoros to complete the book if were previously familiar with functional programming.

<2019-11-18 Mon 03:57> There was a long break in the continuum. But back on it now.

<2015-09-02 Wed 20:13> - 350 Pomodoros <- <2015-09-04 Fri 22:58> This was seemingly wrong. I thought this to be another HTDP but looks like it’s much smaller and almost as fundamental.

<2015-09-03 Thu 13:05> - At the current rate, it looks like there’s a chance to end this in 50 Pomodoros. But very unlikely.

<2015-09-04 Fri 22:20> - If the rest of the chapters are as easy as the current ones, then I’m looking at a completion time of 75-100 Pomodoros.

<2015-09-04 Fri 22:57> - The Current calculation shows that only 20 Pomodoros remains but that’s only if I maintain the current breezy rate which is only possible because I’m familiar with the current recursion patterns, I have to see how quickly this escalates and to where.

<2015-09-05 Sat 20:29> - The current rate shows only 16 or so pomodoros is required. But I’m thinking that at least 30 would be needed.

<2015-09-06 Sun 19:30> - Things are requiring more effort because it requires more thought, but I think it’s going to get easier. If all the chapters are as demanding, then I’m looking at a completion under 80 pomodoros, otherwise, if it goes as easy before it’s a < 40 pomodoros job. But anywhere between 20 - 40 hours looks very like

You can’t perform that action at this time.