source: project/wiki/eggref/5/srfi-143 @ 39301

Last change on this file since 39301 was 39301, checked in by gnosis, 2 months ago

Initial revision of SRFI-143 documentation

File size: 10.2 KB
Line 
1== SRFI 143: Fixnums
2=== Abstract
3This SRFI describes arithmetic procedures applicable to a limited range of exact integers only. These procedures are semantically similar to the corresponding generic-arithmetic procedures, but allow more efficient implementations.
4
5For more information see: [[https://srfi.schemers.org/srfi-141/|SRFI 143: Fixnums]]
6=== Rationale
7It is common for Schemes that support arbitrarily large exact integers to have two different representations: one for smaller integers (in absolute value) and one for the rest. These are colloquially known as fixnums and bignums respectively. Because the maximum size of a fixnum is typically smaller than the size of a machine word, fixnums can be represented more compactly and operated on more efficiently than bignums.
8
9Specific procedures for fixnum arithmetic are already supported by many Scheme systems. Standardizing fixnum arithmetic increases the portability of code that uses it. Standardizing the range of fixnums would make fixnum operations inefficient on some systems, which would defeat their purpose. Therefore, this SRFI specifies some of the semantics of fixnum operations, but makes the range of fixnums implementation-dependent.
10
11This SRFI is a modest extension of the [[http://www.r6rs.org/final/html/r6rs-lib/r6rs-lib-Z-H-12.html#node_sec_11.2|R6RS (rnrs arithmetic fixnum)]] library, with some procedures renamed for consistency with R7RS-small. New procedures include {{fxneg}}, {{fxabs}}, {{fxsquare}}, and {{fxsqrt}}.
12
13Existing implementations employ different implementation strategies for fixnum procedures. Some implement the model specified by R6RS (overflows cause exceptions), some implement modular arithmetic (overflows "wrap around"), and others fail catastrophically. In programs that use fixnums instead of generic arithmetic, overflows are typically programming mistakes.
14=== Specification
15Fixnums are an implementation-defined subset of the exact integers. Every implementation of this SRFI must define its fixnum range as a closed interval {{[-2^w-1, 2^w-1-1]}}, where {{w}} is an integer greater than or equal to 24. Every mathematical integer within an implementation's fixnum range must correspond to an exact integer that is representable within the implementation. A fixnum is an exact integer whose value lies within this fixnum range.
16
17Fixnum operations perform integer arithmetic on their fixnum arguments. If any argument is not a fixnum, or if the mathematical result is not representable as a fixnum, it is an error: this is known as the fixnum rule. In particular, this means that fixnum operations may return a mathematically incorrect fixnum in these situations without raising an error. Consequently, when this SRFI says things like "fx+ is semantically equivalent to +", the phrase "except for the effects of the fixnum rule" is to be understood.
18
19This SRFI uses {{i, j, k}} as parameter names for fixnum arguments. Except as noted, the names of fixnum procedures begin with the letters {{fx}}. In most cases they correspond to an R7RS-small or [[https://srfi.schemers.org/srfi-151/srfi-151.html|SRFI 151]] operation on general integers.
20==== Constants
21
22<constant>fx-width</constant>
23
24Bound to the value {{w}} that specifies the implementation-defined range. (R6RS {{fixnum-width}} is a procedure that always returns this value.)
25
26<constant>fx-greatest</constant>
27
28Bound to the value {{2^w-1-1}}, the largest representable fixnum. (R6RS {{greatest-fixnum}} is a procedure that always returns this value.)
29
30<constant>fx-least</constant>
31
32Bound to the value {{-2^w-1}}, the smallest representable fixnum. (R6RS {{least-fixnum}} is a procedure that always returns this value.)
33==== Predicates
34
35<procedure>(fixnum? obj)</procedure>
36
37Returns {{#t}} if obj is an exact integer within the fixnum range, and {{#f}} otherwise.
38
39<procedure>(fx=? i ...)</procedure>
40
41Semantically equivalent to {{=}}.
42
43<procedure>(fx<? i ...)</procedure>
44
45Semantically equivalent to {{<}}.
46
47<procedure>(fx>? i ...)</procedure>
48
49Semantically equivalent to {{>}}.
50
51<procedure>(fx<=? i ...)</procedure>
52
53Semantically equivalent to {{<=}}.
54
55<procedure>(fx>=? i ...)</procedure>
56
57Semantically equivalent to {{>=}}.
58
59<procedure>(fxzero? i)</procedure>
60
61Semantically equivalent to {{zero?}}.
62
63<procedure>(fxpositive? i)</procedure>
64
65Semantically equivalent to {{positive?}}.
66
67<procedure>(fxnegative? i)</procedure>
68
69Semantically equivalent to {{negative?}}.
70
71<procedure>(fxodd? i)</procedure>
72
73Semantically equivalent to {{odd?}}.
74
75<procedure>(fxeven? i)</procedure>
76
77Semantically equivalent to {{even?}}.
78
79<procedure>(fxmax i j ...)</procedure>
80
81Semantically equivalent to {{max}}.
82
83<procedure>(fxmin i j ...)</procedure>
84
85Semantically equivalent to {{min}}.
86==== Basic arithmetic
87
88<procedure>(fx+ i j)</procedure>
89
90Semantically equivalent to {{+}}, but accepts exactly two arguments.
91
92<procedure>(fx- i j)</procedure>
93
94Semantically equivalent to {{-}}, but accepts exactly two arguments.
95
96<procedure>(fxneg i)</procedure>
97
98Semantically equivalent to {{-}}, but accepts exactly one argument.
99
100<procedure>(fx* i j)</procedure>
101
102Semantically equivalent to {{*}}, but accepts exactly two arguments.
103
104<procedure>(fxquotient i j)</procedure>
105
106Semantically equivalent to {{quotient}}.
107
108<procedure>(fxremainder i j)</procedure>
109
110Semantically equivalent to {{remainder}}.
111
112<procedure>(fxabs i)</procedure>
113
114Semantically equivalent to {{abs}}. In accordance with the fixnum rule, has undefined results when applied to {{fx-least}}.
115
116<procedure>(fxsquare i)</procedure>
117
118Semantically equivalent to {{square}}.
119
120<procedure>(fxsqrt i)</procedure>
121
122Semantically equivalent to {{exact-integer-sqrt}} (not {{sqrt}}).
123==== Arithmetic with carry
124<procedure>(fx+/carry i j k)</procedure>
125
126Returns the two fixnum results of the following computation:
127
128<enscript highlight="scheme">
129(let*-values (((s) (+ i j k))
130       ((q r) (balanced/ s (expt 2 fx-width))))
131  (values r q))
132</enscript>
133
134<procedure>(fx-/carry i j k)</procedure>
135
136Returns the two fixnum results of the following computation:
137
138<enscript highlight="scheme">
139(let*-values (((d) (- i j k))
140       ((q r) (balanced/ d (expt 2 fx-width))))
141  (values r q))
142</enscript>
143
144<procedure>(fx*/carry i j k)</procedure>
145
146Returns the two fixnum results of the following computation:
147
148<enscript highlight="scheme">
149(let*-values (((s) (+ (* i j) k))
150       ((q r) (balanced/ s (expt 2 fx-width))))
151  (values r q))
152</enscript>
153
154The balanced/ procedure is available in [[https://srfi.schemers.org/srfi-141/srfi-141.html|SRFI 141]], and also in the R6RS base library under the name of div0-and-mod0.
155==== Bitwise operations
156The following procedures are the fixnum counterparts of certain bitwise operations from SRFI 151 and the R6RS (rnrs arithmetic fixnums) library. In case of disagreement, SRFI 151 is preferred. The prefixes bitwise- and integer- are dropped for brevity and compatibility.
157
158<procedure>(fxnot i)</procedure>
159
160Semantically equivalent to {{bitwise-not}}.
161
162<procedure>(fxand i ...)</procedure>
163
164Semantically equivalent to {{bitwise-and}}.
165
166<procedure>(fxior i ...)</procedure>
167
168Semantically equivalent to {{bitwise-ior}}.
169
170<procedure>(fxxor i ...)</procedure>
171
172Semantically equivalent to {{bitwise-xor}}.
173
174<procedure>(fxarithmetic-shift i count)</procedure>
175
176Semantically equivalent to {{arithmetic-shift}}, except that it is an error for the absolute value of count to exceed {{w-1}}.
177
178<procedure>(fxarithmetic-shift-left i count)</procedure>
179
180The same as {{fxarithmetic-shift}} except that a negative value of count is an error. This is provided for additional efficiency.
181
182<procedure>(fxarithmetic-shift-right i count)</procedure>
183
184The same as {{fxarithmetic-shift}} except that a non-negative value of count specifies the number of bits to shift right, and a negative value is an error. This is provided for additional efficiency.
185
186<procedure>(fxbit-count i)</procedure>
187
188Semantically equivalent to SRFI 151 {{bit-count}}.
189
190<procedure>(fxlength i)</procedure>
191
192Semantically equivalent to {{integer-length}}.
193
194<procedure>(fxif mask i j)</procedure>
195
196Semantically equivalent to {{bitwise-if}}. It can be implemented as {{(fxior (fxand mask i) (fxand (fxnot mask) j))}}).
197
198<procedure>(fxbit-set? index i)</procedure>
199
200Semantically equivalent to SRFI 151 {{bit-set?}}, except that it is an error for index to be larger than or equal to {{fx-width}}.
201
202<procedure>(fxcopy-bit index i boolean)</procedure>
203
204Semantically equivalent to SRFI 151 {{copy-bit}}, except that it is an error for index to be larger than or equal to {{fx-width}}.
205
206<procedure>(fxfirst-set-bit i)</procedure>
207
208Semantically equivalent to {{first-set-bit}}.
209
210<procedure>(fxbit-field i start end)</procedure>
211
212Semantically equivalent to {{bit-field}}.
213
214<procedure>(fxbit-field-rotate {{i}} count start end)</procedure>
215
216Semantically equivalent to SRFI 151 {{bit-field-rotate}}.
217
218<procedure>(fxbit-field-reverse i start end)</procedure>
219
220Semantically equivalent to {{bit-field-reverse}}.
221=== Acknowledgements
222This SRFI would not be possible without the efforts of Olin Shivers, Audrey Jaffer, Taylor Campbell, and the R6RS editors.
223=== Author
224* John Cowan
225* Ported to Chicken 5 by Sergey Goldgaber
226=== Copyright
227Copyright (C) John Cowan (2016). All Rights Reserved.
228
229Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
230
231The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
232
233THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
234=== Version history
235* [[https://github.com/diamond-lizard/srfi-143/releases/tag/0.1|0.1]] - Ported to Chicken Scheme 5
Note: See TracBrowser for help on using the repository browser.