Getting CoSy with APL and K --------------------------- October 26, 2024 Why this talk? -------------- ⍟ APL is one of the handful of "big idea" languages ⍟ Realization a lot of Bob Armstrong's talks confuse SVFIG sometimes due to lack of APL + K familiarity ⍟ Desire to bridge the gap - Relate Forth and CoSy/APL/K ideas ⍟ To better understand status of CoSy What is APL? ------------ ⍟ Created by Ken Iverson, later won a Turing award for it ⍟ Started as a blackboard notation ⍟ Retroactively dubbed "A Programming Language" ⍟ Motivated by the desire to express programs at a high level ⍟ Inspiration for Matlab, R, and NumPy What does it look like? ----------------------- ⍟ Denser than Forth! ⍟ Special character set ⍟ Infix notation (but not regular order of operations) ⍟ Potentially very write only ⍟ The game of life in APL: life ← {⊃1 ⍵ ∨.∧ 3 4 = +/ +⌿ ¯1 0 1 ∘.⊖ ¯1 0 1 ⌽¨ ⊂⍵} CO-DFNS SOURCE by Aaron W. Hsu ⍝ A B E F G L M N O P V Z ⍝ 0 1 2 3 4 5 6 7 8 9 10 11 tt←{⍞←'C' ⋄ ((d t k n)exp sym)←⍵ ⋄ I←{(⊂⍵)⌷⍺} r←I@{t[⍵]≠3}⍣≡⍨p⊣2{p[⍵]←⍺[⍺⍸⍵]}⌿⊢∘⊂⌸d⊣p←⍳≢d ⍝ PV p,←n[i]←(≢p)+⍳≢i←⍸(t=3)∧p≠⍳≢p ⋄ t k n r,←3 1 0(r[i])⍴⍨¨≢i ⍝ LF p r I⍨←⊂n[i]@i⊢⍳≢p ⋄ t k(⊣@i⍨)←10 1 i←(⍸(~t∊3 4)∧t[p]=3),{⍵⌿⍨2|⍳≢⍵}⍸t[p]=4 ⋄ p t k n r⌿⍨←⊂m←2@i⊢1⍴⍨≢p ⍝ WX p r i I⍨←⊂j←(+⍀m)-1 ⋄ n←j I@(0≤⊢)n ⋄ p[i]←j←i-1 k[j]←-(k[r[j]]=0)∨0@({⊃⌽⍵}⌸p[j])⊢t[j]=1 ⋄ t[j]←2 p[i]←p[x←p[i←{⍵⌿⍨~2|⍳≢⍵}⍸t[p]=4]] ⋄ t[i,x]←t[x,i] ⋄ k[i,x]←k[x,i] ⍝ LG n[x]←n[i] ⋄ p←((x,i)@(i,x)⊢⍳≢p)[p] n[p⌿⍨(t[p]=2)∧k[p]=3]+←1 ⍝ CI p[i]←p[x←p I@{~t[p[⍵]]∊3 4}⍣≡i←⍸t∊4,(⍳3),8+⍳3] ⋄ j←(⌽i)[⍋⌽x] ⍝ LX p t k n r{⍺[⍵]@i⊢⍺}←⊂j ⋄ p←(i@j⊢⍳≢p)[p] s←¯1,⍨∊⍳¨n[∪x]←⊢∘≢⌸x←0⌷⍉e←∪I∘⍋⍨rn←r[b],⍪n[b←⍸t=1] ⍝ SL d←(≢p)↑d ⋄ d[i←⍸t=3]←0 ⋄ _←{z⊣d[i]+←⍵≠z←r[⍵]}⍣≡i ⋄ f←d[0⌷⍉e],¯1 ⍝ FR xn←n⌿⍨(t=1)∧k[r]=0 ⍝ XN v←⍸(t=10)∧n<¯4 ⋄ x←n[y←v,b] ⋄ n[b]←s[e⍳rn] ⋄ i←(≢x)⍴c←≢e ⍝ AV _←{z/⍨c=i[1⌷z]←e⍳⍉x I@1⊢z←r I@0⊢⍵}⍣≡(v,r[b])⍪⍉⍪⍳≢x f s←(f s I¨⊂i)⊣@y¨⊂¯1⍴⍨≢r ⋄ p t k n f s r d xn sym} https://gwern.net/doc/cs/algorithm/2019-hsu-3.pdf History ------- ⍟ Started at Harvard in 1957 ⍟ Moved to IBM in 1960 - Multi-user APL\360 ⍟ Appealed to the finance, insurance, and AI communities ⍟ Filled a hole eventually subsumed by spreadsheets and Matlab, etc. ⍟ Used instead of BASIC in two microcomputers: - MCM/70 - Intel 8008 2-8K RAM, 32K ROM (1974) https://blazorcanvas20210704221924.azurewebsites.net/mcmpoc - VideoBrain APL/S - F8 1KB RAM (1977) ⍟ Praised by John Backus in his famous Turing lecture: Can programming be liberated from the von Neumann style? "We owe a great debt to Kenneth Iverson for showing us that there are programs that are neither word-at-a-time nor dependent on lambda expressions" That Character Set ------------------ ⍟ Intended as a substitute for the rich symbol set used in mathematics ⍟ 31 characters not in ASCII ⍟ Combined with Selectric over-strike - Character, backspace, character ┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬─────────┐ │ │ ¨ │ ¯ │ < │ ≤ │ = │ ≥ │ > │ ≠ │ ∨ │ ∧ │ - │ ÷ │ BACK │ │ │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ 0 │ + │ × │ SPACE │ │ └──┬─┴──┬─┴──┬─┴──┬─┴──┬─┴──┬─┴──┬─┴──┬─┴──┬─┴──┬─┴──┬─┴──┬┬┴─────────┤ │ TAB │ ? │ ⍵ │ ∊ │ ⍴ │ ~ │ ↑ │ ↓ │ ⍳ │ ○ │ * │ → ││ │ │ │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │ ← ││ │ ├───────┴┬───┴┬───┴┬───┴┬───┴┬───┴┬───┴┬───┴┬───┴┬───┴┬───┴┬───┴┤ RETURN │ │ LOCK │ ⍺ │ ⌈ │ ⌊ │ _ │ ∇ │ ∆ │ ∘ │ ' │ ⎕ │ ( │ ) │ │ │ │ A │ S │ D │ F │ G │ H │ J │ K │ L │ [ │ ] │ │ ├────────┴──┬─┴──┬─┴──┬─┴──┬─┴──┬─┴──┬─┴──┬─┴──┬─┴──┬─┴──┬─┴──┬─┴──────────┤ │ SHIFT │ ⊂ │ ⊃ │ ∩ │ ∪ │ ⊥ │ ⊤ │ | │ ; │ : │ \ │ SHIFT │ │ │ Z │ X │ C │ V │ B │ N │ M │ , │ . │ / │ │ └───────────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────┴────────────┘ Overstrike ---------- ○ + * = ⍟ ∩ + ∘ = ⍝ / + - = ⌿ ∆ + | = ⍋ ÷ + ⎕ = ⌹ \ + ○ = ⍉ Large Symbol Set ---------------- +-×÷⌈⌊*⍟|!○~∨∧⍱⍲<≤=≥>≠.⋔⍦∵ ⍴,⍪⍳↑↓?⍒⍋⍉⌽⊖∊⊥⊤⍎⍕⌹⊂⊃∪∩⍷⌷∘⍑ →←⎕⍞/⌿\⍀¨⍣⍨⊆⍥⍠⍤⌸⍸()[];⍝±∓⍊ :⍬∇⍺⍵⍶⍹ᐵᑈ⍡⍁⌾⍢⍫⍛⍧⊇⍮⍭⍇⍈⍐⍗=⍅⍆ ABCDEFGHIJKLMNOPQRSTUVWXYZ ⒶⒷⒸⒹⒺⒻⒼⒽⒾⒿⓀⓁⓂⓃⓄⓅⓆⓇⓈⓉⓊⓋⓌⓍⓎⓏ ⌻⌼⍁⍂⍃⍄⍌⍍⍓⍔⍯⍰⍏⍖⍘' Monadic Dyadic ------- ------ + Conjugate Add - Negation Subtract × Signum Multiply ÷ Reciprocal Divide Monadic Dyadic ------- ------ < Less ≤ Not greater = Equal ≥ Not less > Greater ≠ Not equal Monadic Dyadic ------- ------ ~ Not ∧ And ∨ Or ⍲ Nand ⍱ Nor Monadic Dyadic ------- ------ ⌊ Floor Minimum ⌈ Ceiling Maximum | Magnitude Residue * Exponential Exponentiation ⍟ Nat Log Logarithm ○ Pi times Trigonomy ! Factorial Binomial ? Roll Deal Circlular Operator ○ -------------------- 0○x = sqrt(1-x^2) ¯1○x = arcsin x 1○x = sin x ¯2○x = arccos x 2○x = cos x ¯3○x = arctan x 3○x = tan x ¯4○x = sqrt(x*2-1) 4○x = sqrt(1+x^2) ¯5○x = arcsinh x 5○x = sinh x ¯6○x = arccosh x 6○x = cosh x ¯7○x = arctanh x 7○x = tanh x Monadic Dyadic ------- ------ ⍳ Index Index of ⍴ Size Reshape , Ravel Catenate [] Indexing ↑ Take ↓ Drop Monadic Dyadic ------- ------ ⍋ Ascending ⍒ Descending / Compress ⌽ Reverse L Rotate L ⊖ Reverse F Rotate F ⍉ Transpose Monadic Dyadic ------- ------ ∊ Membership ⊥ Decode ⊤ Encode ⌹ Mat Inverse -------- [] Axis Operators --------- F/ Reduce (last axis) F⌿ Reduce (first axis) F\ Scan (last axis) F⍀ Scan (first axis) ∘.F Outer Product F.G Inner Product No order of operations, binds right: 2×3+5 = 2×(3+5) = 16 (not 11) 2+3×5 = 2+(3×5) = 17 Notation as a Tool of Thought ----------------------------- Important Characteristics of Notation: ⍟ Ease of expressing constructs arising in problems ⍟ Suggestivity ⍟ Ability to subordinate detail ⍟ Economy ⍟ Amenability to formal proofs Ease of expressing constructs arising in problems ⍳5 1 2 3 4 5 +\⍳5 1 3 6 10 15 ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ 3 4 ⍴ 5 5 5 5 5 5 5 5 5 5 5 5 5 Suggestivity 2×3 ←→ 6 2*3 ←→ 8 +/M⍴N ←→ N×M ×/M⍴N ←→ N*M +\M⍴N ←→ N×⍳M ×\M⍴N ←→ N*⍳M Ability to subordinate detail COLUMNS ← 64 ROWS ← 16 BYTES ← COLUMNS × ROWS ⍳5 1 2 3 4 5 ⌽ 1 7 7 6 6 7 7 1 1 2 3 , 4 5 6 1 2 3 4 5 6 (⍳5),(⌽⍳5) 1 2 3 4 5 5 4 3 2 1 Economy ------- ⍟ Large number of ideas in a small vocabulary ⍟ All operators alike, no rules of precedence Amenability to formal proofs LEMMA ----- ⎕ ⎕⎕⎕⎕⎕ ⎕⎕ ⎕⎕⎕⎕ ⎕⎕⎕ ⎕⎕⎕ ⎕⎕⎕⎕ ⎕⎕ ⎕⎕⎕⎕⎕ ⎕ 1 2 3 4 5 + 5 4 3 2 1 ←→ 6 6 6 6 6 (⍳N)+(⌽⍳N) ←→ N⍴(N+1) Gauss's Formula --------------- +/⍳N ⍝ + is associative ⍝ and commutative +/⌽⍳N ⍝ (X + X) ÷ 2 ←→ X ((+/⍳N) + (+/⌽⍳N)) ÷ 2 ⍝ + is associative ⍝ and commutative (+/((⍳N) + (⌽⍳N))) ÷ 2 ⍝ by Lemma (+/(N⍴(N+1))) ÷ 2 ⍝ definition of ⍝ multiplication ((N+1) × N) ÷ 2 tradfns ------- ∇ C←A PYTHAGOREAN B ⍝ Compute Pythagorean Theorem C←((A*2)+(B*2))*÷2 ∇ 3 PYTHAGOREAN 4 5 tradfns (locals) ---------------- ∇ C←A PYTHAGOREAN B;T;R ⍝ Compute Pythagorean Theorem T←A*2 R←B*2 C←(T+R)*÷2 ∇ dfns ---- ⍝ Compute Pythagorean Theorem pythagorean←{((⍺*2)+(⍵*2))*÷2} dfns ---- ⍝ Compute Factorial fact←{0=⍵:1 ⍵×∇⍵-1} ∇ D←F9 E;F;I;K F←(,(E='⍵')∘.≠5↑1)/,E,(⌽4,⍴E)⍴' Y9 ' F←(,(F='⍺')∘.≠5↑1)/,F,(⌽4,⍴F)⍴' X9 ' F←1↓⍴D←(0,+/¯6,I)↓(-(3×I)++\I←':'=F)⌽F,(⌽6,⍴F)⍴'' D←3⌽C9[1+(1+'⍺'∊E),I,0;],⍉D[;1,(I←2↓⍳F),2] K←K+2×K<1⌽K←I∧K∊(>⌿1 0⌽'←⎕'∘.=E)/K←+\~I←E∊A9 F←(0,1+⍴E)⌈⍴D←D,(F,⍴E)↑⍉0 ¯2↓K⌽' ',E,[1.5]';' D←(F↑D),[1]F[2] '⍝',E ∇ A9 C9 -- -- 012345678 FIX Z9← 9ABCDEFGH --- Y9Z9← IJKLMNOPQ 0⍴⎕FX F9 ⍞ Y9Z9←X9 RSTUVWXYZ )/3→(0=1+, ⒶⒷⒸⒹⒺⒻⒼⒽⒾ →0,0⍴Z9← ⒿⓀⓁⓂⓃⓄⓅⓆⓇ ⓈⓉⓊⓋⓌⓍⓎⓏ⎕ Children of APL - J ------------------- ⍟ Iverson and Robert Hui (1990s) ⍟ ASCII to address concern ⍟ Focus on tacit point free style ⍟ Values and operators become nouns, verbs, and adverbs ⍟ Arthur Whitney's famously terse implementation Incunabulum - An Implementation of J https://www.jsoftware.com/ioj/iojATW.htm typedef char C;typedef long I; typedef struct a{I t,r,d[3],p[2];}*A; #define P printf #define R return #define V1(f) A f(w)A w; #define V2(f) A f(a,w)A a,w; #define DO(n,x) {I i=0,_n=(n);for(;i<_n;++i){x;}} I *ma(n){R(I*)malloc(n*4);}mv(d,s,n)I *d,*s;{DO(n,d[i]=s[i]);} tr(r,d)I *d;{I z=1;DO(r,z=z*d[i]);R z;} A ga(t,r,d)I *d;{A z=(A)ma(5+tr(r,d));z->t=t,z->r=r,mv(z->d,d,r); R z;} V1(iota){I n=*w->p;A z=ga(0,1,&n);DO(n,z->p[i]=i);R z;} V2(plus){I r=w->r,*d=w->d,n=tr(r,d);A z=ga(0,r,d); DO(n,z->p[i]=a->p[i]+w->p[i]);R z;} V2(from){I r=w->r-1,*d=w->d+1,n=tr(r,d); A z=ga(w->t,r,d);mv(z->p,w->p+(n**a->p),n);R z;} V1(box){A z=ga(1,0,0);*z->p=(I)w;R z;} V2(cat){I an=tr(a->r,a->d),wn=tr(w->r,w->d),n=an+wn; A z=ga(w->t,1,&n);mv(z->p,a->p,an);mv(z->p+an,w->p,wn);R z;} V2(find){} V2(rsh){I r=a->r?*a->d:1,n=tr(r,a->p),wn=tr(w->r,w->d); A z=ga(w->t,r,a->p);mv(z->p,w->p,wn=n>wn?wn:n); if(n-=wn)mv(z->p+wn,z->p,n);R z;} V1(sha){A z=ga(0,1,&w->r);mv(z->p,w->d,w->r);R z;} V1(id){R w;}V1(size){A z=ga(0,0,0);*z->p=w->r?*w->d:1;R z;} pi(i){P("%d ",i);}nl(){P("\n");} pr(w)A w;{I r=w->r,*d=w->d,n=tr(r,d);DO(r,pi(d[i]));nl(); if(w->t)DO(n,P("< ");pr(w->p[i]))else DO(n,pi(w->p[i]));nl();} C vt[]="+{~<#,"; A(*vd[])()={0,plus,from,find,0,rsh,cat}, (*vm[])()={0,id,size,iota,box,sha,0}; I st[26]; qp(a){R a>='a'&&a<='z';}qv(a){R a<'a';} A ex(e)I *e;{I a=*e; if(qp(a)){if(e[1]=='=')R st[a-'a']=ex(e+2);a= st[ a-'a'];} R qv(a)?(*vm[a])(ex(e+1)):e[1]?(*vd[e[1]])(a,ex(e+2)):(A)a;} noun(c){A z;if(c<'0'||c>'9')R 0;z=ga(0,0,0);*z->p=c-'0';R z;} verb(c){I i=0;for(;vt[i];)if(vt[i++]==c)R i;R 0;} I *wd(s)C *s;{I a,n=strlen(s),*e=ma(n+1);C c; DO(n,e[i]=(a=noun(c=s[i]))?a:(a=verb(c))?a:c);e[n]=0;R e;} main(){C s[99];while(gets(s))pr(ex(wd(s)));} APL J APL J APL J APL J --- - --- - --- - --- - + + ~ -. ⍳ i. ∊ e. - - ∧ *. ⍴ $ ⊥ #. × * ∨ +. , , ⊤ #: ÷ % ⍲ *: [] { ⌹ %. ⌊ <. ⍱ +: ↑ {. / / ⌈ >. < < ↓ }. ⌿ ?? | | ≤ <: ⍋ /: \ \ * ^ = = ⍒ \: ⍀ ?? ⍟ ^. ≥ >: ⌽ |. ∘.F F/ ○ o. > > ⊖ ?? F.G F/ . G ! ! ≠ ~: ⍉ |: ? ? Children of APL - K ------------------- ⍟ Arthur Whitney (1993+) ⍟ ASCII, but focused on single characters - Only the most important operators ⍟ Kx, multiple incompatible generations ⍟ Borrow from Scheme: - lists of lists - more function manipulators APL K3 APL K3 APL K3 --- -- --- -- --- -- ⍉ + + ~ =' ~ ? _draw - - x ⍳ @ ⌈ _ceiling ⊃ × * x ⍣ ? ⌊ _floor ÷ % ⌊ x _ 1○ _sin | > ∨ | x , , 2○ _cos ⍳ < ∧ & ≢ ⍴ # 3○ _tan ⍴ * ^ ⍕ ⍎ $ ⍟ _log ⍳ ⌽ ! . . * _exp ⍋ < < / ⍝ / .... ⍒ > > \ \ x = = ¨ ' x /: [] [] x \: Polymorphism ------------ ⍟ Binary, Integer, Real, and Complex are implicit - Some ops assume binary: ~ ∧ ∨ - Others are type preserving: + - × - Others selectively convert: ÷ (int to real) = < > (float/int to binary) * (float/int to complex) ⍟ Boxed values and strings... coexist Type Rank Dimensions Raveled Data ---- ---- ---------- ------------ Num 3 2 3 4 0 1 2 3 4 5... Boxing? Depth? Array Models ------------ ⍟ APL and others supports nested arrays - APL1 had a "flat box model" - APL2 introduced the "nested box model" ⍟ J continues using multidimensional arrays ⍟ K switches to nested 1D arrays CoSy ---- ⍟ Created by Bob Armstrong ⍟ Translate K's idioms to Forth ⍟ Vocabulary built on top of Reva Forth ⍟ Typed 1D arrays - Integer / Character / Float / Box ⍟ Vocabulary inspired by mix of K + APL names Reva Forth ---------- ⍟ Created by Ron Aaron ⍟ Case Sensitive ⍟ { ... } allows inline :noname ⍟ X86 Forth ⍟ GUI / Tui alias: --aa dup alias: a-- drop alias: --ba swap alias: --aba over alias: --b nip alias: --bab tuck alias: --bca rot alias: --c _2nip alias: --cab -rot : --aaa dup dup ; : --aab over swap ; : --aaba over swap over ; : --aabc 2 pick -rot ; : --aacb --aabc swap ; : --abaa over dup ; : --abba 2dup swap ; : --abca 2 pick ; : --abac 2 pick swap ; : --acab 2 pick rot ; : --acdb 2swap rot ; : --abcda 3 pick ; : --abcab 2 pick 2 pick ; : --bab dup -rot ; : --bba tuck swap ; : --bc rot drop ; i( 1 2 3 4 )i -- list of integer f( 1 2 3 4)f -- list of float `( list of strings )` -- list of strings 123 _i -- list of one integer 123.4 _f -- list of one float " hi" _str -- list of one string ` hi -- single word string +i -- dyadic add -i -- dyadic subtract *i -- dyadic multiply /i -- dyadic divide modi -- dyadic modulus \/ mini -- dyadic minimum /\ maxi -- dyadic maximum ori -- dyadic bitwise or andi -- dyadic bitwise and =i -- dyadic equal <>i -- dyadic not equal <i -- dyadic less >i -- dyadic greater 0<>i -- monadic not equal 0<i -- monadic less than zero 0>i -- monadic greater than zero I>M -- Iverson to Moore logic 1 vs -1 M>I -- Moore to Iverson logic 1 vs -1 absi -- monadic absolute value -0+i -- monadic sign lst -- print a list iota -- counting _iota -- counting from stack integer ,I -- catenate (integers) ,L -- catenate as lists (like lisp cons) 'm -- monadic each 'L -- dyadic each left 'R -- dyadic each left each -- dyadic each ^+ -- dyadic add (seems to assume int?) ^= -- dyadic equal (seems to assume int?) ./ -- dyadic reduce (like APL /) .\ -- dyadic scan (like APL \) +/ -- like APL +/ +\ -- like APL +\ ': -- apply between pairs reverse -- monadic flip rotate -- flip at nth position sublist -- extract subrange of list memb -- check for membership where -- locate an item in a list flip -- transpose Array Languages and Forth ------------------------- ⍟ Both Forth and Array Languages: - Try to be tacit / point-free - Notorious for being write-only - Strive to have a minimal core - Has some idioms for stack manipulation ⍟ But Array Languages: - Favor idioms over abstraction - Have memory safety - Have an unclear approach to stateful programs - Map the problem to the language, not the reverse "It is better to have 100 functions operate on one data structure than to have 10 functions operate on 10 data structures." -- Alan Perlis - Epigrams on Programming (1982) "I admire the elegance of your method of computation; it must be nice to ride through these fields upon the horse of true mathematics while the like of us have to make our way laboriously on foot." -- Einstein to Levi-Civita regarding tensor calculus "If I had asked people what they wanted, they would have said faster horses." -- Henry Ford "Unveiling the Marvels of Geometry and the Cosmos It is the glory of geometry that from so few principles, fetched from without, it is able to accomplish so much." -- Issac Newton Possible Lessons? ----------------- ⍟ APL and friends can be really small - Are we missing out on a safer more powerful base? - Powerful operators need fewer arguments ⍟ Are DSLs a distraction? ⍟ Should we use more symbols? ⍟ Should we find more Forth idioms? ⍟ --cba with Recognizers? ⍟ More infix? Maybe with Recognizers? ⍟ Could we avoid loops and conditionals too? ⍟ Is Math the way? - What kind of suggestivity does Forth have? Putting CoSy on the Web ----------------------- ⍟ Wine - started by Bob Amstadt and Eric Youngdale - Windows on Linux ⍟ Boxedwine - James Bryant - Wine on a 32-bit Linux emulator ⍟ Emscripten - Alon Zakai - C/C++/LLVM to Asm.js and WebAssembly ⍟ WebAssembly - Fast, low level code for the web ⍟ In sum: CoSy on Wine on Boxedwine on WebAssembly https://cosyapl.storage.googleapis.com/cosy.html DEMO + QUESTIONS❓ 🙏 Thank you!