Quicksort in APL Revisited

A message in the Forum inquired on sorting strings in APL with a custom comparison function.

First, sorting strings without a custom comparison function obtains with a terse expression:

      {⍵[⍋↑⍵]} 'syzygy' 'boustrophedon' 'kakistocracy' 'chthonic'
┌─────────────┬────────┬────────────┬──────┐
│boustrophedon│chthonic│kakistocracy│syzygy│
└─────────────┴────────┴────────────┴──────┘

Sorting strings with a custom comparison function can also be accomplished succinctly by simple modifications to the Quicksort function

Q←{1≥≢⍵:⍵ ⋄ S←{⍺⌿⍨⍺ ⍺⍺ ⍵} ⋄ ⍵((∇<S)⍪=S⍪(∇>S))⍵⌷⍨?≢⍵}

in a Dyalog blog post in 2014. A version that accepts a comparison function operand is:

QS←{1≥≢⍵:⍵ ⋄ (∇ ⍵⌿⍨0>s),(⍵⌿⍨0=s),∇ ⍵⌿⍨0<s←⍵ ⍺⍺¨ ⍵⌷⍨?≢⍵}

The operand function ⍺ ⍺⍺ ⍵ is required to return ¯1, 0, or 1, according to whether is less than, equal to, or greater than . In QS, the phrase s←⍵ ⍺⍺¨ ⍵⌷⍨?≢⍵ compares each element of against a randomly chosen pivot ⍵⌷⍨?≢⍵; the function then applies recursively to the elements of which are less than the pivot (0>s) and those which are greater than the pivot (0<s).

Example with numbers:

      (×-)QS 3 1 4 1 5 9 2 6 5 3 5 8 97 9
1 1 2 3 3 4 5 5 5 6 8 9 9 97

      3(×-)4
¯1
      3(×-)3
0
      3(×-)¯17
1

Example with strings:

      strcmp←{⍺≡⍵:0 ⋄ ¯1*</⍋↑⍺ ⍵}

      'syzygy' strcmp 'syzygy'
0
      'syzygy' strcmp 'eleemosynary'
1
      'syzygy' strcmp 'zumba'
¯1

      strcmp QS 'syzygy' 'boustrophedon' 'kakistocracy' 'chthonic'
┌─────────────┬────────┬────────────┬──────┐
│boustrophedon│chthonic│kakistocracy│syzygy│
└─────────────┴────────┴────────────┴──────┘

A more efficient string comparison function is left as an exercise for the reader. :-)

A message from the CTO

Hello! Further to Morten’s kind words of introduction, I’d like to take this opportunity to introduce myself as the new CTO of Dyalog Ltd.

About me

I’m a newcomer to APL. When I started working for Dyalog in 2010 I had only seen the Game of Life video, an intriguing but baffling glimpse into a world of squiggles. But I soon got the opportunity to learn from some giants of the language, and came to appreciate the power and beauty of the notation. Later I learned that, despite its venerable history, the language is not set in stone; with care and attention we can develop and extend it to increase its power, relevance and performance, without sacrificing its elegance and simplicity.

We — not just Dyalog, but the wider APL community — are guardians of a rare thing: a language born more than 50 years ago that is not just relevant and useful today, but groundbreaking in the way it embodies data parallelism from the ground up in a simple, consistent notation.

Before working at Dyalog I spent 13 years developing compilers, optimisers and debuggers for more mainstream programming languages, including C and Java. This has given me a good insight into how to get the best performance out of modern computer hardware, and I’ve made it my continuing mission to help bring that level of performance to APL!

My rôle

As CTO I’ll be responsible for day-to-day management of the core interpreter development team, and for the overall technical strategy of the company. This strategy must include getting the maximum performance out of current and future hardware, but also:

  • Keeping the quality of the product as high as possible.
  • Embracing new platforms and attracting new users.
  • Improving our development tools, and making it easier to create and deploy new applications.
  • Ensuring that Dyalog APL can interoperate smoothly with modern frameworks and services.
  • Continuing to look at new ways of (carefully!) extending and improving the core APL language.

I’m looking forward to working on this alongside the “new” CXO, Morten. At Dyalog we take a lot of care in the design of new features, and I firmly believe that a lively discussion between CXO (representing the needs of the customer) and CTO (representing the language designers and implementers) will only improve the quality of the designs we come up with.

On the road

In the future I expect to spend a bit more time out and about, showing off Dyalog APL, and talking to all of you about your own needs and expectations of the product. In particular, this year I’ll be at DYNA16 in Princeton in April, and the Dyalog ’16 User Meeting in Glasgow in October. I look forward to seeing, or meeting, all of you soon!

Posted in CTO

Hacking with APL

Vassar Hackathon Poster

Vassar Hackathon Poster

Thanks to our dear friend Dr. Ray Polivka, Dan Baronet and I had the opportunity to travel to Vassar College to participate in their Community Hackathon held on 5-6 February 2016.

“What’s a hackathon?” you ask?
Well, we did too, as we’d never participated in one before.  :)
According to the Hackathon’s announcement:

“CommunityHack is a way to bridge the gap between Vassar CS Majors and Vassar students in other departments as well as local high school and community college students in order to provide them with the opportunity to explore innovative applications of Computer Science. Dance, music, art, video games? CS can be incorporated into all of that and more!”

StuCommunityHack_Sponsorsdents from Vassar as well as nearby colleges and high schools were invited to attend. In other words, it was a great opportunity to introduce APL to a new generation.  As this was our first Hackathon, we had no idea what to expect.  Laura, the Hackathon’s organizer, did a wonderful job organizing the event and making us feel welcome. We were invited to give an hour long presentation and Dyalog was listed as an event sponsor.

The Hackathon was a 24 hour event where students were encouraged to split up into groups and pick a problem to solve.  During the course of the event, presentations were made on a variety of subjects including “Autonomous Robots Test Ideas About the Evolution of Brains”, “How to make games quick!”, “Virtual Reality”, and of course “Hacking with APL”. Friday evening started with introductions and ice-breakers. During our introduction, I was able to talk a bit about APL and the presentation we would be making on Saturday. Apparently this generated some interest as a number of students came up to Dan, Ray, Jon McGrew and me to ask about APL. We spent several hours showing them APL, to which they seemed eagerly receptive.

I had the pleasure of working with Grace, a CS sophomore, to implement APL (A Puppy Language) in APL. Her project idea was to write an application for potential puppy owners to use so they could get an idea of the responsibility of owning and caring for a puppy. We worked into the wee hours of the night and wound up implementing a multi-threaded domain-specific-language (DSL) where the “puppy”, running in a separate thread, would react to commands typed into the APL session. Negative actions and ignoring the puppy would cause the the puppy’s happiness points (PHPs) to decrease whereas positive actions would increase PHPs.   Grace seemed to really enjoy working with APL and returned to the hackathon twice on Saturday as her schedule permitted to continue work on her project.

Saturday, I was slightly concerned that following a talk on virtual reality, APL might not seem all that “cool”, but my fears were allayed for, as I was waiting before my presentation, several students asked the person at the registration desk specifically about the APL presentation.

HackingWithAPL

The presentation went rather well.  Watching the jaw-dropping “Wow!” expressions on the faces of many of the students as we showed the power of APL notation made me reminisce back to the time when I first learned APL and was amazed at what I could do with a computer.  It also reminded me how blessed I’ve been to have used APL throughout my career.

Our participation in the Hackathon was a great experience. We were able to show Dyalog to close to 100 students, promote the upcoming APL Problem Solving Competition, and encourage people to download and try Dyalog – we had 18 student downloads over the Hackathon weekend. This may have been our first Hackathon, but I’m certain it won’t be our last.

On a personal note, after Dan and I drove up to Montreal to spend the upcoming week working with the APL Tools Team, I received a very nice email from Grace where she wrote “I just wanted to thank you so much for taking the time to work with me on puppy.dws – it is currently my favorite thing that I have ever made.” and “It was really fun working in APL, and I will definitely check out the Dyalog competition.”

HackingWithAPL3