Hierarchical Packages

1.0 Introduction
2.0 Relative package names
3.0 Compatibility with ANSI Common Lisp
4.0 Package prefixes reserved by Allegro CL
5.0 New Common Lisp functions
6.0 The implementation
7.0 Tests

1.0 Introduction

The Common Lisp package system, designed and standardized some years ago, is not hierarchical. Since Common Lisp was standardized, other languages, including Java and Perl, have evolved namespaces which are hierarchical. This document describes a hierarchical package naming scheme for Common Lisp. We hope that CL implementations other than just Allegro CL will include this facility. All the source code used in Allegro CL to implement the facility is included below.

The goals of hierarchical packages in Common Lisp are:

  • Reduce collisions with user-defined packages: it is a well-known problem that package names used by the Lisp implementation and those defined by users can easily conflict. The intent of hierarchical packages is to reduce such conflicts to a minimum.
  • Improve modularity: the current organization of packages in various implementations has grown over the years and appears somewhat random. Organizing future packages into a hierarchy will help make the intention of the implementation more clear.
  • Foster growth in Common Lisp programs, or modules, available to the CL community: the Perl and Java communities are able to contribute code to repositories, with minimal fear of collision, because of the hierarchical nature of the name spaces used by the contributed code. We want the Lisp community to benefit from shared modules in the same way.

In a nutshell, a dot (.) is used to separate levels in package names, and a leading dot signifies a relative package name. Absolute package names require no modifications to the underlying CL implementation. Relative package names require small and simple modifications, for which the source code is given below.

The choice of dot follows Java. Perl, another language with hierarchical packages,   uses a colon (:) as a delimiter, but the colon is already reserved in Common Lisp.

Franz intends to extend the hierarchy below currently existing packages. For example, we have a test harness available as a patch to ACL 5.0.1 which is in the util.test package.

To get the Hierarchical Packages module, get the new version of code/packages.fasl (perhaps by running sys:update-allegro ) and rebuild your images. Note that there is no way to suppress hierarchical package features once you have the new packages.fasl except by deleting code/packages.fasl and rebuilding your images again. (That may sound bad, but it in fact causes Allegro CL to revert to the packages.fasl in the bundle file.)

2.0 Relative package names

Relative package names are needed for the same reason as relative pathnames, for brevity and to reduce the brittleness of absolute names.

A relative package name is one that begins with one or more dots. A single dot means the current package, two dots mean the parent of the current package, and so on.

Here are some examples, assuming that packages named mypack, mypack.foo, mypack.foo.bar, mypack.foo.baz, mypack.bar, mypack.bar.baz, foo, and foo.bar, have all been created:

relative name current package absolute name of referenced package
foo  any foo
foo.bar any foo.bar
.foo mypack mypack.foo
.foo.bar mypack mypack.foo.bar
..foo mypack.bar mypack.foo
..foo.baz mypack.bar mypack.foo.baz
...foo mypack.bar.baz mypack.foo
. mypack.bar.baz mypack.bar.baz
.. mypack.bar.baz mypack.bar
... mypack.bar.baz mypack

Note 1: To repeat what we said just before the table, all packages in the hierarchy must exist.

Note 2: WARNING ABOUT NICKNAMES! Unless you provide nicknames for your hierarchical packages (and we recommend against doing so because the number gets quite large), you can only use the names supplied. You cannot mix in nicknames or alternate names. cl-user (and user) are nicknames of the common-lisp-user package. Consider the following:

(defpackage :cl-user.foo)

When the current package (the value of *package*) is common-lisp-user, you might expect .foo to refer to cl-user.foo, but it does not. It refers to the non-existent package common-lisp-user.foo. Note that the purpose of nicknames is to provide shorter names in place of the longer names designed to be fully descriptive. The hope is that hierarchical packages makes longer names unnecessary and thus makes nicknames unnecessary.

Note 3: multiple dots can only appear at the beginning. foo.bar..baz does not mean foo.baz -- it is invalid. (Of course, it is perfectly legal to name a package foo.bar..baz but cl:find-package will not process such a name to find foo.baz in the package hierarchy.)

3.0 Compatibility with ANSI Common Lisp

The implementation of hierarchical packages modifies cl:find-package and provides certain auxiliary functions, package-parent, package-children, and relative-package-name-to-package, as described in this section. (defpackage itself requires no modification.)

While the changes to cl:find-package are small and described below, it is an important consideration for authors who would like their programs to run on a variety of implementations that using hierarchical packages will work in an implementation without the modifications discussed in this document. We show why not after describing the changes to cl:find-package.

Absolute hierarchical package names require no changes in the underlying CL implementation.

Changes to cl:find-package:

Using relative hierarchical package names requires a simple modification of cl:find-package.

In ANSI CL, cl:find-package, if passed a package object, returns it; if passed a string, cl:find-package looks for a package with that string as its name or nickname, and returns the package if it finds one and returns nilif it does not; if passed a symbol, the symbol name (a string) is extracted and cl:find-package proceeds as it does with a string.

For implementing hierarchical packages, the behavior when the argument is a package object (return it) does not change. But when the argument is a string starting with one or more dots not directly naming a package, cl:find-package will, instead of returning nil, check whether the string can be resolved as naming a relative package, and if so, return the associated absolute package object. (If the argument is a symbol, the symbol name is extracted and cl:find-package proceeds as it does with a string argument.)

In Allegro CL, cl:find-package passes a string to the function excl::package-name-to-package, which returns a package object or nil. Without hierarchical packages, cl:find-package returns nil if excl::package-name-to-package returns nil. With hierarchical packages, if excl::package-name-to-package returns nil, cl:find-package calls relative-package-name-to-package, which again returns a package object or nil. If nil is returned at this point, cl:find-package returns nil.

The complete source code for the modifications made to Allegro CL (except for the modifications to cl:find-package) is given below and is in the public domain. It can be used by any CL vendor to augment their implementation to behave as this document suggests. cl:find-package should be modified according to the description just above -- trying to resolve a name as relative if the name does not itself name a package.

Note that you should not use leading dots in package names when using hierarchical packages.

Using hierarchical packages without modifying cl:find-package:

Even without the modifications to cl:find-package, authors need not avoid using relative package names, but the ability to reuse relative package names is restricted. The following example illustrates this:

Consider a module foo which is composed of the my.foo.bar and my.foo.baz packages. In the code for each of the these packages there are relative package references, ..bar and ..baz.

Implementations that have the new cl:find-package would have on their *features* list the symbol :relative-package-names.  Then, in the foo module, there would be definitions of the my.foo.bar and my.foo.baz packages like so:

(defpackage :my.foo.bar
  #-relative-package-names (:nicknames #:..bar)
  ...)

(defpackage :my.foo.baz
  #-relative-package-names (:nicknames #:..baz)
  ...)

Then, in a #-relative-package-names implementation, the symbol my.foo.bar:blam would be visible from my.foo.baz as ..bar:blam, just as it would from a #+relative-package-names implementation.

So, even without the implementation of the augmented cl:find-package, one can still write CL code that will work in both types of implementations, but ..bar and ..baz are now used, so you cannot also have otherpack.foo.bar and otherpack.foo.baz and use ..bar and ..baz as relative names. (The point of hierarchical packages, of course, is to allow reusing relative package names.)

4.0 Package prefixes reserved by Allegro CL

From ACL 6.0 and beyond, Franz Inc. intends to put newly created packages under the following top-level names:

  • net -- network related modules
    • uri -- URI/URL/URN parser
    • iserve -- web server
  • xml -- used for generated namespaces
  • java
  • cg -- common graphics
  • ide -- cg-based graphical development environment
  • corba
  • ffi -- foreign function related modules
  • util -- utility modules

The use of these top-level names as packages in applications might run into problems with ACL 6.0 and future versions. Note that all current package names (such as excl, system etc.) will also be used.

5.0 New Common Lisp functions

To facilitate using hierarchical packages, we introduce several new functions, other than the changed cl:find-package: relative-package-name-to-package, package-parent and package-children. The source code for these functions is also given below.

These functions are documented below with their implementation.

6.0 The implementation

;; The following source code is in the public domain.
;; Provided "as is" with no warranty of any kind.  Use at your own risk.
(pushnew :relative-package-names *features*)

(defun relative-package-name-to-package (name)
  ;; Given a package name, a string, do a relative package name lookup.
  ;;
  ;; It is intended that this function will be called from find-package.
  ;; In Allegro, find-package calls package-name-to-package, and the latter
  ;; function calls this function when it does not find the package.
  ;;
  ;; Because this function is called via the reader, we want it to be as
  ;; fast as possible.
  (declare (optimize speed))
  (flet ((relative-to (package name)
	   (if* (string= "" name)
	      then package
	      else (package-name-to-package
		    (concatenate 'simple-string
		      (package-name package) "." name))))
	 (find-non-dot (name)
	   (do* ((len (length name))
		 (i 0 (1+ i)))
	       ((= i len) nil)
	     (declare (fixnum len i))
	     (when (char/= #\. (schar name i)) (return i)))))
    (when (char= #\. (schar (simple-string name) 0))
      (let* ((last-dot-position (or (find-non-dot name) (length name)))
	     (n-dots last-dot-position)
	     (name (subseq name last-dot-position)))
	(cond ((= 1 n-dots)
	       ;; relative to current package
	       (relative-to *package* name))
	      (t
	       ;; relative to our (- n-dots 1)'th parent
	       (let ((p *package*)
		     tmp)
		 (dotimes (i (1- n-dots))
		   (when (not (setq tmp (package-parent p)))
		     (error "The parent of ~a does not exist." p))
		   (setq p tmp))
		 (relative-to p name))))))))

(defun package-parent (package-specifier)
  ;; Given package-specifier, a package, symbol or string, return the
  ;; parent package.  If there is not a parent, signal an error.
  ;;
  ;; Because this function is called via the reader, we want it to be as
  ;; fast as possible.
  (declare (optimize speed))
  (flet ((find-last-dot (name)
	   (do* ((len (1- (length name)))
		 (i len (1- i)))
	       ((= i -1) nil)
	     (declare (fixnum len i))
	     (when (char= #\. (schar name i)) (return i)))))
    (let* ((child (cond ((packagep package-specifier)
			 (package-name package-specifier))
			((symbolp package-specifier)
			 (symbol-name package-specifier))
			((stringp package-specifier) package-specifier)
			(t (error "Illegal package specifier: ~s."
				  package-specifier))))
	   (dot-position (find-last-dot child)))
      (cond (dot-position
	     (let ((parent (subseq child 0 dot-position)))
	       (or (package-name-to-package parent)
		   (error "The parent of ~a does not exist." child))))
	    (t (error "There is no parent of ~a." child))))))

(defun package-children (package-specifier &key (recurse t))
  ;; Given package-specifier, a package, symbol or string, return all the
  ;; packages which are in the hierarchy "under" the given package.  If
  ;; :recurse is nil, then only return the immediate children of the
  ;; package.
  ;;
  ;; While this function is not called via the reader, we do want it to be
  ;; fast.
  (declare (optimize speed))
  (let ((res ())
	(parent (cond ((packagep package-specifier)
		       (package-name package-specifier))
		      ((symbolp package-specifier)
		       (symbol-name package-specifier))
		      ((stringp package-specifier) package-specifier)
		      (t (error "Illegal package specifier: ~s."
				package-specifier)))))
    (labels
	((string-prefix-p (prefix string)
	   ;; Return length of `prefix' if `string' starts with `prefix'.
	   ;; We don't use `search' because it does much more than we need
	   ;; and this version is about 10x faster than calling `search'.
	   (let ((prefix-len (length prefix))
		 (seq-len (length string)))
	     (declare (fixnum prefix-len seq-len))
	     (when (>= prefix-len seq-len)
	       (return-from string-prefix-p nil))
	     (do* ((i 0 (1+ i)))
		 ((= i prefix-len) prefix-len)
	       (declare (fixnum i))
	       (when (not (char= (schar prefix i) (schar string i)))
		 (return nil)))))
	 (test-package (package-name package)
	   (let ((prefix
		  (string-prefix-p (concatenate 'simple-string parent ".")
				   package-name)))
	     (cond (recurse (when prefix (pushnew package res)))
		   (t (when (and prefix
				 (not (find #\. package-name :start prefix)))
			(pushnew package res)))))))

      ;; In Allegro, list-all-packages calls `sort', so use an internal
      ;; method to get the package names.
      #+allegro
      (maphash #'test-package *package-names*)
      #-allegro
      (dolist (package (list-all-packages))
	(funcall #'test-package (package-name package) package))
      
      res)))

7.0 Tests

The following test code can be used to check a hierarchical package implementation. You must use the Allegro CL test harness, documented in the Test Harness document. The test harness is loaded by the (require :tester) form.

;; The following source code is in the public domain.
;; Provided "as is" with no warranty of any kind.  Use at your own risk.
(eval-when (compile eval load)
  (require :tester))

(defpackage :package-tests
  (:use #:common-lisp #:excl #:util.test)
  (:import-from #:excl #:package-children)
  (:import-from #:excl #:package-parent))

(in-package :package-tests)

(defpackage :package-tests.a)
(defpackage :package-tests.a.b)
(defpackage :package-tests.a.b.c)
(defpackage :package-tests.a.b.c.d)
(defpackage :package-tests.a.b.c.d.e)
(defpackage :package-tests.a.b.c.d.f)
(defpackage :package-tests.a.b.c.e)
(defpackage :package-tests.a.b.c.f)
(defpackage :package-tests.a.b.d)
(defpackage :package-tests.a.b.e)
(defpackage :package-tests.a.c)
(defpackage :package-tests.a.d)
(defpackage :package-tests.b)
(defpackage :package-tests.c)
(defpackage :package-tests.d)

(defpackage :package-tests-foo.bar.baz)
(defpackage :package-tests-foo.bar.baz.wham)

(defun do-package-tests ()
  (test t
	(progn #+relative-package-names t
	       #-relative-package-names nil)
	:test #'eq)
  
;;;; test package-children
  (test '("package-tests.a" "package-tests.b"
	  "package-tests.c" "package-tests.d")
	(sort (mapcar #'package-name
		      (package-children :package-tests :recurse nil))
	      #'string<)
	:test #'equal)
  (test '("package-tests.a" "package-tests.a.b" "package-tests.a.b.c"
	  "package-tests.a.b.c.d" "package-tests.a.b.c.d.e"
	  "package-tests.a.b.c.d.f" "package-tests.a.b.c.e"
	  "package-tests.a.b.c.f" "package-tests.a.b.d" "package-tests.a.b.e"
	  "package-tests.a.c" "package-tests.a.d" "package-tests.b"
	  "package-tests.c" "package-tests.d")
	(sort (mapcar #'package-name (package-children :package-tests))
	      #'string<)
	:test #'equal)
  (test '("package-tests.a.b.c.d" "package-tests.a.b.c.d.e"
	  "package-tests.a.b.c.d.f" "package-tests.a.b.c.e"
	  "package-tests.a.b.c.f")
	(sort (mapcar #'package-name (package-children :package-tests.a.b.c))
	      #'string<)
	:test #'equal)
  (test '("package-tests.a.b.c.d" "package-tests.a.b.c.e"
	  "package-tests.a.b.c.f")
	(sort (mapcar #'package-name
		      (package-children :package-tests.a.b.c :recurse nil))
	      #'string<)
	:test #'equal)
  (test '("package-tests.a.b.c.d.e" "package-tests.a.b.c.d.f")
	(sort (mapcar #'package-name (package-children :package-tests.a.b.c.d))
	      #'string<)
	:test #'equal)
  (test '("package-tests.a.b.c.d.e" "package-tests.a.b.c.d.f")
	(sort (mapcar #'package-name
		      (package-children :package-tests.a.b.c.d :recurse nil))
	      #'string<)
	:test #'equal)
  (test '()
	(package-children :package-tests.b)
	:test #'equal)
  (test '()
	(package-children :package-tests.c)
	:test #'equal)
  (test '()
	(package-children :package-tests.d)
	:test #'equal)
  
;;;; test package-parent
  (test (find-package :package-tests)
	(package-parent :package-tests.a))
  (test (find-package :package-tests.a)
	(package-parent :package-tests.a.b))
  (test (find-package :package-tests.a.b)
	(package-parent :package-tests.a.b.c))
  (test (find-package :package-tests.a.b.c)
	(package-parent :package-tests.a.b.c.d))
  (test (find-package :package-tests.a.b.c.d)
	(package-parent :package-tests.a.b.c.d.e))
  (test (find-package :package-tests.a.b.c.d)
	(package-parent :package-tests.a.b.c.d.f))
  (test (find-package :package-tests.a.b.c)
	(package-parent :package-tests.a.b.c.e))
  (test (find-package :package-tests.a.b.c)
	(package-parent :package-tests.a.b.c.f))
  (test (find-package :package-tests.a.b)
	(package-parent :package-tests.a.b.d))
  (test (find-package :package-tests.a.b)
	(package-parent :package-tests.a.b.e))
  (test (find-package :package-tests.a)
	(package-parent :package-tests.a.c))
  (test (find-package :package-tests.a)
	(package-parent :package-tests.a.d))
  (test (find-package :package-tests)
	(package-parent :package-tests.b))
  (test (find-package :package-tests)
	(package-parent :package-tests.c))
  (test (find-package :package-tests)
	(package-parent :package-tests.d))

  (test-error (package-parent :package-tests))
  (test-error (package-parent :package-tests-foo.bar.baz))
  (test-error (package-parent :package-tests-foo.bar))
  (test-error (package-parent :package-tests-foo))
  
;;;; test find-package
  (dolist
      (item
	  '((:package-tests.a         :package-tests.a ".")
	    (:package-tests           :package-tests.a "..")
	    (:package-tests.b         :package-tests.a "..b")
	    (:package-tests.c         :package-tests.a "..c")
	    (:package-tests.d         :package-tests.a "..d")
	    (:package-tests.a.b       :package-tests.b "..a.b")
	    (:package-tests           :package-tests.a.b "...")
	    (:package-tests.b         :package-tests.a.b "...b")
	    (:package-tests.a.b.c.d.f :package-tests.a.b.c.d "...c.d.f")
	    (:package-tests           :package-tests.a.b.c.d ".....")
	    (:package-tests.b         :package-tests.a.b.c.d ".....b")
	    (:package-tests.a.b.c.d   :package-tests.a.b.c.d ".")
	    (:package-tests.a.b.c     :package-tests.a.b.c ".")
	    (:package-tests.a.b       :package-tests.a.b ".")))
    (test (symbol-name (first item))
	  (let* ((*package* (find-package (second item)))
		 (p (find-package (third item))))
	    (cond (p (package-name p))
		  (t (error "could not find package ~s." (third item)))))))

  (test-error (find-package ".."))
  (test-error (find-package "..."))
  (test-error (find-package "...."))
  (test-error (find-package "....foo"))
  (let ((*package* (find-package :package-tests.b)))
    (test-error (find-package "..."))))

(let ((*test-errors* 0)
      (*test-successes* 0)
      (*test-unexpected-failures* 0))
  (format t "Beginning package tests...~%")
  (do-package-tests)
  (format t "Completed package tests.~%")
  (format t "** Successes: ~s~%" *test-successes*)
  (format t "** Errors: ~s~%" *test-errors*)
  (format t "** Unexpected failures: ~s~%" *test-unexpected-failures*))

Last updated on March 29, 2000 09:31:28 Pacific Standard Time

Copyright © 2014 Franz Inc., All Rights Reserved | Privacy Statement
Delicious Google Buzz Twitter Google+