The 30 Year Horizon Manuel Bronstein William Burge Timothy Daly James Davenport Michael Dewar Martin Dunstan Albrecht Fortenbacher Patrizia Gianni Johannes Grabmeier Jocelyn Guidry Richard Jenks Larry Lambe Michael Monagan Scott Morrison William Sit Jonathan Steinbach Robert Sutor Barry Trager Stephen Watt Jim Wen Clifton Williamson Volume 2: Axiom Users Guide i Portions Copyright (c) 2005 Timothy Daly The Blue Bayou image Copyright (c) 2004 Jocelyn Guidry Portions Copyright (c) 2004 Martin Dunstan Portions Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd. All rights reserved. This book and the Axiom software is licensed as follows: Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: - Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. - Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. - Neither the name of The Numerical ALgorithms Group Ltd. nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. Inclusionofnamesinthelistofcreditsisbasedonhistoricalinformationandisasaccurate as possible. Inclusion of names does not in any way imply an endorsement but represents historical influence on Axiom development. ii Cyril Alberga Roy Adler Richard Anderson George Andrews Henry Baker Stephen Balzac Yurij Baransky David R. Barton Gerald Baumgartner Gilbert Baumslag Fred Blair Vladimir Bondarenko Mark Botch Alexandre Bouyer Peter A. Broadbery Martin Brock Manuel Bronstein Florian Bundschuh William Burge Quentin Carpent Bob Caviness Bruce Char Cheekai Chin David V. Chudnovsky Gregory V. Chudnovsky Josh Cohen Christophe Conil Don Coppersmith George Corliss Robert Corless Gary Cornell Meino Cramer Claire Di Crescenzo Timothy Daly Sr. Timothy Daly Jr. James H. Davenport Jean Della Dora Gabriel Dos Reis Michael Dewar Claire DiCrescendo Sam Dooley Lionel Ducos Martin Dunstan Brian Dupee Dominique Duval Robert Edwards Heow Eide-Goodman Lars Erickson Richard Fateman Bertfried Fauser Stuart Feldman Brian Ford Albrecht Fortenbacher George Frances Constantine Frangos Timothy Freeman Korrinn Fu Marc Gaetano Rudiger Gebauer Kathy Gerber Patricia Gianni Holger Gollan Teresa Gomez-Diaz Laureano Gonzalez-Vega Stephen Gortler Johannes Grabmeier Matt Grayson James Griesmer Vladimir Grinberg Oswald Gschnitzer Jocelyn Guidry Steve Hague Vilya Harvey Satoshi Hamaguchi Martin Hassner Ralf Hemmecke Henderson Antoine Hersen Pietro Iglio Richard Jenks Kai Kaminski Grant Keady Tony Kennedy Paul Kosinski Klaus Kusche Bernhard Kutzler Larry Lambe Frederic Lehobey Michel Levaud Howard Levy Rudiger Loos Michael Lucks Richard Luczak Camm Maguire Bob McElrath Michael McGettrick Ian Meikle David Mentre Victor S. Miller Gerard Milmeister Mohammed Mobarak H. Michael Moeller Michael Monagan Marc Moreno-Maza Scott Morrison Mark Murray William Naylor C. Andrew Neff John Nelder Godfrey Nolan Arthur Norman Jinzhong Niu Michael O’Connor Kostas Oikonomou Julian A. Padget Bill Page Jaap Weel Susan Pelzel Michel Petitot Didier Pinchon Claude Quitte Norman Ramsey Michael Richardson Renaud Rioboo Jean Rivlin Nicolas Robidoux Simon Robinson Michael Rothstein Martin Rubey Philip Santas Alfred Scheerhorn William Schelter Gerhard Schneider Martin Schoenert Marshall Schor Fritz Schwarz Nick Simicich William Sit Elena Smirnova Jonathan Steinbach Christine Sundaresan Robert Sutor Moss E. Sweedler Eugene Surowitz James Thatcher Baldir Thomas Mike Thomas Dylan Thurston Barry Trager Themos T. Tsikas Gregory Vanuxem Bernhard Wall Stephen Watt Juergen Weiss M. Weller Mark Wegman James Wen Thorsten Werther Michael Wester John M. Wiley Berhard Will Clifton J. Williamson Stephen Wilson Shmuel Winograd Robert Wisbauer Sandra Wityak Waldemar Wiwianka Knut Wolf Clifford Yapp David Yun Richard Zippel Evelyn Zoernack Bruno Zuercher Dan Zwillinger Contents 0.1 Makefile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 Writing Spad Code 3 1.1 The Description: label and the )describe command . . . . . . . . . . . . . . . 3 iii iv CONTENTS New Foreword On October 1, 2001 Axiom was withdrawn from the market and ended life as a commer- cial product. On September 3, 2002 Axiom was released under the Modified BSD license, including this document. On August 27, 2003 Axiom was released as free and open source software available for download from the Free Software Foundation’s website, Savannah. Work on Axiom has had the generous support of the Center for Algorithms and Interactive Scientific Computation (CAISS) at City College of New York. Special thanks go to Dr. Gilbert Baumslag for his support of the long term goal. The online version of this documentation is roughly 1000 pages. In order to make printed versions we’ve broken it up into three volumes. The first volume is tutorial in nature. The secondvolumeisforprogrammers. Thethirdvolumeisreferencematerial. We’vealsoadded a fourth volume for developers. All of these changes represent an experiment in print-on- demand delivery of documentation. Time will tell whether the experiment succeeded. Axiom has been in existence for over thirty years. It is estimated to contain about three hundred man-years of research and has, as of September 3, 2003, 143 people listed in the credits. AllofthesepeoplehavecontributeddirectlyorindirectlytomakingAxiomavailable. Axiom is being passed to the next generation. I’m looking forward to future milestones. With that in mind I’ve introduced the theme of the “30 year horizon”. We must invent the tools that support the Computational Mathematician working 30 years from now. How will research be done when every bit of mathematical knowledge is online and instantly available? What happens when we scale Axiom by a factor of 100, giving us 1.1 million domains? How can we integrate theory with code? How will we integrate theorems and proofs of the mathematics with space-time complexity proofs and running code? What visualization tools are needed? How do we support the conceptual structures and semantics of mathematics in effective ways? How do we support results from the sciences? How do we teach the next generation to be effective Computational Mathematicians? The “30 year horizon” is much nearer than it appears. Tim Daly CAISS, City College of New York November 10, 2003 ((iHy)) 0.1. MAKEFILE 1 0.1 Makefile This book is actually a literate program[2] and can contain executable source code. In particular,theMakefileforthisbookispartofthesourceofthebookandisincludedbelow. Axiom uses the “noweb” literate programming system by Norman Ramsey[6]. 2 CONTENTS Chapter 1 Writing Spad Code 1.1 The Description: label and the )describe command The describe command will print out the comments associated with Axiom source code ele- ments. Forthecategory,domain,andpackagesectionsthetextistakenfromtheDescription: keyword. This information is stored in a database and can be queried with )lisp (getdatabase ’|Integer| ’documentation) fortheIntegerdomain. However,thisinformationhasotherusesinthesystemsoitcontains tags and control information. Most tags are removed by the describe function since the output is intended to be displayed in ASCII on the terminal. The Description: keyword is in the comment block just after the abbreviation command. It isfreeformandtheparagraphwillbereflowedautomaticallytoallowforabout60characters per line, adjusted for spaces. The Description: section should be written after the keyword in the “++” comments as in: )abbrev package D03AGNT d03AgentsPackage ++ Description: ++ This package does some interesting stuff. We can write multiple ++ lines but they should all line up with the first character of ++ the Description keyword. Special \spad{terms} will be removed. ++ ++ The above line will force a newline. So will ending a line with \br ++ \tab{5}This will allow primitive formatting\br ++ \tab{5}So you can align text\br ++ \tab{10}Start in column 11\tab{5}and skip 5 spaces\br ++ \tab{10}End in column 11\tab{7}and count out the needed spaces\br ++ \tab{5} note that the last line will not need the br command 3 4 CHAPTER 1. WRITING SPAD CODE As the comment says, the Description should all be aligned under the “D” in Description. You can indent using \tab{n} which will insert n spaces. You can force a newline in two ways. Either include a blank line (with the “++” comments) or use the \br keyword. Due to lousy parsing algorithms for comments there are various ways this can all go wrong. There should not be any macros between the Description: section and the beginning of the definition. This is wrong. It will cause the )describe package d03AgentsPackage togivethewrongoutputbecauseitdoesnotfindtheendofthedescriptionsectionproperly. )abbrev package D03AGNT d03AgentsPackage ++ Description: ++ This description does not work LEDF ==> List Expression DoubleFloat d03AgentsPackage(): E == I where In the Description: section the \tab{nn} function will be transformed into nn spaces. If you end each line with a \br you can control alignment. ++ Description: ++ This is an example of a table alignment\br ++ \tab{5}First Item\tab{5} This will line up with the following line\br ++ \tab{5}Second Item\tab{4} This will line up with the following line\br ++ \tab{5}Third Item\tab{5} This will line up with the following line If the main body of the category, domain, or package begins with properties rather than functions the Description will be incorrectly recorded. This is a known bug finding the end of the Description section. For instance, this ++ Description: ++ The category of Lie Algebras. ++ It is used by the domains of non-commutative algebra, ++ LiePolynomial and XPBWPolynomial. LieAlgebra(R: CommutativeRing): Category == Module(R) with NullSquare ++ \axiom{NullSquare} means that \axiom{[x,x] = 0} holds. JacobiIdentity ++ \axiom{JacobiIdentity} means that ++ \axiom{[x,[y,z]]+[y,[z,x]]+[z,[x,y]] = 0} holds. construct: ($,$) -> $ ++ \axiom{construct(x,y)} returns the Lie bracket of \axiom{x} ++ and \axiom{y}. will give the output 1.1. THE DESCRIPTION: LABEL AND THE )DESCRIBE COMMAND 5 {JacobiIdentity} means that} [x,[y,z]]+[y,[z,x]]+[z,[x,y]] = 0 holds. but reordering it to read: ++ Description: ++ The category of Lie Algebras. ++ It is used by the domains of non-commutative algebra, ++ LiePolynomial and XPBWPolynomial. LieAlgebra(R: CommutativeRing): Category == Module(R) with construct: ($,$) -> $ ++ \axiom{construct(x,y)} returns the Lie bracket of \axiom{x} ++ and \axiom{y}. NullSquare ++ \axiom{NullSquare} means that \axiom{[x,x] = 0} holds. JacobiIdentity ++ \axiom{JacobiIdentity} means that ++ \axiom{[x,[y,z]]+[y,[z,x]]+[z,[x,y]] = 0} holds. will give the output The category of Lie Algebras. It is used by the domains of non-commutative algebra, LiePolynomial and XPBWPolynomial. which is correct. h*i≡ PROJECT=bookvol2 TANGLE=/usr/local/bin/NOTANGLE WEAVE=/usr/local/bin/NOWEAVE LATEX=/usr/bin/latex MAKEINDEX=/usr/bin/makeindex all: ${WEAVE} -t8 -delay ${PROJECT}.pamphlet >${PROJECT}.tex ${LATEX} ${PROJECT}.tex 2>/dev/null 1>/dev/null ${MAKEINDEX} ${PROJECT}.idx ${LATEX} ${PROJECT}.tex 2>/dev/null 1>/dev/null