Downloading Resources from Cross-Origin Requests

If you decide to have a separate web- and backend- tier, cross-origin HTTP requests cause no end of difficulties in a variety of unlikely ways. I've written before about using CORS headers to mitigate some of them but here's yet another. It surfaces whenever you try to use the download attribute in an anchor tag but where the URI resource lives on the backend and not the web server. For example, I host tunes on my server and I want users to be able to download the tune scores which are in pdf format:

    
  download pdf

The intention is that when the user selects the link, the browser will know that the resource is intended to be downloaded and will use the download attribute value as the file name. This indeed happens when the resource is hosted locally, but it no longer does so in the most recent versions of Chrome when it's hosted remotely. It seems as if the Chrome developers have now implemented a rather awkward algorithm in the html5 spec designed to mitigate possible security dangers in downloading files from untrusted sites. This is ostensibly because a hostile server could try to inveigle a user into unwittingly downloading private information (thinking it came from the hostile server itself) which could then perhaps be re-uploaded to that server. The solution is to use the Content-Disposition HTTP header when serving up the resource to suggest a file name. For example:

    
  Content-Disposition: attachment; filename=mytune.pdf

Conforming browsers should then use this name when they interpret the download attribute in the anchor tag.

Functional Programming in Scala

Richard Feynman said what I cannot create I do not understand, notoriously misquoted by Craig Venter as what I cannot build I do not understand when he inserted it as a watermark into the DNA of his bacterium with an artificial genome. But Venter has a software engineering approach to biology - the bacterium has a computer for a parent and he went through a series of debugging cycles before eventually the organism would 'boot-up'. His statement is fundamental to the proper understanding of all sorts of disciplines, but non more so than software development.

Manning have today published Functional Programming in Scala by Rúnar Bjarnason and Paul Chiusano. The book is constructed around a carefully graded sequence of exercises where you find yourself attempting to build things of increasing complexity. It's aim is to teach functional programming concepts through the medium of Scala and this means that you must construct your programs from pure functions, free of side effects.  If, like me, you come from an OO background, this causes a massive rethink - there are whole swathes of the language that you just don't use.  For example, you can't reassign a variable; your functions mustn't throw exceptions; you will not develop class hierarchies.  You will use case classes but their use is restricted to the creation of algebraic data types. I found that I had to go through the exercises very slowly and deliberately.  The introductory exercises are relatively straightforward and fun to attempt and your confidence grows, but I found that the material quite soon becomes very challenging indeed.  In fact, whilst studying the various revisions of this book, I was reminded yet again of Feynman - his algorithm:

    Write down the problem.

    Think real hard.

    Write down the solution.

This, as opposed to an approach I've tended to used in OO:

   
    Write down the problem.

    do {
        Think a little bit.

        Type a little bit.

        See what happens

    } until problem solved.

    Write down the solution.  

The problem when lesser mortals attempt Feynman's algorithm is that it tends not to terminate. When it works, however, you often tend to end up with an elegant, terse solution, often incomprehensible to the casual reader. But the main thing is that you gain enormous understanding - you will get no benefit unless you attempt the exercises.

The material is presented tersely, with just enough explanation of the concept and the scala syntax you need to express it.  Some of the problems are very tricky and I would occasionally find myself pondering single questions for an hour or two, struggling to get the types to match.  The satisfaction when you do tease out a solution is immense.  The accompanying material on the web site includes pro-forma Scala exercise files for each chapter with placeholders for the answer, usually in the fom of stubs like this:

    def compose[A,B,C](f: B => C, g: A => B): A => C =
        ??? 

If you get stuck, hints and solutions for each question are provided, as is a fully fleshed-out answer file for each chapter.  Some later chapters use material developed in earlier ones and so, when attempting a new chapter, you need either to have completed the previous ones or to compile the supplied answers before you can proceed.

There are four main sections. The first is an introduction to FP concepts and the authors have given a lot of thought to the progression of ideas.  This allows you gradually to gain confidence in manipulating functions until finally you're able to develop a lazily-evaluated Stream data type and then a purely functional representation of State. If you just get this far, it's of tremendous benefit.

Then the style of the book changes tack to some extent in three chapters devoted to functional design.  The idea is to illustrate some of the thought processes and alternative approaches that can be involved in groping your way towards the development of a combinator library that tackles a particular design space. Three completely different problems (parallelism, test frameworks and parsers) are used. This is illuminating but sometimes a little at odds with the progression of exercises because your approach and the authors' may legitimately diverge.  This means you may occasionally have to look ahead to the answers to keep yourself on track. What is interesting here is that the three different areas evolve solutions with a deep structure in common and you develop something of an intuition of what it is that makes Monads inevitable.

The third section then discusses Monoids, Monads, Functors and Applicatives.  This is familiar territory if you've read Learn You a Haskell but there is considerably more depth of coverage, and because you've spent so much time thinking about the diverse design problems in the previous section, you may well find that your understanding of these deep abstractions takes a more tangible form.

Section 4 deals with the question - if your program is completely pure, how do you deal with an effect such as IO?  There are many aspects to this and the authors review the strengths and limitations of the IO Monad and discuss different alternatives to the problem of handling mutable state. The book ends with a fascinating chapter on Streaming IO.  This was a brave thing to do - the discussion is exploratory in style and feels its way towards a thorough explanation of the design principles behind the scalaz-stream library. It seems as though the chapter might have been developed in parallel with the development of the library itself and you almost think that you are one of the team. Surprisingly, no mention is made of scalaz, however you will learn many of the design principles that underpin it.  (This won't give you everything you need for the scalaz syntax, though.  For this, I would recommend learning-scalaz.)

This is a book which has already taught me a great deal and given me a huge amount of pleasure.  It is one that I will keep going back to until I finally feel that I am getting the hang of that mysterious activity which is called functional programming.
 

A SKI Calculator

I have recently been attempting the exercises in Raymond Smullyan's to mock a Mockingbird. This is a gentle and enjoyable introduction to combinatory logic. He chooses an applicative system of combinators where the objects are birds and so he names them combinator birds. They live in variety of different forests where the inhabitants of each forest have distinctive characteristics.

Combinator Birds

Here are some examples of Smullyan's birds:

  Bluebird: Bxyz = x(yz)
  Cardinal: Cxyz = xzy
  Warbler:  Wxy = xyy
  Identity: Ix = x 

These are conventionally written in a form which minimises the bracketing because the terms are considered to be left-associative. They can be re-written in a normal form which makes the association explicit - for example:

  Cardinal: Cxyz = (xz)y
  Warbler:  Wxy = (xy)y

In the early chapters you learn that you can build all the other birds in a forest by applying birds to other birds. In fact, the birds shown above (BCWI) form the basis for a whole class of birds, and this class can also be generated from a different set (BTMI). More strangely, you can build all the birds you need from just two:

  Starling: Sxyz = xz(yz)
  Kestrel:  Kxy = x

It is very easy to generate the Identity bird from these two, and conventionally you use all three to generate the others - hence the name SKI Calculus. The real interest is that this is a Turing-complete language - a fact that has been used in an elegant piece of work to show that the Scala type system is Turing-complete. But this is not my object here - rather it is to take up Smullyan's challenge on page 178 to write a program that converts any combinator bird to a SKI bird. It also makes sense to write an interpreter for a SKI bird so that when it is applied to the appropriate variables (x,y,z etc.) then the original combinator bird is reconstituted. The puzzles in chapter 18 lead you to discover a deterministic algorithm for doing this which Smullyan sketches out in the answers (although be careful - unfortunately his explanation contains a couple of typos).

Parse Tree

A combinator bird is best represented by a binary tree which can distinguish between the bracketed forms in the following way:

This tree can be generated with the following very simple grammar which recognizes birds in normal form:

   expression ::= term term | term 
   term ::= terminal | bracket
   bracket ::= "(" expression ")" 
   terminal ::= "x"| "y" | "z" | "w" | "v" 

A parse tree in Scala then is of course:

   trait Tree
   case class Leaf(value: String) extends Tree
   case class Node(left: Tree, right: Tree) extends Tree

It is then straightforward to build a parser using the parser combinator library - but be careful - this has been moved to its own jar in Scala 2.11 - scala-parser-combinators_2.11.

α-Elimination

The algorithm that converts a combinator bird to a SKI bird takes one variable at a time, starting with the outermost variable and removes it progressively from each node in the tree until it vanishes - being replaced by a tree of S,K and I. This process is called α-elimination and is an entirely mechanical process which involves invoking any or all of four Principles which are encoded as follows:

   // α-elimination of α alone is I (Iα=α)
   private def principle1 = I

   // α-elimination of X (α not in X) is KX (KXα=X)
   private def principle2(t: Tree) = Node(K,t)

   // α-elimination of Yα (α not in Y) is Y (Yα=α)
   private def principle3(t: Tree) = t

   // α-elimination of XY (X an Y both α-eliminations) is SXY
   private def principle4(l: Tree, r: Tree) =  Node(Node(S,l),r)

where we have:

   object SKINodes {
     val S = Leaf("S")
     val K = Leaf("K")
     val I = Leaf("I") 
   }

This is not a very efficient algorithm because you have to look down the tree to detect whether the α-variable you are trying to replace exists in each branch, and it may not find the optimal SKI representation, but it is entirely deterministic and once you have replaced each variable you obtain a tree where the leaf nodes contain only S, K or I leaves.

SKI Interpretation

To interpret a SKI tree, you attach it to the required variables at its apex and then walk the tree. I have chosen a left side tree walk where I continue translating each branch until (on looking down it) all SKI nodes have been replaced. At each re-write I effectively apply the left hand operator to the right-hand tree. Because I am dealing with a binary tree but the S and K operators require more than one parameter, I accumulate 'partial' operators flowing up the tree until they are fully satisfied. This is done by adding extra transient nodes to the tree:

  // transient nodes used in SKI interpretation - essentially representations
  // of partial application of S, K or I
  case object S0 extends Tree
  case object K0 extends Tree
  case object I0 extends Tree
  case class K1(child: Tree) extends Tree
  case class S1(child: Tree) extends Tree
  case class S2(left: Tree, right: Tree) extends Tree

Again, this algorithm is not extremely efficient because of the look-ahead, but appears to be deterministic (certainly for the class of birds in Smullyan's forest). It will run out of stack space for outrageously complex birds because I have not bothered to preserve stack space by means of tail recursion or trampolining. If you are interested, the code is here.