Array Oriented Functional Programming In APL
1Array OrientedFunctional Programmingin APLMorten KrombergCTO, Dyalog Ltd.ACM Poughkeepsie,Marist College, September 17th, 2019Array Oriented Functional Programming in APL
2Array Oriented Functional Programming in APL
3Paradigms Object Orientation‐‐‐‐Modeling of queues / eventsSimula (1962)Smalltalk (1980)Java (1991), C# (2000) Functional Programming‐ Lambda Calculus (1936)‐ Lisp (1960)‐ Haskell (1992) Array Oriented Programming‐‐‐‐Applied Mathematics (1950's)IBM APL\360 (1966)Dyalog APL (1983)J (1990), k (1993)Introduction toA Programming LanguageKenneth E. Iverson (1962)Applied mathematics is largelyconcerned with the design andanalysis of explicit procedures forcalculating the exact or approximatevalues of various functions.Such explicit procedures are calledalgorithms or programs.Because an effective notation for thedescription of programs exhibitsconsiderable syntactic structure, it iscalled a programming language.Array Oriented Functional Programming in APL
4A Programming LanguageArray Oriented Functional Programming in APL
5Problems:- Wide variety of syntactical forms- Strange and inconsistent precedence rules- Things get worse when you deal with matricesSee http://www.jsoftware.com/papers/EvalOrder.htmArray Oriented Functional Programming in APL
6A Programming Languagea bMat1 . Mat2*xf g xx y(3 x)*2b a /4 6a* n /4 6Array Oriented Functional Programming in APL
7SymbolsPrimitive APL functions are denoted by [Unicode] symbols We learn and use new symbols all the time Symbols help us to communicate more concisely Suppose I asked you to simultaneously play three notes with frequencies of130.81, 155.56, and 196 Hertz. is a more concise way to convey that informationbut only if you know what the symbols mean:)𝑛 Sum all the elements of X 𝑋𝑖𝑖 1 How many combinations of k thingscan you make from n things? /X𝑛!𝑘! 𝑛 𝑘 !Array Oriented Functional Programming in APLk!n
8APL Symbols APL uses about 75 symbolsYou already know many of themArithmeticComparisonsSet OperationsLogic Many symbols are graphically indicative of their meaning ⌈ ⌊ Others are mnemonically indicative Rho – Reshape Iota – Index Many symbols are complementary ⌈ ⌊Array Oriented Functional Programming in APL
9CommentsThe lamp symbol ( ) indicates the beginning of acomment (comments illuminate code).2 3 two times three6Array Oriented Functional Programming in APL
10Array Oriented ProgrammingAlgorithms based on processing entire arraysrather than individual elements one at a timeExample: Count the scores that are greater than or equal to 65Pseudocodecount 0for score in scoresif score ge 65count 1endifendforDyalog APLcount 0:For score :In scores:If score 65count 1:EndIf:EndForArray Oriented Functional Programming in APL
11Array Oriented ProgrammingAlgorithms based on processing entire arraysrather than individual elements one at a timeExample: Count the scores that are greater than or equal to 65scores 20 78 90 56 83 / scores 653scores 65 1 for True, 0 for False0 1 1 0 1 / 0 1 1 0 1 Sum count occurrences of True3Array Oriented Functional Programming in APL
12Scalar FunctionsOperate on all the (scalar) items of arguments:5 7 90 0 13 2 31 2 3 4 5 6 addition10 20 30 25 greater than1 2 3 ⌈ 3 2 1 ⌈ maximum? 6 6 6 64 3 5 4 ? roll (as in dice)Indexing is also an array operation – but not a scalar function:'MISP'[1 2 3 3 2 3 3 2 4 4 2]MISSISSIPPIArray Oriented Functional Programming in APL
13Operators In APL, an operator is a "higher order function" which takesa function as an operand and returns a derived function Example: /( is the plus function and / is the reduction operator) plus reduction is a function which computes the sum of theitems in the right argument by inserting a between items: / 1 2 3 41 2 3 410Array Oriented Functional Programming in APL
14Reduction (f/ or f or f/[n])mat 3 4 12 mat /[2]mat /mat /mat1234102456782616809101112421188045120231384 /[1]matArray Oriented Functional Programming in APL
15Scan (f\ or f or f\[n])mat 3 4 12 \mat 82124Array Oriented Functional Programming in APL
16Outer Product ( .f) f for all combinations of items from left & right arguments121010vec1 .x vec2Array Oriented Functional Programming in APL10010010001000
17Inner Product (f.g)f/ row g col for all combinations of rows left, cols right.m1m2120 11 10302 10m1 . m2 / 1 2 0 1 2 0 15 2 1( . is vector or matrix product)Array Oriented Functional Programming in APL
18Inner Product (f.g)m1m2120 11 10302 10m1 . m2 / 1 2 0 1 2 00320( . is “count of matches”)Array Oriented Functional Programming in APL
19Inner Product (f.g)m1m2120 11 10302 10m1 . m2 / 1 2 0 1 2 00100( . left row identical to right col)Array Oriented Functional Programming in APL
20Summary: Syntax of APLSyntactical FormExamplearray1 3.1415 1.2E18function argument 61 2 3 4 5 6left-argfunction right-arg1 2 3 1 10 1001 20 300operandoperator / 1 2 3 4 5 62 / 1 2 3 4 5 67203 5 7 9 11left-opnd operator right-opnd1 0 2 . 1 2 37array[indices]'ABCDEF'[2 5 5 6]BEEFArray Oriented Functional Programming in APLResult
21Mixed Functions Scalar functions operate on pairs of itemstaken from arguments Mixed functions operate on arrays but maycombine items differently Many mixed functions operate on the structureof data, rather than perform computationsArray Oriented Functional Programming in APL
22Rotate and mat 3 4 120 1 0 1 mat2 0 1 ray Oriented Functional Programming in APL
23Examples of "Mixed" functionsIndexOf 3 1 4 1 5 9 1 2 32 7 1Grade (Up) digits 3 1 4 1 5 9 digits2 4 1 3 5 6digits[ digits] index by grade1 1 3 4 5 9Membership 'HELLO WORLD' 'AEIOU'0 1 0 0 1 0 0 1 0 0 0Array Oriented Functional Programming in APL
24Reshape mat 3 4 1212345678910111212342 2 matArray Oriented Functional Programming in APL
25Take and Drop 2 2 matmat 3 4 1212345678569101112910567891011121 matArray Oriented Functional Programming in APL
26Transpose 2 1 matmat 3 4 121 1 mat mat1234159567826109101112371148121611Array Oriented Functional Programming in APL
27Branch Free LogicThe fact that map is implicit, and indexing can be done using arrays,encourages logic without branches. The data itself provides flow control:ExamplePseudo Codescores 20 78 90 56 83 / scores 65for score in scoresif score ge 65 count 13data 2 7 15 60data ⌈ 1010 10 15 60if data[i] 10then data[i] else 10data data 3 7 152 8 16 60Increment where data[i] is in[3,7,15].(x mask) y maskIf mask[i] then x[i] else y[i]phase 'child' 'young' '20s' 'old' “bucketing”phase[1⌈4⌊ ⌈data 10]child child young oldArray Oriented Functional Programming in APL
28Order of ExecutionNo "precedence", only one rule: as f g x in mathematicsf g x f(g(x))Each function takes as its right argument the result of the entireexpression to its right.If it needs a left argument, take the value immediately to the left.Good APL can be read from left to right by an experienced programmer,but as a beginner you may need to break it down.10 2 3 6"Ten times [the] two three reshape [of the] first natural numbers."NB: You can experiment at https://tryapl.org:https://tryapl.org/?a 10%20%D7%202%203%20%u2374%20%u2373%206&runArray Oriented Functional Programming in APL
29Array Oriented Functional Programming in APL
30APL in 1970Functions: Scalar functions (implicit map) - ! * ⌈⌊ math comparisons logic? (roll) random numbersOperators: Reduction: Scan: Outer Product: Inner Product:/ \ .ff.gMixed functions , (matrix division)? (deal)(f on all combinations)(f/ rows-left g cols-right)Array Oriented Functional Programming in APL
31Driving Forcesfor ModernizationFeatureExternal Influence or RelationNested ArraysRelational Databases / "Tuples" / Heterogenous DataControl StructuresStructured Programming / Death of the GOTONew OperatorsRationalization / New Insights into Array NotationdfnsFunctional ProgrammingObject OrientationGUI other interfaces (COM Microsoft.NET)Futures & IsolatesMulti-core CPUs and Cloud ComputingArray Oriented Functional Programming in APL
32Nested Arrays Second Generation APL (ca 1983)‐‐Each item of an array can be another arrayJuxtapose arrays to create a list(4 5 6)(7 (8 9)) 4 5 6 7 8 9 Scalar functions “pervade”:(1 2 3) 10 (4 5 6) (7 (8 9)) 4 10 18 70 80 90 Array Oriented Functional Programming in APL
33Each Operator ( ) Nested arrays demand a mechanism to apply functions to individual items The Each operator applies the operand function to each element: (4 5 6) (7 8 9) shape of the array2 (4 5 6) (7 8 9) shape of each item 3 3 1 5 (4 5 6) (7 8 9) reshape each item 4 7 8 9 7 8 Array Oriented Functional Programming in APL
34Is APL "Functional"?Wikipedia:Functional programming is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematicalfunctions and avoids changing state and mutable data.count 0:For score :In scores:If score 65count 1:EndIf:EndFor / scores 65Array Oriented Functional Programming in APL
35Functional APLAPL encourages a functional style of problem-solving, but dynamicallyscoped APL allows procedural programming.Since the 1990's, “dfns” provide a lexically scoped way to definefunctions which is a better foundation for "pure" functional definitions:plusdouble { 2 } left arg two times rightfibonacci { Tail-recursive Fibonacci. 0 1 Default left argument 0: If 0, return 1st item of (1 , / ) -1 Tail recursion}Array Oriented Functional Programming in APL
36Syntax of APL w/ User Defined FnsUser-defined functions are infix or prefix, in exactly the same way as primitives.Syntactical FormExamplearray1 3.1415 1.2E18function argument 6fibonacci 101 2 3 4 5 655left-argfunction right-arg1 2 3 1 10 1001 plusdouble 2 31 20 3005 7operandoperator / 1 2 3 4 5 62 / 1 2 3 4 5 6fibonacci 6plusdouble/ 1 2 37203 5 7 9 11left-opnd operator right-opnd1 0 2 . 1 2 37array[indices]'ABCDEF'[2 5 5 6]BEEFArray Oriented Functional Programming in APLResult1 1 2 3 5 817
37New Operators1970: Reduction: Scan: Outer Product: Inner Product:f/ f f\ f .ff.gSelected new operators: Each:f Power:f n Rank:f (l r)(f on all combinations)(f/ rows-left g cols-right)(apply f to items)(apply f n times)(apply f to sub-arrays of given rank)Array Oriented Functional Programming in APL
38Examples of new Operators: Key ( )Apply operand function to items corresponding to unique keys.keys 'red' 'blue' 'red' 'red' 'blue'values 1020304050keys { } values Group by key red 10 30 40 blue 20 50 keys { , / } values Sum items by key red 80 blue 70 Array Oriented Functional Programming in APL
39Examples of new Operators: Stencil ( )“Stencil” applies function operand to each item of an array – and selectedneighbours: 1 2 3 is “same”: identity function1 2 3( 3) 1 2 3 Window Size 30 1 21 2 32 3 0NeighborsItems A one-dimensional ”blur” stencil can be expressed:({ .25 .5 .25 . } 3) 0 10 0 0 10 02.5 5 2.5 2.5 5 2.5Array Oriented Functional Programming in APL
40John Conway’s Game of LifeComputing the next generation: Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.Any live cell with two or three live neighbours lives on to the nextgeneration.Any live cell with more than three live neighbours dies, as if by overpopulation.Any dead cell with exactly three live neighbours becomes a live cell, as if byreproduction.life { 1 . 3 4 /, 1 0 1 . 1 0 1 . }life { 1 . 3 4 { /, } 3 3 }Array Oriented Functional Programming in APL
41Object OrientationF NEW'Form' (('Caption' 'Hello World')('Coord' 'Pixel')('Size'(100 400)))F.(B1 B2 B3) F. NEW {'Button'(('Caption'('Button ', ))('Posn'(5 50 0 )))} 1 2 3F.(B1 B2 B3).(Caption Posn) Button 1 5 55 Button 2 5 105 Button 3 5 155 F.(B1 B2 B3).(Posn[1] 50)Array Oriented Functional Programming in APL
42OO: For InterfacesXL NEW 'OleClient' ( 'ClassName' 'Excel.Application')cities XL.Workbooks.Open 'c:\.\cities.xls'sheets cities.Sheets Sheets collection as an arraysheets.Name D DK UK sheets.UsedRange.Value2 Germany 82.4 Denmark 5.4 United Kingdom 60.2 Berlin 3.4 Copenhagen 2 London 7 München 1.2 Helsingør 0.03 Birmingham 1 Stuttgart 0.5 Basingstoke 0.1 Array Oriented Functional Programming in APL
43Arrays of Objects In most OO languages, everything is an objectIn Dyalog APL, arrays are a higher level of organization‐ Arrays can CONTAIN objects, but.‐ Arrays ARE not objects As a result, the "dot" is a parallel operationarray.member. is a reference to member for each item of the array, not to a property ofthe array. For example, if sheets is a 3-element array of worksheet objects:sheets.Name D DK UK Array Oriented Functional Programming in APL
44Staying "Modern" for 50 YearsRecap. 1982: Nested Arrays (any item of an array can be an array)adopted by all APL vendors. 1995: Control structures (if/then/else) adopted by most APL vendors. 1996: Functional Programming: lexical scope and lambda expressionsin APL (“dfns” – Dyalog). 2006: Object orientation (Dyalog, MicroAPL, VisualAPL). 2014: Point-free or “tacit” syntax (from J) adopted by first APLvendor (Dyalog) 2014: Futures and isolates for asynchronous programming (Dyalog)Array Oriented Functional Programming in APL
45Still Modern after all those Years“Dyalog is a modern, array-first,multi-paradigm programming language,which supports functional, object-oriented andimperative programming,based on an APL language kernel.”Array Oriented Functional Programming in APL
46Why Modern Hardware Loves Arrays The design of APL was driven by human factors‐ Not the architecture of computer hardware Goals of APL Language design‐ Removes unnecessary detail from algorithms‐ Frees the mind to operate at a higher level‐ Allows math to be translated directly into code After 60-70 years, the hardware is also startingto appreciate arraysArray Oriented Functional Programming in APL
47TheFree LunchIs OverCPU scaling showing transistordensity, power consumption,and efficiency. Chart originallyfrom The Free Lunch Is Over: AFundamental Turn TowardConcurrency in SoftwareArray Oriented Functional Programming in APL
48The Power ProblemIn the mid-2000s (at 90nm) gates became too thin to prevent currentfrom leaking out into the substrate. Clock speeds could no longerincrease without excessive power consumption.Innovation continues with technologies like: strained silicon, hi-k metalgate, FinFET, and FD-SOI have helped, but from 2007 to 2011, clock speeds rose 2.9GHz to 3.9GHz (33%) (from 1994 to 1998, CPU clock speeds rose by 300%)Sources: re-still-stuckArray Oriented Functional Programming in APL
49TheFree LunchIs OverCPU scaling showing transistordensity, power consumption,and efficiency. Chart originallyfrom The Free Lunch Is Over: AFundamental Turn TowardConcurrency in SoftwareArray Oriented Functional Programming in APL
50Transistor Count Still Increasing Cannot increase clock frequency without burning yourlap and melting the North Pole Throttle back and do more with parallel coresArray Oriented Functional Programming in APL
51Making Use of Additional Transistors In addition to having parallel cores, use extralogic to do things in parallel WITHIN each core:‐ Prefetch memoryinto larger caches‐ Optimisticallypredict paths andpre-executemultipleinstructionsArray Oriented Functional Programming in APL
52Advantages of (APL) ArraysArrays are DENSE Aggressive conversion to smallest possible representations: 1-bitbooleans, 1-byte, 2-byte, 4-byte integers 8-byte floats. Also 1, 2 and 4 byte Unicode characters Faster memory transfers Better cache utilization Vector instructions can handle many array elements at a timeFew POINTERS Sequential data access is enormously more efficient than "pointerchasing" (pointers also consume extra memory) More successful pre-fetching of data More successful branch predictionArray Oriented Functional Programming in APL
53Branch Free LogicDecisions can be made using translate tables and vectorized computation.Boolean arrays consume 1 bit per element ( 64 elements per instruction!).ExamplePseudo Codescores 20 78 90 56 83 / scores 65for score in scoresif score ge 65 count 13data 2 7 15 60data ⌈ 55 7 15 60if data[i] 5then data[i] else 5data data 3 7 152 8 16 60Increment where data[i] is in[3,7,15].(x mask) y maskages 'child' 'young' '20s' 'old'ages[1⌈4⌊ ⌈data 10]child child young oldIf mask[i] then x else y“bucketing”Array Oriented Functional Programming in APL
54Simple Example:Replace CRLF with LF in a stringCAPLvoid crlf to lf(char* dst, char* src, size t n){int was cr 0;for (size t i 0; i n; i ){char c src[i];if (was cr && c '\n') dst--;dst[i] c;was cr (c '\r');}}CR LF UCS 13 10crlf to lf {(( CR) 1 LF) / }For all chars: If char is not CR, or following char is not LF, keep the charArray Oriented Functional Programming in APL
56Image from Marshalls talkMarshall Lochbaum: Moving Bits Faster in Dyalog Version 16.0.https://dyalog.tv/Dyalog17Array Oriented Functional Programming in APL
57Use Multicore Hardware Multithread primitives on large arrays Compile to Parallel Hardware‐ Aaron Hsu at Indiana University: co-dfns compiler‐ HyperFit / University of Copenhagen: APL to Futhark‐ Bernecky / Scholz @ Herriot Watt: Single Assignment C Introduce Asynchronous Features into Language‐ Futures and IsolatesArray Oriented Functional Programming in APL
58[Arrays of] Futures Parallel ( ) is an operator which applies its left operandfunction asynchronously A future is immediately returned, while the function runsinside an isolate (detached from the current scope) Arrays containing futures can be passed as arguments, andbe subject to selection operations, without blocking The system blocks automatically until the future is resolved,if the value is required for futher computation The following expression computes three averages inparallel: avgs {( ) } (2 3)(3 4 5)(9)2.5 4 9Array Oriented Functional Programming in APL
61Rank Operator (1 of 2)mat (x 1 0) vecMultiplication with left rank 1 (vectors), right rank 0 (scalars)12345610 102030400500600Array Oriented Functional Programming in APL100
62Rank Operator (2 of 2)mat 2 2 4 1612345678910 11121314 1516(( ) 2) mat avg cols31145612 1314( ) mat average along 1st dimension5967810 1112(( ) 1) mat avg rows2.56.510.5 14.5Array Oriented Functional Programming in APL
63
Array Oriented Functional Programming in APL Wikipedia: Functional programming is a programming paradigm— a style of building the structure and elements of computer programs— that treats computation as the evaluation of mathematical functions and avoids changing state and mutable dat
Numeric Functional Programming Functional Data Structures Outline 1 Stuff We Covered Last Time Data Types Multi-precision Verification Array Operations Automatic Differentiation Functional Metaprogramming with Templates 2 Numeric Functional Programming Advanced Functional Programming with Templates Functional Data Structures Sparse Data Structures
Functional programming paradigm History Features and concepts Examples: Lisp ML 3 UMBC Functional Programming The Functional Programming Paradigm is one of the major programming paradigms. FP is a type of declarative programming paradigm Also known as applicative programming and value-oriented
It stands for Object Oriented Programming. Object‐Oriented Programming ﴾223﴿ uses a different set of programming languages than old procedural programming languages ﴾& 3DVFDO, etc.﴿. Everything in 223 is grouped as self sustainable "REMHFWV". Hence, you gain reusability by means of four main object‐oriented programming concepts.
Object Oriented Programming 7 Purpose of the CoursePurpose of the Course To introduce several programming paradigms including Object-Oriented Programming, Generic Programming, Design Patterns To show how to use these programming schemes with the C programming language to build “good” programs.
object-oriented programming language is based on a kind of old object-oriented programming language. For example, though C language is an object-oriented programming language, it still retains the pointer which is complex but has strong function. But C# improved this problem. C# is a kind of pure object-oriented language.
Welcome to Functional Programming in R! I wrote this book, to have teaching material beyond the typical introductory level most textbooks on R have. This book is intended to give an introduction to functions in R and how to write functional programs in R. Functional programming is a style of programming, like object-oriented programming,
Functional Programming Aims 0.1 Aims functional programming is programming with values: value-oriented programming no ‘actions’, no side-effects — a radical departure from ordinary (imperative or OO) programming surprisingly, it is a powerful (and fun!) paradigm ideas are applicabl
ANSI A300 Purpose: To provide performance standards for developing written specifications for tree management. Currently nine individual parts . ANSI Z60 American Nurseryman and Landscape Association began developing this standard back in 1929 Became an ANSI document in 1949 Current version is 2004 . ANSI A300 The Tree Care Industry Association convened a consensus body .
