| 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

UNUMS (Universal Number Format); MOOCs (Massive Open Online Courses); Interesting Looking Game; Euler's Theorem for Polynomials; Weeks 3-6; Reddit Comment; Differential Cryptanalysis For Dummies; Japanese Graphic Design; Books To Be Re-Read; And Today I Learned Bugs Need Clear Examples; Factoring a 67 bit prime in your head; Islamic Geometric Art; Useful Julia Backtraces from Tasks; Nothing, however, is lost with less discomfort than that which, when lost, cannot be missed; Article on Didion; Cost of Living by City; British Slavery; Derrida on Metaphor; African SciFi; Traits in Julia; Alternative Japanese Lit; Pulic Key as Address (Snow); Why Information Grows; The Blindness Of The Chilean Elite; Some Victoriagate Links; This Is Why I Left StackOverflow; New TLS Implementation; Maths for Physicists; How I Am 8; 1000 Word Philosophy; Cyberpunk Reading List; Detailed Discussion of Message Dispatch in ParserCombinator Library for Julia; FizzBuzz in Julia w Dependent Types; kokko - Design Shop in Osaka; Summary of Greece, Currently; LLVM and GPUs; See Also; Schoolgirl Groyps (Maths); Japanese Lit; Another Example - Modular Arithmetic; Music from United; Python 2 and 3 compatible alternative.; Read Agatha Christie for the Plot; A Constructive Look at TempleOS; Music Thread w Many Recommendations; Fixed Version; A Useful Julia Macro To Define Equality And Hash; k3b cdrom access, OpenSuse 13.1; Week 2; From outside, the UK looks less than stellar; Huge Fonts in VirtualBox; Keen - Complex Emergencies; The Fallen of World War II; Some Spanish Fiction; Calling C From Fortran 95; Bjork DJ Set; Z3 Example With Python; Week 1; Useful Guide To Starting With IJulia; UK Election + Media; Review: Reinventing Organizations; Inline Assembly With Julia / LLVM; Against the definition of types; Dumb Crypto Paper; The Search For Quasi-Periodicity...; Is There An Alternative To Processing?; CARDIAC (CARDboard Illustrative Aid to Computation); The Bolivian Case Against Chile At The Hague; Clear, Cogent Economic Arguments For Immigration; A Program To Say If I Am Working; Decent Cards For Ill People; New Photo; Luksic And Barrick Gold; President Bachelet's Speech; Baltimore Primer; libxml2 Parsing Stream; configure.ac Recipe For Library Path; The Davalos Affair For Idiots; Not The Onion: Google Fireside Chat w Kissinger; Bicycle Wheels, Inertia, and Energy; Another Tax Fraud; Google's Borg; 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

© 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