Beauty and the Beast

beauty-and-the-beastFinally, the last accessory I ordered for my Raspberry Pi Zero (that’s the little red thing behind my keyboard) has arrived – an Acer 43″ ET430K monitor. The Zero won’t quite drive this monitor at its maximum resolution of 3840×2160 pixels, but as you can see, you get enough real estate to do real graphics with “ASCII Art” (well, Unicode Art, anyway)!

Some readers will recognise the image as the famous Mandelbrot Set, named after the mathematician Benoit Mandelbrot, who studied fractals. According to Wikipedia a fractal is a mathematical set that exhibits a repeating pattern displayed at every scale – they are interesting because they produce patterns that are very similar to things we can see around us – both in living organisms and landscapes – they seem to be part of the fundamental fabric of the universe.

Fractals are are also interesting because they produce images of staggering beauty, as you can see on the pages linked to above and one of our rotating banner pages, where a one-line form of the APL expression which produced the image is embedded:

Website_banner_MbrotW

The colourful images of the Mandelbrot set are produced by looking at a selection of points in the complex plane. For each point c, start with a value of 0 for z, repeat the computation z = c + z², and colour the point according to the number of iterations required before the function becomes “unbounded in value”.

In APL, the function for each iteration can be expressed as {c+⍵*2}, where c is the point and ⍵ (the right argument of the function) is z (initially 0, and subsequently the result of the previous iteration):

      f←{c+⍵*2} ⍝ define the function
      c←1J1     ⍝ c is 1+i (above and to the right of the set)
      (f 0)(f f 0)(f f f 0)(f f f f 0) (f f f f f 0)
1J1 1J3 ¯7J7 1J¯97 ¯9407J¯193

If you are not familiar with complex numbers, those results may look a bit odd. While complex addition just requires adding the real and the imaginary parts independently, the result of multiplication of two complex numbers (a + bi) and (c + di) is defined as (ac-db) + (bc+ad)i. Geometrically, complex multiplication is a combined stretching and rotation operation.

Typing all those f’s gets a bit tedious, fortunately APL has a power operator , a second-order function that can be used to repeatedly apply a function. We can also compute the magnitude of the result number using |:

      (|(f⍣6)0)(|(f⍣7)0)
8.853E7 7.837E15

Let’s take a look at what happens if we choose a point inside the Mandelbrot set:

      c←0.1J0.1
      {|(f⍣⍵)0}¨ 1 2 3 4 5 6 7 8 9 10
0.1414 0.1562 0.1566 0.1552 0.1547 0.1546 0.1546 0.1546 0.1546 0.1546

Above, I used an anonymous function so I could pass the number of iterations in as a parameter, and use the each operator ¨ to generate all the results up to ten iterations. In this case, we can see that the magnitude of the result stabilises, which is why the point 0.1 + 0.1i is considered to be inside the Mandelbrot set.

Points which are just outside the set will require varying numbers of applications of f before the magnitude “explodes”, and if you colour points according to how many iterations are needed and pick interesting areas along the edge of the set, great beauty is revealed.

1200px-GalaxyOfGalaxies

The above image is in the public domain and was created by Jonathan J. Dickau using ChaosPro 3.3 software, which was created by Martin Pfingstl.

Our next task is to create array of points in the complex plane. A helper function unitstep generates values between zero and 1 with a desired number of steps, so I can vary the resolution and size of the image. Using it, I can create two ranges, multiply one of them by i (0J1 in APL) and use an addition table (∘.+) to generate the array:

      ⎕io←0 ⍝ use index origin zero
      unitstep←{(⍳⍵+1)÷⍵}
      unitstep 6
0 0.1667 0.3333 0.5 0.6667 0.8333 1
      c←¯3 × 0.7J0.5 - (0J1×unitstep 6)∘.+unitstep 6
      c
¯2.1J¯1.5 ¯1.6J¯1.5 ¯1.1J¯1.5 ¯0.6J¯1.5 ¯0.1J¯1.5 0.4J¯1.5 0.9J¯1.5
¯2.1J¯1   ¯1.6J¯1   ¯1.1J¯1   ¯0.6J¯1   ¯0.1J¯1   0.4J¯1   0.9J¯1  
¯2.1J¯0.5 ¯1.6J¯0.5 ¯1.1J¯0.5 ¯0.6J¯0.5 ¯0.1J¯0.5 0.4J¯0.5 0.9J¯0.5
¯2.1      ¯1.6      ¯1.1      ¯0.6      ¯0.1      0.4      0.9     
¯2.1J00.5 ¯1.6J00.5 ¯1.1J00.5 ¯0.6J00.5 ¯0.1J00.5 0.4J00.5 0.9J00.5
¯2.1J01   ¯1.6J01   ¯1.1J01   ¯0.6J01   ¯0.1J01   0.4J01   0.9J01  
¯2.1J01.5 ¯1.6J01.5 ¯1.1J01.5 ¯0.6J01.5 ¯0.1J01.5 0.4J01.5 0.9J01.5

The result is subtracted from 0.7J0.5 (0.7 + 0.5i) to get the origin of the complex plane slightly off centre in the middle, and multiplied the whole thing by 3 to get a set of values that brackets the Mandelbrot set.

Note that APL expressions are typically rank and shape invariant, so our function f can be applied to the entire array without changes. Since our goal is only to produce ASCII art, we don’t need to count iterations, we can just compare the magnitude of the result with 9 to decide whether the point has escaped:

      9<|f 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
      9<|(f⍣3) 0 ⍝ Apply f 3 times
1 1 1 0 0 0 1
1 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
1 0 0 0 0 0 0
1 1 1 0 0 0 1

We can see that points around the edge start escaping after 3 iterations. Using an anonymous function again, we can observe more and more points escape, until we recognise the (very low resolution) outline of the Mandelbrot set:


      ]box on
      {((⍕⍵)@(⊂0 0))' #'[9>|(f⍣⍵)0]}¨2↓⍳9
┌───────┬───────┬───────┬───────┬───────┬───────┬───────┐
│2######│3  ### │4      │5      │6      │7      │8      │
│#######│ ######│   ### │    #  │    #  │    #  │    #  │
│#######│#######│ ##### │  #### │  #### │   ### │   ### │
│#######│#######│###### │ ##### │ ##### │ ##### │ ####  │
│#######│#######│ ##### │  #### │  #### │   ### │   ### │
│#######│ ######│   ### │    #  │    #  │    #  │    #  │
│#######│   ### │       │       │       │       │       │
└───────┴───────┴───────┴───────┴───────┴───────┴───────┘

The last example allowed me to sneak in a preview of the new “at” operator coming in Dyalog v16.0. It is a functional merge operator that I am using to insert the formatted right argument (the number of iterations) into position (0 0) of each matrix.

If I use our remote IDE (RIDE) on my Windows machine and connect to the Pi, I can have an APL session on the Pi with 3840×2160 resolution. In this example, I experimented with grey scale “colouring” the result by rounding down and capping the result at 10, and using the character ⍟ (darkest) for 0, ○ for 1-5, × for 6-9, and blank for points that “escaped”, by indexing into an array of ten characters:

      '⍟○○○○○×××× '[10⌊⌊|(f⍣9)c]

Who needs OpenGL?! (click on the image to enlarge)

mandelbrot-ride4

The 2016 Year Game

Our 2016 Year Game was launched in January 2016 and ran until the end of the year. The idea was simple – to find APL expressions involving exactly the digits 2 0 1 6 in that order to equal the numbers 0 to 100 using the fewest characters possible. The minimum number of characters for an expression is 5 (the four digits 2 0 1 6 and a single primitive function/operator) so the smallest number of characters that a possible solution can have is 505.

A lovely elegant solution was pointed out by Lars Stampe Villadsen:

      ⎕IO←0
      {⍪⍳+/⍵*⌽⍵}2 0 1 6

and Bernard Legrand submitted two one-line solutions:

      (⍴⍬),⍳¯20+!1-⍨6

and

      (⍴⍬),⍳⍴'Be happy: this solution to Game 2016 will be the most stupid one, but it needs only five APL symbols'

These three each return all the numbers from 0 to 100. Not valid submissions for this particular game, but I did find them rather pleasing. Anthony Cipriano was inspired to go one step further and submitted an expression that creates the first 8 Fibonacci numbers:

      (⊢,(+/{(¯2∘↑)⍵}))/(⊂0 1),⍨⍳6

The wonderfully varied ways in which APL can be used (and in which APL users think!) was illustrated beautifully by some of the solutions. Although some numbers were attained in the same way by everyone (36, for example, was always 20+16), others lent themselves to multiple solutions. No-one managed to calculate 100 in fewer than 7 characters, but the 7-character answers included 20∧⌹.16, 20ׯ1+6, -20×1-6, 20×-1-6, ¯20×1-6 and various others on the same theme. Unity experienced similar creativity, with 1 being reached in the minimum possible number of characters (5) using ×2016, 201≢6, 20>16, 20≠16, 2<016, etc.

It was clear early on that submissions fell into two distinct groups – those who wrote a program to find the expressions and those who derived their expressions manually. I found the creativity evident in the manually-derived solutions very satisfying; the results may not have been as terse as those resulting from programs, but the individuality of the creators shows people inspired by their subject matter. Who can fail to appreciate the thought process behind arriving at 96 using (×/+\+\(!2 0 1))+6 rather than the more prosaic ⌈⍟!20+16 or ⎕IO-⍨+⍨20+16 rather than 20+⌈○16 for 71?

Having said that, the goal was conciseness and individual character counts are now tabulated on the 2016 Year Game page; an amalgamation of the lowest-character expressions that anyone achieved can also be downloaded from this page. Congratulations to Jonas Stensiö and Veli-Matti Jantunen, who both achieved the same character count as the amalgamated minimum (693).

(most names omitted to protect the not-so-innocent)

It’s APL…but not as we know it!

by the Dyalog Duck
As the party behind Dyalog’s Twitter account I often search our feed for #APL or just APL to see if anyone is talking about us or APL in general and I am frequently surprised by what pops up. We have often had a giggle in the office over some of the things we find and it was suggested to me that others might find these interesting too hence this rather random blog post.

Probably the most well known alternative APL is the container shipping and ocean freight company American President Lines (@APLShipping). The Dyalog staff often stand at the railway crossing on our way to the village bakery for lunch and chuckle at the APL containers whizzing past on the train … we are easily amused!

My personal favourite other APL has to be Athletic Propulsion Labs (@APLrunning) with their ‘oh so gorgeous running shoes’ … their trainers are things that I desire on a daily basis!! For you non-shoe lovers out there, they are also the official footwear supplier for the Renault Sport Formula One team.

The APL alter-ego that comes up most frequently in my Twitter search is a musical one … it seems we also share #APL with a 4 member boyband from South Korea. This APL (@APL_world) is extremely popular with teenage girls from Japan and Korea who frequently tweet their undying love for the boys … it makes you wonder who thought it was a good idea to name a teenage pop sensation after a programming language!

Still in the musical world we also have an uber cool APL namesake in rapper apl.de.ap (@apldeap) who is also one of the founding members of the Black Eyed Peas.

Another APL that we are proud to share #APL with is the John Hopkins University Applied Physics Laboratory (@JHUAPL) in Maryland USA. NASA’s Juno spacecraft successfully entered Jupiter’s orbit in July carrying an instrument suite that includes the Jupiter Energetic Particle Detector Instrument (JEDI) built by the Johns Hopkins Applied Physics Laboratory. APL in space … how cool is that!

twitterapl_6The Association of Professional Landscapers (@The_APL) are the APL that fill my screen with greenness, tweeting some amazing photos of their garden and landscaping projects.

twitterapl_7Finally, if you are having a bad day and just need cute puppies and kittens to coo over, the Animal Protective League (@APLSpringfield) in Springfield USA is the perfect APL for you. As well as providing cuteness overload they also do a great job re-homing animals in need.

So there you go folks … a few of my favourite alternative APLs for your amusement. Of course there are lots of other APLs out there in Twitterland but frankly most them are just not that interesting … and a few, to spare your blushes, are just not the sort of thing we want to share!

APL Puns

In the Beginning

floor
ceiling
log

and were punnish when the notation was introduced in 1962. They have long since gone mainstream, used even by respectable mathematicians and computer scientists.

To see why is a pun, see the Vector article My Favourite APL Symbol.

•         •        •        •         •

The following are a joint effort by the Dyalog team, many derived after a sumptuous dinner and a few glasses of wine. Column 0 are valid APL expressions. For an enhanced experience may we suggest covering column 1 as you read column 0 for the first time.

In Modern Times

⊃⎕A~'L' the first no el
⍴⍴⍴'your boat' rho rho rho your boat
*⍣¯1⊢fly+fly log of the flies
{⍺←23 ⋄ (2÷(○1)*0.5)×-/⍵×(⍵*2×⍳⍺)÷
(!⍳⍺)×1+2×⍳⍺}ghanistan
erf ghanistan
↑^≡ mix and match
>/+/∘⎕UCS¨'the parts' 'the whole' the sum of the parts is greater than the whole
?⍨2e9 a big deal
○1 APL π
2(⌷⍤1)2 3 4⍴○1 a slice of APL π
0 0⍉3 4⍴○1 another slice of APL π
easy←○1 easy as π
{4×-/÷1+2×⍳⍵}1e6 a π long in the making
pike; see APL Quotations and Anecdotes
spike
pine
spine
Concorde taking (and showing) off
uh-oh
{⍵⌷⍨⊂?⍨≢⍵} degrade
bb∨~bb two b or not two b
bb≥bb two b or not two b
×× sign of the times
a←2÷⍨3 4⍴⍳12 ⋄ *○0j1×a show off
a←2÷⍨3 4⍴⍳12 ⋄ *○0j1×a+2e9 shameless show off
⍎turtles←'⍎turtles' it’s turtles all the way down…

In Honour of a Certain Movie Series

0⍴'menace' I. The Empty Menace
⊢⎕ns¨ 2⍴⎕this II. Tack of the Clones
⌽'htxiS'~'x' III. Reverse of the Sith
⎕io←~⎕io IV. A New Beginning
{'Jedi'⊢1e3×○R} V. The M π R Strikes from the Back
{'Jedi'} VI. Return Jedi
(+⌿÷≢)3 4 5⊣⎕dl 10 VII. The Fork Awakens
may←+⌿÷≢ ⋄ may∘∪ may the fork be with you
0 1 2 3 (⌊/⍬) 5 6 the fourth is strong with this one
4 4 4 4 (⌊/⍬) 4 4 I feel a great disturbance in the fours
1=?2e9 this is not the number you are looking for
1=?2e9 in my experience, there’s no such thing as luck
Luke.## I AM your father
4 ⊃ 0 1 2 3 'dark side' vier ist the path to the dark side
x{0.5×⍵+⍺÷⍵}⍣≡darkside do not underestimate the power of the dark side
⎕ct←1 I find your lack of faith disturbing
0.2 ∊ ÷3 1 4 1 9 2 6 3 8 9 7 9 I find your lack of a-fifth disturbing
{0::⍺⍺~⍵ ⋄ ⍺⍺ ⍵} do, or do not; there is no :Try
R2D2
>⍝ Help me, Obi-Wan Kenobi, you’re my only hope
⊂○⊃ Princess Leia
<○> Yoda
○>--- Death Star
>∘< X-wing fighter
⊢○⊣ tie fighter
○⍨ tie fighter in stealth
⊢○⊣ 1 π fighter
⊣⍲⍲ ATAT
Ewok
Wookie
imperial cruiser
⍋⍒ imperial cruisers colliding
┌──┬──┬──┬──┬──┬──┬──┬──┐
│⊢ │⍒ │⍒⍒│⍋⌽│⌽ │⍋ │⍋⍒│⍒⌽│
├──┼──┼──┼──┼──┼──┼──┼──┤
│⍒ │⍒⍒│⍋⌽│⊢ │⍒⌽│⌽ │⍋ │⍋⍒│
├──┼──┼──┼──┼──┼──┼──┼──┤
│⍒⍒│⍋⌽│⊢ │⍒ │⍋⍒│⍒⌽│⌽ │⍋ │
├──┼──┼──┼──┼──┼──┼──┼──┤
│⍋⌽│⊢ │⍒ │⍒⍒│⍋ │⍋⍒│⍒⌽│⌽ │
├──┼──┼──┼──┼──┼──┼──┼──┤
│⌽ │⍋ │⍋⍒│⍒⌽│⊢ │⍒ │⍒⍒│⍋⌽│
├──┼──┼──┼──┼──┼──┼──┼──┤
│⍋ │⍋⍒│⍒⌽│⌽ │⍋⌽│⊢ │⍒ │⍒⍒│
├──┼──┼──┼──┼──┼──┼──┼──┤
│⍋⍒│⍒⌽│⌽ │⍋ │⍒⍒│⍋⌽│⊢ │⍒ │
├──┼──┼──┼──┼──┼──┼──┼──┤
│⍒⌽│⌽ │⍋ │⍋⍒│⍒ │⍒⍒│⍋⌽│⊢ │
└──┴──┴──┴──┴──┴──┴──┴──┘

 

 

 

climatic space battle

Simply A-maze-ing

maze

One of many things I like about APL is that it’s fun to use for recreational computing. I will frequently happen upon an interesting problem, puzzle, or piece of code and consider how I might implement it in APL.

I was thinking about how to generate mazes for an idea I have about a game to help kids learn APL (that may be a topic for a future blog entry). Anyhow, I found an interesting web page about maze generating algorithms where the author found one, the “Growing Tree Algorithm“, to be of particular interest. His page included roughly 100 lines Ruby code to implement the algorithm. The algorithm can be boiled down to:

  • Seed a list of visited cells with a cell selected at random
  • While there are unvisited cells
    • If the current cell has any unvisited neighboring cells
      • Select one at random
      • Remove the wall between the cells
      • Add the new cell to the list of visited cells
    • Otherwise backtrack (drop from the visited cell list) until you find a cell with an unvisited neighbor

Here’s a clip of the algorithm implemented in APL building a 10×10 maze.
Notice how whenever it hits a “dead end” it backtracks to the last cell that hasn’t been visited.

What might an APL approach to this algorithm look like? How to represent the maze? My first thought was to separate the maze generation from the drawing. After an hour (or so ;-) ) of tinkering, I’d come up with something that seemed to work pretty well and took about a dozen lines of code.

When I originally thought about writing this blog entry, I was going to launch into a discussion of the code and I realized that it might get lengthy and (egad!) boring. So instead, I’ll highlight a couple of the clever bits, show you the core maze generation code, and point you at the complete namespace for your own amusement and experimentation.

First the clever bits (at least I hope they’re clever)…

  • Represent the cells of the maze as an integer matrix where each element is an encoding of the walls surrounding each cell.  Use powers of 2 for the encoding.
  • Precalculate the indices of the neighboring cells around each cell so the core loop only has to use indexing and no on-the-fly computation.
  • Write a function to remove the common wall between two cells. I originally named the function “Reagan” (after President Reagan’s 1987 exhortation “Mr. Gorbachev, tear down this wall”), but in the spirit of political mindfulness, I renamed it “dewall”.

The core code for the maze generation looks like this:

∇ cells←maze size;valid;neighbors;dewall;visited;current;n;choices;next
 ⍝ Maze - modeled from http://weblog.jamisbuck.org/2011/1/27/maze-generation-growing-tree-algorithm
 ⍝ BPB  - Dec2014
 ⍝ size  - size of the maze in rows/cols
 ⍝ cells   - (2⍴size) integer matrix describing the walls around each cell using powers of 2
 ⍝       1
 ⍝     ┌───┐         ┌───┐
 ⍝   8 │   │ 2       │   │ = 11 = 1 + 2 + 8
 ⍝     └───┘
 ⍝       4
  size←2⍴size  ⍝ set size to square if singleton supplied as argument     

  valid←{{⍵/⍨⍵≢¨⊂⍬}size∘{(0∊⍵)⍱⍵∨.>⍺:⍵ ⋄ ⍬}¨⍵} ⍝ determine if a maze coordinate is valid
  neighbors←valid¨↓(⍳size)∘.+,1 ¯1∘.×1 0⌽¨⊂1 0 ⍝ calculate neighbors for each cell
     
  dewall←{{⍵[2]=0:{(1=⍵)⌽4 1}⍵[1] ⋄ {(1=⍵)⌽2 8}⍵[2]}⍺-⍵}  ⍝ remove wall between cells
     
  cells←size⍴15 ⍝ all cells start with 4 walls
     
  visited←,⊂?size ⍝ random starting cell
     
  :While 15∊cells       ⍝ while we still have cells to examine
      current←1↑visited   ⍝ pop the most recent cell
      :If 0=n←⍴choices←cells{⍵/⍨15=⍺[⍵]}current⊃neighbors ⍝ does it have any unvisited neighbors?
          visited↓⍨←1       ⍝ if none, backtrack
      :Else
          visited,⍨←next←choices[?n] ⍝ otherwise, add the new cell to the front of the list
          cells[next current]-←⊃next⊃.dewall current ⍝ update cell values for which wall was removed
      :EndIf
  :EndWhile
∇

You can get all the code in my maze generating namespace from GitHub. Save a local copy and use the SALT Load command to load it into your workspace, or just cut and paste it into your own namespace script with the editor. The maze namespace contains the following functions of interest:

 

      intmat←{animate} maze size
  • animate is an optional Boolean to indicate whether to animate the maze generation
  • size is the size (rows,cols) of the maze to generate; a single number generates a square maze
  • intmat is the integer matrix representation of the maze

For example: mat←1 maze 10 animates and generates a 10×10 maze

 

      z←{line} draw intmat
  • line is an optional Boolean that indicates:
    • 1 = use line-drawing characters
    • 0 = use ASCII characters
  • intmat is an integer matrix representation of a maze
  • z is the drawing of the maze in ASCII or line-drawing characters

For example: pic←1 draw mat produces a line-drawing of the maze generated in the example above

 

      z←html intmat
  • intmat is an integer matrix representation of a maze
  • z is the HTML necessary to render the maze in a web browser. Save it to a native file and open the file in your browser.

For example: h←html mat produces an HTML representation of the maze generated in the example above