2
// -------------------------------------------------------------------
3
// MiniExp - Library for handling lisp expressions
4
// Copyright (c) 2005 Leon Bottou
6
// This software is subject to, and may be distributed under, the
7
// GNU General Public License, either Version 2 of the license,
8
// or (at your option) any later version. The license should have
9
// accompanied the software or you may obtain a copy of the license
10
// from the Free Software Foundation at http://www.fsf.org .
12
// This program is distributed in the hope that it will be useful,
13
// but WITHOUT ANY WARRANTY; without even the implied warranty of
14
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15
// GNU General Public License for more details.
16
// -------------------------------------------------------------------
32
# define MINILISPAPI __declspec(dllexport)
34
# define MINILISPAPI __declspec(dllimport)
39
# define MINILISPAPI /**/
43
/* -------------------------------------------------- */
44
/* LISP EXPRESSIONS */
45
/* -------------------------------------------------- */
48
Opaque pointer type representing a lisp expression,
49
also known as s-expression.
50
S-expressions can be viewed as a simple and powerful
51
alternative to XML. DjVu uses s-expressions to handle
52
annotations. Both the decoding api <ddjvuapi.h> and
53
program <djvused> use s-expressions to describe the
54
hidden text information and the navigation
58
typedef struct miniexp_s* miniexp_t;
61
/* There are four basic types of lisp expressions,
62
numbers, symbols, pairs, and objects.
63
The latter category can represent any c++ object
64
that inherits class <miniobj_t> defined later in this file.
65
The only such objects defined in this file are strings. */
68
/* -------- NUMBERS -------- */
70
/* Minilisp numbers can represent any integer
71
in range [-2^29...2^29-1] */
75
Tests if an expression is a number. */
77
static inline int miniexp_numberp(miniexp_t p) {
78
return (((size_t)(p)&3)==3);
82
Returns the integer corresponding to a lisp expression.
83
Assume that the expression is indeed a number. */
85
static inline int miniexp_to_int(miniexp_t p) {
86
return (((int)(size_t)(p))>>2);
90
Constructs the expression corresponding to an integer. */
92
static inline miniexp_t miniexp_number(int x) {
93
return (miniexp_t) (size_t) ((x<<2)|3);
98
/* -------- SYMBOLS -------- */
100
/* The textual representation of a minilisp symbol is a
101
sequence of printable characters forming an identifier.
102
Each symbol has a unique representation and remain
103
permanently allocated. To compare two symbols,
104
simply compare the <miniexp_t> pointers. */
107
/* miniexp_symbolp --
108
Tests if an expression is a symbol. */
110
static inline int miniexp_symbolp(miniexp_t p) {
111
return ((((size_t)p)&3)==2);
114
/* miniexp_to_name --
115
Returns the symbol name as a string.
116
Returns NULL if the expression is not a symbol. */
118
MINILISPAPI const char* miniexp_to_name(miniexp_t p);
121
Returns the unique symbol expression with the specified name. */
123
MINILISPAPI miniexp_t miniexp_symbol(const char *name);
127
/* -------- PAIRS -------- */
129
/* Pairs (also named "cons") are the basic building blocks for
130
minilisp lists. Each pair contains two expression:
131
- the <car> represents the first element of a list.
132
- the <cdr> usually is a pair representing the rest of the list.
133
The empty list is represented by a null pointer. */
139
#define miniexp_nil ((miniexp_t)(size_t)0)
142
An invalid expression used to represent
143
various exceptional conditions. */
145
#define miniexp_dummy ((miniexp_t)(size_t)2)
148
Tests if an expression is either a pair or the empty list. */
150
static inline int miniexp_listp(miniexp_t p) {
151
return ((((size_t)p)&3)==0);
155
Tests if an expression is a pair. */
157
static inline int miniexp_consp(miniexp_t p) {
158
return p && miniexp_listp(p);
162
Returns the length of a list.
163
Returns 0 for non lists, -1 for circular lists. */
165
MINILISPAPI int miniexp_length(miniexp_t p);
169
Returns the car or cdr of a pair. */
171
static inline miniexp_t miniexp_car(miniexp_t p) {
172
if (miniexp_consp(p))
173
return ((miniexp_t*)p)[0];
177
static inline miniexp_t miniexp_cdr(miniexp_t p) {
178
if (miniexp_consp(p))
179
return ((miniexp_t*)p)[1];
184
Represent common combinations of car and cdr. */
186
MINILISPAPI miniexp_t miniexp_caar (miniexp_t p);
187
MINILISPAPI miniexp_t miniexp_cadr (miniexp_t p);
188
MINILISPAPI miniexp_t miniexp_cdar (miniexp_t p);
189
MINILISPAPI miniexp_t miniexp_cddr (miniexp_t p);
190
MINILISPAPI miniexp_t miniexp_caddr(miniexp_t p);
191
MINILISPAPI miniexp_t miniexp_cdddr(miniexp_t p);
194
Returns the n-th element of a list. */
196
MINILISPAPI miniexp_t miniexp_nth(int n, miniexp_t l);
199
Constructs a pair. */
201
MINILISPAPI miniexp_t miniexp_cons(miniexp_t car, miniexp_t cdr);
205
Changes the car or the cdr of a pair. */
207
MINILISPAPI miniexp_t miniexp_rplaca(miniexp_t pair, miniexp_t newcar);
208
MINILISPAPI miniexp_t miniexp_rplacd(miniexp_t pair, miniexp_t newcdr);
210
/* miniexp_reverse --
211
Reverses a list in place. */
213
MINILISPAPI miniexp_t miniexp_reverse(miniexp_t p);
216
/* -------- OBJECTS (GENERIC) -------- */
218
/* Object expressions represent a c++ object
219
that inherits class <miniobj_t> defined later.
220
Each object expression has a symbolic class name
221
and a pointer to the c++ object. */
223
/* miniexp_objectp --
224
Tests if an expression is an object. */
226
static inline int miniexp_objectp(miniexp_t p) {
227
return ((((size_t)p)&3)==1);
230
/* miniexp_classof --
231
Returns the symbolic class of an expression.
232
Returns nil if the expression is not an object. */
234
MINILISPAPI miniexp_t miniexp_classof(miniexp_t p);
237
If <p> is an instance of class named <c> or one of
238
its subclasses, returns the actual class name.
239
Otherwise returns miniexp_nil. */
241
MINILISPAPI miniexp_t miniexp_isa(miniexp_t p, miniexp_t c);
244
/* -------- OBJECTS (STRINGS) -------- */
246
/* miniexp_stringp --
247
Tests if an expression is a string. */
249
MINILISPAPI int miniexp_stringp(miniexp_t p);
252
Returns the c string represented by the expression.
253
Returns NULL if the expression is not a string.
254
The c string remains valid as long as the
255
corresponding lisp object exists. */
257
MINILISPAPI const char *miniexp_to_str(miniexp_t p);
260
Constructs a string expression by copying string s. */
262
MINILISPAPI miniexp_t miniexp_string(const char *s);
264
/* miniexp_substring --
265
Constructs a string expression by copying
266
at most n character from string s. */
268
MINILISPAPI miniexp_t miniexp_substring(const char *s, int n);
271
Concat all the string expressions in list <l>. */
273
MINILISPAPI miniexp_t miniexp_concat(miniexp_t l);
279
/* -------------------------------------------------- */
280
/* GARBAGE COLLECTION */
281
/* -------------------------------------------------- */
284
/* The garbage collector reclaims the memory allocated for
285
lisp expressions no longer in use. It is automatically
286
invoked by the pair and object allocation functions when
287
the available memory runs low. It is however possible to
288
temporarily disable it.
290
The trick is to determine which lisp expressions are in
291
use at a given moment. This package takes a simplistic
292
approach. All objects of type <minivar_t> are chained and
293
can reference an arbitrary lisp expression. Garbage
294
collection preserves all lisp expressions referenced by a
295
minivar, as well as all lisp expressions that can be
296
accessed from these. When called automatically,
297
garbage collection also preserves the sixteen most recently
298
created miniexps in order to make sure that temporaries do
299
not vanish in the middle of complicated C expressions.
301
The minivar class is designed such that C++ program can
302
directly use instances of <minivar_t> as normal
303
<miniexp_t> variables. There is almost no overhead
304
accessing or changing the lisp expression referenced by a
305
minivar. However, the minivar chain must be updated
306
whenever the minivar object is constructed or destructed.
308
Example (in C++ only):
309
miniexp_t copy_in_reverse(miniexp_t p) {
310
minivar_t l = miniexp_nil;
311
while (miniexp_consp(p)) {
312
l = miniexp_cons(miniexp_car(p), l);
318
When to use minivar_t instead of miniexp_t?
320
* A function that only navigates properly secured
321
s-expressions without modifying them does not need to
322
bother about minivars.
324
* Only the following miniexp functions can cause a
325
garbage collection: miniexp_cons(), miniexp_object(),
326
miniexp_string(), miniexp_substring(),
327
miniexp_concat(), miniexp_pprin(), miniexp_pprint(),
328
miniexp_gc(), and minilisp_release_gc_lock(). A
329
function that does not cause calls to these functions
330
does not need to bother about minivars.
332
* Other functions should make sure that all useful
333
s-expression are directly or indirectly secured by a
334
minivar_t object. In case of doubt, use minivars
337
* Function arguments should remain <miniexp_t> in order
338
to allow interoperability with the C language. As a
339
consequence, functions must often copy their arguments
340
into minivars in order to make sure they remain
341
allocated. A small performance improvement can be
342
achieved by deciding that the function should always be
343
called using properly secured arguments. This is more
344
difficult to get right.
346
C programs cannot use minivars as easily as C++ programs.
347
Wrappers are provided to allocate minivars and to access
348
their value. This is somehow inconvenient. It might be
349
more practical to control the garbage collector
350
invocations with <minilisp_acquire_gc_lock()> and
351
<minilisp_release_gc_lock()>... */
355
Invokes the garbage collector now. */
357
MINILISPAPI void minilisp_gc(void);
360
Prints garbage collector statistics. */
362
MINILISPAPI void minilisp_info(void);
364
/* minilisp_acquire_gc_lock --
365
minilisp_release_gc_lock --
366
Temporarily disables automatic garbage collection.
367
Acquire/release pairs may be nested.
368
Both functions return their argument unmodified.
369
This is practical because <minilisp_release_gc_lock>
370
can invoke the garbage collector. Before doing
371
so it stores its argument in a minivar to
375
miniexp_t copy_in_reverse(miniexp_t p) {
377
minilisp_acquire_gc_lock(0);
378
while (miniexp_consp(p)) {
379
l = miniexp_cons(miniexp_car(p), l);
382
return minilisp_release_gc_lock(l);
385
Disabling garbage collection for a long time
386
increases the memory consumption. */
388
MINILISPAPI miniexp_t minilisp_acquire_gc_lock(miniexp_t);
389
MINILISPAPI miniexp_t minilisp_release_gc_lock(miniexp_t);
396
typedef struct minivar_s minivar_t;
401
Wrappers for creating and destroying minivars in C. */
403
MINILISPAPI minivar_t *minivar_alloc(void);
404
MINILISPAPI void minivar_free(minivar_t *v);
406
/* minivar_pointer --
407
Wrappers to access the lisp expression referenced
408
by a minivar. This function returns a pointer
409
to the actual miniexp_t variable. */
411
MINILISPAPI miniexp_t *minivar_pointer(minivar_t *v);
414
Setting the debug flag runs the garbage collector
415
very often. This is extremely slow, but can be
416
useful to debug memory allocation problems. */
418
MINILISPAPI void minilisp_debug(int debugflag);
420
/* minilisp_finish --
421
Deallocates everything. This is only useful when using
422
development tools designed to check for memory leaks.
423
No miniexp function can be used after calling this. */
425
MINILISPAPI void minilisp_finish(void);
428
/* -------------------------------------------------- */
430
/* -------------------------------------------------- */
432
/* Notes about the textual representation of miniexps.
434
- Special characters are:
435
* the parenthesis <(> and <)>,
436
* the double quote <">,
437
* the vertical bar <|>,
438
* any ascii character with a non zero entry
439
in array <minilisp_macrochar_parser>.
441
- Symbols are represented by their name.
442
Vertical bars <|> can be used to delimit names that
443
contain blanks, special characters, non printable
444
characters, non ascii characters, or
445
can be confused for a number.
447
- Numbers follow the syntax specified by the C
448
function strtol() with base=0.
450
- Strings are delimited by double quotes.
451
All C string escapes are recognized.
452
Non printable ascii characters must be escaped.
454
- List are represented by an open parenthesis <(>
455
followed by the space separated list elements,
456
followed by a closing parenthesis <)>.
457
When the cdr of the last pair is non zero,
458
the closed parenthesis is preceded by
459
a space, a dot <.>, a space, and the textual
460
representation of the cdr.
462
- When the parser encounters an ascii character corresponding
463
to a non zero function pointer in <minilisp_macrochar_parser>,
464
the function is invoked and must return a possibly empty
465
list of miniexps to be returned by subsequent
466
invocations of the parser. */
469
/* minilisp_puts/getc/ungetc --
470
All minilisp i/o is performed by invoking
471
these functions pointers. */
473
extern MINILISPAPI int (*minilisp_puts)(const char *s);
474
extern MINILISPAPI int (*minilisp_getc)(void);
475
extern MINILISPAPI int (*minilisp_ungetc)(int c);
477
/* minilisp_set_output --
478
minilisp_set_input --
479
Sets the above function to read/write from/to file f.
480
Only defined when <stdio.h> has been included. */
483
MINILISPAPI void minilisp_set_output(FILE *f);
484
MINILISPAPI void minilisp_set_input(FILE *f);
488
Reads an expression by repeatedly
489
invoking <minilisp_getc> and <minilisp_ungetc>.
490
Returns <miniexp_dummy> when an error occurs. */
492
MINILISPAPI miniexp_t miniexp_read(void);
496
Prints a minilisp expression by repeatedly invoking <minilisp_puts>.
497
Only <minilisp_print> outputs a final newline character.
498
These functions are safe to call anytime. */
500
MINILISPAPI miniexp_t miniexp_prin(miniexp_t p);
501
MINILISPAPI miniexp_t miniexp_print(miniexp_t p);
505
Prints a minilisp expression with reasonably pretty line breaks.
506
Argument <width> is the intended number of columns.
507
Only <minilisp_pprint> outputs a final newline character.
508
These functions can cause a garbage collection to occur. */
510
MINILISPAPI miniexp_t miniexp_pprin(miniexp_t p, int width);
511
MINILISPAPI miniexp_t miniexp_pprint(miniexp_t p, int width);
514
Returns a string containing the textual representation
515
of a minilisp expression. Set argument <width> to zero
516
to output a single line, or to a positive value to
517
perform pretty line breaks for this intended number of columns.
518
These functions can cause a garbage collection to occur.
519
It works by temporarily redefining <minilisp_puts>. */
521
MINILISPAPI miniexp_t miniexp_pname(miniexp_t p, int width);
523
/* minilisp_print_7bits --
524
When this flag is set, all non ascii characters
525
in strings are escaped in octal. */
527
extern MINILISPAPI int minilisp_print_7bits;
529
/* minilisp_macrochar_parser --
530
A non zero entry in this array defines a special parsing
531
function that runs when the corresponding character is
534
extern MINILISPAPI miniexp_t (*minilisp_macrochar_parser[128])(void);
538
/* -------------------------------------------------- */
539
/* STUFF FOR C++ ONLY */
540
/* -------------------------------------------------- */
548
typedef void minilisp_mark_t(miniexp_t *pp);
550
/* -------- MINIVARS -------- */
553
A class for protected garbage collector variables. */
563
minivar_t(miniexp_t p);
564
minivar_t(const minivar_t &v);
565
operator miniexp_t&() { return data; }
566
miniexp_t* operator&() { return &data; }
567
minivar_t& operator=(miniexp_t p) { data = p; return *this; }
568
minivar_t& operator=(const minivar_t &v) { data = v.data; return *this; }
569
~minivar_t() { if ((*pprev = next)) next->pprev = pprev; }
570
#ifdef MINIEXP_IMPLEMENTATION
571
static minivar_t *vars;
572
static void mark(minilisp_mark_t*);
577
/* -------- MINIOBJ -------- */
581
The base class for c++ objects
582
represented by object expressions. */
587
virtual ~miniobj_t();
589
/* --- stuff defined by MINIOBJ_DECLARE --- */
590
/* classname: a symbol characterizing this class. */
591
static const miniexp_t classname;
592
/* classof: class name symbol for this object. */
593
virtual miniexp_t classof() const = 0;
594
/* isa -- tests if this is an instance of <classname>. */
595
virtual bool isa(miniexp_t classname) const;
597
/* --- optional stuff --- */
598
/* pname: returns a printable name for this object.
599
The caller must deallocate the result with delete[]. */
600
virtual char *pname() const;
601
/* mark: iterates over miniexps contained by this object
602
for garbage collecting purposes. */
603
virtual void mark(minilisp_mark_t*);
604
/* destroy: called by the garbage collector to
605
deallocate the object. Defaults to 'delete this'. */
606
virtual void destroy();
610
/* MINIOBJ_DECLARE --
612
Useful code fragments for implementing
613
the mandatory part of miniobj subclasses. */
615
#define MINIOBJ_DECLARE(cls, supercls, name) \
616
public: static const miniexp_t classname; \
617
virtual miniexp_t classof() const; \
618
virtual bool isa(miniexp_t) const;
620
#define MINIOBJ_IMPLEMENT(cls, supercls, name)\
621
const miniexp_t cls::classname = miniexp_symbol(name);\
622
miniexp_t cls::classof() const {\
623
return cls::classname; }\
624
bool cls::isa(miniexp_t n) const {\
625
return (cls::classname==n) || (supercls::isa(n)); }
629
Returns a pointer to the object represented by an lisp
630
expression. Returns NULL if the expression is not an
634
static inline miniobj_t *miniexp_to_obj(miniexp_t p) {
635
if (miniexp_objectp(p))
636
return ((miniobj_t**)(((size_t)p)&~((size_t)3)))[0];
641
Create an object expression for a given object. */
643
MINILISPAPI miniexp_t miniexp_object(miniobj_t *obj);
646
#endif /* __cplusplus */
652
/* -------------------------------------------------- */
654
/* -------------------------------------------------- */
656
#endif /* MINIEXP_H */