index.md (7955B)
1 --- 2 title: "OTP: a Functional Approach (or Three)" 3 date: 2015-01-29T00:00:00+00:00 4 draft: false 5 canonical_url: https://www.viget.com/articles/otp-ocaml-haskell-elixir/ 6 --- 7 8 I initially started the [OTP 9 challenge](https://viget.com/extend/otp-a-language-agnostic-programming-challenge) 10 as a fun way to write some [OCaml](https://ocaml.org/). It was, so much 11 so that I wrote solutions in two other functional languages, 12 [Haskell](https://wiki.haskell.org/Haskell) and 13 [Elixir](http://elixir-lang.org/). I structured all three sets of 14 programs the same so that I could easily see their similarities and 15 differences. Check out the `encrypt` program in 16 [all](https://github.com/vigetlabs/otp/blob/master/languages/OCaml/encrypt.ml) 17 [three](https://github.com/vigetlabs/otp/blob/master/languages/Haskell/encrypt.hs) 18 [languages](https://github.com/vigetlabs/otp/blob/master/languages/Elixir/apps/encrypt/lib/encrypt.ex) 19 and then I'll share some of my favorite parts. Go ahead, I'll wait. 20 21 ## Don't Cross the Streams 22 23 One tricky part of the OTP challenge is that you have to cycle over the 24 key if it's shorter than the plaintext. My initial approaches involved 25 passing around an offset and using the modulo operator, [like 26 this](https://github.com/vigetlabs/otp/blob/6d607129f78ccafa9a294ca04da9e4c8bf7b7cc1/decrypt.ml#L11-L14): 27 28 ```ocaml 29 let get_mask key index = 30 let c1 = List.nth key (index mod (List.length key)) 31 and c2 = List.nth key ((index + 1) mod (List.length key)) in 32 int_from_hex_chars c1 c2 33 ``` 34 35 Pretty gross, huh? Fortunately, both 36 [Haskell](http://hackage.haskell.org/package/base-4.7.0.2/docs/Prelude.html#v:cycle) 37 and 38 [Elixir](http://elixir-lang.org/docs/master/elixir/Stream.html#cycle/1) 39 have built-in functionality for lazy, cyclical lists, and OCaml (with 40 the [Batteries](http://batteries.forge.ocamlcore.org/) library) has the 41 [Dllist](http://batteries.forge.ocamlcore.org/doc.preview:batteries-beta1/html/api/Dllist.html) 42 (doubly-linked list) data structure. The OCaml code above becomes 43 simply: 44 45 46 ```ocaml 47 let get_mask key = 48 let c1 = Dllist.get key 49 and c2 = Dllist.get (Dllist.next key) in 50 int_of_hex_chars c1 c2 51 ``` 52 53 No more passing around indexes or using `mod` to stay within the bounds 54 of the array -- the Dllist handles that for us. 55 56 Similarly, a naïve Elixir approach: 57 58 ```elixir 59 def get_mask(key, index) do 60 c1 = Enum.at(key, rem(index, length(key))) 61 c2 = Enum.at(key, rem(index + 1, length(key))) 62 int_of_hex_chars(c1, c2) 63 end 64 ``` 65 66 And with streams activated: 67 68 ```elixir 69 def get_mask(key) do 70 Enum.take(key, 2) |> int_of_hex_chars 71 end 72 ``` 73 74 Check out the source code 75 ([OCaml](https://github.com/vigetlabs/otp/blob/master/languages/OCaml/encrypt.ml), 76 [Haskell](https://github.com/vigetlabs/otp/blob/master/languages/Haskell/encrypt.hs), 77 [Elixir](https://github.com/vigetlabs/otp/blob/master/languages/Elixir/apps/encrypt/lib/encrypt.ex)) 78 to get a better sense of cyclical data structures in action. 79 80 ## Partial Function Application 81 82 Most programming languages have a clear distinction between function 83 arguments (input) and return values (output). The line is less clear in 84 [ML](https://en.wikipedia.org/wiki/ML_%28programming_language%29)-derived 85 languages like Haskell and OCaml. Check this out (from Haskell's `ghci` 86 interactive shell): 87 88 ``` 89 Prelude> let add x y = x + y 90 Prelude> add 5 7 91 12 92 ``` 93 94 We create a function, `add`, that (seemingly) takes two arguments and 95 returns their sum. 96 97 ``` 98 Prelude> let add5 = add 5 99 Prelude> add5 7 100 12 101 ``` 102 103 But what's this? Using our existing `add` function, we've created 104 another function, `add5`, that takes a single argument and adds five to 105 it. So while `add` appears to take two arguments and sum them, it 106 actually takes one argument and returns a function that takes one 107 argument and adds it to the argument passed to the initial function. 108 109 When you inspect the type of `add`, you can see this lack of distinction 110 between input and output: 111 112 ``` 113 Prelude> :type add 114 add :: Num a => a -> a -> a 115 ``` 116 117 Haskell and OCaml use a concept called 118 [*currying*](https://en.wikipedia.org/wiki/Currying) or partial function 119 application. It's a pretty big departure from the C-derived languages 120 most of us are used to. Other languages may offer currying as [an 121 option](http://ruby-doc.org/core-2.1.1/Proc.html#method-i-curry), but 122 this is just how these languages work, out of the box, all of the time. 123 124 Let's see this concept in action. To convert a number to its hex 125 representation, you call `printf "%x" num`. To convert a whole list of 126 numbers, pass the partially applied function `printf "%x"` to `map`, 127 [like 128 so](https://github.com/vigetlabs/otp/blob/master/languages/Haskell/encrypt.hs#L12): 129 130 ```haskell 131 hexStringOfInts nums = concat $ map (printf "%x") nums 132 ``` 133 134 For more info on currying/partial function application, check out 135 [*Learn You a Haskell for Great 136 Good*](http://learnyouahaskell.com/higher-order-functions). 137 138 ## A Friendly Compiler 139 140 I learned to program with C++ and Java, where `gcc` and `javac` weren't 141 my friends -- they were jerks, making me jump through a bunch of hoops 142 without catching any actual issues (or so teenage Dave thought). I've 143 worked almost exclusively with interpreted languages in the intervening 144 10+ years, so it was fascinating to work with Haskell and OCaml, 145 languages with compilers that catch real issues. Here's my original 146 `decrypt` function in Haskell: 147 148 ```haskell 149 decrypt ciphertext key = case ciphertext of 150 [] -> [] 151 c1:c2:cs -> xor (intOfHexChars [c1, c2]) (getMask key) : decrypt cs (drop 2 key) 152 ``` 153 154 Using pattern matching, I pull off the first two characters of the 155 ciphertext and decrypt them against they key, and then recurse on the 156 rest of the ciphertext. If the list is empty, we're done. When I 157 compiled the code, I received the following: 158 159 ``` 160 decrypt.hs:16:26: Warning: 161 Pattern match(es) are non-exhaustive 162 In a case alternative: Patterns not matched: [_] 163 ``` 164 165 The Haskell compiler is telling me that I haven't accounted for a list 166 consisting of a single character. And sure enough, this is invalid input 167 that a user could nevertheless use to call the program. Adding the 168 following handles the failure and fixes the warning: 169 170 ```haskell 171 decrypt ciphertext key = case ciphertext of 172 [] -> [] 173 [_] -> error "Invalid ciphertext" 174 c1:c2:cs -> xor (intOfHexChars [c1, c2]) (getMask key) : decrypt cs (drop 2 key) 175 ``` 176 177 ## Elixir's |> operator 178 179 According to [*Programming 180 Elixir*](https://pragprog.com/book/elixir/programming-elixir), the pipe 181 operator (`|>`) 182 183 > takes the result of the expression to its left and inserts it as the 184 > first parameter of the function invocation to its right. 185 186 It's borrowed from F#, so it's not an entirely novel concept, but it's 187 certainly new to me. To build our key, we want to take the first 188 argument passed into the program, convert it to a list of characters, 189 and then turn it to a cyclical stream. My initial approach looked 190 something like this: 191 192 ```elixir 193 key = Stream.cycle(to_char_list(List.first(System.argv))) 194 ``` 195 196 Using the pipe operator, we can flip that around into something much 197 more readable: 198 199 ```elixir 200 key = System.argv |> List.first |> to_char_list |> Stream.cycle 201 ``` 202 203 I like it. Reminds me of Unix pipes or any Western written language. 204 [Here's how I use the pipe operator in my encrypt 205 solution](https://github.com/vigetlabs/otp/blob/master/languages/Elixir/apps/encrypt/lib/encrypt.ex#L11-L17). 206 207 *** 208 209 At the end of this process, I think Haskell offers the most elegant code 210 and [Elixir](https://www.viget.com/services/elixir) the most potential 211 for us at Viget to use professionally. OCaml offers a good middle ground 212 between theory and practice, though the lack of a robust standard 213 library is a [bummer, man](https://www.youtube.com/watch?v=24Vlt-lpVOY). 214 215 I had a great time writing and refactoring these solutions. I encourage 216 you to [check out the 217 code](https://github.com/vigetlabs/otp/tree/master/languages), fork the 218 repo, and take the challenge yourself.