\documentclass{article} \usepackage{axiom} \begin{document} \title{\$SPAD/src/algebra vector.spad} \author{The Axiom Team} \maketitle \begin{abstract} \end{abstract} \eject \tableofcontents \eject \section{category VECTCAT VectorCategory} <>= )abbrev category VECTCAT VectorCategory ++ Author: ++ Date Created: ++ Date Last Updated: ++ Basic Functions: ++ Related Constructors: DirectProductCategory, Vector, IndexedVector ++ Also See: ++ AMS Classifications: ++ Keywords: ++ References: ++ Description: ++ \spadtype{VectorCategory} represents the type of vector like objects, ++ i.e. finite sequences indexed by some finite segment of the ++ integers. The operations available on vectors depend on the structure ++ of the underlying components. Many operations from the component domain ++ are defined for vectors componentwise. It can by assumed that extraction or ++ updating components can be done in constant time. VectorCategory(R:Type): Category == OneDimensionalArrayAggregate R with if R has AbelianSemiGroup then _+ : (%, %) -> % ++ x + y returns the component-wise sum of the vectors x and y. ++ Error: if x and y are not of the same length. if R has AbelianMonoid then zero: NonNegativeInteger -> % ++ zero(n) creates a zero vector of length n. if R has AbelianGroup then _- : % -> % ++ -x negates all components of the vector x. _- : (%, %) -> % ++ x - y returns the component-wise difference of the vectors x and y. ++ Error: if x and y are not of the same length. _* : (Integer, %) -> % ++ n * y multiplies each component of the vector y by the integer n. if R has Monoid then _* : (R, %) -> % ++ r * y multiplies the element r times each component of the vector y. _* : (%, R) -> % ++ y * r multiplies each component of the vector y by the element r. if R has Ring then dot: (%, %) -> R ++ dot(x,y) computes the inner product of the two vectors x and y. ++ Error: if x and y are not of the same length. outerProduct: (%, %) -> Matrix R ++ outerProduct(u,v) constructs the matrix whose (i,j)'th element is ++ u(i)*v(j). cross: (%, %) -> % ++ vectorProduct(u,v) constructs the cross product of u and v. ++ Error: if u and v are not of length 3. if R has RadicalCategory and R has Ring then length: % -> R ++ length(v) computes the sqrt(dot(v,v)), i.e. the magnitude magnitude: % -> R ++ magnitude(v) computes the sqrt(dot(v,v)), i.e. the length add if R has AbelianSemiGroup then u + v == (n := #u) ^= #v => error "Vectors must be of the same length" map(_+ , u, v) if R has AbelianMonoid then zero n == new(n, 0) if R has AbelianGroup then - u == map(- #1, u) n:Integer * u:% == map(n * #1, u) u - v == u + (-v) if R has Monoid then u:% * r:R == map(#1 * r, u) r:R * u:% == map(r * #1, u) if R has Ring then dot(u, v) == #u ^= #v => error "Vectors must be of the same length" _+/[qelt(u, i) * qelt(v, i) for i in minIndex u .. maxIndex u] outerProduct(u, v) == matrix [[qelt(u, i) * qelt(v,j) for i in minIndex u .. maxIndex u] _ for j in minIndex v .. maxIndex v] cross(u, v) == #u ^= 3 or #v ^= 3 => error "Vectors must be of length 3" construct [qelt(u, 2)*qelt(v, 3) - qelt(u, 3)*qelt(v, 2) , _ qelt(u, 3)*qelt(v, 1) - qelt(u, 1)*qelt(v, 3) , _ qelt(u, 1)*qelt(v, 2) - qelt(u, 2)*qelt(v, 1) ] if R has RadicalCategory and R has Ring then length p == sqrt(dot(p,p)) magnitude p == sqrt(dot(p,p)) @ \section{domain IVECTOR IndexedVector} <>= )abbrev domain IVECTOR IndexedVector ++ Author: ++ Date Created: ++ Date Last Updated: ++ Basic Functions: ++ Related Constructors: Vector, DirectProduct ++ Also See: ++ AMS Classifications: ++ Keywords: ++ References: ++ Description: ++ This type represents vector like objects with varying lengths ++ and a user-specified initial index. IndexedVector(R:Type, mn:Integer): VectorCategory R == IndexedOneDimensionalArray(R, mn) @ \section{domain VECTOR Vector} <>= )abbrev domain VECTOR Vector ++ Author: ++ Date Created: ++ Date Last Updated: ++ Basic Functions: ++ Related Constructors: IndexedVector, DirectProduct ++ Also See: ++ AMS Classifications: ++ Keywords: ++ References: ++ Description: ++ This type represents vector like objects with varying lengths ++ and indexed by a finite segment of integers starting at 1. Vector(R:Type): Exports == Implementation where VECTORMININDEX ==> 1 -- if you want to change this, be my guest Exports ==> VectorCategory R with vector: List R -> % ++ vector(l) converts the list l to a vector. Implementation ==> IndexedVector(R, VECTORMININDEX) add vector l == construct l if R has ConvertibleTo InputForm then convert(x:%):InputForm == convert [convert("vector"::Symbol)@InputForm, convert(parts x)@InputForm] @ \section{VECTOR.lsp BOOTSTRAP} {\bf VECTOR} depends on itself. We need to break this cycle to build the algebra. So we keep a cached copy of the translated {\bf VECTOR} category which we can write into the {\bf MID} directory. We compile the lisp code and copy the {\bf VECTOR.o} file to the {\bf OUT} directory. This is eventually forcibly replaced by a recompiled version. Note that this code is not included in the generated catdef.spad file. <>= (|/VERSIONCHECK| 2) (DEFUN |VECTOR;vector;L$;1| (|l| |$|) (SPADCALL |l| (QREFELT |$| 8))) (DEFUN |VECTOR;convert;$If;2| (|x| |$|) (SPADCALL (LIST (SPADCALL (SPADCALL "vector" (QREFELT |$| 12)) (QREFELT |$| 14)) (SPADCALL (SPADCALL |x| (QREFELT |$| 15)) (QREFELT |$| 16))) (QREFELT |$| 18))) (DEFUN |Vector| (#1=#:G84134) (PROG NIL (RETURN (PROG (#2=#:G84135) (RETURN (COND ((LETT #2# (|lassocShiftWithFunction| (LIST (|devaluate| #1#)) (HGET |$ConstructorCache| (QUOTE |Vector|)) (QUOTE |domainEqualList|)) |Vector|) (|CDRwithIncrement| #2#)) ((QUOTE T) (|UNWIND-PROTECT| (PROG1 (|Vector;| #1#) (LETT #2# T |Vector|)) (COND ((NOT #2#) (HREM |$ConstructorCache| (QUOTE |Vector|)))))))))))) (DEFUN |Vector;| (|#1|) (PROG (|DV$1| |dv$| |$| #1=#:G84133 |pv$|) (RETURN (PROGN (LETT |DV$1| (|devaluate| |#1|) . #2=(|Vector|)) (LETT |dv$| (LIST (QUOTE |Vector|) |DV$1|) . #2#) (LETT |$| (GETREFV 36) . #2#) (QSETREFV |$| 0 |dv$|) (QSETREFV |$| 3 (LETT |pv$| (|buildPredVector| 0 0 (LIST (|HasCategory| |#1| (QUOTE (|SetCategory|))) (|HasCategory| |#1| (QUOTE (|ConvertibleTo| (|InputForm|)))) (LETT #1# (|HasCategory| |#1| (QUOTE (|OrderedSet|))) . #2#) (OR #1# (|HasCategory| |#1| (QUOTE (|SetCategory|)))) (|HasCategory| (|Integer|) (QUOTE (|OrderedSet|))) (|HasCategory| |#1| (QUOTE (|AbelianSemiGroup|))) (|HasCategory| |#1| (QUOTE (|AbelianMonoid|))) (|HasCategory| |#1| (QUOTE (|AbelianGroup|))) (|HasCategory| |#1| (QUOTE (|Monoid|))) (|HasCategory| |#1| (QUOTE (|Ring|))) (AND (|HasCategory| |#1| (QUOTE (|RadicalCategory|))) (|HasCategory| |#1| (QUOTE (|Ring|)))) (AND (|HasCategory| |#1| (LIST (QUOTE |Evalable|) (|devaluate| |#1|))) (|HasCategory| |#1| (QUOTE (|SetCategory|)))) (OR (AND (|HasCategory| |#1| (LIST (QUOTE |Evalable|) (|devaluate| |#1|))) #1#) (AND (|HasCategory| |#1| (LIST (QUOTE |Evalable|) (|devaluate| |#1|))) (|HasCategory| |#1| (QUOTE (|SetCategory|))))))) . #2#)) (|haddProp| |$ConstructorCache| (QUOTE |Vector|) (LIST |DV$1|) (CONS 1 |$|)) (|stuffDomainSlots| |$|) (QSETREFV |$| 6 |#1|) (COND ((|testBitVector| |pv$| 2) (QSETREFV |$| 19 (CONS (|dispatchFunction| |VECTOR;convert;$If;2|) |$|)))) |$|)))) (MAKEPROP (QUOTE |Vector|) (QUOTE |infovec|) (LIST (QUOTE #(NIL NIL NIL NIL NIL (|IndexedVector| 6 (NRTEVAL 1)) (|local| |#1|) (|List| 6) (0 . |construct|) |VECTOR;vector;L$;1| (|String|) (|Symbol|) (5 . |coerce|) (|InputForm|) (10 . |convert|) (15 . |parts|) (20 . |convert|) (|List| |$|) (25 . |convert|) (30 . |convert|) (|Mapping| 6 6 6) (|Boolean|) (|NonNegativeInteger|) (|List| 24) (|Equation| 6) (|Integer|) (|Mapping| 21 6) (|Mapping| 21 6 6) (|UniversalSegment| 25) (|Void|) (|Mapping| 6 6) (|Matrix| 6) (|OutputForm|) (|SingleInteger|) (|Union| 6 (QUOTE "failed")) (|List| 25))) (QUOTE #(|vector| 35 |parts| 40 |convert| 45 |construct| 50)) (QUOTE ((|shallowlyMutable| . 0) (|finiteAggregate| . 0))) (CONS (|makeByteWordVec2| 13 (QUOTE (0 0 0 0 0 0 0 3 0 0 13 4 0 0 13 1 2 4))) (CONS (QUOTE #(|VectorCategory&| |OneDimensionalArrayAggregate&| |FiniteLinearAggregate&| |LinearAggregate&| |IndexedAggregate&| |Collection&| |HomogeneousAggregate&| |OrderedSet&| |Aggregate&| |EltableAggregate&| |Evalable&| |SetCategory&| NIL NIL |InnerEvalable&| NIL NIL |BasicType&|)) (CONS (QUOTE #((|VectorCategory| 6) (|OneDimensionalArrayAggregate| 6) (|FiniteLinearAggregate| 6) (|LinearAggregate| 6) (|IndexedAggregate| 25 6) (|Collection| 6) (|HomogeneousAggregate| 6) (|OrderedSet|) (|Aggregate|) (|EltableAggregate| 25 6) (|Evalable| 6) (|SetCategory|) (|Type|) (|Eltable| 25 6) (|InnerEvalable| 6 6) (|CoercibleTo| 32) (|ConvertibleTo| 13) (|BasicType|))) (|makeByteWordVec2| 19 (QUOTE (1 0 0 7 8 1 11 0 10 12 1 13 0 11 14 1 0 7 0 15 1 7 13 0 16 1 13 0 17 18 1 0 13 0 19 1 0 0 7 9 1 0 7 0 15 1 2 13 0 19 1 0 0 7 8)))))) (QUOTE |lookupIncomplete|))) @ \section{package VECTOR2 VectorFunctions2} <>= )abbrev package VECTOR2 VectorFunctions2 ++ Author: ++ Date Created: ++ Date Last Updated: ++ Basic Functions: ++ Related Constructors: ++ Also See: ++ AMS Classifications: ++ Keywords: ++ References: ++ Description: ++ This package provides operations which all take as arguments ++ vectors of elements of some type \spad{A} and functions from \spad{A} to ++ another of type B. The operations all iterate over their vector argument ++ and either return a value of type B or a vector over B. VectorFunctions2(A, B): Exports == Implementation where A, B: Type VA ==> Vector A VB ==> Vector B O2 ==> FiniteLinearAggregateFunctions2(A, VA, B, VB) UB ==> Union(B,"failed") Exports ==> with scan : ((A, B) -> B, VA, B) -> VB ++ scan(func,vec,ident) creates a new vector whose elements are ++ the result of applying reduce to the binary function func, ++ increasing initial subsequences of the vector vec, ++ and the element ident. reduce : ((A, B) -> B, VA, B) -> B ++ reduce(func,vec,ident) combines the elements in vec using the ++ binary function func. Argument ident is returned if vec is empty. map : (A -> B, VA) -> VB ++ map(f, v) applies the function f to every element of the vector v ++ producing a new vector containing the values. map : (A -> UB, VA) -> Union(VB,"failed") ++ map(f, v) applies the function f to every element of the vector v ++ producing a new vector containing the values or \spad{"failed"}. Implementation ==> add scan(f, v, b) == scan(f, v, b)$O2 reduce(f, v, b) == reduce(f, v, b)$O2 map(f:(A->B), v:VA):VB == map(f, v)$O2 map(f:(A -> UB), a:VA):Union(VB,"failed") == res : List B := [] for u in entries(a) repeat r := f u r = "failed" => return "failed" res := [r::B,:res] vector reverse! res @ \section{category DIRPCAT DirectProductCategory} <>= )abbrev category DIRPCAT DirectProductCategory -- all direct product category domains must be compiled -- without subsumption, set SourceLevelSubset to EQUAL --)bo $noSubsumption := true --% DirectProductCategory ++ Author: ++ Date Created: ++ Date Last Updated: ++ Basic Functions: ++ Related Constructors: DirectProduct ++ Also See: VectorCategory ++ AMS Classifications: ++ Keywords: ++ References: ++ Description: ++ This category represents a finite cartesian product of a given type. ++ Many categorical properties are preserved under this construction. DirectProductCategory(dim:NonNegativeInteger, R:Type): Category == Join(IndexedAggregate(Integer, R), CoercibleTo Vector R) with finiteAggregate ++ attribute to indicate an aggregate of finite size directProduct: Vector R -> % ++ directProduct(v) converts the vector v to become ++ a direct product. Error: if the length of v is ++ different from dim. if R has SetCategory then FullyRetractableTo R if R has Ring then BiModule(R, R) DifferentialExtension R FullyLinearlyExplicitRingOver R unitVector: PositiveInteger -> % ++ unitVector(n) produces a vector with 1 in position n and ++ zero elsewhere. dot: (%, %) -> R ++ dot(x,y) computes the inner product of the vectors x and y. if R has AbelianSemiGroup then AbelianSemiGroup if R has CancellationAbelianMonoid then CancellationAbelianMonoid if R has Monoid then _* : (R, %) -> % ++ r * y multiplies the element r times each component of the ++ vector y. _* : (%, R) -> % ++ y * r multiplies each component of the vector y by the element r. if R has Finite then Finite if R has CommutativeRing then Algebra R CommutativeRing if R has unitsKnown then unitsKnown if R has OrderedRing then OrderedRing if R has OrderedAbelianMonoidSup then OrderedAbelianMonoidSup if R has Field then VectorSpace R add if R has Ring then equation2R: Vector % -> Matrix R coerce(n:Integer):% == n::R::% characteristic() == characteristic()$R differentiate(z:%, d:R -> R) == map(d, z) equation2R v == ans:Matrix(R) := new(dim, #v, 0) for i in minRowIndex ans .. maxRowIndex ans repeat for j in minColIndex ans .. maxColIndex ans repeat qsetelt_!(ans, i, j, qelt(qelt(v, j), i)) ans reducedSystem(m:Matrix %):Matrix(R) == empty? m => new(0, 0, 0) reduce(vertConcat, [equation2R row(m, i) for i in minRowIndex m .. maxRowIndex m])$List(Matrix R) reducedSystem(m:Matrix %, v:Vector %): Record(mat:Matrix R, vec:Vector R) == vh:Vector(R) := empty? v => empty() rh := reducedSystem(v::Matrix %)@Matrix(R) column(rh, minColIndex rh) [reducedSystem(m)@Matrix(R), vh] if R has Finite then size == size$R ** dim if R has Field then x / b == x * inv b dimension() == dim::CardinalNumber @ \section{domain DIRPROD DirectProduct} <>= )abbrev domain DIRPROD DirectProduct ++ Author: ++ Date Created: ++ Date Last Updated: ++ Basic Functions: ++ Related Constructors: Vector, IndexedVector ++ Also See: OrderedDirectProduct ++ AMS Classifications: ++ Keywords: ++ References: ++ Description: ++ This type represents the finite direct or cartesian product of an ++ underlying component type. This contrasts with simple vectors in that ++ the members can be viewed as having constant length. Thus many ++ categorical properties can by lifted from the underlying component type. ++ Component extraction operations are provided but no updating operations. ++ Thus new direct product elements can either be created by converting ++ vector elements using the \spadfun{directProduct} function ++ or by taking appropriate linear combinations of basis vectors provided ++ by the \spad{unitVector} operation. DirectProduct(dim:NonNegativeInteger, R:Type): DirectProductCategory(dim, R) == Vector R add Rep := Vector R coerce(z:%):Vector(R) == copy(z)$Rep pretend Vector(R) coerce(r:R):% == new(dim, r)$Rep parts x == VEC2LIST(x)$Lisp directProduct z == size?(z, dim) => copy(z)$Rep error "Not of the correct length" if R has SetCategory then same?: % -> Boolean same? z == every?(#1 = z(minIndex z), z) x = y == _and/[qelt(x,i)$Rep = qelt(y,i)$Rep for i in 1..dim] retract(z:%):R == same? z => z(minIndex z) error "Not retractable" retractIfCan(z:%):Union(R, "failed") == same? z => z(minIndex z) "failed" if R has AbelianSemiGroup then u:% + v:% == map(_+ , u, v)$Rep if R has AbelianMonoid then 0 == zero(dim)$Vector(R) pretend % if R has Monoid then 1 == new(dim, 1)$Vector(R) pretend % u:% * r:R == map(#1 * r, u) r:R * u:% == map(r * #1, u) if R has CancellationAbelianMonoid then subtractIfCan(u:%, v:%):Union(%,"failed") == w := new(dim,0)$Vector(R) for i in 1..dim repeat (c := subtractIfCan(qelt(u, i)$Rep, qelt(v,i)$Rep)) case "failed" => return "failed" qsetelt_!(w, i, c::R)$Rep w pretend % if R has Ring then u:% * v:% == map(_* , u, v)$Rep recip z == w := new(dim,0)$Vector(R) for i in minIndex w .. maxIndex w repeat (u := recip qelt(z, i)) case "failed" => return "failed" qsetelt_!(w, i, u::R) w pretend % unitVector i == v:= new(dim,0)$Vector(R) v.i := 1 v pretend % if R has OrderedSet then x < y == for i in 1..dim repeat qelt(x,i) < qelt(y,i) => return true qelt(x,i) > qelt(y,i) => return false false if R has OrderedAbelianMonoidSup then sup(x, y) == map(sup, x, y) --)bo $noSubsumption := false @ \section{package DIRPROD2 DirectProductFunctions2} <>= )abbrev package DIRPROD2 DirectProductFunctions2 ++ Author: ++ Date Created: ++ Date Last Updated: ++ Basic Functions: ++ Related Constructors: ++ Also See: ++ AMS Classifications: ++ Keywords: ++ References: ++ Description: ++ This package provides operations which all take as arguments ++ direct products of elements of some type \spad{A} and functions from \spad{A} to another ++ type B. The operations all iterate over their vector argument ++ and either return a value of type B or a direct product over B. DirectProductFunctions2(dim, A, B): Exports == Implementation where dim : NonNegativeInteger A, B: Type DA ==> DirectProduct(dim, A) DB ==> DirectProduct(dim, B) VA ==> Vector A VB ==> Vector B O2 ==> FiniteLinearAggregateFunctions2(A, VA, B, VB) Exports ==> with scan : ((A, B) -> B, DA, B) -> DB ++ scan(func,vec,ident) creates a new vector whose elements are ++ the result of applying reduce to the binary function func, ++ increasing initial subsequences of the vector vec, ++ and the element ident. reduce : ((A, B) -> B, DA, B) -> B ++ reduce(func,vec,ident) combines the elements in vec using the ++ binary function func. Argument ident is returned if the vector is empty. map : (A -> B, DA) -> DB ++ map(f, v) applies the function f to every element of the vector v ++ producing a new vector containing the values. Implementation ==> add import FiniteLinearAggregateFunctions2(A, VA, B, VB) map(f, v) == directProduct map(f, v::VA) scan(f, v, b) == directProduct scan(f, v::VA, b) reduce(f, v, b) == reduce(f, v::VA, b) @ \section{License} <>= --Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd. --All rights reserved. -- --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. @ <<*>>= <> <> <> <> <> <> <> <> @ \eject \begin{thebibliography}{99} \bibitem{1} nothing \end{thebibliography} \end{document}