• Uvod
• Proc lisp?
• Xektory
• Vetvareni, modifikovani a cteni xektoru
• Alfa notace
• Beta redukce
• Defstruct
• Aktivni datove struktury
• Zaver

Uvod

(budu se tu drzet skvele knizky the connection machine od Hillise kterou v ceske verzi vydala grada. Kazdemu ji doporucuju)

Takze CM lisp je lisp upraveny tak aby svoji strukturou se co nejvice podobal hardwaru cm. Jako normalni lisp odpovida normalnimu hardwaru. Jak pise Hillis:"CmLisp je rozsireni Common Lispu, navrzene pro podporu paralelnich operaci na pocitaci CM. Ma byt pro pocitac CM tim, cim je lisp pro seriovy pocitac: vyrazem podstatnych rysu architektury, ktera vypousti detaily implementace. Cmlisp je abstraktni verzi pocitace CM ve stejnem smyslu, jako jsou fortran nebo lisp abstraktimi verzemy konvencniho pocitace" Cm lisp je konzervativni paralelni jazyk. Stejne jako clos je konzervativni objektovy jazyk-spojuje vyhody struktorovaneho a objektoveho jazyka narozdil treba od smalltalku. Tak i cmlisp spojuje vyhody sekvencniho a paralelniho programovani-to vychazi z toho ze cm je rizena klasickym nadrazenym pocitacem takze cast toho programu je interpretrovana rovnou na tom pocitaci a cast na cm. Pro takovy nekonzervativny jazyk si prostudujte dokumentaci APL nebo FP. Je ale zvlastni ze programy v cmlispu se pisou snadneji a jsou vykonejsy nez programy psane v APL.

Proc lisp?

Xektory

{SKY->BLUE GRASS->GREEN APPLE->RED} 

Xektor nema dane poradi prvku. takze se muze vypisovat prehazene. Na pocitaci CM je kazdy prvek ve zvlastim procesoru a indexem je adresa jineho procesoru. Xektor ma i jine zapisy:

{A->A 1->1 2->2} je stejne jako {A 1 2}
Take lze psat jako pole:
{0->A 1->B 2->C 3->D} je [A B C D]
Taky tu je konstantni xektor co vsechno zobrazuje do jedne hodnoty
{->2}

(SETQ COLOR-OF '{SKY->BLUE APPLE->RED GRASS->GREEN})
=> {APPLE->RED GRASS->GREEN SKY->BLUE}

(XREF COLOR-OF `APPLE)  => RED

(XSET `BLUE COLOR-OF `GRASS)

COLOR-OF => {APPLE->RED GRASS->BLUE SKY->BLUE}

Tabulka casovych zavislosti:
Operace     Vektor  List  Xektor
ELT            1      N     1
LENGTH         1      N     logN
SUBSEQ         1      N     logN
COPY-SEQ       N      N     1
FILL           N      N     1
REMOVE         N      N     1
DELETE         N      N     1
REPLACE        N      N     logN
COUNT          N      N     logN
REVERSE        N      N     logN
POSITION       N      N     1
REDUCE         N      N     logN
SORT           NlogN  NlogN logN*logN
SEARCH         N      N     1

Jak se takove funkce delaji? verte nebo ne pomoci dvou hloupych operatoru:

Alfa notace

A3   => {->3}
A(+ 1 2) => {->3}
A+   => {->+}

(A+ '{a->1 b->2} '{a->3 b->3} provedou se paralelne dva vypocty a vyjde:
      {a->4 b->5}

Vzdycky vyjde {->3}. Tohle vytykani nam ale vetsinou blokujou xektory pred ktery se alpha nepise. Proto lisp ma dalsi znak-puntik co alphu rusi-stejne jako ` a , u maker. Puntik budu psat jako < > priklady:

A(+ < >  x 1) je (A+ x A1)
Kdyz a je xektor [a b c] a X je [x y z] pak:
(CONS A X) => ([a b c] . [x y z])
A(CONS < > A < > X) => [(a.x) (b.y) (c.z)]

(FUNCALL '[+ - - +] '[1 2 3 4] A1) => [ 2 1 2 5 ]

(B+ `{A->1 B->2 C->3}) => 6
(Band `[T T NIL T]) => NIL

(DEFUN DELKA (x) (B+ A(PROG2 < > X 1))

(DEFUN VELIKOST (x) (SQRT (B+ (a* x x))))
(DEFUN VSE-SHODNE (x y) (Band (A= x y))

Muzeme betu pouzit i na konstrukci nevoho xektoru z oboru hodnot a definicniho oboru:

(B `(a->1 b->2) `{a->x b->y}) {x->1 y->2}

Zobecnena beta ma tri parametry: slucovaci funkci a dva xektory. Beta je zkombinuje jak jsme uz rikaly. Veme hodnoty prvniho xektoru a udela znich indexy pro hodnoty druheho xektoru a vrati vznikly xektor tedy vlastne predratuje spoje. To se provede v jednotkovem case. Slucovaci funkce rika jak resit kolize-tedy kdyz v prnim xektoru jsou dve nebo vice stejnych hodnot musi se hodnoty z druheho xektoru nejak zkombinovat. To dela slucovaci funkce. Kdyz zadnou slucovaci funkci nedate kolize hlasi chybu:

(B '[1 2 5] '[x y z]) => {x->1 y->2 z->5}
(B '[1 2 5] '[x z z]) => error

(B+ '[1 2 5] '[x z z]) => {X->1 Z->5}

(B+ '[1 2 5] '{->3}) => {3->8}

(DEFUN INVERZE (X)
 (B (DOMAIN X) X))

(DEFSTRUCT (PIXEL :CM)
  RED
  GREEN
  BLUE)

1. ohodnot vrcholy hodnotou +nekonecno
2. ohodnot vrchol A cislem 0
3. Ohodnot kazdy vrchol krome A cislem 1 + minimum ohodnoceni jeho sousedu. To opakuj dokud B nebude oznaceno.
4. Skonci. Ohodnoceni vrcholu B je odpovedi.

(DEFSTRUCT (VERTEX :CM)
  LABEL
  NEIGHBORS)

A ted algoritmus:

(DEFUN DELKA_CESTY (a b g) 
   A(SETF (LABEL < > g) +INF)   ; provede bod 1 tedy nastavi vsechny labely na
+INF tedy nekonecno
    (SETF (LABEL a) 0 ;bod a na nula
    (LOOP UNTIL (> < (LABEL b) +INF) ;opakuj dokud label od becka je +INF
      DO A(SETF (LABEL > < (REMOVE A G)) ;pro vsechny labely v G mimo bodu A
          (1+ (Bmin A(LABEL < > NEIGHBORS < > G)))))) ;najdi minimum a zvec o 1
    (LABEL B)) ;navratova hodnota.

(Bmin A(LABEL < > (NEIGHBORS V)))

To je zahul co? ale pritom je to jednoduchy :) Tady je videt jak v lispu jde psat primocare a strucne i kdyz to vypada strasne. Ted si zpocitejte kolik radek by to melo v cecku

Aktivni datove struktury

      1---2
       \ /
        5
       / \
      3   4

[1  2  2  3  4 a dale obracene pro dvousmerne cesty5  5  1  5  5 ]
[5  5  1  5  5                                     1  2  2  3  4 ]
A pomoci bety potom muzeme secist vsechny prvky kolem uzlu 
(B+ a b)

zaver

(Bmin A(LABEL < > (NEIGHBORS V)))

beta(min,alpha(labela,v.neighbors))

shape[20][30][40] s

t:s x;