APL/D Source Code: ──────────────────────────────────────────────────────────────────────────────── eval←exp.evalexp ⍝ eval is function evalexp in namespace exp. ──────────────────────────────────────────────────────────────────────────────── evalexp←{⎕ML←0 ⍝ Evaluate expression ⍵ with defs, fmt: ⍺. defs←0⍴⊂'' 0 ⍝ null definitions vector. ⍺←defs 0 ⍝ default: no defs, standard format. 0=≡⍺:defs ⍺ ∇ ⍵ ⍝ format only: default null defs. 3=|≡⍺:⍺ 0 ∇ ⍵ ⍝ defs only: default standard format. 0 3≡|≡¨⍺:(⌽⍺)∇ ⍵ ⍝ fmt defs: reverse. usage←'[defs] [fmt] eval expr' ⍝ usage message. emsg←'usage: ',usage ⍝ error message. 3 0≢|≡¨⍺:emsg ⎕SIGNAL 11 ⍝ bad left arg: signal domain. defs fmt←⍺ ⍝ definitions and format. 666::(↑⍬⍴⎕DM)⎕SIGNAL ⎕EN ⍝ pass back error. tree←parse ⍵ ⍝ parse to expression tree. expr←defs evaluate tree ⍝ evaluate simple tree nodes. rexp←reduce expr ⍝ reduce resulting expression tree. fmt show rexp ⍝ show numeric or character result. } ──────────────────────────────────────────────────────────────────────────────── until←{ ⍝ Loop until input matches ⍵ terminator. defs←0⍴⊂'' 0 ⍝ null definitions vector. ⍺←defs 0 ⍝ default: no defs, standard format. 0=≡⍺:defs ⍺ ∇ ⍵ ⍝ format only: default null defs. 3=|≡⍺:⍺ 0 ∇ ⍵ ⍝ defs only: default standard format. 0 3≡|≡¨⍺:(⌽⍺)∇ ⍵ ⍝ fmt defs: reverse. usage←'[defs] [fmt] until stop' ⍝ usage message. emsg←'usage: ',usage ⍝ error message. 3 0≢|≡¨⍺:emsg ⎕SIGNAL 11 ⍝ bad left arg: signal domain. ⍺ exp.{ ⍝ with exp: defn←{∧/(1=≡∘⊃¨⍵),,↑2=⍴¨⍵} ⍝ definition: x=... defs fmt←⍺ ⍝ split defs from format. defs{ ⍝ loop: nxt←⍞⊣⍞←4↑'' ⍝ next (commented) input line. src←(∧\nxt≠'⍝')/nxt ⍝ raw source. ⍵≡src~' ':defs←⍺ ⍝ terminator: return (shy) definitions. 0=⍴src~' ':⍺ ∇ ⍵ ⍝ blank line: ignore. 666::⍺ ∇ ⍵⊣⎕←↑⍬⍴⎕DM ⍝ error: display and continue. tree←parse src ⍝ parsed tree from source. expr←⍺ evaluate tree ⍝ evaluated parse tree, defn expr:expr ∇ ⍵ ⍝ defn: continue with extended envt. rexp←reduce expr ⍝ reduced expression. ⎕←fmt show rexp ⍝ show formatted result, ⍺ ∇ ⍵ ⍝ and try again, }⍵ ⍝ until stop. }⍵~' ' ⍝ :endwith exp. } ──────────────────────────────────────────────────────────────────────────────── load←{⎕IO ⎕ML←0 ⍝ Install defns and rules for src ⍵. prep←{ ⍝ prepare char vectors source. rmcm←{(∧\⍵≠'⍝')/⍵} ⍝ remove comment. rmwt←{(~⍵∧.=¨' ')/⍵} ⍝ remove white lines. sepr←{('⋄'=⍵)∧0=-⌿+\'()'∘.=⍵} ⍝ outer-level diamond. diam←{1↓¨(sepr ⍵)⊂⍵}∘{'⋄',⍵}¨ ⍝ split diamondised lines. ↑,/diam rmwt rmcm¨↓⎕FMT↑⍵ ⍝ clean up source vector. } comp←{ ⍝ compile function definitions. sepr←{↑¨,/¨↓⍉↑(⍳⍴⍵)join¨⍵} ⍝ separate. join←{↓⍉↑⍺,¨↑,¨/⍵} ⍝ join fields. tupl←{{1↓¯1↓⍵}\(1,1↓<\⍵='(')⊂⍵} ⍝ asc-apl pair. macro←{ ⍝ convert macro body to dfn. name body←⍵ ⍝ macro name and body. ~'→'∊body:⍵ ⍝ raw apl function: done. masks←0 1=⊂∨\body='→' ⍝ masks to split args from code. args code←0 1↓¨masks/¨⊂body ⍝ macro args and code. sig←'0::⎕signal ⎕en ⋄ ' ⍝ catchall to pass back error. tag←args,' _←⍵,0 ⋄ ' ⍝ argument vector item naming. dfn←'{',sig,tag,code,'}' ⍝ extended dfn. name dfn ⍝ macro assoc and defn. } split←{(1,1↓(top ⍵)∧⍵∊' ')⊂⍵} ⍝ split between definition segments. pair←{ ⍝ assocs, then token vectors. ascs←('←→'⍳⊃⍵)⊃'←→↑' ⍝ association character. defs←split(ascs∊'←→')↓⍵ ⍝ following function definitions, ascs(defs~⊂,' ') ⍝ association code followed by defs. } ⍝ for each function definition line. segs←rlbs¨\¨⌽pair¨⍵ ⍝ defn segments strongest first. sepr macro¨\¨tupl¨\¨segs ⍝ (strength assoc asc apl) } rlbs←{(∨\⍵≠' ')/⍵} ⍝ remove leading blanks. top←{{⍵∨¯1⌽⍵}0=-⌿+\'()'∘.=⍵} ⍝ top level chars (not in parens). infix←{(⊃⍵)∊'←→'} ⍝ infix function line? prefix←{~1∊'=≡'∊(top ⍵)/⍵} ⍝ monadic function line? fndef←{(prefix ⍵)∨infix ⍵} ⍝ function definition line? type←{2⌊(fndef ⍵)+2×1∊'::'⍷⍵} ⍝ 0: redn, 1:fndef, 2: patn var. lines←rlbs¨prep ⍵ ⍝ left aligned definition lines. masks←0 1 2=⊂type¨lines ⍝ type of each line. rsrc fsrc psrc←masks/¨⊂lines ⍝ separate source lines. exp.defns←comp fsrc ⍝ function definition library. exp.(pvars pchks)←aux.pcomp psrc ⍝ pattern vars and predicates. exp.rules←1↓{ ⍝ reduction rules library. 666::(⍵,(⊃⌽⎕TC),⊃⎕DM)⎕SIGNAL 666 ⍝ bad line: display and exit. exp.(strip parse ⍵) ⍝ parse script source line. }¨'0',rsrc ⍝ for each source line. 1:rslt←exp.(defns rules pvars pchks) ⍝ shy rslt. } ──────────────────────────────────────────────────────────────────────────────── parse←{⎕IO ⎕ML←0 ⍝ Infix expression parser. lex←{ ⍝ tokens vector from source. cons←{⍵[⍒↑⍴¨⍵]}⍺,lp rp sp ⍝ constants, longest first. hits←cons⍷¨⊂⍵ ⍝ masks of constant positions. mask←<⍀↑cons{↑∨/(-⍳⍴⍺)⌽¨⊂⍵}¨hits ⍝ matrix mask of all constants. part←{⍺{⍵∨(-⍺)⌽⍵}(⍺⍴1)⍷⍵} ⍝ partition vector from mask. toks←(1,1↓↑∨⌿(⍴¨cons)part¨↓mask)⊂⍵ ⍝ token vector. pvec←¯1++\⊃∘⍴¨toks ⍝ vector of token positions. (,∘1~toks∊⊂,' ')/↓⍉↑(toks,o)(pvec,⍴⍵) ⍝ (token position) pairs. } tree←{ ⍝ generate parse tree. cls dep acc stk←⍺ ⍝ parse state. (tok pos)toks←⍵ ⍝ next token and remainder. tok≡o:(⍺ pos flush dep)toks ⍝ no more tokens: finished. tok≡rp:((⍺ pos flush 0⌊dep-1)o)toks ⍝ ')': flush remaining fns. chk←{↑{⍺ ⍵}/(2×cls=a)1/(i pos)⍵} ⍝ inject error if case 2(3). tok≡lp:⍺ ∇ i(dep+1)o o ∇ chk toks ⍝ '(': sub-expr and remainder. (⊂tok)∊fns:tok ∇{ ⍝ function: bind or stack. bs ad←(cls=a)props ⍺ pos ⍝ bind strength and assoc dirn. ∆stk←bs ad(⍺ pos)stk ⍝ push function on stack. ∆acc←(cls∊f i)⊃acc(o acc) ⍝ monadic fn: push dummy argt. (f dep,∆acc popfns ∆stk)⍺⍺ ⍵ ⍝ pop and bind stronger fns. }toks cls=a:pos error'missing operator' ⍝ adjacent operands: error. a dep(tok acc)stk ∇ toks ⍝ argument: accumulate. } popfns←{ ⍝ pop 'n bind stronger fns. b1 a1 f1(b2 a2 f2 stk)←⍵ ⍝ pop top two functions, b1 a1{ ⍝ top fn stronger? ⍵≡o o:1 ⍝ lower fn null: yes. ⍺≡⍵:(⊃⌽⍺)∊'→↑' ⍝ same: depends on assoc. >/⊃¨⍺ ⍵ ⍝ compare binding strengths. }b2 a2:⍺ ⍵ ⍝ top stronger: continue. rgt(lft acc)←⍺ ⍝ left and right args from acc. (lft f2 rgt)acc ∇ b1 a1 f1 stk ⍝ bind top fn and try again. } props←{ ⍝ function properties. tok pos←⍵ ⍝ token and position. mask←ascs∊⍺⊃'↑' '←→' ⍝ valency mask. fs bs as←mask∘/¨fns strs ascs ⍝ fns, bind-strengths, assocs. (⊂tok)∊fs:(fs⍳⊂tok)⊃¨bs as ⍝ bind-strength and assoc dirn. pos error'missing operand' ⍝ bad valency: error. } flush←{ ⍝ no more tokens: finished. (cls dep acc stk)pos←⍺ ⍝ parse state. cls=f:pos error'missing operand' ⍝ final argument missing: error. cls=i:pos error'null expression' ⍝ null expression (): error. 0=⍵:⊃⊃acc popfns ¯1 o o stk ⍝ ok: flush stack with weak fn. emsg←(1+×⍵)⊃'unexpected' '' 'missing' ⍝ appropriate message. pos error emsg,' ',(|⍵)/')' ⍝ mis-matched parens. } error←{⎕SIGNAL∘666,∘⍵,⍺ 1 1/' \ '} ⍝ error function. strs ascs fns _←defns ⍝ strengths, assocs, functions. i a f o lp rp sp←'·⍵∇∘',,¨'() ' ⍝ parse state constants. ⊃i 0 o o tree↑{⍺ ⍵}/(fns lex,⍵),o ⍝ parse token stack. } ──────────────────────────────────────────────────────────────────────────────── evaluate←{⎕ML←0 ⍝ Evaluate expr ⍵ in envt ⍺. trav←{ ⍝ traverse tree evaluating: env top←⍺ ⍝ environment and top level ','. '∘'≡⍵:⍵ ⍝ dummy left argt. 0=≡⍵:⍵ ⍝ number. 1=≡⍵:env{ ⍝ atom: numc ⍵:⍎⍵ ⍝ number: evaluate. tags vals←↓⍉↑⌽⍺ ⍝ name: split environment. (tags⍳⊂⍵)⊃vals,⊂⍵ ⍝ look up name in environment. }⍵ lft(fn fp)rgt←⍵ ⍝ split expression. fn≡,',':⍺ ∇{ ⍝ "where" or arg list. ~top:⍺ ⍺⍺ vector ⍵ ⍝ string out vector argument. (⍺ ⍺⍺ rgt)top ⍺⍺ redexp lft ⍝ top level: eval larg in envt rarg. }⍵ fn≡,'=':env,⊂lft(⍺ ∇ rgt) ⍝ defn: return extended envt. larg rarg←(env 0)∘∇¨lft rgt ⍝ evaluate left and right args. newx←larg(fn fp)rarg ⍝ partially evaluated expr. 0∊numb¨larg rarg~'∘':newx ⍝ non-number: can't evaluate. aplsrc←(asc⍳⊂,fn)⊃apl ⍝ apl equivalent function. aplsrc≡'':newx ⍝ no apl equivalent: can't evaluate. 0::fp error'bad operator' ⍝ value error: bad function. aplfn←⍎aplsrc ⍝ apl function. 0::fp error'bad operand' ⍝ catchall: bad operand. 5::fp error'wrong number of args' ⍝ length error from lib fn. larg≡'∘':aplfn rarg ⍝ execute monadic expression. larg aplfn rarg ⍝ execute dyadic expression, } redexp←{ ⍝ reduce exp to left of ','. lft(fn fp)rgt←⍵ ⍝ extract fn. (⊂fn)∊,¨',=':⍵ ⍝ another "where" to left: ignore. reduce ⍵ ⍝ otherwise: reduce principal exp. } vector←{ ⍝ vector of args from (,··) list. 1=≡,⍵:⍺ ⍺⍺ ⍵ ⍝ atom: done. larg(fn fp)rarg←⍵ ⍝ split expression. ~fn≡,',':fp error'syntax error' ⍝ e.g.: foo(x, x=2) ↑,/⍺∘⍺⍺¨larg rarg ⍝ join evaluated arguments. } 666::(⊃⎕DM)⎕SIGNAL ⎕EN ⍝ pass back error. error←{(⍺ emsg ⍵)⎕SIGNAL 666} ⍝ error function. emsg←{(pmsg ⍺),⍵} ⍝ positioned error message. pmsg←{(⍵≥0)/⍵ 1 1/' \ '} ⍝ positioned error marker. numc←{(,1)≡⊃⎕VFI ⍵} ⍝ is character rep of number? numb←{∧/0≡¨⊃0⍴⊂⍵} ⍝ numeric scalar or vector? _ _ asc apl←defns ⍝ ascii and apl functions. ⍺←'' ⍝ default null environment, top. ⍺ 1 trav ⍵ ⍝ evaluated expression and flib } ──────────────────────────────────────────────────────────────────────────────── reduce←{⎕IO ⎕ML←0 ⍝ Reduce expression tree. trav←{ ⍝ traverse expr, applying rules. 1=≡,⍵:⍵ ⍝ atom: done. 2=⍴⍵:⍵ ⍝ fun pos:done. expr←⍺∘∇¨⍵ ⍝ simplify sub-expressions. hits←⍺ expr dups ⍺ find expr ⍝ rules that apply at this level. ~1∊hits:''evaluate expr ⍝ none: continue. fm tc to←(hits⍳1)⊃rules ⍝ select applicable rule. simp←fm to repl expr ⍝ simplified expression. tc='=':⍺ ∇''evaluate simp ⍝ try again with simpler expr. join←{↑⍺{⍺,⍺⍺,⍵}/⍵} ⍝ ⍺-join of segments. rfmt←' → 'join show¨fm to ⍝ formatted rule. prev next←show¨expr simp ⍝ previous and next expression. segs←prev(rfmt join'[]')next ⍝ trace segments. tabs←(0=⎕SI⍳⎕SI)/'·' ⍝ trace ident. ⎕←tabs,' 'join segs ⍝ traced reduction. ⍺ ∇''evaluate simp ⍝ try again. } ⍝ expr ← patn :: expr find←{ ⍝ mask of pattern matches. vars←⍺ match ⍵ ⍝ pattern variable matches. 1=≡,⍵:vars∨⍺∊⊂⍕⍵ ⍝ leaf: match larg(fn fp)rarg←⍵ ⍝ expr: split. pfns←⊃⌽2↑↓⍉↑⍺ ⍝ pattern functions. mask←(pfns∊⊂fn)∨pfns match fn ⍝ possible matching patterns. ~1∊mask:vars ⍝ no hits: xvars match expressions. subs←↓⍉↑mask/⍺ ⍝ matching sub-patterns. hits←↑∧/subs ∇¨larg fn rarg ⍝ subexpression matches. vars∨mask\hits ⍝ matches including expr vars. } ⍝ hits ← patns :: expr match←{ ⍝ pattern variable matches. amsk←(⍺∊pvars)∧~⍵≡'∘' ⍝ pattern variables. ~1∊amsk:amsk ⍝ none: done. vars←pvars∩amsk/⍺ ⍝ unique pattern vars. vals←⍎¨(pvars⍳vars)⊃¨⊂pchks ⍝ corresp. check results. amsk\(vars⍳amsk/⍺)⊃¨⊂vals ⍝ check result per pattern var. } ⍝ hits ← patns :: expr dups←{ ⍝ check pattern with duplicate vars. ~1∊⍵:⍵ ⍝ no hits: finished. pats expr←⍺ ⍝ patterns and subject expression. ⍵\{ ⍝ check each hit: fms tos←↓⍉↑⍵ dict expr ⍝ vars and vals. masks←↓(∪fms)∘.≡fms ⍝ selection mask per unique var. tovals←masks/¨⊂strip¨tos ⍝ values per unique var. 1∧.≥⊃∘⍴∘∪¨tovals ⍝ ok if unique vals per var. }¨⍵/pats ⍝ on each selected patterns. } ⍝ hits ← expr :: hits repl←{ ⍝ ⍺-transform expression ⍵. fm to←⍺ ⍝ from and to patterns. fms tos←↓⍉↑fm dict ⍵ ⍝ make substitution dictionary. 0{ ⍝ substitute from dictionary. 1≠≡,⍵:0 1 0 ∇¨⍵ ⍝ expr: substitute sub-expressions. (fms⍳⊂⍵)⊃tos,⊂⍺⊃⍵(⍵ ¯1) ⍝ leaf: substitute from dictionary. }to ⍝ using "to" pattern. } ⍝ expr ← (fm to) :: expr dict←{ ⍝ dictionary from pattern. 1=≡,⍺:⊂⍺ ⍵ ⍝ leaf: (fm to) pair ↑,/⍺ ∇¨⍵ ⍝ expr: collected sub-expr pairs. } (⊃¨rules)trav ⍵ ⍝ patterns to reduce expression. } ──────────────────────────────────────────────────────────────────────────────── show←{⎕IO ⎕ML←0 ⍝ Show expression tree. 0≡⊃0⍴⊂⍵:⍵ ⍝ raw number: finished. 1=≡,⍵:⍵ ⍝ simple: finished. 2∧.=↑⍴¨⍵:⍵ ⍝ defs: finished. sfmt←0∘{ ⍝ standard format. '∘'≡⍵:'' ⍝ null: ignore. lp rp←⍺/¨'()' ⍝ outer parens. 1=≡,⍵:lp,(⍕⍵),rp ⍝ simple: format. 2=⍴⍵:⍺ ∇⊃⍵ ⍝ fn pos: format fn. lft fn rgt←⍵ ⍝ split expression. func←{(1=≡,⍵)⊃(,⊃1↓⍵)''} ⍝ expr's function, or ''. prop←{(fns⍳⊂func ⍵)⊃⍺,⍴⍺} ⍝ fn's ⍺-property. ls os rs←strs∘prop¨lft ⍵ rgt ⍝ binding strengths, as←ascs∘prop¨lft rgt ⍝ association orders. pars←(ls rs<os)∨(ls rs=os)∧as='→←' ⍝ sub-parens needed. over←1,~'∘'≡⊃rgt ⍝ monadic right expr override. name←0,(lft≡'∘')∧1<⍴fn ⍝ monadic "named" fn needs pars. lv rv←(over∧pars∨name)∇¨lft rgt ⍝ format left and right subs. lp,lv,fn,rv,rp ⍝ linear format of expression. } pfmt←{ ⍝ fully parenthesised linear. '∘'≡⍵:⍵ ⍝ null: ignore. 0=≡⍵:⍕⍵ ⍝ number: format. 1=≡⍵:⍵ ⍝ atom: done lft fn rgt←strip ⍵ ⍝ split expression. lft≡'∘':'(',fn,(∇ rgt),')' ⍝ monadic function: '(',(∇ lft),fn,(∇ rgt),')' ⍝ parenthesised expression. } tfmt←{ ⍝ tree format. '∘'≡⍵:0 0⍴'' ⍝ null: ignore. 0=≡⍵:↑,↓,⍕⍵ ⍝ number: format. 1=≡⍵:↑,↓⍵ ⍝ atom: done. lft fn rgt←strip ⍵ ⍝ split expr. subs←{' ',⍵}\∇¨lft rgt ⍝ format subtrees. tops←<\¨' '≠{⌽⍵}\⊃∘↓¨subs ⍝ connection points line←{(⍵++\⍵)⊃¨⊂' ─',⍺} ⍝ line drawing chars. tee←('∘'≡⊃⍵)⊃'┴└' ⍝ dyadic/monadic tee piece. decr←{tee,1↓⌽⍵}\'┌┐'line¨tops ⍝ top decoration. subm←↑,/↑¨↓↑↓¨decr⍪¨subs ⍝ formatted sub-matrix. tabs←(⍴⊃tops)/' ' ⍝ function alignment. ↑(⊂tabs,fn),↓subm ⍝ formatted expr tree. } strs ascs fns _←defns ⍝ strengths, assocs, functions. ⍺←0 ⍝ default: standard format. ⍺∊'s' 0:sfmt strip ⍵ ⍝ standard format. ⍺∊'p' 1:pfmt strip ⍵ ⍝ fully parenthesised. ⍺∊'t' 2:tfmt strip ⍵ ⍝ tree format. } ──────────────────────────────────────────────────────────────────────────────── test←{ ⍝ Check test cases. ⍺←0 ⋄ progress←⍺∘{⍺:{0}⎕←⍵ ⋄ 0} ⍝ ⍺: show progress. ⍵≡'':⍺∘∇∘⍎¨↓⎕NL 2 ⍝ '' => all scripts. (⊂⍵)∊~∘' '¨↓⎕NL 2:⍺ ∇⍎⍵ ⍝ test'script' → test script. ~(⊂⍵)∊⍎¨↓⎕NL 2:⍵,'?' ⍝ bad script name. progress⊃↓⎕FMT ⍵: ⍝ show first line of script. match←{z←eval ⍺ ⋄ z is ⍵:1 ⋄ ⍺ show z} ⍝ display unexpected result. error←{666::chkerr ⍵ ⋄ {0}⎕←eval ⍺} ⍝ confirm expected errors. chkerr←{⍵≡trimerr⊃⎕DM:1 ⋄ {0}⎕←⊃⎕DM} ⍝ check expected error matches. trimerr←{(2++/∧\⍵≠'\')↓⍵} ⍝ trim posn info from error msg. trim←{(+/∧\' '=⍵)↓⍵}{⌽⍺⍺⌽⍺⍺ ⍵} ⍝ trim leading & trailing blanks show←{{0}⎕←⍺,' -> ',⍵} ⍝ display erroneous result. split←{trim¨0 2↓¨(1,1↓⍺⍷⍵)⊂⍵} ⍝ expr and expected result. is←{⍺≡⍵:1 ⋄ 0≠⊃0⍴⍺:0 ⋄ ⍺≡⍎⍵} ⍝ match expr or number. save←exp.(defns rules pvars pchks) ⍝ save current rules. _←load ⍵ ⍝ install rules. oks←{ ⍝ ok vector. progress ⍵: ⍝ optionally, show progress. 1∊'->'⍷⍵:↑match/'->'split ⍵ ⍝ expect match. 1∊'!!'⍷⍵:↑error/'!!'split ⍵ ⍝ expect error. }¨{ ⍝ test script: cmat←⎕FMT↑⍵ ⍝ char matrix script. comm←'⍝'=⊃¨~∘' '¨↓cmat ⍝ lines starting with '⍝' test←∨/↑∨/'->' '!!'⍷¨⊂cmat ⍝ test lines. dlc←{(⍵⍳'⍝')↓⍵} ⍝ drop leading '⍝' char. dtc←{(∧\⍵≠'⍝')/⍵} ⍝ drop trailing comment. dtc∘dlc¨(comm∧test)/↓cmat ⍝ test vector. }⍵ ⍝ for given rule-set. exp.(defns rules pvars pchks)←save ⍝ restore prevailing rules. 1:rslt←oks ⍝ shy result vector. } ──────────────────────────────────────────────────────────────────────────────── Back to: Contents