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:

    For small functions, any of the  codings  may  be  appropriate,  though  for
    larger ones, the first style is  probably  preferable.  There  seems  little
    practical value in coding large functions as trains  or  compositions  other
    than as an entertainment.  One possible exception is that  inverse  operator
    ⍣¯1 may be able to invert some  derived  functions,  whereas  dfns  are  not
    currently within its operand-domain.                                     <V>

    A significant difference between a 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 ⍣ 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    ⍝ (requires interpreter patch[14018])        <V>
    ¯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.

Examples:

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

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

See also: dft

Back to: contents

Back to: Workspaces