Skip to content

Instantly share code, notes, and snippets.

@deadpixi
Last active October 15, 2022 14:58
Show Gist options
  • Save deadpixi/7047ac40f026503b2dced261f9a1fac2 to your computer and use it in GitHub Desktop.
Save deadpixi/7047ac40f026503b2dced261f9a1fac2 to your computer and use it in GitHub Desktop.
UUIDv4 in three different array languages.

UUIDv4 Generation in Three Different Array Languages

Here we see the same UUIDv4 generation function written in three different APL(-like) languages: APL, J, and K.

The algorithm is very simple, but one that lends itself well to implementation in an array language:

  • Generate a list of 36 random numbers between 0 and 15.
  • Transform each of those digits into a single-character string of the corresponding hex digit.
  • Join those characters together into a 36-character string.
  • Replace some of the characters with dashes.
  • Replace the character representing the version nybble with 4 (to indicate a version 4 UUID).
  • Constrain the character whose top two bits represent the variant to one that indicates the UUID is an RFC4122 UUID.
  • Return the string.

The same algorithm is implemented in all three languages. Comments for each step have been provided.

APL

First, in APL (as a dfn). This was tested in Dyalog APL, and can be tested in your browser at TryAPL.

Note that you might need to take care with multi-line input.

uuid{
   Set our index origin to 0, that is, indices start at 0.
   The default is that indices start at 1.
  ⎕IO0
  
   The hex digits in order.
  h'0123456789abcdef'
  
   Create a string 36 characters long, each on selected at random
   from the hex digits by selecting 36 random numbers from 0 to 15
   and using those as indices into the hex digits above.
  th[?3616]
  
   Replace the digits where dashes should be with dashes.
   And force the version nybble to be 4, meaning random UUID.
  t[8 13 18 23 14]'----4'
  
   Force the variant nybble to be "RFC 4122".
  t[19]'8888888889abbbbb'[ht[19]]
  
   Return the UUID string.
  t
}

J

J is a direct descendant of APL, designed by the inventor of APL Kenneth Iverson and his colleague Roger Hui. It is strongly related to Iverson's "Rationalized APL" concept, and could perhaps be considered "Rationalized APL with ASCII syntax".

This was tested with j903, available from J Software.

NB. Define a function called uuid.
NB. The 3 means it's a function, the 0 means that the body is included below.
uuid =: 3 : 0
  NB. The hex digits in order.
  h=.'0123456789abcdef'
  
  NB. Create a string 36 characters long, each on selected at random
  NB. from the hex digits by selecting 36 random numbers from 0 to 15
  NB. and using those as indices into the hex digits above.
  t=.(?36#16){h
  
  NB. Replace the digits where dashes should be with dashes.
  NB. And force the version nybble to be 4, meaning random UUID.
  t=.'----4' 8 13 18 23 14}t
  
  NB. Force the variant nybble to be "RFC 4122".
  NB. As this is the last expression, return the result.
  ((h i.(19{t)){'8888888889abbbbb') 19}t
)

K

K is a language often described as "APL-like", though it uses lists as its fundamental data structure rather than arrays. It was created by Arthur Whitney, who was active in the APL community and famously wrote the "first version" of J.

This was tested with the open-source Kona interpreter, which aims to be compatible with K2/K3.

uuid:{
  / The hex digits in order
  h:"0123456789abcdef"
  
  / Create a string 36 characters long, each on selected at random
  / from the hex digits by selecting 36 random numbers from 0 to 15
  / and using those as indices into the hex digits above.
  t:h[36 _draw 16]
  
  / Replace the digits where dashes should be with dashes.
  / And force the version nybble to be 4, meaning random UUID.
  t[8 13 18 23 14]:"----4"
  
  / Force the variant nybble to be "RFC 4122".
  t[19]:"8888888889abbbbb"[h?t[19]]
  
  / Return the UUID string.
  t}

Conclusion

As you can see, all three languages lend themsleves well to expressing this algorithm. There are definite differences between the three languages however (and dialectical differences within them). APL and J are far more similar to each other than they are to K, for example.

At any rate, it is worth it to study array programming, even if you don't think it would be immediately applicable to your daily life. There is much beauty in them, and they are a good way to expand how you think about problems. For certain ways of solving a problem, like the one shown here, there is a very strong correspondance to the way you might think about solving the problem to the way it is expressed in the language.

@PuercoPop
Copy link

PuercoPop commented Oct 15, 2022

I was trying to solve this by generating an array of dashes, then have a mask for the dash positions, invert it and then replace the characters in the mask with a random hex digit. Something like

h←'0123456789abcdef'
{h[?≢h]}@{~9 14 24 15∊⍨⍳36} 36⍴'-'

Too bad the left argument to @ is a value not a function so its only evaluated once.

I haven't looked into moving the hex digit convertion to use encode(⊥) but there can be some savings there.

APL cart has a solution, not sure if for v4 UUIDs, I still have to unpack it https://aplcart.info/?q=%40%20UUID#

'-'@(4+5×⍳4)⊢(⎕D,⎕C⎕A)[4(9+|)@20⊢5@15?36⍴16]

Edit:

We can avoid bracket indexing to pick the random hex character using h⌷⍨?≢h

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment