Technical questions

1. Is quasiquotation just a hack to get macros to work in Lispy languages, or does it stand on some firm logical footing?
2. Is there a graceful and elegant way randomly to select n items from a list of unknown length without reading the whole list into, and retaining it in, memory?  I know there's a way to select just one item this way, but don't know if there's a generalized method.

Comments

on 2006-01-30 0:19:27.0, tom commented:

I don't know anything about LISP, so I can't answer the first question. I'm not sure I understand the second -- when you say list, what do you mean? A file? If so, the answer is generally yes, but not without the risk of possibly having to open it more than once.

[permalink]

and, further, on 2006-01-30 13:09:13.0, ben wolfson commented:

I mean like this: if you have a source of anything, you can select one item from it in something like the following way, in a C-like language:

object getone(object source) { object cur, tmp; int i = 1; while (!exhausted(source)) { tmp = source.next(); if (i == 1 || random() > float(i-1)/i) { cur = tmp; } i++; } return cur; }

(forgive lack of formatting.) You don't need to hold all the objects from which you're selecting one in memory in order to get one randomly. My question is, if you want to get n randomly, is there a similar way?

[permalink]

and, further, on 2006-01-30 15:07:05.0, son1 commented:

When you say "randomly," do you mean, "uniformly at random?" (So that if the list-of-unknown-length eventually turns out to have length M, the chance of a particular element of that list being in the chosen set is n/M?)

Let me try one more time. Sorry for screwing up your comments.

[permalink]

and, further, on 2006-01-30 15:17:58.0, ben wolfson commented:

I see now that that "i == 1" clause is redundant if you change the > to >=.

And yes, that is what I mean. (I was motivated to think of this for something where currently I just read in a bunch of lines from a file, shuffle it randomly, and then take the first n.)

[permalink]

and, further, on 2006-01-30 15:21:55.0, son1 commented:

Also, isn't quasi-quotation used all over Quine's Mathematical Logic? At least, that's the first place I ever encountered it...

When it comes to quasi-quoting in Lisp and Scheme, I think this is a pretty good motivating paper...

[permalink]

and, further, on 2006-01-30 15:26:23.0, ben wolfson commented:

Yeah, I came across a paper that said that Quine introduced it in 1940. But I was curious because I was reading a paper by…Quine, "Philosophy of Logic", which concludes:

Tarski's paradigm cannot be generalized to read:

'p' is true if and only if p

since quoting the schematic sentence letter 'p' produces a name only of the sixteenth letter of the alphabet, and no generality over sentences.

[permalink]

and, further, on 2006-01-30 15:32:05.0, son1 commented:

Well, ([pulling down Quine from the bookshelf]) my copy of Mathematical Logic says its "Revised" version was published in 1940, so maybe that's the source of that? Anyway, Chapter 1, Section 6, "Quasi-quotation."

Quasi-quotation would have been convenient at earlier points, but was withheld for fear of obscuring fundamentals with excess machinery. Now, however, it may be a useful exercise to recapitulate some sample points from Sections 1-5 in terms of this device. etc.

Dunno about the "choose n items at random" problem, but should be fun to think about on the subway ride home. I might have a book of online algorithms at home with the answer, too, who knows...

Thanks!

[permalink]