Dynamic Functions in Practice

Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 50

[ed] These notes have been adapted from a PowerPoint original, with the addition of some commentary and consolidation of several of the bullet points.

Last summer at the Yale conference I tried to convince Bill Rutiser that they should implement Dynamic functions in APL+Win, too. Bill asked dryly: "Where do you need them?".

I don’t know how convincing I was (under the scorching Yale sun), but I vaguely remember giving estimates that up to 30 percent of all the code I write is dynamic, and my productivity has increased in proportion to that. Besides, dfns have given me back the delight, i.e. the same delight I had when I first met APL aeons ago.

Now I should change that percentage to, say, 45.

A Small APL Teaser¶

• change the nested vector:

   ,A←'Arto' 'Conrad' 'Kimmo' 'Adrian' 'Jukka'
 Arto  Conrad  Kimmo  Adrian  Jukka

to …

 Arto  darnoC  Kimmo  nairdA  Jukka

• fewer than nine APL characters, please
• you are allowed to use dynamic functions ;)

APL Difficulties¶

i.e. APL design flaws.

• only one function type

We have to use the same function type with small utilities and huge applications

• local variables in the header line

Nowadays this should be vice versa <sigh!>.

• local functions are hard to handle
• inefficient argument handling

You never know when the WS FULL appears..

• functions’ loading time backlash
• especially with small functions

When the function is opened for use, the code is parsed especially the header line and labels among others (e.g. possible control structures). This can be dramatic with e.g. DeleteTrailingBlanks ¨ HUGE_NESTED_VECTOR.

Direct Definition¶

There have been some proposals how to circumvent some of the limitations.

• as seen in the (Sharp) APL literature..

I can still remember reading the first APL Conference Proceedings, and testing those examples with VS APL … they didn’t work.

vec:   ,⍵
sum:   +/⍵
mvec:  (sum vec ⍵)÷⍴vec ⍵
mean:   ⍵ : 0∊⍴⍵ : mvec ⍵

• implemented at least in I-APL
• no practical use

Dyalog Peculiarities¶

Dyalog APL has some interesting extensions to the APL language.

• specific functions (∪⎕≢) and operators (∘⍨&)
• function assignment

sum←+/
rank←⍴∘⍴
fn←very_long_function_name

This last one is quite handy: if you need, say, a utility function DoSomethingUseful from the namespace #.utils repeatedly in one function, you can make a local assignment dsu←#.utils.DoSomethingUseful, and use that (function pointer) instead of the original name monster.

• namespaces
• syntax differences (e.g. shy result)
• control structures (:If, :For, :Trap, ..)
• dynamic functions (first seen at Lancaster 1996)

Dynamic Function¶

• delimited with braces {}

… where the braces contain legal APL expressions!

• doesn’t need to return a result, and it can include another D: function
• may call traditional APL functions and operators as well
• uses D: language, which differs slightly from traditional APL
• laconic syntax
• D: behaves like functional languages (e.g. static variable scope)

Arguments¶

• D: functions are ambivalent
• the right argument symbol is ⍵
• the (possible) left argument symbol is ⍺
• arguments are pointers, thus one cannot modify the arguments

There’s one exception to this rule

• it is not necessary to use the arguments

Efficiency¶

• D: is pretty simple for the interpreter
• delimited function structure

no branches, labels, control structures, headers..

• no extra data copying behind the scene
• effectively used with operators

=> usually 10-20% time saving

Some Examples¶

   {⍵×10} 1+2
30
   {1+2} 'hello world'
3
   'vege' {⍺,⍵} 'table'
vegetable
   {(⍵*0.5) +/⍵*2} 3 4
5
   root←{⍵*0.5}
   square←{⍵*2}
   root +/square 5 12
13

Basic Idioms¶

{}        eat
{⍵}       dex
{⍺}       lev
{⍵ ⍵}     duplicate
{⍵/⍳⍴⍵}   indices of a binary vector
{⍵~' '}   blank removal
{⍺[⍵]}    controlled indexing

This is extremely useful with looping and sparse indexing!

{⍵[⍋⍵]}   upgrade vector
{⍵[⍋⊃⍵]}  upgrade nested vector

Did I mention that I’m an APL2 bigot?

{'.'⎕WS'Cursor'⍵}   GUI control

Structure¶

D: function may have line separators ⋄¶

• result = the value of the first non-assigned expression
• every assigned name is local

D: functions are edited with the APL editor¶

• empty lines and comments are OK
• one-liners can be edited in the session, too

Pretty Obvious¶

• global variables are editable

.. but only if you create them beforehand

   a←b←⍳3 ⋄ {}{(a←⍵)(b[]←⍵)} 7 6 5
   a b
1 2 3  7 6 5

• D: function can be assigned to a name

n.b. syntax and name class differences!

   mean←{(+/⍵)÷⍴⍵} 1 2 3
   mean←{(+/⍵)÷⍴⍵}
SYNTAX ERROR
    mean←{(+/⍵)÷⍴⍵}
      ∧

Variable Scope¶

• D: functions have a static scope (traditional APL has a dynamic scope)

   type←{way←'static'
        FN1←{way←'dynamic' ⋄ FN2 ⍵}
        FN2←{way ⍵}
        FN1 ⍵}

   type 'scope'
static  scope

Guard¶

• the only control structure of D:, symbol :
• format: condition:expression
• if condition = 1, the expression will be executed and the D: function is closed, otherwise the next line will be executed

   {2|⍵:'odd' ⋄ 'even' ⋄ 'never'} 313
odd

• even the guard may contain a D: function

    { ..multiple lines producing
   a boolean result.. } ⍵: { .. }

Default Argument & Shy Result¶

• the default value of the left argument can be assigned: ⍺←default
• the assignment takes place only if the left argument doesn’t exist

   root←{⍺←2 ⋄ ⍵*÷⍺}
3 root 64
  4
root 64
  8

• shy result can be attained with guard

1:dummy←result

Recursion¶

Recursion and operators are much more used with dynamic functions than with traditional APL.

• D: function may call itself
• the function symbol is ∇

fact←{⍵=1:1 ⋄ ⍵×∇ ⍵-1}

• pretty efficient with tail call

fact←{1{⍵=0:⍺ ⋄ (⍺×⍵)∇ ⍵-1}⍵}
fact←{⍺←1 ⋄ ⍵=0:⍺ ⋄ (⍺×⍵)∇ ⍵-1}

• going through a nested structure

{1<≡⍵:∇¨⍵ ⋄ fn ⍵}

Dynamic Operators¶

• "functions with four arguments"
• operands ⍺⍺ and ⍵⍵, recursion uses ∇∇
• the mere existence of ⍺⍺ makes D: an operator

   else←{⍺:⍺⍺ ⍵ ⋄ ⍵⍵ ⍵}
   1 + else - 22
  22
0 + else - 33
  ¯33

Multiline Idioms¶

{1<≡⍵:,⍵ ⋄ ,⊂,⍵}    ensure vector of vecs
{2=⎕NC ⍵:⍎⍵ ⋄ def}  default value
⊃{rowfn ⍵}¨↓mat     process matrix lines
{⎕IO←0 ⋄ ⍺+⍳1+⍵-⍺}  integers ⍺..⍵

D:-functions can be used as capsules, thus avoiding the mess with wrong system variables etc.

{⎕ML←3 ⋄ ∊⍵}                    enlist
{⎕ML←0 ⋄ ∊⍵}                    type
{⎕ML←3 ⋄ (⍵≠⍺)⊂⍵}               APL2 partition
{⎕ML←2 ⋄ (1,1↓⍺)⊂⍵}             binary partition
{⎕RL←+/¯3↑⎕TS ⋄ ⍵[(⍴⍵)?⍴⍵]}     randomise vector

Conditional Structures¶

you can make your own controls

:If
   {if_cond:expr_1 ⋄ expr_0}

:Select
      {case1_cond:expr_1
       case2_cond:expr_2
          ..
        expr_0}

Looping Structures¶

:For (no connection between loops)

          {expression}¨⍳n

:For (variables updated between loops)

     ↑{expression}/n⍴x

 condition{(b z)←⍵ ⋄ ⍺:z

          ..algorithm..

        a ∇ b z} var init

:While and :Until
⍺ storage, ⍵ counter

   gcd←{⍵=0:⍺ ⋄ ⍵ ∇ ⍵|⍺}

Error Trapping¶

• errors can be trapped with error codes (0=all errors), symbol ::

errcode(s)::err_expr

• when an error occurs, the err_expr will be executed (unwind)
• nested traps are possible

fopen←{0::0
       22::⍵ ⎕FCREATE 0
    24 25::⍵ ⎕FSTIE 0
           ⍵ ⎕FTIE 0
          }

Possible Uses¶

• file handling

openc←{0::0 ⋄ 22::⍵ ⎕NCREATE 0 ⋄ ⍵ ⎕NTIE 0}
isfil←{0::0 ⋄ {1}⎕NUNTIE ⍵ ⎕NTIE 0 0}
isdir←{0::0 ⋄ {1}⎕NUNTIE(⍵,'\nul')⎕NTIE 0}

These aren’t by far the most useful routines for file handling purposes, but serve as good examples how you can use ad hoc error trapping.

• non-resulting expression giving a result ;)

'fm' ⎕WC 'Form'
'fm' {0::⍵ ⋄ {⍵} ⍺ ⎕WS 'BCol' ⍵} 255 0 0
255 0 0

Unwinding¶

• error trapping brings us back to the trapping line, and that environment comes back, too

beartrap←{0::'erroneous divider:' q
          q←⍵
          ⍺÷q}

   1 beartrap 2
0.5
   1 beartrap 0
VALUE ERROR
   beartrap[1] 0::'erroneous divider:' q
                                       ∧

Creating Globals¶

• it is possible to make globals in D:
• according to the guide:

      {⍎'GLOB←⍵'} 1 2

• or with the compose operator:

      {GLOB∘←⍵} 3 4

• or with the full path name:

   {#.GLOB←⍵} 5 6
   {(⍎'' ⎕NS '').GLOB←⍵} 7 8

Tricks¶

Most of these are copied from dfns@dyadic.com mail group.

• does ⍺ exist?

⍺←1 1 1⍴⎕AV ⋄ ⍺≡1 1 1⍴⎕AV:..  so-so algorithm
0=⎕NC '⍺':..               version 9
⍺←{⍵} ⋄ 1≡⍺ 1:..           works everywhere

• an array of constants, the structure of which is copied from another array

{const}¨array

• "modify" the argument

{q←,⍵ ⋄ ((q='¯')/q)←'-' ⋄ (⍴⍵)⍴q}

• initialise the left argument

1∘{⍵=0:⍺ ⋄ (⍺×⍵)∇ ⍵-1}

• a quick alternative to sink←

{0}expr:              ⍝ sink ← expr

• chaining (to avoid intermediate variables)

{ expr
}{expr
}{expr
 }data

• passing D: function to its sub-D: function

fun←{{fun ⍵}⍵}   ⍝ hardcoded name
fun←{∇{⍺⍺ ⍵}⍵}   ⍝ via operand!

Where Is D: Appropriate?¶

• idioms!

There’s no need any more to have unnecessary intermediate variables

• ad hoc algorithm testing within session

This is one of the real strengths: you can test and retest your code without messing the workspace with temporary variables and functions.

• coding of clean algorithms

logic "shines through"

• local functions

on the fly.

Let’s assume that you have a traditional DeleteTrailingBlanks function (one-liner, perhaps). You can change it pretty easily to a dynamic function with the same name. But you can as well (if you need it only in one processing part) make it as a local function within that routine. Or, as I have done it with one application, make a DynInit function, which creates a toolbox of (semiglobal) D: functions, which only exist during the run time. I have found this approach quite useful for my needs.

• speeding up your ol’ toolbox

The most part of the old workhorses can be very quickly changed to D: functions.

• APL communication

Because D: code is straightforward, you can show APL code easier than before (e.g. working APL code can be fully shown in PowerPoint presentations).

• having fun

This is the part I like most ;)

Where Is D: Inappropriate?¶

• GUI callbacks :(

This may change in the future!

• BIG applications

(strongly a personal opinion)

Maybe this is just an old-dog-new-tricks syndrome, but I think that the old function syntax with control structures et al. shines here.

• BTW: ⎕CS is not supported

Sources¶

• Dyalog APL Manual
• www.pyr.fi/apl/texts/fapliddf.zip
• dfns@dyadic.com ["subscribe"]
• www.dyadic.com [product]
• www.dyadic.com/download/dfns.zip (dfns.rtf)
• www.dyadic.com/download/dsamples.zip (dfns.dws, min.dws, max.dws, tube.dws)
• Vector 17.4: Scholes: "D: a Functional Subset of Dyalog APL"

Packing: General¶

This part of my presentation was meant to be the "practical" part just as to fulfil the promises of the original header line. The idea came last autumn when there was a short but lively discussion about packing in the dfns mailgroup.

Huffman coding¶

• the most common item is replaced with the shortest binary index
• decoding is very s l o w in APL

Lempel-Ziv-Welch packing¶

• a "running" algorithm: if the next part to be handled is already found in the dictionary, it can be replaced with the pointer only -> efficient
• many variations have patents pending
• inefficient to code in APL

I know that someone has tried this ;)

APL Packing¶

Although these methods are not usually comparable with the professional ZIP/ARJ/RAR packers, they have their own uses within the workspaces.

• traditional simple zero-packing

zapN←{(⍴⍵)(,⍵≠0)((,⍵≠0)/,⍵)}
unzN←{⎕IO←1 ⋄ (1⊃⍵)⍴(2⊃⍵)\3⊃⍵}

This is pretty quick, and especially useful when handling sparse multi-dimensional APL arrays.

• running length packing (RLE) is slightly more complicated

zapR←{b←{0∊⍴⍵:⍵
         {¯2-/⍵/⍳⍴⍵}(1,2≠/⍵),1
        },⍵
      ⎕IO←1 ⋄ (⍴⍵)b((,⍵)[+\b])}
unzR←{⎕IO←1 ⋄ (1⊃⍵)⍴(2⊃⍵)/3⊃⍵}

Quite useful with bitmaps.

• unique packing is quite handy

zapU←{⎕IO←0 ⋄ u←∪,⍵ ⋄ (⍴⍵)u(u⍳,⍵)}
unzU←{⎕IO←0 ⋄ (0⊃⍵)⍴(1⊃⍵)[2⊃⍵]}

This works nicely where there are only a small set of unique items in a big variable.

• outer resource: free zlib.dll
• Vector 18.1: Lanzavecchia/Smith

Pros: universal, free, efficient. Cons: you cannot bundle them within the workspace, you need to have extra code to ensure that those resources exist.

We need a couple of D: functions (because .dll handles only 8-bit integer vectors).

zapZ←{(⍴⍵)(32768 ZLIB.DeflateIV 83 ⎕DR,⍵)}
unzZ←{(1⊃⍵)⍴323 ⎕DR 32768 ZLIB.InflateIV 2⊃⍵}

Problem: Bitmaps¶

Nowadays GUI apps contain lots of bitmaps: company logos, backgrounds, icons, pictures. Toolbars contain toolbuttons with lots of icons, both standard (which are easily copied from system resources) and hand-crafted (which are buried within the workspace). If you put these parts outside the application, there's the controlling problem, if you enclose them inside your ws, it will grow exponentially, if you don't squeeze them tightly.

Let’s Test …¶

This is my first test I made after writing a couple of pack-unpack routines.

   'bmp' ⎕WC 'Bitmap' 'D:\bmp\lion'
   cb←'bmp' ⎕WG 'CBits'
   (⍴cb)(⎕SIZE 'cb')
480 568  1090580

First we read a bitmap (in this case we could have read the Bits and CMap properties to save space, but that would have spoiled the results ;) ). We need a tool which tells us the time used with packing/unpacking, the size of the packed data and the percentage saved. Besides, it should test if the data is unpacked unchanged. A dynamic operator is quite suitable for this purpose:

   Tst←{
    ai←⎕AI ⋄ q←⍵⍵ ⍵
    ⍵≢⍺⍺ q:'wrong result'
    sz←∊{s←⍵ ⋄ ⎕SIZE's'}¨q ⍵
 (2⊃⎕AI-ai)(1⊃sz)('%',⍨0⍕100×÷/sz)
       }

Results¶

   unzN Tst zapN cb
   90 1124720   103%

Quick! But the compressing ratio is not nice...

   unzR Tst zapR cb
 240  822148    75%

Chops one quarter off the size, not bad!

   unzU Tst zapU cb
 180  272784    25%

… but this seems to be an approach worth using!

   ZLIB.Init
   unzZ Tst zapZ cb
1132  136692    13%

This works as expected: best compression this far.

   unzB Tst zapB cb
 731  116440    11%

… but this method seems to outperform (in this case) even the ZLIB!!

Let's have a closer look at the last function pair. Actually these are nothing but enhanced unique packing, which works surprisingly well in this case. I have tested with many bitmaps, and usually ZLIB seems to be the winner, but for my purposes these two functions have given a sufficient compression. And hey, you can easily write this algorithm with traditional APL, too!

zapB←{⍝ BMP packer, opened with unzB

   ⎕IO←0 ⋄ u←∪,⍵        ⍝ unique items
   i←u⍳,⍵               ⍝ indices
   w←⌈2⍟⍴u              ⍝ max. width
   b←1,2≠/i             ⍝ repeats
   j←0∨,(w⍴2)⊤b/i       ⍝ binarise
   ((⍴⍴⍵),(⍴⍵),u)b j    ⍝ package

     }

unzB←{⍝ Open a zapB'd package

   ⎕IO←0 ⋄ q←0⊃⍵ ⋄ s←0⊃q ⍝ get vars
   r←s⍴1↓q ⋄ u←(s+1)↓q    ⍝ ⍴, unique items
   w←⌈2⍟⍴u                ⍝ index width
   e←{¯2-/(⍵,1)/⍳1+⍴⍵}1⊃⍵  ⍝ expander
  ⍝ create indices from bit vector
   i←2⊥w{(⍺,⌊(⍴⍵)÷⍺)⍴⍵}2⊃⍵
   r⍴u[e/i]               ⍝ open
     }

These functions, among others (e.g. Shanno-Fano packing), are included in the newest dfns.dws workspace.