This is more a difficult topic for me to describe, than it maybe is.
This is more to see if my hypothesis are correct.
Anyway, I got this project here in which I want to simulate a
computer. It is a 32-bit architecture, so I want 32-bit values to
behave as 32-bit digital register values, that is, when overflowing ->
discard the excess bits.
When using CLISP, it seems that I do not get any detection of
overflow. It just goes from (integer 0 16777215) to (integer
(16777215)). So this probably means that I will have to mask my
arithmetic results using #xFFFFFFFF.
However, after everything is set and done, I like to use SBCL to see
how fast I can get a program running. Turning safety off increases in
a speedup of about 100%. If I turn safety off, does this then mean
that no check is executed and that arithmetic functions will
automatically roll over, or is that pushing my luck too far ?
Another thing which is related to my problem is that CLISP
automatically chooses between bit, (integer 0 16777215) and (integer
(16777215)) for the representation of numbers, and that type
declarations on lexical variables are ignored. The types fixnum and
(un)signed-byte do exist, however. Are these only meant for defining
types on arrays and structs ?
Regards,
Jurgen
From: Pascal J. Bourguignon
Subject: Re: Speed/safety trade-offs and types vs. system classes
Date:
Message-ID: <87r61tieqx.fsf@galatea.local>
jurgen_defurne <··············@pandora.be> writes:
> This is more a difficult topic for me to describe, than it maybe is.
> This is more to see if my hypothesis are correct.
>
> Anyway, I got this project here in which I want to simulate a
> computer. It is a 32-bit architecture, so I want 32-bit values to
> behave as 32-bit digital register values, that is, when overflowing ->
> discard the excess bits.
>
> When using CLISP, it seems that I do not get any detection of
> overflow. It just goes from (integer 0 16777215) to (integer
> (16777215)). So this probably means that I will have to mask my
> arithmetic results using #xFFFFFFFF.
Yes. You also need to determine if you work with two-complement,
one-complement or what other way you want to represent signed numbers
modulo 2^p.
And notice that masking with #xFFFFFFFF is not the only thing you will
have to implement arithmetic operations. You will also have to fetch
the data from registers or memory, compute status bits, check whether
an interuption occured, etc.
> However, after everything is set and done, I like to use SBCL to see
> how fast I can get a program running. Turning safety off increases in
> a speedup of about 100%. If I turn safety off, does this then mean
> that no check is executed and that arithmetic functions will
> automatically roll over, or is that pushing my luck too far ?
This is not specific to clisp, all CL implementations have bignums.
The range of FIXNUM may change, but the range of INTEGER is only
limited by the available memory.
> Another thing which is related to my problem is that CLISP
> automatically chooses between bit, (integer 0 16777215) and (integer
> (16777215)) for the representation of numbers, and that type
> declarations on lexical variables are ignored.
That's not so, and again, it is not something specific to clisp.
What is the type of 42?
(every (lambda (type) (typep 42 type))
'( (integer 42 42) (integer 40 44) (integer 30 50) (integer 0 1000)
fixnum integer real number
(signed-byte 7) (signed-byte 9) (signed-byte 10) (signed-byte 73)
(unsigned-byte 6) (unsigned-byte 16) (unsigned-byte 42) (unsigned-byte 5600)
(member :a 'hello 42) (member 101010 42 '|THE-answer|)
;; ...
))
Types are sets and values are elements. When you have a single
element, it may belong to an infinite number of sets, therefore it has
an infinite number of types.
That's why statically typed languages are useless.
> The types fixnum and
> (un)signed-byte do exist, however. Are these only meant for defining
> types on arrays and structs ?
You may specify the type (whatever it is) of element of any array.
The implementation may choose to optimize specially any type of element.
(otherwise it will "upgrade" the array to some encompassing element type,
possibly T).
There are chances that on an implementation running on a 32-bit
computer, (make-array dimensions :element-type '(unsigned-byte 32)
:initial-element 0) be optimized to use one 32-bit word per array
slot. But this doesn't matter at all. What matter, is that your
array will work on any CL implementation, be it running on a 17-bit
eletronic computer, or on banana skins.
--
__Pascal Bourguignon__
On Feb 20, 11:28 am, ····@informatimago.com (Pascal J. Bourguignon)
wrote:
Trying to get more answers by disassembling everyhing piece by piece.
> > Another thing which is related to my problem is that CLISP
> > automatically chooses between bit, (integer 0 16777215) and (integer
> > (16777215)) for the representation of numbers, and that type
> > declarations on lexical variables are ignored.
>
> That's not so, and again, it is not something specific to clisp.
>
> What is the type of 42?
>
> (every (lambda (type) (typep 42 type))
> '( (integer 42 42) (integer 40 44) (integer 30 50) (integer 0 1000)
> fixnum integer real number
> (signed-byte 7) (signed-byte 9) (signed-byte 10) (signed-byte 73)
> (unsigned-byte 6) (unsigned-byte 16) (unsigned-byte 42) (unsigned-byte 5600)
> (member :a 'hello 42) (member 101010 42 '|THE-answer|)
> ;; ...
> ))
>
> Types are sets and values are elements. When you have a single
> element, it may belong to an infinite number of sets, therefore it has
> an infinite number of types.
When I write the next thing, what does it really mean ?
(let
((a 0))
(declare (type (integer 10 12) a))
(setf a 10)
(setf a 13))
I would expect it to mean that a should only hold numbers of fixed
size, with a value between 10 and 12 inclusive. Based upon this
assumption, I would expect the program to throw an exception (or a fit
maybe), because I initialise it with zero, or either at the place
where I assign 13 to the variable. However, it returns 13, which is
correct as far as the pure functionality of the statement goes.
Then what are type declarations in CL really usable for? I would
assume either to impose more correctness and validation upon the
program, which I suppose would be the case in any CL implementation,
or to do possible optimisations, which certainly works with SBCL.
Regards,
Jurgen
From: Tobias C. Rittweiler
Subject: Re: Speed/safety trade-offs and types vs. system classes
Date:
Message-ID: <87r61tjoh1.fsf@freebits.de>
chthon <··············@pandora.be> writes:
> When I write the next thing, what does it really mean ?
>
> (let
> ((a 0))
> (declare (type (integer 10 12) a))
> (setf a 10)
> (setf a 13))
>
> I would expect it to mean that a should only hold numbers of fixed
> size, with a value between 10 and 12 inclusive. Based upon this
> assumption, I would expect the program to throw an exception (or a fit
> maybe), because I initialise it with zero, or either at the place
> where I assign 13 to the variable. However, it returns 13, which is
> correct as far as the pure functionality of the statement goes.
The behaviour of your program is undefined. It depends upon what your
implementation uses type declarations for, and probably on the
optimization settings.
In case of SBCL (and CMUCL), type declarations are taken as assertions
in safe code. So these two implementation do indeed signal an error on
the code snippet above unless safety is 0.
-T.
On Feb 20, 1:13 pm, "Tobias C. Rittweiler" <····@freebits.de.invalid>
wrote:
> chthon <··············@pandora.be> writes:
> > When I write the next thing, what does it really mean ?
>
> > (let
> > ((a 0))
> > (declare (type (integer 10 12) a))
> > (setf a 10)
> > (setf a 13))
>
> > I would expect it to mean that a should only hold numbers of fixed
> > size, with a value between 10 and 12 inclusive. Based upon this
> > assumption, I would expect the program to throw an exception (or a fit
> > maybe), because I initialise it with zero, or either at the place
> > where I assign 13 to the variable. However, it returns 13, which is
> > correct as far as the pure functionality of the statement goes.
>
> The behaviour of your program is undefined. It depends upon what your
> implementation uses type declarations for, and probably on the
> optimization settings.
>
> In case of SBCL (and CMUCL), type declarations are taken as assertions
> in safe code. So these two implementation do indeed signal an error on
> the code snippet above unless safety is 0.
>
> -T.
CLHS : 3.3.1 says : In general, an implementation is free to ignore
declaration specifiers except for the declaration, notinline, safety,
and special declaration specifiers.
So that is what I expect CLISP to do, the implementation notes of
CLISP say it themselves. But this does seem to imply to me that, if
you follow CLHS to the letter and want to write portable code, you
cannot count on any particular implementation to do automatic bounds
checks.
In this case this would mean that one always needs to check for the
bounds of any particular computation, and that using type declarations
in the way that I used to above, and for optimisation, ties one in to
a certain implementation, if one really wants to get the most
performance out of it.
On the other hand, I know that the cost of automatic checks is that
there is the possibility that a program one day may crash upon a bound
error, so in the long term you would either try to prove for yourself
that your program never can do that, so that you can remove or turn
off checking, or always check for the validity of results, in which
case the point of declaring types becomes moot.
Regards,
Jurgen
From: Tobias C. Rittweiler
Subject: Re: Speed/safety trade-offs and types vs. system classes
Date:
Message-ID: <87eixtjlm6.fsf@freebits.de>
chthon <··············@pandora.be> writes:
> But this [CLHS 3.3.1] does seem to imply to me that, if you follow
> CLHS to the letter and want to write portable code, you cannot count
> on any particular implementation to do automatic bounds checks.
Strictly speaking, I think, this is true. I cannot follow you on how you
deduce this from 3.3.1, but it follows from 1.4.4.3. In practise, the
market pretty much requires implementators to do bound checking unless
safety is 0.
-T.
From: Thomas A. Russ
Subject: Re: Speed/safety trade-offs and types vs. system classes
Date:
Message-ID: <ymi3ae8eolo.fsf@blackcat.isi.edu>
chthon <··············@pandora.be> writes:
> When I write the next thing, what does it really mean ?
>
> (let
> ((a 0))
> (declare (type (integer 10 12) a))
> (setf a 10)
> (setf a 13))
>
> I would expect it to mean that a should only hold numbers of fixed
> size, with a value between 10 and 12 inclusive. Based upon this
> assumption, I would expect the program to throw an exception (or a fit
> maybe), because I initialise it with zero, or either at the place
> where I assign 13 to the variable. However, it returns 13, which is
> correct as far as the pure functionality of the statement goes.
>
> Then what are type declarations in CL really usable for? I would
> assume either to impose more correctness and validation upon the
> program, which I suppose would be the case in any CL implementation,
> or to do possible optimisations, which certainly works with SBCL.
The purpose of type declarations in CL is to enable optimization. They
are PROMISES that the programmer makes to the compiler. In other words,
when you say that the variable A will always be an integer between 10
and 12, you are making a promise to the compiler to always assign only
values in that range to A.
But then you break your promise by assigning values (0 and 13) that are
both outside that range. At that point, you have written non-conforming
code and the behavior of the program is undefined. Some implementations
may completely ignore such type declarations, others may trust them
without checking, and yet others may test them as well as trusting
them. Sometimes an implementation will do all of the above, depending
on the settings of the SPEED, SAFETY and DEBUG optimization settings.
The bottom line is that if you make such declarations, you as the
programmer must ensure that they are not violated.
If you wish to make sure that type restrictions are being followed, then
you will need to insert CHECK-TYPE or ASSERT statements into your code.
That is, in fact, the entire purpose of having the CHECK-TYPE construct
in the language.
So, for example if you did
(defun type-test (initial-value new-value)
(let ((a initial-value))
(declare (type (integer 10 12) a))
(check-type a (integer 10 12))
(setf a new-value)
(check-type a (integer 10 12))
a))
you can be sure that the type checks will be honored.
(type-test 10 12) will work
(type-test 3 12) will throw an error
(type-test 10 13) will throw an error
The key thing to remember is that declarations are promises and not
assertions.
On Feb 20, 11:21 pm, ····@sevak.isi.edu (Thomas A. Russ) wrote:
> chthon <··············@pandora.be> writes:
> > When I write the next thing, what does it really mean ?
>
> > (let
> > ((a 0))
> > (declare (type (integer 10 12) a))
> > (setf a 10)
> > (setf a 13))
>
> > I would expect it to mean that a should only hold numbers of fixed
> > size, with a value between 10 and 12 inclusive. Based upon this
> > assumption, I would expect the program to throw an exception (or a fit
> > maybe), because I initialise it with zero, or either at the place
> > where I assign 13 to the variable. However, it returns 13, which is
> > correct as far as the pure functionality of the statement goes.
>
> > Then what are type declarations in CL really usable for? I would
> > assume either to impose more correctness and validation upon the
> > program, which I suppose would be the case in any CL implementation,
> > or to do possible optimisations, which certainly works with SBCL.
>
> The purpose of type declarations in CL is to enable optimization. They
> are PROMISES that the programmer makes to the compiler. In other words,
> when you say that the variable A will always be an integer between 10
> and 12, you are making a promise to the compiler to always assign only
> values in that range to A.
>
> But then you break your promise by assigning values (0 and 13) that are
> both outside that range. At that point, you have written non-conforming
> code and the behavior of the program is undefined. Some implementations
> may completely ignore such type declarations, others may trust them
> without checking, and yet others may test them as well as trusting
> them. Sometimes an implementation will do all of the above, depending
> on the settings of the SPEED, SAFETY and DEBUG optimization settings.
>
> The bottom line is that if you make such declarations, you as the
> programmer must ensure that they are not violated.
>
> If you wish to make sure that type restrictions are being followed, then
> you will need to insert CHECK-TYPE or ASSERT statements into your code.
> That is, in fact, the entire purpose of having the CHECK-TYPE construct
> in the language.
>
> So, for example if you did
>
> (defun type-test (initial-value new-value)
> (let ((a initial-value))
> (declare (type (integer 10 12) a))
> (check-type a (integer 10 12))
> (setf a new-value)
> (check-type a (integer 10 12))
> a))
>
> you can be sure that the type checks will be honored.
>
> (type-test 10 12) will work
> (type-test 3 12) will throw an error
> (type-test 10 13) will throw an error
>
> The key thing to remember is that declarations are promises and not
> assertions.
Well now, an answer like this is the type of answer I like to get from
this newsgroup. Clear and understandable, and removing all wrong
preconceptions, gotten by years of programming in procedural
programming languages.
Many thanks,
Jurgen
On Feb 20, 11:28 am, ····@informatimago.com (Pascal J. Bourguignon)
wrote:
> > However, after everything is set and done, I like to use SBCL to see
> > how fast I can get a program running. Turning safety off increases in
> > a speedup of about 100%. If I turn safety off, does this then mean
> > that no check is executed and that arithmetic functions will
> > automatically roll over, or is that pushing my luck too far ?
>
> This is not specific to clisp, all CL implementations have bignums.
> The range of FIXNUM may change, but the range of INTEGER is only
> limited by the available memory.
>
The thing I was trying to get at is this. Suppose the following code :
(let
((reg 0))
(declare
(optimize (speed 3) (safety 0))
(type (unsigned-byte 8) reg))
and I put #xFF into reg, then increment it, that I get #x00 as a
result, and not #x100 with an upgrade of reg to something larger then
(unsigned-byte 8), and no traps or errors either.
Regards,
Jurgen
From: Tobias C. Rittweiler
Subject: Re: Speed/safety trade-offs and types vs. system classes
Date:
Message-ID: <87mychjo66.fsf@freebits.de>
chthon <··············@pandora.be> writes:
> ... and I put #xFF into reg, then increment it, that I get #x00 as a
> result, and not #x100 with an upgrade of reg to something larger then
> (unsigned-byte 8), and no traps or errors either.
Use something like
(defun +mod8 (x y)
(declare (type (unsigned-byte 8) x y))
(declare (optimize (speed 3) (safety 0)))
(logand #xFF (+ x y)))
On SBCL, compiling down to
; disassembly for +MOD8
; 0BBDD7B2: 01FA ADD EDX, EDI
; B4: 81E2FC030000 AND EDX, 1020
; BA: 8D65F8 LEA ESP, [EBP-8]
; BD: F8 CLC
; BE: 8B6DFC MOV EBP, [EBP-4]
; C1: C20400 RET 4
-T.
On Feb 20, 1:19 pm, "Tobias C. Rittweiler" <····@freebits.de.invalid>
wrote:
> chthon <··············@pandora.be> writes:
> > ... and I put #xFF into reg, then increment it, that I get #x00 as a
> > result, and not #x100 with an upgrade of reg to something larger then
> > (unsigned-byte 8), and no traps or errors either.
>
> Use something like
>
> (defun +mod8 (x y)
> (declare (type (unsigned-byte 8) x y))
> (declare (optimize (speed 3) (safety 0)))
> (logand #xFF (+ x y)))
>
> On SBCL, compiling down to
>
> ; disassembly for +MOD8
> ; 0BBDD7B2: 01FA ADD EDX, EDI
> ; B4: 81E2FC030000 AND EDX, 1020
> ; BA: 8D65F8 LEA ESP, [EBP-8]
> ; BD: F8 CLC
> ; BE: 8B6DFC MOV EBP, [EBP-4]
> ; C1: C20400 RET 4
>
> -T.
Well, I used this already in a previous project. However, I suffer
from Laziness, so whatever I can make the machine do, I will let the
machine do. Of course, in this case the amount of work I have done to
make sure I can be Lazy, has probably already offset my Laziness.
Regards,
Jurgen
From: Thomas A. Russ
Subject: Re: Speed/safety trade-offs and types vs. system classes
Date:
Message-ID: <ymiy6w0d9ds.fsf@blackcat.isi.edu>
chthon <··············@pandora.be> writes:
> On Feb 20, 1:19��pm, "Tobias C. Rittweiler" <····@freebits.de.invalid>
> wrote:
> > chthon <··············@pandora.be> writes:
> > > ... and I put #xFF into reg, then increment it, that I get #x00 as a
> > > result, and not #x100 with an upgrade of reg to something larger then
> > > (unsigned-byte 8), and no traps or errors either.
You cannot get this automatically through declarations in Common Lisp.
It is not defined behavior, and so you can't count on it.
You may be able to have this occur for certain implementations, but that
really makes it highly implementation-dependent (and also subject to
change in newer releases of the implementation as well. Since it isn't
covered by the standard, it doesn't have to be kept the same either).
> > Use something like
> >
> > � (defun +mod8 (x y)
> > (type (unsigned-byte 8) x y))
> > � � (declare (optimize (speed 3) (safety 0)))
> > � � (logand #xFF (+ x y)))
> >
>
> Well, I used this already in a previous project. However, I suffer
> from Laziness, so whatever I can make the machine do, I will let the
> machine do. Of course, in this case the amount of work I have done to
> make sure I can be Lazy, has probably already offset my Laziness.
Well, the really lazy way to do this is to write your own macro to
define these modulus operators. Then you can at least get the
generation of the underlying operations for free. Maybe something like:
(defmacro defmod (operator modulus)
"Create a new binary function named OPERATOR_MODULUS that implements
modular arithmetic."
(check-type modulus integer)
(let ((name (intern (format nil "~S_~D") operator modulus)))
`(defun ,name (x y)
(type (unsigned-byte ,modulus) x y))
� � (declare (optimize (speed 3) (safety 0)))
� � (the (unsigned-byte ,modulus)
(logand ,(1- (expt 2 modulus)) (,operator x y)))))
You might also want to add an FTYPE declaim statement as well.
Then you just need to have
(defmod + 8)
(defmod - 8)
(defmod * 16)
etc.
--
Thomas A. Russ, USC/Information Sciences Institute
On Feb 20, 11:28 am, ····@informatimago.com (Pascal J. Bourguignon)
wrote:
> There are chances that on an implementation running on a 32-bit
> computer, (make-array dimensions :element-type '(unsigned-byte 32)
> :initial-element 0) be optimized to use one 32-bit word per array
> slot. But this doesn't matter at all. What matter, is that your
> array will work on any CL implementation, be it running on a 17-bit
> eletronic computer, or on banana skins.
>
> --
> __Pascal Bourguignon__
Well, I depend on this feature, mostly developing my code on CLISP for
cross-platform development between Linux and Windows, and then testing
my code (with possible optimisations) on SBCL and ECL.
Bu this is the real beauty of CL : that I can effectively develop
something working without regards to data types, but that I can
afterward compile it with SBCL for almost free 10-fold performance (if
one doesn't mind the memory that SBCL takes up in contrast with
CLISP).
Regards,
Jurgen
From: Kaz Kylheku
Subject: Re: Speed/safety trade-offs and types vs. system classes
Date:
Message-ID: <20090227124056.331@gmail.com>
On 2009-02-20, jurgen_defurne <··············@pandora.be> wrote:
> This is more a difficult topic for me to describe, than it maybe is.
> This is more to see if my hypothesis are correct.
>
> Anyway, I got this project here in which I want to simulate a
> computer. It is a 32-bit architecture, so I want 32-bit values to
> behave as 32-bit digital register values, that is, when overflowing ->
> discard the excess bits.
This is not what happens in a computer. Just in some computers.
On MIPS for instance, overflow on addition triggers an exception.
If you want wrapping addition, you have to use ``addu'' instruction,
which means unsigned.
> When using CLISP, it seems that I do not get any detection of
> overflow. It just goes from (integer 0 16777215) to (integer
> (16777215)).
How can you call it overflow, when the mathematically correct result is
computed? :)
> So this probably means that I will have to mask my
> arithmetic results using #xFFFFFFFF.
If you want arithmetic modulo (expt 2 32) then you can use mod.
(defconstant %32bits% (expt 2 32))
(mod (+ a b) %32bits%)
> However, after everything is set and done, I like to use SBCL to see
> how fast I can get a program running. Turning safety off increases in
> a speedup of about 100%. If I turn safety off, does this then mean
> that no check is executed and that arithmetic functions will
> automatically roll over, or is that pushing my luck too far ?
You can't portably rely on the Lisp declarations to give you particular
semantics, like arithmetic modulo 32 bits.
If you declare types to be fixnums, and set safety to be zero, it means that if
a calculation on these types exceeds the range of fixnum, the behavior is
undefined. I.e. it's up to the program to ensure that there is no overflow.
Since the behavior isn't defined in the standard, you have to check the
documentation of your Lisp compiler, or at least infer the behavior from its
source code.
Does the SBCL documentation say anywhere that declared fixnums will predictably
wrap on overflow, and that the compiler honors all of the implications arising
from that property?
I.e. if you're using your compiler as though it were ``higher level
assembler'', you should check that such use is actually documented!
See, the problem with overflow is that even if the arithmetic appears to wrap
like you expect it to, the optimizing compiler may make decisions based on the
assumption that the arithmetic doesn't overflow.
For instance suppose you have a loop which terminates when some initially
positive increment variable wraps to zero. The compiler might analyze that loop
and realize that since the variable increments, and is initially positive, it
can never reach zero. The termination test is then optimized to a truth, and
the loop becomes infinite, in spite of the wrapping semantics happening
as expected.