| 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.

C-ORM: docs, API.

Last 100 entries

A Verion That Redirects To Local HTTP Server; Spanish Accents For Idiots; Aluminium Cans; Advice on Spray Painting; Female View of Online Chat From a Male; UX Reading List; S4 Subgroups - Geometric Interpretation; Fucking Email; The SQM Affair For Idiots; Using Kolmogorov Complexity; Oblique Strategies in bash; Curses Tools; Markov Chain Monte Carlo Without all the Bullshit; Email Para Matias Godoy Mercado; The Penta Affair For Idiots; Example Code To Create numpy Array in C; Good Article on Bias in Graphic Design (NYTimes); Do You Backup github?; Data Mining Books; SimpleDateFormat should be synchronized; British Words; Chinese Govt Intercepts External Web To DDOS github; Numbering Permutations; Teenage Engineering - Low Price Synths; GCHQ Can Do Whatever It Wants; Dublinesque; A Cryptographic SAT Solver; Security Challenges; Word Lists for Crosswords; 3D Printing and Speaker Design; Searchable Snowden Archive; XCode Backdoored; Derived Apps Have Malware (CIA); Rowhammer - Hacking Software Via Hardware (DRAM) Bugs; Immutable SQL Database (Kinda); Tor GPS Tracker; That PyCon Dongle Mess...; ASCII Fluid Dynamics; Brandalism; Table of Shifter, Cassette and Derailleur Compatability; Lenovo Demonstrates How Bad HTTPS Is; Telegraph Owned by HSBC; Smaptop - Sunrise (Music); Equation Group (NSA); UK Torture in NI; And - A Natural Extension To Regexps; This Is The Future Of Religion; The Shazam (Music Matching) Algorithm; Tributes To Lesbian Community From AIDS Survivors; Nice Rust Summary; List of Good Fiction Books; Constructing JSON From Postgres (Part 2); Constructing JSON From Postgres (Part 1); Postgres in Docker; Why Poor Places Are More Diverse; Smart Writing on Graceland; Satire in France; Free Speech in France; MTB Cornering - Where Should We Point Our Thrusters?; Secure Secure Shell; Java Generics over Primitives; 2014 (Charlie Brooker); How I am 7; Neural Nets Applied to Go; Programming, Business, Social Contracts; Distributed Systems for Fun and Profit; XML and Scheme; Internet Radio Stations (Curated List); Solid Data About Placebos; Half of Americans Think Climate Change Is a Sign of the Apocalypse; Saturday Surf Sessions With Juvenile Delinquents; Ssh, tty, stdout and stderr; Feathers falling in a vacuum; Santiago 30m Bike Route; Mapa de Ciclovias en Santiago; How Unreliable is UDP?; SE Santiago 20m Bike Route; Cameron's Rap; Configuring libxml with Eclipse; Reducing Combinatorial Complexity With Occam - AI; Sentidos Comunes (Chilean Online Magazine); Hilary Mantel: The Assassination of Margaret Thatcher - August 6th 1983; NSA Interceptng Gmail During Delivery; General IIR Filters; What's happening with Scala?; Interesting (But Largely Illegible) Typeface; Retiring Essentialism; Poorest in UK, Poorest in N Europe; 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

© 2006-2015 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