PrimitivePrimitives

From J Wiki
(Redirected from Puzzles/PrimitivePrimitives)
Jump to: navigation, search

Goal

If one of the primitives in the Vocabulary were missing, how would you reproduce its functionality? The goal is to get the definition of every primitive using other primitives.

Motivation

Besides being a fun puzzle, the primary motivation is pedagogical. These definitions can be used to generate sets of 'primitive primitives': J words that can be used to describe all the rest of J, providing an easy path to learning J.

Another nice side effect will be that some phrases/idioms/compound-code-sequences which are often repeated will become obvious (for example i.@:#). These pieces of code could be treated as primitives in their own right, leading to even more ways of expressing J within J. And, as a bonus, these idioms might be optimized in the interpreter, or even assigned to true primitives (as I. =. # i.@:# was).

Methodology

1.#0 We'd like an __exact__ replacement for each primitive. Specifically, the replacement should produce identical results under nominal conditions (even in internal type) to the original, and produce the same errors under exceptional conditions.

1. However, subfunctional replacements are acceptable, as they can be combined to produce a fully functional replacement.

1. Try not to use replacements for primitives within the replacements themselves. For example, in the replacement of ~., use only #~ ~:, not #~ (i.@:# = i.~), (substituting for ~:), #~ (i.@:# = ((#@:[ (>:@:[ | <:@:-) (i.~ |.)~ ))~) (substituting for i.), etc. We'll have code that will automatically explore those relationships.

1. At a later point, we're going to have to think about inverses, identity functions, adverses, tolerance, and derivatives, too. Basically any other characteristic of the primtive built in to the interpreter (accesible via b., D., or !. ?).

1. Tacit code is preferred, but the removal of the Trains Table from Appendix F of the DoJ in version 5 has made this harder. I doubt many operators (adverbs/conjunctions) will be expressible tacitly.

1. Keep in mind that verbs can be monadic, dyadic, or ambivalent. When writing a replacement, indicate which of these cases you are replacing (and, for operators which produce verbs, indicate the valence of the __derived__ entity).

1. If you see a phrase that is oft repeated, feel free to give it a name, and substitute the name for the code in the defitions. Be sure to document the definition of the name somewhere! An example might be count =. i.@:# and substituting #~ count = i.~ for #~ i.@:# = i.~ in the redefinition of ~..

1. Primitives with many possible replacements might be better placed on a seperate subpage.

Comments

See the discussion page for more details. Yours are welcome.

Table of primitive replacements

Primitive Valence Replacement Domain Notes
i: Monad -~ i.@:>:@:+: Full
Dyad <:@:-) (i.~ |.)~ )
{ Monad >@:(,&.>/&.>/) See notes Does not work with an argument with (L. > 0: *. 1: = #)
~. Monad #~ ~: Full
{.;.1~ ~:
{./.~
~: Monad i.@# e. i.~ Full Nubsieve seems dependent on the pseudo primitive i.~
i.~ = i.@#
i.@:# e. (i. ~.)
i.@:# e. ] {./. i.@#
Dyad -.@:= Not equal
/. Dyad 1 : 'u.@#~ =' Full This was much neater in J4, where you could write (@(#~)) =
+ Dyad -- Full
- Monad 0&- Full Monad and dyad are defined in terms of each other.
Dyad + -
[ Ambivalent ]~ Full
] Ambivalent [~ Full
@: Ambivalent 2 : '[: u. v.' Full
,. Ambivalent ,"_1 Full
~ Ambivalent 1 : '(] u. ]) : (] u. [)' Verbs
N/A 1 : 0 Nouns
   if. -. 0 > nc n. =. {.;: m. do.
      ". 'n.=.',5!:5 n.
      n.
   else.
      (13!:8) 4
   end.
)
L. Monad (>:@:(>./)@:($:&>))`0:@.((0: e. $) +. (-: >)) Full L. has no dyadic case as of J5, so this should be a complete replacement
I. Monad # i.@:# Full I. has no dyadic case as of J5, so this should be a complete replacement
.. Ambivalent 2 : '((u. + u.&v.) % 2:) : [:' Full Even though the DoJ says u .. v ⇔ (u + u&v) % 2:, verbs derived from .. have no dyadic case.
.: Ambivalent 2 : '((u. - u.&v.) % 2:) : [:' Full Even though the DoJ says u .: v ⇔ (u - u&v) % 2:, verbs derived from .: have no dyadic case.
= Monad :@:(=/ ~.)@:,@:(<"_1) Full Using the dyadic case of = to define its monadic case. That is OK. We could also use i.~ in place of ,@:(<"_1) as Roger points out.
Dyad -.@:~: Making a cycle between the dyads = and ~:
-: Monad %&2 Full
Dyad =&:< Could also use =&< but I'd rather use &: and define & in terms of &:. Similarly for the use of @: vs @.
0:`(*./@:(=`(0: = +&:#)

($:&>)@.(+&:(=&32)&:(3!:0)))&:,)@.(0:`(*./@:=)@.(=&:#)&:$)

See thread describing reimplementation of match
< Monad a:&(] L: 0 _) Full Box
{.@:;&0
Dyad -.@:>: Less than
> Monad {.@:]^:(0: = L.@:]) ] S: _1 Full Open
Dyad -.@:<: Greater than
0 ^ 0 ^ - Reported by Andrew Nikitin here, who cites Two Notes on Notation by Knuth.
<. Monad Reals (not complex) Floor. I'll get to complex in a minute (it's spelled out in the dictionary)
<:@:>.
Dyad >: { , Full Min
<: { ,~
, +/@:* 2: i.@:* _1: ^ <:
>. Monad ) Reals (not complex) Ceiling, I'll get to complex in a minute (it's spelled out in the dictionary)
>:@:<.
Dyad <: { , Full Max
>: { ,~
, +/@:* 2: i.@:* _1: ^ >:
<: Monad -&1 Full Decrement
Dyad < +. = Less or equal
>: Monad +&1 Full Increment
Dyad > +. = Greater or equal
_: Ambivalent _"_ Full Similarly for _9:, _8:, _7:, _6:, _5:, _4:, _3:, _2:, _1:, 0:, 1:, 2:, 3:, 4:, 5:, 6:, 7:, 8:, and 9:
#. Monad 2&#. Full See rshp in the helper function section. Needed to satisfy the sentence "An atomic argument is reshaped to the shape of the other argument." in the definition of dyadic #. in the Vocabulary (1508 100 qdoj '#.').
Dyad (+/@:* */\.@:}.@:,&1)~ rshp
Monad ."1 Full See polynomial inverse on the J forums
Dyad ."1 scalar x (''-:$@[)
# Monad {.!.1@:$ Full Tally is count of first dimenstion
+/@:(1:"_1) Tally is number of items. (could replace 1: with 1 to save ourselves a primitive)
1 #. 1"_1
E. Dyad  [ -:"_ _1 (];.3~ $)~ Full E. has no monadic case as of J6, so this should be a complete replacement. See Splitting string on pattern and the earlier E. sensitive to type of empty vector LHA threads in the Forums.
. Monad /: i.@-@# Full Hook
| Monad %:@* + Full By definition
% * From Zero Divided by Zero by Eugene McDonnell
>. - real numbers Idea from A Formal Description of System/360, Table 1, "Notation", pp. 200. by KenIverson
Dyad -~^:<:^:_ or {:@:(#:~ 0&,)~ Full
-. Monad -~ 1: Full By definition
1 0&I. boolean (*./@e.&0 1) booleans are the most common application of -.
% Monad %~ 1: Full
Dyad * % Full
<.@% Dyad ([: <:@# -~^:<:^:(<_))~
[. Conj. L=: 2 : 'u.' Full Lev, eg k=: + L m=: - L n=: *
]. Conj. D=: 2 : 'v.' Full Dex
]: Adverb Id=: 1 : 'u.' Full Identity
A. Monad ((- i.)@#@x: #. +/@({. > }.)\."1)@(i.~ /:~) Full See Essays/Permutation Index
Dyad (/:^:2:@,/"1@((- i.)@#@x:@] #: [) i.@#) { ] See Essays/Permutations
(] + <:)/\"1@(#:~ (- i.)@#) { ] See PermRevLexRank
~) !@<:@#) (({~ {.)~ , {:@[

$: ({~ <^:3:@{.)~) ])^:(1: < #@])

Full See Essays/Anagram
e. Monad e.&>~/ ; Full =/~ for open y
Dyad +./@:(-:"_ _1)"_1 _ Full +./@:(-:"r/)~ for item rank r
e. Monad e.&>~/ ; Full =/~ for open y
Dyad +./@:(-:"_ _1)"_1 _ Full +./@:(-:"r/)~ for item rank r
+. Dyad ~ , ]) <./)@:, Positive integers. GCD. Algorithm stolen from the second APL image on this page
i. Monad ([:> +/&.>/)@((* _1++/\@#&1)&.>~ 1,~[:*/\.}.) not $0, no negative dimensions scalar: _1++/\@#&1
)"1 full
($ (,~ <:@:{.)^:]@:(*/)) no negative dimensions iterative (similar solution exists for recursive with $:)
+/\&.:>:@:#&0 no negative dimensions Nice use of &. due to RE Boss
Dyad [: +/ [: *./\ ~: scalar x, vector y
#@[ - [: +/ [: +/\. =/ vector x, vector y posted by Roger in the Forums
4 : '(#x) - +/"1 +./\"1 x =/&:(<"(0>.<:#$x)) y' uninvestigated Posted by Roger Hui.
, Monad {~ (<@#: i.@:(*/) )@:$ [: -. 0 e. $
Dyad none
<<Anchor(<;._3)>> <;._3 Dyad :\&>~ ({~ #@:$))^:(#@:[) < [: -. 0 e. [ I think that ;._3 is wrong when 0 e. [ . If that's changed in the implementation, this replacement will have the complete domain.


Also, I should work on making a minimal tacit replacement for ;._3 instead of <;._3. Ideally, we should replace ;. itself (which would have to be explicit).

\ Dyad (;._3) (,@:) (" 0 _) [: -. 0 e. [ See notes re: domain at cut -3 reimplimentation
#^:_1 Dyad .

] # ({.~ #) ) (0 j. [ i. 1:)
 ,~ 1 j. #;._1~@:[

Full (but no !.) See APL expand in J thread in the Forums. (As Henry Rich pointed out, we can treat #^:_1 as a [unnamed] primitive.)
|: Monad .@:$ $ , 2<#@$@] : -: |.@:$ $ ,) i. 2 2
. $ (#. |. |.@#: i.@:(*/)))@:$ full
Dyad ({$) $"1 ] ,;.1~ (((1;'') {~ e.~) i.@:#@:$) 0 = L.@[ :; it just needs some work. Could replace ;.1 with ;.2.
{. Monad ''&$

(($,)~ }.@$)

non-empty y
j. Monad 0j1&* Full
Dyad + j. Uses own monadic definition; that's ok. Ambivalent replacement to j. would be 0j1&* : (+ $:)
* Monad Full Zero Divided by Zero by Eugene McDonnell
D. 1 ~:&0 See wikipedia on abs. This article defines |D.1 -: (%|) except at 0. But since we have 0%|0 then I think |D.1]0 should be 0 (but J gives 1 instead)
(>-<)&0 Real numbers (i.e. 0={:@+.) See [[../../papers/algebra.htm#A.2|Algebra as a Language (Table A.1, 3rd entry)]]
Dyad +&.^. Full Classic sum under log
#.@(*#:) Positive integers "Ethiopian multiplication" or "Russian peasant multiplication"; this terse formulation is due to Arie Groeneveld
/: Dyad /:~i.@# Full Dyad defined in terms of monad (as opposed to other way around in DoJ)
.@\:~
\: Dyad \:~i.@# Full Dyad defined in terms of monad (as opposed to other way around in DoJ)
.@/:~
,: Ambivalent ,&.< see note Not yet analyzed, but if the dyad has a scalar argument, the equivalence only holds with certain ranks (or shapes?) of the other argument.
}. Monad {~ i.&.<:@# 0 < # There are obvious ways to implement }. in general (both monad and dyad), I just think this is a cute use of &.
%: Monad -:&.^. Full Obviously, the monads could be expressed in terms of the dyad (2 & (^@:(%~^.)) or (^%)&2) or the verb could even be made ambivalent 2&$: : (^@:(%~ ^.)). But the first formulation of the monad is a cute use of under.
^&0.5
(] -:@+ %)^:_&1 Non-negative numbers
Dyad ^@:(%~ ^.) Full
^%
p. Dyad ."1)~ Full If we consider all primitive replacements to be acting at the same rank as the original primitive (i.e. if the substitution s for p is understood to have an implicit "p as in s"p) then the rank specifications are unnecessary and may be elided.


Note also that this equation is derivable from the equivalence #.2&$: : (p.~ |."1) given in the entry for #., so this entry may be redundant. Another redundant, but interesting, observation is that since #.#:^:_1 then p.(#:^:_1"0 1 |."1)~.

See the derivation from an earlier discovery and an essay on calculating polynomials in APL where this is referred to as the "internal Ruf-Horn" method

? Dyad {. ?@!@x: A. i. x<:y A example of a J mapping well onto an English expression of a concept: "Take the first N values from a random rearrangement of the range 0..M-1". Again, this replacements assumes that rank 0 is implied (i.e. the ranks of the reimplementation are artificially fixed to the ranks of the primitive, if they don't fall out that way naturally).

Helper functions

Reshape Atomic Arguments:: See dyadic #. in the table above.

   raa   =. ,&< ($&.>~ ((-.@:] {"_1 [ |:@:,:  ({~ 1: <. i.&1)) (#&>)) )  ,&:<&:$
   rshp  =: ((&:>) /) (@: raa f.)