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 slightly simpler:
{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