login  home  contents  what's new  discussion  bug reports     help  links  subscribe  changes  refresh  edit
FriCAS language
FriCASInterpreter  ← ↑ →  Rep and Per

ProgrammingSPAD
  
last edited 8 years ago by test1

Edit detail for ProgrammingSPAD revision 2 of 28
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
Editor: hemmecke
Time: 2014/02/14 01:07:38 GMT+0
Note: 
changed:
-       Examples are: '42', '3.14159265', '"abc"', '[3,5,11]'.
       Examples are: '42', '3.14159265', '"abc"', <code>[3,5,11]</code>.

changed:
-       '"abc"' is of type 'String', '[1,2,4,8]' is of type 'List(Integer)'.
       '"abc"' is of type 'String', <code>[1,2,4,8]</code> is of type 'List(Integer)'.

changed:
-
-
-
  - SPAD programs are usually definitions of categories and domains whose functionality will
    later be used in an interactive session or by other definitions.

  - While categories define the exports of domains, i.e. which function are provided,
    domains themselves implement the corresponding functions.

  - Domains form a type hierarchy where only inheritance from **one** other domain is allowed.
 
  - Categories form a type hierarchy with a multiple inheritance mechanism.

  - Categories and domains are often called constructors and (as shown above) can be parametrized.

  - SPAD has only very few built-in constructors. Most of the constructors are defined in a library.
    Builtin are 'Record', 'Tuple', 'Join', 'Mapping' (abbreviated via <code>-></code>).
    Library defined are 'Integer', 'List', 'String', 'Symbol', 'Monoid', 'Field', etc.


A running example

  Let us start with a little program.
  We try not to rely on any previously defined library, but we prefix every constructor with 'My'
  in order to avoid name conflicts with existing names.

  Our goal is to provide a domain 'MyFun' that is parametrized by a domain 'S' and represents functions
  from S into itself. We would like to be able to turn any function of type <code>S -> S</code>
  into an element of the 'MyFun(S)' domain. Furthermore, we want to turn this domain into a
  monoid 'MyMonoid'.

  First we define the category 'MyMonoid'.

changed:
-)abbrev domain MINI MinimalInitialNotIntegrated
-MinimalInitialNotIntegrated(x,F): Exports == Implementation where
-    x: Symbol
-    F: Field
-
-    INT ==> Integer
-    P ==> UnivariatePolynomial(x,F)
-    FRP ==> Fraction P
-    LFRP ==> List FRP
-
-    Exports == with
-      
-       degreeX: % -> INT
-
-    Implementation == add
-
-       Rep := LFRP
-
-       degreeX f ==
-          a := [denom i for i in f::Rep]@List(P)  --  denom : FRAC UP -> UP(x,F)
-          b := map(di +-> degree(di), a)$ListFunctions2(P, INT) -- degree : UP -> NonNegativeInteger
-          --b := [degree i for i in a ]
-          reduce( max, b ,0) :: INT
)abbrev category MYMON MyMonoid
MyMonoid: Category == with
    1: %
    _*: (%, %) -> %

added:
  Every constructor needs an ')abbrev' line where one specifies whether the constructore to come is
  a category or domain. Then follows a capitalized identifier of at most 7 characters and finally
  the identifier for the constructor.

  By convention, constructors begin with an uppercase letter and capitalize the first letter
  of each new word. Underscores are not commonly used.

\begin{spad}
rep x ==> (x@%) pretend Rep
per x ==> (x@Rep) pretend %

)abbrev category MYMON MyMonoid
XHashTable(Key : SetCategory, Entry : Type):
  Join(TableAggregate(Key, Entry), finiteAggregate, shallowlyMutable) with
    table : (Key -> SingleInteger) -> %
      ++ table(h) creates an empty hash table that uses h instead of
      ++ hash$Key. Note that h should be a mathematical function in
      ++ the sense that from k1=k2 follows h(k1)=h(k2). If that is not
      ++ the case, k1 and k2 will internally be considered as being
      ++ different keys.
 == add
    Marker ==> None
    toMarker mk ==> mk@Marker -- note that MKey==Marker==UMKE
    VACANT : Marker := (HASHTABLEVACANT$Lisp)  pretend Marker -- pos never used
    DELETED : Marker := (HASHTABLEDELETED$Lisp) pretend Marker -- pos is deleted
    vacant?(mk)  ==> EQ(toMarker mk, VACANT)$Lisp
    deleted?(mk) ==> EQ(toMarker mk, DELETED)$Lisp
    key?(mk) ==> not (vacant? mk or deleted? mk)
    MKey ==> None
    UMKE ==> None
    Buckets ==> PrimitiveArray UMKE
    numOfBuckets(a) ==> shift(#a, -1)
    toUMKE x ==> x pretend UMKE
    toKey k ==> (k@UMKE) pretend Key
    getMKey(a, i)    ==> ((a.i)@UMKE) pretend MKey
    setKey!(a, i, k) ==> (a.i := toUMKE k) pretend Key
    getEntry(a, n, i)     ==> a(n+i) pretend Entry
    setEntry!(a, n, i, e)  ==> (a(n+i) := toUMKE e) pretend Entry
    setKeyEntry!(a, n, i, k, e) ==> (setKey!(a, i, k); setEntry!(a, n, i, e))
    -- deleteKeyEntry!(a, n, i) ==> setKeyEntry!(a, n, i, DELETED, VACANT)
    deleteKeyEntry!(a, n, i) ==> (a.i := toUMKE DELETED; a(n+i) := toUMKE VACANT)
    KE ==> Record(key : Key, entry : Entry)
    UE ==> Union(Entry, "failed")
    maxLoad n ==> n*7 quo 10 -- load factor
    maxVirtualLoad n ==> n*9 quo 10  -- virtual load factor
    Rep ==> Record(_
        numOfEntries : Z, _
        maxNumOfEntries : Z, _
        numOfDeletedEntries : Z, _
        maxNumOfVirtualEntries : Z, _
        idx : Z, _
        arr : Buckets, _
        hashFunction : Key -> I)
    localSearch(a : Buckets, k : Key, h : Key -> I) : Z ==
        n : Z := numOfBuckets a
        h1 : Z := (h k)::Z
        p : Z := positiveRemainder(h1, n) -- position in array
        h2 : Z := 1 + positiveRemainder(h1, n-2)
        mk : MKey := getMKey(a, p)
        deletedPosition? : Boolean := false
        while not vacant? mk repeat
            deleted? mk => (deletedPosition? := true; break)
            k = toKey mk => return p -- key found
            p := p + h2
            if p>=n then p := p-n
            mk := getMKey(a, p)
        q := p -- first position of a free entry
        -- We ignore DELETED entries when looking for the key.
        while not vacant? mk repeat
            not deleted? mk and k = toKey mk =>
                setKeyEntry!(a, n, q, k, getEntry(a, n, p))
                deleteKeyEntry!(a, n, p)
                return q -- entry has been copied to previous DELETED position
            p := p + h2
            if p>=n then p := p-n
            mk := getMKey(a, p)
        if deletedPosition? then q := q-n
        q-n -- KEY not found.
\end{spad}

A very brief introduction to programming in SPAD

  • SPAD is an ordinary programming language, just like C, Java, and Python.
  • SPAD programs are compiled to machine code by the SPAD compiler that comes with FriCAS?.
  • SPAD is a statically typed language with type levels.
    1. Elements: These are the basic data objects. Examples are: 42, 3.14159265, "abc", [3,5,11]. It is one one usually consideres as values in other programming languages.
    2. Domains: These are the types of elements. For example, Integer is a type for 42, 3.14 is of type Float, "abc" is of type String, [1,2,4,8] is of type List(Integer).

      Domains are comparable to classes in object oriented programming languages.

    3. Categories: These are the types of domains. For example, Integer is of type IntegerNumberSystem, String is of type StringCategory, List(Integer) is of type ListAggregate(Integer).

      Categories are somewhat comparable to interfaces in Java, but are much more powerful.

    4. The highest type level is the constant keyword Category. In other words, IntegerNumberSystem, StringCategory, ListAggregate(Integer) are of type Category.
  • SPAD programs are usually definitions of categories and domains whose functionality will later be used in an interactive session or by other definitions.
  • While categories define the exports of domains, i.e. which function are provided, domains themselves implement the corresponding functions.
  • Domains form a type hierarchy where only inheritance from one other domain is allowed.
  • Categories form a type hierarchy with a multiple inheritance mechanism.
  • Categories and domains are often called constructors and (as shown above) can be parametrized.
  • SPAD has only very few built-in constructors. Most of the constructors are defined in a library. Builtin are Record, Tuple, Join, Mapping (abbreviated via ->). Library defined are Integer, List, String, Symbol, Monoid, Field, etc.

A running example

Let us start with a little program. We try not to rely on any previously defined library, but we prefix every constructor with My in order to avoid name conflicts with existing names.

Our goal is to provide a domain MyFun that is parametrized by a domain S and represents functions from S into itself. We would like to be able to turn any function of type S -> S into an element of the MyFun(S) domain. Furthermore, we want to turn this domain into a monoid MyMonoid.

First we define the category MyMonoid.

spad
)abbrev category MYMON MyMonoid
MyMonoid: Category == with
    1: %
    _*: (%, %) -> %
spad
   Compiling FriCAS source code from file 
      /var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/3904508595934233674-25px001.spad
      using old system compiler.
   MYMON abbreviates category MyMonoid 
------------------------------------------------------------------------
   initializing NRLIB MYMON for MyMonoid 
   compiling into NRLIB MYMON 

;;;     ***       |MyMonoid| REDEFINED
Time: 0 SEC.

   finalizing NRLIB MYMON 
   Processing MyMonoid for Browser database:
--->-->MyMonoid(constructor): Not documented!!!!
--->-->MyMonoid(((One) (%) constant)): Not documented!!!!
--->-->MyMonoid((* (% % %))): Not documented!!!!
--->-->MyMonoid(): Missing Description
; compiling file "/var/aw/var/LatexWiki/MYMON.NRLIB/MYMON.lsp" (written 14 FEB 2014 01:07:38 AM):

; /var/aw/var/LatexWiki/MYMON.NRLIB/MYMON.fasl written
; compilation finished in 0:00:00.006
------------------------------------------------------------------------
   MyMonoid is now explicitly exposed in frame initial 
   MyMonoid will be automatically loaded when needed from 
      /var/aw/var/LatexWiki/MYMON.NRLIB/MYMON

Every constructor needs an )abbrev line where one specifies whether the constructore to come is a category or domain. Then follows a capitalized identifier of at most 7 characters and finally the identifier for the constructor.

By convention, constructors begin with an uppercase letter and capitalize the first letter of each new word. Underscores are not commonly used.

spad
rep x ==> (x@%) pretend Rep
per x ==> (x@Rep) pretend %

)abbrev category MYMON MyMonoid
XHashTable(Key : SetCategory, Entry : Type):
  Join(TableAggregate(Key, Entry), finiteAggregate, shallowlyMutable) with
    table : (Key -> SingleInteger) -> %
      ++ table(h) creates an empty hash table that uses h instead of
      ++ hash$Key. Note that h should be a mathematical function in
      ++ the sense that from k1=k2 follows h(k1)=h(k2). If that is not
      ++ the case, k1 and k2 will internally be considered as being
      ++ different keys.
 == add
    Marker ==> None
    toMarker mk ==> mk@Marker -- note that MKey==Marker==UMKE
    VACANT : Marker := (HASHTABLEVACANT$Lisp)  pretend Marker -- pos never used
    DELETED : Marker := (HASHTABLEDELETED$Lisp) pretend Marker -- pos is deleted
    vacant?(mk)  ==> EQ(toMarker mk, VACANT)$Lisp
    deleted?(mk) ==> EQ(toMarker mk, DELETED)$Lisp
    key?(mk) ==> not (vacant? mk or deleted? mk)
    MKey ==> None
    UMKE ==> None
    Buckets ==> PrimitiveArray UMKE
    numOfBuckets(a) ==> shift(#a, -1)
    toUMKE x ==> x pretend UMKE
    toKey k ==> (k@UMKE) pretend Key
    getMKey(a, i)    ==> ((a.i)@UMKE) pretend MKey
    setKey!(a, i, k) ==> (a.i := toUMKE k) pretend Key
    getEntry(a, n, i)     ==> a(n+i) pretend Entry
    setEntry!(a, n, i, e)  ==> (a(n+i) := toUMKE e) pretend Entry
    setKeyEntry!(a, n, i, k, e) ==> (setKey!(a, i, k); setEntry!(a, n, i, e))
    -- deleteKeyEntry!(a, n, i) ==> setKeyEntry!(a, n, i, DELETED, VACANT)
    deleteKeyEntry!(a, n, i) ==> (a.i := toUMKE DELETED; a(n+i) := toUMKE VACANT)
    KE ==> Record(key : Key, entry : Entry)
    UE ==> Union(Entry, "failed")
    maxLoad n ==> n*7 quo 10 -- load factor
    maxVirtualLoad n ==> n*9 quo 10  -- virtual load factor
    Rep ==> Record(_
        numOfEntries : Z, _
        maxNumOfEntries : Z, _
        numOfDeletedEntries : Z, _
        maxNumOfVirtualEntries : Z, _
        idx : Z, _
        arr : Buckets, _
        hashFunction : Key -> I)
    localSearch(a : Buckets, k : Key, h : Key -> I) : Z ==
        n : Z := numOfBuckets a
        h1 : Z := (h k)::Z
        p : Z := positiveRemainder(h1, n) -- position in array
        h2 : Z := 1 + positiveRemainder(h1, n-2)
        mk : MKey := getMKey(a, p)
        deletedPosition? : Boolean := false
        while not vacant? mk repeat
            deleted? mk => (deletedPosition? := true; break)
            k = toKey mk => return p -- key found
            p := p + h2
            if p>=n then p := p-n
            mk := getMKey(a, p)
        q := p -- first position of a free entry
        -- We ignore DELETED entries when looking for the key.
        while not vacant? mk repeat
            not deleted? mk and k = toKey mk =>
                setKeyEntry!(a, n, q, k, getEntry(a, n, p))
                deleteKeyEntry!(a, n, p)
                return q -- entry has been copied to previous DELETED position
            p := p + h2
            if p>=n then p := p-n
            mk := getMKey(a, p)
        if deletedPosition? then q := q-n
        q-n -- KEY not found.
spad
   Compiling FriCAS source code from file 
      /var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/4783886012475744616-25px002.spad
      using old system compiler.
   MYMON abbreviates category MyMonoid 
------------------------------------------------------------------------
   initializing NRLIB XHASHTBL for XHashTable 
   compiling into NRLIB XHASHTBL 
   processing macro definition Marker ==> None 
   processing macro definition toMarker mk ==> @(mk,None) 
   processing macro definition vacant? mk ==> (elt Lisp EQ)(@(mk,None),VACANT) 
   processing macro definition deleted? mk ==> (elt Lisp EQ)(@(mk,None),DELETED) 
   processing macro definition key? mk ==> SEQ(LET(G660,(elt Lisp EQ)(@(mk,None),VACANT)),exit(1,IF(G660,false,SEQ(LET(G661,(elt Lisp EQ)(@(mk,None),DELETED)),exit(1,IF(G661,false,true)))))) 
   processing macro definition MKey ==> None 
   processing macro definition UMKE ==> None 
   processing macro definition Buckets ==> PrimitiveArray None 
   processing macro definition numOfBuckets a ==> shift(# a,- One) 
   processing macro definition toUMKE x ==> pretend(x,None) 
   processing macro definition toKey k ==> pretend(@(k,None),Key) 
   processing macro definition getMKey(a,i) ==> pretend(@(a i,None),None) 
   processing macro definition setKey!(a,i,k) ==> pretend(LET(a i,pretend(k,None)),Key) 
   processing macro definition getEntry(a,n,i) ==> pretend(a +(n,i),Entry) 
   processing macro definition setEntry!(a,n,i,e) ==> pretend(LET(a +(n,i),pretend(e,None)),Entry) 
   processing macro definition setKeyEntry!(a,n,i,k,e) ==> SEQ(pretend(LET(a i,pretend(k,None)),Key),exit(1,pretend(LET(a +(n,i),pretend(e,None)),Entry))) 
   processing macro definition deleteKeyEntry!(a,n,i) ==> SEQ(LET(a i,pretend(DELETED,None)),exit(1,LET(a +(n,i),pretend(VACANT,None)))) 
   processing macro definition KE ==> Record(key: Key,entry: Entry) 
   processing macro definition UE ==> Union(Entry,failed) 
   processing macro definition maxLoad n ==> quo(*(n,7),10) 
   processing macro definition maxVirtualLoad n ==> quo(*(n,9),10) 
   processing macro definition Rep ==> Record(numOfEntries: Z,maxNumOfEntries: Z,numOfDeletedEntries: Z,maxNumOfVirtualEntries: Z,idx: Z,arr: PrimitiveArray None,hashFunction: Key -> I) 
   compiling local localSearch : (PrimitiveArray None,Key,Key -> I) -> Z
   Semantic Errors: 
      [1]  Z is not a known type
      [2] localSearch:  Z is not a known type

   Warnings: 
      [1] pretend(None) -- should replace by @

****** comp fails at level 2 with expression: ******
error in function localSearch 

(SEQ | << |
     (LET (|:| |n| Z)
       (|shift| (|#| |a|) (- 1)))
     | >> |
     (LET (|:| |h1| Z)
       (|::| (|h| |k|) Z))
     (LET (|:| |p| Z)
       (|positiveRemainder| |h1| |n|))
     (LET (|:| |h2| Z)
       (+ 1 (|positiveRemainder| |h1| (- |n| 2))))
     (LET (|:| |mk| (|None|))
       (|pretend| (@ (|a| |p|) (|None|)) (|None|)))
     (LET (|:| |deletedPosition?| (|Boolean|))
       |false|)
     (REPEAT
      (WHILE
       (SEQ
        (LET #1=#:G662
          ((|elt| |Lisp| EQ) (@ |mk| (|None|)) VACANT))
        (|exit| 1
         (IF #1#
             |false|
             |true|))))
      (SEQ
       (LET #2=#:G663
         ((|elt| |Lisp| EQ) (@ |mk| (|None|)) DELETED))
       (|exit| 1
        (IF #2#
            (SEQ
             (LET |deletedPosition?|
               |true|)
             (|exit| 1 (|leave| 1 |$NoValue|)))
            (SEQ
             (LET #3=#:G664
               (= |k| (|pretend| (@ |mk| (|None|)) |Key|)))
             (|exit| 1
              (IF #3#
                  (|return| 1 |p|)
                  (SEQ
                   (LET |p|
                     (+ |p| |h2|))
                   (IF (>= |p| |n|)
                       (LET |p|
                         (- |p| |n|))
                       |noBranch|)
                   (|exit| 1
                    (LET |mk|
                      (|pretend| (@ (|a| |p|) (|None|)) (|None|))))))))))))
     (LET |q|
       |p|)
     (REPEAT
      (WHILE
       (SEQ
        (LET #4=#:G665
          ((|elt| |Lisp| EQ) (@ |mk| (|None|)) VACANT))
        (|exit| 1
         (IF #4#
             |false|
             |true|))))
      (SEQ
       (SEQ
        (LET #5=#:G666
          ((|elt| |Lisp| EQ) (@ |mk| (|None|)) DELETED))
        (|exit| 1
         (IF #5#
             |noBranch|
             (SEQ
              (LET #6=#:G667
                (= |k| (|pretend| (@ |mk| (|None|)) |Key|)))
              (|exit| 1
               (IF #6#
                   (|exit| 3
                    (SEQ
                     (SEQ
                      (|pretend|
                       (LET (|a| |q|)
                         (|pretend| |k| (|None|)))
                       |Key|)
                      (|exit| 1
                       (|pretend|
                        (LET (|a| (+ |n| |q|))
                          (|pretend| (|pretend| (|a| (+ |n| |p|)) |Entry|)
                           (|None|)))
                        |Entry|)))
                     (SEQ
                      (LET (|a| |p|)
                        (|pretend| DELETED (|None|)))
                      (|exit| 1
                       (LET (|a| (+ |n| |p|))
                         (|pretend| VACANT (|None|)))))
                     (|exit| 1 (|return| 1 |q|))))
                   |noBranch|))))))
       (LET |p|
         (+ |p| |h2|))
       (IF (>= |p| |n|)
           (LET |p|
             (- |p| |n|))
           |noBranch|)
       (|exit| 1
        (LET |mk|
          (|pretend| (@ (|a| |p|) (|None|)) (|None|))))))
     (IF |deletedPosition?|
         (LET |q|
           (- |q| |n|))
         |noBranch|)
     (|exit| 1 (- |q| |n|)))
****** level 2  ******
$x:= (LET (: n Z) (shift (# a) (- (One))))
$m:= NoValueMode
$f:=
((((|h| # #) (|k| # #) (|a| # #) (|localSearch| #) ...)))

   >> Apparent user error:
   CANNOT ASSIGN: (shift (# a) (- (One)))
   OF MODE: (NonNegativeInteger)
   TO: n
   OF MODE: Z