I spent a lot of time over the weekend thinking about persistent data. I was trying to come up with a set of base abstractions over which to build a persistent store. I haven't found the best set, but I found part of a good set that can be refined to be better.

You need two things in order to effectively use persistent data. The first is a ‘durable store’ which we will use to remember the information, the second is a management system that gives us control over what is stored and retrieved and acts as an intermediary between transient programs and the persistent data they need. The basic interface between the durable store and the management system is this:

(write-bytes! store-name byte-vector) => address

(read-bytes store-name address) => byte-vector

write-bytes! is the primitive means of saving information. The store-name argument identifies which particular durable store save the bytes in, and the byte-vector argument is a vector of small numbers for the store to save. When invoked, the store should save the numbers somehow (more on this later), and return an address, which is perhaps simply an integer.

read-bytes is the primitive means of recovering information. Again, the store-name argument identifies which particular durable store to read the bytes from, and the address is a value that was previously returned by a call to write-bytes! on that same store. It should return a byte vector whose contents are equal to the one that was stored.

We'll make a very simple requirement for the behavior of this API. write-bytes! may either succeed or fail. If it fails, we require it to not return a success indication. For this API, we assume that if write-bytes! returns an address, that it succeeded. Furthermore, read-bytes may also fail or succeed, but if it succeeds it must return the same bytes that were given in the call to write-bytes! that produced that address.

We'll need to extend this API a bit, but it is an ok start.

This API gives us a mechanism for durability, but it isn't a very useful one. What if you want to save something other than byte vectors? How do you remember the address that you got back? This will be the responsibility of the management layer.

---

Exercise 1: Implement the above API using the file system.

In that last post Student Z made the ridiculous comment that he didn't want to analyze code, he just wanted to run it. I didn't make this up. In an argument I was having a few years back the other person wrote

This is the overriding concern of the FP advocate. They want to reason about their code. This is a strange proposition to the vast majority of industry. They don't want to reason about it, they want it to be easy to implement and run fast!

... I've always come at these problems from the industrial standpoint, not the academic theoretical I-want-to-reason-about-it standpoint.

Well, you do find trolls on the internet, but I was surprised to see a professor say:

I would cheerfully give up [the ability to off-line analyze a file] for the sake of [a top-level REPL and a model where loading a file is just like “typing it in”].

Analysis of code doesn't just mean ‘automated theorem proving’. It also means being able to casually look over the code and get a clue as to what it is doing. Just looking at what identifiers are defined in a program and which are free can give a lot of the context. But as you can see, you cannot just slavishly evaluate each form in turn in order to understand the entire program.

As to Student B's question, “How you can tell what you need to evaluate and what you don't?” I think I was too vague in presenting the question or too caught up in anthropomorphization. We need to step back from what the interpreter does with the code (evaluation) and abstract from it (abstract evaluation). Student B, of course, wouldn't be expected to understand this, but the professor should, and he ought to be able to frame the issue in a way that Student B can at least follow.

For the specific example of this quiz, you can simply say ‘ignore any top-level form that isn't a definition’. This is usually a pretty good rule of thumb, and I'll start there, but we need to be a lot more precise. (Since the questions, if poorly stated, at least have agreed upon answers, we ought to be able to precisely specify why our answers are correct.)

Back in the classroom Student Z complains “You're talking about analyzing code. I don't want to analyze code. That's ivory tower crap. In the real world, they write code and run it. Why should I bother learning this stuff?”

Is this a reasonable viewpoint?

Student B has a more technical question. “So I think I'm getting this idea that you want to be able to understand the code without simply evaluating it, but what I don't get is how you can tell what you need to evaluate and what you don't. If you don't evaluate anything, the how could you know that (define foo (lambda (x) ...)) is going to define a name as a procedure? You sort of have to do some evaluation. But then how do you know that you don't have to evaluate the ‘sanity check’ code?
“I guess what I'm asking is: are there some rules I should know, or is this just seat-of-your-pants stuff?”

---

In other news, I'm thinking about how to do a simple persistent store in Scheme/Lisp. I do a fair amount of database type stuff at work and I'm pretty sure there a lot of improvements on what I'm seeing. It seems to me that the second year course in computer science should deal with persistence and databases, and that a “Structure and Interpretation of Persistent Data” or a “How to Design Databases” would be a great book.

So in order to play with these ideas, I'm putting some work into MIT Scheme. The first thing I wanted was ‘:keyword’ objects — self-evaluating symbolic constants. I prefer the leading colon style, but I know others prefer the trailing. SRFI-88 specifies trailing, but many versions of Scheme have leading (or both). I decided to have a way to switch between the two styles.

CPH suggested that switching should be on a per-file basis, like case-sensitivity. Neither one of us like the #!fold-case #!no-fold-case flags that R6RS suggests. (Read Clinger's rant). After a bit of casting around for ideas, the one that made the most sense was to put the case folding and keyword style in the ‘file attributes line’ at the top of the file.

;;; -*- Mode: Scheme; keyword-style: prefix -*-

That was slightly painful to implement because there is a large variability in the syntax of the file attributes line and I wanted to provide a ‘soft landing’ for strangely written lines.

The upshot is that now I can use keywords (in prefix style!) and correctly interact with code that is written with trailing-colon keywords or with no keywords at all. (Although the latter will find it fairly nasty to invoke to my code: (foo (string->keyword "a") 22).)

Student B goes to the student center to get some tutoring.

“I'm not doing so well in my intro to computer science course. I just took a quiz and didn't finish it. This may sound paranoid, but there's a blog that seems to be talking about the problems I'm having. They were discussing part of the program in the quiz.”

mquander wrote:
Where did student B get the idea that he was supposed to evaluate it?

Blaise Pascal wrote:
He didn't need to evaluate it to answer the quiz questions, and he wasn't asked to evaluate it.

Alexey wrote:
He was expected to ignore the evaluation path of the sanity check form.

“Anyway,”Student B continued, “I don't understand what they are talking about. What else would you do with a program but evaluate it? Isn't that what programs are for? They're telling what not to do, but not what I ought to be doing instead. Can you help me?“

---

How should the tutor approach this? What should he or she say?

Pop quiz fallout

At the end of the two hours, Student B was still furiously scribbling away. He had accumulated a suprising amount of paper around himself. The professor came over to talk to him.
“What seems to be the problem?”
‘I don't have enough time!’
“It isn't that hard a quiz, you know. Every other student has finished. What exactly are you doing?”
‘This part, right here.’
Student B pointed to this line in the quiz:

(= (- (fib 100) (fib 99)) (fib 98))

‘I decided to evaluate this from right to left because you said that order doesn't matter. I'm still working on the (fib 98) subexpression. I think that (fib 99) and (fib 100) are going to take even longer. I can't see how anyone could get past this. I'm getting discouraged. I don't even think a computer could solve this in two hours.’

This is a key question: What, if anything, is Student B doing wrong?

A pop quiz

Partway through the term the professor decides to give the students a pop quiz.

“The quiz is contained in the file quiz.scm which you can find in the usual location. For those of you that prefer hardcopy, I have a printout for you.

“I know that some of you” (and here the professor glared at Student A) “seem to have issues with the way I present code, so you should assume that this code is to be entered into an unmodified R5RS Scheme interpreter.

“You have two hours.

;; Question 1:
;; What does (fib 4) evaluate to?

;; Question 2:
;; What is domain and range of the EVEN? procedure?

;; Question 3:
;; How many top-level forms are in this file?

;; Question 4:
;; Make a list of the free variables in this file.

(define (even? x)
  (or (zero? x)
      (odd? (- x 1))))

(define (odd? x)
  (and (not (zero? x))
       (even? (- x 1))))

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) 
         (fib (- n 2)))))

;; Sanity check
(= (- (fib 100) (fib 99)) (fib 98))

;; Question 5:
;; Are either of the following two forms an infinite loop?
;; Make an informal argument to support your answer.

(define (loop1 n)
  (if (positive? n)
      (loop1 (- n 1))
      (loop1 n)))

(define (loop2 n)
  (if (negative? n)
      (loop2 (+ n 1))
      n))

Meta-questions for readers of this blog:

1. Is this a reasonable quiz? If it is too difficult for first-year students, is there a year at which it would be appropriate or even too simple?
2. Is two hours enough time to answer the questions?
3. Are there any loopholes that will allow Student A to object?

Followup

Pascal Costanza wrote:

Student A's statement is self-contradictory. You can only meaningfully talk about making something incorrect when you have a correct meaning in mind in the first place. So for Student A, the program has a meaning, even if he/she denies that.

Student A might argue: “The professor is the one that is assuming there is a correct meaning. I'm simply pointing out that whatever meaning he might have in mind could be wrong.”

Student C's description of the program is circular. He/she states that FACTORIAL implements factorial, which doesn't say much at all - it's both times the same word, both times the same string of characters (only once in upper case and once in lower case).

Student C replies: “Oh, I meant that the program named FACTORIAL implements the mathematical function ‘factorial’.” (This is a beginner's course, so we shouldn't make him work too hard.)

Alexey wrote:

I would say to student A: That answer is useless. Of course someone could shadow * or IF; but what did the author of the program mean when they wrote it?

Student A replies: “How should I know? I can't read minds!”

What do we say to Student A?

I would say to student B: OK, that's what the program does, for a few trials with a few arguments, but what it does is beside the point. The question was: what does the program mean?

Student B asks: So what is the difference between what it “means” and what it “does”? Doesn't “(+ 2 3)” mean 5? Doesn't “(factorial 4)” mean 24?