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


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

Small Success With Go!; Re: Quick message - This link is broken; Adding Reverb To The Echo Chamber; Sox Audio Tools; Would This Have Been OK?; Honesty only important economically before institutions develop; Stegangraphy via PS4; OpenCL Mess; More Book Recommendations; Good Explanation of Difference Between Majority + Minority; Musical Chairs - Who's The Privileged White Guy; I can see straight men watching this conversation and laffing; When it's Actually a Source of Indignation and Disgust; Meta Thread Defending POC Causes POC To Close Account; Indigenous People Of Chile; Curry Recipe; Interesting Link On Marginality; A Nuclear Launch Ordered, 1962; More Book Recs (Better Person); It's Nuanced, And I Tried, So Back Off; Marx; The Negative Of Positive; Jenny Holzer Rocks; Huge Article on Cultural Evolution and More; "Ignoring language theory"; Negative Finger Counting; Week 12; Communication Via Telecomm Bids; Finding Suspects Via Relatives' DNA From Non-Crime Databases; Statistics and Information Theory; Ice OK in USA; On The Other Hand; (Current Understanding Of) Chilean Taxes / Contributions; M John Harrison; Playing Games on a Cloud GPU; China Gamifies Real Life; Can't Help Thinking It's Thoughtcrime; Mefi Quotes; Spray Painting Bike Frame; Weeks 10 + 11; Change: No Longer Possible To Merge Metadata; Books on Old Age; Health Tree Maps; MRA - Men's Rights Activists; Writing Good C++14; Risk Assessment - Fukushima; The Future of Advertising and Surveillance; Travelling With Betaferon; I think I know what I dislike so much about Metafilter; Weeks 8 + 9; More; Pastamore - Bad Italian in Vitacura; History Books; Iraq + The (UK) Governing Elite; Answering Some Hard Questions; Pinochet: The Dictator's Shadow; An Outsider's Guide To Julia Packages; Nobody gives a shit; Lepton Decay Irregularity; An Easier Way; Julia's BinDeps (aka How To Install Cairo); Good Example Of Good Police Work (And Anonymity Being Hard); Best Santiago Burgers; Also; Michael Emmerich (Vibrator Translator) Interview (Japanese Books); Clarice Lispector (Brazillian Writer); Books On Evolution; Looks like Ara (Modular Phone) is dead; Index - Translations From Chile; More Emotion in Chilean Wines; Week 7; Aeon Magazine (Science-ish); QM, Deutsch, Constructor Theory; Interesting Talk Transcripts; Interesting Suggestion Of Election Fraud; "Hard" Books; Articles or Papers on depolarizing the US; Textbook for "QM as complex probabilities"; SFO Get Libor Trader (14 years); Why Are There Still So Many Jobs?; Navier Stokes Incomplete; More on Benford; FBI Claimed Vandalism; Architectural Tessellation; Also: Go, Blake's 7; Delusions of Gender (book); Crypto AG DID work with NSA / GCHQ; 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

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

General Algebraic Data Types (GADTs)

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

Date: Fri, 10 Feb 2006 10:50:34 -0300 (CLST)

As is probably obvious I'm on some kind of Curry-Howard trip -

Anyway, turns out that this is all related to GADTs.  Paul Snively gave
some links at lambda - http://lambda-the-ultimate.org/node/1293 - that led
to this page - http://www.cs.pdx.edu/~sheard/

Amongst the link on that pages is this thesis -
http://www.cs.rice.edu/~pasalic/thesis/body.pdf - which at first glance
looks  like a very good read.


Started Reading This

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

Date: Sun, 25 Jun 2006 09:17:28 -0400 (CLT)

Last night (we now have a printer that, with psnup, will produce legible
4-up double sided pages, so a 240 page thesis takes only 30 sheets).  Am
currently on page 27 and it is very good indeed.  It's pretty old - 1995 -
so I'm curious to what extent the ideas it develops have been adopted
within Haskell.


Staged Interpreter

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

Date: Mon, 26 Jun 2006 10:26:26 -0400 (CLT)

The following is from pages 29 and 30 or Emir Pasalic's thesis "The Role
of Type in Meta-Programming" (link in previous post on this thread).  I've
added some comments in square brackets to clarify points for a wider
readership.  References have been omitted.


An Untyped Interpreter

We begin by reviewing how one writes a simple interpreter in an untyped
language.  For notational parsimony, we will use Haskell syntax but
disregard types.  An interpreter for a small lambda language [one that
defines and evaluates functions] can be defined as follows:

data Exp = I Int | Var String | Abs String Exp | App Exp Exp

[This defines a Haskell type Exp as one of the alternatives on the right. 
For each alternative, the first word is a "tag" that identifies the
alternative, and subsequent words and the types that are contained.  So an
"Exp" can be "I followed by an integer" or "Var followed by the variable
name as a string" or...  App is function application (evaluation) and Abs
isvariable abstraction (function definition).]

eval e env =
  case e of
    I i     => i
  | Var s   => env s
  | Abs s e => (\v => eval e (ext env s v))
  | App f e => (eval f env) (eval s env)

[That's a simple evaluator with rules for the different types above. 
"env" is some kind of environment that returns variable values and "ext"
extends the environment to include an additional named value (where a
value is a general expression).  The "\x => " syntax defines a function(x)
- it's worth looking at that carefully, because what it does is pretty

This provides a simple implementation of object [the object language is
the language being interpreted; not necessarily the same as the language
this code is written in] programs represented by the datatype Exp.  The
function eval evaluates e (an Exp) in an environment env that binds free
variables in the term to values.

This implementation suffers from a severe performance limitation.  If we
were able to inspect the result of applying eval, such as (eval (Abs "x"
(Var "x")) env0) [evaluate the definition of the function f(x) = x] we
would find that it is equivalent to

(\v -> eval (Var "x") (ext env0 "x" v)).

This term will compute the correct result, but it contains an unevaluated
recursive call to eval.  This problem arrises in both call-by-value and
call-by-name languages, and is one of the main reasons for what is called
the "layer of interpretive overhead" that degrades performance. 
Fortunately, this problem can be eliminated using staging.

Staging the Untyped Interpreter

Staging annotations partition the program into (temporally ordered) stages
so that all computation at stage n is performed before any computation at
stage n+1.  Brackets <> surrounding the expression lift it to the next
stage (building code).  Escape ~ drops its expression to a previous stage.
 The effect of escape is to splice pre-computed code values into code
expressions that are constructed by surrounding brackets.  Staging
annotations change the evaluation order of programs, even evaluating under
lambda abstraction.  Therefore they can be used to force the unfolding of
recursive calls to the eval fucntion at code generation time.  Thus, by
just adding staging annotations to the eval function, we can change its
behaviour to achieve the desired operations semantics:

eval' e env =
  case e of
    I i     => <i>
  | Var s   => env s
  | Abs s e => <\v => ~(eval' e (ext env s <v>))>
  | App f e => <~(eval' f env) ~(eval' e env)>

Now applying eval' to (Abs "x" (Var "x")) in some environment env0 yields
the result

(\v => v)

There are no recursive calls to eval' since the abstraction case of eval'
uses escape to evaluate the body of the function "under the lambda".

Chapter 4

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

Date: Tue, 27 Jun 2006 11:53:12 -0400 (CLT)

Read chapter 4 last night (skipped 3, which was technical).  Again, very
interesting - had the flavour of C++ template "tricks".  The idea was to
encode statements about the type of values inside standard (ish) Haskell
datatypes.  For example, you culd imagine a list datatype that included,
in each "cons cell" not just the list item, but the length of the list.

In practice the numbers are represented as Church Numerals -
http://en.wikipedia.org/wiki/Church_numeral - and you need a lot more
infrastructure than that.  For example, you need to be able to test
whether two of these "embedded types" are equal.  It turns out that you
can get equality via "forall" (at this point I realise I didn't completely
understand this, so will shut up before I say something stupid - hope you
get the idea).


Comment on this post