Translation of D-functions into tacit form
------------------------------------------
The following monadic functions are said  to  be  "extensionally equal"  because
given the same argument they  return  the  same  result.  Conversely,  they  are
"intensionally distinct" as their codings differ.

    {⍬⍴⍴⍵}      ⍝ D-function

    (⍬⍴⍴)       ⍝ Fork

    ⍬∘⍴∘⍴       ⍝ Composition

NB: these functions are extensionally equal only in a monadic context: if a left
argument  is  supplied,  their  behaviours diverge: the dfn ignores it; the fork
uses it; and the composition objects to it.

(muse:

    A significant difference between the dfn coding and the other  two  is  that
    the dfn's curly braces serve as a "quoting  mechanism" with respect  to  the
    dereferencing  (look-up)  of  names.  Names  in  dfns  are  dereferenced  at
    _application_ time, while those in trains and compositions are  dereferenced
    at  _definition_ time:

          tax ← 10                              ⍝ 10% tax

          dfn ← {⍵×1+tax÷100}                   ⍝ dfn including-tax calculation
        train ← (1+tax÷100)×⊢                   ⍝ train     ..      ..      ..
         comp ← (1+tax÷100)∘×                   ⍝ composition       ..      ..

        (dfn, train, comp) 20                   ⍝ tests: 20 + tax → 22
    22 22 22

        dfn ⋄ train ⋄ comp                      ⍝ display of functions
    {⍵×1+tax÷100}
    1.1×⊢
    1.1∘×

        tax ← 12                                ⍝ tax hike to 12%

        (dfn, train, comp) 20                   ⍝ only dfn uses new tax rate
    22.4 22 22
)

The following seven rules, applied recursively, transform a single line dfn into
tacit form:

    {X f Y} → ({X} f {Y})       ⍝ fgh-fork                        rule: {XfY}
    {  f Y} → (    f {Y})       ⍝  gh-atop                              {fY}
    {A f Y} → ( A  f {Y})       ⍝ Agh-fork                              {AfY}
    {X f A} → (A(⊢f⊣){X})       ⍝ commute                               {XfA}
        {⍺} → ⊣                 ⍝ left (base case)                      {⍺}
        {⍵) → ⊢                 ⍝ right (base case)                     {⍵}
        {A} → ((A)⊣⊣)           ⍝ constant (unusual base case)          {A}

where:
    X, Y are array-valued expressions with either ⍺ or ⍵ free.
       A is a constant array-valued expression, with neither ⍺ nor ⍵ free.
       f is a function-valued expression, with neither ⍺ nor ⍵ free.
    where:
        ⍺ (resp ⍵) is said to occur "free" in an expression if any occurrence of
        it is not enclosed in curly braces.  For example, ⍺ (but not ⍵) is  free
        in expression (⍺+2{⍺+⍵}3).

Translation example:

        {(2+⍺)×⍵÷3}             ⍝ rule {XfY}, × is principal (leftmost outer) fn
        ¯¯¯¯¯¯¯¯¯¯¯
    →   ({2+⍺}×{⍵÷3})           ⍝  ..  {AfY}
         ¯¯¯¯¯
    →   ((2+{⍺})×{⍵÷3})         ⍝  ..  {⍺}
            ¯¯¯
    →   ((2+⊣)×{⍵÷3})           ⍝  ..  {XfA}
               ¯¯¯¯¯
    →   ((2+⊣)×{3(⊢÷⊣)⍵})       ⍝  ..  {AfY}
               ¯¯¯¯¯¯¯¯¯
    →   ((2+⊣)×(3(⊢÷⊣){⍵}))     ⍝  ..  {⍵}
                      ¯¯¯
    →   ((2+⊣)×(3(⊢÷⊣)⊢))       ⍝ tacit form

For vector (strand) syntax we need a further rule:

    X Y Z ...  → ((⊂X),(⊂Y),(⊂Z),...)                                   (X Y)

where X, Y, Z, ... are array-valued expressions.

Square-bracket indexing should be replaced with the equivalent index function:

    X[Y] → ((⊂Y)⌷X)                                                     X[Y]

and embedded assignments replaced with inner dfns:

    {n+n←1+⍵} → {{⍵+⍵}1+⍵}                                              (←)

These rules are sufficient to translate single-line dfns into tacit  form.  How-
ever, the resulting function train will typically be longer than  necessary. For
example:

         {(+⌿⍵)÷≢⍵}             ⍝ {XfY}        "mean" (ignores left argument)
         ¯¯¯¯¯¯¯¯¯¯
    →   ({+⌿⍵}÷{≢⍵})            ⍝ {fY} {fY}
         ¯¯¯¯¯ ¯¯¯¯
    →   (((+⌿){⍵})÷((≢){⍵}))    ⍝ {⍵} {⍵}
              ¯¯¯      ¯¯¯
    →   (((+⌿)⊢)÷((≢)⊢))        ⍝ removing superflous parentheses       (())
          ¯  ¯    ¯ ¯
    →   ((+⌿⊢)÷(≢⊢))            ⍝ final non-optimal form (see below)

Optimisation
¯¯¯¯¯¯¯¯¯¯¯¯
     (f⊢)g(h⊢) → (f g h)⊢       ⍝ ⊢ factoring                           (⊢g⊢)
     (f⊢)g ⊢   → (f g ⊢)⊢       ⍝ ⊢ factoring                           (⊢g⊢)
       ⊣ g ⊢   → g              ⍝ dyadic function application           (⊣g⊢)
      (f(g h)) → ((f g)h)       ⍝ association                           (f(gh))

leading to a shortening of the above example "mean":

    →   ((+⌿⊢)÷(≢⊢))            ⍝ (⊢g⊢) (())
         ¯¯¯¯¯¯¯¯¯¯
    →   (+⌿÷≢)⊢                 ⍝ optimal form

where the final ⊢ is present only to ignore an unwanted left argument.

More examples:

        {(⊂⍋⍵)⌷⍵}               ⍝ {XfY}         "sort" (Phil Last)
        ¯¯¯¯¯¯¯¯¯
    →   ({⊂⍋⍵}⌷{⍵})             ⍝ {fY} {⍵}
         ¯¯¯¯¯ ¯¯¯
    →   ((⊂{⍋⍵})⌷⊢)             ⍝ {fY} {⍵}
           ¯¯¯¯
    →   ((⊂(⍋⊢))⌷⊢)             ⍝ (f(gh))
         ¯¯¯¯¯¯¯
    →   (((⊂⍋)⊢)⌷⊢)             ⍝ (⊢g⊢)
              ¯  ¯
    →   ((⊂⍋)⌷⊢)⊢               ⍝ (⊢g⊢)


        {(⊂⍬),⍵}                ⍝ {AfY} {⍵}
        ¯¯¯¯¯¯¯¯
    →   ((⊂⍬),⊢)                ⍝ (see optimisation below)


        {⍵ ⍵}                   ⍝ (X Y)
         ¯¯¯
    →   {(⊂⍵),(⊂⍵)}             ⍝ {XfY}
        ¯¯¯¯¯¯¯¯¯¯¯
    →   ({⊂⍵},{⊂⍵})             ⍝ {fY} {⍵}
         ¯¯¯¯ ¯¯¯¯
    →   ((⊂⊢),(⊂⊢))             ⍝ (⊢g⊢)
         ¯¯¯¯¯¯¯¯¯
    →   (⊂,⊂)⊢


        {⍵[⍺]}                  ⍝ X[Y]
         ¯¯¯¯
    →   {(⊂⍺)⌷⍵}                ⍝ {XfY} {⍵}
        ¯¯¯¯¯¯¯¯
    →   ({⊂⍺}⌷⊢)                ⍝ {fY} {⍺}
         ¯¯¯¯¯¯
    →   ((⊂⊣)⌷⊢)


        {32+⍵×1.8}              ⍝ {AfY}         °C → °F
        ¯¯¯¯¯¯¯¯¯¯
    →   (32+{⍵×1.8})            ⍝ {XfA} {⍵}
            ¯¯¯¯¯¯¯
    →   (32+(1.8(⊢×⊣)⊢))        ⍝ (⊢×⊣) → ×  (× is commutative)
                ¯¯¯¯¯
    →   (32+(1.8×⊢))

The last example results in a form for which, unlike the original dfn coding, ⍣
has an inverse:

        F ← 32+(1.8×⊢)          ⍝ °C → °F

        F ¯273.15 ¯40 0 100     ⍝ Fahrenheit from Celsius
    ¯459.67 ¯40 32 212

        C ← F⍣¯1                ⍝ °F → °C

        C ¯459.67 ¯40 32 212    ⍝ Celsius from Fahrenheit
    ¯273.15 ¯40 0 100

Restrictions and Extensions
---------------------------
[1] The process cannot translate an expression that contains ⍺ or ⍵ free in the
    operand of an operator:

        {(⊂⍣⍵)'Doh!'}
            ¯
[2] Nor will it transform a recursive call ∇.  Although it seems likely (to JMS)
    that  rules  might  be discovered for replacing some cases of recursion with
    the power operator ⍣.

[3] For multi-line dfns,  Phil Last has shown us how to transform a guard into a
    simple expression using /. See examples in →pow← and →cond←.

        {C:T⋄F}  →  {⊃{F}/(⍳~C),{T}/(⍳C),⊂⍵}                ⍝ (:⋄)

    where C, T and F are expressions. Unfortunately, guard expression C is eval-
    uated twice in the transformed code.  Note, however, that if neither T nor F
    makes  reference  to ⍺, then expression C may be evaluated just once and its
    result passed as left argument to an inner function:

        {C:T⋄F}  →  ((C){⊃{F}/(⍳~⍺),{T}/(⍳⍺),⊂⍵}⊢)          ⍝ (:⋄) T,F "monadic"

    (muse:

        There was overwhelming cultural pressure, in the specification of primi-
        tive power operator ⍣, for the "repeat count" to be the right _operand_.

        Had  the  repeat count been assigned to the left _argument_ of a monadic
        operator, as in →pow←, rule (⋄) could have been the simplified slightly:

            {C:T⋄F}  →  {(~C){F}⍣ C{T}⍣ ⍵}                  ⍝ (:⋄)
                                ¯     ¯
        Oh, and the _monadic_ derived function could have been "fixpoint":

            (1+÷)⍣ 1        ⍝ 1+÷ 1+÷ ... 1
        1.61803  ¯
    )

There is plenty of scope for further optimisation, particularly by employing the
compose (∘) and commute (⍨) operators:

   (A g ⊢) → A∘(g) ⊢
    (f g)⊢ → f∘(g) ⊢
     (⊢g⊣) → g⍨
       f⍨⍨ → f
      f⍨∘A → A∘(f)
    A∘(f⍨) → (f∘A)
          ...

On optimisation:  "By what course of calculation can these results be arrived at
by the machine in the shortest time?" - Passages from the Life of a Philosopher,
Charles Babbage, 1864, p.137.

Tacit programming in the large
------------------------------
It is possible to write substantial programs using predominatly tacit style. See
Aaron Hsu's Co-dfns compiler for a high-performance parallel version of APL:

    https://github.com/arcfide/Co-dfns

Source files c.cd, d.cd, e.cd and f.cd are good examples.

Examples:

        F ← 32+(1.8×⊢)
    →   F ← 32+1.8∘×

        ((⊂⍬),⊢)
    →   (⊂⍬)∘,

See also: dft defs

Back to: contents

Back to: Workspaces