Reasoned Schemer 2nd Edition

[Rick Moynihan]

I've had a treasured copy of the reasoned schemer for many years, and recently noticed that there's a second edition.

Can anyone tell me what's new?  And whether it's worth buying if you have a first edition copy?

Is the main difference that it's based on an implementation of microkanren rather than minikanren? 

Does microkanren have different semantics to minikanren?  I'd initially thought it was mainly just a smaller and simpler implementation, however I've also seen comments indicating it changes the search strategy.  Any pointers to resources discussing the differences between the two would also be greatly appreciated.

R.

[William Byrd]

Hi Rick!

> I've had a treasured copy of the reasoned schemer for many years, and recently noticed that there's a second edition.

Indeed there is, finally! ;)

> Can anyone tell me what's new? And whether it's worth buying if you have a first edition copy?
>
> Is the main difference that it's based on an implementation of microkanren rather than minikanren?

I'd say there are four big differences in the second edition.

First, we simplified the miniKanren language in several critical ways.
The second edition only has one type of == (which always uses the
occur check), an improved conde that replaces the conde and condi from
the first edition, and an improved fresh that removes the need for
alli. I think this this is a huge improvement pedagogically, since
you needn't chose between the operator variants every time you write a
relation. And, from a design standpoint, I think it is far better to
have 3 core operators rather than 6. (I don't count condu or conda as
core operators--they are still in the book, though).

Another simplification remove much the 'Schemely-ness' of the logic
language. Instead of (define appendo (lambda (l s out) ...)), we use
a new 'defrel' form that combines the jobs of 'define' and 'lambda'.
The purpose is to make the language more stand-alone--for example, if
you wanted to write an interpreter or compiler for the language of the
book, you could now do it without having to implement 'define',
'lambda', or other Schemely constructs. I was hesitant about this
change for a while, but have come to appreciate it. 'defrel' is just
a Scheme macro, of course, so you aren't really losing any of the
power, but it does make the semantics a bit more clear, and avoids
some classic errors in using the language (such as forgetting to add a
'(fresh () ...)' inside any lambda that includes multiple goal
expressions).

Second, we simplified the implementation, effectively splitting it
into a microKanren part, and a miniKanren part. The microKanren part
is explained in detail in Chapter 10, while the miniKanren part is
implemented using macros in Appendix A, after a brief explanation of
Scheme macros. We found that the Scheme macros in the first edition
confused most readers, and also made it harder to port miniKanren from
Scheme to another host language. By moving all the macros to an
appendix, and adding a brief explanation of macros, we hope to avoid
this confusion.

Third, we tried to improve the explanation of concepts, based on the
feedback we've received over the past 13 years. We completely rewrote
Chapter 1 to allow it to build up the ideas in a (hopefully) more
logical fashion. We also added Translation rules, to make explicit
how to translate Scheme functions into miniKanren relations. I think
we usually succeeded in making the explanations more clear, but a few
of the older explanations may appeal to some readers.

We also simplified the notation-- we replaced the bold parens and
italic variables with explicit quasiquotes and unquotes, for example,
and tried to make it more clear how to type in code from the book.

Fourth, the book contains a new Preface, Forward, and Afterward, to
better give context to the work.


Whether it is worth reading the new edition probably depends on how
well you understand the first edition. If you have already
implemented microKanren, have used modern versions of miniKanren or
core.logic, have followed recent work on miniKanren, watched my
tutorials, etc., there probably won't be many surprises for you.

If you struggled with the implementation or some of the explanations
in the first edition, or are not completely comfortable with the
miniKanren language, I think the new edition should help clarify those
concepts.

In short, we rewrote and simplified much of the book, but the core
ideas are the same. As Dan likes to say, this is the edition we wish
we had written 13 years ago, but we didn't know enough then to write
it.

I should also point out that the book does *not* include constraints
other than unification, interpreters, program synthesis, or other more
advanced miniKanren topics. We found it too difficult to include all
those ideas in a single book and keep it 'little'. (Believer me, we
tried! :)) Hopefully you will see more on those topics in the
future...

I should also point out that the code for the new implementation is
available online:

https://github.com/TheReasonedSchemer2ndEd/CodeFromTheReasonedSchemer2ndEd

This implementation is similar in spirit to microKanren:

http://webyrd.net/scheme-2013/papers/HemannMuKanren2013.pdf

https://github.com/jasonhemann/microKanren

> Does microkanren have different semantics to minikanren? I'd initially thought it was mainly just a smaller and simpler implementation, however I've also seen comments indicating it changes the search strategy. Any pointers to resources discussing the differences between the two would also be greatly appreciated.

The microKanren paper above discusses the search strategy--it is
similar in spirit to the old search, but can produce answers in a
different order. The exact search strategy used by miniKanren isn't
set in stone--we always use an interleaved, complete, biased search,
but the exact details differ among implementations. It is true that
the order of answers may change depending on these details, but
miniKanren's semantics make no guarantees about the order in which
answers are returned.


Hope this helps!

--Will


> R.
>
> --
> You received this message because you are subscribed to the Google Groups "minikanren" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to minikanren+...@googlegroups.com.
> To post to this group, send email to minik...@googlegroups.com.
> Visit this group at https://groups.google.com/group/minikanren.
> For more options, visit https://groups.google.com/d/optout.

[Rick Moynihan]

Hi Will,

Thanks for taking the time to describe the changes between editions.  I'll read through this in detail later.

Dan also contacted me off list and convinced me to buy it, as I said to him, I could probably also use more placemats to catch the baba ganoush stains!  I honestly don't know why I hesitated.

Many thanks, your work, and that of the minikanren community has been a joy to follow.

R.