api-compound.texi 136 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741274227432744274527462747274827492750275127522753275427552756275727582759276027612762276327642765276627672768276927702771277227732774277527762777277827792780278127822783278427852786278727882789279027912792279327942795279627972798279928002801280228032804280528062807280828092810281128122813281428152816281728182819282028212822282328242825282628272828282928302831283228332834283528362837283828392840284128422843284428452846284728482849285028512852285328542855285628572858285928602861286228632864286528662867286828692870287128722873287428752876287728782879288028812882288328842885288628872888288928902891289228932894289528962897289828992900290129022903290429052906290729082909291029112912291329142915291629172918291929202921292229232924292529262927292829292930293129322933293429352936293729382939294029412942294329442945294629472948294929502951295229532954295529562957295829592960296129622963296429652966296729682969297029712972297329742975297629772978297929802981298229832984298529862987298829892990299129922993299429952996299729982999300030013002300330043005300630073008300930103011301230133014301530163017301830193020302130223023302430253026302730283029303030313032303330343035303630373038303930403041304230433044304530463047304830493050305130523053305430553056305730583059306030613062306330643065306630673068306930703071307230733074307530763077307830793080308130823083308430853086308730883089309030913092309330943095309630973098309931003101310231033104310531063107310831093110311131123113311431153116311731183119312031213122312331243125312631273128312931303131313231333134313531363137313831393140314131423143314431453146314731483149315031513152315331543155315631573158315931603161316231633164316531663167316831693170317131723173317431753176317731783179318031813182318331843185318631873188318931903191319231933194319531963197319831993200320132023203320432053206320732083209321032113212321332143215321632173218321932203221322232233224322532263227322832293230323132323233323432353236323732383239324032413242324332443245324632473248324932503251325232533254325532563257325832593260326132623263326432653266326732683269327032713272327332743275327632773278327932803281328232833284328532863287328832893290329132923293329432953296329732983299330033013302330333043305330633073308330933103311331233133314331533163317331833193320332133223323332433253326332733283329333033313332333333343335333633373338333933403341334233433344334533463347334833493350335133523353335433553356335733583359336033613362336333643365336633673368336933703371337233733374337533763377337833793380338133823383338433853386338733883389339033913392339333943395339633973398339934003401340234033404340534063407340834093410341134123413341434153416341734183419342034213422342334243425342634273428342934303431343234333434343534363437343834393440344134423443344434453446344734483449345034513452345334543455345634573458345934603461346234633464346534663467346834693470347134723473347434753476347734783479348034813482348334843485348634873488348934903491349234933494349534963497349834993500350135023503350435053506350735083509351035113512351335143515351635173518351935203521352235233524352535263527352835293530353135323533353435353536353735383539354035413542354335443545354635473548354935503551355235533554355535563557355835593560356135623563356435653566356735683569357035713572357335743575357635773578357935803581358235833584358535863587358835893590359135923593359435953596359735983599360036013602360336043605360636073608360936103611361236133614361536163617361836193620362136223623362436253626362736283629363036313632363336343635363636373638363936403641364236433644364536463647364836493650365136523653365436553656365736583659366036613662366336643665366636673668366936703671367236733674367536763677367836793680368136823683368436853686368736883689369036913692369336943695369636973698
  1. @c -*-texinfo-*-
  2. @c This is part of the GNU Guile Reference Manual.
  3. @c Copyright (C) 1996, 1997, 2000, 2001, 2002, 2003, 2004, 2005, 2006,
  4. @c 2007, 2009, 2010, 2011 Free Software Foundation, Inc.
  5. @c See the file guile.texi for copying conditions.
  6. @node Compound Data Types
  7. @section Compound Data Types
  8. This chapter describes Guile's compound data types. By @dfn{compound}
  9. we mean that the primary purpose of these data types is to act as
  10. containers for other kinds of data (including other compound objects).
  11. For instance, a (non-uniform) vector with length 5 is a container that
  12. can hold five arbitrary Scheme objects.
  13. The various kinds of container object differ from each other in how
  14. their memory is allocated, how they are indexed, and how particular
  15. values can be looked up within them.
  16. @menu
  17. * Pairs:: Scheme's basic building block.
  18. * Lists:: Special list functions supported by Guile.
  19. * Vectors:: One-dimensional arrays of Scheme objects.
  20. * Bit Vectors:: Vectors of bits.
  21. * Generalized Vectors:: Treating all vector-like things uniformly.
  22. * Arrays:: Matrices, etc.
  23. * VLists:: Vector-like lists.
  24. * Records::
  25. * Structures::
  26. * Dictionary Types:: About dictionary types in general.
  27. * Association Lists:: List-based dictionaries.
  28. * VHashes:: VList-based dictionaries.
  29. * Hash Tables:: Table-based dictionaries.
  30. @end menu
  31. @node Pairs
  32. @subsection Pairs
  33. @tpindex Pairs
  34. Pairs are used to combine two Scheme objects into one compound object.
  35. Hence the name: A pair stores a pair of objects.
  36. The data type @dfn{pair} is extremely important in Scheme, just like in
  37. any other Lisp dialect. The reason is that pairs are not only used to
  38. make two values available as one object, but that pairs are used for
  39. constructing lists of values. Because lists are so important in Scheme,
  40. they are described in a section of their own (@pxref{Lists}).
  41. Pairs can literally get entered in source code or at the REPL, in the
  42. so-called @dfn{dotted list} syntax. This syntax consists of an opening
  43. parentheses, the first element of the pair, a dot, the second element
  44. and a closing parentheses. The following example shows how a pair
  45. consisting of the two numbers 1 and 2, and a pair containing the symbols
  46. @code{foo} and @code{bar} can be entered. It is very important to write
  47. the whitespace before and after the dot, because otherwise the Scheme
  48. parser would not be able to figure out where to split the tokens.
  49. @lisp
  50. (1 . 2)
  51. (foo . bar)
  52. @end lisp
  53. But beware, if you want to try out these examples, you have to
  54. @dfn{quote} the expressions. More information about quotation is
  55. available in the section @ref{Expression Syntax}. The correct way
  56. to try these examples is as follows.
  57. @lisp
  58. '(1 . 2)
  59. @result{}
  60. (1 . 2)
  61. '(foo . bar)
  62. @result{}
  63. (foo . bar)
  64. @end lisp
  65. A new pair is made by calling the procedure @code{cons} with two
  66. arguments. Then the argument values are stored into a newly allocated
  67. pair, and the pair is returned. The name @code{cons} stands for
  68. "construct". Use the procedure @code{pair?} to test whether a
  69. given Scheme object is a pair or not.
  70. @rnindex cons
  71. @deffn {Scheme Procedure} cons x y
  72. @deffnx {C Function} scm_cons (x, y)
  73. Return a newly allocated pair whose car is @var{x} and whose
  74. cdr is @var{y}. The pair is guaranteed to be different (in the
  75. sense of @code{eq?}) from every previously existing object.
  76. @end deffn
  77. @rnindex pair?
  78. @deffn {Scheme Procedure} pair? x
  79. @deffnx {C Function} scm_pair_p (x)
  80. Return @code{#t} if @var{x} is a pair; otherwise return
  81. @code{#f}.
  82. @end deffn
  83. @deftypefn {C Function} int scm_is_pair (SCM x)
  84. Return 1 when @var{x} is a pair; otherwise return 0.
  85. @end deftypefn
  86. The two parts of a pair are traditionally called @dfn{car} and
  87. @dfn{cdr}. They can be retrieved with procedures of the same name
  88. (@code{car} and @code{cdr}), and can be modified with the procedures
  89. @code{set-car!} and @code{set-cdr!}. Since a very common operation in
  90. Scheme programs is to access the car of a car of a pair, or the car of
  91. the cdr of a pair, etc., the procedures called @code{caar},
  92. @code{cadr} and so on are also predefined.
  93. @rnindex car
  94. @rnindex cdr
  95. @deffn {Scheme Procedure} car pair
  96. @deffnx {Scheme Procedure} cdr pair
  97. @deffnx {C Function} scm_car (pair)
  98. @deffnx {C Function} scm_cdr (pair)
  99. Return the car or the cdr of @var{pair}, respectively.
  100. @end deffn
  101. @deftypefn {C Macro} SCM SCM_CAR (SCM pair)
  102. @deftypefnx {C Macro} SCM SCM_CDR (SCM pair)
  103. These two macros are the fastest way to access the car or cdr of a
  104. pair; they can be thought of as compiling into a single memory
  105. reference.
  106. These macros do no checking at all. The argument @var{pair} must be a
  107. valid pair.
  108. @end deftypefn
  109. @deffn {Scheme Procedure} cddr pair
  110. @deffnx {Scheme Procedure} cdar pair
  111. @deffnx {Scheme Procedure} cadr pair
  112. @deffnx {Scheme Procedure} caar pair
  113. @deffnx {Scheme Procedure} cdddr pair
  114. @deffnx {Scheme Procedure} cddar pair
  115. @deffnx {Scheme Procedure} cdadr pair
  116. @deffnx {Scheme Procedure} cdaar pair
  117. @deffnx {Scheme Procedure} caddr pair
  118. @deffnx {Scheme Procedure} cadar pair
  119. @deffnx {Scheme Procedure} caadr pair
  120. @deffnx {Scheme Procedure} caaar pair
  121. @deffnx {Scheme Procedure} cddddr pair
  122. @deffnx {Scheme Procedure} cdddar pair
  123. @deffnx {Scheme Procedure} cddadr pair
  124. @deffnx {Scheme Procedure} cddaar pair
  125. @deffnx {Scheme Procedure} cdaddr pair
  126. @deffnx {Scheme Procedure} cdadar pair
  127. @deffnx {Scheme Procedure} cdaadr pair
  128. @deffnx {Scheme Procedure} cdaaar pair
  129. @deffnx {Scheme Procedure} cadddr pair
  130. @deffnx {Scheme Procedure} caddar pair
  131. @deffnx {Scheme Procedure} cadadr pair
  132. @deffnx {Scheme Procedure} cadaar pair
  133. @deffnx {Scheme Procedure} caaddr pair
  134. @deffnx {Scheme Procedure} caadar pair
  135. @deffnx {Scheme Procedure} caaadr pair
  136. @deffnx {Scheme Procedure} caaaar pair
  137. @deffnx {C Function} scm_cddr (pair)
  138. @deffnx {C Function} scm_cdar (pair)
  139. @deffnx {C Function} scm_cadr (pair)
  140. @deffnx {C Function} scm_caar (pair)
  141. @deffnx {C Function} scm_cdddr (pair)
  142. @deffnx {C Function} scm_cddar (pair)
  143. @deffnx {C Function} scm_cdadr (pair)
  144. @deffnx {C Function} scm_cdaar (pair)
  145. @deffnx {C Function} scm_caddr (pair)
  146. @deffnx {C Function} scm_cadar (pair)
  147. @deffnx {C Function} scm_caadr (pair)
  148. @deffnx {C Function} scm_caaar (pair)
  149. @deffnx {C Function} scm_cddddr (pair)
  150. @deffnx {C Function} scm_cdddar (pair)
  151. @deffnx {C Function} scm_cddadr (pair)
  152. @deffnx {C Function} scm_cddaar (pair)
  153. @deffnx {C Function} scm_cdaddr (pair)
  154. @deffnx {C Function} scm_cdadar (pair)
  155. @deffnx {C Function} scm_cdaadr (pair)
  156. @deffnx {C Function} scm_cdaaar (pair)
  157. @deffnx {C Function} scm_cadddr (pair)
  158. @deffnx {C Function} scm_caddar (pair)
  159. @deffnx {C Function} scm_cadadr (pair)
  160. @deffnx {C Function} scm_cadaar (pair)
  161. @deffnx {C Function} scm_caaddr (pair)
  162. @deffnx {C Function} scm_caadar (pair)
  163. @deffnx {C Function} scm_caaadr (pair)
  164. @deffnx {C Function} scm_caaaar (pair)
  165. These procedures are compositions of @code{car} and @code{cdr}, where
  166. for example @code{caddr} could be defined by
  167. @lisp
  168. (define caddr (lambda (x) (car (cdr (cdr x)))))
  169. @end lisp
  170. @code{cadr}, @code{caddr} and @code{cadddr} pick out the second, third
  171. or fourth elements of a list, respectively. SRFI-1 provides the same
  172. under the names @code{second}, @code{third} and @code{fourth}
  173. (@pxref{SRFI-1 Selectors}).
  174. @end deffn
  175. @rnindex set-car!
  176. @deffn {Scheme Procedure} set-car! pair value
  177. @deffnx {C Function} scm_set_car_x (pair, value)
  178. Stores @var{value} in the car field of @var{pair}. The value returned
  179. by @code{set-car!} is unspecified.
  180. @end deffn
  181. @rnindex set-cdr!
  182. @deffn {Scheme Procedure} set-cdr! pair value
  183. @deffnx {C Function} scm_set_cdr_x (pair, value)
  184. Stores @var{value} in the cdr field of @var{pair}. The value returned
  185. by @code{set-cdr!} is unspecified.
  186. @end deffn
  187. @node Lists
  188. @subsection Lists
  189. @tpindex Lists
  190. A very important data type in Scheme---as well as in all other Lisp
  191. dialects---is the data type @dfn{list}.@footnote{Strictly speaking,
  192. Scheme does not have a real datatype @dfn{list}. Lists are made up of
  193. @dfn{chained pairs}, and only exist by definition---a list is a chain
  194. of pairs which looks like a list.}
  195. This is the short definition of what a list is:
  196. @itemize @bullet
  197. @item
  198. Either the empty list @code{()},
  199. @item
  200. or a pair which has a list in its cdr.
  201. @end itemize
  202. @c FIXME::martin: Describe the pair chaining in more detail.
  203. @c FIXME::martin: What is a proper, what an improper list?
  204. @c What is a circular list?
  205. @c FIXME::martin: Maybe steal some graphics from the Elisp reference
  206. @c manual?
  207. @menu
  208. * List Syntax:: Writing literal lists.
  209. * List Predicates:: Testing lists.
  210. * List Constructors:: Creating new lists.
  211. * List Selection:: Selecting from lists, getting their length.
  212. * Append/Reverse:: Appending and reversing lists.
  213. * List Modification:: Modifying existing lists.
  214. * List Searching:: Searching for list elements
  215. * List Mapping:: Applying procedures to lists.
  216. @end menu
  217. @node List Syntax
  218. @subsubsection List Read Syntax
  219. The syntax for lists is an opening parentheses, then all the elements of
  220. the list (separated by whitespace) and finally a closing
  221. parentheses.@footnote{Note that there is no separation character between
  222. the list elements, like a comma or a semicolon.}.
  223. @lisp
  224. (1 2 3) ; @r{a list of the numbers 1, 2 and 3}
  225. ("foo" bar 3.1415) ; @r{a string, a symbol and a real number}
  226. () ; @r{the empty list}
  227. @end lisp
  228. The last example needs a bit more explanation. A list with no elements,
  229. called the @dfn{empty list}, is special in some ways. It is used for
  230. terminating lists by storing it into the cdr of the last pair that makes
  231. up a list. An example will clear that up:
  232. @lisp
  233. (car '(1))
  234. @result{}
  235. 1
  236. (cdr '(1))
  237. @result{}
  238. ()
  239. @end lisp
  240. This example also shows that lists have to be quoted when written
  241. (@pxref{Expression Syntax}), because they would otherwise be
  242. mistakingly taken as procedure applications (@pxref{Simple
  243. Invocation}).
  244. @node List Predicates
  245. @subsubsection List Predicates
  246. Often it is useful to test whether a given Scheme object is a list or
  247. not. List-processing procedures could use this information to test
  248. whether their input is valid, or they could do different things
  249. depending on the datatype of their arguments.
  250. @rnindex list?
  251. @deffn {Scheme Procedure} list? x
  252. @deffnx {C Function} scm_list_p (x)
  253. Return @code{#t} iff @var{x} is a proper list, else @code{#f}.
  254. @end deffn
  255. The predicate @code{null?} is often used in list-processing code to
  256. tell whether a given list has run out of elements. That is, a loop
  257. somehow deals with the elements of a list until the list satisfies
  258. @code{null?}. Then, the algorithm terminates.
  259. @rnindex null?
  260. @deffn {Scheme Procedure} null? x
  261. @deffnx {C Function} scm_null_p (x)
  262. Return @code{#t} iff @var{x} is the empty list, else @code{#f}.
  263. @end deffn
  264. @deftypefn {C Function} int scm_is_null (SCM x)
  265. Return 1 when @var{x} is the empty list; otherwise return 0.
  266. @end deftypefn
  267. @node List Constructors
  268. @subsubsection List Constructors
  269. This section describes the procedures for constructing new lists.
  270. @code{list} simply returns a list where the elements are the arguments,
  271. @code{cons*} is similar, but the last argument is stored in the cdr of
  272. the last pair of the list.
  273. @c C Function scm_list(rest) used to be documented here, but it's a
  274. @c no-op since it does nothing but return the list the caller must
  275. @c have already created.
  276. @c
  277. @deffn {Scheme Procedure} list elem @dots{}
  278. @deffnx {C Function} scm_list_1 (elem1)
  279. @deffnx {C Function} scm_list_2 (elem1, elem2)
  280. @deffnx {C Function} scm_list_3 (elem1, elem2, elem3)
  281. @deffnx {C Function} scm_list_4 (elem1, elem2, elem3, elem4)
  282. @deffnx {C Function} scm_list_5 (elem1, elem2, elem3, elem4, elem5)
  283. @deffnx {C Function} scm_list_n (elem1, @dots{}, elemN, @nicode{SCM_UNDEFINED})
  284. @rnindex list
  285. Return a new list containing elements @var{elem} @enddots{}.
  286. @code{scm_list_n} takes a variable number of arguments, terminated by
  287. the special @code{SCM_UNDEFINED}. That final @code{SCM_UNDEFINED} is
  288. not included in the list. None of @var{elem} @dots{} can
  289. themselves be @code{SCM_UNDEFINED}, or @code{scm_list_n} will
  290. terminate at that point.
  291. @end deffn
  292. @c C Function scm_cons_star(arg1,rest) used to be documented here,
  293. @c but it's not really a useful interface, since it expects the
  294. @c caller to have already consed up all but the first argument
  295. @c already.
  296. @c
  297. @deffn {Scheme Procedure} cons* arg1 arg2 @dots{}
  298. Like @code{list}, but the last arg provides the tail of the
  299. constructed list, returning @code{(cons @var{arg1} (cons
  300. @var{arg2} (cons @dots{} @var{argn})))}. Requires at least one
  301. argument. If given one argument, that argument is returned as
  302. result. This function is called @code{list*} in some other
  303. Schemes and in Common LISP.
  304. @end deffn
  305. @deffn {Scheme Procedure} list-copy lst
  306. @deffnx {C Function} scm_list_copy (lst)
  307. Return a (newly-created) copy of @var{lst}.
  308. @end deffn
  309. @deffn {Scheme Procedure} make-list n [init]
  310. Create a list containing of @var{n} elements, where each element is
  311. initialized to @var{init}. @var{init} defaults to the empty list
  312. @code{()} if not given.
  313. @end deffn
  314. Note that @code{list-copy} only makes a copy of the pairs which make up
  315. the spine of the lists. The list elements are not copied, which means
  316. that modifying the elements of the new list also modifies the elements
  317. of the old list. On the other hand, applying procedures like
  318. @code{set-cdr!} or @code{delv!} to the new list will not alter the old
  319. list. If you also need to copy the list elements (making a deep copy),
  320. use the procedure @code{copy-tree} (@pxref{Copying}).
  321. @node List Selection
  322. @subsubsection List Selection
  323. These procedures are used to get some information about a list, or to
  324. retrieve one or more elements of a list.
  325. @rnindex length
  326. @deffn {Scheme Procedure} length lst
  327. @deffnx {C Function} scm_length (lst)
  328. Return the number of elements in list @var{lst}.
  329. @end deffn
  330. @deffn {Scheme Procedure} last-pair lst
  331. @deffnx {C Function} scm_last_pair (lst)
  332. Return the last pair in @var{lst}, signalling an error if
  333. @var{lst} is circular.
  334. @end deffn
  335. @rnindex list-ref
  336. @deffn {Scheme Procedure} list-ref list k
  337. @deffnx {C Function} scm_list_ref (list, k)
  338. Return the @var{k}th element from @var{list}.
  339. @end deffn
  340. @rnindex list-tail
  341. @deffn {Scheme Procedure} list-tail lst k
  342. @deffnx {Scheme Procedure} list-cdr-ref lst k
  343. @deffnx {C Function} scm_list_tail (lst, k)
  344. Return the "tail" of @var{lst} beginning with its @var{k}th element.
  345. The first element of the list is considered to be element 0.
  346. @code{list-tail} and @code{list-cdr-ref} are identical. It may help to
  347. think of @code{list-cdr-ref} as accessing the @var{k}th cdr of the list,
  348. or returning the results of cdring @var{k} times down @var{lst}.
  349. @end deffn
  350. @deffn {Scheme Procedure} list-head lst k
  351. @deffnx {C Function} scm_list_head (lst, k)
  352. Copy the first @var{k} elements from @var{lst} into a new list, and
  353. return it.
  354. @end deffn
  355. @node Append/Reverse
  356. @subsubsection Append and Reverse
  357. @code{append} and @code{append!} are used to concatenate two or more
  358. lists in order to form a new list. @code{reverse} and @code{reverse!}
  359. return lists with the same elements as their arguments, but in reverse
  360. order. The procedure variants with an @code{!} directly modify the
  361. pairs which form the list, whereas the other procedures create new
  362. pairs. This is why you should be careful when using the side-effecting
  363. variants.
  364. @rnindex append
  365. @deffn {Scheme Procedure} append lst @dots{} obj
  366. @deffnx {Scheme Procedure} append
  367. @deffnx {Scheme Procedure} append! lst @dots{} obj
  368. @deffnx {Scheme Procedure} append!
  369. @deffnx {C Function} scm_append (lstlst)
  370. @deffnx {C Function} scm_append_x (lstlst)
  371. Return a list comprising all the elements of lists @var{lst} @dots{}
  372. @var{obj}. If called with no arguments, return the empty list.
  373. @lisp
  374. (append '(x) '(y)) @result{} (x y)
  375. (append '(a) '(b c d)) @result{} (a b c d)
  376. (append '(a (b)) '((c))) @result{} (a (b) (c))
  377. @end lisp
  378. The last argument @var{obj} may actually be any object; an improper
  379. list results if the last argument is not a proper list.
  380. @lisp
  381. (append '(a b) '(c . d)) @result{} (a b c . d)
  382. (append '() 'a) @result{} a
  383. @end lisp
  384. @code{append} doesn't modify the given lists, but the return may share
  385. structure with the final @var{obj}. @code{append!} modifies the
  386. given lists to form its return.
  387. For @code{scm_append} and @code{scm_append_x}, @var{lstlst} is a list
  388. of the list operands @var{lst} @dots{} @var{obj}. That @var{lstlst}
  389. itself is not modified or used in the return.
  390. @end deffn
  391. @rnindex reverse
  392. @deffn {Scheme Procedure} reverse lst
  393. @deffnx {Scheme Procedure} reverse! lst [newtail]
  394. @deffnx {C Function} scm_reverse (lst)
  395. @deffnx {C Function} scm_reverse_x (lst, newtail)
  396. Return a list comprising the elements of @var{lst}, in reverse order.
  397. @code{reverse} constructs a new list, @code{reverse!} modifies
  398. @var{lst} in constructing its return.
  399. For @code{reverse!}, the optional @var{newtail} is appended to the
  400. result. @var{newtail} isn't reversed, it simply becomes the list
  401. tail. For @code{scm_reverse_x}, the @var{newtail} parameter is
  402. mandatory, but can be @code{SCM_EOL} if no further tail is required.
  403. @end deffn
  404. @node List Modification
  405. @subsubsection List Modification
  406. The following procedures modify an existing list, either by changing
  407. elements of the list, or by changing the list structure itself.
  408. @deffn {Scheme Procedure} list-set! list k val
  409. @deffnx {C Function} scm_list_set_x (list, k, val)
  410. Set the @var{k}th element of @var{list} to @var{val}.
  411. @end deffn
  412. @deffn {Scheme Procedure} list-cdr-set! list k val
  413. @deffnx {C Function} scm_list_cdr_set_x (list, k, val)
  414. Set the @var{k}th cdr of @var{list} to @var{val}.
  415. @end deffn
  416. @deffn {Scheme Procedure} delq item lst
  417. @deffnx {C Function} scm_delq (item, lst)
  418. Return a newly-created copy of @var{lst} with elements
  419. @code{eq?} to @var{item} removed. This procedure mirrors
  420. @code{memq}: @code{delq} compares elements of @var{lst} against
  421. @var{item} with @code{eq?}.
  422. @end deffn
  423. @deffn {Scheme Procedure} delv item lst
  424. @deffnx {C Function} scm_delv (item, lst)
  425. Return a newly-created copy of @var{lst} with elements
  426. @code{eqv?} to @var{item} removed. This procedure mirrors
  427. @code{memv}: @code{delv} compares elements of @var{lst} against
  428. @var{item} with @code{eqv?}.
  429. @end deffn
  430. @deffn {Scheme Procedure} delete item lst
  431. @deffnx {C Function} scm_delete (item, lst)
  432. Return a newly-created copy of @var{lst} with elements
  433. @code{equal?} to @var{item} removed. This procedure mirrors
  434. @code{member}: @code{delete} compares elements of @var{lst}
  435. against @var{item} with @code{equal?}.
  436. See also SRFI-1 which has an extended @code{delete} (@ref{SRFI-1
  437. Deleting}), and also an @code{lset-difference} which can delete
  438. multiple @var{item}s in one call (@ref{SRFI-1 Set Operations}).
  439. @end deffn
  440. @deffn {Scheme Procedure} delq! item lst
  441. @deffnx {Scheme Procedure} delv! item lst
  442. @deffnx {Scheme Procedure} delete! item lst
  443. @deffnx {C Function} scm_delq_x (item, lst)
  444. @deffnx {C Function} scm_delv_x (item, lst)
  445. @deffnx {C Function} scm_delete_x (item, lst)
  446. These procedures are destructive versions of @code{delq}, @code{delv}
  447. and @code{delete}: they modify the pointers in the existing @var{lst}
  448. rather than creating a new list. Caveat evaluator: Like other
  449. destructive list functions, these functions cannot modify the binding of
  450. @var{lst}, and so cannot be used to delete the first element of
  451. @var{lst} destructively.
  452. @end deffn
  453. @deffn {Scheme Procedure} delq1! item lst
  454. @deffnx {C Function} scm_delq1_x (item, lst)
  455. Like @code{delq!}, but only deletes the first occurrence of
  456. @var{item} from @var{lst}. Tests for equality using
  457. @code{eq?}. See also @code{delv1!} and @code{delete1!}.
  458. @end deffn
  459. @deffn {Scheme Procedure} delv1! item lst
  460. @deffnx {C Function} scm_delv1_x (item, lst)
  461. Like @code{delv!}, but only deletes the first occurrence of
  462. @var{item} from @var{lst}. Tests for equality using
  463. @code{eqv?}. See also @code{delq1!} and @code{delete1!}.
  464. @end deffn
  465. @deffn {Scheme Procedure} delete1! item lst
  466. @deffnx {C Function} scm_delete1_x (item, lst)
  467. Like @code{delete!}, but only deletes the first occurrence of
  468. @var{item} from @var{lst}. Tests for equality using
  469. @code{equal?}. See also @code{delq1!} and @code{delv1!}.
  470. @end deffn
  471. @deffn {Scheme Procedure} filter pred lst
  472. @deffnx {Scheme Procedure} filter! pred lst
  473. Return a list containing all elements from @var{lst} which satisfy the
  474. predicate @var{pred}. The elements in the result list have the same
  475. order as in @var{lst}. The order in which @var{pred} is applied to
  476. the list elements is not specified.
  477. @code{filter} does not change @var{lst}, but the result may share a
  478. tail with it. @code{filter!} may modify @var{lst} to construct its
  479. return.
  480. @end deffn
  481. @node List Searching
  482. @subsubsection List Searching
  483. The following procedures search lists for particular elements. They use
  484. different comparison predicates for comparing list elements with the
  485. object to be searched. When they fail, they return @code{#f}, otherwise
  486. they return the sublist whose car is equal to the search object, where
  487. equality depends on the equality predicate used.
  488. @rnindex memq
  489. @deffn {Scheme Procedure} memq x lst
  490. @deffnx {C Function} scm_memq (x, lst)
  491. Return the first sublist of @var{lst} whose car is @code{eq?}
  492. to @var{x} where the sublists of @var{lst} are the non-empty
  493. lists returned by @code{(list-tail @var{lst} @var{k})} for
  494. @var{k} less than the length of @var{lst}. If @var{x} does not
  495. occur in @var{lst}, then @code{#f} (not the empty list) is
  496. returned.
  497. @end deffn
  498. @rnindex memv
  499. @deffn {Scheme Procedure} memv x lst
  500. @deffnx {C Function} scm_memv (x, lst)
  501. Return the first sublist of @var{lst} whose car is @code{eqv?}
  502. to @var{x} where the sublists of @var{lst} are the non-empty
  503. lists returned by @code{(list-tail @var{lst} @var{k})} for
  504. @var{k} less than the length of @var{lst}. If @var{x} does not
  505. occur in @var{lst}, then @code{#f} (not the empty list) is
  506. returned.
  507. @end deffn
  508. @rnindex member
  509. @deffn {Scheme Procedure} member x lst
  510. @deffnx {C Function} scm_member (x, lst)
  511. Return the first sublist of @var{lst} whose car is
  512. @code{equal?} to @var{x} where the sublists of @var{lst} are
  513. the non-empty lists returned by @code{(list-tail @var{lst}
  514. @var{k})} for @var{k} less than the length of @var{lst}. If
  515. @var{x} does not occur in @var{lst}, then @code{#f} (not the
  516. empty list) is returned.
  517. See also SRFI-1 which has an extended @code{member} function
  518. (@ref{SRFI-1 Searching}).
  519. @end deffn
  520. @node List Mapping
  521. @subsubsection List Mapping
  522. List processing is very convenient in Scheme because the process of
  523. iterating over the elements of a list can be highly abstracted. The
  524. procedures in this section are the most basic iterating procedures for
  525. lists. They take a procedure and one or more lists as arguments, and
  526. apply the procedure to each element of the list. They differ in their
  527. return value.
  528. @rnindex map
  529. @c begin (texi-doc-string "guile" "map")
  530. @deffn {Scheme Procedure} map proc arg1 arg2 @dots{}
  531. @deffnx {Scheme Procedure} map-in-order proc arg1 arg2 @dots{}
  532. @deffnx {C Function} scm_map (proc, arg1, args)
  533. Apply @var{proc} to each element of the list @var{arg1} (if only two
  534. arguments are given), or to the corresponding elements of the argument
  535. lists (if more than two arguments are given). The result(s) of the
  536. procedure applications are saved and returned in a list. For
  537. @code{map}, the order of procedure applications is not specified,
  538. @code{map-in-order} applies the procedure from left to right to the list
  539. elements.
  540. @end deffn
  541. @rnindex for-each
  542. @c begin (texi-doc-string "guile" "for-each")
  543. @deffn {Scheme Procedure} for-each proc arg1 arg2 @dots{}
  544. Like @code{map}, but the procedure is always applied from left to right,
  545. and the result(s) of the procedure applications are thrown away. The
  546. return value is not specified.
  547. @end deffn
  548. See also SRFI-1 which extends these functions to take lists of unequal
  549. lengths (@ref{SRFI-1 Fold and Map}).
  550. @node Vectors
  551. @subsection Vectors
  552. @tpindex Vectors
  553. Vectors are sequences of Scheme objects. Unlike lists, the length of a
  554. vector, once the vector is created, cannot be changed. The advantage of
  555. vectors over lists is that the time required to access one element of a vector
  556. given its @dfn{position} (synonymous with @dfn{index}), a zero-origin number,
  557. is constant, whereas lists have an access time linear to the position of the
  558. accessed element in the list.
  559. Vectors can contain any kind of Scheme object; it is even possible to
  560. have different types of objects in the same vector. For vectors
  561. containing vectors, you may wish to use arrays, instead. Note, too,
  562. that vectors are the special case of one dimensional non-uniform arrays
  563. and that most array procedures operate happily on vectors
  564. (@pxref{Arrays}).
  565. @menu
  566. * Vector Syntax:: Read syntax for vectors.
  567. * Vector Creation:: Dynamic vector creation and validation.
  568. * Vector Accessors:: Accessing and modifying vector contents.
  569. * Vector Accessing from C:: Ways to work with vectors from C.
  570. * Uniform Numeric Vectors:: Vectors of unboxed numeric values.
  571. @end menu
  572. @node Vector Syntax
  573. @subsubsection Read Syntax for Vectors
  574. Vectors can literally be entered in source code, just like strings,
  575. characters or some of the other data types. The read syntax for vectors
  576. is as follows: A sharp sign (@code{#}), followed by an opening
  577. parentheses, all elements of the vector in their respective read syntax,
  578. and finally a closing parentheses. The following are examples of the
  579. read syntax for vectors; where the first vector only contains numbers
  580. and the second three different object types: a string, a symbol and a
  581. number in hexadecimal notation.
  582. @lisp
  583. #(1 2 3)
  584. #("Hello" foo #xdeadbeef)
  585. @end lisp
  586. Like lists, vectors have to be quoted:
  587. @lisp
  588. '#(a b c) @result{} #(a b c)
  589. @end lisp
  590. @node Vector Creation
  591. @subsubsection Dynamic Vector Creation and Validation
  592. Instead of creating a vector implicitly by using the read syntax just
  593. described, you can create a vector dynamically by calling one of the
  594. @code{vector} and @code{list->vector} primitives with the list of Scheme
  595. values that you want to place into a vector. The size of the vector
  596. thus created is determined implicitly by the number of arguments given.
  597. @rnindex vector
  598. @rnindex list->vector
  599. @deffn {Scheme Procedure} vector arg @dots{}
  600. @deffnx {Scheme Procedure} list->vector l
  601. @deffnx {C Function} scm_vector (l)
  602. Return a newly allocated vector composed of the
  603. given arguments. Analogous to @code{list}.
  604. @lisp
  605. (vector 'a 'b 'c) @result{} #(a b c)
  606. @end lisp
  607. @end deffn
  608. The inverse operation is @code{vector->list}:
  609. @rnindex vector->list
  610. @deffn {Scheme Procedure} vector->list v
  611. @deffnx {C Function} scm_vector_to_list (v)
  612. Return a newly allocated list composed of the elements of @var{v}.
  613. @lisp
  614. (vector->list '#(dah dah didah)) @result{} (dah dah didah)
  615. (list->vector '(dididit dah)) @result{} #(dididit dah)
  616. @end lisp
  617. @end deffn
  618. To allocate a vector with an explicitly specified size, use
  619. @code{make-vector}. With this primitive you can also specify an initial
  620. value for the vector elements (the same value for all elements, that
  621. is):
  622. @rnindex make-vector
  623. @deffn {Scheme Procedure} make-vector len [fill]
  624. @deffnx {C Function} scm_make_vector (len, fill)
  625. Return a newly allocated vector of @var{len} elements. If a
  626. second argument is given, then each position is initialized to
  627. @var{fill}. Otherwise the initial contents of each position is
  628. unspecified.
  629. @end deffn
  630. @deftypefn {C Function} SCM scm_c_make_vector (size_t k, SCM fill)
  631. Like @code{scm_make_vector}, but the length is given as a @code{size_t}.
  632. @end deftypefn
  633. To check whether an arbitrary Scheme value @emph{is} a vector, use the
  634. @code{vector?} primitive:
  635. @rnindex vector?
  636. @deffn {Scheme Procedure} vector? obj
  637. @deffnx {C Function} scm_vector_p (obj)
  638. Return @code{#t} if @var{obj} is a vector, otherwise return
  639. @code{#f}.
  640. @end deffn
  641. @deftypefn {C Function} int scm_is_vector (SCM obj)
  642. Return non-zero when @var{obj} is a vector, otherwise return
  643. @code{zero}.
  644. @end deftypefn
  645. @node Vector Accessors
  646. @subsubsection Accessing and Modifying Vector Contents
  647. @code{vector-length} and @code{vector-ref} return information about a
  648. given vector, respectively its size and the elements that are contained
  649. in the vector.
  650. @rnindex vector-length
  651. @deffn {Scheme Procedure} vector-length vector
  652. @deffnx {C Function} scm_vector_length (vector)
  653. Return the number of elements in @var{vector} as an exact integer.
  654. @end deffn
  655. @deftypefn {C Function} size_t scm_c_vector_length (SCM vec)
  656. Return the number of elements in @var{vec} as a @code{size_t}.
  657. @end deftypefn
  658. @rnindex vector-ref
  659. @deffn {Scheme Procedure} vector-ref vec k
  660. @deffnx {C Function} scm_vector_ref (vec, k)
  661. Return the contents of position @var{k} of @var{vec}.
  662. @var{k} must be a valid index of @var{vec}.
  663. @lisp
  664. (vector-ref '#(1 1 2 3 5 8 13 21) 5) @result{} 8
  665. (vector-ref '#(1 1 2 3 5 8 13 21)
  666. (let ((i (round (* 2 (acos -1)))))
  667. (if (inexact? i)
  668. (inexact->exact i)
  669. i))) @result{} 13
  670. @end lisp
  671. @end deffn
  672. @deftypefn {C Function} SCM scm_c_vector_ref (SCM vec, size_t k)
  673. Return the contents of position @var{k} (a @code{size_t}) of
  674. @var{vec}.
  675. @end deftypefn
  676. A vector created by one of the dynamic vector constructor procedures
  677. (@pxref{Vector Creation}) can be modified using the following
  678. procedures.
  679. @emph{NOTE:} According to R5RS, it is an error to use any of these
  680. procedures on a literally read vector, because such vectors should be
  681. considered as constants. Currently, however, Guile does not detect this
  682. error.
  683. @rnindex vector-set!
  684. @deffn {Scheme Procedure} vector-set! vec k obj
  685. @deffnx {C Function} scm_vector_set_x (vec, k, obj)
  686. Store @var{obj} in position @var{k} of @var{vec}.
  687. @var{k} must be a valid index of @var{vec}.
  688. The value returned by @samp{vector-set!} is unspecified.
  689. @lisp
  690. (let ((vec (vector 0 '(2 2 2 2) "Anna")))
  691. (vector-set! vec 1 '("Sue" "Sue"))
  692. vec) @result{} #(0 ("Sue" "Sue") "Anna")
  693. @end lisp
  694. @end deffn
  695. @deftypefn {C Function} void scm_c_vector_set_x (SCM vec, size_t k, SCM obj)
  696. Store @var{obj} in position @var{k} (a @code{size_t}) of @var{vec}.
  697. @end deftypefn
  698. @rnindex vector-fill!
  699. @deffn {Scheme Procedure} vector-fill! vec fill
  700. @deffnx {C Function} scm_vector_fill_x (vec, fill)
  701. Store @var{fill} in every position of @var{vec}. The value
  702. returned by @code{vector-fill!} is unspecified.
  703. @end deffn
  704. @deffn {Scheme Procedure} vector-copy vec
  705. @deffnx {C Function} scm_vector_copy (vec)
  706. Return a copy of @var{vec}.
  707. @end deffn
  708. @deffn {Scheme Procedure} vector-move-left! vec1 start1 end1 vec2 start2
  709. @deffnx {C Function} scm_vector_move_left_x (vec1, start1, end1, vec2, start2)
  710. Copy elements from @var{vec1}, positions @var{start1} to @var{end1},
  711. to @var{vec2} starting at position @var{start2}. @var{start1} and
  712. @var{start2} are inclusive indices; @var{end1} is exclusive.
  713. @code{vector-move-left!} copies elements in leftmost order.
  714. Therefore, in the case where @var{vec1} and @var{vec2} refer to the
  715. same vector, @code{vector-move-left!} is usually appropriate when
  716. @var{start1} is greater than @var{start2}.
  717. @end deffn
  718. @deffn {Scheme Procedure} vector-move-right! vec1 start1 end1 vec2 start2
  719. @deffnx {C Function} scm_vector_move_right_x (vec1, start1, end1, vec2, start2)
  720. Copy elements from @var{vec1}, positions @var{start1} to @var{end1},
  721. to @var{vec2} starting at position @var{start2}. @var{start1} and
  722. @var{start2} are inclusive indices; @var{end1} is exclusive.
  723. @code{vector-move-right!} copies elements in rightmost order.
  724. Therefore, in the case where @var{vec1} and @var{vec2} refer to the
  725. same vector, @code{vector-move-right!} is usually appropriate when
  726. @var{start1} is less than @var{start2}.
  727. @end deffn
  728. @node Vector Accessing from C
  729. @subsubsection Vector Accessing from C
  730. A vector can be read and modified from C with the functions
  731. @code{scm_c_vector_ref} and @code{scm_c_vector_set_x}, for example. In
  732. addition to these functions, there are two more ways to access vectors
  733. from C that might be more efficient in certain situations: you can
  734. restrict yourself to @dfn{simple vectors} and then use the very fast
  735. @emph{simple vector macros}; or you can use the very general framework
  736. for accessing all kinds of arrays (@pxref{Accessing Arrays from C}),
  737. which is more verbose, but can deal efficiently with all kinds of
  738. vectors (and arrays). For vectors, you can use the
  739. @code{scm_vector_elements} and @code{scm_vector_writable_elements}
  740. functions as shortcuts.
  741. @deftypefn {C Function} int scm_is_simple_vector (SCM obj)
  742. Return non-zero if @var{obj} is a simple vector, else return zero. A
  743. simple vector is a vector that can be used with the @code{SCM_SIMPLE_*}
  744. macros below.
  745. The following functions are guaranteed to return simple vectors:
  746. @code{scm_make_vector}, @code{scm_c_make_vector}, @code{scm_vector},
  747. @code{scm_list_to_vector}.
  748. @end deftypefn
  749. @deftypefn {C Macro} size_t SCM_SIMPLE_VECTOR_LENGTH (SCM vec)
  750. Evaluates to the length of the simple vector @var{vec}. No type
  751. checking is done.
  752. @end deftypefn
  753. @deftypefn {C Macro} SCM SCM_SIMPLE_VECTOR_REF (SCM vec, size_t idx)
  754. Evaluates to the element at position @var{idx} in the simple vector
  755. @var{vec}. No type or range checking is done.
  756. @end deftypefn
  757. @deftypefn {C Macro} void SCM_SIMPLE_VECTOR_SET (SCM vec, size_t idx, SCM val)
  758. Sets the element at position @var{idx} in the simple vector
  759. @var{vec} to @var{val}. No type or range checking is done.
  760. @end deftypefn
  761. @deftypefn {C Function} {const SCM *} scm_vector_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
  762. Acquire a handle for the vector @var{vec} and return a pointer to the
  763. elements of it. This pointer can only be used to read the elements of
  764. @var{vec}. When @var{vec} is not a vector, an error is signaled. The
  765. handle must eventually be released with
  766. @code{scm_array_handle_release}.
  767. The variables pointed to by @var{lenp} and @var{incp} are filled with
  768. the number of elements of the vector and the increment (number of
  769. elements) between successive elements, respectively. Successive
  770. elements of @var{vec} need not be contiguous in their underlying
  771. ``root vector'' returned here; hence the increment is not necessarily
  772. equal to 1 and may well be negative too (@pxref{Shared Arrays}).
  773. The following example shows the typical way to use this function. It
  774. creates a list of all elements of @var{vec} (in reverse order).
  775. @example
  776. scm_t_array_handle handle;
  777. size_t i, len;
  778. ssize_t inc;
  779. const SCM *elt;
  780. SCM list;
  781. elt = scm_vector_elements (vec, &handle, &len, &inc);
  782. list = SCM_EOL;
  783. for (i = 0; i < len; i++, elt += inc)
  784. list = scm_cons (*elt, list);
  785. scm_array_handle_release (&handle);
  786. @end example
  787. @end deftypefn
  788. @deftypefn {C Function} {SCM *} scm_vector_writable_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
  789. Like @code{scm_vector_elements} but the pointer can be used to modify
  790. the vector.
  791. The following example shows the typical way to use this function. It
  792. fills a vector with @code{#t}.
  793. @example
  794. scm_t_array_handle handle;
  795. size_t i, len;
  796. ssize_t inc;
  797. SCM *elt;
  798. elt = scm_vector_writable_elements (vec, &handle, &len, &inc);
  799. for (i = 0; i < len; i++, elt += inc)
  800. *elt = SCM_BOOL_T;
  801. scm_array_handle_release (&handle);
  802. @end example
  803. @end deftypefn
  804. @node Uniform Numeric Vectors
  805. @subsubsection Uniform Numeric Vectors
  806. A uniform numeric vector is a vector whose elements are all of a single
  807. numeric type. Guile offers uniform numeric vectors for signed and
  808. unsigned 8-bit, 16-bit, 32-bit, and 64-bit integers, two sizes of
  809. floating point values, and complex floating-point numbers of these two
  810. sizes. @xref{SRFI-4}, for more information.
  811. For many purposes, bytevectors work just as well as uniform vectors, and have
  812. the advantage that they integrate well with binary input and output.
  813. @xref{Bytevectors}, for more information on bytevectors.
  814. @node Bit Vectors
  815. @subsection Bit Vectors
  816. @noindent
  817. Bit vectors are zero-origin, one-dimensional arrays of booleans. They
  818. are displayed as a sequence of @code{0}s and @code{1}s prefixed by
  819. @code{#*}, e.g.,
  820. @example
  821. (make-bitvector 8 #f) @result{}
  822. #*00000000
  823. @end example
  824. Bit vectors are also generalized vectors, @xref{Generalized
  825. Vectors}, and can thus be used with the array procedures, @xref{Arrays}.
  826. Bit vectors are the special case of one dimensional bit arrays.
  827. @deffn {Scheme Procedure} bitvector? obj
  828. @deffnx {C Function} scm_bitvector_p (obj)
  829. Return @code{#t} when @var{obj} is a bitvector, else
  830. return @code{#f}.
  831. @end deffn
  832. @deftypefn {C Function} int scm_is_bitvector (SCM obj)
  833. Return @code{1} when @var{obj} is a bitvector, else return @code{0}.
  834. @end deftypefn
  835. @deffn {Scheme Procedure} make-bitvector len [fill]
  836. @deffnx {C Function} scm_make_bitvector (len, fill)
  837. Create a new bitvector of length @var{len} and
  838. optionally initialize all elements to @var{fill}.
  839. @end deffn
  840. @deftypefn {C Function} SCM scm_c_make_bitvector (size_t len, SCM fill)
  841. Like @code{scm_make_bitvector}, but the length is given as a
  842. @code{size_t}.
  843. @end deftypefn
  844. @deffn {Scheme Procedure} bitvector bit @dots{}
  845. @deffnx {C Function} scm_bitvector (bits)
  846. Create a new bitvector with the arguments as elements.
  847. @end deffn
  848. @deffn {Scheme Procedure} bitvector-length vec
  849. @deffnx {C Function} scm_bitvector_length (vec)
  850. Return the length of the bitvector @var{vec}.
  851. @end deffn
  852. @deftypefn {C Function} size_t scm_c_bitvector_length (SCM vec)
  853. Like @code{scm_bitvector_length}, but the length is returned as a
  854. @code{size_t}.
  855. @end deftypefn
  856. @deffn {Scheme Procedure} bitvector-ref vec idx
  857. @deffnx {C Function} scm_bitvector_ref (vec, idx)
  858. Return the element at index @var{idx} of the bitvector
  859. @var{vec}.
  860. @end deffn
  861. @deftypefn {C Function} SCM scm_c_bitvector_ref (SCM vec, size_t idx)
  862. Return the element at index @var{idx} of the bitvector
  863. @var{vec}.
  864. @end deftypefn
  865. @deffn {Scheme Procedure} bitvector-set! vec idx val
  866. @deffnx {C Function} scm_bitvector_set_x (vec, idx, val)
  867. Set the element at index @var{idx} of the bitvector
  868. @var{vec} when @var{val} is true, else clear it.
  869. @end deffn
  870. @deftypefn {C Function} SCM scm_c_bitvector_set_x (SCM vec, size_t idx, SCM val)
  871. Set the element at index @var{idx} of the bitvector
  872. @var{vec} when @var{val} is true, else clear it.
  873. @end deftypefn
  874. @deffn {Scheme Procedure} bitvector-fill! vec val
  875. @deffnx {C Function} scm_bitvector_fill_x (vec, val)
  876. Set all elements of the bitvector
  877. @var{vec} when @var{val} is true, else clear them.
  878. @end deffn
  879. @deffn {Scheme Procedure} list->bitvector list
  880. @deffnx {C Function} scm_list_to_bitvector (list)
  881. Return a new bitvector initialized with the elements
  882. of @var{list}.
  883. @end deffn
  884. @deffn {Scheme Procedure} bitvector->list vec
  885. @deffnx {C Function} scm_bitvector_to_list (vec)
  886. Return a new list initialized with the elements
  887. of the bitvector @var{vec}.
  888. @end deffn
  889. @deffn {Scheme Procedure} bit-count bool bitvector
  890. @deffnx {C Function} scm_bit_count (bool, bitvector)
  891. Return a count of how many entries in @var{bitvector} are equal to
  892. @var{bool}. For example,
  893. @example
  894. (bit-count #f #*000111000) @result{} 6
  895. @end example
  896. @end deffn
  897. @deffn {Scheme Procedure} bit-position bool bitvector start
  898. @deffnx {C Function} scm_bit_position (bool, bitvector, start)
  899. Return the index of the first occurrence of @var{bool} in
  900. @var{bitvector}, starting from @var{start}. If there is no @var{bool}
  901. entry between @var{start} and the end of @var{bitvector}, then return
  902. @code{#f}. For example,
  903. @example
  904. (bit-position #t #*000101 0) @result{} 3
  905. (bit-position #f #*0001111 3) @result{} #f
  906. @end example
  907. @end deffn
  908. @deffn {Scheme Procedure} bit-invert! bitvector
  909. @deffnx {C Function} scm_bit_invert_x (bitvector)
  910. Modify @var{bitvector} by replacing each element with its negation.
  911. @end deffn
  912. @deffn {Scheme Procedure} bit-set*! bitvector uvec bool
  913. @deffnx {C Function} scm_bit_set_star_x (bitvector, uvec, bool)
  914. Set entries of @var{bitvector} to @var{bool}, with @var{uvec}
  915. selecting the entries to change. The return value is unspecified.
  916. If @var{uvec} is a bit vector, then those entries where it has
  917. @code{#t} are the ones in @var{bitvector} which are set to @var{bool}.
  918. @var{uvec} and @var{bitvector} must be the same length. When
  919. @var{bool} is @code{#t} it's like @var{uvec} is OR'ed into
  920. @var{bitvector}. Or when @var{bool} is @code{#f} it can be seen as an
  921. ANDNOT.
  922. @example
  923. (define bv #*01000010)
  924. (bit-set*! bv #*10010001 #t)
  925. bv
  926. @result{} #*11010011
  927. @end example
  928. If @var{uvec} is a uniform vector of unsigned long integers, then
  929. they're indexes into @var{bitvector} which are set to @var{bool}.
  930. @example
  931. (define bv #*01000010)
  932. (bit-set*! bv #u(5 2 7) #t)
  933. bv
  934. @result{} #*01100111
  935. @end example
  936. @end deffn
  937. @deffn {Scheme Procedure} bit-count* bitvector uvec bool
  938. @deffnx {C Function} scm_bit_count_star (bitvector, uvec, bool)
  939. Return a count of how many entries in @var{bitvector} are equal to
  940. @var{bool}, with @var{uvec} selecting the entries to consider.
  941. @var{uvec} is interpreted in the same way as for @code{bit-set*!}
  942. above. Namely, if @var{uvec} is a bit vector then entries which have
  943. @code{#t} there are considered in @var{bitvector}. Or if @var{uvec}
  944. is a uniform vector of unsigned long integers then it's the indexes in
  945. @var{bitvector} to consider.
  946. For example,
  947. @example
  948. (bit-count* #*01110111 #*11001101 #t) @result{} 3
  949. (bit-count* #*01110111 #u(7 0 4) #f) @result{} 2
  950. @end example
  951. @end deffn
  952. @deftypefn {C Function} {const scm_t_uint32 *} scm_bitvector_elements (SCM vec, scm_t_array_handle *handle, size_t *offp, size_t *lenp, ssize_t *incp)
  953. Like @code{scm_vector_elements} (@pxref{Vector Accessing from C}), but
  954. for bitvectors. The variable pointed to by @var{offp} is set to the
  955. value returned by @code{scm_array_handle_bit_elements_offset}. See
  956. @code{scm_array_handle_bit_elements} for how to use the returned
  957. pointer and the offset.
  958. @end deftypefn
  959. @deftypefn {C Function} {scm_t_uint32 *} scm_bitvector_writable_elements (SCM vec, scm_t_array_handle *handle, size_t *offp, size_t *lenp, ssize_t *incp)
  960. Like @code{scm_bitvector_elements}, but the pointer is good for reading
  961. and writing.
  962. @end deftypefn
  963. @node Generalized Vectors
  964. @subsection Generalized Vectors
  965. Guile has a number of data types that are generally vector-like:
  966. strings, uniform numeric vectors, bytevectors, bitvectors, and of course
  967. ordinary vectors of arbitrary Scheme values. These types are disjoint:
  968. a Scheme value belongs to at most one of the five types listed above.
  969. If you want to gloss over this distinction and want to treat all four
  970. types with common code, you can use the procedures in this section.
  971. They work with the @emph{generalized vector} type, which is the union
  972. of the five vector-like types.
  973. @deffn {Scheme Procedure} generalized-vector? obj
  974. @deffnx {C Function} scm_generalized_vector_p (obj)
  975. Return @code{#t} if @var{obj} is a vector, bytevector, string,
  976. bitvector, or uniform numeric vector.
  977. @end deffn
  978. @deffn {Scheme Procedure} generalized-vector-length v
  979. @deffnx {C Function} scm_generalized_vector_length (v)
  980. Return the length of the generalized vector @var{v}.
  981. @end deffn
  982. @deffn {Scheme Procedure} generalized-vector-ref v idx
  983. @deffnx {C Function} scm_generalized_vector_ref (v, idx)
  984. Return the element at index @var{idx} of the
  985. generalized vector @var{v}.
  986. @end deffn
  987. @deffn {Scheme Procedure} generalized-vector-set! v idx val
  988. @deffnx {C Function} scm_generalized_vector_set_x (v, idx, val)
  989. Set the element at index @var{idx} of the
  990. generalized vector @var{v} to @var{val}.
  991. @end deffn
  992. @deffn {Scheme Procedure} generalized-vector->list v
  993. @deffnx {C Function} scm_generalized_vector_to_list (v)
  994. Return a new list whose elements are the elements of the
  995. generalized vector @var{v}.
  996. @end deffn
  997. @deftypefn {C Function} int scm_is_generalized_vector (SCM obj)
  998. Return @code{1} if @var{obj} is a vector, string,
  999. bitvector, or uniform numeric vector; else return @code{0}.
  1000. @end deftypefn
  1001. @deftypefn {C Function} size_t scm_c_generalized_vector_length (SCM v)
  1002. Return the length of the generalized vector @var{v}.
  1003. @end deftypefn
  1004. @deftypefn {C Function} SCM scm_c_generalized_vector_ref (SCM v, size_t idx)
  1005. Return the element at index @var{idx} of the generalized vector @var{v}.
  1006. @end deftypefn
  1007. @deftypefn {C Function} void scm_c_generalized_vector_set_x (SCM v, size_t idx, SCM val)
  1008. Set the element at index @var{idx} of the generalized vector @var{v}
  1009. to @var{val}.
  1010. @end deftypefn
  1011. @deftypefn {C Function} void scm_generalized_vector_get_handle (SCM v, scm_t_array_handle *handle)
  1012. Like @code{scm_array_get_handle} but an error is signalled when @var{v}
  1013. is not of rank one. You can use @code{scm_array_handle_ref} and
  1014. @code{scm_array_handle_set} to read and write the elements of @var{v},
  1015. or you can use functions like @code{scm_array_handle_<foo>_elements} to
  1016. deal with specific types of vectors.
  1017. @end deftypefn
  1018. @node Arrays
  1019. @subsection Arrays
  1020. @tpindex Arrays
  1021. @dfn{Arrays} are a collection of cells organized into an arbitrary
  1022. number of dimensions. Each cell can be accessed in constant time by
  1023. supplying an index for each dimension.
  1024. In the current implementation, an array uses a generalized vector for
  1025. the actual storage of its elements. Any kind of generalized vector
  1026. will do, so you can have arrays of uniform numeric values, arrays of
  1027. characters, arrays of bits, and of course, arrays of arbitrary Scheme
  1028. values. For example, arrays with an underlying @code{c64vector} might
  1029. be nice for digital signal processing, while arrays made from a
  1030. @code{u8vector} might be used to hold gray-scale images.
  1031. The number of dimensions of an array is called its @dfn{rank}. Thus,
  1032. a matrix is an array of rank 2, while a vector has rank 1. When
  1033. accessing an array element, you have to specify one exact integer for
  1034. each dimension. These integers are called the @dfn{indices} of the
  1035. element. An array specifies the allowed range of indices for each
  1036. dimension via an inclusive lower and upper bound. These bounds can
  1037. well be negative, but the upper bound must be greater than or equal to
  1038. the lower bound minus one. When all lower bounds of an array are
  1039. zero, it is called a @dfn{zero-origin} array.
  1040. Arrays can be of rank 0, which could be interpreted as a scalar.
  1041. Thus, a zero-rank array can store exactly one object and the list of
  1042. indices of this element is the empty list.
  1043. Arrays contain zero elements when one of their dimensions has a zero
  1044. length. These empty arrays maintain information about their shape: a
  1045. matrix with zero columns and 3 rows is different from a matrix with 3
  1046. columns and zero rows, which again is different from a vector of
  1047. length zero.
  1048. Generalized vectors, such as strings, uniform numeric vectors,
  1049. bytevectors, bit vectors and ordinary vectors, are the special case of
  1050. one dimensional arrays.
  1051. @menu
  1052. * Array Syntax::
  1053. * Array Procedures::
  1054. * Shared Arrays::
  1055. * Accessing Arrays from C::
  1056. @end menu
  1057. @node Array Syntax
  1058. @subsubsection Array Syntax
  1059. An array is displayed as @code{#} followed by its rank, followed by a
  1060. tag that describes the underlying vector, optionally followed by
  1061. information about its shape, and finally followed by the cells,
  1062. organized into dimensions using parentheses.
  1063. In more words, the array tag is of the form
  1064. @example
  1065. #<rank><vectag><@@lower><:len><@@lower><:len>...
  1066. @end example
  1067. where @code{<rank>} is a positive integer in decimal giving the rank of
  1068. the array. It is omitted when the rank is 1 and the array is non-shared
  1069. and has zero-origin (see below). For shared arrays and for a non-zero
  1070. origin, the rank is always printed even when it is 1 to distinguish
  1071. them from ordinary vectors.
  1072. The @code{<vectag>} part is the tag for a uniform numeric vector, like
  1073. @code{u8}, @code{s16}, etc, @code{b} for bitvectors, or @code{a} for
  1074. strings. It is empty for ordinary vectors.
  1075. The @code{<@@lower>} part is a @samp{@@} character followed by a signed
  1076. integer in decimal giving the lower bound of a dimension. There is one
  1077. @code{<@@lower>} for each dimension. When all lower bounds are zero,
  1078. all @code{<@@lower>} parts are omitted.
  1079. The @code{<:len>} part is a @samp{:} character followed by an unsigned
  1080. integer in decimal giving the length of a dimension. Like for the lower
  1081. bounds, there is one @code{<:len>} for each dimension, and the
  1082. @code{<:len>} part always follows the @code{<@@lower>} part for a
  1083. dimension. Lengths are only then printed when they can't be deduced
  1084. from the nested lists of elements of the array literal, which can happen
  1085. when at least one length is zero.
  1086. As a special case, an array of rank 0 is printed as
  1087. @code{#0<vectag>(<scalar>)}, where @code{<scalar>} is the result of
  1088. printing the single element of the array.
  1089. Thus,
  1090. @table @code
  1091. @item #(1 2 3)
  1092. is an ordinary array of rank 1 with lower bound 0 in dimension 0.
  1093. (I.e., a regular vector.)
  1094. @item #@@2(1 2 3)
  1095. is an ordinary array of rank 1 with lower bound 2 in dimension 0.
  1096. @item #2((1 2 3) (4 5 6))
  1097. is a non-uniform array of rank 2; a 3@cross{}3 matrix with index ranges 0..2
  1098. and 0..2.
  1099. @item #u32(0 1 2)
  1100. is a uniform u8 array of rank 1.
  1101. @item #2u32@@2@@3((1 2) (2 3))
  1102. is a uniform u8 array of rank 2 with index ranges 2..3 and 3..4.
  1103. @item #2()
  1104. is a two-dimensional array with index ranges 0..-1 and 0..-1, i.e.@:
  1105. both dimensions have length zero.
  1106. @item #2:0:2()
  1107. is a two-dimensional array with index ranges 0..-1 and 0..1, i.e.@: the
  1108. first dimension has length zero, but the second has length 2.
  1109. @item #0(12)
  1110. is a rank-zero array with contents 12.
  1111. @end table
  1112. In addition, bytevectors are also arrays, but use a different syntax
  1113. (@pxref{Bytevectors}):
  1114. @table @code
  1115. @item #vu8(1 2 3)
  1116. is a 3-byte long bytevector, with contents 1, 2, 3.
  1117. @end table
  1118. @node Array Procedures
  1119. @subsubsection Array Procedures
  1120. When an array is created, the range of each dimension must be
  1121. specified, e.g., to create a 2@cross{}3 array with a zero-based index:
  1122. @example
  1123. (make-array 'ho 2 3) @result{} #2((ho ho ho) (ho ho ho))
  1124. @end example
  1125. The range of each dimension can also be given explicitly, e.g., another
  1126. way to create the same array:
  1127. @example
  1128. (make-array 'ho '(0 1) '(0 2)) @result{} #2((ho ho ho) (ho ho ho))
  1129. @end example
  1130. The following procedures can be used with arrays (or vectors). An
  1131. argument shown as @var{idx}@dots{} means one parameter for each
  1132. dimension in the array. A @var{idxlist} argument means a list of such
  1133. values, one for each dimension.
  1134. @deffn {Scheme Procedure} array? obj
  1135. @deffnx {C Function} scm_array_p (obj, unused)
  1136. Return @code{#t} if the @var{obj} is an array, and @code{#f} if
  1137. not.
  1138. The second argument to scm_array_p is there for historical reasons,
  1139. but it is not used. You should always pass @code{SCM_UNDEFINED} as
  1140. its value.
  1141. @end deffn
  1142. @deffn {Scheme Procedure} typed-array? obj type
  1143. @deffnx {C Function} scm_typed_array_p (obj, type)
  1144. Return @code{#t} if the @var{obj} is an array of type @var{type}, and
  1145. @code{#f} if not.
  1146. @end deffn
  1147. @deftypefn {C Function} int scm_is_array (SCM obj)
  1148. Return @code{1} if the @var{obj} is an array and @code{0} if not.
  1149. @end deftypefn
  1150. @deftypefn {C Function} int scm_is_typed_array (SCM obj, SCM type)
  1151. Return @code{0} if the @var{obj} is an array of type @var{type}, and
  1152. @code{1} if not.
  1153. @end deftypefn
  1154. @deffn {Scheme Procedure} make-array fill bound @dots{}
  1155. @deffnx {C Function} scm_make_array (fill, bounds)
  1156. Equivalent to @code{(make-typed-array #t @var{fill} @var{bound} ...)}.
  1157. @end deffn
  1158. @deffn {Scheme Procedure} make-typed-array type fill bound @dots{}
  1159. @deffnx {C Function} scm_make_typed_array (type, fill, bounds)
  1160. Create and return an array that has as many dimensions as there are
  1161. @var{bound}s and (maybe) fill it with @var{fill}.
  1162. The underlying storage vector is created according to @var{type},
  1163. which must be a symbol whose name is the `vectag' of the array as
  1164. explained above, or @code{#t} for ordinary, non-specialized arrays.
  1165. For example, using the symbol @code{f64} for @var{type} will create an
  1166. array that uses a @code{f64vector} for storing its elements, and
  1167. @code{a} will use a string.
  1168. When @var{fill} is not the special @emph{unspecified} value, the new
  1169. array is filled with @var{fill}. Otherwise, the initial contents of
  1170. the array is unspecified. The special @emph{unspecified} value is
  1171. stored in the variable @code{*unspecified*} so that for example
  1172. @code{(make-typed-array 'u32 *unspecified* 4)} creates a uninitialized
  1173. @code{u32} vector of length 4.
  1174. Each @var{bound} may be a positive non-zero integer @var{n}, in which
  1175. case the index for that dimension can range from 0 through @var{n}-1; or
  1176. an explicit index range specifier in the form @code{(LOWER UPPER)},
  1177. where both @var{lower} and @var{upper} are integers, possibly less than
  1178. zero, and possibly the same number (however, @var{lower} cannot be
  1179. greater than @var{upper}).
  1180. @end deffn
  1181. @deffn {Scheme Procedure} list->array dimspec list
  1182. Equivalent to @code{(list->typed-array #t @var{dimspec}
  1183. @var{list})}.
  1184. @end deffn
  1185. @deffn {Scheme Procedure} list->typed-array type dimspec list
  1186. @deffnx {C Function} scm_list_to_typed_array (type, dimspec, list)
  1187. Return an array of the type indicated by @var{type} with elements the
  1188. same as those of @var{list}.
  1189. The argument @var{dimspec} determines the number of dimensions of the
  1190. array and their lower bounds. When @var{dimspec} is an exact integer,
  1191. it gives the number of dimensions directly and all lower bounds are
  1192. zero. When it is a list of exact integers, then each element is the
  1193. lower index bound of a dimension, and there will be as many dimensions
  1194. as elements in the list.
  1195. @end deffn
  1196. @deffn {Scheme Procedure} array-type array
  1197. Return the type of @var{array}. This is the `vectag' used for
  1198. printing @var{array} (or @code{#t} for ordinary arrays) and can be
  1199. used with @code{make-typed-array} to create an array of the same kind
  1200. as @var{array}.
  1201. @end deffn
  1202. @deffn {Scheme Procedure} array-ref array idx @dots{}
  1203. Return the element at @code{(idx @dots{})} in @var{array}.
  1204. @example
  1205. (define a (make-array 999 '(1 2) '(3 4)))
  1206. (array-ref a 2 4) @result{} 999
  1207. @end example
  1208. @end deffn
  1209. @deffn {Scheme Procedure} array-in-bounds? array idx @dots{}
  1210. @deffnx {C Function} scm_array_in_bounds_p (array, idxlist)
  1211. Return @code{#t} if the given index would be acceptable to
  1212. @code{array-ref}.
  1213. @example
  1214. (define a (make-array #f '(1 2) '(3 4)))
  1215. (array-in-bounds? a 2 3) @result{} #t
  1216. (array-in-bounds? a 0 0) @result{} #f
  1217. @end example
  1218. @end deffn
  1219. @deffn {Scheme Procedure} array-set! array obj idx @dots{}
  1220. @deffnx {C Function} scm_array_set_x (array, obj, idxlist)
  1221. Set the element at @code{(idx @dots{})} in @var{array} to @var{obj}.
  1222. The return value is unspecified.
  1223. @example
  1224. (define a (make-array #f '(0 1) '(0 1)))
  1225. (array-set! a #t 1 1)
  1226. a @result{} #2((#f #f) (#f #t))
  1227. @end example
  1228. @end deffn
  1229. @deffn {Scheme Procedure} array-shape array
  1230. @deffnx {Scheme Procedure} array-dimensions array
  1231. @deffnx {C Function} scm_array_dimensions (array)
  1232. Return a list of the bounds for each dimension of @var{array}.
  1233. @code{array-shape} gives @code{(@var{lower} @var{upper})} for each
  1234. dimension. @code{array-dimensions} instead returns just
  1235. @math{@var{upper}+1} for dimensions with a 0 lower bound. Both are
  1236. suitable as input to @code{make-array}.
  1237. For example,
  1238. @example
  1239. (define a (make-array 'foo '(-1 3) 5))
  1240. (array-shape a) @result{} ((-1 3) (0 4))
  1241. (array-dimensions a) @result{} ((-1 3) 5)
  1242. @end example
  1243. @end deffn
  1244. @deffn {Scheme Procedure} array-rank array
  1245. @deffnx {C Function} scm_array_rank (array)
  1246. Return the rank of @var{array}.
  1247. @end deffn
  1248. @deftypefn {C Function} size_t scm_c_array_rank (SCM array)
  1249. Return the rank of @var{array} as a @code{size_t}.
  1250. @end deftypefn
  1251. @deffn {Scheme Procedure} array->list array
  1252. @deffnx {C Function} scm_array_to_list (array)
  1253. Return a list consisting of all the elements, in order, of
  1254. @var{array}.
  1255. @end deffn
  1256. @c FIXME: Describe how the order affects the copying (it matters for
  1257. @c shared arrays with the same underlying root vector, presumably).
  1258. @c
  1259. @deffn {Scheme Procedure} array-copy! src dst
  1260. @deffnx {Scheme Procedure} array-copy-in-order! src dst
  1261. @deffnx {C Function} scm_array_copy_x (src, dst)
  1262. Copy every element from vector or array @var{src} to the corresponding
  1263. element of @var{dst}. @var{dst} must have the same rank as @var{src},
  1264. and be at least as large in each dimension. The return value is
  1265. unspecified.
  1266. @end deffn
  1267. @deffn {Scheme Procedure} array-fill! array fill
  1268. @deffnx {C Function} scm_array_fill_x (array, fill)
  1269. Store @var{fill} in every element of @var{array}. The value returned
  1270. is unspecified.
  1271. @end deffn
  1272. @c begin (texi-doc-string "guile" "array-equal?")
  1273. @deffn {Scheme Procedure} array-equal? array @dots{}
  1274. Return @code{#t} if all arguments are arrays with the same shape, the
  1275. same type, and have corresponding elements which are either
  1276. @code{equal?} or @code{array-equal?}. This function differs from
  1277. @code{equal?} (@pxref{Equality}) in that all arguments must be arrays.
  1278. @end deffn
  1279. @c FIXME: array-map! accepts no source arrays at all, and in that
  1280. @c case makes calls "(proc)". Is that meant to be a documented
  1281. @c feature?
  1282. @c
  1283. @c FIXME: array-for-each doesn't say what happens if the sources have
  1284. @c different index ranges. The code currently iterates over the
  1285. @c indices of the first and expects the others to cover those. That
  1286. @c at least vaguely matches array-map!, but is it meant to be a
  1287. @c documented feature?
  1288. @deffn {Scheme Procedure} array-map! dst proc src @dots{}
  1289. @deffnx {Scheme Procedure} array-map-in-order! dst proc src1 @dots{} srcN
  1290. @deffnx {C Function} scm_array_map_x (dst, proc, srclist)
  1291. Set each element of the @var{dst} array to values obtained from calls
  1292. to @var{proc}. The value returned is unspecified.
  1293. Each call is @code{(@var{proc} @var{elem1} @dots{} @var{elemN})},
  1294. where each @var{elem} is from the corresponding @var{src} array, at
  1295. the @var{dst} index. @code{array-map-in-order!} makes the calls in
  1296. row-major order, @code{array-map!} makes them in an unspecified order.
  1297. The @var{src} arrays must have the same number of dimensions as
  1298. @var{dst}, and must have a range for each dimension which covers the
  1299. range in @var{dst}. This ensures all @var{dst} indices are valid in
  1300. each @var{src}.
  1301. @end deffn
  1302. @deffn {Scheme Procedure} array-for-each proc src1 src2 @dots{}
  1303. @deffnx {C Function} scm_array_for_each (proc, src1, srclist)
  1304. Apply @var{proc} to each tuple of elements of @var{src1} @var{src2}
  1305. @dots{}, in row-major order. The value returned is unspecified.
  1306. @end deffn
  1307. @deffn {Scheme Procedure} array-index-map! dst proc
  1308. @deffnx {C Function} scm_array_index_map_x (dst, proc)
  1309. Set each element of the @var{dst} array to values returned by calls to
  1310. @var{proc}. The value returned is unspecified.
  1311. Each call is @code{(@var{proc} @var{i1} @dots{} @var{iN})}, where
  1312. @var{i1}@dots{}@var{iN} is the destination index, one parameter for
  1313. each dimension. The order in which the calls are made is unspecified.
  1314. For example, to create a @m{4\times4, 4x4} matrix representing a
  1315. cyclic group,
  1316. @tex
  1317. \advance\leftskip by 2\lispnarrowing {
  1318. $\left(\matrix{%
  1319. 0 & 1 & 2 & 3 \cr
  1320. 1 & 2 & 3 & 0 \cr
  1321. 2 & 3 & 0 & 1 \cr
  1322. 3 & 0 & 1 & 2 \cr
  1323. }\right)$} \par
  1324. @end tex
  1325. @ifnottex
  1326. @example
  1327. / 0 1 2 3 \
  1328. | 1 2 3 0 |
  1329. | 2 3 0 1 |
  1330. \ 3 0 1 2 /
  1331. @end example
  1332. @end ifnottex
  1333. @example
  1334. (define a (make-array #f 4 4))
  1335. (array-index-map! a (lambda (i j)
  1336. (modulo (+ i j) 4)))
  1337. @end example
  1338. @end deffn
  1339. @deffn {Scheme Procedure} uniform-array-read! ra [port_or_fd [start [end]]]
  1340. @deffnx {C Function} scm_uniform_array_read_x (ra, port_or_fd, start, end)
  1341. Attempt to read all elements of array @var{ra}, in lexicographic order, as
  1342. binary objects from @var{port_or_fd}.
  1343. If an end of file is encountered,
  1344. the objects up to that point are put into @var{ra}
  1345. (starting at the beginning) and the remainder of the array is
  1346. unchanged.
  1347. The optional arguments @var{start} and @var{end} allow
  1348. a specified region of a vector (or linearized array) to be read,
  1349. leaving the remainder of the vector unchanged.
  1350. @code{uniform-array-read!} returns the number of objects read.
  1351. @var{port_or_fd} may be omitted, in which case it defaults to the value
  1352. returned by @code{(current-input-port)}.
  1353. @end deffn
  1354. @deffn {Scheme Procedure} uniform-array-write ra [port_or_fd [start [end]]]
  1355. @deffnx {C Function} scm_uniform_array_write (ra, port_or_fd, start, end)
  1356. Writes all elements of @var{ra} as binary objects to
  1357. @var{port_or_fd}.
  1358. The optional arguments @var{start}
  1359. and @var{end} allow
  1360. a specified region of a vector (or linearized array) to be written.
  1361. The number of objects actually written is returned.
  1362. @var{port_or_fd} may be
  1363. omitted, in which case it defaults to the value returned by
  1364. @code{(current-output-port)}.
  1365. @end deffn
  1366. @node Shared Arrays
  1367. @subsubsection Shared Arrays
  1368. @deffn {Scheme Procedure} make-shared-array oldarray mapfunc bound @dots{}
  1369. @deffnx {C Function} scm_make_shared_array (oldarray, mapfunc, boundlist)
  1370. Return a new array which shares the storage of @var{oldarray}.
  1371. Changes made through either affect the same underlying storage. The
  1372. @var{bound} @dots{} arguments are the shape of the new array, the same
  1373. as @code{make-array} (@pxref{Array Procedures}).
  1374. @var{mapfunc} translates coordinates from the new array to the
  1375. @var{oldarray}. It's called as @code{(@var{mapfunc} newidx1 @dots{})}
  1376. with one parameter for each dimension of the new array, and should
  1377. return a list of indices for @var{oldarray}, one for each dimension of
  1378. @var{oldarray}.
  1379. @var{mapfunc} must be affine linear, meaning that each @var{oldarray}
  1380. index must be formed by adding integer multiples (possibly negative)
  1381. of some or all of @var{newidx1} etc, plus a possible integer offset.
  1382. The multiples and offset must be the same in each call.
  1383. @sp 1
  1384. One good use for a shared array is to restrict the range of some
  1385. dimensions, so as to apply say @code{array-for-each} or
  1386. @code{array-fill!} to only part of an array. The plain @code{list}
  1387. function can be used for @var{mapfunc} in this case, making no changes
  1388. to the index values. For example,
  1389. @example
  1390. (make-shared-array #2((a b c) (d e f) (g h i)) list 3 2)
  1391. @result{} #2((a b) (d e) (g h))
  1392. @end example
  1393. The new array can have fewer dimensions than @var{oldarray}, for
  1394. example to take a column from an array.
  1395. @example
  1396. (make-shared-array #2((a b c) (d e f) (g h i))
  1397. (lambda (i) (list i 2))
  1398. '(0 2))
  1399. @result{} #1(c f i)
  1400. @end example
  1401. A diagonal can be taken by using the single new array index for both
  1402. row and column in the old array. For example,
  1403. @example
  1404. (make-shared-array #2((a b c) (d e f) (g h i))
  1405. (lambda (i) (list i i))
  1406. '(0 2))
  1407. @result{} #1(a e i)
  1408. @end example
  1409. Dimensions can be increased by for instance considering portions of a
  1410. one dimensional array as rows in a two dimensional array.
  1411. (@code{array-contents} below can do the opposite, flattening an
  1412. array.)
  1413. @example
  1414. (make-shared-array #1(a b c d e f g h i j k l)
  1415. (lambda (i j) (list (+ (* i 3) j)))
  1416. 4 3)
  1417. @result{} #2((a b c) (d e f) (g h i) (j k l))
  1418. @end example
  1419. By negating an index the order that elements appear can be reversed.
  1420. The following just reverses the column order,
  1421. @example
  1422. (make-shared-array #2((a b c) (d e f) (g h i))
  1423. (lambda (i j) (list i (- 2 j)))
  1424. 3 3)
  1425. @result{} #2((c b a) (f e d) (i h g))
  1426. @end example
  1427. A fixed offset on indexes allows for instance a change from a 0 based
  1428. to a 1 based array,
  1429. @example
  1430. (define x #2((a b c) (d e f) (g h i)))
  1431. (define y (make-shared-array x
  1432. (lambda (i j) (list (1- i) (1- j)))
  1433. '(1 3) '(1 3)))
  1434. (array-ref x 0 0) @result{} a
  1435. (array-ref y 1 1) @result{} a
  1436. @end example
  1437. A multiple on an index allows every Nth element of an array to be
  1438. taken. The following is every third element,
  1439. @example
  1440. (make-shared-array #1(a b c d e f g h i j k l)
  1441. (lambda (i) (list (* i 3)))
  1442. 4)
  1443. @result{} #1(a d g j)
  1444. @end example
  1445. The above examples can be combined to make weird and wonderful
  1446. selections from an array, but it's important to note that because
  1447. @var{mapfunc} must be affine linear, arbitrary permutations are not
  1448. possible.
  1449. In the current implementation, @var{mapfunc} is not called for every
  1450. access to the new array but only on some sample points to establish a
  1451. base and stride for new array indices in @var{oldarray} data. A few
  1452. sample points are enough because @var{mapfunc} is linear.
  1453. @end deffn
  1454. @deffn {Scheme Procedure} shared-array-increments array
  1455. @deffnx {C Function} scm_shared_array_increments (array)
  1456. For each dimension, return the distance between elements in the root vector.
  1457. @end deffn
  1458. @deffn {Scheme Procedure} shared-array-offset array
  1459. @deffnx {C Function} scm_shared_array_offset (array)
  1460. Return the root vector index of the first element in the array.
  1461. @end deffn
  1462. @deffn {Scheme Procedure} shared-array-root array
  1463. @deffnx {C Function} scm_shared_array_root (array)
  1464. Return the root vector of a shared array.
  1465. @end deffn
  1466. @deffn {Scheme Procedure} array-contents array [strict]
  1467. @deffnx {C Function} scm_array_contents (array, strict)
  1468. If @var{array} may be @dfn{unrolled} into a one dimensional shared array
  1469. without changing their order (last subscript changing fastest), then
  1470. @code{array-contents} returns that shared array, otherwise it returns
  1471. @code{#f}. All arrays made by @code{make-array} and
  1472. @code{make-typed-array} may be unrolled, some arrays made by
  1473. @code{make-shared-array} may not be.
  1474. If the optional argument @var{strict} is provided, a shared array will
  1475. be returned only if its elements are stored internally contiguous in
  1476. memory.
  1477. @end deffn
  1478. @deffn {Scheme Procedure} transpose-array array dim1 dim2 @dots{}
  1479. @deffnx {C Function} scm_transpose_array (array, dimlist)
  1480. Return an array sharing contents with @var{array}, but with
  1481. dimensions arranged in a different order. There must be one
  1482. @var{dim} argument for each dimension of @var{array}.
  1483. @var{dim1}, @var{dim2}, @dots{} should be integers between 0
  1484. and the rank of the array to be returned. Each integer in that
  1485. range must appear at least once in the argument list.
  1486. The values of @var{dim1}, @var{dim2}, @dots{} correspond to
  1487. dimensions in the array to be returned, and their positions in the
  1488. argument list to dimensions of @var{array}. Several @var{dim}s
  1489. may have the same value, in which case the returned array will
  1490. have smaller rank than @var{array}.
  1491. @lisp
  1492. (transpose-array '#2((a b) (c d)) 1 0) @result{} #2((a c) (b d))
  1493. (transpose-array '#2((a b) (c d)) 0 0) @result{} #1(a d)
  1494. (transpose-array '#3(((a b c) (d e f)) ((1 2 3) (4 5 6))) 1 1 0) @result{}
  1495. #2((a 4) (b 5) (c 6))
  1496. @end lisp
  1497. @end deffn
  1498. @node Accessing Arrays from C
  1499. @subsubsection Accessing Arrays from C
  1500. For interworking with external C code, Guile provides an API to allow C
  1501. code to access the elements of a Scheme array. In particular, for
  1502. uniform numeric arrays, the API exposes the underlying uniform data as a
  1503. C array of numbers of the relevant type.
  1504. While pointers to the elements of an array are in use, the array itself
  1505. must be protected so that the pointer remains valid. Such a protected
  1506. array is said to be @dfn{reserved}. A reserved array can be read but
  1507. modifications to it that would cause the pointer to its elements to
  1508. become invalid are prevented. When you attempt such a modification, an
  1509. error is signalled.
  1510. (This is similar to locking the array while it is in use, but without
  1511. the danger of a deadlock. In a multi-threaded program, you will need
  1512. additional synchronization to avoid modifying reserved arrays.)
  1513. You must take care to always unreserve an array after reserving it,
  1514. even in the presence of non-local exits. If a non-local exit can
  1515. happen between these two calls, you should install a dynwind context
  1516. that releases the array when it is left (@pxref{Dynamic Wind}).
  1517. In addition, array reserving and unreserving must be properly
  1518. paired. For instance, when reserving two or more arrays in a certain
  1519. order, you need to unreserve them in the opposite order.
  1520. Once you have reserved an array and have retrieved the pointer to its
  1521. elements, you must figure out the layout of the elements in memory.
  1522. Guile allows slices to be taken out of arrays without actually making a
  1523. copy, such as making an alias for the diagonal of a matrix that can be
  1524. treated as a vector. Arrays that result from such an operation are not
  1525. stored contiguously in memory and when working with their elements
  1526. directly, you need to take this into account.
  1527. The layout of array elements in memory can be defined via a
  1528. @emph{mapping function} that computes a scalar position from a vector of
  1529. indices. The scalar position then is the offset of the element with the
  1530. given indices from the start of the storage block of the array.
  1531. In Guile, this mapping function is restricted to be @dfn{affine}: all
  1532. mapping functions of Guile arrays can be written as @code{p = b +
  1533. c[0]*i[0] + c[1]*i[1] + ... + c[n-1]*i[n-1]} where @code{i[k]} is the
  1534. @nicode{k}th index and @code{n} is the rank of the array. For
  1535. example, a matrix of size 3x3 would have @code{b == 0}, @code{c[0] ==
  1536. 3} and @code{c[1] == 1}. When you transpose this matrix (with
  1537. @code{transpose-array}, say), you will get an array whose mapping
  1538. function has @code{b == 0}, @code{c[0] == 1} and @code{c[1] == 3}.
  1539. The function @code{scm_array_handle_dims} gives you (indirect) access to
  1540. the coefficients @code{c[k]}.
  1541. @c XXX
  1542. Note that there are no functions for accessing the elements of a
  1543. character array yet. Once the string implementation of Guile has been
  1544. changed to use Unicode, we will provide them.
  1545. @deftp {C Type} scm_t_array_handle
  1546. This is a structure type that holds all information necessary to manage
  1547. the reservation of arrays as explained above. Structures of this type
  1548. must be allocated on the stack and must only be accessed by the
  1549. functions listed below.
  1550. @end deftp
  1551. @deftypefn {C Function} void scm_array_get_handle (SCM array, scm_t_array_handle *handle)
  1552. Reserve @var{array}, which must be an array, and prepare @var{handle} to
  1553. be used with the functions below. You must eventually call
  1554. @code{scm_array_handle_release} on @var{handle}, and do this in a
  1555. properly nested fashion, as explained above. The structure pointed to
  1556. by @var{handle} does not need to be initialized before calling this
  1557. function.
  1558. @end deftypefn
  1559. @deftypefn {C Function} void scm_array_handle_release (scm_t_array_handle *handle)
  1560. End the array reservation represented by @var{handle}. After a call to
  1561. this function, @var{handle} might be used for another reservation.
  1562. @end deftypefn
  1563. @deftypefn {C Function} size_t scm_array_handle_rank (scm_t_array_handle *handle)
  1564. Return the rank of the array represented by @var{handle}.
  1565. @end deftypefn
  1566. @deftp {C Type} scm_t_array_dim
  1567. This structure type holds information about the layout of one dimension
  1568. of an array. It includes the following fields:
  1569. @table @code
  1570. @item ssize_t lbnd
  1571. @itemx ssize_t ubnd
  1572. The lower and upper bounds (both inclusive) of the permissible index
  1573. range for the given dimension. Both values can be negative, but
  1574. @var{lbnd} is always less than or equal to @var{ubnd}.
  1575. @item ssize_t inc
  1576. The distance from one element of this dimension to the next. Note, too,
  1577. that this can be negative.
  1578. @end table
  1579. @end deftp
  1580. @deftypefn {C Function} {const scm_t_array_dim *} scm_array_handle_dims (scm_t_array_handle *handle)
  1581. Return a pointer to a C vector of information about the dimensions of
  1582. the array represented by @var{handle}. This pointer is valid as long as
  1583. the array remains reserved. As explained above, the
  1584. @code{scm_t_array_dim} structures returned by this function can be used
  1585. calculate the position of an element in the storage block of the array
  1586. from its indices.
  1587. This position can then be used as an index into the C array pointer
  1588. returned by the various @code{scm_array_handle_<foo>_elements}
  1589. functions, or with @code{scm_array_handle_ref} and
  1590. @code{scm_array_handle_set}.
  1591. Here is how one can compute the position @var{pos} of an element given
  1592. its indices in the vector @var{indices}:
  1593. @example
  1594. ssize_t indices[RANK];
  1595. scm_t_array_dim *dims;
  1596. ssize_t pos;
  1597. size_t i;
  1598. pos = 0;
  1599. for (i = 0; i < RANK; i++)
  1600. @{
  1601. if (indices[i] < dims[i].lbnd || indices[i] > dims[i].ubnd)
  1602. out_of_range ();
  1603. pos += (indices[i] - dims[i].lbnd) * dims[i].inc;
  1604. @}
  1605. @end example
  1606. @end deftypefn
  1607. @deftypefn {C Function} ssize_t scm_array_handle_pos (scm_t_array_handle *handle, SCM indices)
  1608. Compute the position corresponding to @var{indices}, a list of
  1609. indices. The position is computed as described above for
  1610. @code{scm_array_handle_dims}. The number of the indices and their
  1611. range is checked and an appropriate error is signalled for invalid
  1612. indices.
  1613. @end deftypefn
  1614. @deftypefn {C Function} SCM scm_array_handle_ref (scm_t_array_handle *handle, ssize_t pos)
  1615. Return the element at position @var{pos} in the storage block of the
  1616. array represented by @var{handle}. Any kind of array is acceptable. No
  1617. range checking is done on @var{pos}.
  1618. @end deftypefn
  1619. @deftypefn {C Function} void scm_array_handle_set (scm_t_array_handle *handle, ssize_t pos, SCM val)
  1620. Set the element at position @var{pos} in the storage block of the array
  1621. represented by @var{handle} to @var{val}. Any kind of array is
  1622. acceptable. No range checking is done on @var{pos}. An error is
  1623. signalled when the array can not store @var{val}.
  1624. @end deftypefn
  1625. @deftypefn {C Function} {const SCM *} scm_array_handle_elements (scm_t_array_handle *handle)
  1626. Return a pointer to the elements of a ordinary array of general Scheme
  1627. values (i.e., a non-uniform array) for reading. This pointer is valid
  1628. as long as the array remains reserved.
  1629. @end deftypefn
  1630. @deftypefn {C Function} {SCM *} scm_array_handle_writable_elements (scm_t_array_handle *handle)
  1631. Like @code{scm_array_handle_elements}, but the pointer is good for
  1632. reading and writing.
  1633. @end deftypefn
  1634. @deftypefn {C Function} {const void *} scm_array_handle_uniform_elements (scm_t_array_handle *handle)
  1635. Return a pointer to the elements of a uniform numeric array for reading.
  1636. This pointer is valid as long as the array remains reserved. The size
  1637. of each element is given by @code{scm_array_handle_uniform_element_size}.
  1638. @end deftypefn
  1639. @deftypefn {C Function} {void *} scm_array_handle_uniform_writable_elements (scm_t_array_handle *handle)
  1640. Like @code{scm_array_handle_uniform_elements}, but the pointer is good
  1641. reading and writing.
  1642. @end deftypefn
  1643. @deftypefn {C Function} size_t scm_array_handle_uniform_element_size (scm_t_array_handle *handle)
  1644. Return the size of one element of the uniform numeric array represented
  1645. by @var{handle}.
  1646. @end deftypefn
  1647. @deftypefn {C Function} {const scm_t_uint8 *} scm_array_handle_u8_elements (scm_t_array_handle *handle)
  1648. @deftypefnx {C Function} {const scm_t_int8 *} scm_array_handle_s8_elements (scm_t_array_handle *handle)
  1649. @deftypefnx {C Function} {const scm_t_uint16 *} scm_array_handle_u16_elements (scm_t_array_handle *handle)
  1650. @deftypefnx {C Function} {const scm_t_int16 *} scm_array_handle_s16_elements (scm_t_array_handle *handle)
  1651. @deftypefnx {C Function} {const scm_t_uint32 *} scm_array_handle_u32_elements (scm_t_array_handle *handle)
  1652. @deftypefnx {C Function} {const scm_t_int32 *} scm_array_handle_s32_elements (scm_t_array_handle *handle)
  1653. @deftypefnx {C Function} {const scm_t_uint64 *} scm_array_handle_u64_elements (scm_t_array_handle *handle)
  1654. @deftypefnx {C Function} {const scm_t_int64 *} scm_array_handle_s64_elements (scm_t_array_handle *handle)
  1655. @deftypefnx {C Function} {const float *} scm_array_handle_f32_elements (scm_t_array_handle *handle)
  1656. @deftypefnx {C Function} {const double *} scm_array_handle_f64_elements (scm_t_array_handle *handle)
  1657. @deftypefnx {C Function} {const float *} scm_array_handle_c32_elements (scm_t_array_handle *handle)
  1658. @deftypefnx {C Function} {const double *} scm_array_handle_c64_elements (scm_t_array_handle *handle)
  1659. Return a pointer to the elements of a uniform numeric array of the
  1660. indicated kind for reading. This pointer is valid as long as the array
  1661. remains reserved.
  1662. The pointers for @code{c32} and @code{c64} uniform numeric arrays point
  1663. to pairs of floating point numbers. The even index holds the real part,
  1664. the odd index the imaginary part of the complex number.
  1665. @end deftypefn
  1666. @deftypefn {C Function} {scm_t_uint8 *} scm_array_handle_u8_writable_elements (scm_t_array_handle *handle)
  1667. @deftypefnx {C Function} {scm_t_int8 *} scm_array_handle_s8_writable_elements (scm_t_array_handle *handle)
  1668. @deftypefnx {C Function} {scm_t_uint16 *} scm_array_handle_u16_writable_elements (scm_t_array_handle *handle)
  1669. @deftypefnx {C Function} {scm_t_int16 *} scm_array_handle_s16_writable_elements (scm_t_array_handle *handle)
  1670. @deftypefnx {C Function} {scm_t_uint32 *} scm_array_handle_u32_writable_elements (scm_t_array_handle *handle)
  1671. @deftypefnx {C Function} {scm_t_int32 *} scm_array_handle_s32_writable_elements (scm_t_array_handle *handle)
  1672. @deftypefnx {C Function} {scm_t_uint64 *} scm_array_handle_u64_writable_elements (scm_t_array_handle *handle)
  1673. @deftypefnx {C Function} {scm_t_int64 *} scm_array_handle_s64_writable_elements (scm_t_array_handle *handle)
  1674. @deftypefnx {C Function} {float *} scm_array_handle_f32_writable_elements (scm_t_array_handle *handle)
  1675. @deftypefnx {C Function} {double *} scm_array_handle_f64_writable_elements (scm_t_array_handle *handle)
  1676. @deftypefnx {C Function} {float *} scm_array_handle_c32_writable_elements (scm_t_array_handle *handle)
  1677. @deftypefnx {C Function} {double *} scm_array_handle_c64_writable_elements (scm_t_array_handle *handle)
  1678. Like @code{scm_array_handle_<kind>_elements}, but the pointer is good
  1679. for reading and writing.
  1680. @end deftypefn
  1681. @deftypefn {C Function} {const scm_t_uint32 *} scm_array_handle_bit_elements (scm_t_array_handle *handle)
  1682. Return a pointer to the words that store the bits of the represented
  1683. array, which must be a bit array.
  1684. Unlike other arrays, bit arrays have an additional offset that must be
  1685. figured into index calculations. That offset is returned by
  1686. @code{scm_array_handle_bit_elements_offset}.
  1687. To find a certain bit you first need to calculate its position as
  1688. explained above for @code{scm_array_handle_dims} and then add the
  1689. offset. This gives the absolute position of the bit, which is always a
  1690. non-negative integer.
  1691. Each word of the bit array storage block contains exactly 32 bits, with
  1692. the least significant bit in that word having the lowest absolute
  1693. position number. The next word contains the next 32 bits.
  1694. Thus, the following code can be used to access a bit whose position
  1695. according to @code{scm_array_handle_dims} is given in @var{pos}:
  1696. @example
  1697. SCM bit_array;
  1698. scm_t_array_handle handle;
  1699. scm_t_uint32 *bits;
  1700. ssize_t pos;
  1701. size_t abs_pos;
  1702. size_t word_pos, mask;
  1703. scm_array_get_handle (&bit_array, &handle);
  1704. bits = scm_array_handle_bit_elements (&handle);
  1705. pos = ...
  1706. abs_pos = pos + scm_array_handle_bit_elements_offset (&handle);
  1707. word_pos = abs_pos / 32;
  1708. mask = 1L << (abs_pos % 32);
  1709. if (bits[word_pos] & mask)
  1710. /* bit is set. */
  1711. scm_array_handle_release (&handle);
  1712. @end example
  1713. @end deftypefn
  1714. @deftypefn {C Function} {scm_t_uint32 *} scm_array_handle_bit_writable_elements (scm_t_array_handle *handle)
  1715. Like @code{scm_array_handle_bit_elements} but the pointer is good for
  1716. reading and writing. You must take care not to modify bits outside of
  1717. the allowed index range of the array, even for contiguous arrays.
  1718. @end deftypefn
  1719. @node VLists
  1720. @subsection VLists
  1721. @cindex vlist
  1722. The @code{(ice-9 vlist)} module provides an implementation of the @dfn{VList}
  1723. data structure designed by Phil Bagwell in 2002. VLists are immutable lists,
  1724. which can contain any Scheme object. They improve on standard Scheme linked
  1725. lists in several areas:
  1726. @itemize
  1727. @item
  1728. Random access has typically constant-time complexity.
  1729. @item
  1730. Computing the length of a VList has time complexity logarithmic in the number of
  1731. elements.
  1732. @item
  1733. VLists use less storage space than standard lists.
  1734. @item
  1735. VList elements are stored in contiguous regions, which improves memory locality
  1736. and leads to more efficient use of hardware caches.
  1737. @end itemize
  1738. The idea behind VLists is to store vlist elements in increasingly large
  1739. contiguous blocks (implemented as vectors here). These blocks are linked to one
  1740. another using a pointer to the next block and an offset within that block. The
  1741. size of these blocks form a geometric series with ratio
  1742. @code{block-growth-factor} (2 by default).
  1743. The VList structure also serves as the basis for the @dfn{VList-based hash
  1744. lists} or ``vhashes'', an immutable dictionary type (@pxref{VHashes}).
  1745. However, the current implementation in @code{(ice-9 vlist)} has several
  1746. noteworthy shortcomings:
  1747. @itemize
  1748. @item
  1749. It is @emph{not} thread-safe. Although operations on vlists are all
  1750. @dfn{referentially transparent} (i.e., purely functional), adding elements to a
  1751. vlist with @code{vlist-cons} mutates part of its internal structure, which makes
  1752. it non-thread-safe. This could be fixed, but it would slow down
  1753. @code{vlist-cons}.
  1754. @item
  1755. @code{vlist-cons} always allocates at least as much memory as @code{cons}.
  1756. Again, Phil Bagwell describes how to fix it, but that would require tuning the
  1757. garbage collector in a way that may not be generally beneficial.
  1758. @item
  1759. @code{vlist-cons} is a Scheme procedure compiled to bytecode, and it does not
  1760. compete with the straightforward C implementation of @code{cons}, and with the
  1761. fact that the VM has a special @code{cons} instruction.
  1762. @end itemize
  1763. We hope to address these in the future.
  1764. The programming interface exported by @code{(ice-9 vlist)} is defined below.
  1765. Most of it is the same as SRFI-1 with an added @code{vlist-} prefix to function
  1766. names.
  1767. @deffn {Scheme Procedure} vlist? obj
  1768. Return true if @var{obj} is a VList.
  1769. @end deffn
  1770. @defvr {Scheme Variable} vlist-null
  1771. The empty VList. Note that it's possible to create an empty VList not
  1772. @code{eq?} to @code{vlist-null}; thus, callers should always use
  1773. @code{vlist-null?} when testing whether a VList is empty.
  1774. @end defvr
  1775. @deffn {Scheme Procedure} vlist-null? vlist
  1776. Return true if @var{vlist} is empty.
  1777. @end deffn
  1778. @deffn {Scheme Procedure} vlist-cons item vlist
  1779. Return a new vlist with @var{item} as its head and @var{vlist} as its tail.
  1780. @end deffn
  1781. @deffn {Scheme Procedure} vlist-head vlist
  1782. Return the head of @var{vlist}.
  1783. @end deffn
  1784. @deffn {Scheme Procedure} vlist-tail vlist
  1785. Return the tail of @var{vlist}.
  1786. @end deffn
  1787. @defvr {Scheme Variable} block-growth-factor
  1788. A fluid that defines the growth factor of VList blocks, 2 by default.
  1789. @end defvr
  1790. The functions below provide the usual set of higher-level list operations.
  1791. @deffn {Scheme Procedure} vlist-fold proc init vlist
  1792. @deffnx {Scheme Procedure} vlist-fold-right proc init vlist
  1793. Fold over @var{vlist}, calling @var{proc} for each element, as for SRFI-1
  1794. @code{fold} and @code{fold-right} (@pxref{SRFI-1, @code{fold}}).
  1795. @end deffn
  1796. @deffn {Scheme Procedure} vlist-ref vlist index
  1797. Return the element at index @var{index} in @var{vlist}. This is typically a
  1798. constant-time operation.
  1799. @end deffn
  1800. @deffn {Scheme Procedure} vlist-length vlist
  1801. Return the length of @var{vlist}. This is typically logarithmic in the number
  1802. of elements in @var{vlist}.
  1803. @end deffn
  1804. @deffn {Scheme Procedure} vlist-reverse vlist
  1805. Return a new @var{vlist} whose content are those of @var{vlist} in reverse
  1806. order.
  1807. @end deffn
  1808. @deffn {Scheme Procedure} vlist-map proc vlist
  1809. Map @var{proc} over the elements of @var{vlist} and return a new vlist.
  1810. @end deffn
  1811. @deffn {Scheme Procedure} vlist-for-each proc vlist
  1812. Call @var{proc} on each element of @var{vlist}. The result is unspecified.
  1813. @end deffn
  1814. @deffn {Scheme Procedure} vlist-drop vlist count
  1815. Return a new vlist that does not contain the @var{count} first elements of
  1816. @var{vlist}. This is typically a constant-time operation.
  1817. @end deffn
  1818. @deffn {Scheme Procedure} vlist-take vlist count
  1819. Return a new vlist that contains only the @var{count} first elements of
  1820. @var{vlist}.
  1821. @end deffn
  1822. @deffn {Scheme Procedure} vlist-filter pred vlist
  1823. Return a new vlist containing all the elements from @var{vlist} that satisfy
  1824. @var{pred}.
  1825. @end deffn
  1826. @deffn {Scheme Procedure} vlist-delete x vlist [equal?]
  1827. Return a new vlist corresponding to @var{vlist} without the elements
  1828. @var{equal?} to @var{x}.
  1829. @end deffn
  1830. @deffn {Scheme Procedure} vlist-unfold p f g seed [tail-gen]
  1831. @deffnx {Scheme Procedure} vlist-unfold-right p f g seed [tail]
  1832. Return a new vlist, as for SRFI-1 @code{unfold} and @code{unfold-right}
  1833. (@pxref{SRFI-1, @code{unfold}}).
  1834. @end deffn
  1835. @deffn {Scheme Procedure} vlist-append vlist @dots{}
  1836. Append the given vlists and return the resulting vlist.
  1837. @end deffn
  1838. @deffn {Scheme Procedure} list->vlist lst
  1839. Return a new vlist whose contents correspond to @var{lst}.
  1840. @end deffn
  1841. @deffn {Scheme Procedure} vlist->list vlist
  1842. Return a new list whose contents match those of @var{vlist}.
  1843. @end deffn
  1844. @node Records
  1845. @subsection Records
  1846. A @dfn{record type} is a first class object representing a user-defined
  1847. data type. A @dfn{record} is an instance of a record type.
  1848. @deffn {Scheme Procedure} record? obj
  1849. Return @code{#t} if @var{obj} is a record of any type and @code{#f}
  1850. otherwise.
  1851. Note that @code{record?} may be true of any Scheme value; there is no
  1852. promise that records are disjoint with other Scheme types.
  1853. @end deffn
  1854. @deffn {Scheme Procedure} make-record-type type-name field-names [print]
  1855. Create and return a new @dfn{record-type descriptor}.
  1856. @var{type-name} is a string naming the type. Currently it's only used
  1857. in the printed representation of records, and in diagnostics.
  1858. @var{field-names} is a list of symbols naming the fields of a record
  1859. of the type. Duplicates are not allowed among these symbols.
  1860. @example
  1861. (make-record-type "employee" '(name age salary))
  1862. @end example
  1863. The optional @var{print} argument is a function used by
  1864. @code{display}, @code{write}, etc, for printing a record of the new
  1865. type. It's called as @code{(@var{print} record port)} and should look
  1866. at @var{record} and write to @var{port}.
  1867. @end deffn
  1868. @deffn {Scheme Procedure} record-constructor rtd [field-names]
  1869. Return a procedure for constructing new members of the type represented
  1870. by @var{rtd}. The returned procedure accepts exactly as many arguments
  1871. as there are symbols in the given list, @var{field-names}; these are
  1872. used, in order, as the initial values of those fields in a new record,
  1873. which is returned by the constructor procedure. The values of any
  1874. fields not named in that list are unspecified. The @var{field-names}
  1875. argument defaults to the list of field names in the call to
  1876. @code{make-record-type} that created the type represented by @var{rtd};
  1877. if the @var{field-names} argument is provided, it is an error if it
  1878. contains any duplicates or any symbols not in the default list.
  1879. @end deffn
  1880. @deffn {Scheme Procedure} record-predicate rtd
  1881. Return a procedure for testing membership in the type represented by
  1882. @var{rtd}. The returned procedure accepts exactly one argument and
  1883. returns a true value if the argument is a member of the indicated record
  1884. type; it returns a false value otherwise.
  1885. @end deffn
  1886. @deffn {Scheme Procedure} record-accessor rtd field-name
  1887. Return a procedure for reading the value of a particular field of a
  1888. member of the type represented by @var{rtd}. The returned procedure
  1889. accepts exactly one argument which must be a record of the appropriate
  1890. type; it returns the current value of the field named by the symbol
  1891. @var{field-name} in that record. The symbol @var{field-name} must be a
  1892. member of the list of field-names in the call to @code{make-record-type}
  1893. that created the type represented by @var{rtd}.
  1894. @end deffn
  1895. @deffn {Scheme Procedure} record-modifier rtd field-name
  1896. Return a procedure for writing the value of a particular field of a
  1897. member of the type represented by @var{rtd}. The returned procedure
  1898. accepts exactly two arguments: first, a record of the appropriate type,
  1899. and second, an arbitrary Scheme value; it modifies the field named by
  1900. the symbol @var{field-name} in that record to contain the given value.
  1901. The returned value of the modifier procedure is unspecified. The symbol
  1902. @var{field-name} must be a member of the list of field-names in the call
  1903. to @code{make-record-type} that created the type represented by
  1904. @var{rtd}.
  1905. @end deffn
  1906. @deffn {Scheme Procedure} record-type-descriptor record
  1907. Return a record-type descriptor representing the type of the given
  1908. record. That is, for example, if the returned descriptor were passed to
  1909. @code{record-predicate}, the resulting predicate would return a true
  1910. value when passed the given record. Note that it is not necessarily the
  1911. case that the returned descriptor is the one that was passed to
  1912. @code{record-constructor} in the call that created the constructor
  1913. procedure that created the given record.
  1914. @end deffn
  1915. @deffn {Scheme Procedure} record-type-name rtd
  1916. Return the type-name associated with the type represented by rtd. The
  1917. returned value is @code{eqv?} to the @var{type-name} argument given in
  1918. the call to @code{make-record-type} that created the type represented by
  1919. @var{rtd}.
  1920. @end deffn
  1921. @deffn {Scheme Procedure} record-type-fields rtd
  1922. Return a list of the symbols naming the fields in members of the type
  1923. represented by @var{rtd}. The returned value is @code{equal?} to the
  1924. field-names argument given in the call to @code{make-record-type} that
  1925. created the type represented by @var{rtd}.
  1926. @end deffn
  1927. @node Structures
  1928. @subsection Structures
  1929. @tpindex Structures
  1930. A @dfn{structure} is a first class data type which holds Scheme values
  1931. or C words in fields numbered 0 upwards. A @dfn{vtable} represents a
  1932. structure type, giving field types and permissions, and an optional
  1933. print function for @code{write} etc.
  1934. Structures are lower level than records (@pxref{Records}) but have
  1935. some extra features. The vtable system allows sets of types be
  1936. constructed, with class data. The uninterpreted words can
  1937. inter-operate with C code, allowing arbitrary pointers or other values
  1938. to be stored along side usual Scheme @code{SCM} values.
  1939. @menu
  1940. * Vtables::
  1941. * Structure Basics::
  1942. * Vtable Contents::
  1943. * Vtable Vtables::
  1944. @end menu
  1945. @node Vtables, Structure Basics, Structures, Structures
  1946. @subsubsection Vtables
  1947. A vtable is a structure type, specifying its layout, and other
  1948. information. A vtable is actually itself a structure, but there's no
  1949. need to worry about that initially (@pxref{Vtable Contents}.)
  1950. @deffn {Scheme Procedure} make-vtable fields [print]
  1951. Create a new vtable.
  1952. @var{fields} is a string describing the fields in the structures to be
  1953. created. Each field is represented by two characters, a type letter
  1954. and a permissions letter, for example @code{"pw"}. The types are as
  1955. follows.
  1956. @itemize @bullet{}
  1957. @item
  1958. @code{p} -- a Scheme value. ``p'' stands for ``protected'' meaning
  1959. it's protected against garbage collection.
  1960. @item
  1961. @code{u} -- an arbitrary word of data (an @code{scm_t_bits}). At the
  1962. Scheme level it's read and written as an unsigned integer. ``u''
  1963. stands for ``uninterpreted'' (it's not treated as a Scheme value), or
  1964. ``unprotected'' (it's not marked during GC), or ``unsigned long'' (its
  1965. size), or all of these things.
  1966. @item
  1967. @code{s} -- a self-reference. Such a field holds the @code{SCM} value
  1968. of the structure itself (a circular reference). This can be useful in
  1969. C code where you might have a pointer to the data array, and want to
  1970. get the Scheme @code{SCM} handle for the structure. In Scheme code it
  1971. has no use.
  1972. @end itemize
  1973. The second letter for each field is a permission code,
  1974. @itemize @bullet{}
  1975. @item
  1976. @code{w} -- writable, the field can be read and written.
  1977. @item
  1978. @code{r} -- read-only, the field can be read but not written.
  1979. @item
  1980. @code{o} -- opaque, the field can be neither read nor written at the
  1981. Scheme level. This can be used for fields which should only be used
  1982. from C code.
  1983. @item
  1984. @code{W},@code{R},@code{O} -- a tail array, with permissions for the
  1985. array fields as per @code{w},@code{r},@code{o}.
  1986. @end itemize
  1987. A tail array is further fields at the end of a structure. The last
  1988. field in the layout string might be for instance @samp{pW} to have a
  1989. tail of writable Scheme-valued fields. The @samp{pW} field itself
  1990. holds the tail size, and the tail fields come after it.
  1991. Here are some examples.
  1992. @example
  1993. (make-vtable "pw") ;; one writable field
  1994. (make-vtable "prpw") ;; one read-only and one writable
  1995. (make-vtable "pwuwuw") ;; one scheme and two uninterpreted
  1996. (make-vtable "prpW") ;; one fixed then a tail array
  1997. @end example
  1998. The optional @var{print} argument is a function called by
  1999. @code{display} and @code{write} (etc) to give a printed representation
  2000. of a structure created from this vtable. It's called
  2001. @code{(@var{print} struct port)} and should look at @var{struct} and
  2002. write to @var{port}. The default print merely gives a form like
  2003. @samp{#<struct ADDR:ADDR>} with a pair of machine addresses.
  2004. The following print function for example shows the two fields of its
  2005. structure.
  2006. @example
  2007. (make-vtable "prpw"
  2008. (lambda (struct port)
  2009. (display "#<" port)
  2010. (display (struct-ref struct 0) port)
  2011. (display " and " port)
  2012. (display (struct-ref struct 1) port)
  2013. (display ">" port)))
  2014. @end example
  2015. @end deffn
  2016. @node Structure Basics, Vtable Contents, Vtables, Structures
  2017. @subsubsection Structure Basics
  2018. This section describes the basic procedures for working with
  2019. structures. @code{make-struct} creates a structure, and
  2020. @code{struct-ref} and @code{struct-set!} access write fields.
  2021. @deffn {Scheme Procedure} make-struct vtable tail-size init @dots{}
  2022. @deffnx {C Function} scm_make_struct (vtable, tail_size, init_list)
  2023. Create a new structure, with layout per the given @var{vtable}
  2024. (@pxref{Vtables}).
  2025. @var{tail-size} is the size of the tail array if @var{vtable}
  2026. specifies a tail array. @var{tail-size} should be 0 when @var{vtable}
  2027. doesn't specify a tail array.
  2028. The optional @var{init}@dots{} arguments are initial values for the
  2029. fields of the structure (and the tail array). This is the only way to
  2030. put values in read-only fields. If there are fewer @var{init}
  2031. arguments than fields then the defaults are @code{#f} for a Scheme
  2032. field (type @code{p}) or 0 for an uninterpreted field (type @code{u}).
  2033. Type @code{s} self-reference fields, permission @code{o} opaque
  2034. fields, and the count field of a tail array are all ignored for the
  2035. @var{init} arguments, ie.@: an argument is not consumed by such a
  2036. field. An @code{s} is always set to the structure itself, an @code{o}
  2037. is always set to @code{#f} or 0 (with the intention that C code will
  2038. do something to it later), and the tail count is always the given
  2039. @var{tail-size}.
  2040. For example,
  2041. @example
  2042. (define v (make-vtable "prpwpw"))
  2043. (define s (make-struct v 0 123 "abc" 456))
  2044. (struct-ref s 0) @result{} 123
  2045. (struct-ref s 1) @result{} "abc"
  2046. @end example
  2047. @example
  2048. (define v (make-vtable "prpW"))
  2049. (define s (make-struct v 6 "fixed field" 'x 'y))
  2050. (struct-ref s 0) @result{} "fixed field"
  2051. (struct-ref s 1) @result{} 2 ;; tail size
  2052. (struct-ref s 2) @result{} x ;; tail array ...
  2053. (struct-ref s 3) @result{} y
  2054. (struct-ref s 4) @result{} #f
  2055. @end example
  2056. @end deffn
  2057. @deffn {Scheme Procedure} struct? obj
  2058. @deffnx {C Function} scm_struct_p (obj)
  2059. Return @code{#t} if @var{obj} is a structure, or @code{#f} if not.
  2060. @end deffn
  2061. @deffn {Scheme Procedure} struct-ref struct n
  2062. @deffnx {C Function} scm_struct_ref (struct, n)
  2063. Return the contents of field number @var{n} in @var{struct}. The
  2064. first field is number 0.
  2065. An error is thrown if @var{n} is out of range, or if the field cannot
  2066. be read because it's @code{o} opaque.
  2067. @end deffn
  2068. @deffn {Scheme Procedure} struct-set! struct n value
  2069. @deffnx {C Function} scm_struct_set_x (struct, n, value)
  2070. Set field number @var{n} in @var{struct} to @var{value}. The first
  2071. field is number 0.
  2072. An error is thrown if @var{n} is out of range, or if the field cannot
  2073. be written because it's @code{r} read-only or @code{o} opaque.
  2074. @end deffn
  2075. @deffn {Scheme Procedure} struct-vtable struct
  2076. @deffnx {C Function} scm_struct_vtable (struct)
  2077. Return the vtable used by @var{struct}.
  2078. This can be used to examine the layout of an unknown structure, see
  2079. @ref{Vtable Contents}.
  2080. @end deffn
  2081. @node Vtable Contents, Vtable Vtables, Structure Basics, Structures
  2082. @subsubsection Vtable Contents
  2083. A vtable is itself a structure, with particular fields that hold
  2084. information about the structures to be created. These include the
  2085. fields of those structures, and the print function for them. The
  2086. variables below allow access to those fields.
  2087. @deffn {Scheme Procedure} struct-vtable? obj
  2088. @deffnx {C Function} scm_struct_vtable_p (obj)
  2089. Return @code{#t} if @var{obj} is a vtable structure.
  2090. Note that because vtables are simply structures with a particular
  2091. layout, @code{struct-vtable?} can potentially return true on an
  2092. application structure which merely happens to look like a vtable.
  2093. @end deffn
  2094. @defvr {Scheme Variable} vtable-index-layout
  2095. @defvrx {C Macro} scm_vtable_index_layout
  2096. The field number of the layout specification in a vtable. The layout
  2097. specification is a symbol like @code{pwpw} formed from the fields
  2098. string passed to @code{make-vtable}, or created by
  2099. @code{make-struct-layout} (@pxref{Vtable Vtables}).
  2100. @example
  2101. (define v (make-vtable "pwpw" 0))
  2102. (struct-ref v vtable-index-layout) @result{} pwpw
  2103. @end example
  2104. This field is read-only, since the layout of structures using a vtable
  2105. cannot be changed.
  2106. @end defvr
  2107. @defvr {Scheme Variable} vtable-index-vtable
  2108. @defvrx {C Macro} scm_vtable_index_vtable
  2109. A self-reference to the vtable, ie.@: a type @code{s} field. This is
  2110. used by C code within Guile and has no use at the Scheme level.
  2111. @end defvr
  2112. @defvr {Scheme Variable} vtable-index-printer
  2113. @defvrx {C Macro} scm_vtable_index_printer
  2114. The field number of the printer function. This field contains @code{#f}
  2115. if the default print function should be used.
  2116. @example
  2117. (define (my-print-func struct port)
  2118. ...)
  2119. (define v (make-vtable "pwpw" my-print-func))
  2120. (struct-ref v vtable-index-printer) @result{} my-print-func
  2121. @end example
  2122. This field is writable, allowing the print function to be changed
  2123. dynamically.
  2124. @end defvr
  2125. @deffn {Scheme Procedure} struct-vtable-name vtable
  2126. @deffnx {Scheme Procedure} set-struct-vtable-name! vtable name
  2127. @deffnx {C Function} scm_struct_vtable_name (vtable)
  2128. @deffnx {C Function} scm_set_struct_vtable_name_x (vtable, name)
  2129. Get or set the name of @var{vtable}. @var{name} is a symbol and is
  2130. used in the default print function when printing structures created
  2131. from @var{vtable}.
  2132. @example
  2133. (define v (make-vtable "pw"))
  2134. (set-struct-vtable-name! v 'my-name)
  2135. (define s (make-struct v 0))
  2136. (display s) @print{} #<my-name b7ab3ae0:b7ab3730>
  2137. @end example
  2138. @end deffn
  2139. @deffn {Scheme Procedure} struct-vtable-tag vtable
  2140. @deffnx {C Function} scm_struct_vtable_tag (vtable)
  2141. Return the tag of the given @var{vtable}.
  2142. @c
  2143. @c FIXME: what can be said about what this means?
  2144. @c
  2145. @end deffn
  2146. @node Vtable Vtables, , Vtable Contents, Structures
  2147. @subsubsection Vtable Vtables
  2148. As noted above, a vtable is a structure and that structure is itself
  2149. described by a vtable. Such a ``vtable of a vtable'' can be created
  2150. with @code{make-vtable-vtable} below. This can be used to build sets
  2151. of related vtables, possibly with extra application fields.
  2152. This second level of vtable can be a little confusing. The ball
  2153. example below is a typical use, adding a ``class data'' field to the
  2154. vtables, from which instance structures are created. The current
  2155. implementation of Guile's own records (@pxref{Records}) does something
  2156. similar, a record type descriptor is a vtable with room to hold the
  2157. field names of the records to be created from it.
  2158. @deffn {Scheme Procedure} make-vtable-vtable user-fields tail-size [print]
  2159. @deffnx {C Function} scm_make_vtable_vtable (user_fields, tail_size, print_and_init_list)
  2160. Create a ``vtable-vtable'' which can be used to create vtables. This
  2161. vtable-vtable is also a vtable, and is self-describing, meaning its
  2162. vtable is itself. The following is a simple usage.
  2163. @example
  2164. (define vt-vt (make-vtable-vtable "" 0))
  2165. (define vt (make-struct vt-vt 0
  2166. (make-struct-layout "pwpw"))
  2167. (define s (make-struct vt 0 123 456))
  2168. (struct-ref s 0) @result{} 123
  2169. @end example
  2170. @code{make-struct} is used to create a vtable from the vtable-vtable.
  2171. The first initializer is a layout object (field
  2172. @code{vtable-index-layout}), usually obtained from
  2173. @code{make-struct-layout} (below). An optional second initializer is
  2174. a printer function (field @code{vtable-index-printer}), used as
  2175. described under @code{make-vtable} (@pxref{Vtables}).
  2176. @sp 1
  2177. @var{user-fields} is a layout string giving extra fields to have in
  2178. the vtables. A vtable starts with some base fields as per @ref{Vtable
  2179. Contents}, and @var{user-fields} is appended. The @var{user-fields}
  2180. start at field number @code{vtable-offset-user} (below), and exist in
  2181. both the vtable-vtable and in the vtables created from it. Such
  2182. fields provide space for ``class data''. For example,
  2183. @example
  2184. (define vt-of-vt (make-vtable-vtable "pw" 0))
  2185. (define vt (make-struct vt-of-vt 0))
  2186. (struct-set! vt vtable-offset-user "my class data")
  2187. @end example
  2188. @var{tail-size} is the size of the tail array in the vtable-vtable
  2189. itself, if @var{user-fields} specifies a tail array. This should be 0
  2190. if nothing extra is required or the format has no tail array. The
  2191. tail array field such as @samp{pW} holds the tail array size, as
  2192. usual, and is followed by the extra space.
  2193. @example
  2194. (define vt-vt (make-vtable-vtable "pW" 20))
  2195. (define my-vt-tail-start (1+ vtable-offset-user))
  2196. (struct-set! vt-vt (+ 3 my-vt-tail-start) "data in tail")
  2197. @end example
  2198. The optional @var{print} argument is used by @code{display} and
  2199. @code{write} (etc) to print the vtable-vtable and any vtables created
  2200. from it. It's called as @code{(@var{print} vtable port)} and should
  2201. look at @var{vtable} and write to @var{port}. The default is the
  2202. usual structure print function, which just gives machine addresses.
  2203. @end deffn
  2204. @deffn {Scheme Procedure} make-struct-layout fields
  2205. @deffnx {C Function} scm_make_struct_layout (fields)
  2206. Return a structure layout symbol, from a @var{fields} string.
  2207. @var{fields} is as described under @code{make-vtable}
  2208. (@pxref{Vtables}). An invalid @var{fields} string is an error.
  2209. @example
  2210. (make-struct-layout "prpW") @result{} prpW
  2211. (make-struct-layout "blah") @result{} ERROR
  2212. @end example
  2213. @end deffn
  2214. @defvr {Scheme Variable} vtable-offset-user
  2215. @defvrx {C Macro} scm_vtable_offset_user
  2216. The first field in a vtable which is available for application use.
  2217. Such fields only exist when specified by @var{user-fields} in
  2218. @code{make-vtable-vtable} above.
  2219. @end defvr
  2220. @sp 1
  2221. Here's an extended vtable-vtable example, creating classes of
  2222. ``balls''. Each class has a ``colour'', which is fixed. Instances of
  2223. those classes are created, and such each such ball has an ``owner'',
  2224. which can be changed.
  2225. @lisp
  2226. (define ball-root (make-vtable-vtable "pr" 0))
  2227. (define (make-ball-type ball-color)
  2228. (make-struct ball-root 0
  2229. (make-struct-layout "pw")
  2230. (lambda (ball port)
  2231. (format port "#<a ~A ball owned by ~A>"
  2232. (color ball)
  2233. (owner ball)))
  2234. ball-color))
  2235. (define (color ball)
  2236. (struct-ref (struct-vtable ball) vtable-offset-user))
  2237. (define (owner ball)
  2238. (struct-ref ball 0))
  2239. (define red (make-ball-type 'red))
  2240. (define green (make-ball-type 'green))
  2241. (define (make-ball type owner) (make-struct type 0 owner))
  2242. (define ball (make-ball green 'Nisse))
  2243. ball @result{} #<a green ball owned by Nisse>
  2244. @end lisp
  2245. @node Dictionary Types
  2246. @subsection Dictionary Types
  2247. A @dfn{dictionary} object is a data structure used to index
  2248. information in a user-defined way. In standard Scheme, the main
  2249. aggregate data types are lists and vectors. Lists are not really
  2250. indexed at all, and vectors are indexed only by number
  2251. (e.g.@: @code{(vector-ref foo 5)}). Often you will find it useful
  2252. to index your data on some other type; for example, in a library
  2253. catalog you might want to look up a book by the name of its
  2254. author. Dictionaries are used to help you organize information in
  2255. such a way.
  2256. An @dfn{association list} (or @dfn{alist} for short) is a list of
  2257. key-value pairs. Each pair represents a single quantity or
  2258. object; the @code{car} of the pair is a key which is used to
  2259. identify the object, and the @code{cdr} is the object's value.
  2260. A @dfn{hash table} also permits you to index objects with
  2261. arbitrary keys, but in a way that makes looking up any one object
  2262. extremely fast. A well-designed hash system makes hash table
  2263. lookups almost as fast as conventional array or vector references.
  2264. Alists are popular among Lisp programmers because they use only
  2265. the language's primitive operations (lists, @dfn{car}, @dfn{cdr}
  2266. and the equality primitives). No changes to the language core are
  2267. necessary. Therefore, with Scheme's built-in list manipulation
  2268. facilities, it is very convenient to handle data stored in an
  2269. association list. Also, alists are highly portable and can be
  2270. easily implemented on even the most minimal Lisp systems.
  2271. However, alists are inefficient, especially for storing large
  2272. quantities of data. Because we want Guile to be useful for large
  2273. software systems as well as small ones, Guile provides a rich set
  2274. of tools for using either association lists or hash tables.
  2275. @node Association Lists
  2276. @subsection Association Lists
  2277. @tpindex Association Lists
  2278. @tpindex Alist
  2279. @cindex association List
  2280. @cindex alist
  2281. @cindex database
  2282. An association list is a conventional data structure that is often used
  2283. to implement simple key-value databases. It consists of a list of
  2284. entries in which each entry is a pair. The @dfn{key} of each entry is
  2285. the @code{car} of the pair and the @dfn{value} of each entry is the
  2286. @code{cdr}.
  2287. @example
  2288. ASSOCIATION LIST ::= '( (KEY1 . VALUE1)
  2289. (KEY2 . VALUE2)
  2290. (KEY3 . VALUE3)
  2291. @dots{}
  2292. )
  2293. @end example
  2294. @noindent
  2295. Association lists are also known, for short, as @dfn{alists}.
  2296. The structure of an association list is just one example of the infinite
  2297. number of possible structures that can be built using pairs and lists.
  2298. As such, the keys and values in an association list can be manipulated
  2299. using the general list structure procedures @code{cons}, @code{car},
  2300. @code{cdr}, @code{set-car!}, @code{set-cdr!} and so on. However,
  2301. because association lists are so useful, Guile also provides specific
  2302. procedures for manipulating them.
  2303. @menu
  2304. * Alist Key Equality::
  2305. * Adding or Setting Alist Entries::
  2306. * Retrieving Alist Entries::
  2307. * Removing Alist Entries::
  2308. * Sloppy Alist Functions::
  2309. * Alist Example::
  2310. @end menu
  2311. @node Alist Key Equality
  2312. @subsubsection Alist Key Equality
  2313. All of Guile's dedicated association list procedures, apart from
  2314. @code{acons}, come in three flavours, depending on the level of equality
  2315. that is required to decide whether an existing key in the association
  2316. list is the same as the key that the procedure call uses to identify the
  2317. required entry.
  2318. @itemize @bullet
  2319. @item
  2320. Procedures with @dfn{assq} in their name use @code{eq?} to determine key
  2321. equality.
  2322. @item
  2323. Procedures with @dfn{assv} in their name use @code{eqv?} to determine
  2324. key equality.
  2325. @item
  2326. Procedures with @dfn{assoc} in their name use @code{equal?} to
  2327. determine key equality.
  2328. @end itemize
  2329. @code{acons} is an exception because it is used to build association
  2330. lists which do not require their entries' keys to be unique.
  2331. @node Adding or Setting Alist Entries
  2332. @subsubsection Adding or Setting Alist Entries
  2333. @code{acons} adds a new entry to an association list and returns the
  2334. combined association list. The combined alist is formed by consing the
  2335. new entry onto the head of the alist specified in the @code{acons}
  2336. procedure call. So the specified alist is not modified, but its
  2337. contents become shared with the tail of the combined alist that
  2338. @code{acons} returns.
  2339. In the most common usage of @code{acons}, a variable holding the
  2340. original association list is updated with the combined alist:
  2341. @example
  2342. (set! address-list (acons name address address-list))
  2343. @end example
  2344. In such cases, it doesn't matter that the old and new values of
  2345. @code{address-list} share some of their contents, since the old value is
  2346. usually no longer independently accessible.
  2347. Note that @code{acons} adds the specified new entry regardless of
  2348. whether the alist may already contain entries with keys that are, in
  2349. some sense, the same as that of the new entry. Thus @code{acons} is
  2350. ideal for building alists where there is no concept of key uniqueness.
  2351. @example
  2352. (set! task-list (acons 3 "pay gas bill" '()))
  2353. task-list
  2354. @result{}
  2355. ((3 . "pay gas bill"))
  2356. (set! task-list (acons 3 "tidy bedroom" task-list))
  2357. task-list
  2358. @result{}
  2359. ((3 . "tidy bedroom") (3 . "pay gas bill"))
  2360. @end example
  2361. @code{assq-set!}, @code{assv-set!} and @code{assoc-set!} are used to add
  2362. or replace an entry in an association list where there @emph{is} a
  2363. concept of key uniqueness. If the specified association list already
  2364. contains an entry whose key is the same as that specified in the
  2365. procedure call, the existing entry is replaced by the new one.
  2366. Otherwise, the new entry is consed onto the head of the old association
  2367. list to create the combined alist. In all cases, these procedures
  2368. return the combined alist.
  2369. @code{assq-set!} and friends @emph{may} destructively modify the
  2370. structure of the old association list in such a way that an existing
  2371. variable is correctly updated without having to @code{set!} it to the
  2372. value returned:
  2373. @example
  2374. address-list
  2375. @result{}
  2376. (("mary" . "34 Elm Road") ("james" . "16 Bow Street"))
  2377. (assoc-set! address-list "james" "1a London Road")
  2378. @result{}
  2379. (("mary" . "34 Elm Road") ("james" . "1a London Road"))
  2380. address-list
  2381. @result{}
  2382. (("mary" . "34 Elm Road") ("james" . "1a London Road"))
  2383. @end example
  2384. Or they may not:
  2385. @example
  2386. (assoc-set! address-list "bob" "11 Newington Avenue")
  2387. @result{}
  2388. (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road")
  2389. ("james" . "1a London Road"))
  2390. address-list
  2391. @result{}
  2392. (("mary" . "34 Elm Road") ("james" . "1a London Road"))
  2393. @end example
  2394. The only safe way to update an association list variable when adding or
  2395. replacing an entry like this is to @code{set!} the variable to the
  2396. returned value:
  2397. @example
  2398. (set! address-list
  2399. (assoc-set! address-list "bob" "11 Newington Avenue"))
  2400. address-list
  2401. @result{}
  2402. (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road")
  2403. ("james" . "1a London Road"))
  2404. @end example
  2405. Because of this slight inconvenience, you may find it more convenient to
  2406. use hash tables to store dictionary data. If your application will not
  2407. be modifying the contents of an alist very often, this may not make much
  2408. difference to you.
  2409. If you need to keep the old value of an association list in a form
  2410. independent from the list that results from modification by
  2411. @code{acons}, @code{assq-set!}, @code{assv-set!} or @code{assoc-set!},
  2412. use @code{list-copy} to copy the old association list before modifying
  2413. it.
  2414. @deffn {Scheme Procedure} acons key value alist
  2415. @deffnx {C Function} scm_acons (key, value, alist)
  2416. Add a new key-value pair to @var{alist}. A new pair is
  2417. created whose car is @var{key} and whose cdr is @var{value}, and the
  2418. pair is consed onto @var{alist}, and the new list is returned. This
  2419. function is @emph{not} destructive; @var{alist} is not modified.
  2420. @end deffn
  2421. @deffn {Scheme Procedure} assq-set! alist key val
  2422. @deffnx {Scheme Procedure} assv-set! alist key value
  2423. @deffnx {Scheme Procedure} assoc-set! alist key value
  2424. @deffnx {C Function} scm_assq_set_x (alist, key, val)
  2425. @deffnx {C Function} scm_assv_set_x (alist, key, val)
  2426. @deffnx {C Function} scm_assoc_set_x (alist, key, val)
  2427. Reassociate @var{key} in @var{alist} with @var{value}: find any existing
  2428. @var{alist} entry for @var{key} and associate it with the new
  2429. @var{value}. If @var{alist} does not contain an entry for @var{key},
  2430. add a new one. Return the (possibly new) alist.
  2431. These functions do not attempt to verify the structure of @var{alist},
  2432. and so may cause unusual results if passed an object that is not an
  2433. association list.
  2434. @end deffn
  2435. @node Retrieving Alist Entries
  2436. @subsubsection Retrieving Alist Entries
  2437. @rnindex assq
  2438. @rnindex assv
  2439. @rnindex assoc
  2440. @code{assq}, @code{assv} and @code{assoc} find the entry in an alist
  2441. for a given key, and return the @code{(@var{key} . @var{value})} pair.
  2442. @code{assq-ref}, @code{assv-ref} and @code{assoc-ref} do a similar
  2443. lookup, but return just the @var{value}.
  2444. @deffn {Scheme Procedure} assq key alist
  2445. @deffnx {Scheme Procedure} assv key alist
  2446. @deffnx {Scheme Procedure} assoc key alist
  2447. @deffnx {C Function} scm_assq (key, alist)
  2448. @deffnx {C Function} scm_assv (key, alist)
  2449. @deffnx {C Function} scm_assoc (key, alist)
  2450. Return the first entry in @var{alist} with the given @var{key}. The
  2451. return is the pair @code{(KEY . VALUE)} from @var{alist}. If there's
  2452. no matching entry the return is @code{#f}.
  2453. @code{assq} compares keys with @code{eq?}, @code{assv} uses
  2454. @code{eqv?} and @code{assoc} uses @code{equal?}. See also SRFI-1
  2455. which has an extended @code{assoc} (@ref{SRFI-1 Association Lists}).
  2456. @end deffn
  2457. @deffn {Scheme Procedure} assq-ref alist key
  2458. @deffnx {Scheme Procedure} assv-ref alist key
  2459. @deffnx {Scheme Procedure} assoc-ref alist key
  2460. @deffnx {C Function} scm_assq_ref (alist, key)
  2461. @deffnx {C Function} scm_assv_ref (alist, key)
  2462. @deffnx {C Function} scm_assoc_ref (alist, key)
  2463. Return the value from the first entry in @var{alist} with the given
  2464. @var{key}, or @code{#f} if there's no such entry.
  2465. @code{assq-ref} compares keys with @code{eq?}, @code{assv-ref} uses
  2466. @code{eqv?} and @code{assoc-ref} uses @code{equal?}.
  2467. Notice these functions have the @var{key} argument last, like other
  2468. @code{-ref} functions, but this is opposite to what @code{assq}
  2469. etc above use.
  2470. When the return is @code{#f} it can be either @var{key} not found, or
  2471. an entry which happens to have value @code{#f} in the @code{cdr}. Use
  2472. @code{assq} etc above if you need to differentiate these cases.
  2473. @end deffn
  2474. @node Removing Alist Entries
  2475. @subsubsection Removing Alist Entries
  2476. To remove the element from an association list whose key matches a
  2477. specified key, use @code{assq-remove!}, @code{assv-remove!} or
  2478. @code{assoc-remove!} (depending, as usual, on the level of equality
  2479. required between the key that you specify and the keys in the
  2480. association list).
  2481. As with @code{assq-set!} and friends, the specified alist may or may not
  2482. be modified destructively, and the only safe way to update a variable
  2483. containing the alist is to @code{set!} it to the value that
  2484. @code{assq-remove!} and friends return.
  2485. @example
  2486. address-list
  2487. @result{}
  2488. (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road")
  2489. ("james" . "1a London Road"))
  2490. (set! address-list (assoc-remove! address-list "mary"))
  2491. address-list
  2492. @result{}
  2493. (("bob" . "11 Newington Avenue") ("james" . "1a London Road"))
  2494. @end example
  2495. Note that, when @code{assq/v/oc-remove!} is used to modify an
  2496. association list that has been constructed only using the corresponding
  2497. @code{assq/v/oc-set!}, there can be at most one matching entry in the
  2498. alist, so the question of multiple entries being removed in one go does
  2499. not arise. If @code{assq/v/oc-remove!} is applied to an association
  2500. list that has been constructed using @code{acons}, or an
  2501. @code{assq/v/oc-set!} with a different level of equality, or any mixture
  2502. of these, it removes only the first matching entry from the alist, even
  2503. if the alist might contain further matching entries. For example:
  2504. @example
  2505. (define address-list '())
  2506. (set! address-list (assq-set! address-list "mary" "11 Elm Street"))
  2507. (set! address-list (assq-set! address-list "mary" "57 Pine Drive"))
  2508. address-list
  2509. @result{}
  2510. (("mary" . "57 Pine Drive") ("mary" . "11 Elm Street"))
  2511. (set! address-list (assoc-remove! address-list "mary"))
  2512. address-list
  2513. @result{}
  2514. (("mary" . "11 Elm Street"))
  2515. @end example
  2516. In this example, the two instances of the string "mary" are not the same
  2517. when compared using @code{eq?}, so the two @code{assq-set!} calls add
  2518. two distinct entries to @code{address-list}. When compared using
  2519. @code{equal?}, both "mary"s in @code{address-list} are the same as the
  2520. "mary" in the @code{assoc-remove!} call, but @code{assoc-remove!} stops
  2521. after removing the first matching entry that it finds, and so one of the
  2522. "mary" entries is left in place.
  2523. @deffn {Scheme Procedure} assq-remove! alist key
  2524. @deffnx {Scheme Procedure} assv-remove! alist key
  2525. @deffnx {Scheme Procedure} assoc-remove! alist key
  2526. @deffnx {C Function} scm_assq_remove_x (alist, key)
  2527. @deffnx {C Function} scm_assv_remove_x (alist, key)
  2528. @deffnx {C Function} scm_assoc_remove_x (alist, key)
  2529. Delete the first entry in @var{alist} associated with @var{key}, and return
  2530. the resulting alist.
  2531. @end deffn
  2532. @node Sloppy Alist Functions
  2533. @subsubsection Sloppy Alist Functions
  2534. @code{sloppy-assq}, @code{sloppy-assv} and @code{sloppy-assoc} behave
  2535. like the corresponding non-@code{sloppy-} procedures, except that they
  2536. return @code{#f} when the specified association list is not well-formed,
  2537. where the non-@code{sloppy-} versions would signal an error.
  2538. Specifically, there are two conditions for which the non-@code{sloppy-}
  2539. procedures signal an error, which the @code{sloppy-} procedures handle
  2540. instead by returning @code{#f}. Firstly, if the specified alist as a
  2541. whole is not a proper list:
  2542. @example
  2543. (assoc "mary" '((1 . 2) ("key" . "door") . "open sesame"))
  2544. @result{}
  2545. ERROR: In procedure assoc in expression (assoc "mary" (quote #)):
  2546. ERROR: Wrong type argument in position 2 (expecting
  2547. association list): ((1 . 2) ("key" . "door") . "open sesame")
  2548. (sloppy-assoc "mary" '((1 . 2) ("key" . "door") . "open sesame"))
  2549. @result{}
  2550. #f
  2551. @end example
  2552. @noindent
  2553. Secondly, if one of the entries in the specified alist is not a pair:
  2554. @example
  2555. (assoc 2 '((1 . 1) 2 (3 . 9)))
  2556. @result{}
  2557. ERROR: In procedure assoc in expression (assoc 2 (quote #)):
  2558. ERROR: Wrong type argument in position 2 (expecting
  2559. association list): ((1 . 1) 2 (3 . 9))
  2560. (sloppy-assoc 2 '((1 . 1) 2 (3 . 9)))
  2561. @result{}
  2562. #f
  2563. @end example
  2564. Unless you are explicitly working with badly formed association lists,
  2565. it is much safer to use the non-@code{sloppy-} procedures, because they
  2566. help to highlight coding and data errors that the @code{sloppy-}
  2567. versions would silently cover up.
  2568. @deffn {Scheme Procedure} sloppy-assq key alist
  2569. @deffnx {C Function} scm_sloppy_assq (key, alist)
  2570. Behaves like @code{assq} but does not do any error checking.
  2571. Recommended only for use in Guile internals.
  2572. @end deffn
  2573. @deffn {Scheme Procedure} sloppy-assv key alist
  2574. @deffnx {C Function} scm_sloppy_assv (key, alist)
  2575. Behaves like @code{assv} but does not do any error checking.
  2576. Recommended only for use in Guile internals.
  2577. @end deffn
  2578. @deffn {Scheme Procedure} sloppy-assoc key alist
  2579. @deffnx {C Function} scm_sloppy_assoc (key, alist)
  2580. Behaves like @code{assoc} but does not do any error checking.
  2581. Recommended only for use in Guile internals.
  2582. @end deffn
  2583. @node Alist Example
  2584. @subsubsection Alist Example
  2585. Here is a longer example of how alists may be used in practice.
  2586. @lisp
  2587. (define capitals '(("New York" . "Albany")
  2588. ("Oregon" . "Salem")
  2589. ("Florida" . "Miami")))
  2590. ;; What's the capital of Oregon?
  2591. (assoc "Oregon" capitals) @result{} ("Oregon" . "Salem")
  2592. (assoc-ref capitals "Oregon") @result{} "Salem"
  2593. ;; We left out South Dakota.
  2594. (set! capitals
  2595. (assoc-set! capitals "South Dakota" "Pierre"))
  2596. capitals
  2597. @result{} (("South Dakota" . "Pierre")
  2598. ("New York" . "Albany")
  2599. ("Oregon" . "Salem")
  2600. ("Florida" . "Miami"))
  2601. ;; And we got Florida wrong.
  2602. (set! capitals
  2603. (assoc-set! capitals "Florida" "Tallahassee"))
  2604. capitals
  2605. @result{} (("South Dakota" . "Pierre")
  2606. ("New York" . "Albany")
  2607. ("Oregon" . "Salem")
  2608. ("Florida" . "Tallahassee"))
  2609. ;; After Oregon secedes, we can remove it.
  2610. (set! capitals
  2611. (assoc-remove! capitals "Oregon"))
  2612. capitals
  2613. @result{} (("South Dakota" . "Pierre")
  2614. ("New York" . "Albany")
  2615. ("Florida" . "Tallahassee"))
  2616. @end lisp
  2617. @node VHashes
  2618. @subsection VList-Based Hash Lists or ``VHashes''
  2619. @cindex VList-based hash lists
  2620. @cindex VHash
  2621. The @code{(ice-9 vlist)} module provides an implementation of @dfn{VList-based
  2622. hash lists} (@pxref{VLists}). VList-based hash lists, or @dfn{vhashes}, are an
  2623. immutable dictionary type similar to association lists that maps @dfn{keys} to
  2624. @dfn{values}. However, unlike association lists, accessing a value given its
  2625. key is typically a constant-time operation.
  2626. The VHash programming interface of @code{(ice-9 vlist)} is mostly the same as
  2627. that of association lists found in SRFI-1, with procedure names prefixed by
  2628. @code{vhash-} instead of @code{alist-} (@pxref{SRFI-1 Association Lists}).
  2629. In addition, vhashes can be manipulated using VList operations:
  2630. @example
  2631. (vlist-head (vhash-consq 'a 1 vlist-null))
  2632. @result{} (a . 1)
  2633. (define vh1 (vhash-consq 'b 2 (vhash-consq 'a 1 vlist-null)))
  2634. (define vh2 (vhash-consq 'c 3 (vlist-tail vh1)))
  2635. (vhash-assq 'a vh2)
  2636. @result{} (a . 1)
  2637. (vhash-assq 'b vh2)
  2638. @result{} #f
  2639. (vhash-assq 'c vh2)
  2640. @result{} (c . 3)
  2641. (vlist->list vh2)
  2642. @result{} ((c . 3) (a . 1))
  2643. @end example
  2644. However, keep in mind that procedures that construct new VLists
  2645. (@code{vlist-map}, @code{vlist-filter}, etc.) return raw VLists, not vhashes:
  2646. @example
  2647. (define vh (alist->vhash '((a . 1) (b . 2) (c . 3)) hashq))
  2648. (vhash-assq 'a vh)
  2649. @result{} (a . 1)
  2650. (define vl
  2651. ;; This will create a raw vlist.
  2652. (vlist-filter (lambda (key+value) (odd? (cdr key+value))) vh))
  2653. (vhash-assq 'a vl)
  2654. @result{} ERROR: Wrong type argument in position 2
  2655. (vlist->list vl)
  2656. @result{} ((a . 1) (c . 3))
  2657. @end example
  2658. @deffn {Scheme Procedure} vhash? obj
  2659. Return true if @var{obj} is a vhash.
  2660. @end deffn
  2661. @deffn {Scheme Procedure} vhash-cons key value vhash [hash-proc]
  2662. @deffnx {Scheme Procedure} vhash-consq key value vhash
  2663. @deffnx {Scheme Procedure} vhash-consv key value vhash
  2664. Return a new hash list based on @var{vhash} where @var{key} is associated with
  2665. @var{value}, using @var{hash-proc} to compute the hash of @var{key}.
  2666. @var{vhash} must be either @code{vlist-null} or a vhash returned by a previous
  2667. call to @code{vhash-cons}. @var{hash-proc} defaults to @code{hash} (@pxref{Hash
  2668. Table Reference, @code{hash} procedure}). With @code{vhash-consq}, the
  2669. @code{hashq} hash function is used; with @code{vhash-consv} the @code{hashv}
  2670. hash function is used.
  2671. All @code{vhash-cons} calls made to construct a vhash should use the same
  2672. @var{hash-proc}. Failing to do that, the result is undefined.
  2673. @end deffn
  2674. @deffn {Scheme Procedure} vhash-assoc key vhash [equal? [hash-proc]]
  2675. @deffnx {Scheme Procedure} vhash-assq key vhash
  2676. @deffnx {Scheme Procedure} vhash-assv key vhash
  2677. Return the first key/value pair from @var{vhash} whose key is equal to @var{key}
  2678. according to the @var{equal?} equality predicate (which defaults to
  2679. @code{equal?}), and using @var{hash-proc} (which defaults to @code{hash}) to
  2680. compute the hash of @var{key}. The second form uses @code{eq?} as the equality
  2681. predicate and @code{hashq} as the hash function; the last form uses @code{eqv?}
  2682. and @code{hashv}.
  2683. Note that it is important to consistently use the same hash function for
  2684. @var{hash-proc} as was passed to @code{vhash-cons}. Failing to do that, the
  2685. result is unpredictable.
  2686. @end deffn
  2687. @deffn {Scheme Procedure} vhash-delete key vhash [equal? [hash-proc]]
  2688. @deffnx {Scheme Procedure} vhash-delq key vhash
  2689. @deffnx {Scheme Procedure} vhash-delv key vhash
  2690. Remove all associations from @var{vhash} with @var{key}, comparing keys with
  2691. @var{equal?} (which defaults to @code{equal?}), and computing the hash of
  2692. @var{key} using @var{hash-proc} (which defaults to @code{hash}). The second
  2693. form uses @code{eq?} as the equality predicate and @code{hashq} as the hash
  2694. function; the last one uses @code{eqv?} and @code{hashv}.
  2695. Again the choice of @var{hash-proc} must be consistent with previous calls to
  2696. @code{vhash-cons}.
  2697. @end deffn
  2698. @deffn {Scheme Procedure} vhash-fold proc init vhash
  2699. @deffnx {Scheme Procedure} vhash-fold-right proc init vhash
  2700. Fold over the key/value elements of @var{vhash} in the given direction,
  2701. with each call to @var{proc} having the form @code{(@var{proc} key value
  2702. result)}, where @var{result} is the result of the previous call to
  2703. @var{proc} and @var{init} the value of @var{result} for the first call
  2704. to @var{proc}.
  2705. @end deffn
  2706. @deffn {Scheme Procedure} vhash-fold* proc init key vhash [equal? [hash]]
  2707. @deffnx {Scheme Procedure} vhash-foldq* proc init key vhash
  2708. @deffnx {Scheme Procedure} vhash-foldv* proc init key vhash
  2709. Fold over all the values associated with @var{key} in @var{vhash}, with each
  2710. call to @var{proc} having the form @code{(proc value result)}, where
  2711. @var{result} is the result of the previous call to @var{proc} and @var{init} the
  2712. value of @var{result} for the first call to @var{proc}.
  2713. Keys in @var{vhash} are hashed using @var{hash} are compared using @var{equal?}.
  2714. The second form uses @code{eq?} as the equality predicate and @code{hashq} as
  2715. the hash function; the third one uses @code{eqv?} and @code{hashv}.
  2716. Example:
  2717. @example
  2718. (define vh
  2719. (alist->vhash '((a . 1) (a . 2) (z . 0) (a . 3))))
  2720. (vhash-fold* cons '() 'a vh)
  2721. @result{} (3 2 1)
  2722. (vhash-fold* cons '() 'z vh)
  2723. @result{} (0)
  2724. @end example
  2725. @end deffn
  2726. @deffn {Scheme Procedure} alist->vhash alist [hash-proc]
  2727. Return the vhash corresponding to @var{alist}, an association list, using
  2728. @var{hash-proc} to compute key hashes. When omitted, @var{hash-proc} defaults
  2729. to @code{hash}.
  2730. @end deffn
  2731. @node Hash Tables
  2732. @subsection Hash Tables
  2733. @tpindex Hash Tables
  2734. Hash tables are dictionaries which offer similar functionality as
  2735. association lists: They provide a mapping from keys to values. The
  2736. difference is that association lists need time linear in the size of
  2737. elements when searching for entries, whereas hash tables can normally
  2738. search in constant time. The drawback is that hash tables require a
  2739. little bit more memory, and that you can not use the normal list
  2740. procedures (@pxref{Lists}) for working with them.
  2741. Guile provides two types of hashtables. One is an abstract data type
  2742. that can only be manipulated with the functions in this section. The
  2743. other type is concrete: it uses a normal vector with alists as
  2744. elements. The advantage of the abstract hash tables is that they will
  2745. be automatically resized when they become too full or too empty.
  2746. @menu
  2747. * Hash Table Examples:: Demonstration of hash table usage.
  2748. * Hash Table Reference:: Hash table procedure descriptions.
  2749. @end menu
  2750. @node Hash Table Examples
  2751. @subsubsection Hash Table Examples
  2752. For demonstration purposes, this section gives a few usage examples of
  2753. some hash table procedures, together with some explanation what they do.
  2754. First we start by creating a new hash table with 31 slots, and
  2755. populate it with two key/value pairs.
  2756. @lisp
  2757. (define h (make-hash-table 31))
  2758. ;; This is an opaque object
  2759. h
  2760. @result{}
  2761. #<hash-table 0/31>
  2762. ;; We can also use a vector of alists.
  2763. (define h (make-vector 7 '()))
  2764. h
  2765. @result{}
  2766. #(() () () () () () ())
  2767. ;; Inserting into a hash table can be done with hashq-set!
  2768. (hashq-set! h 'foo "bar")
  2769. @result{}
  2770. "bar"
  2771. (hashq-set! h 'braz "zonk")
  2772. @result{}
  2773. "zonk"
  2774. ;; Or with hash-create-handle!
  2775. (hashq-create-handle! h 'frob #f)
  2776. @result{}
  2777. (frob . #f)
  2778. ;; The vector now contains three elements in the alists and the frob
  2779. ;; entry is at index (hashq 'frob).
  2780. h
  2781. @result{}
  2782. #(((braz . "zonk")) ((foo . "bar")) () () () () ((frob . #f)))
  2783. (hashq 'frob 7)
  2784. @result{}
  2785. 6
  2786. @end lisp
  2787. You can get the value for a given key with the procedure
  2788. @code{hashq-ref}, but the problem with this procedure is that you
  2789. cannot reliably determine whether a key does exists in the table. The
  2790. reason is that the procedure returns @code{#f} if the key is not in
  2791. the table, but it will return the same value if the key is in the
  2792. table and just happens to have the value @code{#f}, as you can see in
  2793. the following examples.
  2794. @lisp
  2795. (hashq-ref h 'foo)
  2796. @result{}
  2797. "bar"
  2798. (hashq-ref h 'frob)
  2799. @result{}
  2800. #f
  2801. (hashq-ref h 'not-there)
  2802. @result{}
  2803. #f
  2804. @end lisp
  2805. Better is to use the procedure @code{hashq-get-handle}, which makes a
  2806. distinction between the two cases. Just like @code{assq}, this
  2807. procedure returns a key/value-pair on success, and @code{#f} if the
  2808. key is not found.
  2809. @lisp
  2810. (hashq-get-handle h 'foo)
  2811. @result{}
  2812. (foo . "bar")
  2813. (hashq-get-handle h 'not-there)
  2814. @result{}
  2815. #f
  2816. @end lisp
  2817. There is no procedure for calculating the number of key/value-pairs in
  2818. a hash table, but @code{hash-fold} can be used for doing exactly that.
  2819. @lisp
  2820. (hash-fold (lambda (key value seed) (+ 1 seed)) 0 h)
  2821. @result{}
  2822. 3
  2823. @end lisp
  2824. @node Hash Table Reference
  2825. @subsubsection Hash Table Reference
  2826. @c FIXME: Describe in broad terms what happens for resizing, and what
  2827. @c the initial size means for this.
  2828. Like the association list functions, the hash table functions come in
  2829. several varieties, according to the equality test used for the keys.
  2830. Plain @code{hash-} functions use @code{equal?}, @code{hashq-}
  2831. functions use @code{eq?}, @code{hashv-} functions use @code{eqv?}, and
  2832. the @code{hashx-} functions use an application supplied test.
  2833. A single @code{make-hash-table} creates a hash table suitable for use
  2834. with any set of functions, but it's imperative that just one set is
  2835. then used consistently, or results will be unpredictable.
  2836. Hash tables are implemented as a vector indexed by a hash value formed
  2837. from the key, with an association list of key/value pairs for each
  2838. bucket in case distinct keys hash together. Direct access to the
  2839. pairs in those lists is provided by the @code{-handle-} functions.
  2840. The abstract kind of hash tables hide the vector in an opaque object
  2841. that represents the hash table, while for the concrete kind the vector
  2842. @emph{is} the hashtable.
  2843. When the number of table entries in an abstract hash table goes above
  2844. a threshold, the vector is made larger and the entries are rehashed,
  2845. to prevent the bucket lists from becoming too long and slowing down
  2846. accesses. When the number of entries goes below a threshold, the
  2847. vector is shrunk to save space.
  2848. A abstract hash table is created with @code{make-hash-table}. To
  2849. create a vector that is suitable as a hash table, use
  2850. @code{(make-vector @var{size} '())}, for example.
  2851. For the @code{hashx-} ``extended'' routines, an application supplies a
  2852. @var{hash} function producing an integer index like @code{hashq} etc
  2853. below, and an @var{assoc} alist search function like @code{assq} etc
  2854. (@pxref{Retrieving Alist Entries}). Here's an example of such
  2855. functions implementing case-insensitive hashing of string keys,
  2856. @example
  2857. (use-modules (srfi srfi-1)
  2858. (srfi srfi-13))
  2859. (define (my-hash str size)
  2860. (remainder (string-hash-ci str) size))
  2861. (define (my-assoc str alist)
  2862. (find (lambda (pair) (string-ci=? str (car pair))) alist))
  2863. (define my-table (make-hash-table))
  2864. (hashx-set! my-hash my-assoc my-table "foo" 123)
  2865. (hashx-ref my-hash my-assoc my-table "FOO")
  2866. @result{} 123
  2867. @end example
  2868. In a @code{hashx-} @var{hash} function the aim is to spread keys
  2869. across the vector, so bucket lists don't become long. But the actual
  2870. values are arbitrary as long as they're in the range 0 to
  2871. @math{@var{size}-1}. Helpful functions for forming a hash value, in
  2872. addition to @code{hashq} etc below, include @code{symbol-hash}
  2873. (@pxref{Symbol Keys}), @code{string-hash} and @code{string-hash-ci}
  2874. (@pxref{String Comparison}), and @code{char-set-hash}
  2875. (@pxref{Character Set Predicates/Comparison}).
  2876. @sp 1
  2877. @deffn {Scheme Procedure} make-hash-table [size]
  2878. Create a new abstract hash table object, with an optional minimum
  2879. vector @var{size}.
  2880. When @var{size} is given, the table vector will still grow and shrink
  2881. automatically, as described above, but with @var{size} as a minimum.
  2882. If an application knows roughly how many entries the table will hold
  2883. then it can use @var{size} to avoid rehashing when initial entries are
  2884. added.
  2885. @end deffn
  2886. @deffn {Scheme Procedure} hash-table? obj
  2887. @deffnx {C Function} scm_hash_table_p (obj)
  2888. Return @code{#t} if @var{obj} is a abstract hash table object.
  2889. @end deffn
  2890. @deffn {Scheme Procedure} hash-clear! table
  2891. @deffnx {C Function} scm_hash_clear_x (table)
  2892. Remove all items from @var{table} (without triggering a resize).
  2893. @end deffn
  2894. @deffn {Scheme Procedure} hash-ref table key [dflt]
  2895. @deffnx {Scheme Procedure} hashq-ref table key [dflt]
  2896. @deffnx {Scheme Procedure} hashv-ref table key [dflt]
  2897. @deffnx {Scheme Procedure} hashx-ref hash assoc table key [dflt]
  2898. @deffnx {C Function} scm_hash_ref (table, key, dflt)
  2899. @deffnx {C Function} scm_hashq_ref (table, key, dflt)
  2900. @deffnx {C Function} scm_hashv_ref (table, key, dflt)
  2901. @deffnx {C Function} scm_hashx_ref (hash, assoc, table, key, dflt)
  2902. Lookup @var{key} in the given hash @var{table}, and return the
  2903. associated value. If @var{key} is not found, return @var{dflt}, or
  2904. @code{#f} if @var{dflt} is not given.
  2905. @end deffn
  2906. @deffn {Scheme Procedure} hash-set! table key val
  2907. @deffnx {Scheme Procedure} hashq-set! table key val
  2908. @deffnx {Scheme Procedure} hashv-set! table key val
  2909. @deffnx {Scheme Procedure} hashx-set! hash assoc table key val
  2910. @deffnx {C Function} scm_hash_set_x (table, key, val)
  2911. @deffnx {C Function} scm_hashq_set_x (table, key, val)
  2912. @deffnx {C Function} scm_hashv_set_x (table, key, val)
  2913. @deffnx {C Function} scm_hashx_set_x (hash, assoc, table, key, val)
  2914. Associate @var{val} with @var{key} in the given hash @var{table}. If
  2915. @var{key} is already present then it's associated value is changed.
  2916. If it's not present then a new entry is created.
  2917. @end deffn
  2918. @deffn {Scheme Procedure} hash-remove! table key
  2919. @deffnx {Scheme Procedure} hashq-remove! table key
  2920. @deffnx {Scheme Procedure} hashv-remove! table key
  2921. @deffnx {Scheme Procedure} hashx-remove! hash assoc table key
  2922. @deffnx {C Function} scm_hash_remove_x (table, key)
  2923. @deffnx {C Function} scm_hashq_remove_x (table, key)
  2924. @deffnx {C Function} scm_hashv_remove_x (table, key)
  2925. @deffnx {C Function} scm_hashx_remove_x (hash, assoc, table, key)
  2926. Remove any association for @var{key} in the given hash @var{table}.
  2927. If @var{key} is not in @var{table} then nothing is done.
  2928. @end deffn
  2929. @deffn {Scheme Procedure} hash key size
  2930. @deffnx {Scheme Procedure} hashq key size
  2931. @deffnx {Scheme Procedure} hashv key size
  2932. @deffnx {C Function} scm_hash (key, size)
  2933. @deffnx {C Function} scm_hashq (key, size)
  2934. @deffnx {C Function} scm_hashv (key, size)
  2935. Return a hash value for @var{key}. This is a number in the range
  2936. @math{0} to @math{@var{size}-1}, which is suitable for use in a hash
  2937. table of the given @var{size}.
  2938. Note that @code{hashq} and @code{hashv} may use internal addresses of
  2939. objects, so if an object is garbage collected and re-created it can
  2940. have a different hash value, even when the two are notionally
  2941. @code{eq?}. For instance with symbols,
  2942. @example
  2943. (hashq 'something 123) @result{} 19
  2944. (gc)
  2945. (hashq 'something 123) @result{} 62
  2946. @end example
  2947. In normal use this is not a problem, since an object entered into a
  2948. hash table won't be garbage collected until removed. It's only if
  2949. hashing calculations are somehow separated from normal references that
  2950. its lifetime needs to be considered.
  2951. @end deffn
  2952. @deffn {Scheme Procedure} hash-get-handle table key
  2953. @deffnx {Scheme Procedure} hashq-get-handle table key
  2954. @deffnx {Scheme Procedure} hashv-get-handle table key
  2955. @deffnx {Scheme Procedure} hashx-get-handle hash assoc table key
  2956. @deffnx {C Function} scm_hash_get_handle (table, key)
  2957. @deffnx {C Function} scm_hashq_get_handle (table, key)
  2958. @deffnx {C Function} scm_hashv_get_handle (table, key)
  2959. @deffnx {C Function} scm_hashx_get_handle (hash, assoc, table, key)
  2960. Return the @code{(@var{key} . @var{value})} pair for @var{key} in the
  2961. given hash @var{table}, or @code{#f} if @var{key} is not in
  2962. @var{table}.
  2963. @end deffn
  2964. @deffn {Scheme Procedure} hash-create-handle! table key init
  2965. @deffnx {Scheme Procedure} hashq-create-handle! table key init
  2966. @deffnx {Scheme Procedure} hashv-create-handle! table key init
  2967. @deffnx {Scheme Procedure} hashx-create-handle! hash assoc table key init
  2968. @deffnx {C Function} scm_hash_create_handle_x (table, key, init)
  2969. @deffnx {C Function} scm_hashq_create_handle_x (table, key, init)
  2970. @deffnx {C Function} scm_hashv_create_handle_x (table, key, init)
  2971. @deffnx {C Function} scm_hashx_create_handle_x (hash, assoc, table, key, init)
  2972. Return the @code{(@var{key} . @var{value})} pair for @var{key} in the
  2973. given hash @var{table}. If @var{key} is not in @var{table} then
  2974. create an entry for it with @var{init} as the value, and return that
  2975. pair.
  2976. @end deffn
  2977. @deffn {Scheme Procedure} hash-map->list proc table
  2978. @deffnx {Scheme Procedure} hash-for-each proc table
  2979. @deffnx {C Function} scm_hash_map_to_list (proc, table)
  2980. @deffnx {C Function} scm_hash_for_each (proc, table)
  2981. Apply @var{proc} to the entries in the given hash @var{table}. Each
  2982. call is @code{(@var{proc} @var{key} @var{value})}. @code{hash-map->list}
  2983. returns a list of the results from these calls, @code{hash-for-each}
  2984. discards the results and returns an unspecified value.
  2985. Calls are made over the table entries in an unspecified order, and for
  2986. @code{hash-map->list} the order of the values in the returned list is
  2987. unspecified. Results will be unpredictable if @var{table} is modified
  2988. while iterating.
  2989. For example the following returns a new alist comprising all the
  2990. entries from @code{mytable}, in no particular order.
  2991. @example
  2992. (hash-map->list cons mytable)
  2993. @end example
  2994. @end deffn
  2995. @deffn {Scheme Procedure} hash-for-each-handle proc table
  2996. @deffnx {C Function} scm_hash_for_each_handle (proc, table)
  2997. Apply @var{proc} to the entries in the given hash @var{table}. Each
  2998. call is @code{(@var{proc} @var{handle})}, where @var{handle} is a
  2999. @code{(@var{key} . @var{value})} pair. Return an unspecified value.
  3000. @code{hash-for-each-handle} differs from @code{hash-for-each} only in
  3001. the argument list of @var{proc}.
  3002. @end deffn
  3003. @deffn {Scheme Procedure} hash-fold proc init table
  3004. @deffnx {C Function} scm_hash_fold (proc, init, table)
  3005. Accumulate a result by applying @var{proc} to the elements of the
  3006. given hash @var{table}. Each call is @code{(@var{proc} @var{key}
  3007. @var{value} @var{prior-result})}, where @var{key} and @var{value} are
  3008. from the @var{table} and @var{prior-result} is the return from the
  3009. previous @var{proc} call. For the first call, @var{prior-result} is
  3010. the given @var{init} value.
  3011. Calls are made over the table entries in an unspecified order.
  3012. Results will be unpredictable if @var{table} is modified while
  3013. @code{hash-fold} is running.
  3014. For example, the following returns a count of how many keys in
  3015. @code{mytable} are strings.
  3016. @example
  3017. (hash-fold (lambda (key value prior)
  3018. (if (string? key) (1+ prior) prior))
  3019. 0 mytable)
  3020. @end example
  3021. @end deffn
  3022. @c Local Variables:
  3023. @c TeX-master: "guile.texi"
  3024. @c End: