| 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

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); Interesting Take On Mandela's Context; Haskell Cabal O(n^2) / O(n) Fix; How I Am 4; Chilean Charity Supporting Women; Doing SSH right; Festival of Urban Intervention; Neat Idea - Wormholes Provide Entanglement; And a Link....; Simple Encryption for Python 2.7; OpenSuse 13.1 Is Better!; Little Gain...; More Details on Technofull Damage; Palmrest Cracked Too....; Tecnofull (Lenovo Support) Is Fucking Useless; The Neuroscientist Who Discovered He Was a Psychopath; Interpolating Polynomials; Bottlehead Crack as Pre-amp; Ooops K702!; Bottlehead Crack, AKG K701; Breaking RC5 Without Rotation; Great post thank you; Big Balls of Mud; Phabricator - Tools for working together; Amazing Julia RC5 Code Parameterized By Word Size; Chi-Square Can Be Two-Sided; Why Do Brits Accept Surveillance?; Statistics Done Wrong; Mesas Trape from Bravo; European Report on Crypto Primitives and Protocols; Interesting Omissions; Oryx And Crake (Margaret Atwood); Music and Theory; My Arduino Programs; Elliptic Curve Crypto; Re: Licensing Interpreted Code; Licensing Interpreted Code; ASUS 1015E-DS03 OpenSuse 12.3 SSD; translating lettuce feature files into stub steps files; Re: translating lettuce feature files into stub steps files

© 2006-2013 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 -
http://en.wikipedia.org/wiki/Curry-Howard_correspondence

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.

Andrew

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.

Andrew

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

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

Andrew

Comment on this post