Lisp

I have decided to focus more on Clojure, and start working on How To Design Programs (aka “HtDP”), and then onto Structure and Interpretation of Computer Programs (aka “SICP”, PDF here). HtDP is written by the founders of the Racket project, and SICP uses Scheme (one of the authors, Gerald Sussman, invented Scheme along with Guy L. Steele; I think Scheme was Steele’s PhD thesis).

I looked one last time into The Reasoned Schemer. I changed to a different KanRen library. More of the examples worked, but this book is really not coming together for me as quickly as the other ones did. I think I will put aside the “Little” books, at least for the time being. I think it might be time to get ready to climb Mount SICP.

Many people have said that SICP is a good way to “level up” (as the gamer kids put it). Many people have said it gave them something like the famous “Lisp enlightenment”, that it altered their perception of how to make software and made them better. As the Teach Yourself CS site put it: Because SICP is unique in its ability—at least potentially—to alter your fundamental beliefs about computers and programming. Not everybody will experience this. Some will hate the book, others won’t get past the first few pages. But the potential reward makes it worth trying.

SICP is an introductory CS text used at MIT. The general consensus is that you will get more out of it if you have been in software development for a few years. It is a bit much for most people right off the bat. I have been through Simply Scheme, which states in the last chapter that it is intended to prepare you for SICP. HtDP was made as an alternative to SICP; the authors felt that SICP requires a lot of higher math, and if they made a less math-heavy alternative they could introduce more people to CS and help them become better programmers.

One of the authors of Simply Scheme wrote an essay entitled “Why Structure and Interpretation of Computer Programs matters”. He states that unlike other introductory textbooks, SICP does not spend a lot of time on the syntax of a specific language, but instead teaches broader concepts. Someone at the local Clojure meetup once said to me that if you can work through the problems in SICP, “you can solve any problem with parentheses”. In other words, you learn how to design programs.

A few years back, MIT (and a few other schools using SICP) replaced Scheme and SICP with other texts that use Python. Sussman said there were a few reasons for this. One is that he and Harold Abelson (one of the other co-authors of SICP) were tired of teaching the course after more than 15 or so years. Another reason is that SICP was designed for programmers who would make systems from the ground of using smaller components. Now a lot of programming is just linking or wiring together components that are black boxes. Sussman called it “programming by poking”. You could contrast this with the SICP style of “analysis-by-synthesis”. The site Lambda The Ultimate has a post with a link to a now-extinct blog post, but there is a quote that summarizes the ideas nicely. There is also a link to a thread on Hacker News. This has come up several times on Hacker News and Reddit.

There is a section in the preface to Simply Scheme that covers this:

There are two schools of thought about teaching computer science. We might caricature the two views this way:

• The conservative view: Computer programs have become too large and complex to encompass in a human mind. Therefore, the job of computer science education is to teach people how to discipline their work in such a way that 500 mediocre programmers can join together and produce a program that correctly meets its specification.
• The radical view: Computer programs have become too large and complex to encompass in a human mind. Therefore, the job of computer science education is to teach people how to expand their minds so that the programs can fit, by learning to think in a vocabulary of larger, more powerful, more flexible ideas than the obvious ones. Each unit of programming thought must have a big payoff in the capabilities of the program.

(I think you could also call these the “business mindset”, and the “engineering mindset”: Do things in a way that the suits think they understand, or actually knowing what you are doing.)

Per a comment on the Lambda The Ultimate post, one of the authors of HtDP said that other departments sent students to their CS intro course to learn how to think. That is where I want to go. I feel that “programming by poking” is what I have been doing. I feel like I should be better at this than I am, and that there has to be a better way of doing things. Where “progress” isn’t just learning yet another vendor’s product.

Why not level up? Why settle for poor understanding? As one of the commenters on Hacker News put it: What about the people who make the black boxes? How do you know they know what they are doing? If you could learn to solve any problem with parentheses, why wouldn’t you?

The obligatory links (I have not gone through most of these):

• SICP course notes
• MIT SICP Lectures on YouTube – this set is taught by Abelman and G. Sussman, two of the authors of SICP
• Same MIT SICP Lectures on MIT site
• MIT 6.001 Structure and Interpretation, 1986 on YouTube – I think this includes the prior set and an additional set
• 6.001 SICP: Structure and Interpretation of Computer Programs (2004) this is taught by a different MIT professor
• UC Berkeley CS 61A The Structure and Interpretation of Computer Programs, Spring 2010
• Lectures for a course using How To Design Programs
• I think this is a course using HtDP by Gregor Kiczales, author of The Art of the Metaobject Protocol
• SICP walk-through with a virtual meetup group
• Robert Martin finds SICP, and talks about it
• SICP Review
• Structure and Interpretation of Computer Programs: SICP – Conor Hoekstra – CppCon 2020

You’re welcome.

Image from “Evangelia quattuor, pars”, an 11th-century manuscript housed at the Bibliothèque nationale de France. Source gallica.bnf.fr / BnF; image assumed allowed under Public Domain.

I know I said I was going to focus on Clojure, but I looked at some other things in the past week.

I am looking into some Amazon certification for AWS. There is a big push to get certified at my current employer, and I would like to do something different.

I started the org-mode tutorial from Udemy.

I also looked at The Seasoned Schemer. I think that having already gone through Simply Scheme I may have gotten some of the concepts. A lot of it deals with recursion.

Chapter 12 dealt with “letrec”. letrec is like let, but instead of binding a name to a variable or data, you can bind a name to a function, and you can call that function recursively.

One thing this can allow you to do is it can relieve you of the need to call a helper function. In Simply Scheme, I made all the functions tail-recursive. To do this, you usually need a parameter that is the “accumulator” or the output (see this answer on Stack Overflow or my post here).

In The Seasoned Schemer, they use letrec for functions in which one argument does not change and one does, such as checking if an atom is a member of a list, or performing a union of two lists:

(define (union-letrec s1 s2)
  (letrec
      ([U (lambda (set-1)
            (cond [(null? set-1) s2]
                  [(ss-sc:member? (car set-1) s2) (U (cdr set-1))]
                  [else (cons (car set-1) (U (cdr set-1)))]))])
    (U s1)))

I know I think the whole argument about Lisp/Scheme being hard to read because of all the parentheses is usually exaggerated, here I think for these letrec examples there might be something to it. These were hard to type correctly from the book. For example, the internal function has to be after the “(set-1)” which is the argument to the “lambda”, but before the closing parens for “lambda”. And the call to the internal function has to be before the closing call to “letrec”. You can have multiple functions defined in a “letrec”, and your call to the internal functions can be in a cond.

A helper function to do the actual work with tail-recursion might be more lines of code, but I think it is easier to understand.

Chapter 13 is about let/cc, combining let with “call-with-current-continuation”. I think some people consider this Scheme’s defining feature.

They have a function rember-upto-last which takes an atom and a list of atoms and removes everything in the list before the last instance of the atom as well as the atom.

Here it is:

(define (rember-upto-last a lat)
  (let/cc skip
      (letrec
          ([R (lambda (lat)
                (cond [(null? lat) '()]
                      [(ss-sc:equal5? (car lat) a) 
                       (skip (R (cdr lat)))
                       ; (R (cdr lat))
                       ]
                      [else (cons (car lat) (R (cdr lat)))]))])
          (R lat))))

Here is a tail-recursive version:

(define (rember-upto-last-r a lat)
  (let/cc skip
      (letrec
          ([R (lambda (lat outp)
                (ss-sc:display-all "Calling R w/lat: " lat 
                                   " and outp: " outp)
                (cond [(null? lat) (reverse outp)]
                      [(ss-sc:equal5? (car lat) a) 
                         (skip (R (cdr lat) '()))
                         ;(R (cdr lat) '())
                       ]
                      [else (R (cdr lat) (cons (car lat) outp))]))])
        (R lat '()))))

Both of these have a commented out call to “(R (cdr lat)” (with a second arg in the tail-recursive version) below the call to “skip”.[Note 1]. In the tail-recursive version, either  call gives the proper result. In the regular version, we are building our answer through a chain of calls to “cons”. The “skip” eliminates all the pending “cons” calls, and the function is called anew with whatever the then-current values are. In the tail-recursive version, we can get rid of those “pending” values ourselves.

I think Java might get continuations soon.

You’re welcome.

[Note 1]: For some reason, the code formatter I am using does not always color comments correctly. In all variants of Lisp that I have seen, comments start with a semi-colon.

Image from Psalterium Gallicanum with Cantica, a 9th-century manuscript from the monastery of St. Gall, housed at Central Library of Zurich. Image from e-Codices. This image is assumed to be allowed under Fair Use.