(setq s "toto")
(setf (char s 1) (character "a")) ;; is illegal
(setq s (make-string 4 :initial-element (character "n")))
(setf (char s 1) (character "a")) ;; is legal
How can I distinguish programmatically between the two cases?
((constantp s) of course returns T in both cases, and type-of returns
the same type).
--
__Pascal_Bourguignon__ http://www.informatimago.com/
----------------------------------------------------------------------
Do not adjust your mind, there is a fault in reality.
Pascal Bourguignon <····@thalassa.informatimago.com> writes:
> (setq s "toto")
> (setf (char s 1) (character "a")) ;; is illegal
>
> (setq s (make-string 4 :initial-element (character "n")))
> (setf (char s 1) (character "a")) ;; is legal
>
> How can I distinguish programmatically between the two cases?
You advertise to the caller of a function that you plan to mutate the
string and you ask the caller not to pass inappropriate data.
What makes "toto" immutable is NOT that it can't be mutated; in most
implementations, it can be. What makes it immutable is that if you
mutate it, you will mutate a shared string, which means that other
copies you don't mean to mutate will change, too.
This situation is no different than:
(defun foo () '(toto))
(setq s '(toto))
(rplaca s 'flying-monkey-food) ;illegal
The language in general does not protect you from doing this. You must
protect yourself by not doing the wrong thing.
Neither does the language protect you from this:
(setq s (list 'toto))
(setq r s)
(rplaca s 'flying-monkey-food) ;not illegal, but ill-advised
This "probable programming error" couldn't be tested
for, since in some cases it is right and in some cases it's not.
> ((constantp s) of course returns T in both cases, and type-of returns
> the same type).
CONSTANTP tests whether the object will evaluate to itself.
This is not what you're wanting.
In Maclisp, long ago, there was the notion of data allocated on what was
called a 'pure page' (that is, a read-only page). Accessing such a page
would give you a 'pure page trap'. You could test (though I don't offhand
remember how--maybe a PUREP operation) that an object was allocated thus.
However, we decided in CL not to require that shared objects be pure, partly
because the underlying hardware and/or operating system might not support
this, and partly because the implementation might not do the coalescing that
they are allowed to do, and might want to choose to have other semantics.
It's an implementation flexibility we left, and we didn't want people writing
programs that would detect it and therefore run differently on different
systems. You are to write your programs in a way that makes it not matter.
Which means you cannot correctly call a function without knowing how it plans
to use its argument and without giving it an appropriate argument.
BOTTOM LINE: It is _inherently_ not a testable quantity whether (a) an
object is shared and (b) it is intended that this sharing make any
given side-effect appropriate. You might say this limits your introspective
capability, but I disagree. Unless (a) the language is FULLY introspective
and (b) unless you can, as a result of that fact enumerate ALL data in order
to ascertain total knowledge of the sharing of a given argument, you don't
have even a hope of doing the right thing. Certainly such a test would
not be O(1) cost, which I assume is what Pascal is asking for.
Kent M Pitman <······@world.std.com> writes:
> In Maclisp, long ago, there was the notion of data allocated on what was
> called a 'pure page' (that is, a read-only page). Accessing such a page
> would give you a 'pure page trap'. You could test (though I don't offhand
> remember how--maybe a PUREP operation) that an object was allocated thus.
Allegro CL has this as well, although only on architectures whose signal
handling allows it, and only for strings. For these, we use what we call
a .pll file (a "pure lisp library"), which holds both pure strings and
code-vectors:
CL-USER(1): (pll-file)
#p"/net/quadra/acl/6.2/bin/solaris/acli623.pll"
CL-USER(2): (setf (aref (symbol-name 'car) 0) #\B)
Error: Attempt to store into purespace address #xfa307ae4.
[condition type: SIMPLE-ERROR]
Restart actions (select using :continue):
0: Return to Top Level (an "abort" restart).
1: Abort entirely from this process.
[1] CL-USER(3):
Note however that we don't provide an easy way to check for "purity",
for reasons you describe below.
> However, we decided in CL not to require that shared objects be pure, partly
> because the underlying hardware and/or operating system might not support
> this, and partly because the implementation might not do the coalescing that
> they are allowed to do, and might want to choose to have other semantics.
>
> It's an implementation flexibility we left, and we didn't want people writing
> programs that would detect it and therefore run differently on different
> systems. You are to write your programs in a way that makes it not matter.
> Which means you cannot correctly call a function without knowing how it plans
> to use its argument and without giving it an appropriate argument.
>
> BOTTOM LINE: It is _inherently_ not a testable quantity whether (a) an
> object is shared and (b) it is intended that this sharing make any
> given side-effect appropriate. You might say this limits your introspective
> capability, but I disagree. Unless (a) the language is FULLY introspective
> and (b) unless you can, as a result of that fact enumerate ALL data in order
> to ascertain total knowledge of the sharing of a given argument, you don't
> have even a hope of doing the right thing. Certainly such a test would
> not be O(1) cost, which I assume is what Pascal is asking for.
O(1) cost is possible, but in my opinion much too expensive. Let me
explain:
To identify an individual object as a pure object is sort of a type
issue; a bit could be allocated somewhere in each object that identifies
the object as having been allocated as a literal, or if the type set of the
implementation is less than half full, duplicate types can be allocated. I
would prefer the extra-bit approach, since other type-operations would become
unnecessarily more expensive otherwise, having to dispatch on twice as many
types as before. This bit could be tested by any mutating operators, and
the operation rejected if set.
This would be relatively easy on strings and many other objects - there is
always a bit here or there that is unused which can be used as a pure
bit. At worst case, a tradeoff could be made to steal that bit from
another field, such as a size field.
The problem comes with conses. List structures are more likely to have
their constant-purity violated than any other object with the possible
exception of strings. However, in GP hardware, conses tend to fit
perfectly into a single allocation-unit (i.e. 2 words, each with exactly
one LispVal). In a system where the tag is at the least-significant end,
adding one bit will effectively double the size of the cons, because it
must be aligned to 2-word boundaries. And since conses tend to have their
type information encoded in the tag, another tag value would be needed
in order to identify the cons as pure. This would upset (on machines that
allow alignment-checks) the ability to do car/cdr operations in one
instruction each.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
Duane Rettig <·····@franz.com> writes:
> For these, we use what we call a .pll file (a "pure lisp library"),
Wow, so next time someone comes around asking about Pure Lisp, we can
point them to Allegro? ;-)
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Duane Rettig <·····@franz.com> writes:
> > BOTTOM LINE: It is _inherently_ not a testable quantity whether
> > (a) an object is shared and (b) it is intended that this sharing
> > make any given side-effect appropriate. You might say this limits
> > your introspective capability, but I disagree. Unless (a) the
> > language is FULLY introspective and (b) unless you can, as a
> > result of that fact enumerate ALL data in order to ascertain total
> > knowledge of the sharing of a given argument, you don't have even
> > a hope of doing the right thing. Certainly such a test would not
> > be O(1) cost, which I assume is what Pascal is asking for.
>
> O(1) cost is possible, but in my opinion much too expensive. Let me
> explain: [...]
I didn't mean it wasn't possible to make a pure check O(1), I meant it
wasn't possible to determine if something was shared in such a way that
destruction would not hurt anything in O(1). At minimum, you'd have to
sweep all of memory to even see if there WAS sharing involved (barring
reference counts or some such scheme), and then there's the issue of
sweeping and understanding the memory containing the program to decide
whether the program was going to "mind"... that's subject to the halting
problem.
Kent M Pitman <······@world.std.com> writes:
> Duane Rettig <·····@franz.com> writes:
>
> > > BOTTOM LINE: It is _inherently_ not a testable quantity whether
> > > (a) an object is shared and (b) it is intended that this sharing
> > > make any given side-effect appropriate. You might say this limits
> > > your introspective capability, but I disagree. Unless (a) the
> > > language is FULLY introspective and (b) unless you can, as a
> > > result of that fact enumerate ALL data in order to ascertain total
> > > knowledge of the sharing of a given argument, you don't have even
> > > a hope of doing the right thing. Certainly such a test would not
> > > be O(1) cost, which I assume is what Pascal is asking for.
> >
> > O(1) cost is possible, but in my opinion much too expensive. Let me
> > explain: [...]
>
> I didn't mean it wasn't possible to make a pure check O(1), I meant it
> wasn't possible to determine if something was shared in such a way that
> destruction would not hurt anything in O(1). At minimum, you'd have to
> sweep all of memory to even see if there WAS sharing involved (barring
> reference counts or some such scheme), and then there's the issue of
> sweeping and understanding the memory containing the program to decide
> whether the program was going to "mind"... that's subject to the halting
> problem.
Right. Sharing and immutability overlap, but are not the same. In you
paragraph above you had shifted to talking about sharing from talking
about pure-ness ealier (in my mind an immutability issue more than a
sharing issue [*] ), and I had not made the transition, because I actually
did not know if you were treating them as different. Now I know...
[*] A "pure" space mapping has a prerequisite of being read-only, and
that allows it thus to be shared with other lisps that map the same
purespace, although such sharing is not required. It also allows objects
within the purespace to be looked up, if desired, and used by multiple
parts of the same lisp, thus allowing two kinds of sharing. Allegro CL
takes advantage of this concept, and allows multiple different lisps to
be build with the same .pll file. Thus, you might have 5 differnt lisps
running, whose (symbol-name 'car) consume the same two words in real memory.
We also define a function called pure-string, which, like string, coerces
the argument to a string, but which returns the purified string instead of
a new one, if a pure one is available. Thus, (pure-string "CAR") would
return the same object as (symbol-name 'car).
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
In article <···············@shell01.TheWorld.com>, Kent M Pitman
<······@world.std.com> wrote:
> Unless (a) the language is FULLY introspective
> and (b) unless you can, as a result of that fact enumerate ALL data in order
> to ascertain total knowledge of the sharing of a given argument, you don't
> have even a hope of doing the right thing. Certainly such a test would
> not be O(1) cost, which I assume is what Pascal is asking for.
"No hope" is overstating the case. You could, for example, introduce
immutable counterparts to all the mutable data types. (Actually, I think
all you'd need would be immutable-cons and immutable-vector, which would
cover immutable-string. There would seem to be very little point to
having an immutable-hash-table.)
Of course, this would be a lot of work, and would slow down all mutation
operations (at least when compiled with a high safety optimization).
E.
···@jpl.nasa.gov (Erann Gat) writes:
> In article <···············@shell01.TheWorld.com>, Kent M Pitman
> <······@world.std.com> wrote:
>
> > Unless (a) the language is FULLY introspective
> > and (b) unless you can, as a result of that fact enumerate ALL data in order
> > to ascertain total knowledge of the sharing of a given argument, you don't
> > have even a hope of doing the right thing. Certainly such a test would
> > not be O(1) cost, which I assume is what Pascal is asking for.
>
> "No hope" is overstating the case. You could, for example, introduce
> immutable counterparts to all the mutable data types. (Actually, I think
> all you'd need would be immutable-cons and immutable-vector, which would
> cover immutable-string. There would seem to be very little point to
> having an immutable-hash-table.)
>
> Of course, this would be a lot of work, and would slow down all mutation
> operations (at least when compiled with a high safety optimization).
This would allow you to check for a subset of the things I was talking
about. You still couldn't freely side effect something, though, just
based on such a test, if you didn't know where it came from. All these
tests tell you is whether you're going to get an instantaneous meltdown
by the attempt to change the memory location; they don't tell you whether
the structure was shared and whether changing the structure will affect
other programs that hold onto a shared copy. So no, the structure you
refer to is an interesting one in its own right, but it is not enough.
Kent M Pitman <······@world.std.com> writes:
> It's an implementation flexibility we left, and we didn't want people writing
> programs that would detect it and therefore run differently on different
> systems. You are to write your programs in a way that makes it not matter.
> Which means you cannot correctly call a function without knowing how it plans
> to use its argument and without giving it an appropriate argument.
>
> BOTTOM LINE: It is _inherently_ not a testable quantity whether (a) an
> object is shared and (b) it is intended that this sharing make any
> given side-effect appropriate. You might say this limits your introspective
> capability, but I disagree. Unless (a) the language is FULLY introspective
> and (b) unless you can, as a result of that fact enumerate ALL data in order
> to ascertain total knowledge of the sharing of a given argument, you don't
> have even a hope of doing the right thing. Certainly such a test would
> not be O(1) cost, which I assume is what Pascal is asking for.
Note that I got the problem from the other point of view, that is,
from within a function that get passed a string. Since I want to
memoize the last result, I have to keep that string argument along
with the result. From that point of view, I want to accept both
"literal" strings and variable strings as argument. But I cannot just
keep a reference to the string, because either I could be given
another "literal" string that is equal but not eq by property of the
reader, or I could be given the same string object, but now with a
modified value.
In Objective-C, I would have checked if the string was immutable in
which case I could have kept it as is, otherwise I would have had to
copy it. In Common-Lisp, I must copy it in all cases because I can't
distinguish between both cases. For the comparison, in Objective-C,
the strings check first if they're same (eq) before comparing the
characters (equal). Of course, we can (or (eq a b) (equal a b))
(perhaps equal does it already?), but that's purposeless because the
mandatory copy.
For strings, arrays, conses, O(1) could easily be realized introducing
immutable types. Objects created by the reader would be instances of
these immutable types. (Objective-C compilers instanciate an immutable
class of string literals). Only that the same reader is used to read
data at run time too, not only from the source... So, along with the
considerations of interperter vs. compiler, etc, I understand that
it's not possible.
Thanks,
--
__Pascal_Bourguignon__ http://www.informatimago.com/
----------------------------------------------------------------------
Do not adjust your mind, there is a fault in reality.
Pascal Costanza <········@web.de> writes:
> Pascal Bourguignon wrote:
>
> > Note that I got the problem from the other point of view, that is,
> > from within a function that get passed a string. Since I want to
> > memoize the last result, I have to keep that string argument along
> > with the result. From that point of view, I want to accept both
> > "literal" strings and variable strings as argument. But I cannot just
> > keep a reference to the string, because either I could be given
> > another "literal" string that is equal but not eq by property of the
> > reader, or I could be given the same string object, but now with a
> > modified value.
>
> Just an idea: you could intern the strings you get in a dedicated
> package, and then memoize the results in an eq-hashtable. I guess this
> should lessen the negative impact of copying strings.
I assume that interning a string implies copying it, and later finding
an interned symbol implies hashing the string. The interface of the
function is taking a string only (a pathname namestring), it would be
inconvenient to exchange it for an interned symbol.
But you're right, if the problem was more "query-intensive" (and the
strings "static"), it would be worthwhile exchanging them for symbols.
--
__Pascal_Bourguignon__ http://www.informatimago.com/
----------------------------------------------------------------------
Do not adjust your mind, there is a fault in reality.
"Pascal Bourguignon" <····@thalassa.informatimago.com> wrote in message
···················@thalassa.informatimago.com...
>
> (setq s "toto")
> (setf (char s 1) (character "a")) ;; is illegal
>
> (setq s (make-string 4 :initial-element (character "n")))
> (setf (char s 1) (character "a")) ;; is legal
>
> How can I distinguish programmatically between the two cases?
I don't know.
> ((constantp s) of course returns T in both cases, and type-of returns
> the same type).
I would advise adhering to the convention of using +S+ rather than just S if
it is intended to be a constant and organize your code accordingly. If you
truly can not know where the string came from in the code you are writing
and you must mutate it rather than use a new string it suggests to me a
design flaw.
--
Coby Beck
(remove #\Space "coby 101 @ bigpond . com")
"Coby Beck" <·····@mercury.bc.ca> writes:
> "Pascal Bourguignon" <····@thalassa.informatimago.com> wrote in message
> ···················@thalassa.informatimago.com...
> >
> > (setq s "toto")
> > (setf (char s 1) (character "a")) ;; is illegal
> >
> > (setq s (make-string 4 :initial-element (character "n")))
> > (setf (char s 1) (character "a")) ;; is legal
> >
> > How can I distinguish programmatically between the two cases?
>
> I don't know.
>
> > ((constantp s) of course returns T in both cases, and type-of returns
> > the same type).
>
> I would advise adhering to the convention of using +S+ rather than just S if
> it is intended to be a constant and organize your code accordingly. If you
> truly can not know where the string came from in the code you are writing
> and you must mutate it rather than use a new string it suggests to me a
> design flaw.
Obviously, the problem does not appear when writting these simple two
lines. LISP is call-by-value, not call-by-name. So naming it +S+
does not change anything once it's passed to a function.
It's more like:
(defun some-library-function (a-string)
(declare (type 'string a-string))
(setf (char a-string 0) (character "X")))
;; one kilometer farther:
(some-library-function "toto")
Or worse:
(defun some-library-function (a-string)
(declare (type 'string a-string))
(if (eq a-string (car *slf-cache*))
(cdr *slf-cache*)
(let ((res (some-heavy-computation a-string)))
(setq *slf-cache* (cons a-string res))
res)))
;; and some kilometers later:
(setq s (make-string 4 :initial-element (character "n")))
(some-library-function s)
(setf (char s 0) (character "X"))
(some-library-function s)
--
__Pascal_Bourguignon__ http://www.informatimago.com/
----------------------------------------------------------------------
Do not adjust your mind, there is a fault in reality.
Pascal Bourguignon wrote:
> "Coby Beck" <·····@mercury.bc.ca> writes:
>
>
>>"Pascal Bourguignon" <····@thalassa.informatimago.com> wrote in message
>>···················@thalassa.informatimago.com...
>>
>>>(setq s "toto")
>>>(setf (char s 1) (character "a")) ;; is illegal
>>>
>>>(setq s (make-string 4 :initial-element (character "n")))
>>>(setf (char s 1) (character "a")) ;; is legal
>>>
>>>How can I distinguish programmatically between the two cases?
>>
>>I don't know.
>>
>>
>>>((constantp s) of course returns T in both cases, and type-of returns
>>>the same type).
>>
>>I would advise adhering to the convention of using +S+ rather than just S if
>>it is intended to be a constant and organize your code accordingly. If you
>>truly can not know where the string came from in the code you are writing
>>and you must mutate it rather than use a new string it suggests to me a
>>design flaw.
>
>
> Obviously, the problem does not appear when writting these simple two
> lines. LISP is call-by-value, not call-by-name. So naming it +S+
> does not change anything once it's passed to a function.
>
> It's more like:
>
> (defun some-library-function (a-string)
> (declare (type 'string a-string))
> (setf (char a-string 0) (character "X")))
But there is another naming convention to identify destructive
functions, in which case one would have to be coding:
(nstring-something +s+)
Not good. I haven't thought about this enough to be sure, but offhand it
does seem strange that a constant string could come in harm's way in
well-written code.
--
kenny tilton
clinisys, inc
http://www.tilton-technology.com/
---------------------------------------------------------------
"Everything is a cell." -- Alan Kay
On 10 Jun 2003 05:08:22 +0200, Pascal Bourguignon wrote:
> (setq s "toto")
> (setf (char s 1) (character "a")) ;; is illegal
> (setq s (make-string 4 :initial-element (character "n")))
> (setf (char s 1) (character "a")) ;; is legal
> How can I distinguish programmatically between the two cases?
You can't. The only difference is when the strings are allocated.
--
When C++ is your hammer, everything looks like a thumb.
-- Steven M. Haflich
(setq reply-to
(concatenate 'string "Paul Foley " "<mycroft" '(··@) "actrix.gen.nz>"))
Paul Foley <·······@actrix.gen.nz> writes:
> On 10 Jun 2003 05:08:22 +0200, Pascal Bourguignon wrote:
>
> > (setq s "toto")
> > (setf (char s 1) (character "a")) ;; is illegal
>
> > (setq s (make-string 4 :initial-element (character "n")))
> > (setf (char s 1) (character "a")) ;; is legal
>
> > How can I distinguish programmatically between the two cases?
>
> You can't. The only difference is when the strings are allocated.
So, that means that we have to copy a lot more strings that would have
been necessary, and to use a lot more equal instead of eq.
And note that a simple 'n' prefix convention is not enough: you may
have to copy the string because you want to keep the value it has now,
or you may have to copy it because you want to be able to change it.
--
__Pascal_Bourguignon__ http://www.informatimago.com/
----------------------------------------------------------------------
Do not adjust your mind, there is a fault in reality.
On Tue, Jun 10, 2003 at 09:32:19AM +0200, Pascal Bourguignon wrote:
> So, that means that we have to copy a lot more strings that would have
> been necessary, and to use a lot more equal instead of eq.
It is important to specify in an interface whether the objects which are
passed as parameters will be modified, or not. If it is so, then it is
the responsibility of the interface user to ensure that mutable objects
are supplied. If it is not so, then it is the responsibility of the
implementation programmer not to modify the parameter objects.
This is an issue in every language that permits mutation of objects.
In Lisp there is the convenience of being able to quickly manipulate
objects in the REPL. An interface designed for such use should
naturally take into account what a typical user might use as parameters.
--
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
"Pascal Bourguignon" <····@thalassa.informatimago.com> wrote in message
···················@thalassa.informatimago.com...
>
> So, that means that we have to copy a lot more strings that would have
> been necessary, and to use a lot more equal instead of eq.
>
If you want things like immutable strings you could get quite far using uninterned
symbols. Then you will know that they are not mutable strings,
as they are strings at all. Also symbols satisfy many of the string functions.
CL-USER 11 > (setf s (make-symbol "toto"))
#:|toto|
CL-USER 12 > (setf (char s 1) #\a)
Error: #:|toto| is not of type STRING.
1 (abort) Return to level 0.
2 Return to top loop level 0.
Type :b for backtrace, :c <option number> to proceed, or :? for other options
CL-USER 13 : 1 >
CL-USER 15 > (string s)
"toto"
CL-USER 16 > (string "toto")
"toto"
CL-USER 17 > (string= s "toto")
4
Wade
In article <·······················@news0.telusplanet.net>, "Wade
Humeniuk" <····@nospam.nowhere> wrote:
> "Pascal Bourguignon" <····@thalassa.informatimago.com> wrote in message
> ···················@thalassa.informatimago.com...
> >
> > So, that means that we have to copy a lot more strings that would have
> > been necessary, and to use a lot more equal instead of eq.
> >
>
> If you want things like immutable strings you could get quite far using
uninterned
> symbols. Then you will know that they are not mutable strings,
> as they are strings at all. Also symbols satisfy many of the string
functions.
>
> CL-USER 11 > (setf s (make-symbol "toto"))
> #:|toto|
>
> CL-USER 12 > (setf (char s 1) #\a)
>
> Error: #:|toto| is not of type STRING.
> 1 (abort) Return to level 0.
> 2 Return to top loop level 0.
>
> Type :b for backtrace, :c <option number> to proceed, or :? for other options
>
> CL-USER 13 : 1 >
>
> CL-USER 15 > (string s)
> "toto"
>
> CL-USER 16 > (string "toto")
> "toto"
>
> CL-USER 17 > (string= s "toto")
> 4
>
> Wade
But beware. This can still be undermined by someone with a sufficiently
twisted mind:
? (setf x '#:foo)
#:FOO
? (setf (char (symbol-name x) 0) #\B)
#\B
? x
#:BOO
?
Hm, this is interesting:
? (setf x 'foo)
FOO
? (setf (char (symbol-name x) 0) #\B)
#\B
? x
#|symbol not found in home package!!|#COMMON-LISP-USER::BOO
?
Hm. I think it's time to reboot now.
E.