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