Friday, October 30, 2015

The Definitive All Dancing, All Complete, "WTF Happened to my nice list of integers in Elixir?" Post.

This question happens over and over on every forum where people just starting out with Elixir
go to ask questions. Especially with folks that start with the Euler challenges as a way to learn
Elixir. It generally starts like this.

iex>, fn(x) -> x*x end )
[1, 4, 9, 16, 25]

iex>, fn(x) -> x*x end )


And the reaction is always more or less...

"WTF! where did my nice list of integers go?"

What is really happening is something that is generally so hidden for users of
languages like Ruby or Python is that they've forgotten it exists. Computers do
not store data as readable sections of text, but as binary sequences of ones and
zeros. Ruby et al, do a lot of work to turn those sequences of binary data into
readable strings that can be printed at a terminal. Elixir does the same, it
uses the Inspect Protocol to turn every result that is returned by Elixir
expressions into a readable string.

So lets look at the code that actually gets run when you type an Elixir expression in IEx that returns a List.

defimpl Inspect, for: List do
  def inspect([], _opts), do: "[]"

  def inspect(thing, %Inspect.Opts{char_lists: lists} = opts) do

    cond do
      lists == :as_char_lists or (lists == :infer and printable?(thing)) ->
        << ?', Inspect.BitString.escape(IO.chardata_to_string(thing), ?') :: binary, ?' >>
      keyword?(thing) ->
        surround_many("[", thing, "]", opts, &keyword/2)
      true ->
        surround_many("[", thing, "]", opts, &to_doc/2)

Now, the key thing understand here is that the default for the Inspect Protocol is

char_lists: infer

This means that the code will call the printable? function on the list. If every integer in the 
list corresponds to a printable ASCII character (i.e. is in the range  32..126 plus some integers that
represent various whitespace and newline characters. ), it will print the list as a string rather than
that nice list of integers separated by commas and surrounded by brackets that you were expecting.

Now you are asking yourself:

"Why does Elixir do this batshit transformation just because my list is small numbers?"

It's a good question to ask. Elixir has a perfectly fine String data type that doesn't look anything like
a List of small numbers. The reason Elixir has this logic in it's List Inspect implementation is that Elixir is built on top of Erlang and all Erlang functions are perfectly valid Elixir functions. This is
one of the great strengths of Elixir. Elixir users get 20+ years of solid software engineering that is used to manage a large percentage of the world's cell phone traffic.

Unfortunately, this comes with a price. The price is the list to string transformation above. You see in Erlang, strings are implemented in what was the style at the time:

Lists of Integers 

This means that if the Inspect Protocol has tell you about Erlang error messages or strings returned from Erlang functions, it must convert any List of small integers into an ASCII string. Well, lets see what happens if we turn that transformation off.

[loaded: [{:iex, 'iex', '1.1.1'}, {:stdlib, 'ERTS  CXC 138 10', '2.6'},
  {:logger, 'logger', '1.1.1'}, {:compiler, 'ERTS  CXC 138 10', '6.0.1'},
  {:elixir, 'elixir', '1.1.1'}, {:kernel, 'ERTS  CXC 138 10', '4.1'}],
 loading: [],
 started: [logger: :temporary, iex: :temporary, elixir: :temporary,
  compiler: :temporary, stdlib: :permanent, kernel: :permanent],
 start_p_false: [],
 running: [logger: #PID<0.48.0>, iex: #PID<0.42.0>, elixir: #PID<0.35.0>,
  compiler: :undefined, stdlib: :undefined, kernel: #PID<0.9.0>], starting: []]

That's all very useful information. There are many Erlang functions that simply don't have Elixir aware wrappers to do the transformation from Erlang to Elixir strings. 

Now if we turn off the nasty :infer that destroyed our beautiful list of integers, what happens to all that useful information. 

iex> IEx.configure inspect: [ char_lists: false]
[loaded: [{:iex, [105, 101, 120], [49, 46, 49, 46, 49]},
  {:stdlib, [69, 82, 84, 83, 32, 32, 67, 88, 67, 32, 49, 51, 56, 32, 49, 48],
   [50, 46, 54]},
  {:logger, [108, 111, 103, 103, 101, 114], [49, 46, 49, 46, 49]},
  {:compiler, [69, 82, 84, 83, 32, 32, 67, 88, 67, 32, 49, 51, 56, 32, 49, 48],
   [54, 46, 48, 46, 49]},
  {:elixir, [101, 108, 105, 120, 105, 114], [49, 46, 49, 46, 49]},
  {:kernel, [69, 82, 84, 83, 32, 32, 67, 88, 67, 32, 49, 51, 56, 32, 49, 48],
   [52, 46, 49]}], loading: [],
 started: [logger: :temporary, iex: :temporary, elixir: :temporary,
  compiler: :temporary, stdlib: :permanent, kernel: :permanent],
 start_p_false: [],
 running: [logger: #PID<0.48.0>, iex: #PID<0.42.0>, elixir: #PID<0.35.0>,
  compiler: :undefined, stdlib: :undefined, kernel: #PID<0.9.0>], starting: []]

That's terrible, what do all those weird lists of number mean? Now imagine you got an error message that was just a list of integers. 

It really seems like there should be a way to straighten this out, but unfortunately all the solutions are worse than the problem. However, once Elixir Golf becomes a thing ( and it's just a matter of time) , you will be able to turn that nastily long list of integers into a cryptic string and your code will still work. 

iex> '%*&^%*&^%' , fn(x) -> x*x end )
[1369, 1764, 1444, 8836, 1369, 1764, 1444, 8836, 1369]

And finally for those that have made it this far, some real dancing.


Friday, August 28, 2015

Making Complex Streams Easier to Understand

Recently the topic of complicated pipe sequences came up on the Elixir Slack channel and there were comments about the inscrutability of a really complicated Stream built of pipes. This is a typical example:!("priv/data/stops.csv")
    |> Stream.drop(1)
    |> &1)
    |> Enum.each(&(Station.Store.put(&1)))

One thing to always keep in mind is that Elixir is an expression based language and any result can always be replaced by a function. The other is that Streams are merely a composition of functions. A more readable way to write the above would be
def station_stream(file) do!(file) 
   |> Stream.drop(1)
   |> &1))

  |> Enum.each(&(Station.Store.put(&1))

Additionally, you can put that Stream in a variable and use it anywhere in the program. As long as the underlying file does not change, the values of the enumeration will not change.

stops = station_stream("priv/data/stops.csv")

A always enumerates through the whole file each time it is evaluated. 
Pipes are one of the features that draws programmers to Elixir, but like anything good you can always over do it. Readability and maintainability should be the first goal. I'm not sure where the exact limit is, but I am sure that pipes can be abused to make code very difficult to reason about. My personal limit seems to be about 3-4 in a sequence.

Saturday, August 1, 2015

Thinking about Stream and Enum in Terms of Function Composition

Coming from a Ruby background it took me a while to wrap my head around what Stream and Enum really are. It's far too easy to think about them as a generalized version of a Ruby Array.

At their heart, they are both tools for composing functions.

Let's start with Enum, in most object style languages enumerators support an "each" method
that allows you to operate one at a time on members of the collection.

Elixir Enum looks quite different at first. It requires that the collection implement these basic functions.

Retrieves the collection’s size
member?(collection, value)
Checks if a value exists within the collection
reduce(collection, acc, fun)
Reduces the collection into a value

None of these looks like an "each" method[1]. 

All the Enum functions do is use these 3 basic functions to provide handy shortcuts for 
using the reduce function of the original collection. Unlike a typical "each" method in Ruby,
an Enum function can bail out at any time. For example, look at the implementation for 

  def all?(collection, fun) do
    Enumerable.reduce(collection, {:cont, true}, fn(entry, _) ->
      if fun.(entry), do: {:cont, true}, else: {:halt, false}
    end) |> elem(1)

Like most of the functions in Enum, it's using the collection's reduce function to implement a specific kind of reduction. In effect it's a composition of functions. It's also "lazy" in the sense that it only iterates as far as it has to generate the correct result. It's important to note that Enumerable implements a different reduce function than the standard one in Enum. ( The accumulator variable must return a tuple consisting of status and "real" accumulator. )

Now let's consider the case of Stream. What it does is very similar to Enum, except that it doesn't
actually execute the reduce function. In effect it creates an anonymous function for transforming the 
collection into another collection. You can use this "dynamic" collection anyplace you can use a regular collection. 

iex(9)> foo =  1..10 |> fn(x) -> x * 2 end )
#Stream<[enum: 1..10, 
funs: [#Function<45.113986093/1 in>]]>

iex(10)> foo |> Enum.max

iex(11)> foo |> Enum.min

iex(12)> foo |> Enum.take(1)

iex(13)> foo |> Enum.take(3)
[2, 4, 6]

The important thing to note from this example is that the a collection defined by Stream does not imply state. It behaves just like a normal collection and is just as immutable. Every time you use it
it starts at the beginning. The decision about when to use a Stream or Enum is should be based on the tradeoffs of storing the collection verses creating it runtime. One difference that is important to note is that Stream only supports using reduce, using count or member directly from Enumerable will fail. Looking at the code for Enum.count we see how you can use reduce to 
emulate these functions. 

def count(collection) do
    case Enumerable.count(collection) do
      {:ok, value} when is_integer(value) ->
      {:error, module} ->
        module.reduce(collection, {:cont, 0}, fn
          _, acc -> {:cont, acc + 1}
        end) |> elem(1)

[1]- It's simple enough to create an "each" from a reduce once you've played around with enough
examples of reduce. 

Thursday, July 16, 2015

Tilting at Windmills: Accessing Erlang man pages from Iex, Part 2:

Digging into the source code of iex, you find that the helpers are macros that pull apart the code and do introspection on the Elixir module to find the documentation. To get the documentation for a specific function in a module the code that eventually gets run is this:

iex> Code.get_docs(Atom, :docs)

[{{:to_char_list, 1}, 22, :def, [{:atom, [], nil}],
  "Converts an atom to a char list.\n\nInlined by the compiler.\n"},
 {{:to_string, 1}, 12, :def, [{:atom, [], nil}],
  "Converts an atom to string.\n\nInlined by the compiler.\n"}]

Where module is a Atom. All module names are Atoms. Code.get_docs returns a list of tuples describing the attributes of each of the functions exported by the module.

 {{function, arity }, line, kind, signature, text}

The initial tuple is the function name and arity. line is the line of the source file on which the function. kind is an atom that describes whether the exported function is a macro or a function.
signature is a list of tuples that define the arguments that the function takes, and lastly text is
the markdown documentation for the function.

If you're willing to fudge things a bit you can duplicate the parts of this function that the iex h command uses by parsing erlang man pages. Every erlang module supports the function module_info.

iex> Atom.module_info(:exports)

[__info__: 1, to_string: 1, to_char_list: 1, module_info: 0, module_info: 1]

iex> :et.module_info(:exports) 

[trace_me: 4, trace_me: 5, phone_home: 4, phone_home: 5, report_event: 4,
 report_event: 5, module_info: 0, module_info: 1]

Since the erlang man pages are created by a standard xml -> nroff process, it's relatively straightforward to split the nroff man page into documentation sections and to identify the function
documented by that section. So creating an ErlangCode.get_docs is possible by mapping the text
from the man page to the appropriate tuple in the export list. You can find code that does this in
the Erlman project on github.


Unfortunately, this is kind of a dead end since it's not general enough to be included in the main elixir source code. It requires that the erlang man pages be installed and that is simply something that can not be counted on. It's also unclear if the current version will even work on Windows with the man pages installed.

My next thought is "Is there a hook into iex commands that I can use to make this an optional addon?"

Friday, June 19, 2015

Tilting At Windmills, Accessing Erlang man pages from Iex Part: 1

In the process of learning how to get a cryptographic hash of a file in Elixir, I found myself switching back and forth from iex to erl -man to better understand how
to use the available Erlang functions in Elixir. After all there are over 500 modules in the standard Erlang libraries that are available in Elixir. Wouldn't it be nice I thought to just be able to type

iex> h :crypto.hash 

and get some basic information about the functions. Elixir already supports listing all the functions available in both Elixir and Erlang modules, using the module.TAB sequence

iex> h :crypto.TAB 
If we have Erlang installed, the man pages must be there somewhere. And of course one of the tenants of Iex is that any functionality should be available in the Windows version if at all possible. While creating a command to shell out to erl -man would be simple, it wouldn't be portable.

Erlang installs it's man pages in a separate path to avoid conflicts with the standard unix man pages but puts them in the standard man/man3 locations. The convention is that the man page for an Erlang module is the Erlang module name followed by section number. The standard Erlang functions are documented in the erlang.3 man page.

So my next step was to reimplement erl -man in purely Elixir code. The first part went really quickly, finding the man page for a given module was relatively straight forward. We just find where the erl executable is and work backwards from that to find where the erlang man pages are and then search for the module name.

 def manpath do
    start = System.find_executable("erl")
    case start do
      nil -> nil
      _   -> find_manpath(start) 

  defp find_manpath(erl_path) do
    mpath = erl_path |>
            Path.split |>
            Stream.scan(&Path.join(&2,&1)) |>
            Enum.filter( fn(p)  -> File.exists?(Path.join([p,"man","man3","ets.3"])) end ) |>
    if mpath , do: Path.join(mpath,"man"), else: nil

After that I implemented a very simple-minded man nroff macro to markdown translator and was able to display an Erlang man page from the iex prompt. During this process I noticed that the Erlang man pages use a very consistant, small subset of the man nroff macro package. This lead me to believe that it would be possible to extract the specific function documentation from the man pages.

It turns out that Erlang documentation is maintained in XML and translated by an xmerl based program into both man pages and html documentation. Unfortunately, this XML source is not included in the default binary distributions of Erlang. Unix versions get the man pages ( and html usually ), but the Windows distributions only get the html. Parsing the html is a lot more complicated that dealing with the nroff and there are no HTML parsers in the standard Elixir libs.

At this point, I decided to dig a bit deeper and figure out just how

iex> h Atom.to_char 

really works.

Friday, June 5, 2015

Micro Benchmarking in Elixir using Benchfella

When I finished the last post, I had complete intentions of writing a post about how to use the Ports module in Elixir to interaction with the system shell to do I/O redirection. However, I now understand why people complain about Erlang documentation. Ports in Elixir aren't documented other than by a reference to the underlying Erlang libraries and the documentation in Erlang for ports is very incomplete. ( For example, what are the default drivers available in erlang?)

Ports are gateways between the Erlang VM and external codes and processes. The Erlang VM is sensitive to code "hanging" in any fashion and Ports need drivers that are aware of how to interact with the Erlang VM safely. However I was unable to find any clear documentation of just what drivers are available and the examples I found were inconsistent.


The types and drivers are documented in the man page for erlang in the open_port section. 

erl -man erlang

I did however find the Porcelain Elixir module that is both well documented and very straightforward to use. Having taken this long to get back to this, I'd just as soon go on to the actual benchmarks.

Benchfella is a micro benchmarking framework that works much like ExUnit does for testing and
you can use the same Dave Thomas hack for creating many tests that iterate over a list of values.

defmodule Hash do
  use Benchfella

  @lengths [1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216]
  for chunk <- @lengths do 
    @chunk chunk 
    bench "Hash 2**24 file by #{Integer.to_string(@chunk)}" do

  for chunk <- @lengths do 
    @chunk chunk 
    bench "Hash 2**26 file by #{Integer.to_string(@chunk)}" do

  for chunk <- @lengths do 
    @chunk chunk 
    bench "Hash 2**28 file by #{Integer.to_string(@chunk)}" do

  def hash_test(file,chunk) do!(file,[],chunk) 
    Enum.reduce(:crypto.hash_init(:sha256),fn(line, acc) -> :crypto.hash_update(acc,line) end ) 


Benchfella runs each test for as many times as possible in a given interval ( the default is one second ) and returns the average time per test over that interval. Data from each run is stored on the filesystem so you can do comparisons between runs.  The plot below shows the results from using a chunk size in powers of 2 from 2**10 to 2**24 to hash a file of size 2**24.

The results are similar for files of size 2**26 and 2**28. As you can see there is a significant advantage to using a large chunk size. ( With an odd bump at 2**23 ) This test
was done on a MacBook Pro with 16gig of memory and an SSD disk drive.

This shows that using large binaries in Elixir ( and Erlang ) is generally the fastest way to deal with large data sets. Of course you need to make the tradeoff between total available memory and the number of binaries you want to process at a time.

The other benchmark I tested was to compare using the "chunk" method of hashing the file with a chunk size larger than the file and simply reading the entire file into a string and
computing it's hash. The simple read method was consistently twice as fast as the single chunk method. 

So for my resulting application I choose to pick a chunk size that allows the code to process multiple files at a time and chooses a method for computing the hash based on the
size of the file.

Thursday, May 14, 2015

Benchmarking Elixir File Hashing Step 1. Creating test data

In my previous post I outlined how to get a cryptographic hash of a file using Elixir. For large files, you want to chunk the file rather than read the whole thing into memory, it would be good to determine if there is an optimal chunk size to use to for passing into the encryption functions.
|> Enum.reduce(:crypto.hash_init(:sha256),fn(line, acc) -> :crypto.hash_update(acc,line) end )
|> :crypto.hash_final |> Base.encode16 "97368E46417DF00CB833C73457D2BE0509C9A404B255D4C70BBDC792D248B4A2" 

The first step in doing this is to create test data files of a specific length. An obvious approach is to simply open /dev/random and read until you've got enough sample data. A simple shell example.
 head -c 1024 < /dev/random > 

Translating that to Elixir looks like
  iex(1)>!("/dev/random",[],1024) |> Enum.take(1) ** (File.Error) could not stream /dev/random: illegal operation on a directory (elixir) lib/file/stream.ex:81: anonymous fn/2 in Enumerable.File.Stream.reduce/3 (elixir) lib/stream.ex:1012: anonymous fn/5 in Stream.resource/3 (elixir) lib/enum.ex:1740: Enum.take/2
That sure looks like a bug, /dev/random is not a directory, but a char special device file. While the error message is misleading, there is no actual bug. Erlang will not open files for reading that it considers dangerous to the overall scheduler. In this case, /dev/random is a character special device file and since these kinds of files usually block on I/O, Erlang errs on the side of caution and will refuse to open the file. There is an exception in the Erlang code for /dev/null since that is considered safe for the scheduler. This post goes into the details.

Reading Device Files in Erlang

There are several ways to get around this problem. The first solution that springs to mind is actually one of the more difficult ones to do in Elixir. In many languages there is a system call that you can use to execute shell commands. Elixir has System.cmd, but it is relatively limited. You can specify the command to execute and the argument list, but you cannot use shell based I/O redirection.

The most straightforward Elixir solution is to use the rand_bytes function from the Erlang crypto library.
  iex(1)> File.write("",:crypto.rand_bytes(1024))

But that isn't much fun, and while it solves this problem it doesn't give us a tool for interacting with external programs. We'll look at more general solutions in the next post...