SAL (Stephe's Ada Library)

Current version: 2.00

SAL is a collection of stuff I've found useful in my projects.

A large part of SAL provides a coherent set of generic abstract data types, intended to be yet another entry in the "Standard Ada Library" discussion. My goal in this part of SAL was to provide Ada packages that take full advantage of the flexibility and power of Ada generics, while at the same time making things relatively easy for the casual user. See here for more on my design philosophy.

Another large part of SAL provides math operations for kinematics and dynamics of masses in 3 dimensional space. Cartesian vectors, quaternions, orthonormal rotation matrices, moments of inertia, forces, acceleration, velocity are supported, in 3 and 6 degrees of freedom (translation and rotation). I've used this library for both robotics and satelite simulation. This portion is partially documented in spacecraft_math.pdf

Download the source in tar.gz format. Then follow the simple installation instructions.

Review the release history.

Design philosophy

SAL grew out of my desire to provide abstract data types and algorithms that could work with the widest possible range of Ada types. I did not want to build a direct replacement for the C++ Standard Template Library; I wanted to see what I could accomplish by pushing the generics in Ada as far as I could.

This was started in 1997, well before the Ada 2005 standard Containers effort. The SAL design is quite different from the Containers design; I believe both packages are useful.

So far, SAL does not take advantage of any Ada 2005 features, except for 'raise .. with' and the Ada.Text_IO.Get_Line function. It probably will evolve to use more Ada 2005 features in the future.

Since Ada allows abstract data types that are polymorphic or not, and in some applications polymorphism is not desired, I provide both kinds of data types. The child package tree rooted at SAL.Gen (for generic) provides non-polymorphic data types, while the tree rooted at SAL.Poly provides polymorphic data types. However, it turns out the Poly packages are not much more useful than the Gen packages (at least in my applications), so I stopped writing Poly packages after the first few.

If the item type is indefinite, the abstract data type packages require helper functions that do allocation and deallocation. If the item type is not indefinite, providing these helper functions is a chore. The SAL.Aux packages simplify that chore.

Here's a short list of some of the data types provided by SAL. See the source for complete details on the packages currently provided.

SAL.Poly.Unbounded_Arrays provides polymorphic unbounded arrays of indefinite types.
SAL.Gen.Lists.Double provides doubly-linked lists. Since this package is in the Gen tree, it does not use Ada.Finalization.Controlled (because that is tagged), so the user is responsible for freeing the list when done.
SAL.Poly.Lists.Double provides polymorphic doubly-linked lists, using Ada.Finalization to manage the list.
SAL.Gen.Stacks.Bounded_Nonlimited provides stacks of non-limited types, with a fixed maximum size.
SAL.Gen.Stacks.Bounded_limited provides stacks of limited types, with a fixed maximum size.
SAL.Poly.Stacks.Unbounded_Array provides polymorphic stacks of indefinite types, implemented with an unbounded array so there is no fixed maximum size.
SAL.Poly.Binary_Trees.Sorted provides sorted binary trees for indefinite limited types.
SAL.Poly.Function.Tables.Monotonic.First_Order provides invertible functions expressed as a table of value pairs, with first-order interpolation on lookup.

One purpose of a coherent set of abstract data types is to provide algorithms that can be used with them. SAL has a small set of algorithm packages, rooted at SAL.Gen.Alg. The root packages take generic formal parameters that are common to all the algorithms in the tree; child packages may require additional functions (such as comparison). In one sense, it is these root algorithm packages that define a SAL container; any abstract data type that can be used with SAL.Gen.Alg is a SAL container. This contrasts with the C++ Standard Template Library approach of defining a class hierarchy, and algorithms that work with various levels in the hierarchy. SAL does not have a common root container type. Here are a couple of algorithm packages:

SAL.Gen.Alg.Find_Binary provides a binary search algorithm on containers that can provide a Middle function for iterators.
SAL.Gen.Alg.Find_Linear provides a linear search algorithm on containers that are sorted.

Ada provides a wide range of types; definite/indefinite, limited/non-limited, tagged/non-tagged, abstract/concrete. By contrast, C++ classes can only be abstract or concrete; there are no other choices. A C++ class corresponds to an Ada non-limited tagged type, either abstract or concrete. This range of Ada types complicates container packages; we want to allow the item type for container packages to be any possible Ada type. In practice, this is not possible, but it is possible to allow the item type to cover most of the possibilities.

Each package that does allocation takes a generic Storage_Pool parameter. This allows users to implement their own storage pools, and still use SAL. I use this capability in the tests to show that deallocation is done properly. Unfortunately, Ada does not allow a default parameter for the Storage_Pools, so even novice users must provide a parameter.
Each package providing a container allows the item type to be indefinite, and in most cases limited indefinite. This means that allocators must be used, and the actual container type contains pointers. To ensure that allocation and deallocation are done properly, the container package takes generic formal subprograms that allocate and free individual items, and uses them at the appropriate places in the container operations. Auxiliary packages are provided that simplify the task of providing null allocation functions for definite non-limited types, so the one container package can be used with the widest range of Ada types.
Access functions are provided to retrieve items from containers. If the container is instantiated to use access types, the access functions allow operating on items in place in containers. This can be a problem in sorted containers; it is up to the user to resort the container if a key value is changed. Thus SAL favors flexibility over strict rule enforcement.
Iterators for container types in the Gen hierarchy are declared in a child package. In the Poly hierarchy, they are in the main container package. If the Poly iterators were in a child package, they would have to take class-wide arguments, and they would not match the profiles required by Gen.Alg. Container types in the Gen hierarchy do not have this problem; keeping the iterators in child packages allows the user to instantiate them only if needed.
Iterators generally do not contain a reference to a container (one exception is SAL.Aux.Enum_Iterators, which provides iterators for plain Ada arrays). This greatly simplifies declaring iterators, which would otherwise almost always require 'Unchecked_Access (I have not yet investigated whether Ada 2005 makes this better). On the other hand, it means the iterator operations cannot enforce the requirement that iterators be used with only one container. It also means the iterator cannot tell if the container has been deleted. Again, SAL favors flexibility over strict control. The Ada 2005 standard Containers library makes the opposite choice; it favors safety over flexibility.
Iterators are non-limited, so they can be copied. This can lead to dangling pointers if abused, but it greatly simplifies writing algorithms.
The Insert_Before (Iterator) operation has a simple meaning when Iterator is null; it inserts after the tail of a list (which is otherwise impossible with Insert_Before). Similarly, Insert_After (null) inserts before the head of a list. This makes it easier to write algorithms using these functions; there are fewer special cases.
Gen.Alg.Container_Type is indefinite, to allow more general container types. This means Gen.Alg.Find_Linear.Sorted.Sort takes a Temp_Container argument rather than declaring it locally. Thus the user is forced to provide temporary storage; this gives the user better control over memory usage anyway, so it's a good thing.
Gen.Alg supports non-limited containers, and thus requires a Copy operation for items. When instantiating with limited items, Copy should raise SAL.Invalid_Operation. An alternate design would be to provide both Gen.Alg_Limited and Gen.Alg_Non_Limited; that requires maintaining two copies of each algorithm, which is too high a burden.
In sorted containers, the key is assumed stored in Item_Type, accessed via Item_Node_Type. This allows for keys that are complex functions of Item_Type, including caching.

SAL.Gen.Alg.Find_Linear.Key_Type is indefinite limited private to support keys like:

type Keys_Type (Label : Label_Type) is record
      case Label is
      when Muppet =>
         Arms    : Integer;
         Fingers : Integer;
      when Beanie =>
         Legs : Integer;
      end case;
   end record;

This means we also require several versions of Is_*_Equal, rather than a single To_Key.

Flexibility is emphasized over efficiency. For example, the package SAL.Simple.Function_Tables.Monotonic.First_Order contains an alternate implementation of lookup tables, using SAL.Simple.Searches.Binary, while SAL.Poly.Function.Tables.Monotonic.First_Order uses SAL.Gen.Alg.Find_Binary. SAL.Simple.Searches.Binary uses a simple scalar type for an iterator, while SAL.Gen.Alg.Find_Binary uses a general iterator. The files SAL/Source_Common/Test/time_poly_function_tables_monotonic_first_order.adb and time_simple_function_tables_monotonic_first_order.adb contain programs to time these two implementations. With GNAT 3.15p on Windows 98, the Simple version is about three times as fast. For GNAT 5.04a on Windows XP, this ratio still holds. I wrote the Simple version before I started SAL; I'm keeping it as an example of what can be done to improve efficiency when you relax the requirement for flexibility.

Test code

There is complete test code for each SAL package. The intent is to provide full path coverage. Each test runs autonomously, and most produce an output file that can be compared to known good output. Some tests have been converted to use the AUnit framework, and do the comparisons in the test, rather than generating output files. This was necessary because different platforms produce slightly different results for some of the complex computations in the manipulator packages. As I've gotten used to AUnit, I like it a lot; there is a SAL.AUnit package that provides useful Check functions for writing AUnit based tests. There is a makefile that runs all the tests.

If you find a bug in SAL, let me know. If you are up to it, please try to enhance the appropriate test to pinpoint the bug.

Installation

SAL is distributed in source form only. One way for you to use it is simply to incorporate it in your Ada code just like code you write; you don't need to use my development environment.

Development tools

If you'd like to compile SAL the way I do, here is the list of tools I use, with brief installation hints.

Windows XP
GNAT GPL-2006 or GNAT 5.04a the GNU Ada compiler.
cygwin tools for cvs, make, bash, sh, diff, grep, find, perl, etc.
I use the following packages:
- Base
- Devel/cvs
- Devel/make
- Doc
- Interpreters/Perl
- Net/openssh
- Text/aspell
- Utils/patch
emacs 21.3 the all-around best software development environment. See my emacs customizations.
MiKTeK for documentation.
Maxima 5.9.1 for symbolic algebra used in deriving algorithms.
Add Maxima-5.9.1/bin/ to your path.

cvs2cl.pl for creating a Changelog from CVS.

SAL Installation instructions - download

Download sal-2.00.tar.gz to a temporary directory.
Extract to the directory of your choice (herinafter called "the root directory"). This will create two top-level directories in the root directory:
- SAL contains the source code, test code, and makefiles, totalling about 628 Kb.
- Makerules contains rules for the makefiles (shared among all my projects).

Installation instructions - your way

You can just compile the SAL source as if it were your code.

Download as above.
Delete Makerules and SAL/Build
Add SAL/Source_Common to your development environment's list of source directories, and have fun!

Installation instructions - my way

Download as above.
Define GNAT_VERSION as an environment variable; it must have one of the values "5.04a", "gpl-2006", "3.4.4" (GNAT 3.15p is no longer supported by SAL). This is used to select the proper compiler switches.
Define SAL as an environment variable; its value must be the absolute path to the SAL directory. I define SAL as c:/Stephe/Ada/SAL. Cygwin Gnu make and GNAT can handle Windows device letters and forward slashes.
Define MAKERULES as an environment variable; its value must be the absolute path to the Makerules directory.
From directory SAL/Build/release_windows_x86_gnu, run make. This will compile all the code and run all the tests. The object and ali files are in the same directory as the makefile.
To use the library without project files, add -I$(SAL)/Build/release_windows_x86_gnu to your INCLUDE list.
To use the library with project files, add SAL/Build/release_windows_x86_gnu to ADA_PROJECT_PATHS and add "with sal;" in your project file.
To use debug versions: From directory SAL/Build/debug_windows_x86_gnu, run make. Then put SAL/Build/debug_windows_x86_gnu to ADA_PROJECT_PATHS.

Known Bugs

none :)

History

Version 2.00 18 June 2006

Compiles cleanly with GNAT GPL-2006, GNAT 5.04a
Does not compile with Cygwin release of gcc 3.4.4 Ada; that doesn't support Ada 2005.
Lots of changes; it's been a while :). Not all listed here.
GNAT 3.15p is no longer supported; SAL uses some Ada 2005 syntax.
Lots more AUnit utilities.
Lots more Config_Files features.
Support both left- and right-multiply quaternions, via SAL.Gen_Math.Gen_DOF_3.Gen_Left, .Gen_Wertz. See spacecraft_math.pdf.
Add SAL.Gen_Math.Gen_Linear_Fit, SAL.Gen_Math.Gen_Polynomial_Fit.
Add SAL.Generic_Decimal_Image_Unsigned.
Add SAL.Intel_Hex_IO
Add SAL.Network_Order.Arrays
Delete SAL.Poly.Alg; it was not consitent with SAL.Gen.Alg, and not as useful.

Version 1.70 7 August 2004

Add gtk_more directory, with useful gtk widgets and test utilities. Some of them aren't quite working.
Change gnat project files to a standard naming convention.
Interfaces_More renamed to SAL.Interfaces_More
In SAL.Endianness, add better support for different length bitfields.
In SAL.File_Names, add Replace_Environment_Variables, Resolve_Relative, special case ".".
In SAL.Config_Files:
- use SAL.File_Names.Replace_Environment_Variables to allow environment variables in config file names.
- Add Read_Iterator_Modular
- Add Read (Iterator) to get the current value.
- Allow nodes having a value and children.
In AUnit, add catch all exception handler for Set_Up_Case, Tear_Down_Case.
Add several *.AUnit children, to support AUnit tests of SAL types.
In SAL.Time_Conversions, change Time_Type to fixed point, add extended ASIST format, other functions.
Add Text_IO instantiations for Auto_Text_IO run time.

Version 1.60 3 April 2004

Delete sal-gen_math-gen_gauss; not a good implementation.
New packages:
- sal-file_names
- sal-gen_sets
- sal-network_order-*
- sal-gen-queues-gen_bounded_nonlimited
changes in Config_Files:
- Add option Read_Only on Open.
- Add option Case_Insensitive_Keys on Open.
- Add Iterator_Type for processing lists of keys.
- All errors in the config file raise SAL.Config_File_Error, with a Gnu style error message.
- Add Is_Open.
Add *.AUnit child packages, to aid in writing AUnit tests of code that uses SAL.
sal-gen_math-gen_dof_3.ads: Add "+" renaming of To_Unit_Vector.
In spacecraft_math.tex, significantly improve discussions of left multiply vs right multiply and passive vs active. Add explicit references to Wertz and Kane.

Version 1.51 16 Nov 2003

Replace Build/Gnat_Debug, Build/Gnat_Release with Build/debug_windows_x86_gnu, Build/release_windows_x86_gnu; better organization of compiler options.
Delete _ROOT from all environment variable names.
In spacecraft_math.tex, add discussion of vector, scalar formulation of quaternions.
Move a copy of Grace.Config_Files into SAL; easier to use and maintain.
In AUnit.Test_Cases, add dispatching Set_Up_Case.

Version 1.50 2 Sept 2003

Merge Auto_Text_IO run-time into SAL; SAL.Gen_Array_Text_IO is significantly different.
Use Auto_Text_IO to generate all Text_IO children in SAL; they now all provide Get procedures.
SAL.Polynomials renamed to SAL.Gen_Math.Gen_Polynomials; test changed to an AUnit test.
New package SAL.Gen_Math.Gen_Gauss for Gaussian distributions.
New package SAL.Gen_Math.Gen_Stats for mean and standard deviation.
In SAL.Poly.Lists.Double:
- add procedure Add; rename of Insert_Tail.
- add procedure Replace.
In SAL.Poly.Alg; delete generic parameter Item_Type; only used in lower level packages.
generic_array_text_io_83 renamed to gen_array_text_io_83
test_math_float_den_hart changed to an AUnit test
In Makerules, delete standard_debug.gpr, standard_release.gpr; simpler to use standard_common.gpr directly.

Version 1.06 24 April 2003

Updated to GNAT 3.15p
New package: SAL.Gen_FIFO
SAL.Gen.Alg : move generic formal parameter Item_Type to child package where it is actually needed. (Suggested by a warning in GNAT 5.01).
SAL.Poly.Unbounded_Array : add generic formal parameter Index_Type.
SAL.Poly.Stacks.Unbounded_Array : add procedure Pop (Stack, Item).
SAL.Gen_Array_Text_IO : delete unnecessary generic formal parameter Zero_Index_Type. Note that Auto_Text_IO has a more powerful generic array text io package.
Lots of files : add "constant" where GNAT 3.16a suggests it.
Lots of files : add "pragma Unreferenced" where GNAT 3.15p suggests it.
Add Maxima files for documentation derivations.
Improve some algorithms in SAL.Gen_Math.Gen_DOF_3, Gen_DOF_6 based on Maxima results.
Add Maxima files for documentation derivations.
Add spacecraft_math documentation; documents algorithms in SAL.Gen_Math.Gen_DOF_3, Gen_DOF_6.
Changed some tests to use the Aunit framework; they generated slightly different results on different platforms, so simple diff was no longer enough.
Makefile "include"s are cleaned up; all now done from the top Makefile.

Version 1.05 26 September, 2002

Added Runge-Kutta 4th order integrator (sal-gen_math-gen_runge_kutta_4th.ads), used in 6 DOF kinematic integrator (sal-gen_math-gen_dof_6-gen_integrator.ads).
Gen_Math.Gen_DOF_6.Inertia is no longer private; there was no real reason for it.
Gen_Math.Gen_DOF_3.Gen_Image, Gen_Math.Gen_DOF_6.Gen_Image provide String images of types.
Fixed a bug in Gen_Math.Gen_DOF_3.To_Mag_Axis.
Gen_Math.Gen_DOF_3.Inverse (inertia) is new, and optimized by Maxima code.
Gen_Math.Gen_DOF_6.CM_Mass_Type is new; simpler mass object.
Poly.Unbounded_Arrays now have a default Initialization, so they are easier to use.

Version 1.04b 26 July, 2002

Add Null_List and "function None return Iterator" to SAL.Poly.Lists.Double, for Grace.Lists implementation.

Version 1.04 14 June, 2002

Add SAL.Gen_Math.Gen_Manipulator and associated packages, instantiations, and tests.

Version 1.03 9 December, 2001

Add missing SAL.Endianness package. Clean up SAL.Convert_Word_Order packages, add test.
Add SAL.Gen.Math packages, instantiations, and tests.
Add other missing tests.

Version 1.02 17 November, 2001

In sal-poly-binary_trees-sorted, change Boolean Allow_Duplicate_Keys to enumeral Duplicate_Key_Action.
Add helper package sal-aux-sort_indefinite_items_definite_keys.
Add test for Gray_Code.
Add test for Polynomials.

Version 1.01 2 October, 2000

Significant upgrade; refined notion of "containers", added many containers and algorithms. Upgraded to GNAT 3.13p. Dropped support for ObjectAda.

Version 1.00 19 October, 1999

First release.

my home page.

Author : Stephen Leake

Last modified: Sun Jun 18 12:28:23 Eastern Daylight Time 2006