2021-04-11 Update

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:

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:

Here is a tail-recursive version:

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.

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.

Image from World Digital Library, assumed allowed under Fair Use. Image from the Ashburnham Pentateuch, or Tours Pentateuch, a Latin manuscript of the first five books of the Old Testament from the 6th century or 7th century. Its place of origin is unknown.

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.

Image from Corpus Agrimensorum Romanorum, a 6th century manuscript on land surveying housed at the Herzog August Library in  Wolfenbüttel. According to Wikipedia, “It is one of the few surviving non-literary and non-religious illuminated manuscripts from late antiquity.” This image is assumed to be allowed under Fair Use.

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. The definitions in Simply Scheme and on the Aalborg page are not tail-recursive. I made versions that are tail-recursive.

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.