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 Back to: contents Back to: Workspaces