| Andrew Cooke | Contents | Latest | RSS | Twitter | Previous | Next

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.

Personal Projects

Lepl parser for Python.

Colorless Green.

Photography around Santiago.

SVG experiment.

Professional Portfolio

Calibration of seismometers.

Data access via web services.

Cache rewrite.

Extending OpenSSH.

Last 100 entries

I Want To Be A Redneck!; Reverse Racism; The Lost Art Of Nomography; IBM Data Center (Photo); Interesting Account Of Gamma Hack; The Most Interesting Audiophile In The World; How did the first world war actually end?; Ky - Restaurant Santiago; The Black Dork Lives!; The UN Requires Unaninmous Decisions; LPIR - Steganography in Practice; How I Am 6; Clear Explanation of Verizon / Level 3 / Netflix; Teenage Girls; Formalising NSA Attacks; Switching Brakes (Tektro Hydraulic); Naim NAP 100 (Power Amp); AKG 550 First Impressions; Facebook manipulates emotions (no really); Map Reduce "No Longer Used" At Google; Removing RAID metadata; New Bike (Good Bike Shop, Santiago Chile); Removing APE Tags in Linux; Compiling Python 3.0 With GCC 4.8; Maven is Amazing; Generating Docs from a GitHub Wiki; Modular Shelves; Bash Best Practices; Good Emergency Gasfiter (Santiago, Chile); Readings in Recent Architecture; Roger Casement; Integrated Information Theory (Or Not); Possibly undefined macro AC_ENABLE_SHARED; Update on Charges; Sunburst Visualisation; Spectral Embeddings (Distances -> Coordinates); Introduction to Causality; Filtering To Help Colour-Blindness; ASUS 1015E-DS02 Too; Ready Player One; Writing Clear, Fast Julia Code; List of LatAm Novels; Running (for women); Building a Jenkins Plugin and a Jar (for Command Line use); Headphone Test Recordings; Causal Consistency; The Quest for Randomness; Chat Wars; Real-life Financial Co Without ACID Database...; Flexible Muscle-Based Locomotion for Bipedal Creatures; SQL Performance Explained; The Little Manual of API Design; Multiple Word Sizes; CRC - Next Steps; FizzBuzz; Update on CRCs; Decent Links / Discussion Community; Automated Reasoning About LLVM Optimizations and Undefined Behavior; A Painless Guide To CRC Error Detection Algorithms; Tests in Julia; Dave Eggers: what's so funny about peace, love and Starship?; Cello - High Level C Programming; autoreconf needs tar; Will Self Goes To Heathrow; Top 5 BioInformatics Papers; Vasovagal Response; Good Food in Vina; Chilean Drug Criminals Use Subsitution Cipher; Adrenaline; Stiglitz on the Impact of Technology; Why Not; How I Am 5; Lenovo X240 OpenSuse 13.1; NSA and GCHQ - Psychological Trolls; Finite Fields in Julia (Defining Your Own Number Type); Julian Assange; Starting Qemu on OpenSuse; Noisy GAs/TMs; Venezuela; Reinstalling GRUB with EFI; Instructions For Disabling KDE Indexing; Evolving Speakers; Changing Salt Size in Simple Crypt 3.0.0; Logarithmic Map (Moved); More Info; Words Found in Voynich Manuscript; An Inventory Of 3D Space-Filling Curves; Foxes Using Magnetic Fields To Hunt; 5 Rounds RC5 No Rotation; JP Morgan and Madoff; Ori - Secure, Distributed File System; Physical Unclonable Functions (PUFs); Prejudice on Reddit; Recursion OK; Optimizing Julia Code; Cash Handouts in Brazil; Couple Nice Music Videos; It Also Works!; Adaptive Plaintext; It Works!; RC5 Without Rotation (2)

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

Python Code for ASCII Trees

From: "andrew cooke" <andrew@...>

Date: Sat, 7 Feb 2009 09:10:54 -0300 (CLST)

I doubt I could have written code like this a few years ago.  That's quite
a reassuring feeling - that in some ways you can continue to improve.

Anyway, this is a visitor.  It's the usual visitor pattern (a
catamorphism).  And it's invoked depth-first on a tree of objects.  node()
method is called with arguments that reflect the constructor arguments
used to construct the original tree.


 class GraphStr(Visitor):

   def __init__(self):
     super(GraphStr, self).__init__()
     self.loop = lambda first, rest, name: \
                   [first + name + ' <loop>']

   def node(self, *args, **kargs):
     def fun(first, rest, name, type_=self.type_):
       spec = []
       for arg in args:
	 spec.append(('+- ', '|  ', '', arg))
       for arg in kargs:
	 spec.append(('+- ', '|  ', arg, kargs[arg]))
       if spec:
	 spec[-1] = ('`- ', '   ', spec[-1][2], spec[-1][3])
       yield first + name + (' ' if name else '') + type_.__name__
       for (a, b, c, f) in spec:
	 for line in f(a, b, c):
	   yield rest + line
     return fun

   def arg(self, value):
     return lambda first, rest, name: \
       [first + name + ' ' + repr(value)]

   def postprocess(self, f):
     return '\n'.join(f('', '', ''))


Note the following:

- 'spec' is a list of calls.  Preparing a specification for the calls
  before making them allows the *last* call to be modified simply.

- Generators are used where appropriate (spec cannot be as we need to
  use a -1 index on it to access the last element)

- The walker is depth-first (bottom-up), but the final processing is
  top-down.  So the first stage generates a set of functions that
  implement the second stage (much like implementing foldr in foldl -
  or have I got that backwards? :o)


When applied to the tree generated by this code:

  expression  = Delayed()
  number      = Digit()[1:,...]
  expression += (number | '(' / expression / ')')

It generates:

Delayed
`- matcher Or
   +- Apply
   |  +- function <function add at 0x7f30bf3da738>
   |  +- matcher DepthFirst
   |  |  +- start 1
   |  |  +- stop None
   |  |  +- rest Any
   |  |  |  `- restrict '0123456789'
   |  |  `- first Any
   |  |     `- restrict '0123456789'
   |  +- args False
   |  `- raw True
   `- And
      +- And
      |  +- Literal
      |  |  `- text '('
      |  +- Apply
      |  |  +- function <function add at 0x7f30bef4d380>
      |  |  +- matcher DepthFirst
      |  |  |  +- start 0
      |  |  |  +- stop None
      |  |  |  +- rest Any
      |  |  |  |  `- restrict ' \t'
      |  |  |  `- first Any
      |  |  |     `- restrict ' \t'
      |  |  +- args False
      |  |  `- raw True
      |  `- Delayed
      |     `- matcher <loop>
      +- Apply
      |  +- function <function add at 0x7f30bf176d98>
      |  +- matcher DepthFirst
      |  |  +- start 0
      |  |  +- stop None
      |  |  +- rest Any
      |  |  |  `- restrict ' \t'
      |  |  `- first Any
      |  |     `- restrict ' \t'
      |  +- args False
      |  `- raw True
      `- Literal
         `- text ')'

Andrew

Simple Tree Rewriting

From: "andrew cooke" <andrew@...>

Date: Sat, 7 Feb 2009 09:18:08 -0300 (CLST)

The above is also an example of how some simple tree-rewriting would make
things more efficient by flattening the nested 'And()'.

Andrew

Alternative Representation

From: "andrew cooke" <andrew@...>

Date: Sat, 7 Feb 2009 09:22:55 -0300 (CLST)

And an example of a different visitor applied to the same data.  This is
used for 'repr' (but fails to work completely because the object graph
contains a cycle - hence '<loop>').  The aim here was to get as compact
a representation as possible while remaining readable and not exceeding
a certain width.

The implementation is a nightmare of ad-hoc fixes, but it works...

Delayed(
 matcher=Or(
  Apply(
   function=<function add at 0x7f30eb3ac738>,
   matcher=DepthFirst(
    start=1, stop=None, rest=Any(restrict='0123456789'),
    first=Any(restrict='0123456789')),
   args=False, raw=True),
  And(
   And(
    Literal(text='('),
    Apply(
     function=<function add at 0x7f30eaf1f380>,
     matcher=DepthFirst(
      start=0, stop=None, rest=Any(restrict=' \t'),
      first=Any(restrict=' \t')),
     args=False, raw=True),
    Delayed(matcher=<loop>)),
   Apply(
    function=<function add at 0x7f30eb148d98>,
    matcher=DepthFirst(
     start=0, stop=None, rest=Any(restrict=' \t'),
     first=Any(restrict=' \t')),
    args=False, raw=True),
   Literal(text=')'))))

Too Complicated!

From: andrew cooke <andrew@...>

Date: Tue, 31 May 2011 07:57:06 -0400

Maybe there was a reason for the complexity above, but you can print trees
without needing to construct intermediate functions as above.  See the code at
http://www.acooke.org/cute/ASCIIDispl0.html

(Embarassing that I was apparently so proud of this code, when it seems now
much too complicated for its own good....)

Andrew

Comment on this post