I was reading Graham's "ANSI Common LISP" while travelling home from
work on the bus last night.
In one of the appendicies at the back of the book he gives examples of
possible implementations for a number of the functions/macros that make
up CLISP.
However, it is prefaced with a list of 30-odd operations that are
assumed to already exist, of which
car and cdr are included. Why is this? is this (to quote another) "deep
magic" ?
I am a 'newbie' with little experience of LISP and realise this may be a
daft thing to ask. :-)
Regards,
Will
In article <·················@pindar.com>,
William Deakin <········@pindar.com> wrote:
>However, it is prefaced with a list of 30-odd operations that are
>assumed to already exist, of which
>car and cdr are included. Why is this? is this (to quote another) "deep
>magic" ?
What more primitive Lisp operation would you suggest they be implemented in
terms of? While it's possible to implement them using structures, CLOS, or
closures, such implementations would not be useful the the pedagogic
purpose of that appendix. It's supposed to be showing how complex
functions could be implemented in terms of simpler functions that the
reader is likely to understand already, and implementing CAR/CDR in terms
of these complex features would not serve that purpose.
In reality, CAR and CDR are typically recognized by the compiler and
open-coded into simple machine instructions. A cons is represented as two
adjacent pointers in memory, and CAR/CDR just indirect through the address
in the word that a reference points to (CAR) or the word following it
(CDR). Most CPUs provide native instructions and addressing modes that
implement this in a single instruction (although the compiler may need to
include additional code to do type checking first). On the PDP-10, the
instruction HLRZ implemented the CAR function (Howard Cannon, the inventor
of Flavors for the MIT Lisp Machine, had HLRZ as his vanity license plate).
In fact, the names CAR and CDR come from the machine instructions that
implemented them on the computer system that Lisp was first implemented on.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
* William Deakin wrote:
> I was reading Graham's "ANSI Common LISP" while travelling home from
> However, it is prefaced with a list of 30-odd operations that are
> assumed to already exist, of which
> car and cdr are included. Why is this? is this (to quote another) "deep
> magic" ?
I think because CAR & CDR and such like are really primitive machine
operations. They basically say `get the first word of this two-word
chunk of memory' or something similar. It's a bit like asking why `+'
is a primitive function (well, why `binary-+' is I suppose). Machines
just have those operations.
Except...
(defun kons (kar kdr)
#'(lambda (op &optional new)
(ecase op
(:kar kar)
(:kdr kdr)
(:set-kar (setf kar new))
(:set-kdr (setf kdr new)))))
(defun kar (kons)
(funcall kons ':kar))
(defun kdr (kons)
(funcall kons ':kdr))
(defun (setf kar) (new kons)
(funcall kons ':set-kar new))
(defun (setf kdr) (new kons)
(funcall kons ':set-kdr new))
So they don't need to be primitive, really.
--tim
In article <···············@lostwithiel.tfeb.org> Tim Bradshaw writes:
[...]
(defun kons (kar kdr)
#'(lambda (op &optional new)
(ecase op
(:kar kar)
(:kdr kdr)
(:set-kar (setf kar new))
(:set-kdr (setf kdr new)))))
(defun kar (kons)
(funcall kons ':kar))
[...]
So they don't need to be primitive, really.
For immutable conses (no setters), I'd prefer the procedural
implementation given somewhere in SICP, i.e. Abelson/Sussman:
Structure_and_Interpretation_of_Computer_Programs:
(define (kons x y)
(lambda (p) (p x y)))
(define (kar pair)
(pair (lambda (x y) x)))
Aah, that lambda appeal!
rthappe
·······@leonce.mathematik.uni-freiburg.de (Rolf-Thomas Happe) writes:
> In article <···············@lostwithiel.tfeb.org> Tim Bradshaw writes:
> [...]
> (defun kons (kar kdr)
> #'(lambda (op &optional new)
> (ecase op
> (:kar kar)
> (:kdr kdr)
> (:set-kar (setf kar new))
> (:set-kdr (setf kdr new)))))
>
> (defun kar (kons)
> (funcall kons ':kar))
> [...]
> So they don't need to be primitive, really.
>
> For immutable conses (no setters), I'd prefer the procedural
> implementation (...)
Tim's Bradshaw is essentially the same, except he has to use FUNCALL
and provides for modification.
In article <··············@pc-hrvoje.srce.hr> Hrvoje Niksic writes:
·······@leonce.mathematik.uni-freiburg.de (Rolf-Thomas Happe) writes:
> For immutable conses (no setters), I'd prefer the procedural
> implementation (...)
Tim's Bradshaw is essentially the same, except he has to use FUNCALL
and provides for modification.
Hm, to me the message passing implementation and the one I cited
differ -- perhaps not essentially, but vastly with respect to
lambda appeal. Compare
(define (kar kons) (define (kar pair)
(kons ':kar)) (pair (lambda (x y) x)))
Note that the right way (I refer to the right hand side above, of
course) doesn't require anything but functions.
rthappe
·······@leonce.mathematik.uni-freiburg.de (Rolf-Thomas Happe) writes:
> Note that the right way (I refer to the right hand side above, of
> course) doesn't require anything but functions.
Of course, in practice, a function might take up a lot more space
than a symbol. Or it might not. Depends on the implementation.
But I find statements like this odd ("doesn't require anything
but functions") since they presuppose a preference for an item
of unspecified cost at the core. Sort of the "let them eat cake"
approach to computation.
It isn't obvious to me that "one function plus one symbol" is better
than "two functions" given that the system already really does have to
support both functions and symbols.
In article <···············@world.std.com>,
Kent M Pitman <······@world.std.com> wrote:
> ·······@leonce.mathematik.uni-freiburg.de (Rolf-Thomas Happe) writes:
>
> > Note that the right way (I refer to the right hand side above, of
> > course) doesn't require anything but functions.
>
> Of course, in practice, a function might take up a lot more space
> than a symbol. Or it might not. Depends on the implementation.
> But I find statements like this odd ("doesn't require anything
> but functions") since they presuppose a preference for an item
> of unspecified cost at the core. Sort of the "let them eat cake"
> approach to computation.
>
> It isn't obvious to me that "one function plus one symbol" is better
> than "two functions" given that the system already really does have to
> support both functions and symbols.
I pondered that one too.
I understood `better' on that particular occasion to mean `can be done
in lambda calculus' which has functions but does not have symbols.
I don't feel competent enough to say if this is a good meaning for
`better.'
(So, `there are no symbols? Let them eat lambdas...')
--
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
LEGEMANVALEMFVTVTVM (Ancient Roman programmers' adage.)
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
In article <···············@world.std.com> Kent M Pitman writes:
Of course, in practice, a function might take up a lot more space
than a symbol. Or it might not. Depends on the implementation.
But I find statements like this odd ("doesn't require anything
but functions") since they presuppose a preference for an item
of unspecified cost at the core. Sort of the "let them eat cake"
approach to computation.
It isn't obvious to me that "one function plus one symbol" is better
than "two functions" given that the system already really does have to
support both functions and symbols.
Well, practice ... Reality tends to be wet, sticky, and vulgar.
I'm not into practice here, I'm -- I'm on the quest for the spirit
of lambda, the holy bone.
The message passing implementation of CONS sets up some
procedures, some procedure ids (accidentally symbols), and relates
them in an arbitrary way. In the functional (procedure passing)
implementation you pass the procedures themselves, not proc ids.
In my mind, the functional implementation is more beautiful,
mathematically.
rthappe
PS: My description of the message passing KONS doesn't fit 100% with
Tim Bradshaw's code. So I'm going to torture the code a little.
See below, and please bear with the Scheme here in comp.lang.lisp.
It's convenient for this sort of unpractical things, and I have no
CL system at hand for testing. I messed things up a little by
adding setters.
;; procedure passing
(define (kons x y)
(lambda (access old->new)
(call-with-values
(lambda () (old->new x y))
(lambda (new-x new-y)
(set! x new-x)
(set! y new-y)))
(access x y)))
(define (kar pair)
(pair (lambda (x y) x) ; 1
(lambda (x y) (values x y))))
(define (set-kar! pair new-x)
(pair (lambda (x y) x) ; 3
(lambda (x y) (values new-x y)))) ; 4
;; contorted message passing
(define (kons x y)
(lambda (message . z)
(case message
((kar) ((lambda (x y) x) x y)) ; 1
((set-kar!) (call-with-values
(lambda ()
(call-with-values
(lambda () (values x y))
(lambda (x y) (values (car z) y)))) ; 4
(lambda (new-x new-y)
(set! x new-x)
(set! y new-y)))
((lambda (x y) x) x y))))) ; 3
(define (kar pair) (pair 'kar))
(define (set-kar! pair x) (pair 'set-kar! x))
·······@leonce.mathematik.uni-freiburg.de (Rolf-Thomas Happe) writes:
> I'm not into practice here, I'm -- I'm on the quest for the spirit
> of lambda, the holy bone.
Well, there's nothing wrong with that, of course, but I will observe
that one of the principal differences between CL and Scheme (other
than myriad differences in syntax and semantics) is that Scheme is
politically a lot about having the perfect language, and CL very
specifically trades off having the perfect language for having
something practical. One could very well ask why Scheme has CAR/CDR,
but in Common Lisp the answer is much easier: because someone put it
there and people use it and it would be disruptive not to have it.
From the X3J13 charter:
Whenever there is a proposal for the standard to differ from
Common Lisp: The Language, the committee shall weigh both
future costs of adopting (or not adopting) a change and costs
of conversion of existing code. Aesthetic criteria shall be
a subordinate consideration.
I finally got this document online, since I like to refer to it a lot.
http://world.std.com/~pitman/CL/x3j13-86-020.html
> The message passing implementation of CONS sets up some
> procedures, some procedure ids (accidentally symbols), and relates
> them in an arbitrary way. In the functional (procedure passing)
> implementation you pass the procedures themselves, not proc ids.
> In my mind, the functional implementation is more beautiful,
> mathematically.
This is a fine end, but you should understand that it is a "domain
application" and not, historically, a "design criterion" for Lisp.
You will confuse others if you ask questions of the form "why did
you do this as ..." rather than "how can I do this as ..." unless
you are prepared to receive non-purist, non-mathy answers.
Of course, nothing keeps you personally from ignoring the non-mathy
parts of the language.
Incidentally, the T dialect of Scheme from Yale years ago, which I
had some early involvement in, began from the kind of design basis
that you're looking at. Indeed, it had a message-passing system
based on functions. It didn't case on symbols, though, it cased on
the message passing functions themselves. So if you did:
(define-operation foo)
you could handle operation FOO but someone in another environment could
do
(define bar foo)
and then use the (bar x) everywhere, including in defining its own
message handlers. The method itself did
(define foo
(let ((foo nil))
(set! foo #'(lambda (what &rest args)
(apply internal-send what foo args)))))
so that renaming it was harmless. It was closed over itself.
and used its own object-identity as the message. Case dispatch
did
(cond ((eq? message foo) ...) ...etc.)
rather than
(cond ((eq? message 'foo) ...) ...etc.)
Originally we bootstrapped the system with symbols and then one day removed
all the quotes. It was very weird that it still worked. (Well, we might
have had to make one or two other changes at the same time--might not have
been as easy as removing quoes, but it was close...)
T had better syntax than some of that I've used above. I tried to use
a mix of modern CL and Scheme to make it more readable by this community
of readers, but T had nice macros that made this all a good deal
prettier.
In article <···············@world.std.com> Kent M Pitman writes:
[...]
> In my mind, the functional implementation is more beautiful,
> mathematically.
This is a fine end, but you should understand that it is a "domain
application" and not, historically, a "design criterion" for Lisp.
Sure. I don't mean to imply that Lisp should ascend into Platonic
heaven, leaving behind the sublunar worries of storage bounds, code
maintainability, exacerbated sales managers, etc. etc.
You will confuse others if you ask questions of the form "why did
you do this as ..." rather than "how can I do this as ..." unless
Usually the "send" function of my news reader not only posts the
article, but it doesn't fail to raise some doubts (on my part) with
respect to the wording/presentation I chose.
Incidentally, the T dialect of Scheme from Yale years ago, which I
had some early involvement in, began from the kind of design basis
that you're looking at. Indeed, it had a message-passing system
based on functions. It didn't case on symbols, though, it cased on
the message passing functions themselves. So if you did:
This is interesting, but if I may switch back in my math mode:
functions like it better to be called rather than compared.
rthappe
From: Howard R. Stearns
Subject: unaddressed X3J13 issues? (Re: How are car/cdr implemented?)
Date:
Message-ID: <371CA3C8.484956EA@elwood.com>
Kent M Pitman wrote:
> ...
> I finally got this document online, since I like to refer to it a lot.
> http://world.std.com/~pitman/CL/x3j13-86-020.html ...
Thanks for posting this. I was surprised to see that this charter for
X3J13 says:
"The committee will address at least the following topics..., in each
case either incorporating specific features or explaining why no action
was
taken:
....
(f) Multiprocessing
(g) Graphics
(h) Windows
(i) Validation"
Do you happen to know of any fossil record explaining what was done for
these. For example, was there specific recorded consideration, or just
a blanket statement that "all the above are not yet ready for
standardization." For that matter, is there a record of why FFI and SCT
were left off this list?
(I confess that I haven't done my homework to look through the
archives.)
From: Kent M Pitman
Subject: Re: unaddressed X3J13 issues? (Re: How are car/cdr implemented?)
Date:
Message-ID: <sfw4smbounf.fsf@world.std.com>
"Howard R. Stearns" <······@elwood.com> writes:
> "The committee will address at least the following topics..., in each
> case either incorporating specific features or explaining why no action
> was
> taken:
> ....
> (f) Multiprocessing
> (g) Graphics
> (h) Windows
> (i) Validation"
>
> Do you happen to know of any fossil record explaining what was done for
> these.
I don't have a record, but I can tell you that for f,g,h the answer was
that they were beyond our resources to address in the time permitted by
1988 (feature freeze).
(i) was attempted by someone at ISI but it didn't go anywhere. there was
talk that vendors would pick up the slack but every vendor saw validation
as a big investment they had in their product quality and when it came to
contributing to a public fund, each said to the others "you go first" and
no one did.
> For example, was there specific recorded consideration, or just
> a blanket statement that "all the above are not yet ready for
> standardization."
I believe what you're looking for doesn't exist. No one was going to say
it couldn't be done. If someone had walked in with a proposal, we'd have
looked at it. But no one did. CLIM came along too late, for example.
And no one was happy enough with the things that preceded it.
> For that matter, is there a record of why FFI and SCT
> were left off this list?
Yes for SCT. Feature freeze date passed without it. I proposed it
later and it was rejected as "too late" by people who worried it would
slow down the standard. I pleaded with people saying the process had
enough parallism in it that doing this would not slow me down on the
editing work. They didn't buy it. I said that it wouldn't take any
time to do DEFSYSTEM and that I would cancel dates with my
then-girlfriend just to make sure the time didn't come out of my
already-allocated editing time and they still didn't buy it. I wash my
hand of that.
As to FFI, there was a political split between RPC and FFI at the time such
a proposal might have been done, and so since either answer would have had
one vendor win at another's major retooling expense, I recall this
floundering.
These are just my personal recollections and I could be in error. No slight
on any party is intended. I don't see how to learn from history without
recounting its warts, though. But the problems I recall were very real at
the time.
> (I confess that I haven't done my homework to look through the
> archives.)
I doubt you'd have found anything, except maybe for sct. I can pull the
records on that because there are such if you're terribly curious.
In article <···············@world.std.com>, Kent M Pitman
<······@world.std.com> wrote:
> Incidentally, the T dialect of Scheme from Yale years ago, which I
> had some early involvement in, began from the kind of design basis
> that you're looking at.
As an item of historical interest, at JPL in the late 1980's T was
ported to run under the real-time operating system vxWorks and was
used to write the control software for an autonomous mobile robot
named Robbie. This work led eventually (after a great deal of
munging and indirection) to the Sojourner Mars Rover. But Sojourner
would very likely not have happened if it weren't for T, which really
was a tremendously cool language. It's a shame that T has faded away.
(Likewise for Oaklisp.)
Erann Gat
···@jpl.nasa.gov
From: Paolo Amoroso
Subject: Re: Historical footnote on T (was: Re: How are car/cdr implemented)
Date:
Message-ID: <372070b6.81455@news.mclink.it>
On Wed, 21 Apr 1999 09:04:04 -0800, ···@jpl.nasa.gov (Erann Gat) wrote:
From the ANNOUNCE file included with CLISP:
* About packages running in CLISP:
[...]
New Millenium Space Flight Mission
(They chose Harlequin CL for the space flight, with CLISP as
second-to-best alternative.)
http://www-aig.jpl.nasa.gov/home/gat/home.html
[Erann Gat]
I checked your site, but I wasn't able to find anything directly related to
Common Lisp and its use for New Millennium missions (somewhere else I found
a few papers about Deep Space 1 with unmistakable traces of sexps :-) I'd
love to learn more about it. Is there any publicly available material?
Paolo
--
Paolo Amoroso <·······@mclink.it>
In article <··············@news.mclink.it>, ·······@mclink.it (Paolo
Amoroso) wrote:
> On Wed, 21 Apr 1999 09:04:04 -0800, ···@jpl.nasa.gov (Erann Gat) wrote:
>
> From the ANNOUNCE file included with CLISP:
>
>
> * About packages running in CLISP:
> [...]
> New Millenium Space Flight Mission
> (They chose Harlequin CL for the space flight, with CLISP as
> second-to-best alternative.)
> http://www-aig.jpl.nasa.gov/home/gat/home.html
> [Erann Gat]
>
>
> I checked your site, but I wasn't able to find anything directly related to
> Common Lisp and its use for New Millennium missions (somewhere else I found
> a few papers about Deep Space 1 with unmistakable traces of sexps :-) I'd
> love to learn more about it. Is there any publicly available material?
To my knowledge we haven't published anything about the use of Lisp in space
per se. A custom port of Harlequin Lispworks is going to fly aboard the
DS1 mission (now renamed ST1 - Space Technology 1) next month as part of
the Remote Agent Experiment (RAX). The main obstacle to using Clisp in
this application was its lack of threads. Anything else you want to know
please feel free to contact me directly.
Erann Gat
···@jpl.nasa.gov
In article <··············@leonce.mathematik.uni-freiburg.de>
Rolf-Thomas Happe (myself) writes:
PS: My description of the message passing KONS doesn't fit 100% with
Tim Bradshaw's code. So I'm going to torture the code a little.
[...]
;; contorted message passing
Due to haste or cerebral dysfunction, I added some extra contortion
not called for by my explanatory purpose. Who cares, nonetheless,
here goes
;; contorted message passing, revised edition
(define (kons x y)
(lambda (message z)
(let ((kar-essence (lambda (x y) x))
(set-kar-essence (lambda (x y) (values z y))))
(case message
((kar) (kar-essence x y))
((set-kar!) (call-with-values
(lambda () (set-kar-essence x y))
(lambda (new-x new-y)
(set! x new-x)
(set! y new-y)))
(kar-essence x y))))))
(define (kar pair) (pair 'kar #f))
(define (set-kar! pair x) (pair 'set-kar! x))
The implementation of CAR and CDR depends on the implementation
of CONS, or rather, how you decide to implement a CONS cell.
Perhaps someone will look at the source for CLISP and CMUCL for you,
or you could try doing DISASSEMBLE of functions like (DEFUN FOO (X) (CAR X))
in whatever Lisp you might have around. (I am unfortunately not sitting
in front of a real coputer at the moment or I'd do it.)
It would also be interesting to know what GNU Emacs does.
On the Lisp Machine, of course, there were CAR and CDR machine instructions.
But single-instruction implementation is possible without special hardware.
On the PDP-10 computers, a CONS cell was implemented as a single
word that stored pointers to both halves of the cell, so CAR and CDR
are machine instructions. (The assembler mnemonics were HLRZ and HRRZ.)
Umm, an on older IBM computer, the implementation of CAR and CDR
involved two machine registers. Guess what their names were?
Christopher C Stacy <······@world.std.com> writes:
> The implementation of CAR and CDR depends on the implementation
> of CONS, or rather, how you decide to implement a CONS cell.
>
> Perhaps someone will look at the source for CLISP and CMUCL for you,
> or you could try doing DISASSEMBLE of functions like (DEFUN FOO (X) (CAR X))
> in whatever Lisp you might have around. (I am unfortunately not sitting
> in front of a real coputer at the moment or I'd do it.)
> It would also be interesting to know what GNU Emacs does.
>
> On the Lisp Machine, of course, there were CAR and CDR machine instructions.
> But single-instruction implementation is possible without special hardware.
>
> On the PDP-10 computers, a CONS cell was implemented as a single
> word that stored pointers to both halves of the cell, so CAR and CDR
> are machine instructions. (The assembler mnemonics were HLRZ and HRRZ.)
>
> Umm, an on older IBM computer, the implementation of CAR and CDR
> involved two machine registers. Guess what their names were?
It's possible whoever asked this question originally wanted to know
why it's not left as an exercise to the programmer to do
(defstruct kons kar kdr)
if that's what someone wants. The thing to understand here is that,
at least conceptually, and absent situations in which the compiler can
know enough to block-compile away such information, this leads to a
structure like the following being created by (make-kons :kar 'a :kdr 'b)
Pointer with primitive STRUCTURE-CLASS type-tag
|
| +----------+
+-------------> | |
| ----------> #<Class KONS>
| |
+----------+
| |
| ----------> A
| |
+----------+
| |
| ----------> B
| |
+----------+
That is, an object that takes 3 Q's (pointer-widths) to store.
By contrast, a CONS is only 2 Q's wide because it doesn't have
a block that describes a user-defined class--the class information
is primitive.
Pointer with primitive CONS type-tag
|
| +----------+
+-------------> | |
| ----------> A
| |
+----------+
| |
| ----------> B
| |
+----------+
The "reason" therefore that CAR/CDR are primitive is that
(a) Lisp has a special need to understand the data storage
layout for the sake of the garbage collector and so can't
have you doing what you might otherwise think is totally optimal
user-defined data layout (without making you cooperate with the
type tag scheme so that the GC doesn't get confused)
and (b) conses are sufficiently useful that lispers believe
they are worth the system providing primitively.
Another way of stating the same "reason" is that Lisp trades
off the risk that you might wish you could define a CONS
primitively but can't (without loss of an extra Q
per cons to hold the type pointer) for the safety of knowing
it won't have memory leaks. C on the other hand trades off
the absolute promise that the programmer will just avoid
all memory leaks by careful programming and so is able to
give people access to arbitrary user-defined data structure
at "no cost". I guess it's a matter of perspective which is
the better choice...
Though personally I think Lisp made a good trade. People can
fuss all they like about O(2) vs O(3) being somehow different,
but by many accounts they aren't very much different. On
the other hand, the big-O notation for a "memory leak" is
another matter entirely.
> It's possible whoever asked this question originally wanted to know
> why it's not left as an exercise to the programmer to do
>
> (defstruct kons kar kdr)
>
> if that's what someone wants.
> That is, an object that takes 3 Q's (pointer-widths) to store.
> By contrast, a CONS is only 2 Q's wide because it doesn't have
> a block that describes a user-defined class--the class information
> is primitive.
FYI, Stalin only has structures, and not pairs, as primitives. And it defines
pairs as two element structures precisely as above. Furthermore, structures in
Stalin never have a header. So there is no overhead to representing pairs as
structures.
An advantage is that all optimizations get shared between pairs and
structures. And users can decide which to use on stylistic grounds, rather
than on grounds of efficiency.
Jeff (http://www.neci.nj.nec.com/homepages/qobi)
In article <···············@qobi.nj.nec.com>,
Jeffrey Mark Siskind <····@research.nj.nec.com> wrote:
(...)
> > (defstruct kons kar kdr)
(...)
> > That is, an object that takes 3 Q's (pointer-widths) to store.
> > By contrast, a CONS is only 2 Q's wide because it doesn't have
> > a block that describes a user-defined class--the class information
> > is primitive.
>
> FYI, Stalin only has structures, and not pairs, as primitives. And it defines
> pairs as two element structures precisely as above. Furthermore, structures in
> Stalin never have a header. So there is no overhead to representing pairs as
> structures.
(...)
Could you also tell us how Stalin represents references, tags in
particular, and if there are any possibilities for user-defined
tags?
--
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
LEGEMANVALEMFVTVTVM (Ancient Roman programmers' adage.)
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
> Could you also tell us how Stalin represents references, tags in
> particular, and if there are any possibilities for user-defined
> tags?
Stalin chooses between six different representations on a per-location (i.e.
variable, slot, element, etc.) basis. And it does representation translation
on moves between location with different representations. It strives to
minimize the amount of representation translation.
The six representation are:
fictitious: Here the data is not represented at all. This happens when a
location can hold only one type and that type has only one member.
monomorphic: Here the data has no tag. C representations are used. This happens
when the compiler can prove that a location holds data of only
one type.
tag-only: Here the data consists only of a tag. But no value. The compiler
can be configured to represent the tag as any size C integer: char,
short, int, or long (all unsigned). This happens when a location
can hold values of different types but when the compiler can prove
that all of the types that a location can hold have only a single
member.
squeezed: Here the data consists of only a pointer value. With no tag. This
happens when a location can hold a single pointer type or one of a
finite number of other types all of which have a single member. Like
(union pair null) or (union pair null true false 'a 'b 'c) or even
(union pair char eof-object null true false 'a 'b 'c). The
non-pointer are represented as unusable address.
squished: Here the data consists of only an aligned pointer value. The
low-order bits that arise from the alignment of the pointer are
used to hold the tag. The assignment of tags varies from location to
location. So if you have 2 tag bits (which are a precious comodity)
one location can use them to represent
(union pair vector structure-a structure-b) and another could use
them to represent (union pair string structure-b structure-c).
Fixnums can also be squeezed, loosing some range.
general case: Here the data consists of a struct of a tag and a value. This
is used only when no other representation is suitable.
In practise, the general case is almost never used. Almost all cases where it
is used occur when you have a type (union float ...) or (union double ...).
I'm planning on adding a seventh representation to handle this case:
squashed: Here the data consists of an IEEE floating point number. Non-float
values are represented as NaNs.
Yes, Stalin allows user-defined data types (through defstruct) which have
distinct tags from any other objects. The user can't control the tag
assignment but the objects are unforgeable.
Jeff (http://www.neci.nj.nec.com/homepages/qobi)
In article <···············@world.std.com>,
Kent M Pitman <······@world.std.com> wrote:
>The "reason" therefore that CAR/CDR are primitive is that
>(a) Lisp has a special need to understand the data storage
>layout for the sake of the garbage collector and so can't
>have you doing what you might otherwise think is totally optimal
>user-defined data layout (without making you cooperate with the
>type tag scheme so that the GC doesn't get confused)
>and (b) conses are sufficiently useful that lispers believe
>they are worth the system providing primitively.
Actually, I think the "reason" is mostly historical. Conses predate
DEFSTRUCT by two decades, and some early DEFSTRUCT implementations actually
used conses as the underlying representation.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: Vassil Nikolov
Subject: origin of Q? (Ex: Re: How are car/cdr implemented?)
Date:
Message-ID: <7fa5t6$36c$1@nnrp1.dejanews.com>
In article <···············@world.std.com>,
Kent M Pitman <······@world.std.com> wrote:
(...)
> Q's (pointer-widths)
(...)
May I take this occasion to ask where does Q in this sense
come from?
(`Quad'? (meaning `four octets'))
--
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
LEGEMANVALEMFVTVTVM (Ancient Roman programmers' adage.)
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
From: Kent M Pitman
Subject: Re: origin of Q? (Ex: Re: How are car/cdr implemented?)
Date:
Message-ID: <sfw3e1znvoj.fsf@world.std.com>
Vassil Nikolov <········@poboxes.com> writes:
> In article <···············@world.std.com>,
> Kent M Pitman <······@world.std.com> wrote:
> (...)
> > Q's (pointer-widths)
> (...)
>
> May I take this occasion to ask where does Q in this sense
> come from?
>
> (`Quad'? (meaning `four octets'))
I'm not sure. I'll ask around. I doubt it's octets. I heard it used
a lot around the time of the lisp machine bootstrapping by people who
were comparing storage efficiencies across machine architectures.
Sort of like people used to talk LIPS (logical inferences per second)
rather than instruction speeds (which made no sense as we migrated
from very wide instructions full of options to very narrow ones). And
at that time, there were no "octets"... well, maybe on the VAX, I'm
not sure. Could have come from there. But we had 7bit bytes on the
PDP10 (36 bit word divided into 5 7bit bytes with 1 bit left
over--lots of fun figuring out what to do with that. Some things used
9-bit bytes, but not many.) I don't recall any presupposed byte
structure at all on the lisp machines (which had varying word sizes to
accomodate evolving theories of tagging and how much pointer was
enough); you can use LDB to load a byte, but there are no preferred
byte sizes or counts. In practice, only pointers matter.
Vassil Nikolov wrote:
>
> In article <···············@world.std.com>,
> Kent M Pitman <······@world.std.com> wrote:
> (...)
> > Q's (pointer-widths)
> (...)
>
> May I take this occasion to ask where does Q in this sense
> come from?
>
> (`Quad'? (meaning `four octets'))
I always assumed it was for Quantum; basically a synonym for "word". At
least, that seems to be the way its used. But maybe I'm missing
something.