A Closer Look at Maxima

The primary purpose of software estimation is not to predict a project’s outcome; it is to determine whether a project’s targets are realistic enough to allow the project to be controlled to meet them. — attributed to Steve McConnell, Software Estimation: Demystifying the Black Art

Introduction

This is third in a series of articles starting with The Scope of Mathematical Programming Projects. A number of terms are defined precisely and concepts discussed further in the second article in the series: LAME: A Case Study in Mathematical Programming. In the author’s experience, it is common to encounter extremely optimistic ideas about the scope of mathematical programming projects, where mathematical programming refers to mathematics more advanced than the basic arithmetic used in business applications and other common programming projects. Mathematical programming projects are much more likely to be successful with realistic ideas about the scope, cost, schedule, performance, and risk level of the project.  This article discusses the scope of the software development and mathematical research and development of the widely used free open-source Maxima computer algebra system (CAS).

Maxima is a computer algebra system derived from the DOE (United States Department of Energy) MACSYMA computer algebra system which began development at the Massachusetts Institute of Technology (MIT) in the 1960’s. MACSYMA was one of the first computer algebra systems, a precursor to present day commercial computer algebra systems such as Mathematica and Maple. MACSYMA was developed in large part for use in theoretical physics, hence the funding by the US Department of Energy (formerly the Atomic Energy Commission). According to the Maxima web site:

The Maxima branch of Macsyma was maintained by William Schelter from 1982 until he passed away in 2001. In 1998 he obtained permission to release the source code under the GNU General Public License (GPL).

Maxima was selected for this case study for several reasons. Maxima is a successful widely used research tool with practical applications. It is an example of an “artificial intelligence” program that works, performing a range of functions that used to be performed only by human mathematicians: factoring polynomials, simplifying expressions, symbolic differentiation, symbolic integration, and a number of other mathematical tasks. Maxima has been hosted by the SourceForge open source web site since 2002. SourceForge maintains a record of downloads and copies of all releases of Maxima from Maxima 5.0 in May, 2002 to the present version. The techniques developed to assess the scope of the  LAME free open source MP3 audio encoder project, which is also hosted on SourceForge, can be directly applied to Maxima.

5.23.2-Windows 2011-02-04 20,833 downloads
5.23.1-Windows 2011-01-16 837 downloads
5.23.0-Windows 2011-01-04 4,171 downloads
5.22.1-Windows 2010-08-13 216,085 downloads
5.22.0-Windows 2010-08-04 3,924 downloads
5.21.1-Windows 2010-04-26 57,666 downloads
5.21.0-Windows 2010-04-12 10,266 downloads
5.20.1-Windows 2009-12-14 110,463 downloads
5.20.0-Windows 2009-12-08 5,179 downloads
5.19.2-Windows 2009-08-31 56,554 downloads
5.18.1-Windows 2009-04-20 44,359 downloads
5.17.1-Windows 2008-12-18 39,358 downloads

Table 1 Downloads of Recent Windows Versions of Maxima

5.23.2-Linux 2011-01-17 595 downloads
5.23.1-Linux 2011-01-15 24 downloads
5.23.0-Linux 2010-12-24 396 downloads
5.22.1-Linux 2010-08-12 2,805 downloads
5.22.0-Linux 2010-08-01 318 downloads
5.21.1-Linux 2010-04-24 1,723 downloads
5.21.0-Linux 2010-04-14 946 downloads
5.20.1-Linux 2009-12-14 2,814 downloads
5.20.0-Linux 2009-12-07 327 downloads
5.19.2-Linux 2009-08-30 12,637 downloads

Table 2: Downloads of Recent Linux Versions of Maxima

5.23.2-source 2011-01-17 4,385 downloads
5.23.1-source 2011-01-15 69 downloads
5.23.0-source 2010-12-24 806 downloads
5.22.1-source 2010-08-12 5,552 downloads
5.22.0-source 2010-08-01 955 downloads
5.21.1-source 2010-04-24 3,750 downloads
5.21.0-source 2010-04-10 652 downloads
5.20.1-source 2009-12-14 6,578 downloads
5.20.0-source 2009-12-07 2,420 downloads
5.19.2-source 2009-08-30 4,670 downloads
5.17.1-source 2008-12-15 4,272 downloads

Table 3: Downloads of Recent Source Code for Maxima

5.21.1-MacOS 2010-05-25 11,819 downloads
5.19.2-MacOS 2009-09-01 19,049 downloads
5.19.1-MacOS 2009-08-17 827 downloads
5.18.1-MacOS 2009-04-19 4,297 downloads

Table 4: Downloads of Recent MacOS Versions of Maxima

5.15.0-Linux 2009-07-17
5.17.0-Windows 2008-12-04 82,588 downloads
5.17.0-Linux 2008-12-04 3,658 downloads
5.17.0-source 2008-12-04 3,503 downloads
5.16.3-Windows 2008-08-25 106,713 downloads
5.16.3-source 2008-08-24 10,946 downloads
5.16.3-Linux 2008-08-24 6,247 downloads
5.16.2-Windows 2008-08-18 16,353 downloads
5.16.2-source 2008-08-17 679 downloads
5.16.2-Linux 2008-08-17 1,277 downloads
5.15.0-Windows 2008-04-20 54,046 downloads
5.15.0-source 2008-04-20 5,674 downloads
5.14.0-Windows 2007-12-27 44,019 downloads
5.14.0-source 2007-12-22 28,884 downloads
5.13.0-Windows 2007-09-10 50,353 downloads
5.13.0-source 2007-08-25 6,908 downloads
5.12.0-Windows 2007-06-08 24,356 downloads
5.12.0-source 2007-05-03 6,828 downloads
5.11.0-Windows 2007-02-11 27,251 downloads
5.11.0-source 2006-12-21 6,466 downloads
5.10.0-Windows 2006-10-24 26,853 downloads
5.10.0-source 2006-09-21 5,636 downloads
5.9.3-Windows 2006-06-07 40,848 downloads
5.9.3-source 2006-03-19 7,154 downloads
5.9.3-Linux 2006-03-19 6,038 downloads
5.9.2 2006-01-30 47,706 downloads
5.9.1 2004-09-24 102,642 downloads
5.9.0 2003-02-10 78,537 downloads
historical 2002-05-13 3,056 downloads

Table 5: Downloads of Versions of Maxima from 2002 to 2009

maxima-5.4-beta.tar.gz 2002-05-13 2.8 MB 187 downloads
maxima-5.6.tar.gz 2002-05-13 3.3 MB 1,054 downloads
maxima-5.5-beta3.tar.gz 2002-05-13 3.0 MB 205 downloads
maxima-5.5-beta.tar.gz 2002-05-13 3.1 MB 221 downloads
maxima-5.4.tar.gz 2002-05-13 2.8 MB 229 downloads
maxima-5.4-beta-2.tar.gz 2002-05-13 2.5 MB 186 downloads
maxima-5.2a-beta.tar.gz 2002-05-13 2.6 MB 175 downloads
maxima-5.2.tar.gz 2002-05-13 2.5 MB 225 downloads
maxima-5.1-beta.tar.gz 2002-05-13 2.7 MB 176 downloads
maxima-5.0.tar.gz 2002-05-13 2.5 MB 398 downloads

Table 6: Downloads of Versions of Maxima in 2002

NOTE: The data for these tables was acquired by selecting the tables displayed by the SourceForge web pages (follow the links in the table captions) with a mouse in Mozilla Firefox 3.6.13 on a Microsoft Windows XP Service Pack 2 PC, copying, and pasting the selection into the Notepad++ Version 5.2 text and code editor on Saturday, February 15, 2011. This procedure gives the cumulative downloads to date in the table in the pasted text. The text was then converted to an HTML table using the free open-source Kompozer HTML/web page editor. This same trick does not appear to work in the Safari web browser on the Macintosh; the pasted text does not include the total number of downloads. The number of downloads can be accessed by clicking on the graphic in the final column of the web page table.

Contributors

Unlike many free open-source projects, Maxima does not have a prominent list of contributors on the web site or in the source code other than frequent mention of William Schelter. As will be discussed futher below, there has been extensive work on Maxima since 2001. A partial list of contributors was collected by using the DOS FIND command to search the files in Maxima for Copyright notices. For example:

C:\Documents and Settings\John F. McGowan\Desktop\maxima-5.23.2\share\vector>find "Copyright" *
---------- RTEST_VECT.MAC
---------- VECT.DEM
---------- VECT.MAC
---------- VECT.USG
---------- VECTOR.DEM
---------- VECTOR.MAC
---------- VECTOR.USG
---------- VECTOR_REBUILD.LISP
;; Copyright (C)  Nov. 2008  Volker van Nek
---------- VECTOR_REBUILD.MAC
  Copyright (C)  Nov. 2008  Volker van Nek
---------- VECTOR_REBUILD.USG
Copyright (C)  Nov. 2008  Volker van Nek (van dot nek at arcor dot de)
---------- VECT_TRANSFORM.MAC

The following contributors were listed in copyright notices in files in the src folder of Maxima 5.23.2

Copyright Holders Listed in *.lisp files in src folder (not numeric subfolder which appears to contain the slatec numerical library)

"MIT"

William Schelter

J. Villate  (Jaime E. Villate)  https://villate.org/

Barton Willis                 https://www.unk.edu/facultyandstaff.aspx?id=669

Paul Foley

Andrej Vodopivec

Volker van Nek

Kevin M. Rosenberg

Dieter Kaiser
 Raymond Toy

James F. Amundson (Maxima project leader for several years)

David Billinghurst

The share folder contains much more of the source code for Maxima. The following additional contributors were identified from the files in the share folder: A number of the contributors listed above also contributed to files in the share folder.

share/tensor

Viktor T. Toth

Valerij Pipin

share/simplification

Wolfgang Jenkner

share/numeric

Mario Rodriguez Riotorto

share/libfgs

Robert Dodier

share/draw

Mark H. Weaver

share/contrib

Edmond Orignac

Martin Rubey

Thomas Baruchel

Dan Stanger

Salvador Bosch Perez

This is not an exhaustive list of copyright holders (presumably contributors). Maxima is quite large and, for example, the share/contrib folder contains many sub-folders that were not searched due to time constraints.

This is twenty-two (22) individuals including William Schelter and not including whomever “MIT” may, in fact, refer to, presumably the original developers of MACSYMA. A substantial amount of work clearly took place before William Schelter became involved in the early 1980’s. Many, many files contain a copyright notice of the form:

;;;  Copyright (c) 1984,1987 by William Schelter,University of Texas   ;;;;;
;;;     (c) Copyright 1981 Massachusetts Institute of Technology         ;;;
 variously MIT copyrights are 1980, 1981, 1982

The Scope of the Maxima Project

Maxima is written largely in the LISP programming language, one of the oldest programming languages and a favorite of artificial intelligence research. There is some FORTRAN and a tiny amount of other languages (TCL, Bourne Shell, a few others). Maxima was expanded extensively between 2006 and 2008. More recent work has been in adding documentation.

Release Date Lines of Code Mythical Man Months Notional Cost
maxima 5.23.2 2011-01-17 467,915 1,527.17 $12,217,336.75
maxima 5.20.1 2009-12-14 453,151 1,476.61 $11,812,894.32
maxima 5.16.3 2008-08-24 404,486 1,310.57 $10,484,552.48
maxima 5.9.2 2006-01-30 233,394 735.71 $5,885,663.12
maxima 5.6 2002-05-13 138,037 423.84 $3,390,755.82
maxima 5.0 2002-05-13 114,453 348.15 $2,785,221.69

Table 7: Scope of Selected Releases of Maxima (from 2002 to Feb. 15, 2011) The number of lines of code were determined by using the free open-source CLOC (Count Lines of Code) utility run from a DOS batch file:

cloc --exclude-lang=HTML --force-lang="Lisp",lisp  --force-lang="Lisp",mac --force-lang="Lisp",dem -csv maxima-5.23.2 > maxima-5.23.2.csv
cloc --exclude-lang=HTML --force-lang="Lisp",lisp  --force-lang="Lisp",mac --force-lang="Lisp",dem -csv maxima-5.20.1 > maxima-5.20.1.csv
cloc --exclude-lang=HTML --force-lang="Lisp",lisp  --force-lang="Lisp",mac --force-lang="Lisp",dem -csv maxima-5.16.3 > maxima-5.16.3.csv
cloc --exclude-lang=HTML --force-lang="Lisp",lisp  --force-lang="Lisp",mac --force-lang="Lisp",dem -csv maxima-5.9.2 > maxima-5.9.2.csv
cloc --exclude-lang=HTML --force-lang="Lisp",lisp  --force-lang="Lisp",mac --force-lang="Lisp",dem -csv maxima-5.6 > maxima-5.6.csv
cloc --exclude-lang=HTML --force-lang="Lisp",lisp  --force-lang="Lisp",mac --force-lang="Lisp",dem -csv maxima-5.0 > maxima-5.0.csv

Maxima is written in the LISP programming language. By default, CLOC expects LISP files to have the extension lsp. The LISP files in the maxima source have the extensions lisp, mac, and dem. The HTML documentation is excluded from the count of the lines of code. The number of man-months, the actual effort that may have been expended is estimated using the “organic” version of the Basic Constructive Cost Model (COCOMO) from Barry Boehm’s Software Engineering Economics. This is a very rough estimate and should not be taken too seriously; the goal is to get a ball park estimate of the size of the project. The estimated man-months and notional cost are cumulative numbers since the start of the Maxima/MACSYMA project in the 1960’s. Maxima includes at least one third party library in source code form, the slatec numerical FORTRAN library, which is also therefore included in the estimate.

The comma separated values (CSV) files of results generated by the cloc utility were analyzed using an Octave script:. Octave is a free open-source numerical programming tool that is mostly compatible with MATLAB.

% analyze maxima lines of code data
%
max5p23p2 = csvread('maxima-5.23.2.csv');
max5p20p1 = csvread('maxima-5.20.1.csv');
max5p16p3 = csvread('maxima-5.16.3.csv');
max5p9p2 = csvread('maxima-5.9.2.csv');
max5p6 = csvread('maxima-5.6.csv');
max5p0 = csvread('maxima-5.0.csv');
index = 5;
sum5p23p2 = sum(max5p23p2(index:end, 5));
sum5p20p1 = sum(max5p20p1(index:end, 5));
sum5p16p3 = sum(max5p16p3(index:end, 5));
sum5p9p2 = sum(max5p9p2(index:end, 5));
sum5p6 = sum(max5p6(index:end, 5));
sum5p0 = sum(max5p0(index:end, 5));
% generate table of results
printf("Release\tLines of Code\tMythical Man Months\tNotional Cost\n");
fflush(stdout);
[man_months, people, time, cost] = cocomo(sum5p23p2/1000.0);
printf("maxima 5.23.2\t%d\t%6.2f\t% 9.2f\n", sum5p23p2, man_months, cost);
fflush(stdout);
[man_months, people, time, cost] = cocomo(sum5p20p1/1000.0);
printf("maxima 5.20.1\t%d\t%6.2f\t% 9.2f\n", sum5p20p1, man_months, cost);
fflush(stdout);
[man_months, people, time, cost] = cocomo(sum5p16p3/1000.0);
printf("maxima 5.16.3\t%d\t%6.2f\t% 9.2f\n", sum5p16p3, man_months, cost);
fflush(stdout);
[man_months, people, time, cost] = cocomo(sum5p9p2/1000.0);
printf("maxima 5.9.2\t%d\t%6.2f\t% 9.2f\n", sum5p9p2, man_months, cost);
fflush(stdout);
[man_months, people, time, cost] = cocomo(sum5p6/1000.0);
printf("maxima 5.6\t%d\t%6.2f\t% 9.2f\n", sum5p6, man_months, cost);
fflush(stdout);
[man_months, people, time, cost] = cocomo(sum5p0/1000.0);
printf("maxima 5.0\t%d\t%6.2f\t% 9.2f\n", sum5p0, man_months, cost);
fflush(stdout);
disp('ALL DONE');

which calls an Octave function cocomo.m that implements the Basic COCOMO model and estimates the cost by assuming an hourly rate of $50 per hour and that a man-month is 160 hours: This is an updated version of the cocomo function introduced in the first article in this series.

function [man_months, dev_time, people_required, cost] = cocomo(kloc, type, hourly_rate)
% [man_months, dev_time, people_required, cost] = cocomo(kloc [, type, hourly_rate])
%
% kloc (thousands of lines of code)
% type (type of project: organic, semi-detached, embedded)
% hourly_rate  (rates in USD per hour used to calculate project cost)
%
% Implements Basic COCOMO (Constructive Cost Model), also known as COCOMO 81, from
% Software Engineering Economics by Barry Boehm
%
if nargin < 2
    type = 'organic';
end
if nargin < 3
    hourly_rate = 50.0;  % $50/hour
end
c = 2.5;
if strcmp(type, 'organic')
    a = 2.4;
    b = 1.05;
    d = 0.38;
end
if strcmp(type, 'semi')  % semi detached
    a = 3.0;
    b = 1.12;
    d = 0.35;
end
if strcmp(type, 'embedded')
    a = 3.6;
    b = 1.2;
    d = 0.32;
end
man_months = a*(kloc)^b;
dev_time = c*(man_months)^d;
people_required = man_months / dev_time;
cost = man_months * 160 * hourly_rate;
end

The output of the maxima_anal.m Octave script was pasted into this article using the Kompozer HTML editor. Kompozer has a feature to convert text tables to HTML tables. The “Date” column was then added manually using the table editing features of Kompozer.

Conclusion

Maxima is clearly a substantial project, covering a calendar period from the 1960’s to the present. It probably incorporated both algorithm research and development as well as the implementation of known algorithms, especially during the 1960’s when it was one of the first computer algebra systems, a subject of intense research at the time.

There are many pressing problems ranging from speech recognition for mobile and other devices to cancer to energy shortages that may fall to mathematical research and development and mathematical programming combined with the enormous power of modern computers. As can be seen from Maxima, the dollar cost of such projects is not especially large. The guesstimated $12 million cost of Maxima is quite small compared to many publicly and privately funded activities. However, the calendar time of such projects is substantial, in this case over forty years. Very few mathematical programming projects can be completed in a calendar quarter (a few can). Generally, such projects take between six months and several years. Successful genuine research projects typically take years; Maxima/MACSYMA is an example, being a rare example of a successful artificial intelligence research and development project. Successful mathematical programming projects are much more likely with realistic targets and plans based on historical experience and data.

References/Suggested Reading

Software Engineering Economics
Barry W. Boehm
Prentice Hall (November 1, 1981)

Software Estimation: Demystifying the Black Art
Steve McConnell
Microsoft Press; 1 edition (March 1, 2006)

© 2011 John F. McGowan

About the Author

John F. McGowan, Ph.D. is a software developer, research scientist, and consultant. He works primarily in the area of complex algorithms that embody advanced mathematical and logical concepts, including speech recognition and video compression technologies. He has extensive experience developing software in C, C++, Visual Basic, Mathematica, MATLAB, and many other programming languages. He is probably best known for his AVI Overview, an Internet FAQ (Frequently Asked Questions) on the Microsoft AVI (Audio Video Interleave) file format. He has worked as a contractor at NASA Ames Research Center involved in the research and development of image and video processing algorithms and technology. He has published articles on the origin and evolution of life, the exploration of Mars (anticipating the discovery of methane on Mars), and cheap access to space. He has a Ph.D. in physics from the University of Illinois at Urbana-Champaign and a B.S. in physics from the California Institute of Technology (Caltech). He can be reached at [email protected].

Sponsor’s message: Math Better Explained is an insightful ebook and screencast series that will help you deeply understand fundamental mathematical concepts, and see math in a new light. Get it here.

2 Comments

  1. Basil February 22, 2011
    • Antonio Cangiano February 22, 2011

Leave a Reply