Chapter 9 of ‘The Little Schemer’

I finally finished chaper 9 of The Little Schemer. This was about partial functions, total functions, and ended with the applicative-order Y combinator.

Frankly, what I understood in this chapter I did not see the point of, and I am not sure there is much point in the parts I do not understand. I think a total function returns a unique value for every input, and partial functions do not. Some of the functions they described as partial sometimes did not return values. Which to me sounds like a badly-designed function.

Maybe Godel’s incompleteness theorem has seeped into our collective consciousness to such a degree that the idea that some functions cannot be computed seems obvious.

Maybe I am not smart enough to be one of those super high-level math/language theory people. I realize I do not have the inclination to do so. I do not have much interest in conjectures about functions that do not return values. I will have to ask a few people I know who have been through SICP if this is the sort of thing in that book. I will finish The Little Schemer and go on to The Seasoned Schemer in a while.

I went through the part about the Y-combinator a second time, and I am not too sure I understand it or see the point. Is there a point? According to some guy named Mike, the point of the Y-combinator is:  The Y combinator allows us to define recursive functions in computer languages that do not have built-in support for recursive functions, but that do support first-class functions.

Are there languages that fit that description? I did some googling, and I found a Hacker News discussion about “The Why of Y” on Dreamsongs (an interesting website I hope to explore in depth someday). As one commenter points out, the article goes into the How of Y, but never the Why.

The Seasoned Schemer says you only need to understand the first eight chapters of The Little Schemer to go through TSS. So hopefully I should be fine. I was hoping to get through TLS more quickly. I am more busy at work, and chapters 8 and 9 were a lot harder (and had more concepts that were new to me) than the first seven.

I have not gone through these yet, but here are a few more links I found about total and partial functions:

You’re welcome.

Update on ‘The Little Schemer’

I am almost through with The Little Schemer. I got through the first seven chapters fairly quickly. There are no exercises per se. They will ask questions, invite you to figure out the answer, and show you. I admit, a few times I peeked, but only after trying to get it myself.

There were a few things in chapter 8 that were mind-bending. One was using higher-order functions for code-reuse.

In chapter 3, the authors introduce a few functions. One is “rember”, which removes an element (or member) from a list:

Another is “insertR”, which inserts a new element to the right of an old element in a list:

The third is “insertL”, which inserts a new element to the left of an old element:

The functions are pretty much identical. In chapter 8, they make a base function, and then make three more to cover the three different requirements.

It works just like the original:

This reminds me of something that Eric Normand showed in Purely Functional, where he puts anonymous functions in the values of a map. I wrote about that in August of 2018.

The truly mind-bending part was the “collectors”. Dark arts, these are.

They define a function that does the usual removing of members. It takes an additional parameter which is a function that does some calculations/manipulations on the resulting list. But in the recursive calls, the function uses inline lambdas to make additional collections.

Here is their explanation from page 140; the function is (multirember&co a lat f), where “a” is an atom, “lat” is a list of atoms, and “f’ is a function: It looks at every atom of the lat to see whether it is eq? to a. Those atoms that are not are collected in one list ls1 ; the others for which the answer is true are collected in a second list ls2 . Finally, it determines the value of (f ls1 ls2 ).

Here is the multirember&co function:

Here is the function we will use in our test:

The second argument is unused in last-friend. So when you use last-friend, it will count how many elements are not equal to the first argument. If it returned the length of y, it would tell us how many times the first argument is in the list.

Here are the tests in Racket:

Later, they use collectors on functions that work on multi-level lists. There is a recursive call within the collector.

I think I understand this, but I am not entirely sure about it. I was able to figure out some of the collector examples as they went along. Truly this is unholy power.

You’re welcome.

On To The Little Books

I finished the poker program from Chapter 15 of Simply Scheme, and I finished Chapter 24.

I have decided I am willing to let MengSince1996 be the King of Berkeley, and move on to Daniel Friedman’s “Little” books.

The first is “The Little Schemer“. This seems to deal with recursion. The first sequel is “The Seasoned Schemer“. The co-author of these books is Matthias Felleisen, one of the founders of Racket. On his Northeastern University page, he states that “The Seasoned Schemer” deals with higher-order functions, set! and continuations.

Next is “The Reasoned Schemer“. This bridges functional programming and logic programming. I work with a rules engine in my day job. I wonder if that is what this is about.

The next book is “The Little Prover“. According to the book’s page on the MIT Press site, this book “introduces inductive proofs as a way to determine facts about computer programs.” Honestly, I am not too clear what that means at this point.

The most recent book in the series is “The Little Typer“. For this book, Friedman and co-author David Thrane Christiansen made a language for the book using Racket.

I will probably use Racket for all these books instead of straight Scheme because I want to be able to run a tests and not type and re-type function invocations every time I make a change. In order to use tests, I had to require the R6RS packages into a program using “#lang racket/base”. I do not think there is a way to use the Racket unit test libraries in an R6RS program. So there are a lot of prefixes.

I like prefixes before function names. It is a bit more typing, and maybe it is not as clean, but I like to know where everything is coming from. One of the things that I did not like about Rails was there were no import or require statements. Everything was everywhere. That made tutorials look very interesting, but it was frustrating finding documentation for classes if you wanted to see what else the gems could do.

I plan on getting through these faster than I took to get through Simply Scheme.

See also my mentions of these books in a post from a few years ago.

You’re welcome.

More Progress On Simply Scheme

I am closer to finishing Simply Scheme. I have completed almost all the regular chapters.

Most of the other people who have github repos for Simply Scheme have not gotten as far as I have. It’s me, buntine, and some guy in New Zealand named MengSince1996. I might go back to the poker project in chapter 15 and finish that; then it will just be me and Meng. As soon as I get through chapter 24.

To be honest, I am not too clear that I learned a whole lot. I admit, some of the exercises were pretty hard, but overall a lot of the main concepts were not new to me. I had done a few other Scheme tutorials before Simply Scheme, and I have been working with Clojure on and off for a while, so I was already familiar with higher-order functions.

I did learn more about recursion, especially tail recursion. I tried to make all my recursive functions tail-recursive. This made them longer that the non-recursive versions, but I think it is a good practice to get into. Recursion is not a hard concept, but I still think it helps to go through exercises like, “Do this weird thing with recursion.”

There was an answer on Stack Exchange about tail recursion; someone wrote that you should prefer using higher-order functions, and go with tail recursion as a last resort. I assume this person was referring to the built-in higher-order functions, like map, reduce and filter. Simply Scheme threw a lot of things at you where the Big Three would not work (like filtering out the first instance of a predicate but leaving any others). Sometimes you just gotta recur. Interestingly, I think that the Big Three themselves rely on recursion. I have not been able to find the Common Lisp or Racket implementations of the Big Three, but I did find a page for a course at Aalborg University in Denmark that gives source code for the Big Three (there is one page with map and filter, and another page with reduce. Chapter 19 of Simply Scheme also gives the Big Three, with some hints in Chapter 14.

I did get a bit tripped up with lists. There were a few times I sent a function a pair instead of a list. (Yes, I know this could be a problem if I go forward with most Lisps; the Clojure community seems to prefer vectors over lists.) The way the Lisp family handles lists is different than any other language. I think in most languages, you add stuff to the end. In Lisps, although many Lisps have “append” functions, I think the preferred way to make lists is to use “cons” to add to the front.

It is interesting the way languages use the same word to mean different things, or different words for the same thing. An array in C, C++ or Java does not exist in Ruby (at least, not when I was using it). What Ruby calls an array is like a list in Java. Clojure lists are like Common Lisp/Scheme lists, and vectors in Lisps are like lists in Java. I should probably find a book on data structures and learn more about this stuff.

Maybe I was ready for SICP from the beginning.

You’re welcome.

2019-08-13: Thoughts On Simply Scheme

I may not finish the rest of Simply Scheme.

Chapter 22 deals with files and I/O, and some of the exercises and examples are not working. Simply Scheme came out just after R5RS, but I cannot find anything about a specific version. It might even be running R4RS.

I guess the I/O functions work differently in different implementations. Or perhaps Racket is handling things differently. My goal of completing 100% of Simply Scheme will not happen.

I do not know what I will do next. The options are: The Little Schemer books, How To Design Programs, climb Mount SICP, or get back to Clojure.

You’re welcome.

2019-06-30 Update

I am up to chapter 19 in Simply Scheme. This chapter is higher-order functions.

I looked into a couple of other Clojure web frameworks this month. Someone did a presentation on Duct at the Austin Clojure meetup a while back. I might have to look at James Reeves’ presentation on Integrant at Skills Matter, since Duct is built on Integrant. (That presentation is hard to search for; if you search for “Integrant”, you get anything to do with “integration”.)

There is a tutorial on Duct by someone at Circle Ci that I was kind of able to follow. Until I saw this code:

I am not too clear what that does. Perhaps knowing more about Integrant will help. (There are also other presentations on Duct at Skills Matter here and here.)

There is also Clojure on Coast (Github repo here, website here). I think the aim is to be Rails for Clojure. I might try this out too. I would really like to work with Clara Rules, and I think a web app might be the best way to enter data.

Or I might just stick with Luminus.

You’re welcome.

2019-04-07: Done with Chapter 15 of Simply Scheme

I am done with chapter 15 of Simply Scheme. I have been working through SS for a while. Sometimes I come home from work, and I do not feel like doing anything. Or I get stuck and take a break.

I took a break when I got to chapter 9. Then I started back up, and flew through lambdas and recursion. I started making my answers tail-recursive, so mine were a bit bigger than other repos I found with answers. They do not cover tail recursion in the text, but I thought it was a good idea to work on it. I got stuck on question 5 in Chapter 15. I ported my answers to Clojure, then to Racket (with the emacs Racket mode). Eventually I wound up back at the question I had problems with.

I spent a lot of time on it, and I think the problem was that I was trying both do it with tail recursion and to follow the text’s recommendation, which is NOT tail-recursive. I was having no luck with the “Leap of Faith”, so I decided to try solving the problem with higher-order functions, and then port the answers to recursion. In Chapter 14, they have a section called “How To Use Recursive Patterns” in which they show how to use recursion to do every/map, keep/filter and accumulate/reduce. Doing it that way, I solved the problem pretty quickly.

I think I read somewhere that if you have the choice to use recursion or higher-order functions, you should use higher order functions.

I ran some tests comparing my solutions (one with recursion and one with every) with someone who followed the text’s recommended solution. Usually theirs was a bit faster. But if you give the functions a number with 8 digits, mine are noticeably faster.

At first I thought that “tail recursion” meant that the “tail call” had to be at the bottom of a function. I kind of thought that is what people meant when they said the recursive call had to be the last thing called. But you can have tail recursion even in every branch of a cond or an if statement.

Here are a couple of implementations of factorial from a CS course at the University of Washington:

This is not tail-recursive. For Lisp languages, you can tell what order things are called in by starting at the innermost parens and working outward. First, the minus function is called. Then the recursive “factorial” function is called. Then the multiply function is called. Then the system leaves the function.

Here is a tail-recursive version:

First off, you need another argument for your function. Think of having one as an “input” (which in this case gets decremented to 0 with each call) and an “output” (or accumulator), which holds the increasing total. If we look at the line in “acc-factorial” where it calls itself, it calls the minus and multiply functions, and THEN makes a recursive call. And that call would cause the system to exit the function (or that instance of the function). In the first function, it makes the recursive call, then it makes the call to multiply, and THEN it exits the function.

I hope I understood that. I am not going to name-and-shame, but while writing this I found a gist on github that the author claimed was a tail-recursive factorial in Scheme, but it looks more like the first example I posted from UWash and not the second. So either our mystery gist-er misunderstands tail-recursion, or I do.

You’re welcome.

2019-03-14 Update: Simply Scheme, Simply Clojure, Simply Racket

I have been taking a break from Simply Scheme. I got stumped on one of the exercises. I started doing the exercises in Clojure for a couple of reasons. One is that is the most commercially viable Lisp out there right now. Another reason is that I want to run automated tests. I would like to be able to quickly run a function multiple times with different inputs. I was typing and re-typing the same calls over and over. Or I could just use tests.

I do not know how to do tests in Scheme. I was using Chicken Scheme for Simply Scheme. There are a few “eggs” for testing, but the instructions were not that great. Also some of them were not working on the version of Chicken that I was using for Simply Scheme. I use Chicken on Ubuntu and Cygwin, and not directly; they are a bit behind the official version. I did find out recently there is an SFRI for testing. It is implemented by Kawa, so perhaps I could have used Kawa. I do not plan on building any apps with Scheme, or using it long-term. It is just a vehicle for enlightenment. I do not know what the most common test libraries are, and I do not want to spend time on something that I might not be able to use later. Clojure has testing out of the box.

I also started looking into using Racket. I have thought about it before, since there are a lot of language modules for Racket. There is one for Simply Scheme. I also found out about an Emacs mode for Racket. I am just running some tests from some .rkt files, but from what I understand, this is intended to be a replacement for Dr Racket. I do not know how to make an app with Racket, but right now I do not need much. I think I might be better off going with Racket, even if I am using a Scheme language module. While Racket is pretty rare, it is used more than Scheme.

So I have started a project using Racket and the Simply Scheme library to do the Simply Scheme exercises. Maybe someday I will do SICP in Racket, and become a Little, Reasoned or Seasoned Racketeer.

You’re welcome.

Image from ImgFlip, assumed allowed under Fair Use.

2019-02-27 Update: Web Apps and Multimethods

I have started looking at the tutorial for Luminus, the Clojure web framework. I am thinking about making a web app that sends data to Clara, the Clojure rules engine.

I have started looking at the tutorial for Luminus, the Clojure web framework. I am thinking about making a web app that sends data to Clara, the Clojure rules engine.

I have also started a github sub-project simply-clojure, which is a port of Simply Scheme to Clojure. I used multimethods, based on the use seen in Clojure For the Brave and True.

One of the functions that comes with Simply Scheme is appearances, which “returns the number of times its first argument appears as a member of its second argument”. It works with “words” and “sentences”. A “word” in SS is any type of data with a single member; it could be a number or a string with one word. A “sentence” is basically a list.

It can handle various datatypes. For Clojure, I decided to use multimethods. I think they can only take one argument, so I cheated and used a map.

Here are the tests:

Code highlighted at http://hilite.me/.

You’re welcome.

2019-01-09 Update

I recently attended the first meeting of the Austin Kotlin Meetup. I might keep going in the future. I am kind of on the fence about Kotlin. It is nicer than Java, at least Java as most companies use it today.

I get the impression there are a lot of teams using old versions of Java, and old versions of Spring. They might solve a lot of their pain by upgrading and not really have any need to go to a new language. I wish I knew a way to get teams to upgrade. When Java came out, it was the sleek language (vis a vis C++); now it is the old chestnut. Rails has gone through the same cycle. If companies have fallen behind on Java, and fallen behind on Rails, will going to Kotlin really make things better? Maybe Kotlin teams will get bogged down by legacy Kotlin in ten years. Do we need more languages? Why can’t we just be more intelligent about the languages we use? (And since languages seem to becoming more like Lisp, perhaps we should just go to some dialect of Lisp.)

At one point in the meeting, someone asked what makes a language a “functional language”. I thought a language is considered “functional” when a function can be sent as an argument to another function, or a function can return a new function. One person mentioned immutability. Another mentioned tail-call optimization.

I have been working a bit more on Simply Scheme. Chapters 9 and 10 dealt with lambdas and higher-order functions. I think I am understanding functional programming, but I do not feel like I am getting the enlightenment that people keep talking about. Perhaps this is because I have been exposed to these concepts for a while now.

One reason I doubt I am becoming enlightened is sometimes my answers are larger than other people’s. I can make something that works, but it is not always elegant and minimal.

Another reason I doubt my potential enlightenment is that I am not sure it is making me a better programmer at my job. We are running JDK 6, we are using XML to configure Spring, and there is logic in the views. I am not sure how understanding higher-order functions will help me improve things. There are a lot of things I cannot change. I think it should be re-written from the ground up. Perhaps I will get more insights when I finish Simply Scheme.

Frankly, I think a lot of people where I work do not understand a lot of this stuff and have not been exposed to a lot of these concepts. (Most people I talk to have never even heard of Lisp, or Smalltalk, or Erlang or Scala, or Ruby.) I was not exposed to it for a long time, and I did not understand it at first either. When you are surrounded by people who think that the Gang Of Four patterns are the height of technological sophistication, it is easy to think that is the way things should be done. Part of the issue is that the functional programming community does not explain a lot of this stuff very well. I do not think that state is bad, or that changing state is bad. And side effects are hard to avoid if you want a program to be useful. I/O is a side effect, and it is important. I think the real issue is that state changes and side effects can cause problems if they happen when you do not intend for them to happen, and it is better to explicitly control them.

I am considering taking another break from Simply Scheme and making some web apps in Clojure. Perhaps I should work on getting better in the technologies I want to work in, and go for enlightenment later.

The viability of web apps showed up on Hacker News a few times the past few weeks: “Start with a Website, Not a Mobile App” and “Ask HN: Is web development still a viable career choice?” I will look at these a bit and comment more later.

Going back to chapters 9 and 10 of Simply Scheme.: They showed a neat trick to use lambda to wrap a higher-order function that only takes one argument (like every, keep and accumulate, which are their versions of Clojure’s map, filter and reduce) and put it in an anonymous function so it can take two or more arguments. Pretty slick.

Note: To search the c2.com wiki, try the search page.