Comp Alg1

Download as pdf or txt
Download as pdf or txt
You are on page 1of 16

@8IC%%! 3_]`edQdY_^Q\=UdX_Tc_V@XicYSc !

)#
3XQ`dUb!! Ci]R_\YS`b_WbQ]]Y^WQ^TS_]`edUbQ\WURbQ

Ci]R_\YS`b_WbQ]]Y^WQ^TS_]`edUbQ\WURbQ

2QH RI WKH PRVW UHYROXWLRQDU\ FRPSXWHU DSSOLFDWLRQV RI UHFHQW \HDUV KDV EHHQ WKH GHYHORSPHQW RI
SURJUDPV WKDW SHUIRUP YDULRXV DOJHEUDLF DQG PDWKHPDWLFDO RSHUDWLRQV RQ V\PEROV UDWKHU WKDQ RQ
Š Š Š
QXPEHUV 3URJUDPV VXFK DV 5('8&( 6&+2216&,3 0$&6<0$  '(5,9(  0DWKHPDWLFD RU
Š
0DSOH KDYH HOLPLQDWHG PXFK RI WKH WHGLXP RI OHQJWK\ SDSHUDQGSHQFLO PDQLSXODWLRQV QRW WR

PHQWLRQ UHGXFLQJ WKH LQFLGHQFH RI DOJHEUDLF HUURUV 

6\PEROLF SURJUDPPLQJ LV EDVHG RQ UXOHV³VHWV RI JHQHUDOL]HG LQVWUXFWLRQV WKDW WHOO WKH FRPSXWHU KRZ
WR WUDQVIRUP RQH VHW RI WRNHQV LQWR DQRWKHU $Q DVVHPEOHU HJ LQSXWV D VHULHV RI PDFKLQH LQVWUXFWLRQV
LQ PQHPRQLF IRUP DQG RXWSXWV D VHULHV RI QXPEHUV WKDW UHSUHVHQW WKH DFWXDO PDFKLQH LQVWUXFWLRQV
DV ELQDU\ QXPEHUV LQ H[HFXWDEOH IRUP +LJKHU RQ WKH VFDOH RI FRPSOH[LW\ D FRPSLOHU LQSXWV KLJKOHYHO
ODQJXDJH FRQVWUXFWV IRUPHG DFFRUGLQJ WR VSHFLILF UXOHV D ´JUDPPDUµ DQG RXWSXWV DQ H[HFXWDEOH
SURJUDP LQ DQRWKHU ODQJXDJH VXFK DV DVVHPEOHU RU PDFKLQH FRGH 7R WDNH EXW RQH H[DPSOH WKH
)2575$1 FRPSLOHU UHFRJQL]HV DQG WUDQVODWHV WKHP LQWR PDFKLQH ODQJXDJH WH[W VWULQJV UHSUH
VHQWLQJ PDWKHPDWLFDO UHODWLRQV LQ TXDVLDOJHEUDLF IRUP

:KDW GR UXOHV KDYH WR GR ZLWK FRPSXWDWLRQDO PHWKRGV RI SK\VLFV" 7KH FUXFLDO HOHPHQW LQ WKH
UXOHEDVHG VW\OH RI SURJUDPPLQJ LV WKH DELOLW\ WR VSHFLI\ JHQHUDO SDWWHUQV RU HYHQ FODVVHV RI SDWWHUQV
VR WKH FRPSXWHU FDQ UHFRJQL]H WKHP LQ WKH LQSXW DQG WDNH DSSURSULDWH DFWLRQ )RU H[DPSOH LQ D
PRGHUQ KLJKHQHUJ\ SK\VLFV H[SHULPHQW WKH UDWH DW ZKLFK YDULRXV SDUWLFOHV LPSLQJH RQ GHWHFWRUV

PLJKW EH  GLVFUHWH HYHQWV SHU VHFRQG 6LQFH HDFK VXFK HYHQW PLJKW EH UHSUHVHQWHG E\  QXPEHUV
WKH VWRUDJH UHTXLUHPHQWV IRU UHFRUGLQJ WKH UHVXOWV RI D W\SLFDO H[SHULPHQW ODVWLQJ  PRQWKV RI
   
UXQQLQJ WLPH PLJKW EH  ² E\WHV RU  ² KLJKFDSDFLW\ GLVN GULYHV &OHDUO\ VR PXFK
VWRUDJH LV RXW RI WKH TXHVWLRQ DQG PRVW RI WKH LQFRPLQJ GDWD PXVW EH GLVFDUGHG 7KDW LV VXFK

H[SHULPHQWV GHPDQG H[WUHPHO\ IDVW ILOWHULQJ PHWKRGV WKDW FDQ GHWHUPLQH³LQ  WR  µVHF³
ZKHWKHU D JLYHQ HYHQW LV LQWHUHVWLQJ 7KH FULWHULD IRU ´LQWHUHVWLQJµ PD\ EH TXLWH JHQHUDO DQG PD\ QHHG
WR EH FKDQJHG GXULQJ WKH UXQQLQJ RI WKH H[SHULPHQW ,Q D ZRUG WKH\ PXVW EH VSHFLILHG E\ VRPH IRUP
RI SDWWHUQ UHFRJQLWLRQ SURJUDP UDWKHU WKDQ KDUGZLUHG

6LQFH WKH SKLORVRSK\ RI WKLV ERRN LV WKDW VWXGHQWV VKRXOG NQRZ ZKDW LV LQVLGH WKH EODFN ER[HV ZH
LOOXVWUDWH UXOHEDVHG SURJUDPPLQJ ZLWK VRPH VLPSOH DSSOLFDWLRQV D SDUHGGRZQ )25PXOD 75$1V

ODWRU
 
VXLWDEOH IRU SDUVLQJ LQWHJHU H[SUHVVLRQV LQWR )RUWK  D VLPSOH SURJUDP IRU PDQLSXODWLQJ WKH γ
PDWULFHV RI TXDQWXP ILHOG WKHRU\ DQG D SURJUDP IRU V\PEROLF GLIIHUHQWLDWLRQ

 5 3DYHOOH 0 5RWKVWHLQ DQG - )LWFK ´&RPSXWHU $OJHEUDµ   'HF 


6FLHQWLILF $PHULFDQ

 7KLV LV D SXQ³WKH ODQJXDJH )2575$1 GHULYHV LWV QDPH IURP ´)25PXOD 75$1VODWRUµ
 $ PRUH VRSKLVWLFDWHG YHUVLRQ IRU VHULRXV FRPSXWDWLRQ LV IRXQG ZLWK WKH LQFOXGHG SURJUDPV
!)$ 9^dUWUb6?B]e\QDB1>c\Qd_b

! 9^dUWUb6?B]e\QDB1>c\Qd_b
7KH HYDOXDWLRQ RI PDWKHPDWLFDO H[SUHVVLRQV LV EDVHG RQ UHFRJQL]LQJ JHQHUDOL]HG SDWWHUQV EDVHG RQ
UXOHV )LUVW ZH VWDWH WKH UXOHV IRU WUDQVODWLQJ VLPSOH IRUPXODV

Be\Uc
7R VSHFLI\ UXOHV ZH QHHG D ODQJXDJH WR H[SUHVV WKHP LQ 7KDW LV ZH QHHG WR EH DEOH WR GHVFULEH WKH

JUDPPDU RI WKH UXOHV 2QH VWDQGDUG QRWDWLRQ UHSUHVHQWV UXOHV DV UHJXODU H[SUHVVLRQV  7KH IROORZLQJ
GHVFULSWLRQ RI D UHGXFHG )2575$1 LOOXVWUDWH KRZ WKLV ZRUNV

\ Rules for integer FORmula TRANslator

\ NOTATION:
\ | -> “or”,
\ ^ -> “unlimited repetitions”
\ ^n -> “0-n repetitions”
\ Q -> “empty set”
\ & -> + | -
\ % -> * | /

\ <integer> -> { - | Q} {<digit> <digit>^8}

\ FORMULAS:
\ <id> -> <letter> {<letter>|<digit>}^6
\ <assign> -> <id> = <expression>
\ <expressionn> -> <term> | <term> & <expression>
\ <term> -> <factor>|<factor> % <term>
\ <factor> -> <id> | integer | ( <expression> )

$QJOH EUDFNHWV GHQRWH JUDPPDWLFDO HOHPHQWV VXFK DV <expression>  DUURZV -> PHDQ ´LV GHILQHG
E\µ RWKHU QRWDWLRQDO FRQYHQWLRQV VXFK DV ´_µ WR VWDQG IRU ´RUµ DUH OLVWHG LQ WKH NOTATION VHFWLRQ
RI WKH UXOHV OLVW IRU PQHPRQLF FRQYHQHQLHQFH $ VWDWHPHQW VXFK DV

\ <integer> -> {– | Q} {<digit> <digit>^8}

WKHUHIRUH PHDQV

1^ Y^dUWUb Yc TUVY^UT Ri Q^ _`dY_^Q\ \UQTY^W ]Y^ec cYW^ V_\\_gUT Ri ! TYWYd gXYSX Yc Y^ deb^ V_\\_gUT

Ri Qc ]Q^i Qc ( ]_bU TYWYdc

6LPLODUO\ WKH SKUDVH

\ <assign> -> <id> = <expression>

PHDQV

1^ QccYW^]U^d cdQdU]U^d S_^cYcdc _V Q^ YTU^dYVYUb±Q ci]R_\ bU`bUcU^dY^W Q^ QTTbUcc Y^

]U]_bi±V_\\_gUT Ri Q^ UaeQ\c cYW^ V_\\_gUT Ri Q^ Uh`bUccY_^

 6HH $9 $KR 5 6HWKL DQG -' 8OOPDQ &RPSLOHUV … $GGLVRQ:HVOH\ 5HDGLQJ  
@8IC%%! 3_]`edQdY_^Q\=UdX_Tc_V@XicYSc !)%
3XQ`dUb!! Ci]R_\YS`b_WbQ]]Y^WQ^TS_]`edUbQ\WURbQ

1RWH WKDW VRPH RI WKHVH GHILQLWLRQV DUH UHFXUVLYH D VWDWHPHQW VXFK DV

\ <expressionn> -> <term> | <term> & <expression>

VHHPV WR EH GHILQHG LQ WHUPV RI LWVHOI 6R LW LV D JRRG EHW WKDW D SURJUDP WKDW UHFRJQL]HV DQG WUDQVODWHV

DQ H[SUHVVLRQ FDQ EH ZULWWHQ UHFXUVLYHO\ 

D__\c
7R DSSO\ D UXOH VWDWHG DV D UHJXODU H[SUHVVLRQ WKH SURJUDP PXVW EH DEOH WR UHFRJQL]H D JLYHQ SDWWHUQ
7KDW LV JLYHQ D VWULQJ ZH QHHG WR EH DEOH WR GHFLGH ZKHWKHU LW LV DQ LQWHJHU RU VRPHWKLQJ HOVH :H
GR WKLV E\ VWHSSLQJ WKURXJK WKH VWULQJ RQH FKDUDFWHU DW D WLPH IROORZLQJ WKH UXOH

\ <integer> -> {– | Q} {<digit> <digit>^8}

7KLV SDWWHUQ EHJLQV ZLWK D PLQXV RU QRWKLQJ IROORZHG E\ D GLJLW DQG ]HUR WR HLJKW PRUH GLJLWV

@QddUb^bUS_W^YjUbc
2QH RIWHQ VHHV SDWWHUQ UHFRJQL]HUV H[SUHVVHG DV FRPSOH[ ORJLF WUHHV LH DV VHTXHQFHV RI QHVWHG
FRQGLWLRQDOV DV LQ WKH IORZ GLDJUDP RQ WKH QH[W SDJH $V ZH VHH WKH WUHH LV ILYH OHYHOV GHHS HYHQ
WKRXJK ZH KDYH FRQFHDOHG WKH GHFLVLRQV SHUWDLQLQJ WR WKH H[SRQHQW SDUW RI WKH QXPEHU LQ D ZRUG
exponent? :KHQ SURJUDPPHG FRQYHQWLRQDOO\ ZLWK IF… ELSE… THEN VWDWHPHQWV WKH SUR

JUDP EHFRPHV WRR FRPSOH[ IRU FRPSUHKHQVLRQ RU PDLQWDLQDQFH 

,W KDV EHHQ NQRZQ IRU PDQ\ \HDUV WKDW D EHWWHU ZD\ WR DSSO\ JHQHUDO UXOHV³HJ WR GHWHUPLQH ZKHWKHU
D JLYHQ VWULQJ FRQIRUPV WR WKH UXOHV IRU ´IORDWLQJ SRLQW QXPEHUµ³XVHV ILQLWH VWDWH PDFKLQHV )60 
+HUH LV DQ H[DPSOH ZULWWHQ LQ VWDQGDUG )RUWK

\ determine whether the string at $adr is a fp#


: skip_char ( adr char -- adr’) OVER C@ = ABS + ;
\ assumes “true” = -1 or +1

: skip- ( adr -- adr’) [CHAR] - skip_char ;


: skip_dp ( adr -- adr’) [CHAR] . skip_char ;

: digit? ( char -- f) [CHAR] 0 [ CHAR 9 1+ ] LITERAL WITHIN ;


: skip_dig ( adr2 adr1 - - adr2 adr1’)
BEGIN 2DUP > OVER C@ digit? AND
WHILE 1+
REPEAT ;

 %\ WKHRUHP D UHFXUVLYH SURJUDP FDQ DOZD\V EH ZULWWHQ QRQUHFXUVLYHO\ +RZHYHU WKLV SURFHVV RIWHQ
KLGHV WKH VWUXFWXUH RI WKH SURJUDP DQG PDNHV LW XQQHFHVVDULO\ FRPSOH[
 7KHVH GHIHFWV RI QHVWHG FRQGLWLRQDOV DUH JHQHUDOO\ UHFRJQL]HG &RPPHUFLDOO\ DYDLODEOH &$6( WRROV VXFK
DV 6WLUOLQJ &DVWOH·V/RJLF *HP WKDW WUDQVODWHV ORJLFDO UXOHV WR FRQGLWLRQDOV  DQG 0DWUL[ 6RIWZDUH·V0D
WUL[ /D\RXWDQG $<(&2 ,QF·V &203(',725 WKDW WUDQVODWH WDEXODU UHSUHVHQWDWLRQV RI )60V WR FRQ
GLWLRQDOV LQ DQ\ RI VHYHUDO ODQJXDJHV ZHUH RULJLQDOO\ GHYHORSHG DV LQKRXVH DLGV
!)& 9^dUWUb6?B]e\QDB1>c\Qd_b
@8IC%%! 3_]`edQdY_^Q\=UdX_Tc_V@XicYSc !)'
3XQ`dUb!! Ci]R_\YS`b_WbQ]]Y^WQ^TS_]`edUbQ\WURbQ

: skip_exponent … ; \ this definition shown below

: fp#? ( $adr -- f)
DUP 0 OVER COUNT + C! \ add terminator
DUP C@ 1+ OVER C! \ count =count+1
COUNT OVER + 1- SWAP ( end beg )
skip-
skip_dig
skip_dp
skip_dig
skip_exponent ( end beg’ )
TUCK ( beg’ end beg’ )
= \ beg’ = end ?
SWAP C@ 0= AND ; \ and last_char = terminal?

7KH SURJUDP ZRUNV OLNH WKLV

• $SSHQG D XQLTXH WHUPLQDO FKDUDFWHU WR WKH VWULQJ


• ,I WKH ILUVW FKDUDFWHU LV ´²µ DGYDQFH WKH SRLQWHU  E\WH RWKHUZLVH DGYDQFH  E\WHV
• 6NLS RYHU DQ\ GLJLWV XQWLO D QRQGLJLW LV IRXQG
• ,I WKDW FKDUDFWHU LV D GHFLPDO SRLQW VNLS RYHU LW
• 6NLS DQ\ GLJLWV IROORZLQJ WKH GHFLPDO SRLQW
• $ IORDWLQJ SRLQW QXPEHU WHUPLQDWHV ZLWK DQ H[SRQHQW IRUPHG DFFRUGLQJ WR WKH DSSURSULDWH UXOH
skip_exponent DGYDQFHV WKH SRLQWHU WKURXJK WKLV VXE VWULQJ RU HOVH KDOWV DW WKH ILUVW FKDUDF
WHU WKDW IDLOV WR ILW WKH UXOH
• 'RHV WKH LQLWLDO SRLQWHU beg’ QRZ SRLQW WR WKH FDOFXODWHG HQG RI WKH VWULQJ end " $QG LV WKH
ODVW FKDUDFWHU WKH XQLTXH WHUPLQDO" ,I VR UHSRUW ´WUXHµ HOVH UHSRUW ´IDOVHµ

:H GHIHUUHG WKH GHILQLWLRQ RI skip_exponent 8VLQJ FRQGLWLRQDOV LW FRXOG ORRN OLNH


: skip+ ( adr -- adr’) [CHAR] + skip_char ;
: dDeE? ( char -- f)
>ucase \ change to uppercase
[CHAR] D [ CHAR E 1+ ] WITHIN ;
: skip_exponent ( adr -- adr’)
DUP C@ dDeE? IF 1+ ELSE EXIT THEN
skip- skip+
DUP C@ digit? IF 1+ ELSE EXIT THEN
DUP C@ digit? IF 1+ ELSE EXIT THEN
DUP C@ digit? IF 1+ ELSE EXIT THEN ;

7KDW LV

• VNLS DQ LQLWLDO H[SRQHQW VLJQLILFDWRU dD RU eE


• VNLS DQ LQLWLDO DOJHEUDLF VLJQ
• VNLS XS WR  GLJLWV H[SRQHQWV FDQ EH XS WR  GLJLWV ORQJ 
!)( 9^dUWUb6?B]e\QDB1>c\Qd_b

6Y^YdUcdQdU]QSXY^Uc
-XVW DV ZH QHHG D )60 WR DFKLHYH D
JUDFHIXO GHILQLWLRQ RI fp#?  ZH PLJKW
WU\ WR GHILQH skip_exponent DV D
VWDWH PDFKLQH DOVR 7KLV PHDQV LW LV
WLPH WR GHILQH ZKDW ZH PHDQ E\ ILQLWH
VWDWH PDFKLQHV $ ILQLWH VWDWH PD

FKLQH LV D SURJUDP RULJLQDOO\ LW ZDV

D KDUGZLUHG VZLWFKLQJ FLUFXLW WKDW
WDNHV D VHW RI GLVFUHWH PXWXDOO\ H[FOX
VLYH LQSXWV DQG PDLQWDLQV D VWDWH
YDULDEOH WKDW WUDFNV WKH KLVWRU\ RI WKH
PDFKLQH·V LQSXWV $FFRUGLQJ WR ZKLFK
VWDWH WKH PDFKLQH LV FXUUHQWO\ LQ D
JLYHQ LQSXW ZLOO SURGXFH GLIIHUHQW UH
State transition diagram for skip_exponent
VXOWV 7KH )60 SURJUDP FDQ EH H[
SUHVVHG HLWKHU DV D VWDWH WUDQVLWLRQ GLD
JUDP RU DV D WUDQVLWLRQ WDEOH

7DEXODU UHSUHVHQWDWLRQ IRU ILQLWH VWDWH PDFKLQH skip_exponent


VWDWH ↓ ? LQSXW RWKHU G'H( VLJQ GLJLW

 LQLWLDO QRRS →  → HUURU → HUURU →


 QRRS → HUURU →  →  →
 QRRS → HUURU → HUURU →  →
 QRRS → HUURU → HUURU →  →
 QRRS → HUURU → HUURU →  →
 WHUPLQDO

ZKLFK , ILQG FOHDUHU  ,Q WKH WDEXODU UHSUHVHQWDWLRQ HDFK FHOO FRQWDLQV WZR FRPSRQHQWV DQ DFWLRQ
IROORZHG E\ D WUDQVLWLRQ WR DQRWKHU VWDWH 7KH SRVVLEOH DFWLRQV LQ WKLV H[DPSOH DUH

noop \ do nothing
1+ \ increment pointer
error \ display an error message.

 5 6HGJHZLFN $OJRULWKPV $GGLVRQ:HVOH\ 3XEOLVKLQJ &R 5HDGLQJ 0$  S II


 $9 $KR 5 6HWKL DQG -' 8OOPDQ $GGLVRQ :HVOH\ 3XE
&RPSLOHUV 3ULQFLSOHV 7RROV DQG 7HFKQLTXHV
OLVKLQJ &RPSDQ\ 5HDGLQJ 0$  
 =YL .RKDYL  QG HG 0F*UDZ+LOO 3XEOLVKLQJ &R 1HZ <RUN
6ZLWFKLQJ DQG )LQLWH $XWRPDWD 7KHRU\
 
@8IC%%! 3_]`edQdY_^Q\=UdX_Tc_V@XicYSc !))
3XQ`dUb!! Ci]R_\YS`b_WbQ]]Y^WQ^TS_]`edUbQ\WURbQ

7KH WDEXODU UHSUHVHQWDWLRQ RI D )60 LV FOHDQHU WKDQ QHVWHG ORJLF ,Q D )60 WKH LQSXWV PXVW EH
 
PXWXDOO\ H[FOXVLYH DQG H[KDXVWLYH  WKHUHE\ HOLPLQDWLQJ FRQGLWLRQV WKDW FDQQRW EH IXOILOOHG³WKDW
LV FRQGLWLRQV OHDGLQJ WR ´GHDGµ FRGH³VRPHWKLQJ WKDW RZLQJ WR KXPDQ IUDLOW\ IUHTXHQWO\ KDSSHQV
ZLWK QHVWHG ORJLF 7KH LQFLGHQFH RI EXJV LQ WDEXODU )60V LV PXFK OHVV WKDQ ZLWK ORJLF WUHHV

)2575$1 %$6,& RU $VVHPEOHU FDQ LPSOHPHQW )60V ZLWK FRPSXWHG GOTOV ,Q %$6,& HJ ZH
FRXOG ZULWH

DEF SUB FSM (c$, adress%)


k% =0 ’ convert input to column #
C$=UCASE (c$)
IF C$=“D” OR C$=“E” THEN k%=1
IF C$=“+” OR C$=“-” THEN k%=2
IF ASC(C$) >= 48 AND ASC(C$) <=57 THEN k%=3
’ begin FSM proper
ON state% *3 + k% GOTO (0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19)
0: state%=5
1: adress% = adress% +1 : state% = 1
2: CALL Error : state% = 5 ’ row 0
3: state%=5
4: state%=5
5: state%=5
6: adress% = adress% +1 : state% = 2 ’ row 1
7: adress% = adress% +1 : state% = 3
… … etc. … …

16: state%=5
… … etc. … … ’ row 4
19: adress% = adress% +1 : state% = 5
END SUB

7KH DGYDQWDJH RI )60 FRQVWUXFWLRQ XVLQJ FRPSXWHG GOTOV LV VLPSOLFLW\ LWV GLVDGYDQWDJH LV WKH OLQHDU
IRUPDW RI WKH SURJUDP ZKLFK KLGHV WKH VWDWH WDEOH·V VWUXFWXUH 7KH (DNHU CASE VWDWHPHQW³D FRQWURO
VWUXFWXUH DYDLODEOH LQ & 3DVFDO 4XLFN%$6,& RU )RUWK³SURGXFHV FRGH WKDW LV QR FOHDUHU 7R DFKLHYH
FODULW\ ZLWK VXFK WRROV ZH PXVW ZULWH RXW WKH VWDWH WDEOH LQ FRPPHQW IRUP LQ D GRFXPHQWDWLRQ VHFWLRQ
WKHUHE\ LQFUHDVLQJ WKH OHQJWK DQG GHFUHDVLQJ WKH UHDGDELOLW\ RI WKH VRXUFH FRGH

+RZHYHU H[WHQVLEOH ODQJXDJHV OLNH )RUWK /LVS DQG & SHUPLW XV WR GHILQH FRGH WKDW ZLOO FUHDWH D
)60 IURP LWV VWDWHWDEOH UHSUHVHQWDWLRQ ,Q )RUWK WKLV ORRNV OLNH

 ´0XWXDOO\ H[FOXVLYHµ PHDQV RQO\ RQH LQSXW DW D WLPH FDQ EH WUXH
 ´([KDXVWLYHµ PHDQV HYHU\ SRVVLEOH LQSXW PXVW EH UHSUHVHQWHG
" 3_]`edUbQ\WURbQ

4 wide fsm: (exponent) \ begin fsm, giving # of columns


\ input | other | dDeE | sign | digit |
\ state --------------------------------------------
( 0) | noop >5 | 1+ >1 | err >5 | err >5
( 1) | noop >5 | err >5 | 1+ >2 | 1+ >3 \ "nothing"
( 2) | noop >5 | err >5 | err >5 | 1+ >3
( 3) | noop >5 | err >5 | err >5 | 1+ >4
( 4) | noop >5 | err >5 | err >5 | 1+ >5
;fsm \ terminate fsm

: skip_exponent ( adr -- adr’)


0 >state (exponent) \ initialize state
BEGIN DUP C@ ( -- adr char)
DUP dDeE? ABS OVER \ convert input char to col#
+/-? 2 AND + SWAP
digit? 3 AND + ( -- adr col#)
state: (exponent) \ get state
5 < \ not terminal state?
WHILE (exponent) \ perform the fsm
REPEAT ;

@eddY^WYdd_WUdXUb
2QFH ZH KDYH WKH WRROV IRU UHFRJQL]LQJ SDWWHUQV LQ VWULQJV ZH FUHDWH WKH SDUWV ERWWRP XS WR WUDQVODWH
D IRUPXOD 7KH SURJUDP JLYHQ LQ $SSHQGL[ $ VKRZV KRZ WKLV LV GRQH

" 3_]`edUbQ\WURbQ
T he study of symbolic manipulation has led to rich new areas of pure mathematics12. H ere we
illustrateour new tool (for compilingfinitestateautomata) with arule-based recursiveprogram
to solve a problem that does not need much formal mathematical background. T he resulting
program executed much faster on a slow, old PC than REDU CE (a symbolic manipulation
program with built-in γ-matrix algebrafeatures) did on alargemainframe, so theprogramming
effort was definitely worthwhile.

CdQdY^WdXU`b_R\U]
Dirac γ-matrices are 4×4 traceless, complex matrices defined by a set of (anti)commutation
relations13. T hese are

 6HH  0 0LJQRWWH


HJ 0DWKHPDWLFV IRU &RPSXWHU $OJHEUD 6SULQJHU9HUODJ %HUOLQ  
 7KH\ DUH VDLG WR VDWLVI\ D &OLIIRUG DOJHEUD 6HH  -' %MRUNHQ DQG 6' 'UHOO
HJ 5HODWLYLVWLF 4XDQWXP
0HFKDQLFV 0F*UDZ+LOO ,QF 1HZ <RUN   DOVR 9% %HUHVWHWVNLv (0 /LIVKLW] DQG /3 3L
WDHYVNLv 3HUJDPRQ 3UHVV 2[IRUG  S II
5HODWLYLVWLF 4XDQWXP 7KHRU\ 3DUW 
@8IC%%! 3_]`edQdY_^Q\=UdX_Tc_V@XicYSc " !
3XQ`dUb!! Ci]R_\YS`b_WbQ]]Y^WQ^TS_]`edUbQ\WURbQ

γµ γν + γν γµ =  ηµν  µ  ν =  …   

ZKHUH ηµν LV D PDWUL[YDOXHG WHQVRU


µ?ν    
  ,   
ηµν =  
   −,    
   −,  

 
     −, 
 
,Q )H\QPDQ·V QRWDWLRQ ZH IRUP PDWULFHV $ E\ WDNLQJ WKH GRW SURGXFW RI D YHFWRU ZLWK D γPDWUL[
GI
$ = $µ γµ ≡ $

γ −

$

γ −

$ γ − $

γ


7KH WUDFH RI DQ\ PDWUL[ LV GHILQHG WR EH WKH VXP RI LWV GLDJRQDO HOHPHQWV

GI 1
) = ∑
7U ($ $ NN  
N= 

&OHDUO\ WUDFHV REH\ WKH GLVWULEXWLYH ODZ

7U ($ + % ) ≡ 7U ($ ) + 7U (% ) D

DV ZHOO DV D FRPPXWDWLYH ODZ

7U ($ )% ≡ 7U ( % ) 
$ E

)URP (T   DQG DE ZH ILQG

7U ($ )% ≡


[ 7U ($ % ) + 7U (% $ )] =


7U ( %
$ + % )
$ 


=  $ ⋅% 7U (,) ≡  $ ⋅%


7KH WUDFH RI  JDPPD PDWULFHV FDQ EH REWDLQHG DQDORJRXV WR (T  E\ UHSHDWHG DSSOLFDWLRQ RI WKH
DOJHEUDLF ODZV 

7U ($ % )
& ' = $ ⋅ % 7U (& ' ) − 7U (% )
$ & ' 

≡ $ ⋅ % 7U (& ' ) − 7U ($ )
& ' %

≡  $ ⋅% & ⋅' − $ ⋅& % ⋅' + $ ⋅' % ⋅&


 
:H LQFOXGH (T  IRU WHVWLQJ SXUSRVHV 7KH IDFWRUV RI  LQ (T  DQG  GR QRWKLQJ XVHIXO VR ZH PLJKW
DV ZHOO VXSSUHVV WKHP IURP WKH RXWSXW LQ WKH LQWHUHVW RI D VLPSOHU SURJUDP
" " 3_]`edUbQ\WURbQ

DXUbe\Uc
:H DSSO\ IRUPDO UXOHV DQDORJRXV WR WKRVH XVHG LQ SDUVLQJ D ODQJXDJH 7KH UXOHV IRU WUDFHV DUH

\ Gamma Matrix Algebra Rules:


\ a -> string of length <=3
\ / -> delineator for factors
\ <factor> -> a/
\ product/ -> a/b/c/d/ …
\ Tr( a/b/prod/) -> a.b ( tr( prod/) ) - tr( a/prod/b/)
\ b -> mark b as permuted
\ Tr( a/) -> 0 (a single factor is traceless)

5HSHDWHG DGMDFHQW IDFWRUV FDQ EH FRPELQHG WR SURGXFH D PXOWLSOLFDWLYH FRQVWDQW

%
% ≡ % ⋅% 

UHFRJQL]LQJ VXFK IDFWRUV FDQ VKRUWHQ WKH ILQDO H[SUHVVLRQV VLJQLILFDQWO\ KHQFH WKH UXOH

\ Tr( a/a/prod/) -> a.a ( Tr( prod/) ).

,Q WKH VDPH FDWHJRU\ ZKHQ WZR YHFWRUV DUH RUWKRJRQDO ⋅ =  DQRWKHU VLPSOLILFDWLRQ RFFXUV
$ %

\ PERP A B -> A.B = 0


\ Tr( A/B/prod/) -> – Tr( A/prod/B/)

7KH DELOLW\ WR UHFRJQL]H RUWKRJRQDO YHFWRUV OHWV XV HYDOXDWH WKH WUDFH RI D SURGXFW WLPHV WKH VSHFLDO

γPDWUL[ 

    
    
γ =Lγ γ γ γ =
    
 
   
 
   

WKDW DQWLFRPPXWHV ZLWK DOO IRXU RI WKH γµ 


γ γµ + γµ γ ≡   µ =  …   
 

7KH IXOO\ DQWLV\PPHWULF WHQVRU εµνκλ ≡ − ενµκλ  HWF OHWV XV ZULWH

γ
%
$ & ≡ L εµνκλ $ µ % ν & κ γλ  

ZKHUH DV XVXDO L = √− 

$ FRPSOHWH JDPPD PDWUL[ SDFNDJH ZLOO LQFOXGH UXOHV IRU WUDFHV FRQWDLQLQJ γ


\ Trg5( a/b/c/d/x/) -> i Tr( ^/d/x/)


\ ^.d -> [a,b,c,d] (antisymmetric product)
\ Note: ^.a = ^.b = ^.c = 0

 1RWH %HUHVWHWVNLv HW DO  RS FLW GHILQH γ ZLWK DQ RYHUDOO ´²µ VLJQ UHODWLYH WR (T 
@8IC%%! 3_]`edQdY_^Q\=UdX_Tc_V@XicYSc " #
3XQ`dUb!! Ci]R_\YS`b_WbQ]]Y^WQ^TS_]`edUbQ\WURbQ

6LQFH γPDWULFHV RIWHQ DSSHDU LQ H[SUHVVLRQV OLNH ($


+ $ , )  LW ZLOO DOVR EH FRQYHQLHQW WR LQFOXGH
P

WKH DGGLWLRQDO QRWDWLRQ DQG LWV UXOHV

\ *A/ -> [A/ + mA]


\ Tr( *A/ x/ ) -> m[A] ( Tr( x/) ) + Tr( x/ A/)

DXU`b_WbQ]
:H SURJUDP IURP WKH ERWWRP XS WHVWLQJ DGGLQJ DQG PRGLI\LQJ DV ZH JR %HJLQ ZLWK WKH XVHU LQWHUIDFH
ZH ZRXOG OLNH WR VD\

tr( a/b/c/d/)

WR REWDLQ WKH RXWSXW

= a.bc.d-a.cb.d+a.db.c ok

(YLGHQWO\ RXU SURJUDP ZLOO LQSXW D VWULQJ WHUPLQDWHG E\ D ULJKW SDUHQWKHVLV ´)µ LH WKH ULJKW
SDUHQWKHVLV WHOOV LW WR VWRS LQSXWWLQJ 7KLV FDQ EH GRQH ZLWK WKH ZRUG

: TEXT WORD HERE PAD $! ;


: get$ [CHAR] ) TEXT PAD X$ $! ;

6LQFH WKH UXOHV DUH LQKHUHQWO\ UHFXUVLYH ZH SXVK WKH LQSXW VWULQJ RQWR D VWDFN EHIRUH RSHUDWLRQV
FRPPHQFH :KDW VWDFN" &OHDUO\ ZH QHHG D VWDFN WKDW FDQ KROG VWULQJV RI ´DUELWUDU\µ OHQJWK 7KH
VWULQJV FDQQRW EH WRR ORQJ EHFDXVH WKH QXPEHU RI WHUPV RI RXWSXW KHQFH WKH RSHUDWLQJ WLPH JURZV

ZLWK WKH QXPEHU RI IDFWRUV 1 LQ IDFW OLNH (1 ⁄ )  


7KH SVHXGRFRGH IRU WKH ODVW ZRUG RI WKH GHILQLWLRQ LV FOHDUO\ VRPHWKLQJ OLNH
: tr(
get$ \ get a $ (terminated with “)” )
setup \ push $ on $stack
do_trace ;

7KH UHDO ZRUN LV GRQH E\ do_trace ZKRVH SVHXGRFRGH ORRNV OLNH

: do_trace ( $: a/b/x/ )
$pop \ pop the current sub-string off the $-stack
2factors \ get the 2 leftmost factors
b=b’? \ is the 2nd factor marked (i.e. has it come home)?
IF EXIT THEN \ output nothing
a.b \ output dot product
more? \ is x/ <> "" (empty string)?
IF rearrange ( $: ~a/x/b’ x/)
." (" RECURSE ." )" \ print a left-(, evaluate x/ and print a right-)
RECURSE \ evaluate the item left on the $-stack
THEN ;

1RWH KRZ UHFXUVLRQ VLPSOLILHV WKH SUREOHP RI PDWFKLQJ OHIW DQG ULJKW SDUHQWKHVHV LQ WKH RXWSXW

1H[W ZH GHILQH WKH XQGHUO\LQJ GDWD VWUXFWXUHV 5HFXUVLRQ GHPDQGV D VWDFN WR KROG VWULQJV LQ YDULRXV
VWDJHV RI GHFRPSRVLWLRQ DQG SHUPXWDWLRQ 6LQFH WKH QXPEHU RI WHUPV JURZV YHU\ UDSLGO\ ZLWK WKH
" $ 3_]`edUbQ\WURbQ

QXPEHU RI IDFWRUV LW ZLOO WXUQ RXW WKDW WDNLQJ WKH WUDFH RI DV PDQ\ DV  GLVWLQFW IDFWRUV LV D PDWWHU
RI VRPH ZHHNV RQ ²VD\² D  0K]  3& WKDW LV ² LV WKH ODUJHVW SUDFWLFDEOH QXPEHU RI IDFWRUV
6R LI ZH PDNH SURYLVLRQ IRU H[SUHVVLRQV  IDFWRUV ORQJ WKDW VKRXOG EH ODUJH HQRXJK IRU DQ\ SUDFWLFDO
SXUSRVH

7R VLPSOLI\ WKH PDQLSXODWLRQV DQG UHGXFH WKH VL]H RI WKH VWULQJ VWDFN ZH ZLOO WRNHQL]H WKH LQSXW VWULQJ
7KDW LV HDFK IDFWRUQDPH LQ WKH RULJLQDO ZLOO EH UHSUHVHQWHG E\ D E\WH LQWHJHU IURP  WR K LH

VPDOOHU WKDQ G 7KLV OHDYHV WKH WK WK DQG WK ELWV IUHH WR VHUYH DV IODJV WR LQGLFDWH WKH SURSHUWLHV
RI WKH IDFWRUV 7KDW LV ZH QHHG WR LQGLFDWH ZKHWKHU D IDFWRU LV ´VWDUUHGµ LH ZKHWKHU LW UHSUHVHQWV

($ + P$ , ) RU $  DFFRUGLQJ WR WKH UXOH

\ *A/ -> (A/ + m[A] ) .

$JDLQ ZH QHHG WR EH DEOH WR LQGLFDWH ´UHGQHVVµ VKRZLQJ WKDW D IDFWRU KDV EHHQ SHUPXWHG IROORZLQJ
WKH UXOH

\ Tr( a/b/prod/) -> a.b ( tr( prod/) ) - tr( a/prod/b/)

7KXV ZH VHW ELW  128 OR WR LQGLFDWH ´VWDUµ DQG ELW  64 OR WR LQGLFDWH ´UHGµ
:H VWLOO QHHG WR LQGLFDWH WKH OHDGLQJ VLJQ 0\ ILUVW LPSXOVH ZDV WR XVH ELW  EXW , UHDOL]HG WKH ILUVW
IDFWRU LV QHYHU SHUPXWHG KHQFH LWV WK ELW LV DYDLODEOH WR VLJQLI\ WKH VLJQ ,W LV WRJJOHG E\ WKH SKUDVH
64 XOR ,Q WKH $-stack SLFWXUHV DSSHDULQJ LQ WKH )LJXUHV ZH LQGLFDWH WRJJOLQJ E\ D OHDGLQJ ´~µ
)RU VDIHW\ ZH RXJKW WR LQTXLUH KRZ GHHS WKH $-stack FDQ JHW 7KDW LV ZH FHUWDLQO\ ZDQW WR DOORZ HQRXJK
VSDFH WKDW ZH ZLOO QRW RYHUZULWH SURJUDP PHPRU\ E\ KDYLQJ WKH VWDFN JHW WRR GHHS 7KH UXOH

\ Tr( a/b/x/) -> a.b ( Tr( x/) ) - Tr( a/x/b’/)

VXJJHVWV WKDW IRU DQ H[SUHVVLRQ RI OHQJWK Q = N WKH PD[LPXP GHSWK ZLOO EH RQO\ N +  7KXV ZH
VKRXOG SODQ IRU D VWDFN GHSWK RI DW OHDVW  SHUKDSV  IRU VDIHW\ 6LQFH ZH DUH WRNHQL]LQJ WKH LQSXW
WKLV PHDQV DW PRVW  E\WHV RI PHPRU\ D WULYLDO DPRXQW RQ WRGD\·V FRPSXWHUV

3URJUDPPLQJ WKHVH DVSHFWV LV VLPSOH HQRXJK WKDW ZH QHHG QRW GZHOO RQ LW 7KH HQWLUH SURJUDP DSSHDUV
LQ $SSHQGL[ % EHORZ

1RZ ZH WHVW WKH SURJUDP


TR( A/B/C/D/E/F/) =
A.B(C.D(E.F)–C.E(D.F)+C.F(D.E))
–A.C(D.E(B.F)–D.F(B.E)+B.D(E.F))
+A.D(E.F(B.C)–B.E(C.F)+C.E(B.F))
-A.E(B.F(C.D)–C.F(B.D)+D.F(B.C))
+A.F(B.C(D.E)–B.D(C.E)+B.E(C.D)) ok

Clearly the concept works. Our next task is to incorporate branches to take care of “starred”,
as well as identical and/or orthogonal adjacent factors. T he possible responses to the different
cases are presented in decision-table form below.
VWDFN UHDUUDQJHPHQWV DQG DFWLRQV IRU SRVVVLEOH LQSXWV
LQSXW a/b/x/ *a/b/x/ a/*b/x/ a/a/x/ a/b/x/
UHVXOWLQJ ~a/x/b/ a/b/x/ a/b/x/ … …
@8IC%%! 3_]`edQdY_^Q\=UdX_Tc_V@XicYSc " %
3XQ`dUb!! Ci]R_\YS`b_WbQ]]Y^WQ^TS_]`edUbQ\WURbQ

VWDFN UHDUUDQJHPHQWV DQG DFWLRQV IRU SRVVVLEOH LQSXWV


VWDFN x/ b/x/ a/x/ x/ ~a/x/b/
DFWLRQ V  ‚ a.b m_a m_b a.a RECURSE
( RECURSE ) ( RECURSE ) ( RECURSE ) ( RECURSE )
RECURSE RECURSE RECURSE
‚
1RWH FKDUDFWHUV VKRZQ LQ italic DUH HPLWWHG DQG m_a PHDQV PD 

7R DYRLG H[FHVVLYHO\ FRQYROXWHG ORJLF ZH HVFKHZ QHVWHG EUDQFKLQJ FRQVWUXFWV $ ILQLWH VWDWH PDFKLQH
ZRXOG EH LGHDO IRU FODULW\ KRZHYHU DV WKH DERYH WDEOH PDNHV FOHDU WKH ORJLF LV QRW UHDOO\ WKDW RI D
)60 EHVLGHV ZKLFK WKH )60 FRPSLOHU GHVFULEHG DERYH ZRXOG KDYH WR EH PRGLILHG WR NHHS LWV VWDWH
YDULDEOH RQ WKH VWDFN VLQFH RWKHUZLVH LW FRXOG QRW VXSSRUW UHFXUVLRQ 7KH UHVXOWLQJ SVHXGRFRGH
SURJUDP LV

: do_trace ( --)
$pop empty? IF EXIT THEN
1factor ( -- a) \ tail -> x$
star? IF REARRANGE* .m_ (. RECURSE ). RECURSE EXIT THEN
x$ empty$ $= IF EXIT THEN
b=red? IF EXIT THEN \ done?
star? IF REARRANGE** .m_ (. RECURSE ). RECURSE EXIT THEN
twins? IF x$ $push a.b (. RECURSE ). EXIT THEN
permute buf$ $push
perps? IF RECURSE EXIT THEN
x$ $push a.b (. RECURSE ). RECURSE
;

,PSOHPHQWLQJ WKH FRGH LV QRZ VWUDLJKWIRUZDUG VR ZH RPLW WKH GHWDLOV VXFK DV KRZ WR GHILQH perp
WR PDUN WKH V\PEROV DSSURSULDWHO\ 7KH VLPSOHVW PHWKRG LV D OLQNHG OLVW RU WDEOH RI VRPH VRUW WKDW LV
ILOOHG E\ PERP DQG FRQVXOWHG E\ WKH WHVW ZRUG perps?

H ow might we implement aleading factor of γ5? Whilethereis no difficulty in taking traces of


the form

7U (γ

… )
$ % & ' ≡ L 7U ( εµνκλ$ µ% ν& κγ λ ' … )  

H[SUHVVLRQV ZLWK γ EHWZHHQ ´VWDUUHGµ IDFWRUV DUH PRUH GLIILFXOW +RZHYHU WKH SHUPXWDWLRQ SURSHUWLHV


RI WUDFHV OHW XV ZULWH HJ

7U ( ($ + P$ ) (% + P% ) γ 
& (' + P
' ) ( … )


≡ 7U ( γ

( + ' ) … ( + $ ) ( + % ) ) 
& ' P ( $ P % P

VR WKH NH\ LVVXH EHFRPHV GHFRPSRVLQJ OHDGLQJ VWDUUHG IDFWRUV VDYLQJ WKH SLHFHV RQ WKH $-stack
XQWLO DW OHDVW WKUHH GLVWLQFW XQVWDUUHG IDFWRUV DUH DGMDFHQW RQ WKH OHIW 5HSODFH WKHVH E\ D VSHFLDO WRNHQ
" & 3_]`edUbQ\WURbQ

ZKLFK VWDQGV IRU ´^µ DV VKRZQ RQ SDJH  7KLV WRNHQ LV PDUNHG RUWKRJRQDO WR DOO WKUHH RI WKH YHFWRUV
LW UHSUHVHQWV DW WKH WLPH LW LV LQVHUWHG

7R DYRLG IXUWKHU H[WHQGLQJ do_trace SUREDEO\ WKH EHVW VFKHPH LV WR GHILQH D GLVWLQFW ZRUG Trg5(
Tr( WR SHUIRUP WKH DERYH SUHOLPLQDU\ VWHSV 7KHQ Trg5(
WKDW XVHV WKH FRPSRQHQWV RI ZLOO LQYRNH
do_trace WR GR WKH UHVW RI LWV ZRUN
7KH RQO\ RWKHU VLJQLILFDQW WDVNV DUH WR H[WHQG WKH RXWSXW URXWLQH WR

a) recognize the special “^” token; and

b) replace dot products like “ ^.d ” by [a,b,c,d].

T he program for all this is given in Appendix B.


@8IC%%! 3_]`edQdY_^Q\=UdX_Tc_V@XicYSc " '
3XQ`dUb!! Ci]R_\YS`b_WbQ]]Y^WQ^TS_]`edUbQ\WURbQ

# Ci]R_\YSTYVVUbU^dYQdY_^
$V RXU WKLUG H[DPSOH RI UXOHEDVHG SURJUDPPLQJ ZH FRQVLGHU FRPSXWLQJ WKH GHULYDWLYH RI D IXQFWLRQ
 Š
ZLWK UHVSHFW WR DQ LQGHSHQGHQW YDULDEOH 7KH VFUHHQ VQDSVKRW EHORZ  RI D ZLQGRZ LQ WKH 0DSOH
FRPSXWHU DOJHEUD V\VWHP LOOXVWUDWHV RQH FRPPRQ XVHU LQWHUIDFH IRU V\PEROLF GLIIHUHQWLDWLRQ RI D
IXQFWLRQ

6XSSRVH ZH GHILQH WKH XVHU LQWHUIDFH E\ WKH UXOH

D(f,x) -> Df = df/dx

7KHQ WKH UXOHV RI GLIIHUHQWLDWLRQ DUH

D(f & g,x) -> Df & Dg \ distributive rule (& = + or -)


D(f * g,x) -> Df * g + f * Dg \ product rule
D(f/g,x) -> Df / g - (f/g^2) * Dg \ quotient rule
D(f(g),x) -> D(f,g) * Dg \ chain rule
D(f^g,x) -> f^g * D(log(f) * g,x) \ exponent rule

D(c,x) -> 0 \ specific functions


D(x,x) -> 1
D(exp(x),x) -> exp(x)
D(log(x),x) -> x^(-1)
D(sin(x),x) -> cos(x)
D(cos(x),x) -> -sin(x)
etc.

 …LQFOXGLQJ FXUVRU DQG PRXVH SRLQWHU


" ( Ci]R_\YSTYVVUbU^dYQdY_^

7KXV WKH SURJUDP ZLOO HPSOR\ UHFXUVLRQ DQG PXVW EH DEOH WR UHFRJQL]H WKH IROORZLQJ HOHPHQWV

expression -> term & expression \ & = + or -


term -> factor % term \ % = * or /
factor -> constant \ does not depend on x
-> x
-> function \ does depend on x
-> factor ^ factor

function -> id ( expression )

:H VHH IURP WKH DERYH WKDW WKH GLIIHUHQWLDWLQJ IXQFWLRQ ZLOO VKDUH PDQ\ RI WKH HOHPHQWV RI D )25PXOD
75$1VODWRU 7KH SURJUDPPLQJ LV WKHUHIRUH IDLUO\ VWUDLJKWIRUZDUG XVLQJ LGHDV ZH KDYH DOUHDG\
HQFRXQWHUHG³SDWWHUQ UHFRJQLWLRQ DQG SDUVLQJ 7KH FRGH DSSHDUV LQ $SSHQGL[ ; RI WKLV ERRN

You might also like