The ucons Reference Manual

Table of Contents

Next: , Previous: , Up: (dir)   [Contents][Index]

The ucons Reference Manual

This is the ucons Reference Manual, generated automatically by Declt version 2.4 patchlevel 1 "Will Decker" on Mon Apr 08 15:13:59 2019 GMT+0.


Next: , Previous: , Up: Top   [Contents][Index]

1 Introduction

#+TITLE: UCONS - Unique CONSes

Some applications benefit a lot by reusing existing cons cells instead of
actual consing.  Usually this technique is called hash consing.  Users of
this technique are e.g. the optimizer of the computer algebra system Maxima
and the theorem prover ACL2.

This particular implementation is intended for use cases where performance
is so critical, that even a single hash table access per cons is too
expensive.  To achieve such near-optimal speed, this library does not
actually provide conses, but uconses.  A ucons has not only a car and a
cdr, but also a table of past users.  Furthermore, the cdr of each ucons is
restricted to other uconses or NIL.  This setup has several advantages:

- Checking whether a certain ucons already exists is a single lookup of its
  car in the table of its cdr.

- The immutability of a ucons is enforced by its defstruct definition

- The compiler has reliable type information of the slots of a ucons.

- Lists of uconses are neither circular, nor improper.

Unfortunately there is also a painful downside of this approach.
Traditional cons cells are a fundamental Lisp data type and well supported
throughout the standard library.  Uconses lack this integration and require
a completely new set of library functions.  Furthermore it must be noted
that uconses are --- except if one explicitly clears the =*root-table*= ---
a permanent memory leak.

Yet if you are willing to accept these trade-offs, uconses offer some
unique benefits:

- their usage is little more expensive than a call to CONS. If you include
  GC time, they can even be much faster.

- given enough potential for structural sharing, uconses can decrease the
  memory consumption of an application by orders of magnitude.

- checks for structural similarity can be done in constant time.  Two ucons
  trees are equal if and only if their roots are EQL.

Benchmarks (SBCL 1.3.20, X86-64 Intel i7-5500U CPU @ 2.40GHz):

#+BEGIN_SRC lisp
(bench  (list 1 2 3 4 5 6 7 8)) ; -> 25.77 nanoseconds
(bench (ulist 1 2 3 4 5 6 7 8)) ; -> 38.18 nanoseconds
#+END_SRC


Next: , Previous: , Up: Top   [Contents][Index]

2 Systems

The main system appears first, followed by any subsystem dependency.


Previous: , Up: Systems   [Contents][Index]

2.1 ucons

Author

Marco Heisig <marco.heisig@fau.de>

License

MIT

Description

Unique conses and functions for working on them.

Dependencies
Source

ucons.asd (file)

Components

Next: , Previous: , Up: Top   [Contents][Index]

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.1 ucons.asd

Location

ucons.asd

Systems

ucons (system)


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.2 ucons/packages.lisp

Parent

ucons (system)

Location

packages.lisp

Packages

ucons


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.3 ucons/ucons.lisp

Dependency

packages.lisp (file)

Parent

ucons (system)

Location

ucons.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.4 ucons/library.lisp

Dependency

ucons.lisp (file)

Parent

ucons (system)

Location

library.lisp

Exported Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.5 ucons/readtable.lisp

Dependency

library.lisp (file)

Parent

ucons (system)

Location

readtable.lisp

Exported Definitions

read-ulist (function)

Internal Definitions

Previous: , Up: Lisp files   [Contents][Index]

3.1.6 ucons/print-object.lisp

Dependency

readtable.lisp (file)

Parent

ucons (system)

Location

print-object.lisp

Internal Definitions

print-list (function)


Next: , Previous: , Up: Top   [Contents][Index]

4 Packages

Packages are listed by definition order.


Previous: , Up: Packages   [Contents][Index]

4.1 ucons

Source

packages.lisp (file)

Use List

common-lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.1 Special variables

Special Variable: *root-table*

The table of all uconses whose cdr is NIL.

Package

ucons

Source

ucons.lisp (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.2 Macros

Macro: do-ulist (VAR ULIST &optional RESULT) &body BODY
Package

ucons

Source

library.lisp (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.3 Compiler macros

Compiler Macro: ulist &rest ARGS
Package

ucons

Source

library.lisp (file)

Compiler Macro: ulist* &rest ARG-FORMS
Package

ucons

Source

library.lisp (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.4 Functions

Function: list-from-ulist ULIST

Return a list of the elements of ULIST.

Package

ucons

Source

library.lisp (file)

Function: make-root-table &key (CACHE CACHE) (SMALL-INTEGER-CACHE SMALL-INTEGER-CACHE)
Package

ucons

Source

ucons.lisp (file)

Function: read-ulist STREAM CHAR
Package

ucons

Source

readtable.lisp (file)

Function: tree-from-utree UTREE

Return a tree of the same shape as UTREE, but where all occuring ulists have been converted to lists.

Package

ucons

Source

library.lisp (file)

Function: ucar INSTANCE
Package

ucons

Source

ucons.lisp (file)

Function: ucdr INSTANCE
Package

ucons

Source

ucons.lisp (file)

Function: ucons CAR CDR

Given a suitable CAR and CDR, return a UCONS that is EQL to all future and past invocation of this function with the same arguments.

Package

ucons

Source

ucons.lisp (file)

Function: uconsp OBJECT
Package

ucons

Source

ucons.lisp (file)

Function: ulength ULIST

Return the length of the given ulist.

Package

ucons

Source

library.lisp (file)

Function: ulist &rest ARGS

Return the ulist associated with the supplied arguments.

Package

ucons

Source

library.lisp (file)

Function: ulist* &rest ARGS

Return the ulist associated with the supplied arguments, but using the last argument as the tail of the constructed ulist.

Package

ucons

Source

library.lisp (file)

Function: ulist-from-list LIST
Package

ucons

Source

library.lisp (file)

Function: umapcar FUNCTION &rest SEQUENCES

Return an ulist containing the results of applying FUNCTION to successive elements of the supplied sequences. The resulting ulist is as long as the shortest supplied sequence.

Package

ucons

Source

library.lisp (file)

Function: utree-from-tree TREE
Package

ucons

Source

library.lisp (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.5 Structures

Structure: ucons ()
Package

ucons

Source

ucons.lisp (file)

Direct superclasses

structure-object (structure)

Direct methods

print-object (method)

Direct slots
Slot: cdr
Type

(or structure-object null)

Readers

ucdr (function)

Writers

(setf ucdr) (function)

Slot: car
Readers

ucar (function)

Writers

(setf ucar) (function)

Slot: table
Type

(or list hash-table)

Readers

utable (function)

Writers

(setf utable) (function)


Previous: , Up: Exported definitions   [Contents][Index]

5.1.6 Types

Type: ulist ()

A list made of UCONSes, or NIL.

Package

ucons

Source

ucons.lisp (file)


Previous: , Up: Definitions   [Contents][Index]

5.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.1 Functions

Function: make-fresh-ucons CAR CDR
Package

ucons

Source

ucons.lisp (file)

Function: print-list LIST STREAM PREFIX SUFFIX
Package

ucons

Source

print-object.lisp (file)

Function: read-right-square-bracket STREAM CHAR
Package

ucons

Source

readtable.lisp (file)

Function: root-table-cache INSTANCE
Package

ucons

Source

ucons.lisp (file)

Function: root-table-small-integer-cache INSTANCE
Package

ucons

Source

ucons.lisp (file)

Function: ucons-hash CAR CDR
Package

ucons

Source

ucons.lisp (file)

Function: ucons-leaf CAR
Package

ucons

Source

ucons.lisp (file)

Function: ucons-list CAR CDR
Package

ucons

Source

ucons.lisp (file)

Function: utable INSTANCE
Function: (setf utable) VALUE INSTANCE
Package

ucons

Source

ucons.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.2 Conditions

Condition: unmatched-closing-square-bracket ()
Package

ucons

Source

readtable.lisp (file)

Direct superclasses

reader-error (condition)


Previous: , Up: Internal definitions   [Contents][Index]

5.2.3 Structures

Structure: root-table ()
Package

ucons

Source

ucons.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: cache
Type

hash-table

Initform

(make-hash-table)

Readers

root-table-cache (function)

Writers

(setf root-table-cache) (function)

Slot: small-integer-cache
Type

(simple-array ucons:ucons (33))

Initform

(let ((array (make-array 33))) (loop ucons::for ucons::index ucons::from -16 ucons::to 16 do (setf (aref array (+ ucons::index 16)) (ucons::make-fresh-ucons ucons::index nil))) array)

Readers

root-table-small-integer-cache (function)

Writers

(setf root-table-small-integer-cache) (function)


Previous: , Up: Top   [Contents][Index]

Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts

Jump to:   F   L   U  
Index Entry  Section

F
File, Lisp, ucons.asd: The ucons<dot>asd file
File, Lisp, ucons/library.lisp: The ucons/library<dot>lisp file
File, Lisp, ucons/packages.lisp: The ucons/packages<dot>lisp file
File, Lisp, ucons/print-object.lisp: The ucons/print-object<dot>lisp file
File, Lisp, ucons/readtable.lisp: The ucons/readtable<dot>lisp file
File, Lisp, ucons/ucons.lisp: The ucons/ucons<dot>lisp file

L
Lisp File, ucons.asd: The ucons<dot>asd file
Lisp File, ucons/library.lisp: The ucons/library<dot>lisp file
Lisp File, ucons/packages.lisp: The ucons/packages<dot>lisp file
Lisp File, ucons/print-object.lisp: The ucons/print-object<dot>lisp file
Lisp File, ucons/readtable.lisp: The ucons/readtable<dot>lisp file
Lisp File, ucons/ucons.lisp: The ucons/ucons<dot>lisp file

U
ucons.asd: The ucons<dot>asd file
ucons/library.lisp: The ucons/library<dot>lisp file
ucons/packages.lisp: The ucons/packages<dot>lisp file
ucons/print-object.lisp: The ucons/print-object<dot>lisp file
ucons/readtable.lisp: The ucons/readtable<dot>lisp file
ucons/ucons.lisp: The ucons/ucons<dot>lisp file

Jump to:   F   L   U  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   (  
C   D   F   L   M   P   R   T   U  
Index Entry  Section

(
(setf utable): Internal functions

C
Compiler Macro, ulist: Exported compiler macros
Compiler Macro, ulist*: Exported compiler macros

D
do-ulist: Exported macros

F
Function, (setf utable): Internal functions
Function, list-from-ulist: Exported functions
Function, make-fresh-ucons: Internal functions
Function, make-root-table: Exported functions
Function, print-list: Internal functions
Function, read-right-square-bracket: Internal functions
Function, read-ulist: Exported functions
Function, root-table-cache: Internal functions
Function, root-table-small-integer-cache: Internal functions
Function, tree-from-utree: Exported functions
Function, ucar: Exported functions
Function, ucdr: Exported functions
Function, ucons: Exported functions
Function, ucons-hash: Internal functions
Function, ucons-leaf: Internal functions
Function, ucons-list: Internal functions
Function, uconsp: Exported functions
Function, ulength: Exported functions
Function, ulist: Exported functions
Function, ulist*: Exported functions
Function, ulist-from-list: Exported functions
Function, umapcar: Exported functions
Function, utable: Internal functions
Function, utree-from-tree: Exported functions

L
list-from-ulist: Exported functions

M
Macro, do-ulist: Exported macros
make-fresh-ucons: Internal functions
make-root-table: Exported functions

P
print-list: Internal functions

R
read-right-square-bracket: Internal functions
read-ulist: Exported functions
root-table-cache: Internal functions
root-table-small-integer-cache: Internal functions

T
tree-from-utree: Exported functions

U
ucar: Exported functions
ucdr: Exported functions
ucons: Exported functions
ucons-hash: Internal functions
ucons-leaf: Internal functions
ucons-list: Internal functions
uconsp: Exported functions
ulength: Exported functions
ulist: Exported compiler macros
ulist: Exported functions
ulist*: Exported compiler macros
ulist*: Exported functions
ulist-from-list: Exported functions
umapcar: Exported functions
utable: Internal functions
utree-from-tree: Exported functions

Jump to:   (  
C   D   F   L   M   P   R   T   U  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables

Jump to:   *  
C   S   T  
Index Entry  Section

*
*root-table*: Exported special variables

C
cache: Internal structures
car: Exported structures
cdr: Exported structures

S
Slot, cache: Internal structures
Slot, car: Exported structures
Slot, cdr: Exported structures
Slot, small-integer-cache: Internal structures
Slot, table: Exported structures
small-integer-cache: Internal structures
Special Variable, *root-table*: Exported special variables

T
table: Exported structures

Jump to:   *  
C   S   T  

Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

Jump to:   C   P   R   S   T   U  
Index Entry  Section

C
Condition, unmatched-closing-square-bracket: Internal conditions

P
Package, ucons: The ucons package

R
root-table: Internal structures

S
Structure, root-table: Internal structures
Structure, ucons: Exported structures
System, ucons: The ucons system

T
Type, ulist: Exported types

U
ucons: The ucons system
ucons: The ucons package
ucons: Exported structures
ulist: Exported types
unmatched-closing-square-bracket: Internal conditions

Jump to:   C   P   R   S   T   U