| Andrew Cooke | Contents | RSS | Twitter | Previous

C[omp]ute

Welcome to my blog, which was once a mailing list of the same name and is still generated by mail. Please reply via the "comment" links.

Always interested in offers/projects/new ideas. Eclectic experience in fields like: numerical computing; Python web; Java enterprise; functional languages; GPGPU; SQL databases; etc. Based in Santiago, Chile; telecommute worldwide. CV; email.

© 2006-2015 Andrew Cooke (site) / post authors (content).

Why Information Grows

From: andrew cooke <andrew@...>

Date: Sat, 4 Jul 2015 20:17:37 -0300

https://www.youtube.com/watch?v=9cXe8w62_ow

Andrew

Permalink | Comment on this post

Previous Entries

For comments, see relevant pages (permalinks).

The Blindness Of The Chilean Elite

From: andrew cooke <andrew@...>

Date: Sat, 4 Jul 2015 15:37:59 -0300

..

  This is a loose translation of
  http://internacional.elpais.com/internacional/2015/06/30/actualidad/1435617430_119551.html
  by Cristobal Rovira Kaltwasser.

  Please note that my Spanish is imperfect (my English too!) and use the
  original for reference.

  See also (other translations):
  * The Bolvian Case Against Chile At The Hague
    http://acooke.org/cute/TheBolivia0.html
  * The Davalos Affair For Idiots http://acooke.org/cute/TheDavalos0.html
  * Another Tax Fraud http://acooke.org/cute/AnotherTax0.html
  * The SQM Affair For Idiots http://www.acooke.org/cute/TheSQMAffa0.html
  * The Penta Affair For Idiots http://acooke.org/cute/ThePentaAf0.html

  Andrew




  It's no longer possible to rebuild the trust that has been broken, 
  the outbreak of populism is just around the corner.


Chile is usually considered an exemplary member of the Latin America ensemble.
Unlike most of its neighbours, Chile has enjoyed three decades of remarkable
economic expansion, with political stability and a strong legal system.
Today, however, this image of a model country is fading.  Why?

Everything started with a corruption scandal linked to the illegal financing
of the main right-wing political party - Union Democratica Independiente
(UDI).  This party is the main proponent of the socio-economic model
implemented by the Pinochet dictatorship, which privatised much of the public
sector, creating economic groups that, in turn, have financed, legally and
illegally, the UDI, in particular, but also political leaders, right-wing think
tanks, and open market technocrats in general.  This has recently been brought
into public view, thanks to the work of the public prosecutor.

But what started as a story of illegal finance for just one party has
blossomed into a political thriller.  The public prosecutor's investigations
show that various deputies and senators - from both right and left - have
received illegal funding through various companies.  Even the presidential
campaigns are now under judicial scrutiny.  These investigations have shown
that one of the main political financiers is Julio Ponce Lerou, a character
worthy of a Stefan Zweig biography.  Mr Ponce Lerou is son-in-law of Pinochet
and enriched himself in an unseemly way during the dictatorship.  If that is
not enough, the son of the current President of the Republic is mixed up in a
dirty property deal.

Faced with these complex circumstances, the Chilean elite have followed a
dismal strategy: stay silent, deny, or lie.  On one hand, a large fraction of
the political class have chosen to dismiss the claims, or given absurd, or
untrue, justifications.  On the other, the businessmen have stayed
complicitly, deeply silent - something of a tradition (as far as I know, there
has been no apology, from any entrepreneur, for their role during the
dictatorship, or for any more recent malpractice).


  The Chilean transition to democracy emerged as a pact between elites 
  who went on to control the country's economic and political systems.


How do you explain the blindness of the Chilean elite?  The answer is simple:
the Chilean transition to democracy emerged as a pact between elites who went
on to control the country's economic and political systems.  If this pact gave
stability to the country, it also normalised practices noxious for democracy.

With time the elites have modified details of the pact, but they have lacked
the wisdom or the motivation to create a new balance of power, suitable for
todays society.  Chile is no longer a country marked by high levels of
poverty, an absent civil society, and a submissive press.  In fact, today,
Chile has a growing middle class, with new social movements and a media that
is no longer afraid of established power.  The problem is that the elite have
not adapted; they are walking blindly on, to the cliff edge.

There is no better example than the results from the recent Report on Human
Development from the UN -
http://desarrollohumano.cl/idh/download/Synopsis_English.pdf
http://desarrollohumano.cl/idh/informes/2015-los-tiempos-de-la-politizacion/ -
which reveals the huge gap between the opinions of the citizens and the
political elites.  A single example: about 60% of the population feel that
private companies should not profit in areas like health care, education and
basic services, but only 25% of the elite share this opinion.

Nothing suggests that the elite are changing.  The current political thriller
continues to expose the pernicious overlap between business and politics.  The
situation is worrying, and is illustrated by rising levels of distrust and
worry.  How to face this problem?  The solution requires a new social pact.
For that, the elites need to drop their guard of silence; they need to accept
their errors and listen to the demands of their citizens.

It may already be too late for the elite to act.  It's highly likely that it's
not longer possible to rebuild the trust that has been broken.  If so, an
outbreak of populism is just around the corner.  Because populism is based on
the distinction between a corrupt establishment and the sovereign people, who
demand the unrestricted use of popular power.  The blindness of the Chilean
elite is paving the way for the growth of populism.  Don't say you haven't
been warned.

Permalink

This Is Why I Left StackOverflow

From: andrew cooke <andrew@...>

Date: Wed, 1 Jul 2015 17:47:28 -0300

It's a perfect example of the arbitrary way it's run.  It wasn't the "final
straw" - that was someone being an arsehole when I asked a question on meta -
but every time I see it, it strikes me as the perfect example of everything
wrong with the moderation there:

http://stackoverflow.com/questions/11390143 - "not a real question"

Andrew

Permalink

New TLS Implementation

From: andrew cooke <andrew@...>

Date: Tue, 30 Jun 2015 16:51:46 -0300

Nice development guide -
https://github.com/awslabs/s2n/blob/master/docs/DEVELOPMENT-GUIDE.md

https://github.com/awslabs/s2n

Andrew

Permalink

Maths for Physicists

From: andrew cooke <andrew@...>

Date: Mon, 29 Jun 2015 17:22:38 -0300

https://www.reddit.com/r/math/comments/3bia10/maths_book_recommendations_for_a_physicist/

Title may be misleading - it's for physicists that want to learn real maths.

Andrew

Permalink

How I Am 8

From: andrew cooke <andrew@...>

Date: Sun, 28 Jun 2015 16:47:01 -0300

http://acooke.org/cute/HowIAm0.html
...
http://acooke.org/cute/HowIam70.html

Wrote the last one of these 6 months ago.  Now almost 31 months from being
diagnosed, 30 months on Betaferon.

About a month ago I had an "aura" - the visial effects of a migraine - that
lasted for a week, more or less.  I've had similar things in the past (since
way before the diagnosis for MS), but never for that long.  It was worrying,
and my doctor was worried too.  But a NMR scan showed nothing new, and
clearing up after a week is relatively fast for an MS symptom.

Flying back from Osaka a couple of days ago, after around 28 hours travelling,
it started again.  I checked and it seems to affect both eyes.  The effect
started slightly below the centre of vision and then moved upwards, until it
was just above.  The effect is like a small "gap" in the vision - things are
simply "missing".  After an hour there was breakfast service - ate a foul
cheese sandwich and had a glass of juice - and soon after that it went away.

Other than that, nothing much has changed.  I have had a problem with
tendonitis in my left knee for most of those 6 months.  Been going to physio
regularly, but it's not clear anything is helping, or what is causing it (no
evidence it's MS).

Buying a digital thermometer / clock that records maximum temperature has made
travelling with Betaferon much less nerve-wracking.  As has some practical
experience - two ice blocks and no opening can survive 24 hours, even when
some of that time is ~30C externally.

I also started working half time (alternate weeks) a month or so ago.
Certainly an improvement, although I am surprised how strongly it has affected
(diminished) my feeling of involvement with work.

Hello to future self.  Good luck.

Andrew

Permalink

1000 Word Philosophy

From: andrew cooke <andrew@...>

Date: Sun, 28 Jun 2015 15:21:57 -0300

https://1000wordphilosophy.wordpress.com/

Andrew

Permalink

Cyberpunk Reading List

From: andrew cooke <andrew@...>

Date: Sun, 28 Jun 2015 14:10:01 -0300

I should probably read more of these.  It's a guilty pleasure....

http://io9.com/the-essential-cyberpunk-reading-list-1714180001

Andrew

Permalink

Detailed Discussion of Message Dispatch in ParserCombinator Library for Julia

From: andrew cooke <andrew@...>

Date: Sun, 28 Jun 2015 07:13:57 -0300

Introduction

I am going to describe some of the decisions behind the
ParserCombinator library, which, I hope, will show how useful Julia's
method-centred, multiple dispatch can be.

OK, so I wanted to write a parser combinator library in Julia.

If you don't know what a parser combinator library is, here's a quick
sketch:

  There's a pretty neat, easy to understand, way of writing parsers by
  hand, which is common in functional languages, where you construct a
  "tree" (or even a DAG) of functions that take a stream of characters
  as input and return some structured output as a result (along with
  the remaining text).

  The stream of characters is (of course) what you want to parse, and
  the structured output becomes your AST.

  Here's a simple (untested!) example (in Julia):

      function equals(text)
          return function _(string)
              n = length(text)
              if string[1:n] == text
                  return string[n:end], text
              else
                  throw(Backtrack())
              end
          end
      end

  By itself that doesn't seem very useful, but consider

      function follows(m1, m2)
          return function _(string)
              string1, result1 = m1(string)
              string2, result2 = m2(string1)
              return string2, [result1, result2]
          end
      end

  which can be used like:

     grammar = follows(equals("hello"), equals("world"))
     grammar("helloworld")
  
  and returns ["hello", "world"].

  And, of course, you can go crazy, with functions that test
  alternatives, or repeat a given number of times, or as often as
  possible, etc etc.

So that's the kind of thing I wanted to write.  But when you start
digging into the details, it's not quite so simple.


Complications

First, Julia isn't intended to be used as a functional language.  It's
not designed to support deep, recursive calls of functions (in fact,
the stack limit in a simple test is a little greater than 100,000 on
my machine, so providing you write combinators for multiple matches
that work with iteration rather than recursion, that's probably not
such a serious issue).

Second, there are different variations on the general idea of "parser
combinators", which work in slightly different ways.  For example, you
might want to cache calls to matchers so that when the "same" call is
made a second time, the cached value is used.  Or you might want to
write the parser so that all possible parses (of an ambiguous grammar)
are returned.  Or you might want to restrict backtracking so that
error messages are more reliable.  Or you might want to display a
record of what is happening to help with debugging.  Or...

These variations, on a little inspection, tend to be connected more
with how the parser "executes", rather than with how the individual
matchers are implemented.

What do I mean by that?  Take, for example, the idea that you cache
results to avoid repeated evaluation.  That is trivial in a "lazy"
language.  But in an eager language (like Julia) you need to intercept
each call to a function, so you can check whether it was cached
earlier.  These are, in a sense, "meta" issues, that have little to do
with checking whether one string is equal to another.

So the question is: can we write our library in a way that makes it
easy to change how the parser "executes"?  And the answer is,
thankfully, yes (or I wouldn't be writing this article)!

How do we do this?  We need two things.  First, we need to use a
"trampoline" to take control of execution.  Second, we need some way
of allowing different behaviors to be "plugged in".  In Julia, this is
typically done by multiple dispatch with methods.  And it works really
well.


Trampolines

All a trampoline is, really, is a "manual" replacement for what a
compiler does automatically: it's a loop, with a stack, that calls
each function in turn, checks what the result is, and then calls
another function, as appropriate.

In practice, what that means is that when we write a function, and we
need to call some other function, we don't just "make the call".
Instead, we return a "message" to the trampoline that says "please
call this other function and then give me the result".

In addition, of course, we need the main loop, which receives these
messages and does the work.

That may sound complicated, but in fact it's not so much work.
Particularly when you're only evaluating matchers in a parser, which
all work in a similar way.

Here's most of the code needed for the main loop, taken from
parsers.jl:

    type NoCache<:Config
        source::Any
        stack::Array{Tuple{Matcher, State},1}
    end

    function dispatch(k::NoCache, e::Execute)
        push!(k.stack, (e.parent, e.parent_state))
        execute(k, e.child, e.child_state, e.iter)
    end

    function dispatch(k::NoCache, s::Success)
        (parent, parent_state) = pop!(k.stack)
        success(k, parent, parent_state, s.child_state, s.iter, s.result)
    end

    function dispatch(k::NoCache, f::Failure)
        (parent, parent_state) = pop!(k.stack)
        failure(k, parent, parent_state)
    end

Those functions are simply responding to the different message types
(Execute, Success and Failure) by manipulating the stack and calling
the appropriate matchers.  Everything is driven by this main loop:

    while true
        msg = dispatch(k, msg)
    end
    
(plus some extra details for handling the setup and teardown).

Now if you're trying to understand the above in detail, you're
probably wondering what execute(), success() and failure() are.  These
are the methods where the matcher itself is implemented.

For example, an "equals" matcher looks like this:

    type Equal<:Matcher
        string
    end

    function execute(k::Config, m::Equal, s::Clean, i)
        for x in m.string
            if done(k.source, i)
                return FAILURE
            end
            y, i = next(k.source, i)
            if x != y
                return FAILURE
            end
        end
        Success(DIRTY, i, Any[m.string])
    end

where FAILURE is the singleton Failure() message and most of the work
is just checking for equality, character by character.

A more complex matcher, which calls out to child matchers, has work
spread across several methods.  Its success() method is called when a
child matcher successfully matches, for example.

You may still be a little confused, however, because Equal, above, is
a type, not a function.  That's because it makes more sense in Julia
to work this way.

Let me explain in more detail...


Grammar As Types

Originally, when I sketched how parser combinators worked, I described
them as functions that returned functions that parsed data (see
"equals()" and "follows()" above).

But in Julia, when you use a trampoline, it makes much more sense to
use types.  So constructing a grammar is not done be calling
functions, but by calling type constructors (like "Equal()" above).

That's because Julia is based around methods, which are dispatched on
multiple types.  By using types to describe our grammar we can then
use method dispatch to implement the work.

And that's what you can see above.  The execute() method includes
"m::Equal", which means that specific execute() is called ONLY when m
is an instance of Equal.  So that execute() is equivalent, roughly, to
the anonymous function in the original sketch.

It's similar to OOP, where the method "belongs" to the type.

To make it completely clear, let's work through things in more detail.

We have to start somewhere, and I am trying to avoid the details of
how we bootstrap or return a final result, since the important idea is
"in the middle".  So let's just assume that some other matcher (an
instance of a type) is similar to the "follows()" function above, in
that it contains two Equals children.  And we'll start with the
execute() method associated with that matcher returning an Execute
message to the trampoline, which contains the first Equal child
(containing the string "hello").

So the parent matcher is saying to the trampoline "call this Equal for
me".

The main loop of the trampoline receives the Execute message, saves
the parent matcher on the stack, and then calls the dispatch() method
for Execute.  That results in calling the execute(... m::Equal, ...)
method, which checks the input against "hello" in the child.

Assuming that matches, the child returns a Success message, which the
trampoline receives.  The trampoline pops the original matcher from
the stack and calls its success() method.  That, in turn, then returns
another Execute message, to match "world", etc etc.

Obviously these matchers need to save data as they work.  The parent
matcher discussed above, for example, needs to save "hello" while it
calls the second Equals for "world".  This is done in the State types
that appear in the dispatch code.

A very nice side effect of having this explicit state is that it makes
adding memoization very easy, because we know exactly when the context
is identical (when the state is identical) and so can decide when to
use the cache.


Was That Worth It?!

OK, so at this point you're probably starting to see how things work
(I hope).  It may help to think of the grammar (the DAG of types) as a
"program" that the trampoline is executing - it's very like an
interpreter, where the grammar is the "program" that the trampoline
"executes" given some input (which is being parsed).

But you may ask "OK, I kind-of get how it works, but was all that
complexity worth it?"

Well, first of all, it's not as complex as it sounds.  It's different,
sure.  Which means it takes some getting used to.  But with a little
experience it becomes surprisingly easy to understand.  The matchers,
for example, are "just" state machines, where the State instances
describe the state, and the execute(), success() and failure() methods
drive transitions from one state to another.

More than "not as bad as it looks" - it's actually surprisingly
elegant.  In a traditional interpreter the main loop is a case
statement that checks the type of what is being executed and then
calls the appropriate function.  Here, in a sense, the function is
always the same - "execute()" - and the right choice of which
particular execute is made for us, by Julia's type system.  Things get
even better when many matchers have similar functionality because they
can, by sharing a common super-type, share a single implementation.
In the case of the ParserCombinator library, for example, most
matchers that call a child matcher are derived from a Delegate
super-type, which provides common support.

And, second of all, it's easy - almost trivial - to hack things at a
"meta" level.  Take the example of caching results.  All you need to
do is add a Map (the cache) to a new sub-type of Config and provide
new dispatch() functions as above: the dispatch for Success should
populate the Map with results; the dispatch for Execute should check
the Map in case a value already exists.  That's it!


Multiple Dispatch v OOP

If the same ideas were implemented in a traditional OOP language, much
of what I have described above would carry across nicely.  There would
be a Trampoline base class that would be subclassed for different
approaches to execution, for example.

But Julia's multiple dispatch wins out when you want behavior to "cut
across" more than one type.

In the ParserCombinator library, one of the approaches to execution
emulates the Parsec library from Haskell.  This doesn't allow
backtracking if the source has been successfully matched.  But one,
"magic", matcher, Try() changes this.  So this one particular matcher
has to "know" about the trampoline in more detail than normal, so that
it can enable backtracking.

How do you do that in a traditional OO language?  It's not so clear,
because the matchers are, presumably, classes that are quite separate
from the trampoline (in Java, for example, you start having to worry
about "package private" access)

But in Julia a method can dispatch on multiple types.  So there's
nothing to stop you having an execute() method that is for one
specific trampoline type and one specific matcher type.  And which is
only called when both those types are used together.

(It may confuse more than it helps, but a similar idea is used here -
http://acooke.org/cute/FizzBuzzin0.html)


Conclusions

I've tried to show how you can implement a parser combinator library
with more than one way for the parser to "execute", by providing
pluggable trampolines.

Much of the approach can be done in any OO language (and the general
idea comes from an earlier attempt in Python, called Lepl).  But
Julia's methods make things particularly easy.

If you want to try ParserCombinator for yourself, please check it out
at https://github.com/andrewcooke/ParserCombinator.jl

Thanks!

Permalink

FizzBuzz in Julia w Dependent Types

From: andrew cooke <andrew@...>

Date: Fri, 26 Jun 2015 16:44:24 -0300

# this is what happens when you're jetlagged somewhere between osaka
# and santiago

typealias Zero Type{Val{0}}

print(fizz, buzz, n) = println(n)
print(fizz::Zero, buzz, n) = println("Fizz")
print(fizz, buzz::Zero, n) = println("Buzz")
print(fizz::Zero, buzz::Zero, n) = println("FizzBuzz")

for n in 1:100
    print(Val{n%3}, Val{n%5}, n)
end

Permalink

kokko - Design Shop in Osaka

From: andrew cooke <andrew@...>

Date: Thu, 25 Jun 2015 05:15:17 -0300

Last day in Osaka, and I was having a hard time finding the kind of ceramics
that I would like as a souvenir (should maybe habe spent the money in Nara).
But some googling turned up
http://www.spoon-tamago.com/2013/04/18/kokko-a-new-crafts-shop-in-osaka/ which
led to an address at
https://foursquare.com/v/kokko---lifestyle-gallery-/513aef0ee4b0b7f3d549f089
(for the record - 万代3-12-1, 大阪市住吉区, Ōsaka, 558-0055, Japan - although
I am not sure that will display correctly).  And so I took a tram south from
Tennoji, stopping at HN07 (Tezukayama Sanchome), near Bandiike Park, and
walking East and then South a few blocks.  And it was there!  And open!  And
it contained some rather nice handmade local porcelain (I think), as well as
some antique pottery from Finland(!).  So now I have a mug and a small dish to
take home :o)

It was also intersting to see a real "designer" Japanese house - just sitting
there amongst much more typical houses.  It wasn't as fancy as I expected - by
which I mean that it was clearly built with a mind to price, and appears to be
a practical place for a "normal" family, not an exclusive art-work for someone
who is super-rich.

Andrew

Permalink