mcr@Latour.Sandelman.OCUnix.On.Ca (Michael Richardson) (12/15/90)
While bored between classes I started playing with building some
sort of symbolic differentiation program (I'm a physics student. I
hate differentiating things like spherical coordinates, etc...).
TI-Scheme was around on some PCs in one lab so I started with that.
In my style of lisp, I use a lot of property lists --- my friendly
interaction loops usually say something like:
(do ((cmd (read) (read)))
((eqv? cmd 'q))
((getprop cmd 'shell)))
TI-Scheme has putprop/getprop.
Now that exams have started, I've got around to compiling
MIT Scheme (6.1.2, Microcode 10.2, runtime 13.91, sf 3.13). I
discovered to my amusement that property lists seem to be absent.
Okay, I says, is assq a primitive? Seems to be. No problem.
While grep'ing through the runtime code and microcode for
references to property lists, I noticed a bunch of stuff on hash
functions, etc... Is there, (already existing?) some code to do
property list-like things using hash codes?
I've read R^3S (quite awhile ago), but haven't haven't gotten
TeX up so I can print off the R^4S included in the docs. There is
a hacked up copy of one of them (I don't remember which) with the
TI-Scheme 'manuals' in the CS labs. They actually don't mention
property lists at all (that I remember).
Were property lists dropped in scheme? Why?
[ I'm sorry, I'm new to Scheme --- but I've written some very
nice (I think) Lisp interpreters. My favorite one attached a
'SUBRn' property to a symbol to give it a primitive definition.
The SUBRn symbol had a property called '*NUMBER-OF-ARGUMENTS*' that
told how many arguments this primitive received. One could define
new kinds of primitive invocation methods via similar methods. I
was working on a property list cache at the time... If this
sounds like Anatomy of Lisp, it is. ]
On a somewhat related note --- I believe that there is a 6.2
MIT Scheme no? Has anyone implemented the rational types? Does
6.2 have them? I read a comment here a couple of days ago stating
that including rationals in the definition was a mistake. I'm
curious as to why? Can anyone expand on this comment?
Please note Reply-To: if email'ing.
--
:!mcr!: | The postmaster never | So much mail,
Michael Richardson | resolves twice. | so few cycles.
mcr@julie.UUCP/michael@fts1.UUCP/mcr@doe.carleton.ca -- Domain address
- Pay attention only to _MY_ opinions. - registration in progress.markf@zurich.ai.mit.edu (Mark Friedman) (12/19/90)
The current version of MIT Scheme (version 7.0) has a generalization
of the Lisp property list mechanism called the Association Table. The
new version of MIT Scheme (which will be available soon) includes an
implementation of rational numbers. Thr biggest mistake that I can
see with including rationals is illustrated by the following sometimes
frustrating transcript :-)
(/ 27 157)
;Value: 27/157
That is, if you want to use Scheme as a calculator you must do:
(exact->inexact (/ 27 157))
;Value: .17197452229299362
The following is some documentation on the MIT Scheme association
mechanism.
-Mark
---------------------------------------------------------------------
The Association Table
=====================
MIT Scheme provides a generalization of the property list
mechanism found in most other implementations of Lisp. MIT Scheme
uses weak pairs (*note Weak Pairs::.) to implement rapid access to a
global two-dimensional "association table". This table is indexed by
two keys, called X-KEY and Y-KEY in the following procedure
descriptions. These keys and the value associated with them can be
arbitrary objects. Scheme uses `eq?' to compare keys to the key
values stored in the table.
You can think of the association table as a matrix; you can access
a single value using both keys, a column using X-KEY only, and a row
using Y-KEY only.
Note: because these procedures accept arbitrary objects as keys,
they are less efficient than their property-list counterparts in
other Lisps. This is because they must perform an extra association
to find the stored value.
* procedure+: 2d-put! X-KEY Y-KEY VALUE
Associates VALUE with X-KEY and Y-KEY, and returns an
unspecified value. To retrieve this association, use `2d-get',
`2d-get-alist-x', and `2d-get-alist-y'. Notice that X-KEY and
Y-KEY can be arbitrary objects (unlike other Lisp systems where
they must be symbols).
* procedure+: 2d-get X-KEY Y-KEY
Returns the entry associated with X-KEY and Y-KEY by `2d-put!';
returns `#f' if no such association exists.
* procedure+: 2d-get-alist-x X-KEY
Returns an association list (a list of pairs of key-value
associations) of all entries made by `2d-put!' with X-KEY as its
first argument. Returns the empty list if no entries for X-KEY
exist.
For example,
(2d-put! 'foo 'bar 5)
(2d-put! 'foo 'baz 6)
(2d-get-alist-x 'foo) => ((baz . 6) (bar . 5))
* procedure+: 2d-get-alist-y Y-KEY
Returns an association list (a list of pairs of key-value
associations) of all entries made by `2d-put!' with Y-KEY as its
second argument. Returns the empty list if there are no entries
for Y-KEY.
For example,
(2d-put! 'bar 'foo 5)
(2d-put! 'baz 'foo 6)
(2d-get-alist-y 'foo) => ((baz . 6) (bar . 5))
* procedure+: 2d-remove! X-KEY Y-KEY
Removes an association made by `2d-put!'. Returns `#t' if an
entry was found and removed, or `#f' if there was no such entry.
1D Tables
=========
"1D tables" ("one dimensional" tables) are a generalization of
association lists. In a 1D table, unlike an association list, the
keys of the table are held weakly. 1D tables are implemented by the
"weak pair" datatype (*note Weak Pairs::.).
1D tables can often be used as a higher performance alternative to
the two dimensional association table (*note The Association
Table::.). If one of the keys being associated is a compound object
such as a vector, the 1D table can be stored in one of the vector's
slots. Under these circumstances, accessing items in the 1D table
will be comparable in performance to using a property list in a
conventional Lisp.
* procedure+: make-1d-table
Creates and returns a new, empty, 1D table.
* procedure+: 1d-table? OBJECT
Returns `#t' if OBJECT is a 1D table, otherwise returns `#f'.
* procedure+: 1d-table/put! 1D-TABLE KEY VALUE
Creates an association between KEY and VALUE in 1D-TABLE. The
value is unspecified.
* procedure+: 1d-table/get 1D-TABLE KEY DEFAULT
If 1D-TABLE contains an association for KEY, returns its value.
Otherwise returns DEFAULT.
* procedure+: 1d-table/lookup 1D-TABLE KEY IF-FOUND IF-NOT-FOUND
An alternative method for looking up values in a 1D table.
IF-FOUND must be a procedure of one argument, and IF-NOT-FOUND
must be a procedure of no arguments. If 1D-TABLE contains an
association for KEY, IF-FOUND is invoked on the value of the
association. Otherwise, IF-NOT-FOUND is invoked with no
arguments.
* procedure+: 1d-table/remove! 1D-TABLE KEY
Removes any association for KEY in 1D-TABLE and returns an
unspecified value.
Hashing
=======
The MIT Scheme object hash facility provides a mechanism for
generating a unique hash number for an arbitrary object. This hash
number, unlike an object's address, is unchanged by garbage collection.
* procedure+: object-hash OBJECT
* procedure+: object-unhash K
`object-hash' associates a non-negative exact integer with
OBJECT and returns that integer. If `object-hash' was
previously called with OBJECT as its argument, the integer
returned is the same as was returned by the previous call.
`object-hash' guarantees that distinct objects (in the sense of
`eq?') are associated with distinct integers.
`object-unhash' takes a non-negative exact integer K and returns
the object associated with that integer if there is one,
returning `#f' otherwise. In other words, if `object-hash'
previously returned K for some object, that object is the value
of the call to `object-unhash'.
An object that is passed to `object-hash' as an argument is not
protected from being garbage collected. If all other references
to that object are eliminated, the object will be garbage
collected; subsequently calling `object-unhash' with the hash
number of the (garbage-collected) object will return `#f'.
(define x (cons 0 0)) => unspecified
(object-hash x) => 77
(eqv? (object-hash x) (object-hash x)) => #t
(define x 0) => unspecified
(gc-flip) ;force a garbage collection
(object-unhash 77) => #f
It is useful to know that objects whose external representation
begins with the character sequence `#[' almost always print
their hash number as a part of the representation. This can be
an invaluable debugging aid. The format of this representation
is:
#[TYPE HASH OTHER-STUFF]
Here TYPE is the name of the object's datatype, for example,
`procedure' or `uninterned-symbol'; HASH is the hash number for
that object, and OTHER-STUFF differs depending on the object's
datatype (often it is empty).
(define (f x) (+ x 2))
f => #[compound-procedure 84 f]
(object-hash f) => 84
(object-unhash 84) => #[compound-procedure 84 f]
Note: `hash' is a synonym for `object-hash'; and `unhash' is a
synonym for `object-unhash'. These synonyms are obsolete and
should not be used.
Weak Pairs
==========
"Weak pairs" are a mechanism for building data structures that
point at objects without protecting them from garbage collection.
The car of a weak pair holds its pointer weakly, while the cdr holds
its pointer in the normal way. If the object in the car of a weak
pair is not held normally anywhere else, it will be garbage collected.
Note: weak pairs are *not* pairs; that is, they do not satisfy the
predicate `pair?'.
* procedure+: weak-pair? OBJECT
Returns `#t' if OBJECT is a weak pair; otherwise returns `#f'.
* procedure+: weak-cons CAR CDR
Allocates and returns a new weak pair, with components CAR and
CDR. The component CAR is held weakly.
* procedure+: weak-pair/car? WEAK-PAIR
This predicate returns `#f' if the car of WEAK-PAIR has been
garbage collected. In other words, this operation is true if
WEAK-PAIR has a valid car component.
Normally, this procedure is used to determine if `weak-car'
would return a valid value. An obvious way of using this
procedure would be:
(if (weak-pair/car? x)
(weak-car x)
...)
However, since a garbage collection could occur between the call
to `weak-pair/car?' and `weak-car', this would not always work
correctly. Instead, the following should be used, which always
works:
(or (weak-car x)
(and (not (weak-pair/car? x))
...))
The reason that the latter expression works is that `weak-car'
returns `#f' in just two instances: when the car component is
`#f', and when the car component has been garbage collected. In
the former case, if a garbage collection happens between the two
calls, it won't matter, because `#f' will never be garbage
collected. And in the latter case, it also won't matter (the
object will not become un-collected!).
* procedure+: weak-car WEAK-PAIR
Returns the car component of WEAK-PAIR. Use the predicate
`weak-pair/car?' to determine if there is such a component. If
the car component has been garbage collected, this operation
returns `#f' (but it can also return `#f' if that is the value
that was stored in the car).
See `weak-pair/car?' for an example showing how to use this
operation correctly.
* procedure+: weak-set-car! WEAK-PAIR CAR
Sets the car component of WEAK-PAIR to CAR.
* procedure+: weak-cdr WEAK-PAIR
* procedure+: weak-set-cdr! WEAK-PAIR CDR
These operations manipulate the cdr component of WEAK-PAIR in
the usual way. Since the cdr is held in the normal way, they
work identically to `cdr' and `set-cdr!', respectively.
--
Mark Friedman
MIT Artificial Intelligence Lab
545 Technology Sq.
Cambridge, Ma. 02139
markf@zurich.ai.mit.educph@ALTDORF.AI.MIT.EDU (Chris Hanson) (12/28/90)
Date: 15 Dec 90 07:54:21 GMT
From: Michael Richardson <snorkelwacker.mit.edu!apple!julius.cs.uiuc.edu!zaphod.mps.ohio-state.edu!van-bc!ubc-cs!news-server.csri.toronto.edu!utgpu!cunews!micor!latour!mcr@bloom-beacon.mit.edu>
Now that exams have started, I've got around to compiling
MIT Scheme (6.1.2, Microcode 10.2, runtime 13.91, sf 3.13). I
discovered to my amusement that property lists seem to be absent.
Okay, I says, is assq a primitive? Seems to be. No problem.
Property lists are available in MIT Scheme, with slightly different
names:
putprop 2d-put!
getprop 2d-get
remprop 2d-remove!
The names were changed because these property lists differ in some
important respects from those of Lisp:
* The keys can both be any object -- it not necessary that one be a
symbol.
* The keys are not protected from garbage collection -- if one of the
keys is reclaimed, the property is automatically removed from the
table.
* The performance is somewhat worse -- two linear-time lookups instead
of one.
While grep'ing through the runtime code and microcode for
references to property lists, I noticed a bunch of stuff on hash
functions, etc... Is there, (already existing?) some code to do
property list-like things using hash codes?
The hash-code stuff is used for hash tables, not property lists.
I've read R^3S (quite awhile ago), but haven't haven't gotten
TeX up so I can print off the R^4S included in the docs. There is
a hacked up copy of one of them (I don't remember which) with the
TI-Scheme 'manuals' in the CS labs. They actually don't mention
property lists at all (that I remember).
Were property lists dropped in scheme? Why?
Property lists were never part of the Scheme reports.
On a somewhat related note --- I believe that there is a 6.2
MIT Scheme no? Has anyone implemented the rational types? Does
6.2 have them?
6.2 doesn't have rationals. Release 7.1, entering beta test in a few
days, does.
:!mcr!: | The postmaster never | So much mail,
Michael Richardson | resolves twice. | so few cycles.
mcr@julie.UUCP/michael@fts1.UUCP/mcr@doe.carleton.ca -- Domain address
- Pay attention only to _MY_ opinions. - registration in progress.