Hi,
I posted this to comp.ai.nat-lang, but later realized some
people here might also be interested, so I'll repost:
I finally got around to posting my results of getting SHRDLU to
run at this address:
http://www.ont.com/~keldon/shrdlu.html
I don't want to repeat everything I said there, but there were
two distinct efforts: one to port the SHRDLU code to Common LISP, and a
second to write from scratch a MacLISP interpreter to run the original
unmodified code.
The Common LISP attempt was fairly successful. It correctly
handles the first six sentences of the sample dialogue but then fails
to parse the seventh (Is at least one of them narrower than the one
which I told you to pick up?). There are also still problems in the
history log of events. It can't handle questions as to why or when it
performed certain actions. But it is still fun to play with.
Unfortunately there is no graphical display. The students at UMR were
supposed to work on one in the semester after I graduated, but I never
saw their results.
The MacLISP interpreter was not quite as successful. It fails
to handle any event that requires it to actually move the arm and pick
up blocks, but it can handle questions. It's included mainly for
completeness sake.
Anyway, I hope that either of these will prove useful to
someone. Maybe a second pair of eyes will find the bugs that prevent
SHRDLU from working completely, but for now I'm tired of messing with
it.
Keldon
Keldon Jones wrote:
> I finally got around to posting my results of getting SHRDLU to
> run at this address:
>
> http://www.ont.com/~keldon/shrdlu.html
Extremely cool!
> I don't want to repeat everything I said there, but there were
> two distinct efforts: one to port the SHRDLU code to Common LISP, and a
> second to write from scratch a MacLISP interpreter to run the original
> unmodified code.
> The Common LISP attempt was fairly successful. It correctly
> handles the first six sentences of the sample dialogue but then fails
> to parse the seventh (Is at least one of them narrower than the one
> which I told you to pick up?). There are also still problems in the
> history log of events. It can't handle questions as to why or when it
> performed certain actions. But it is still fun to play with.
> Unfortunately there is no graphical display. The students at UMR were
> supposed to work on one in the semester after I graduated, but I never
> saw their results.
My experiences so far (with CMU CL, version 18d, on FreeBSD):
- Defining MEMQ makes CMU CL blow up (looks like an
infinite recursion). CMU CL already defines MEMQ,
and presumably it's used inside the interpreter or
something. The same is true for ASSQ.
Putting #-cmu in front of the definitions in "fixes"
deals with that.
- The colon on line 269 of "morpho" makes CMU CL unhappy;
presumably it's trying to interpret that as a package
separator. Escaping it seems to solve that problem.
- The definition beginning "(DEFS \#DIRECTION" produces
a complaint about invalid args in DEFUN-FEXPR, because
that doesn't know how to cope with a FEXPR having more
than one argument. (*Is* there such a thing?) Removing
the second argument fixes this.
- After fixing all these things, SHRDLU gets as far as
giving me a prompt, but everything I tell it produces
one of four responses:
- I CAN'T .
- I DON'T UNDERSTAND.
- I'M NOT SURE WHAT YOU MEAN BY " " IN THE PHRASE " ".
DO YOU MEAN:
1 ?
- a mysterious error complaining about TC-MORE not
being a list in the call
(APPLY THTRUE TC-MODE)
which the debugger claims is happening inside
a call (THTRY1), though I can't see anything there
to explain it. (CMU CL does not cope well with
interpreted code, and I haven't had the courage
to try to get this stuff to run compiled yet.)
The third one appears to be impossible to get out of
without terminating SHRDLU. (Entering "1" produces
the same question again.)
The fourth (the error) doesn't happen in CLISP. Even
odder. It happens in CMU CL after, e.g., "pick up the
big block", but not after "pick up a big block" or
"pick up the red block".
Now, I must confess that I have made a few other changes
in the course of trying to understand the code; it's
amazing how Lisp programming style has changed since those
days. I'm fairly sure nothing I've done has changed anything
that matters, but for completeness here are all the changes.
1. Replace the definition of MAPBLAND in "smutil" with
(defun mapbland (fn args)
"Apply FN to each item in ARGS. Make a list of them all, splicing in
any answers that are lists already. Do splicing with APPEND, not NCONC.
NIL is considered a list here."
(loop for item in (mapcar fn args)
when (consp item) append item
else collect item))
2. Replace the definition of MAPC2 in "smutil" with
(defun mapc2 (fn args)
"Apply FN to successive pairs of values from ARGS. Discard results.
Caller undertakes to provide a list with an even number of elements."
(loop for (a b . rest) on args by #'cddr do
(funcall fn a b)))
I remark in passing that the documentation for MAPC2 claims that
it returns a list of the results of the funcalls (it never did),
and doesn't mention the requirement for an even number of elements.
3. Replace the definition of DEFS in "syscom" with
(defun-fexpr defs (args)
(let ((symbol (first args))
(props (rest args)))
(loop for (kind value . tail) on props by #'cddr do
(case kind
(expr (eval (append (list 'defun symbol (cadr value))
(cddr value))))
(fexpr (eval (append (list 'defun-fexpr symbol (cadr value))
(cddr value))))
(t (setf (get symbol kind) value))))
symbol))
--
Gareth McCaughan ················@pobox.com
.sig under construc
Gareth McCaughan <················@pobox.com> wrote:
> Keldon Jones wrote:
>> I finally got around to posting my results of getting SHRDLU to
>> run at this address:
>>
>> http://www.ont.com/~keldon/shrdlu.html
> My experiences so far (with CMU CL, version 18d, on FreeBSD):
> - Defining MEMQ makes CMU CL blow up (looks like an
> infinite recursion). CMU CL already defines MEMQ,
> and presumably it's used inside the interpreter or
> something. The same is true for ASSQ.
> Putting #-cmu in front of the definitions in "fixes"
> deals with that.
> - The colon on line 269 of "morpho" makes CMU CL unhappy;
> presumably it's trying to interpret that as a package
> separator. Escaping it seems to solve that problem.
> - The definition beginning "(DEFS \#DIRECTION" produces
> a complaint about invalid args in DEFUN-FEXPR, because
> that doesn't know how to cope with a FEXPR having more
> than one argument. (*Is* there such a thing?) Removing
> the second argument fixes this.
All of these should be good fixes. I should mention that I never tried
to run this except on clisp (a version from July 1999).
> Now, I must confess that I have made a few other changes
> in the course of trying to understand the code; it's
> amazing how Lisp programming style has changed since those
> days. I'm fairly sure nothing I've done has changed anything
> that matters, but for completeness here are all the changes.
> 1. Replace the definition of MAPBLAND in "smutil" with
> (defun mapbland (fn args)
> "Apply FN to each item in ARGS. Make a list of them all, splicing in
> any answers that are lists already. Do splicing with APPEND, not NCONC.
> NIL is considered a list here."
> (loop for item in (mapcar fn args)
> when (consp item) append item
> else collect item))
This behaves differently from SHRDLU's MAPBLAND when FN returns NIL.
For example:
(defun foo (x) nil)
(mapbland #'foo '(1 2 3))
returns NIL with SHRDLU's version, but yours returns (NIL NIL NIL).
This may be the cause of your problems.
Keldon
Keldon Jones wrote:
[I said:]
> > Now, I must confess that I have made a few other changes
> > in the course of trying to understand the code; it's
> > amazing how Lisp programming style has changed since those
> > days. I'm fairly sure nothing I've done has changed anything
> > that matters, but for completeness here are all the changes.
>
> > 1. Replace the definition of MAPBLAND in "smutil" with
>
> > (defun mapbland (fn args)
> > "Apply FN to each item in ARGS. Make a list of them all, splicing in
> > any answers that are lists already. Do splicing with APPEND, not NCONC.
> > NIL is considered a list here."
> > (loop for item in (mapcar fn args)
> > when (consp item) append item
> > else collect item))
>
> This behaves differently from SHRDLU's MAPBLAND when FN returns NIL.
> For example:
>
> (defun foo (x) nil)
> (mapbland #'foo '(1 2 3))
>
> returns NIL with SHRDLU's version, but yours returns (NIL NIL NIL).
> This may be the cause of your problems.
Ow! How did I manage to do that? Oh yes, I understand.
I meant LISTP, not CONSP. ... And there's another error
in my translation of MAPBLAND, which is harder to spot:
the original code rather nastily treats an empty list
as if it were a list containing just the item NIL. So
if the function sends NIL to something other than NIL,
the results differ.
With both those errors fixed, SHRDLU works (to the extent
you already described) with CLISP, but not with CMU CL.
I'll investigate further...
--
Gareth McCaughan ················@pobox.com
.sig under construc
Gareth McCaughan <················@pobox.com> wrote:
> Ow! How did I manage to do that? Oh yes, I understand.
> I meant LISTP, not CONSP. ... And there's another error
> in my translation of MAPBLAND, which is harder to spot:
> the original code rather nastily treats an empty list
> as if it were a list containing just the item NIL. So
> if the function sends NIL to something other than NIL,
> the results differ.
> With both those errors fixed, SHRDLU works (to the extent
> you already described) with CLISP, but not with CMU CL.
> I'll investigate further...
There are extensive debugging facilities built-in, if you haven't
already noticed them. First change (USERMODE) to (DEBUGMODE) in the
loader file, and then at SHRDLU's ">>>" prompt you can use the "show"
and "tell" interface (in the file 'show') to do various things. For
example, "tell action on" will dump all the planner theorems that are
attempted. "tell semantics" can disable semantic analysis or show
addition information about the created structures. You can enter "~" at
the READY prompt to get back to the >>> prompt.
Keldon
················@pobox.com (Gareth McCaughan) writes:
> [...] the original code rather nastily treats an empty list
> as if it were a list containing just the item NIL.
Ow! Ow! This brought back *painful* memories. In my second semester as a CS
student, we had to do our Lisp exercises on a system written by a *totally*
clueless graduate student (a math major :-), where the empty list *was*
represented as a list containing a NIL. I Kid You Not.[1]
I never could make the moron see why this was wrong, either. Luckily I managed
to program around this bug...
The second most painful experience occurred that same semester, using a Modula
programming system[2] with a structural editor, which could comment out code,
but not convert comments *back* into code...
Bye,
Jens.
[1] The idiot apparently assumed that every list, even an empty one, had to
have at least one cons cell.
[2] Written by another bunch of graduates, but this time they were victims
themselves, because *they* had to use a programming system generator
produced in the same institute (probably by... you can guess, right?)
Such fun we had ;-)
--
··········@acm.org phone:+49-7031-464-7698 (TELNET 778-7698)
http://www.bawue.de/~jjk/ fax:+49-7031-464-7351
PGP: 06 04 1C 35 7B DC 1F 26 As the air to a bird, or the sea to a fish,
0x555DA8B5 BB A2 F0 66 77 75 E1 08 so is contempt to the contemptible. [Blake]
In Common Lisp (but not in Scheme) the car and the cdr of the empty list
are both defined to be NIL. One way to implement this is to represent the
empty list as priveleged cons cell whose car and cdr both point to
itself. This makes it possible to implement #'CAR and #'CDR more
efficiently since they don't have to treat NIL as a special case.
Reasonable people may disagree on whether this is the best design, but
calling someone who adopts it an idiot or a moron reflects more poorly on
you than it does on them.
E.
In article <··············@bstde026.germany.agilent.com>, Jens Kilian
<···········@agilent.com> wrote:
> ················@pobox.com (Gareth McCaughan) writes:
> > [...] the original code rather nastily treats an empty list
> > as if it were a list containing just the item NIL.
>
> Ow! Ow! This brought back *painful* memories. In my second semester as a CS
> student, we had to do our Lisp exercises on a system written by a *totally*
> clueless graduate student (a math major :-), where the empty list *was*
> represented as a list containing a NIL. I Kid You Not.[1]
>
> I never could make the moron see why this was wrong, either. Luckily I
managed
> to program around this bug...
>
> The second most painful experience occurred that same semester, using a Modula
> programming system[2] with a structural editor, which could comment out code,
> but not convert comments *back* into code...
>
> Bye,
> Jens.
>
> [1] The idiot apparently assumed that every list, even an empty one, had to
> have at least one cons cell.
> [2] Written by another bunch of graduates, but this time they were victims
> themselves, because *they* had to use a programming system generator
> produced in the same institute (probably by... you can guess, right?)
> Such fun we had ;-)
···@jpl.nasa.gov (Erann Gat) writes:
> In Common Lisp (but not in Scheme) the car and the cdr of the empty list
> are both defined to be NIL. One way to implement this is to represent the
> empty list as priveleged cons cell whose car and cdr both point to
> itself. This makes it possible to implement #'CAR and #'CDR more
> efficiently since they don't have to treat NIL as a special case.
Such an implementation could not conform to CL, unless this priveledged
cons cell were special-cased not to be CONSP:
CL-USER(1): (consp nil)
NIL
CL-USER(2): (symbolp nil)
T
CL-USER(3): (consp ())
NIL
CL-USER(4):
It is, of course, listp:
CL-USER(4): (listp nil)
T
CL-USER(5):
I think that most CL implementations implement NIL as its own separate
low-level type. It has some characteristics of cons-ness, but is not
a cons. In fact, it is defined to be a symbol, albeit a special kind
of symbol (one which is listp, as well).
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 ·····@Franz.COM (internet)
In article <·············@beta.franz.com>, Duane Rettig <·····@franz.com> wrote:
> ···@jpl.nasa.gov (Erann Gat) writes:
>
> > In Common Lisp (but not in Scheme) the car and the cdr of the empty list
> > are both defined to be NIL. One way to implement this is to represent the
> > empty list as priveleged cons cell whose car and cdr both point to
> > itself. This makes it possible to implement #'CAR and #'CDR more
> > efficiently since they don't have to treat NIL as a special case.
>
> Such an implementation could not conform to CL, unless this priveledged
> cons cell were special-cased not to be CONSP:
Yes, of course.
> I think that most CL implementations implement NIL as its own separate
> low-level type.
Be that as it may, someone who chooses to do it otherwise is not
self-evidently an idiot.
E.
···@jpl.nasa.gov (Erann Gat) writes:
> In article <·············@beta.franz.com>, Duane Rettig <·····@franz.com> wrote:
>
> > ···@jpl.nasa.gov (Erann Gat) writes:
> >
> > > In Common Lisp (but not in Scheme) the car and the cdr of the empty list
> > > are both defined to be NIL. One way to implement this is to represent the
> > > empty list as priveleged cons cell whose car and cdr both point to
> > > itself. This makes it possible to implement #'CAR and #'CDR more
> > > efficiently since they don't have to treat NIL as a special case.
> >
> > Such an implementation could not conform to CL, unless this priveledged
> > cons cell were special-cased not to be CONSP:
>
> Yes, of course.
And it does seem to be the case that SBCL/CMUCL implement nil as such a
cons (although also with storage layed out as if a symbol). But they
specifically check for NIL in such predicates as CONSP and ATOM and work
that into the logic (I took a look at the source) and thus treat that
cons as if it weren't a cons cell in those cases where it shouldn't be
thought of as a cons cell.
Also, your implication was that #'CAR and #'CDR would be less efficient
in an implementation that didn't treat NIL as a cons cell. This is
simply not true; it is possible (and we do this) to take CAR and CDR
of cons cells _and_ of the non-cons NIL without testing for NIL as a
special case. In fact, since there are two "aligned" positions within
any one cons cell, no matter the word size, it is easy to select a pair
of distinct type tags for CONS and NIL so that on machines with
misalignment checking, no check need be done at all, even for CONS-ness,
before a CAR or CDR operation; it is just one instruction, which is
then trapped if the object being referenced is not a cons or nil.
> > I think that most CL implementations implement NIL as its own separate
> > low-level type.
>
> Be that as it may, someone who chooses to do it otherwise is not
> self-evidently an idiot.
That is true when "it" means to implement NIL in a similar manner as
SBCL/CMUCL. But my reading of Jens Kilian's post (which Jens has since
confirmed as the correct reading) was that not only was there a cons
cell, but it was not really of NULL type, and that implies that that
cons cell, while containing NIL, was not NIL itself, as is required
by the CL spec (and on a different front, scheme apparently treats the
empty list as a null pointer, whatever that means, but I read into
that that NIL cannot thus be a cons by definiton - this seems to be
consistent with the lack of ability to take the CAR or CDR of NIL -
but someone will have to correct me if I'm wrong, there).
I try not to call people idiots myself. But the programmer to whom
Jens refers was at best uninformed, and if the description of the
efforts that were taken to educate the uninformed programmer were
true, there are probably three conclusions that could be made:
1. The programmer was arrogant and thus uneducable.
2. Jens was not a good teacher (though from Jens' point of view
this would probably not be true)
3. The programmer was not very well informed about Lisp
implementation requirements.
Thus, when taking on Jens' point of view and frustration, I understood
perfectly the use of the word. I don't have to agree with someone's
wording in order to understand the meaning conveyed. In fact, the use
of the word conveyed to me a level of frustration felt.
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 ·····@Franz.COM (internet)
In article <·············@beta.franz.com>, Duane Rettig <·····@franz.com> wrote:
> Also, your implication was that #'CAR and #'CDR would be less efficient
> in an implementation that didn't treat NIL as a cons cell.
Could, not would.
> it is easy to select a pair
> of distinct type tags for CONS and NIL so that on machines with
> misalignment checking, no check need be done at all, even for CONS-ness,
> before a CAR or CDR operation; it is just one instruction, which is
> then trapped if the object being referenced is not a cons or nil.
AFAIK the Pentium is a notable example of an architecture that doesn't
have misalignment traps. (At least, a naive attempt to generate one by
doing:
char *x = "0000000000";
int y = *(int *)(x+1);
didn't work in Linux386.)
E.
···@jpl.nasa.gov (Erann Gat) writes:
> In article <·············@beta.franz.com>, Duane Rettig <·····@franz.com> wrote:
>
> > Also, your implication was that #'CAR and #'CDR would be less efficient
> > in an implementation that didn't treat NIL as a cons cell.
>
> Could, not would.
I'm saying that your statement was incorrect. When you said:
> ···@jpl.nasa.gov (Erann Gat) writes:
>
> > In Common Lisp (but not in Scheme) the car and the cdr of the empty list
> > are both defined to be NIL. One way to implement this is to represent the
> > empty list as priveleged cons cell whose car and cdr both point to
> > itself. This makes it possible to implement #'CAR and #'CDR more
> > efficiently since they don't have to treat NIL as a special case.
The statement "they [implementations that represent NIL as a cons] don't
have to treat NIL as a special case" implies that it is possible to
implement CAR/CDR more efficiently [than separate representations of
NIL and conses]. But if it can be shown that it is not possible to
implement CAR/CDR more efficiently than my nil-is-not-a-cons implementation,
then your statement is disproved, since no nil-as-a-cons implementation
you can come up with can then truly make it possible to be any more
efficient than my nil-is-not-a-cons implementation.
> > it is easy to select a pair
> > of distinct type tags for CONS and NIL so that on machines with
> > misalignment checking, no check need be done at all, even for CONS-ness,
> > before a CAR or CDR operation; it is just one instruction, which is
> > then trapped if the object being referenced is not a cons or nil.
>
> AFAIK the Pentium is a notable example of an architecture that doesn't
> have misalignment traps. (At least, a naive attempt to generate one by
> doing:
>
> char *x = "0000000000";
> int y = *(int *)(x+1);
>
> didn't work in Linux386.)
It doesn't matter. Alignment trapping can be done in software as well
as in hardware. Consider the "qcar" runtime function (yes, Allegro CL's
disassembler does work on entry points as well as Lisp functions). In the
following, I've cut off the trap code, which is uninteresting, and just
showed the bulk of this function:
CL-USER(1): (disassemble "qcar")
;; disassembly of #("qcar" 1075260738)
;; code start: #x40172d42:
0: 48 decl eax
1: a8 03 testb al,$3
3: 75 04 jnz 9
5: 8b 40 f0 movl eax,[eax-16]
8: c3 ret
9: ...
For cons tags of #b001 and a nil tag of #b101, the first instruction
decrements the LispVal, which should presumably be a cons or NIL.
The second instruction tests the least significant two bits for zero,
and the jnz jumps to trap code if the test fails. Otherwise the move
instruction moves the CAR at the (already-decremented) address, and
the access is done. (Allegro CL has an additional offset of 16 bytes
for every Lisp object, if you're wondering about that, but it's not
important here).
The "testb al,$3" is essentially a LISTP test. If I had done a
CONSP test instead, it would have been "testb al,$7" instead, which
would have been a test for the least significant _three_ bits to be
zero (with no performance difference). And as far as I know this
three byte instruction sequence is the fastest way to mask and test
a value for either a `*01' or a `001' tag value. It would be
interesting if anyone can come up with a better sequence...
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 ·····@Franz.COM (internet)
In article <·············@beta.franz.com>, Duane Rettig <·····@franz.com> wrote:
> It doesn't matter. Alignment trapping can be done in software as well
> as in hardware.
But that's less efficient. If I have hardware alignment trapping then I
can implement car and cdr with a single instruction, relying on the
hardware alignment traps to detect attempts to take the car and cdr of
non-listp values.
But surely you knew that (in fact you're the one who *taught* me this!),
so I must be missing something here.
E.
···@jpl.nasa.gov (Erann Gat) writes:
> In article <·············@beta.franz.com>, Duane Rettig <·····@franz.com> wrote:
>
> > It doesn't matter. Alignment trapping can be done in software as well
> > as in hardware.
>
> But that's less efficient. If I have hardware alignment trapping then I
> can implement car and cdr with a single instruction, relying on the
> hardware alignment traps to detect attempts to take the car and cdr of
> non-listp values.
Of course. But the difference between trapping/non-trapping CAR/CDR
accesses not what we've been discussing. What we have been discussing is
the difference between CAR/CDR accesses when NIL is a cons vs CAR/CDR
accesses when NIL is its own type.
> But surely you knew that (in fact you're the one who *taught* me this!),
> so I must be missing something here.
I think you must have switched gears when I brought up alignment-check
accesses as an example of how one can do CAR/CDR accesses with the same
efficiency regardless of whether nil is a cons or is its own type (i.e.,
in one instruction). I have never in this thread asked you to consider
the difference in efficiencies between trapping vs non-trapping styles.
In showing you that there is no way you can beat my nil-as-non-cons
tagging architecture with your (or any) nil-as-cons style, it was
easiest to show you with the trapping architecture, because it's
_really_ hard to beat a single instruction implementation with _any_
tagging style. But when you asked me about it, I then went back to
the non-trapping style and showed that its going to also be _really_
hard to beat my nil-as-non-cons tagging architecture with any
nil-as-cons tagging architecture.
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 ·····@Franz.COM (internet)
In article <·············@beta.franz.com>, Duane Rettig <·····@franz.com> wrote:
> ···@jpl.nasa.gov (Erann Gat) writes:
>
> > In article <·············@beta.franz.com>, Duane Rettig
<·····@franz.com> wrote:
> >
> > > It doesn't matter. Alignment trapping can be done in software as well
> > > as in hardware.
> >
> > But that's less efficient. If I have hardware alignment trapping then I
> > can implement car and cdr with a single instruction, relying on the
> > hardware alignment traps to detect attempts to take the car and cdr of
> > non-listp values.
>
> Of course. But the difference between trapping/non-trapping CAR/CDR
> accesses not what we've been discussing. What we have been discussing is
> the difference between CAR/CDR accesses when NIL is a cons vs CAR/CDR
> accesses when NIL is its own type.
>
> > But surely you knew that (in fact you're the one who *taught* me this!),
> > so I must be missing something here.
>
> I think you must have switched gears when I brought up alignment-check
> accesses as an example of how one can do CAR/CDR accesses with the same
> efficiency regardless of whether nil is a cons or is its own type (i.e.,
> in one instruction). I have never in this thread asked you to consider
> the difference in efficiencies between trapping vs non-trapping styles.
> In showing you that there is no way you can beat my nil-as-non-cons
> tagging architecture with your (or any) nil-as-cons style, it was
> easiest to show you with the trapping architecture, because it's
> _really_ hard to beat a single instruction implementation with _any_
> tagging style. But when you asked me about it, I then went back to
> the non-trapping style and showed that its going to also be _really_
> hard to beat my nil-as-non-cons tagging architecture with any
> nil-as-cons tagging architecture.
OK, fair enough. But I'll make a few additional comments:
1. In between being self-evidently an idiot, and being smart enough to
come up with compiler optimizations like yours there is a broad range of
possibilities that one ought to consider before hurling epithets around.
(This isn't directed at you, but at the person to whom I originally
replied.)
2. It still seems to me that in a trapping architecture, nil-as-cons is
potentially more efficient because I can take the CAR/CDR of NIL in one
instruction without trapping only if it's a CONS. (But I haven't studied
your non-trapping design closely enough to know if it's applicable to a
trapping architecture, so I could be wrong about this.)
3. One might for reasons of portability be writing all this is C or C++,
in which case clever compiler tricks like the one you suggest are not
generally possible. In such cases, nil-as-cons can still be a win.
E.
···@jpl.nasa.gov (Erann Gat) writes:
> OK, fair enough. But I'll make a few additional comments:
>
> 1. In between being self-evidently an idiot, and being smart enough to
> come up with compiler optimizations like yours there is a broad range of
> possibilities that one ought to consider before hurling epithets around.
> (This isn't directed at you, but at the person to whom I originally
> replied.)
Agreed. I try never to hurl epithets myself.
> 2. It still seems to me that in a trapping architecture, nil-as-cons is
> potentially more efficient because I can take the CAR/CDR of NIL in one
> instruction without trapping only if it's a CONS. (But I haven't studied
===============================^^^^^^^^^^^^^^^^^^^
But this is precisely what I've been trying to demonstrate to you
is _not_ the case! Apparently I've not been successful. If, in a
32-bit width lisp NIL has a tag that happens to be 4 larger than the
CONS tag, then either tag can support a CAR/CDR style access without
alignment problems, whether hardware induced or software induced.
> your non-trapping design closely enough to know if it's applicable to a
> trapping architecture, so I could be wrong about this.)
It is simply an implementation in software of a trapping architecture,
so I'd say Yes, it is applicable.
> 3. One might for reasons of portability be writing all this is C or C++,
> in which case clever compiler tricks like the one you suggest are not
> generally possible. In such cases, nil-as-cons can still be a win.
The fact that such clever tricks are not possible in C/C++ are the
very reason why we don't use C as our "assembler". I posted a rather
long article a couple of years ago enumerating this and other reasons
for not using C as a target language.
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 ·····@Franz.COM (internet)
From: Teemu Kalvas
Subject: Re: Results of SHRDLU porting project
Date:
Message-ID: <877km4wtch.fsf@gobi.s2.org>
···@jpl.nasa.gov (Erann Gat) writes:
> In article <·············@beta.franz.com>, Duane Rettig <·····@franz.com> wrote:
>
> > Also, your implication was that #'CAR and #'CDR would be less efficient
> > in an implementation that didn't treat NIL as a cons cell.
>
> Could, not would.
>
> > it is easy to select a pair
> > of distinct type tags for CONS and NIL so that on machines with
> > misalignment checking, no check need be done at all, even for CONS-ness,
> > before a CAR or CDR operation; it is just one instruction, which is
> > then trapped if the object being referenced is not a cons or nil.
>
> AFAIK the Pentium is a notable example of an architecture that doesn't
> have misalignment traps. (At least, a naive attempt to generate one by
> doing:
>
> char *x = "0000000000";
> int y = *(int *)(x+1);
>
> didn't work in Linux386.)
IIRC, alignment checks were introduced to the processor family in the
486. Your attempt fails because it can be, and typically is turned
off. There are two processor control bits in two different places
which both need to be ones for misaligned memory references to be
trapped. The other one is in the flags register and settable by user
programs, and the other is somewhere in the control registers (CR0, I
think), and with the usual operating systems not modifiable.
This second bit is on on Linux and off on at least NetBSD and Windows.
I discussed CAR and CDR optimization with Duane maybe two years ago
here, and the same issue came up then, too.
--
Teemu Kalvas
In article <··············@gobi.s2.org>, Teemu Kalvas <·····@s2.org> wrote:
> IIRC, alignment checks were introduced to the processor family in the
> 486. Your attempt fails because it can be, and typically is turned
> off. There are two processor control bits in two different places
> which both need to be ones for misaligned memory references to be
> trapped. The other one is in the flags register and settable by user
> programs, and the other is somewhere in the control registers (CR0, I
> think), and with the usual operating systems not modifiable.
>
> This second bit is on on Linux and off on at least NetBSD and Windows.
Sorry, I'm having trouble following all the antedecent referents, since
you make multiple references to "the other one". What's the bottom line
on Linux: is it possible for a user program to generate an alignment
trap? (And if not, is it possible to generate an alignment trap with a
kernel hack without crashing the whole kernel?)
E.
···@jpl.nasa.gov (Erann Gat) writes:
> Sorry, I'm having trouble following all the antedecent referents, since
> you make multiple references to "the other one". What's the bottom line
> on Linux: is it possible for a user program to generate an alignment
> trap? (And if not, is it possible to generate an alignment trap with a
> kernel hack without crashing the whole kernel?)
This varies from machine to machine and kernel to kernel.
Many Unix systems catch alignment faults and execute the load/store by
hand. (Indeed, that's exactly what the Vax did in microcode.)
Thomas
From: Teemu Kalvas
Subject: Re: Results of SHRDLU porting project
Date:
Message-ID: <873cwrx5db.fsf@gobi.s2.org>
···@jpl.nasa.gov (Erann Gat) writes:
> In article <··············@gobi.s2.org>, Teemu Kalvas <·····@s2.org> wrote:
>
> > IIRC, alignment checks were introduced to the processor family in the
> > 486. Your attempt fails because it can be, and typically is turned
> > off. There are two processor control bits in two different places
> > which both need to be ones for misaligned memory references to be
> > trapped. The other one is in the flags register and settable by user
> > programs, and the other is somewhere in the control registers (CR0, I
> > think), and with the usual operating systems not modifiable.
> >
> > This second bit is on on Linux and off on at least NetBSD and Windows.
>
> Sorry, I'm having trouble following all the antedecent referents, since
> you make multiple references to "the other one". What's the bottom line
> on Linux: is it possible for a user program to generate an alignment
> trap? (And if not, is it possible to generate an alignment trap with a
> kernel hack without crashing the whole kernel?)
Um, sorry, I probably had a long day.
On Linux, you can generate an alignment trap from a user program. The
trap will be delivered to the process as a signal.
On NetBSD and Windows, you cannot. I made the necessary changes on
OpenBSD, actually, to make it possible to generate the trap, and the
kernel crashed, but the kernel crash was not too difficult to fix. I
have not submitted diffs, because I feel that it is a decision and not
an accident to disallow the alignment traps on the *BSDs. I don't
really feel like debating the issue on several kernel development
mailing lists.
--
Teemu Kalvas
In article <··············@gobi.s2.org>, Teemu Kalvas <·····@s2.org> wrote:
> On Linux, you can generate an alignment trap from a user program. The
> trap will be delivered to the process as a signal.
Ah, that's good to know. If you happen to have a pointer to instructions
on how to do it and/or example code that would be much appreciated. (I'm
not a systems programmer, so I don't have a Pentium manual at ready hand.)
Thanks,
E.
From: Teemu Kalvas
Subject: Re: Results of SHRDLU porting project
Date:
Message-ID: <87y9ejuv2e.fsf@gobi.s2.org>
···@jpl.nasa.gov (Erann Gat) writes:
> In article <··············@gobi.s2.org>, Teemu Kalvas <·····@s2.org> wrote:
>
> > On Linux, you can generate an alignment trap from a user program. The
> > trap will be delivered to the process as a signal.
>
> Ah, that's good to know. If you happen to have a pointer to instructions
> on how to do it and/or example code that would be much appreciated. (I'm
> not a systems programmer, so I don't have a Pentium manual at ready hand.)
Here's some code to test it.
#include <stdlib.h>
#include <signal.h>
#include <stdio.h>
#include <ucontext.h>
enum {
I386_GS = 0, I386_FS, I386_ES, I386_DS, I386_EDI, I386_ESI, I386_EBP,
I386_ESP, I386_EBX, I386_EDX, I386_ECX, I386_EAX, I386_TRAPNO,
I386_ERR, I386_EIP, I386_CS, I386_EFL, I386_UESP, I386_SS
};
void signal_handler(int sig, siginfo_t *siginfo, struct ucontext *ucontext)
{
if (sig == SIGBUS && siginfo->si_code == BUS_ADRALN) {
fprintf(stderr,
"alignment fault at instruction pointer %p\neax = %x\nedx = %x\n",
siginfo->si_addr, ucontext->uc_mcontext.gregs[I386_EAX],
ucontext->uc_mcontext.gregs[I386_EDX]);
}
exit(1);
}
int buffer[4] = { 0x12345678, 0x21436587, 0x13243546, 0x31425364 };
int main(void)
{
int i;
struct sigaction action;
action.sa_flags = SA_SIGINFO;
action.sa_sigaction = (void(*)(int,siginfo_t*,void*))&signal_handler;
sigaction(SIGBUS, &action, 0);
asm("pushfl\n popl %%eax\n orl $0x40000,%%eax\n pushl %%eax\n popfl"
: : : "eax");
i = *(int*)(((char*)buffer)+1);
printf("%x\n", i);
return 0;
}
The critical flags modifying part in assembler just sets bit 18 in the
flags register.
This compiles with gcc on Linux. In real life you would probably want
to set signal masks and system call restart behaviour but all that is
explained in the siginfo and related man pages, and omitted here for
brevity.
--
Teemu Kalvas
Teemu Kalvas <·····@s2.org> writes:
> ···@jpl.nasa.gov (Erann Gat) writes:
>
> > In article <··············@gobi.s2.org>, Teemu Kalvas <·····@s2.org> wrote:
> >
> > > On Linux, you can generate an alignment trap from a user program. The
> > > trap will be delivered to the process as a signal.
> >
> > Ah, that's good to know. If you happen to have a pointer to instructions
> > on how to do it and/or example code that would be much appreciated. (I'm
> > not a systems programmer, so I don't have a Pentium manual at ready hand.)
> Here's some code to test it.
[ example code elided ]
If you are performing a specific code sequence that uses this alignment
trap trick, then this technique is fine (but be sure to reset the bit
before returning from the function, when further processing is going
to be done). However, if the AC (alignment check) bit is being set
for a general purpose environment (e.g., Lisp), then you must also
arrange for the bit to be un-set before any calls to C functionality.
The reason for this is that C libraries do not expect the bit to be
set, and some would fail if it were set. For example, alignments of
double-floats in C structs are specified to be 4 bytes on both Linux
and FreeBSD on the x86, instead of the usual (more space-wasteful but
aligned) 8 bytes. But that means that structure accesses of
double-floats that happened to be 4-byte aligned but not 8-byte aligned
will cause an alignment trap unexpectedly.
Now it may be, and I haven't tested it lately, that such misaligned
double-float accesses are caught and handled by a first-level interrupt
handler. And since we generally don't use alignment traps for
double-floats in Lisp (on those ports where we take advantage of
alignment traps), this automatic handling of double-floats would not
conflict with the Lisp operations. But because other alignment traps
might also be possible in C code, there is still no way to get around
the need to un-set the AC bit before entering/re-entering the C world,
because there's no way we want to be responsible for broken C code...
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 ·····@Franz.COM (internet)
In article <·············@beta.franz.com>, Duane Rettig <·····@franz.com> wrote:
> If you are performing a specific code sequence that uses this alignment
> trap trick, then this technique is fine (but be sure to reset the bit
> before returning from the function, when further processing is going
> to be done). However, if the AC (alignment check) bit is being set
> for a general purpose environment (e.g., Lisp), then you must also
> arrange for the bit to be un-set before any calls to C functionality.
A prescient observation. When I ran Teemu's code unmodified I got an
infinite regress of bus errors, apparently because the fprintf call inside
the signal handler was generating alignment faults!
E.
From: Teemu Kalvas
Subject: Re: Results of SHRDLU porting project
Date:
Message-ID: <87u1p6vb7o.fsf@gobi.s2.org>
···@jpl.nasa.gov (Erann Gat) writes:
> In article <·············@beta.franz.com>, Duane Rettig <·····@franz.com> wrote:
>
> > If you are performing a specific code sequence that uses this alignment
> > trap trick, then this technique is fine (but be sure to reset the bit
> > before returning from the function, when further processing is going
> > to be done). However, if the AC (alignment check) bit is being set
> > for a general purpose environment (e.g., Lisp), then you must also
> > arrange for the bit to be un-set before any calls to C functionality.
>
> A prescient observation. When I ran Teemu's code unmodified I got an
> infinite regress of bus errors, apparently because the fprintf call inside
> the signal handler was generating alignment faults!
Interesting, it ran just fine for me. Serves me right for my "it
runs, post it" attitude. :-)
--
Teemu Kalvas
In article <··············@gobi.s2.org>, Teemu Kalvas <·····@s2.org> wrote:
> ···@jpl.nasa.gov (Erann Gat) writes:
>
> > In article <·············@beta.franz.com>, Duane Rettig
<·····@franz.com> wrote:
> >
> > > If you are performing a specific code sequence that uses this alignment
> > > trap trick, then this technique is fine (but be sure to reset the bit
> > > before returning from the function, when further processing is going
> > > to be done). However, if the AC (alignment check) bit is being set
> > > for a general purpose environment (e.g., Lisp), then you must also
> > > arrange for the bit to be un-set before any calls to C functionality.
> >
> > A prescient observation. When I ran Teemu's code unmodified I got an
> > infinite regress of bus errors, apparently because the fprintf call inside
> > the signal handler was generating alignment faults!
>
> Interesting, it ran just fine for me. Serves me right for my "it
> runs, post it" attitude. :-)
It's a really weird bug. If I change the diagnostic message to print to
stdout rather than stderr it works. Trying to write more than 20
characters to stderr seems to be the proximate cause of the second
alignment fault, which is actually generated inside memcpy. Here's a
backtrace just in case you're curious:
#0 0x4011b73c in __mempcpy () from /lib/i686/libc.so.6
#1 0x401100ab in _IO_default_xsputn (f=0xbfffcfa4, data=0x80487fd, n=21)
at genops.c:415
#2 0x400e95eb in _IO_vfprintf (s=0xbfffcfa4,
format=0x80487fd '.' <repeats 20 times>, "\n", ap=0xbffff74c)
at vfprintf.c:1307
#3 0x400ee564 in buffered_vfprintf (s=0x40066960,
format=0x80487fd '.' <repeats 20 times>, "\n", args=0x0) at vfprintf.c:2087
#4 0x400e94bb in _IO_vfprintf (s=0x40066960,
format=0x80487fd '.' <repeats 20 times>, "\n", ap=0xbffff74c)
at vfprintf.c:1272
#5 0x400f35b7 in fprintf (stream=0x40066960,
format=0x80487fd '.' <repeats 20 times>, "\n") at fprintf.c:32
#6 0x080486d0 in signal_handler ()
#7 <signal handler called>
#8 0x08048719 in main ()
#9 0x400b0177 in __libc_start_main (main=0x80486e0 <main>, argc=1,
ubp_av=0xbffffbfc, init=0x80484d4 <_init>, fini=0x8048780 <_fini>,
rtld_fini=0x4000e184 <_dl_fini>, stack_end=0xbffffbec)
at ../sysdeps/generic/libc-start.c:129
I think the bottom line on this is just that Duane is right: turn
alignment checking off before going back the C world. (Damn, what a pain
in the ass!) Thanks Duane! (And thanks Teemu for posting the code.)
E.
Duane Rettig <·····@franz.com> writes:
> I think that most CL implementations implement NIL as its own separate
> low-level type. It has some characteristics of cons-ness, but is not
> a cons. In fact, it is defined to be a symbol, albeit a special kind
> of symbol (one which is listp, as well).
In SBCL (and CMUCL) it's actually both a cons and a symbol:
The tag bits are chosen such that list-pointer-lowtag+4=other-pointer-lowtag
A symbol has a 4 byte header word, and its first two slots are `value'
and `unused' (or on some platforms, `hash code'). A cons has no
header
The symbol for NIL is 4 bytes from the start of static space. Because
of this unusual alignment (everything else is usually 8 byte aligned)
a pointer to it looks like a list pointer with car and cdr slots which
overlap the value and `unused' of the symbol. However, anything that
_knows_ it's pointing at a symbol will subtract other-pointer-lowtag
instead of list-pointer-lowtag before dereferencing, et viola, it's
looking at a symbol.
(I found this out by accident a few months ago when the `unused' slot
was removed. Anything setting symbol properties on 'NIL then caused
(CDR NIL) to be non-NIL, which was briefly fun to work out.)
http://www.geocrawler.com/lists/3/SourceForge/1663/0/7739869
-dan
--
http://ww.telent.net/cliki/ - Link farm for free CL-on-Unix resources
Daniel Barlow <···@telent.net> writes:
> Duane Rettig <·····@franz.com> writes:
>
> > I think that most CL implementations implement NIL as its own separate
> > low-level type. It has some characteristics of cons-ness, but is not
> > a cons. In fact, it is defined to be a symbol, albeit a special kind
> > of symbol (one which is listp, as well).
>
> In SBCL (and CMUCL) it's actually both a cons and a symbol:
I stand corrected. It looks to me like NIL actually has the same tag
as a cons cell. (In fact, that is consistent with the name
"list-pointer-lowtag", as opposed to something with "cons" in the name,
which is what Allegro CL uses). And my browsing through CMUCL sources
tells me that CONSP must check for NIL (for rejection) as well as the
list-tag.
> The tag bits are chosen such that list-pointer-lowtag+4=other-pointer-lowtag
Does this then mean that SBCL and CMUCL cannot take advantage of alignment
traps on machines which provide them? Such alignment traps allow CxxR
sequences to be blown through with one instruction per access without
worrying about any of the intermediate values not being conses or nil.
> A symbol has a 4 byte header word, and its first two slots are `value'
> and `unused' (or on some platforms, `hash code'). A cons has no
> header
>
> The symbol for NIL is 4 bytes from the start of static space. Because
> of this unusual alignment (everything else is usually 8 byte aligned)
> a pointer to it looks like a list pointer with car and cdr slots which
> overlap the value and `unused' of the symbol. However, anything that
> _knows_ it's pointing at a symbol will subtract other-pointer-lowtag
> instead of list-pointer-lowtag before dereferencing, et viola, it's
> looking at a symbol.
This is the kind of base-level design that makes building CL's fun.
Allegro CL used to do something similar to this. However, because we
chose the cons tag, symbol tag (which was different from an "other" tag)
and null tag to be distinct from the start, it was hard to choose
appropriate slots to double as symbol slots and cons slots, especially
on machines where misaligned word accesses would cause problems. At
one point we masked out one of the tag bits to allow proper alignment
of the punned words. But that meant that every symbol access needed
an extra AND instruction, and we finally settled on checking explicitly
for NIL on symbol accesses, and providing a special symbol close to NIL
to serve as NIL's symbol.
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 ·····@Franz.COM (internet)
Duane Rettig <·····@franz.com> writes:
> Daniel Barlow <···@telent.net> writes:
>
> > The tag bits are chosen such that list-pointer-lowtag+4=other-pointer-lowtag
>
> Does this then mean that SBCL and CMUCL cannot take advantage of alignment
> traps on machines which provide them? Such alignment traps allow CxxR
> sequences to be blown through with one instruction per access without
> worrying about any of the intermediate values not being conses or nil.
To answer your question, I think you're right, and that there's
nothing particularly clever in the sbcl/cmucl system that would enable
the kind of optimization you're discussing here; I don't think that
it's possible in a system that doesn't tag NIL specially (though I'm
open to correction on that point :-)
> > [ tag punning ]
>
> This is the kind of base-level design that makes building CL's fun.
Oh, indeed :-) the juggling of different constraints is entertaining.
Though currently I'm suffering pains of not understanding some of
SBCL's performance characteristics[*], so possibly I'm less able to talk
about "fun" than I am generally. Still, it's a good hobby!
Cheers,
Christophe
[*] In trying some optimizations, I've just managed to implement a 30x
performance degradation in complex CLOS methods. I don't think I'll be
checking that change in...
--
Jesus College, Cambridge, CB5 8BL +44 1223 510 299
http://www-jcsu.jesus.cam.ac.uk/~csr21/ (defun pling-dollar
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)
Christophe Rhodes <·····@cam.ac.uk> writes:
> Duane Rettig <·····@franz.com> writes:
>
> > Daniel Barlow <···@telent.net> writes:
> >
> > > The tag bits are chosen such that list-pointer-lowtag+4=other-pointer-lowtag
> >
> > Does this then mean that SBCL and CMUCL cannot take advantage of alignment
> > traps on machines which provide them? Such alignment traps allow CxxR
> > sequences to be blown through with one instruction per access without
> > worrying about any of the intermediate values not being conses or nil.
>
> To answer your question, I think you're right, and that there's
> nothing particularly clever in the sbcl/cmucl system that would enable
> the kind of optimization you're discussing here; I don't think that
> it's possible in a system that doesn't tag NIL specially (though I'm
> open to correction on that point :-)
You could still take CAR/CDR in the same way, even if NIL were the same
tag as CONS, but there would be two other changes that would have to
be made:
1. You'd have to move the tag at list-pointer-lowtag+4 somewhere else;
it could never represent any object for which CAR or CDR is an illegal
operation. Otherwise, you might have users trying to take the CAR of
'foo and succeeding...
2. Given #1, It would be very hard to pun symbols (of which NIL is
one) against CONSes, so you would probably have to put NIL's symbol
structure somewhere close (but not on top of the CONS representing
nil).
> > > [ tag punning ]
> >
> > This is the kind of base-level design that makes building CL's fun.
>
> Oh, indeed :-) the juggling of different constraints is entertaining.
> Though currently I'm suffering pains of not understanding some of
> SBCL's performance characteristics[*], so possibly I'm less able to talk
> about "fun" than I am generally. Still, it's a good hobby!
>
> Cheers,
>
> Christophe
>
> [*] In trying some optimizations, I've just managed to implement a 30x
> performance degradation in complex CLOS methods. I don't think I'll be
> checking that change in...
Yes, that is part of the game, too :-)
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 ·····@Franz.COM (internet)
···@jpl.nasa.gov (Erann Gat) writes:
> Reasonable people may disagree on whether this is the best design, but
> calling someone who adopts it an idiot or a moron reflects more poorly on
> you than it does on them.
Well, it wasn't the only stupid idea of his; and in his "Lisp",
(NULL '())
-> NIL
I consider that moronic enough.
--
··········@acm.org phone:+49-7031-464-7698 (TELNET 778-7698)
http://www.bawue.de/~jjk/ fax:+49-7031-464-7351
PGP: 06 04 1C 35 7B DC 1F 26 As the air to a bird, or the sea to a fish,
0x555DA8B5 BB A2 F0 66 77 75 E1 08 so is contempt to the contemptible. [Blake]
Jens Kilian <···········@agilent.com> writes:
> we had to do our Lisp exercises on a system written by a *totally*
> clueless graduate student (a math major :-), where the empty list *was*
> represented as a list containing a NIL.
I don't quite understand the axioms of this system.
What were the CAR and CDR of the empty list?
Was there a difference between (T NIL) and (T)?
Kalle Olavi Niemitalo <···@iki.fi> writes:
> Jens Kilian <···········@agilent.com> writes:
>
> > we had to do our Lisp exercises on a system written by a *totally*
> > clueless graduate student (a math major :-), where the empty list *was*
> > represented as a list containing a NIL.
>
> I don't quite understand the axioms of this system.
> What were the CAR and CDR of the empty list?
> Was there a difference between (T NIL) and (T)?
I don't remember exactly; what I do know is that this was *not* an attempt
at clever implementation techniques as mentioned upthread; discussion with
the guy showed that he didn't even understand *why* it was a problem that
in his "Lisp", NULL applied to an "empty" list returned NIL.
--
··········@acm.org phone:+49-7031-464-7698 (TELNET 778-7698)
http://www.bawue.de/~jjk/ fax:+49-7031-464-7351
PGP: 06 04 1C 35 7B DC 1F 26 As the air to a bird, or the sea to a fish,
0x555DA8B5 BB A2 F0 66 77 75 E1 08 so is contempt to the contemptible. [Blake]
On 14 May 2002 20:44:48 +0300, Kalle Olavi Niemitalo <···@iki.fi> wrote:
>Jens Kilian <···········@agilent.com> writes:
>
>> we had to do our Lisp exercises on a system written by a *totally*
>> clueless graduate student (a math major :-), where the empty list *was*
>> represented as a list containing a NIL.
>
>I don't quite understand the axioms of this system.
>What were the CAR and CDR of the empty list?
>Was there a difference between (T NIL) and (T)?
I fail to understand how a graduate level mathematician could be confused about
this. This is analogous to the difference between the empty set, and a set
containing the empty set. If you can't sort that out, you belong in the
Liberal Arts faculty. ;)
···@localhost.localdomain (Kaz Kylheku) writes:
> I fail to understand how a graduate level mathematician could be
> confused about this. This is analogous to the difference between the
> empty set, and a set containing the empty set. If you can't sort
> that out, you belong in the Liberal Arts faculty. ;)
The liberal arts faculty that *I* hang out with are perfectly well
aware of the distinction, since it was their sort--philosophers--who
first noted it. Logic and foundations of math is, after all, part of
our bailiwick.
Thomas
·········@becket.net (Thomas Bushnell, BSG) writes:
> ···@localhost.localdomain (Kaz Kylheku) writes:
>
> > I fail to understand how a graduate level mathematician could be
> > confused about this. This is analogous to the difference between the
> > empty set, and a set containing the empty set. If you can't sort
> > that out, you belong in the Liberal Arts faculty. ;)
>
> The liberal arts faculty that *I* hang out with are perfectly well
> aware of the distinction, since it was their sort--philosophers--who
> first noted it. Logic and foundations of math is, after all, part of
> our bailiwick.
Oops, and of course I missed the *REAL* point, which is that:
Mathematics *is* a liberal art--and in the humanities, not the natural
sciences. (Which does not, by any means, excuse the legions of
humanties academics who are mathematically illiterate.)
Indeed, the seven liberal arts are:
the trivium: grammar, rhetoric, and logic
the quadrivium: arithmetic, music, geometry, astronomy
The trivium were arts of language, and the quadrivium arts of
mathematics. (Though interestingly the present question, the
distinction between {} and {{}}, is these days one of logic and
foundations of math, and would belong under "logic" in the medieval
list.)
Modern universities typically have four academic curricula (in
addition to professional schools like management, medicine, law, and
so forth): humanities, sciences, engineering, fine arts.
Of the seven liberal arts, five of them belong in the humanities
curriculum: grammar, rhetoric, logic, arithmetic, and geometry.
Music of course lands in the fine arts curricilum, and astronomy in
the sciences curriculum.
Medieval universities (from which we get the list of liberal arts) did
not teach engineering; those tasks were managed by the guilds and
other arrangements entirely outside the academic system.
Obviously we have added more to the medieval list than just
engineering. The fine art labelled "music" in the middle ages was
mostly theory--it's part of the quadrivium--the math--because music
theory is a kind of applied mathematics. Practical performance
aspects were also not academic in the middle ages.
The rest of the special sciences--physics, chemistry, and so forth,
were of course also studied in the middle ages. Physics was under the
rubric "philosophy", which you would study after you finished the
seven liberal arts. Chemistry was mostly non-academic, and the
provenance of alchemists working in mostly secret. Psychology was a
very important subject, also studied as a branch of philosophy.
There are also brand new humanities, mostly ignored in the medieval
university, history being the most important one.
Now if you've followed me thus far you're going "wait, mathematics is
in the sciences, not the humanities". Here you are right about the
usual de facto placement, but not about where it actually belongs...
Mathematics is simply not a science (in the modern sense of that
word); a brief reflection on the role of experiment and theory will
show this. I have a theory about why this is so:
History of the academy then:
The medieval curriculum had everyone studying mostly the same things
in the following order: trivium, quadrivium, philosophy, theology. In
the late middle ages various specialized degrees were available after
you had studied philosophy.
This mostly lasted all the way to the 18th century. Then new
humanities like history started to get added, and shortly thereafter
the special sciences began to become much more advanced and highly
specialized. The result was the humanities/science/fine-arts split,
with engineering coming along in the 20th century as a distinct
academic category.
I believe that this structure is now breaking down. One sign of that
is the miscategorization of mathematics as a science. Another is the
much varied question of the correct placement of computer science--is
it a science? a branch of mathematics? an engineering discipline? a
social science (think of the MIT Media Lab)? A branch of psychology?
It's not clear...and different universities have taken all these
tacks. In many it lands completely outside the existing "colleges"
into which the university is divided.
I think we are heading to a break between "technical" and
"non-technical"--the reason that math is in the natural sciences
category in most universities is because the natural sciences use lots
of math! The exact shape of this is yet to be seen.
Thomas
"Thomas Bushnell, BSG" <·········@becket.net> wrote in message ···················@becket.becket.net...
> >
> > The liberal arts faculty that *I* hang out with are perfectly well
> > aware of the distinction, since it was their sort--philosophers--who
> > first noted it. Logic and foundations of math is, after all, part of
> > our bailiwick.
>
> Oops, and of course I missed the *REAL* point, which is that:
[long discussion of the history of liberal arts elided]
So this comes in handy when you are flipping burgers at McDonalds?
From: Erik Naggum
Subject: Re: clueless representation of empty list
Date:
Message-ID: <3230591232456842@naggum.net>
* "Joe Marshall" <·············@attbi.com>
| [long discussion of the history of liberal arts elided]
|
| So this comes in handy when you are flipping burgers at McDonalds?
At least you know what a customer _really_ means when he says
"make me one with everything".
--
In a fight against something, the fight has value, victory has none.
In a fight for something, the fight is a loss, victory merely relief.
70 percent of American adults do not understand the scientific process.
Erik Naggum <····@naggum.net> wrote in message
·····················@naggum.net...
> * "Joe Marshall" <·············@attbi.com>
> | [long discussion of the history of liberal arts elided]
> |
> | So this comes in handy when you are flipping burgers at McDonalds?
>
> At least you know what a customer _really_ means when he says
> "make me one with everything".
ROTFLMAO!! hilarious... :)
--
Coby Beck
(remove #\Space "coby 101 @ bigpond . com")
In article <················@naggum.net>, Erik Naggum wrote:
> * "Joe Marshall" <·············@attbi.com>
> | [long discussion of the history of liberal arts elided]
> |
> | So this comes in handy when you are flipping burgers at McDonalds?
>
> At least you know what a customer _really_ means when he says
> "make me one with everything".
In my younger days I worked at McDonalds and there are regional
hamburger encoding issues( mustard for example) that come into play.
So when you ask for everything you can and will get different burgers
depending on where you are.
there is just no escaping localization issues
marc
> --
> In a fight against something, the fight has value, victory has none.
> In a fight for something, the fight is a loss, victory merely relief.
>
> 70 percent of American adults do not understand the scientific process.
"Marc Spitzer" <····@oscar.eng.cv.net> wrote in message ························@oscar.eng.cv.net...
> In article <················@naggum.net>, Erik Naggum wrote:
> > * "Joe Marshall" <·············@attbi.com>
> > | [long discussion of the history of liberal arts elided]
> > |
> > | So this comes in handy when you are flipping burgers at McDonalds?
> >
> > At least you know what a customer _really_ means when he says
> > "make me one with everything".
>
> In my younger days I worked at McDonalds and there are regional
> hamburger encoding issues( mustard for example) that come into play.
The UNICONDIMENT consortium is attempting to address just this issue.
By assigning a unique number to anything anybody has ever put on a
burger (or burger-like sandwich), they hope to avoid problems like the
above. One benefit of UNICONDIMENT is that the various toppings are
assigned in gray-code, thus it is possible to measure the similarity
of topping sets by counting how many bits have changed. This value
is the ham-burger-ing distance.
There are, however, still issues concerning the grain used to make
the buns (see http://www.unicondiment.org/cerealization.htm)
"Joe Marshall" <·············@attbi.com> writes:
> So this comes in handy when you are flipping burgers at McDonalds?
Oh, I wouldn't (er, didn't) last three months at McDonald's.
But I think it would do well driving a cab. Who knows.
Thomas
Keldon Jones <······@ont.com> writes:
> I don't want to repeat everything I said there, but there were
> two distinct efforts: one to port the SHRDLU code to Common LISP, and a
> second to write from scratch a MacLISP interpreter to run the original
> unmodified code.
There is now a PDP-10 emulator capable of running ITS, so I believe
you can run the original MacLISP if you want to.
http://www.aracnet.com/~healyzh/pdp10emu.html
http://www.its.os.org/
--
Lars Brinkhoff http://lars.nocrew.org/ Linux, GCC, PDP-10,
Brinkhoff Consulting http://www.brinkhoff.se/ HTTP programming