| 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

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); 8 Years...; Attack Against Encrypted Linux Disks; Pushing Back On NSA At IETF; Summary of Experimental Ethics; Very Good Talk On Security, Snowden; Locusts are Grasshoppers!; Vagrant (OpenSuse and IDEs)

© 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