2 @c This is part of the GNU Guile Reference Manual.
3 @c Copyright (C) 1996, 1997, 2000, 2001, 2002, 2003, 2004
4 @c Free Software Foundation, Inc.
5 @c See the file guile.texi for copying conditions.
7 @c essay \input texinfo
8 @c essay @c -*-texinfo-*-
9 @c essay @c %**start of header
10 @c essay @setfilename data-rep.info
11 @c essay @settitle Data Representation in Guile
12 @c essay @c %**end of header
14 @c essay @include version.texi
16 @c essay @dircategory The Algorithmic Language Scheme
18 @c essay * data-rep: (data-rep). Data Representation in Guile --- how to use
19 @c essay Guile objects in your C code.
20 @c essay @end direntry
22 @c essay @setchapternewpage off
25 @c essay Data Representation in Guile
27 @c essay Copyright (C) 1998, 1999, 2000, 2003, 2006 Free Software Foundation
29 @c essay Permission is granted to make and distribute verbatim copies of
30 @c essay this manual provided the copyright notice and this permission notice
31 @c essay are preserved on all copies.
34 @c essay Permission is granted to process this file through TeX and print the
35 @c essay results, provided the printed document carries copying permission
36 @c essay notice identical to this one except for the removal of this paragraph
37 @c essay (this paragraph not being relevant to the printed manual).
40 @c essay Permission is granted to copy and distribute modified versions of this
41 @c essay manual under the conditions for verbatim copying, provided that the entire
42 @c essay resulting derived work is distributed under the terms of a permission
43 @c essay notice identical to this one.
45 @c essay Permission is granted to copy and distribute translations of this manual
46 @c essay into another language, under the above conditions for modified versions,
47 @c essay except that this permission notice may be stated in a translation approved
48 @c essay by the Free Software Foundation.
53 @c essay @comment The title is printed in a large font.
54 @c essay @title Data Representation in Guile
55 @c essay @subtitle $Id: data-rep.texi,v 1.19.2.1 2006-02-12 13:42:50 mvo Exp $
56 @c essay @subtitle For use with Guile @value{VERSION}
57 @c essay @author Jim Blandy
58 @c essay @author Free Software Foundation
59 @c essay @author @email{jimb@@red-bean.com}
60 @c essay @c The following two commands start the copyright page.
62 @c essay @vskip 0pt plus 1filll
63 @c essay @vskip 0pt plus 1filll
64 @c essay Copyright @copyright{} 1998, 2006 Free Software Foundation
66 @c essay Permission is granted to make and distribute verbatim copies of
67 @c essay this manual provided the copyright notice and this permission notice
68 @c essay are preserved on all copies.
70 @c essay Permission is granted to copy and distribute modified versions of this
71 @c essay manual under the conditions for verbatim copying, provided that the entire
72 @c essay resulting derived work is distributed under the terms of a permission
73 @c essay notice identical to this one.
75 @c essay Permission is granted to copy and distribute translations of this manual
76 @c essay into another language, under the above conditions for modified versions,
77 @c essay except that this permission notice may be stated in a translation approved
78 @c essay by Free Software Foundation.
79 @c essay @end titlepage
81 @c essay @c @smallbook
83 @c essay @headings double
86 @c essay @node Top, Data Representation in Scheme, (dir), (dir)
87 @c essay @top Data Representation in Guile
90 @c essay This essay is meant to provide the background necessary to read and
91 @c essay write C code that manipulates Scheme values in a way that conforms to
92 @c essay libguile's interface. If you would like to write or maintain a
93 @c essay Guile-based application in C or C++, this is the first information you
96 @c essay In order to make sense of Guile's @code{SCM_} functions, or read
97 @c essay libguile's source code, it's essential to have a good grasp of how Guile
98 @c essay actually represents Scheme values. Otherwise, a lot of the code, and
99 @c essay the conventions it follows, won't make very much sense.
101 @c essay We assume you know both C and Scheme, but we do not assume you are
102 @c essay familiar with Guile's C interface.
106 @node Data Representation
107 @appendix Data Representation in Guile
109 @strong{by Jim Blandy}
111 [Due to the rather non-orthogonal and performance-oriented nature of the
112 SCM interface, you need to understand SCM internals *before* you can use
113 the SCM API. That's why this chapter comes first.]
115 [NOTE: this is Jim Blandy's essay almost entirely unmodified. It has to
116 be adapted to fit this manual smoothly.]
118 In order to make sense of Guile's SCM_ functions, or read libguile's
119 source code, it's essential to have a good grasp of how Guile actually
120 represents Scheme values. Otherwise, a lot of the code, and the
121 conventions it follows, won't make very much sense. This essay is meant
122 to provide the background necessary to read and write C code that
123 manipulates Scheme values in a way that is compatible with libguile.
125 We assume you know both C and Scheme, but we do not assume you are
126 familiar with Guile's implementation.
129 * Data Representation in Scheme:: Why things aren't just totally
130 straightforward, in general terms.
131 * How Guile does it:: How to write C code that manipulates
132 Guile values, with an explanation
133 of Guile's garbage collector.
136 @node Data Representation in Scheme
137 @section Data Representation in Scheme
139 Scheme is a latently-typed language; this means that the system cannot,
140 in general, determine the type of a given expression at compile time.
141 Types only become apparent at run time. Variables do not have fixed
142 types; a variable may hold a pair at one point, an integer at the next,
143 and a thousand-element vector later. Instead, values, not variables,
146 In order to implement standard Scheme functions like @code{pair?} and
147 @code{string?} and provide garbage collection, the representation of
148 every value must contain enough information to accurately determine its
149 type at run time. Often, Scheme systems also use this information to
150 determine whether a program has attempted to apply an operation to an
151 inappropriately typed value (such as taking the @code{car} of a string).
153 Because variables, pairs, and vectors may hold values of any type,
154 Scheme implementations use a uniform representation for values --- a
155 single type large enough to hold either a complete value or a pointer
156 to a complete value, along with the necessary typing information.
158 The following sections will present a simple typing system, and then
159 make some refinements to correct its major weaknesses. However, this is
160 not a description of the system Guile actually uses. It is only an
161 illustration of the issues Guile's system must address. We provide all
162 the information one needs to work with Guile's data in @ref{How Guile
167 * A Simple Representation::
173 @node A Simple Representation
174 @subsection A Simple Representation
176 The simplest way to meet the above requirements in C would be to
177 represent each value as a pointer to a structure containing a type
178 indicator, followed by a union carrying the real value. Assuming that
179 @code{SCM} is the name of our universal type, we can write:
182 enum type @{ integer, pair, string, vector, ... @};
184 typedef struct value *SCM;
190 struct @{ SCM car, cdr; @} pair;
191 struct @{ int length; char *elts; @} string;
192 struct @{ int length; SCM *elts; @} vector;
197 with the ellipses replaced with code for the remaining Scheme types.
199 This representation is sufficient to implement all of Scheme's
200 semantics. If @var{x} is an @code{SCM} value:
203 To test if @var{x} is an integer, we can write @code{@var{x}->type == integer}.
205 To find its value, we can write @code{@var{x}->value.integer}.
207 To test if @var{x} is a vector, we can write @code{@var{x}->type == vector}.
209 If we know @var{x} is a vector, we can write
210 @code{@var{x}->value.vector.elts[0]} to refer to its first element.
212 If we know @var{x} is a pair, we can write
213 @code{@var{x}->value.pair.car} to extract its car.
217 @node Faster Integers
218 @subsection Faster Integers
220 Unfortunately, the above representation has a serious disadvantage. In
221 order to return an integer, an expression must allocate a @code{struct
222 value}, initialize it to represent that integer, and return a pointer to
223 it. Furthermore, fetching an integer's value requires a memory
224 reference, which is much slower than a register reference on most
225 processors. Since integers are extremely common, this representation is
226 too costly, in both time and space. Integers should be very cheap to
227 create and manipulate.
229 One possible solution comes from the observation that, on many
230 architectures, structures must be aligned on a four-byte boundary.
231 (Whether or not the machine actually requires it, we can write our own
232 allocator for @code{struct value} objects that assures this is true.)
233 In this case, the lower two bits of the structure's address are known to
236 This gives us the room we need to provide an improved representation
237 for integers. We make the following rules:
240 If the lower two bits of an @code{SCM} value are zero, then the SCM
241 value is a pointer to a @code{struct value}, and everything proceeds as
244 Otherwise, the @code{SCM} value represents an integer, whose value
245 appears in its upper bits.
248 Here is C code implementing this convention:
250 enum type @{ pair, string, vector, ... @};
252 typedef struct value *SCM;
257 struct @{ SCM car, cdr; @} pair;
258 struct @{ int length; char *elts; @} string;
259 struct @{ int length; SCM *elts; @} vector;
264 #define POINTER_P(x) (((int) (x) & 3) == 0)
265 #define INTEGER_P(x) (! POINTER_P (x))
267 #define GET_INTEGER(x) ((int) (x) >> 2)
268 #define MAKE_INTEGER(x) ((SCM) (((x) << 2) | 1))
271 Notice that @code{integer} no longer appears as an element of @code{enum
272 type}, and the union has lost its @code{integer} member. Instead, we
273 use the @code{POINTER_P} and @code{INTEGER_P} macros to make a coarse
274 classification of values into integers and non-integers, and do further
275 type testing as before.
277 Here's how we would answer the questions posed above (again, assume
278 @var{x} is an @code{SCM} value):
281 To test if @var{x} is an integer, we can write @code{INTEGER_P (@var{x})}.
283 To find its value, we can write @code{GET_INTEGER (@var{x})}.
285 To test if @var{x} is a vector, we can write:
287 @code{POINTER_P (@var{x}) && @var{x}->type == vector}
289 Given the new representation, we must make sure @var{x} is truly a
290 pointer before we dereference it to determine its complete type.
292 If we know @var{x} is a vector, we can write
293 @code{@var{x}->value.vector.elts[0]} to refer to its first element, as
296 If we know @var{x} is a pair, we can write
297 @code{@var{x}->value.pair.car} to extract its car, just as before.
300 This representation allows us to operate more efficiently on integers
301 than the first. For example, if @var{x} and @var{y} are known to be
302 integers, we can compute their sum as follows:
304 MAKE_INTEGER (GET_INTEGER (@var{x}) + GET_INTEGER (@var{y}))
306 Now, integer math requires no allocation or memory references. Most
307 real Scheme systems actually use an even more efficient representation,
308 but this essay isn't about bit-twiddling. (Hint: what if pointers had
309 @code{01} in their least significant bits, and integers had @code{00}?)
313 @subsection Cheaper Pairs
315 However, there is yet another issue to confront. Most Scheme heaps
316 contain more pairs than any other type of object; Jonathan Rees says
317 that pairs occupy 45% of the heap in his Scheme implementation, Scheme
318 48. However, our representation above spends three @code{SCM}-sized
319 words per pair --- one for the type, and two for the @sc{car} and
320 @sc{cdr}. Is there any way to represent pairs using only two words?
322 Let us refine the convention we established earlier. Let us assert
326 If the bottom two bits of an @code{SCM} value are @code{#b00}, then
327 it is a pointer, as before.
329 If the bottom two bits are @code{#b01}, then the upper bits are an
330 integer. This is a bit more restrictive than before.
332 If the bottom two bits are @code{#b10}, then the value, with the bottom
333 two bits masked out, is the address of a pair.
336 Here is the new C code:
338 enum type @{ string, vector, ... @};
340 typedef struct value *SCM;
345 struct @{ int length; char *elts; @} string;
346 struct @{ int length; SCM *elts; @} vector;
355 #define POINTER_P(x) (((int) (x) & 3) == 0)
357 #define INTEGER_P(x) (((int) (x) & 3) == 1)
358 #define GET_INTEGER(x) ((int) (x) >> 2)
359 #define MAKE_INTEGER(x) ((SCM) (((x) << 2) | 1))
361 #define PAIR_P(x) (((int) (x) & 3) == 2)
362 #define GET_PAIR(x) ((struct pair *) ((int) (x) & ~3))
365 Notice that @code{enum type} and @code{struct value} now only contain
366 provisions for vectors and strings; both integers and pairs have become
367 special cases. The code above also assumes that an @code{int} is large
368 enough to hold a pointer, which isn't generally true.
371 Our list of examples is now as follows:
374 To test if @var{x} is an integer, we can write @code{INTEGER_P
375 (@var{x})}; this is as before.
377 To find its value, we can write @code{GET_INTEGER (@var{x})}, as
380 To test if @var{x} is a vector, we can write:
382 @code{POINTER_P (@var{x}) && @var{x}->type == vector}
384 We must still make sure that @var{x} is a pointer to a @code{struct
385 value} before dereferencing it to find its type.
387 If we know @var{x} is a vector, we can write
388 @code{@var{x}->value.vector.elts[0]} to refer to its first element, as
391 We can write @code{PAIR_P (@var{x})} to determine if @var{x} is a
392 pair, and then write @code{GET_PAIR (@var{x})->car} to refer to its
396 This change in representation reduces our heap size by 15%. It also
397 makes it cheaper to decide if a value is a pair, because no memory
398 references are necessary; it suffices to check the bottom two bits of
399 the @code{SCM} value. This may be significant when traversing lists, a
400 common activity in a Scheme system.
402 Again, most real Scheme systems use a slightly different implementation;
403 for example, if GET_PAIR subtracts off the low bits of @code{x}, instead
404 of masking them off, the optimizer will often be able to combine that
405 subtraction with the addition of the offset of the structure member we
406 are referencing, making a modified pointer as fast to use as an
410 @node Guile Is Hairier
411 @subsection Guile Is Hairier
413 We originally started with a very simple typing system --- each object
414 has a field that indicates its type. Then, for the sake of efficiency
415 in both time and space, we moved some of the typing information directly
416 into the @code{SCM} value, and left the rest in the @code{struct value}.
417 Guile itself employs a more complex hierarchy, storing finer and finer
418 gradations of type information in different places, depending on the
419 object's coarser type.
421 In the author's opinion, Guile could be simplified greatly without
422 significant loss of efficiency, but the simplified system would still be
423 more complex than what we've presented above.
426 @node How Guile does it
427 @section How Guile does it
429 Here we present the specifics of how Guile represents its data. We
430 don't go into complete detail; an exhaustive description of Guile's
431 system would be boring, and we do not wish to encourage people to write
432 code which depends on its details anyway. We do, however, present
433 everything one need know to use Guile's data.
435 This section is in limbo. It used to document the 'low-level' C API
436 of Guile that was used both by clients of libguile and by libguile
439 In the future, clients should only need to look into the sections
440 @ref{Programming in C} and @ref{API Reference}. This section will in
441 the end only contain stuff about the internals of Guile.
446 * Immediates vs Non-immediates::
447 * Immediate Datatypes::
448 * Non-immediate Datatypes::
449 * Signalling Type Errors::
450 * Unpacking the SCM type::
454 @subsection General Rules
456 Any code which operates on Guile datatypes must @code{#include} the
457 header file @code{<libguile.h>}. This file contains a definition for
458 the @code{SCM} typedef (Guile's universal type, as in the examples
459 above), and definitions and declarations for a host of macros and
460 functions that operate on @code{SCM} values.
462 All identifiers declared by @code{<libguile.h>} begin with @code{scm_}
465 @c [[I wish this were true, but I don't think it is at the moment. -JimB]]
466 @c Macros do not evaluate their arguments more than once, unless documented
469 The functions described here generally check the types of their
470 @code{SCM} arguments, and signal an error if their arguments are of an
471 inappropriate type. Macros generally do not, unless that is their
472 specified purpose. You must verify their argument types beforehand, as
475 Macros and functions that return a boolean value have names ending in
476 @code{P} or @code{_p} (for ``predicate''). Those that return a negated
477 boolean value have names starting with @code{SCM_N}. For example,
478 @code{SCM_IMP (@var{x})} is a predicate which returns non-zero iff
479 @var{x} is an immediate value (an @code{IM}). @code{SCM_NCONSP
480 (@var{x})} is a predicate which returns non-zero iff @var{x} is
481 @emph{not} a pair object (a @code{CONS}).
484 @node Conservative GC
485 @subsection Conservative Garbage Collection
487 Aside from the latent typing, the major source of constraints on a
488 Scheme implementation's data representation is the garbage collector.
489 The collector must be able to traverse every live object in the heap, to
490 determine which objects are not live.
492 There are many ways to implement this, but Guile uses an algorithm
493 called @dfn{mark and sweep}. The collector scans the system's global
494 variables and the local variables on the stack to determine which
495 objects are immediately accessible by the C code. It then scans those
496 objects to find the objects they point to, @i{et cetera}. The collector
497 sets a @dfn{mark bit} on each object it finds, so each object is
498 traversed only once. This process is called @dfn{tracing}.
500 When the collector can find no unmarked objects pointed to by marked
501 objects, it assumes that any objects that are still unmarked will never
502 be used by the program (since there is no path of dereferences from any
503 global or local variable that reaches them) and deallocates them.
505 In the above paragraphs, we did not specify how the garbage collector
506 finds the global and local variables; as usual, there are many different
507 approaches. Frequently, the programmer must maintain a list of pointers
508 to all global variables that refer to the heap, and another list
509 (adjusted upon entry to and exit from each function) of local variables,
510 for the collector's benefit.
512 The list of global variables is usually not too difficult to maintain,
513 since global variables are relatively rare. However, an explicitly
514 maintained list of local variables (in the author's personal experience)
515 is a nightmare to maintain. Thus, Guile uses a technique called
516 @dfn{conservative garbage collection}, to make the local variable list
519 The trick to conservative collection is to treat the stack as an
520 ordinary range of memory, and assume that @emph{every} word on the stack
521 is a pointer into the heap. Thus, the collector marks all objects whose
522 addresses appear anywhere in the stack, without knowing for sure how
523 that word is meant to be interpreted.
525 Obviously, such a system will occasionally retain objects that are
526 actually garbage, and should be freed. In practice, this is not a
527 problem. The alternative, an explicitly maintained list of local
528 variable addresses, is effectively much less reliable, due to programmer
531 To accommodate this technique, data must be represented so that the
532 collector can accurately determine whether a given stack word is a
533 pointer or not. Guile does this as follows:
537 Every heap object has a two-word header, called a @dfn{cell}. Some
538 objects, like pairs, fit entirely in a cell's two words; others may
539 store pointers to additional memory in either of the words. For
540 example, strings and vectors store their length in the first word, and a
541 pointer to their elements in the second.
544 Guile allocates whole arrays of cells at a time, called @dfn{heap
545 segments}. These segments are always allocated so that the cells they
546 contain fall on eight-byte boundaries, or whatever is appropriate for
547 the machine's word size. Guile keeps all cells in a heap segment
548 initialized, whether or not they are currently in use.
551 Guile maintains a sorted table of heap segments.
554 Thus, given any random word @var{w} fetched from the stack, Guile's
555 garbage collector can consult the table to see if @var{w} falls within a
556 known heap segment, and check @var{w}'s alignment. If both tests pass,
557 the collector knows that @var{w} is a valid pointer to a cell,
558 intentional or not, and proceeds to trace the cell.
560 Note that heap segments do not contain all the data Guile uses; cells
561 for objects like vectors and strings contain pointers to other memory
562 areas. However, since those pointers are internal, and not shared among
563 many pieces of code, it is enough for the collector to find the cell,
564 and then use the cell's type to find more pointers to trace.
567 @node Immediates vs Non-immediates
568 @subsection Immediates vs Non-immediates
570 Guile classifies Scheme objects into two kinds: those that fit entirely
571 within an @code{SCM}, and those that require heap storage.
573 The former class are called @dfn{immediates}. The class of immediates
574 includes small integers, characters, boolean values, the empty list, the
575 mysterious end-of-file object, and some others.
577 The remaining types are called, not surprisingly, @dfn{non-immediates}.
578 They include pairs, procedures, strings, vectors, and all other data
581 @deftypefn Macro int SCM_IMP (SCM @var{x})
582 Return non-zero iff @var{x} is an immediate object.
585 @deftypefn Macro int SCM_NIMP (SCM @var{x})
586 Return non-zero iff @var{x} is a non-immediate object. This is the
587 exact complement of @code{SCM_IMP}, above.
590 Note that for versions of Guile prior to 1.4 it was necessary to use the
591 @code{SCM_NIMP} macro before calling a finer-grained predicate to
592 determine @var{x}'s type, such as @code{SCM_CONSP} or
593 @code{SCM_VECTORP}. This is no longer required: the definitions of all
594 Guile type predicates now include a call to @code{SCM_NIMP} where
598 @node Immediate Datatypes
599 @subsection Immediate Datatypes
601 The following datatypes are immediate values; that is, they fit entirely
602 within an @code{SCM} value. The @code{SCM_IMP} and @code{SCM_NIMP}
603 macros will distinguish these from non-immediates; see @ref{Immediates
604 vs Non-immediates} for an explanation of the distinction.
606 Note that the type predicates for immediate values work correctly on any
607 @code{SCM} value; you do not need to call @code{SCM_IMP} first, to
608 establish that a value is immediate.
618 @subsubsection Integers
620 Here are functions for operating on small integers, that fit within an
621 @code{SCM}. Such integers are called @dfn{immediate numbers}, or
622 @dfn{INUMs}. In general, INUMs occupy all but two bits of an
625 Bignums and floating-point numbers are non-immediate objects, and have
626 their own, separate accessors. The functions here will not work on
627 them. This is not as much of a problem as you might think, however,
628 because the system never constructs bignums that could fit in an INUM,
629 and never uses floating point values for exact integers.
631 @deftypefn Macro int SCM_INUMP (SCM @var{x})
632 Return non-zero iff @var{x} is a small integer value.
635 @deftypefn Macro int SCM_NINUMP (SCM @var{x})
636 The complement of SCM_INUMP.
639 @deftypefn Macro int SCM_INUM (SCM @var{x})
640 Return the value of @var{x} as an ordinary, C integer. If @var{x}
641 is not an INUM, the result is undefined.
644 @deftypefn Macro SCM SCM_MAKINUM (int @var{i})
645 Given a C integer @var{i}, return its representation as an @code{SCM}.
646 This function does not check for overflow.
651 @subsubsection Characters
653 Here are functions for operating on characters.
655 @deftypefn Macro int SCM_CHARP (SCM @var{x})
656 Return non-zero iff @var{x} is a character value.
659 @deftypefn Macro {unsigned int} SCM_CHAR (SCM @var{x})
660 Return the value of @code{x} as a C character. If @var{x} is not a
661 Scheme character, the result is undefined.
664 @deftypefn Macro SCM SCM_MAKE_CHAR (int @var{c})
665 Given a C character @var{c}, return its representation as a Scheme
671 @subsubsection Booleans
673 Booleans are represented as two specific immediate SCM values,
674 @code{SCM_BOOL_T} and @code{SCM_BOOL_F}. @xref{Booleans}, for more
678 @subsubsection Unique Values
680 The immediate values that are neither small integers, characters, nor
681 booleans are all unique values --- that is, datatypes with only one
684 @deftypefn Macro SCM SCM_EOL
685 The Scheme empty list object, or ``End Of List'' object, usually written
686 in Scheme as @code{'()}.
689 @deftypefn Macro SCM SCM_EOF_VAL
690 The Scheme end-of-file value. It has no standard written
691 representation, for obvious reasons.
694 @deftypefn Macro SCM SCM_UNSPECIFIED
695 The value returned by expressions which the Scheme standard says return
696 an ``unspecified'' value.
698 This is sort of a weirdly literal way to take things, but the standard
699 read-eval-print loop prints nothing when the expression returns this
700 value, so it's not a bad idea to return this when you can't think of
701 anything else helpful.
704 @deftypefn Macro SCM SCM_UNDEFINED
705 The ``undefined'' value. Its most important property is that is not
706 equal to any valid Scheme value. This is put to various internal uses
707 by C code interacting with Guile.
709 For example, when you write a C function that is callable from Scheme
710 and which takes optional arguments, the interpreter passes
711 @code{SCM_UNDEFINED} for any arguments you did not receive.
713 We also use this to mark unbound variables.
716 @deftypefn Macro int SCM_UNBNDP (SCM @var{x})
717 Return true if @var{x} is @code{SCM_UNDEFINED}. Apply this to a
718 symbol's value to see if it has a binding as a global variable.
722 @node Non-immediate Datatypes
723 @subsection Non-immediate Datatypes
725 A non-immediate datatype is one which lives in the heap, either because
726 it cannot fit entirely within a @code{SCM} word, or because it denotes a
727 specific storage location (in the nomenclature of the Revised^5 Report
730 The @code{SCM_IMP} and @code{SCM_NIMP} macros will distinguish these
731 from immediates; see @ref{Immediates vs Non-immediates}.
733 Given a cell, Guile distinguishes between pairs and other non-immediate
734 types by storing special @dfn{tag} values in a non-pair cell's car, that
735 cannot appear in normal pairs. A cell with a non-tag value in its car
736 is an ordinary pair. The type of a cell with a tag in its car depends
737 on the tag; the non-immediate type predicates test this value. If a tag
738 value appears elsewhere (in a vector, for example), the heap may become
741 Note how the type information for a non-immediate object is split
742 between the @code{SCM} word and the cell that the @code{SCM} word points
743 to. The @code{SCM} word itself only indicates that the object is
744 non-immediate --- in other words stored in a heap cell. The tag stored
745 in the first word of the heap cell indicates more precisely the type of
748 The type predicates for non-immediate values work correctly on any
749 @code{SCM} value; you do not need to call @code{SCM_NIMP} first, to
750 establish that a value is non-immediate.
765 Pairs are the essential building block of list structure in Scheme. A
766 pair object has two fields, called the @dfn{car} and the @dfn{cdr}.
768 It is conventional for a pair's @sc{car} to contain an element of a
769 list, and the @sc{cdr} to point to the next pair in the list, or to
770 contain @code{SCM_EOL}, indicating the end of the list. Thus, a set of
771 pairs chained through their @sc{cdr}s constitutes a singly-linked list.
772 Scheme and libguile define many functions which operate on lists
773 constructed in this fashion, so although lists chained through the
774 @sc{car}s of pairs will work fine too, they may be less convenient to
775 manipulate, and receive less support from the community.
777 Guile implements pairs by mapping the @sc{car} and @sc{cdr} of a pair
778 directly into the two words of the cell.
781 @deftypefn Macro int SCM_CONSP (SCM @var{x})
782 Return non-zero iff @var{x} is a Scheme pair object.
785 @deftypefn Macro int SCM_NCONSP (SCM @var{x})
786 The complement of SCM_CONSP.
789 @deftypefun SCM scm_cons (SCM @var{car}, SCM @var{cdr})
790 Allocate (``CONStruct'') a new pair, with @var{car} and @var{cdr} as its
794 The macros below perform no type checking. The results are undefined if
795 @var{cell} is an immediate. However, since all non-immediate Guile
796 objects are constructed from cells, and these macros simply return the
797 first element of a cell, they actually can be useful on datatypes other
798 than pairs. (Of course, it is not very modular to use them outside of
799 the code which implements that datatype.)
801 @deftypefn Macro SCM SCM_CAR (SCM @var{cell})
802 Return the @sc{car}, or first field, of @var{cell}.
805 @deftypefn Macro SCM SCM_CDR (SCM @var{cell})
806 Return the @sc{cdr}, or second field, of @var{cell}.
809 @deftypefn Macro void SCM_SETCAR (SCM @var{cell}, SCM @var{x})
810 Set the @sc{car} of @var{cell} to @var{x}.
813 @deftypefn Macro void SCM_SETCDR (SCM @var{cell}, SCM @var{x})
814 Set the @sc{cdr} of @var{cell} to @var{x}.
817 @deftypefn Macro SCM SCM_CAAR (SCM @var{cell})
818 @deftypefnx Macro SCM SCM_CADR (SCM @var{cell})
819 @deftypefnx Macro SCM SCM_CDAR (SCM @var{cell}) @dots{}
820 @deftypefnx Macro SCM SCM_CDDDDR (SCM @var{cell})
821 Return the @sc{car} of the @sc{car} of @var{cell}, the @sc{car} of the
822 @sc{cdr} of @var{cell}, @i{et cetera}.
827 @subsubsection Vectors, Strings, and Symbols
829 Vectors, strings, and symbols have some properties in common. They all
830 have a length, and they all have an array of elements. In the case of a
831 vector, the elements are @code{SCM} values; in the case of a string or
832 symbol, the elements are characters.
834 All these types store their length (along with some tagging bits) in the
835 @sc{car} of their header cell, and store a pointer to the elements in
836 their @sc{cdr}. Thus, the @code{SCM_CAR} and @code{SCM_CDR} macros
837 are (somewhat) meaningful when applied to these datatypes.
839 @deftypefn Macro int SCM_VECTORP (SCM @var{x})
840 Return non-zero iff @var{x} is a vector.
843 @deftypefn Macro int SCM_STRINGP (SCM @var{x})
844 Return non-zero iff @var{x} is a string.
847 @deftypefn Macro int SCM_SYMBOLP (SCM @var{x})
848 Return non-zero iff @var{x} is a symbol.
851 @deftypefn Macro int SCM_VECTOR_LENGTH (SCM @var{x})
852 @deftypefnx Macro int SCM_STRING_LENGTH (SCM @var{x})
853 @deftypefnx Macro int SCM_SYMBOL_LENGTH (SCM @var{x})
854 Return the length of the object @var{x}. The result is undefined if
855 @var{x} is not a vector, string, or symbol, respectively.
858 @deftypefn Macro {SCM *} SCM_VECTOR_BASE (SCM @var{x})
859 Return a pointer to the array of elements of the vector @var{x}.
860 The result is undefined if @var{x} is not a vector.
863 @deftypefn Macro {char *} SCM_STRING_CHARS (SCM @var{x})
864 @deftypefnx Macro {char *} SCM_SYMBOL_CHARS (SCM @var{x})
865 Return a pointer to the characters of @var{x}. The result is undefined
866 if @var{x} is not a symbol or string, respectively.
869 There are also a few magic values stuffed into memory before a symbol's
870 characters, but you don't want to know about those. What cruft!
872 Note that @code{SCM_VECTOR_BASE}, @code{SCM_STRING_CHARS} and
873 @code{SCM_SYMBOL_CHARS} return pointers to data within the respective
874 object. Care must be taken that the object is not garbage collected
875 while that data is still being accessed. This is the same as for a
876 smob, @xref{Remembering During Operations}.
880 @subsubsection Procedures
882 Guile provides two kinds of procedures: @dfn{closures}, which are the
883 result of evaluating a @code{lambda} expression, and @dfn{subrs}, which
884 are C functions packaged up as Scheme objects, to make them available to
887 (There are actually other sorts of procedures: compiled closures, and
888 continuations; see the source code for details about them.)
890 @deftypefun SCM scm_procedure_p (SCM @var{x})
891 Return @code{SCM_BOOL_T} iff @var{x} is a Scheme procedure object, of
892 any sort. Otherwise, return @code{SCM_BOOL_F}.
897 @subsubsection Closures
899 [FIXME: this needs to be further subbed, but texinfo has no subsubsub]
901 A closure is a procedure object, generated as the value of a
902 @code{lambda} expression in Scheme. The representation of a closure is
903 straightforward --- it contains a pointer to the code of the lambda
904 expression from which it was created, and a pointer to the environment
907 In Guile, each closure also has a property list, allowing the system to
908 store information about the closure. I'm not sure what this is used for
909 at the moment --- the debugger, maybe?
911 @deftypefn Macro int SCM_CLOSUREP (SCM @var{x})
912 Return non-zero iff @var{x} is a closure.
915 @deftypefn Macro SCM SCM_PROCPROPS (SCM @var{x})
916 Return the property list of the closure @var{x}. The results are
917 undefined if @var{x} is not a closure.
920 @deftypefn Macro void SCM_SETPROCPROPS (SCM @var{x}, SCM @var{p})
921 Set the property list of the closure @var{x} to @var{p}. The results
922 are undefined if @var{x} is not a closure.
925 @deftypefn Macro SCM SCM_CODE (SCM @var{x})
926 Return the code of the closure @var{x}. The result is undefined if
927 @var{x} is not a closure.
929 This function should probably only be used internally by the
930 interpreter, since the representation of the code is intimately
931 connected with the interpreter's implementation.
934 @deftypefn Macro SCM SCM_ENV (SCM @var{x})
935 Return the environment enclosed by @var{x}.
936 The result is undefined if @var{x} is not a closure.
938 This function should probably only be used internally by the
939 interpreter, since the representation of the environment is intimately
940 connected with the interpreter's implementation.
947 [FIXME: this needs to be further subbed, but texinfo has no subsubsub]
949 A subr is a pointer to a C function, packaged up as a Scheme object to
950 make it callable by Scheme code. In addition to the function pointer,
951 the subr also contains a pointer to the name of the function, and
952 information about the number of arguments accepted by the C function, for
953 the sake of error checking.
955 There is no single type predicate macro that recognizes subrs, as
956 distinct from other kinds of procedures. The closest thing is
957 @code{scm_procedure_p}; see @ref{Procedures}.
959 @deftypefn Macro {char *} SCM_SNAME (@var{x})
960 Return the name of the subr @var{x}. The result is undefined if
961 @var{x} is not a subr.
964 @deftypefun SCM scm_c_define_gsubr (char *@var{name}, int @var{req}, int @var{opt}, int @var{rest}, SCM (*@var{function})())
965 Create a new subr object named @var{name}, based on the C function
966 @var{function}, make it visible to Scheme the value of as a global
967 variable named @var{name}, and return the subr object.
969 The subr object accepts @var{req} required arguments, @var{opt} optional
970 arguments, and a @var{rest} argument iff @var{rest} is non-zero. The C
971 function @var{function} should accept @code{@var{req} + @var{opt}}
972 arguments, or @code{@var{req} + @var{opt} + 1} arguments if @code{rest}
975 When a subr object is applied, it must be applied to at least @var{req}
976 arguments, or else Guile signals an error. @var{function} receives the
977 subr's first @var{req} arguments as its first @var{req} arguments. If
978 there are fewer than @var{opt} arguments remaining, then @var{function}
979 receives the value @code{SCM_UNDEFINED} for any missing optional
982 If @var{rst} is non-zero, then any arguments after the first
983 @code{@var{req} + @var{opt}} are packaged up as a list and passed as
984 @var{function}'s last argument. @var{function} must not modify that
985 list. (Because when subr is called through @code{apply} the list is
986 directly from the @code{apply} argument, which the caller will expect
989 Note that subrs can actually only accept a predefined set of
990 combinations of required, optional, and rest arguments. For example, a
991 subr can take one required argument, or one required and one optional
992 argument, but a subr can't take one required and two optional arguments.
993 It's bizarre, but that's the way the interpreter was written. If the
994 arguments to @code{scm_c_define_gsubr} do not fit one of the predefined
995 patterns, then @code{scm_c_define_gsubr} will return a compiled closure
996 object instead of a subr object.
1001 @subsubsection Ports
1003 Haven't written this yet, 'cos I don't understand ports yet.
1006 @node Signalling Type Errors
1007 @subsection Signalling Type Errors
1009 Every function visible at the Scheme level should aggressively check the
1010 types of its arguments, to avoid misinterpreting a value, and perhaps
1011 causing a segmentation fault. Guile provides some macros to make this
1014 @deftypefn Macro void SCM_ASSERT (int @var{test}, SCM @var{obj}, unsigned int @var{position}, const char *@var{subr})
1015 If @var{test} is zero, signal a ``wrong type argument'' error,
1016 attributed to the subroutine named @var{subr}, operating on the value
1017 @var{obj}, which is the @var{position}'th argument of @var{subr}.
1020 @deftypefn Macro int SCM_ARG1
1021 @deftypefnx Macro int SCM_ARG2
1022 @deftypefnx Macro int SCM_ARG3
1023 @deftypefnx Macro int SCM_ARG4
1024 @deftypefnx Macro int SCM_ARG5
1025 @deftypefnx Macro int SCM_ARG6
1026 @deftypefnx Macro int SCM_ARG7
1027 One of the above values can be used for @var{position} to indicate the
1028 number of the argument of @var{subr} which is being checked.
1029 Alternatively, a positive integer number can be used, which allows to
1030 check arguments after the seventh. However, for parameter numbers up to
1031 seven it is preferable to use @code{SCM_ARGN} instead of the
1032 corresponding raw number, since it will make the code easier to
1036 @deftypefn Macro int SCM_ARGn
1037 Passing a value of zero or @code{SCM_ARGn} for @var{position} allows to
1038 leave it unspecified which argument's type is incorrect. Again,
1039 @code{SCM_ARGn} should be preferred over a raw zero constant.
1043 @node Unpacking the SCM type
1044 @subsection Unpacking the SCM Type
1046 The previous sections have explained how @code{SCM} values can refer to
1047 immediate and non-immediate Scheme objects. For immediate objects, the
1048 complete object value is stored in the @code{SCM} word itself, while for
1049 non-immediates, the @code{SCM} word contains a pointer to a heap cell,
1050 and further information about the object in question is stored in that
1051 cell. This section describes how the @code{SCM} type is actually
1052 represented and used at the C level.
1054 In fact, there are two basic C data types to represent objects in
1055 Guile: @code{SCM} and @code{scm_t_bits}.
1058 * Relationship between SCM and scm_t_bits::
1059 * Immediate objects::
1060 * Non-immediate objects::
1061 * Allocating Cells::
1062 * Heap Cell Type Information::
1063 * Accessing Cell Entries::
1064 * Basic Rules for Accessing Cell Entries::
1068 @node Relationship between SCM and scm_t_bits
1069 @subsubsection Relationship between @code{SCM} and @code{scm_t_bits}
1071 A variable of type @code{SCM} is guaranteed to hold a valid Scheme
1072 object. A variable of type @code{scm_t_bits}, on the other hand, may
1073 hold a representation of a @code{SCM} value as a C integral type, but
1074 may also hold any C value, even if it does not correspond to a valid
1077 For a variable @var{x} of type @code{SCM}, the Scheme object's type
1078 information is stored in a form that is not directly usable. To be able
1079 to work on the type encoding of the scheme value, the @code{SCM}
1080 variable has to be transformed into the corresponding representation as
1081 a @code{scm_t_bits} variable @var{y} by using the @code{SCM_UNPACK}
1082 macro. Once this has been done, the type of the scheme object @var{x}
1083 can be derived from the content of the bits of the @code{scm_t_bits}
1084 value @var{y}, in the way illustrated by the example earlier in this
1085 chapter (@pxref{Cheaper Pairs}). Conversely, a valid bit encoding of a
1086 Scheme value as a @code{scm_t_bits} variable can be transformed into the
1087 corresponding @code{SCM} value using the @code{SCM_PACK} macro.
1089 @node Immediate objects
1090 @subsubsection Immediate objects
1092 A Scheme object may either be an immediate, i.e. carrying all necessary
1093 information by itself, or it may contain a reference to a @dfn{cell}
1094 with additional information on the heap. Although in general it should
1095 be irrelevant for user code whether an object is an immediate or not,
1096 within Guile's own code the distinction is sometimes of importance.
1097 Thus, the following low level macro is provided:
1099 @deftypefn Macro int SCM_IMP (SCM @var{x})
1100 A Scheme object is an immediate if it fulfills the @code{SCM_IMP}
1101 predicate, otherwise it holds an encoded reference to a heap cell. The
1102 result of the predicate is delivered as a C style boolean value. User
1103 code and code that extends Guile should normally not be required to use
1111 Given a Scheme object @var{x} of unknown type, check first
1112 with @code{SCM_IMP (@var{x})} if it is an immediate object.
1114 If so, all of the type and value information can be determined from the
1115 @code{scm_t_bits} value that is delivered by @code{SCM_UNPACK
1120 @node Non-immediate objects
1121 @subsubsection Non-immediate objects
1123 A Scheme object of type @code{SCM} that does not fulfill the
1124 @code{SCM_IMP} predicate holds an encoded reference to a heap cell.
1125 This reference can be decoded to a C pointer to a heap cell using the
1126 @code{SCM2PTR} macro. The encoding of a pointer to a heap cell into a
1127 @code{SCM} value is done using the @code{PTR2SCM} macro.
1129 @c (FIXME:: this name should be changed)
1130 @deftypefn Macro (scm_t_cell *) SCM2PTR (SCM @var{x})
1131 Extract and return the heap cell pointer from a non-immediate @code{SCM}
1135 @c (FIXME:: this name should be changed)
1136 @deftypefn Macro SCM PTR2SCM (scm_t_cell * @var{x})
1137 Return a @code{SCM} value that encodes a reference to the heap cell
1141 Note that it is also possible to transform a non-immediate @code{SCM}
1142 value by using @code{SCM_UNPACK} into a @code{scm_t_bits} variable.
1143 However, the result of @code{SCM_UNPACK} may not be used as a pointer to
1144 a @code{scm_t_cell}: only @code{SCM2PTR} is guaranteed to transform a
1145 @code{SCM} object into a valid pointer to a heap cell. Also, it is not
1146 allowed to apply @code{PTR2SCM} to anything that is not a valid pointer
1153 Only use @code{SCM2PTR} on @code{SCM} values for which @code{SCM_IMP} is
1156 Don't use @code{(scm_t_cell *) SCM_UNPACK (@var{x})}! Use @code{SCM2PTR
1159 Don't use @code{PTR2SCM} for anything but a cell pointer!
1162 @node Allocating Cells
1163 @subsubsection Allocating Cells
1165 Guile provides both ordinary cells with two slots, and double cells
1166 with four slots. The following two function are the most primitive
1167 way to allocate such cells.
1169 If the caller intends to use it as a header for some other type, she
1170 must pass an appropriate magic value in @var{word_0}, to mark it as a
1171 member of that type, and pass whatever value as @var{word_1}, etc that
1172 the type expects. You should generally not need these functions,
1173 unless you are implementing a new datatype, and thoroughly understand
1174 the code in @code{<libguile/tags.h>}.
1176 If you just want to allocate pairs, use @code{scm_cons}.
1178 @deftypefn Function SCM scm_cell (scm_t_bits word_0, scm_t_bits word_1)
1179 Allocate a new cell, initialize the two slots with @var{word_0} and
1180 @var{word_1}, and return it.
1182 Note that @var{word_0} and @var{word_1} are of type @code{scm_t_bits}.
1183 If you want to pass a @code{SCM} object, you need to use
1187 @deftypefn Function SCM scm_double_cell (scm_t_bits word_0, scm_t_bits word_1, scm_t_bits word_2, scm_t_bits word_3)
1188 Like @code{scm_cell}, but allocates a double cell with four
1192 @node Heap Cell Type Information
1193 @subsubsection Heap Cell Type Information
1195 Heap cells contain a number of entries, each of which is either a scheme
1196 object of type @code{SCM} or a raw C value of type @code{scm_t_bits}.
1197 Which of the cell entries contain Scheme objects and which contain raw C
1198 values is determined by the first entry of the cell, which holds the
1199 cell type information.
1201 @deftypefn Macro scm_t_bits SCM_CELL_TYPE (SCM @var{x})
1202 For a non-immediate Scheme object @var{x}, deliver the content of the
1203 first entry of the heap cell referenced by @var{x}. This value holds
1204 the information about the cell type.
1207 @deftypefn Macro void SCM_SET_CELL_TYPE (SCM @var{x}, scm_t_bits @var{t})
1208 For a non-immediate Scheme object @var{x}, write the value @var{t} into
1209 the first entry of the heap cell referenced by @var{x}. The value
1210 @var{t} must hold a valid cell type.
1214 @node Accessing Cell Entries
1215 @subsubsection Accessing Cell Entries
1217 For a non-immediate Scheme object @var{x}, the object type can be
1218 determined by reading the cell type entry using the @code{SCM_CELL_TYPE}
1219 macro. For each different type of cell it is known which cell entries
1220 hold Scheme objects and which cell entries hold raw C data. To access
1221 the different cell entries appropriately, the following macros are
1224 @deftypefn Macro scm_t_bits SCM_CELL_WORD (SCM @var{x}, unsigned int @var{n})
1225 Deliver the cell entry @var{n} of the heap cell referenced by the
1226 non-immediate Scheme object @var{x} as raw data. It is illegal, to
1227 access cell entries that hold Scheme objects by using these macros. For
1228 convenience, the following macros are also provided.
1231 SCM_CELL_WORD_0 (@var{x}) @result{} SCM_CELL_WORD (@var{x}, 0)
1233 SCM_CELL_WORD_1 (@var{x}) @result{} SCM_CELL_WORD (@var{x}, 1)
1237 SCM_CELL_WORD_@var{n} (@var{x}) @result{} SCM_CELL_WORD (@var{x}, @var{n})
1241 @deftypefn Macro SCM SCM_CELL_OBJECT (SCM @var{x}, unsigned int @var{n})
1242 Deliver the cell entry @var{n} of the heap cell referenced by the
1243 non-immediate Scheme object @var{x} as a Scheme object. It is illegal,
1244 to access cell entries that do not hold Scheme objects by using these
1245 macros. For convenience, the following macros are also provided.
1248 SCM_CELL_OBJECT_0 (@var{x}) @result{} SCM_CELL_OBJECT (@var{x}, 0)
1250 SCM_CELL_OBJECT_1 (@var{x}) @result{} SCM_CELL_OBJECT (@var{x}, 1)
1254 SCM_CELL_OBJECT_@var{n} (@var{x}) @result{} SCM_CELL_OBJECT (@var{x},
1259 @deftypefn Macro void SCM_SET_CELL_WORD (SCM @var{x}, unsigned int @var{n}, scm_t_bits @var{w})
1260 Write the raw C value @var{w} into entry number @var{n} of the heap cell
1261 referenced by the non-immediate Scheme value @var{x}. Values that are
1262 written into cells this way may only be read from the cells using the
1263 @code{SCM_CELL_WORD} macros or, in case cell entry 0 is written, using
1264 the @code{SCM_CELL_TYPE} macro. For the special case of cell entry 0 it
1265 has to be made sure that @var{w} contains a cell type information which
1266 does not describe a Scheme object. For convenience, the following
1267 macros are also provided.
1270 SCM_SET_CELL_WORD_0 (@var{x}, @var{w}) @result{} SCM_SET_CELL_WORD
1271 (@var{x}, 0, @var{w})
1273 SCM_SET_CELL_WORD_1 (@var{x}, @var{w}) @result{} SCM_SET_CELL_WORD
1274 (@var{x}, 1, @var{w})
1278 SCM_SET_CELL_WORD_@var{n} (@var{x}, @var{w}) @result{} SCM_SET_CELL_WORD
1279 (@var{x}, @var{n}, @var{w})
1283 @deftypefn Macro void SCM_SET_CELL_OBJECT (SCM @var{x}, unsigned int @var{n}, SCM @var{o})
1284 Write the Scheme object @var{o} into entry number @var{n} of the heap
1285 cell referenced by the non-immediate Scheme value @var{x}. Values that
1286 are written into cells this way may only be read from the cells using
1287 the @code{SCM_CELL_OBJECT} macros or, in case cell entry 0 is written,
1288 using the @code{SCM_CELL_TYPE} macro. For the special case of cell
1289 entry 0 the writing of a Scheme object into this cell is only allowed
1290 if the cell forms a Scheme pair. For convenience, the following macros
1294 SCM_SET_CELL_OBJECT_0 (@var{x}, @var{o}) @result{} SCM_SET_CELL_OBJECT
1295 (@var{x}, 0, @var{o})
1297 SCM_SET_CELL_OBJECT_1 (@var{x}, @var{o}) @result{} SCM_SET_CELL_OBJECT
1298 (@var{x}, 1, @var{o})
1302 SCM_SET_CELL_OBJECT_@var{n} (@var{x}, @var{o}) @result{}
1303 SCM_SET_CELL_OBJECT (@var{x}, @var{n}, @var{o})
1311 For a non-immediate Scheme object @var{x} of unknown type, get the type
1312 information by using @code{SCM_CELL_TYPE (@var{x})}.
1314 As soon as the cell type information is available, only use the
1315 appropriate access methods to read and write data to the different cell
1320 @node Basic Rules for Accessing Cell Entries
1321 @subsubsection Basic Rules for Accessing Cell Entries
1323 For each cell type it is generally up to the implementation of that type
1324 which of the corresponding cell entries hold Scheme objects and which
1325 hold raw C values. However, there is one basic rule that has to be
1326 followed: Scheme pairs consist of exactly two cell entries, which both
1327 contain Scheme objects. Further, a cell which contains a Scheme object
1328 in it first entry has to be a Scheme pair. In other words, it is not
1329 allowed to store a Scheme object in the first cell entry and a non
1330 Scheme object in the second cell entry.
1332 @c Fixme:shouldn't this rather be SCM_PAIRP / SCM_PAIR_P ?
1333 @deftypefn Macro int SCM_CONSP (SCM @var{x})
1334 Determine, whether the Scheme object @var{x} is a Scheme pair,
1335 i.e. whether @var{x} references a heap cell consisting of exactly two
1336 entries, where both entries contain a Scheme object. In this case, both
1337 entries will have to be accessed using the @code{SCM_CELL_OBJECT}
1338 macros. On the contrary, if the @code{SCM_CONSP} predicate is not
1339 fulfilled, the first entry of the Scheme cell is guaranteed not to be a
1340 Scheme value and thus the first cell entry must be accessed using the
1341 @code{SCM_CELL_WORD_0} macro.
1346 @c TeX-master: "guile.texi"