Home > Lisp, Scheme > List abbreviations

List abbreviations

Since List is a basic and very usefull data structure of Lisp, so there are several ways to create lists. I whould like to discuss some subtle details of the subject.

Book “How to design programs” at Section 13 Intermezzo 2 says that
‘(1 2 3)
abbreviates to
(list 1 2 3)
but later it says that
‘(a b c)
abbreviates to
(list ‘a ‘b ‘c)
See the difference ? symbols are quoted, and numbers are not! Why that difference ?

It turns out that a single approach could be taken: to quote everything. It works, because quoting a number doesn’t produce a symbol, but a number itself, so (+ ‘1 ‘2) evaluates to 3.

More interesting issue is that ‘(a b c) is not perfectly the same as (list ‘a ‘b ‘c). In my interpreter, I’ve made it completelly different. For parser, first expression is a sequence of quote and a list of three elements, and second is a list of four elements.

Evaluation is also different. For first expression, quote allows evaluator to treat the following item as data, so a list of three symbols created by parser is simply re-used. Second expression is a procedure appliance, so first arguments are evaluated, then they are passed to list procedure, which returns a list of three elements. Then evaluator uses first expression in form returned by parser, it contains raw parser data: symbols and lists, and each time it evaluates symbol it first checks if symbol should be converted into number. This is a good test:
(symbol? (car ‘(1)))
evaluates to #f

My implementation handles this expression in following way: parser creates list for expression text, which consists of symbols and other lists. Then evaluator starts evaluating expressions. quote returns list generated by parser, which contains symbol “1”, then car extracts that symbol, and then procedure symbol? checks if it is a number.

Second approach, which is probably better, whould be to let parser recognize numbers. It should be more performant, then to convert symbol to number every time it is accessed. Third approach is to perform conversion once in evaluator, then replace symbol with number in that list. However, this last approach doesn’t eliminate checking if symbol is a number every time real symbol is accessed

So, I see three implementation strategies, which provide similar results:

  • Parser builds representation for expression from lists, symbols and numbers. Quote simply returns that list
  • Parser builds representation for expression from lists and symbols. Quote simply returns that list. Symbols are converted into numbers then they are accessed.
  • Parser builds representation for expression from lists and symbols. Quote treats lists in special way (recursively)
Advertisements
Categories: Lisp, Scheme
  1. August 28, 2017 at 11:16 pm

    Design Ghandi, Io ti ringrazio per la vostra tanta pazienza con me! Martin e mi aveva un tempo molto grande con te e Martin va in giro come un vero e proprio sub! Tu sei un istruttore molto buono e ci sarà di nuovo con voi e poi proverò di nuovo con voi!

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: