| 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

Payroll Service Quotes for Cat Soft LLC; (Beating Dead Horse) StackOverflow; Current State of Justice in China; Now Is Cat Soft LLC's Chance To Save Up To 32% On Mail; Axiom of Determinacy; Ewww; Fee Chaos Book; Course on Differential Geometry; Increase Efficiency with GPS Vehicle Tracking for Cat Soft LLC; Okay, but...; Sparse Matrices, Deep Learning; Sounds Bad; Applebaum Rape; Tomato Chutney v4; Have to add...; Culturally Liberal and Nothing More; Weird Finite / Infinite Result; Your diamond is a beaten up mess; Maths Books; Good Bike Route from Providencia / Las Condes to Panul\; Iain Pears (Author of Complex Plots); Plum Jam; Excellent; More Recently; For a moment I forgot StackOverflow sucked; A Few Weeks On...; Chilean Book Recommendations; How To Write Shared Libraries; Jenny Erpenbeck (Author); Dijkstra, Coins, Tables; Python libraries error on OpenSuse; Deserving Trump; And Smugness; McCloskey Economics Trilogy; cmocka - Mocks for C; Concept Creep (Americans); Futhark - OpenCL Language; Moved / Gone; Fan and USB issues; Burgers in Santiago; The Origin of Icosahedral Symmetry in Viruses; autoenum on PyPI; Jars Explains; Tomato Chutney v3; REST; US Elections and Gender: 24 Point Swing; PPPoE on OpenSuse Leap 42.1; SuperMicro X10SDV-TLN4F/F with Opensuse Leap 42.1; Big Data AI Could Be Very Bad Indeed....; Cornering; Postcapitalism (Paul Mason); Black Science Fiction; Git is not a CDN; Mining of Massive Data Sets; Rachel Kaadzi Ghansah; How great republics meet their end; Raspberry, Strawberry and Banana Jam; Interesting Dead Areas of Math; Later Taste; For Sale; Death By Bean; It's Good!; Tomato Chutney v2; Time ATAC MX 2 Pedals - First Impressions; Online Chilean Crafts; Intellectual Variety; Taste + Texture; Time Invariance and Gauge Symmetry; Jodorowsky; Tomato Chutney; Analysis of Support for Trump; Indian SF; TP-Link TL-WR841N DNS TCP Bug; TP-Link TL-WR841N as Wireless Bridge; Sending Email On Time; Maybe run a command; Sterile Neutrinos; Strawberry and Banana Jam; The Best Of All Possible Worlds; Kenzaburo Oe: The Changeling; Peach Jam; Taste Test; Strawberry and Raspberry Jam; flac to mp3 on OpenSuse 42.1; Also, Sebald; Kenzaburo Oe Interview; Otake (Kitani Minoru) move Black 121; Is free speech in British universities under threat?; I am actually good at computers; Was This Mansplaining?; WebFaction / LetsEncrypt / General Disappointment; Sensible Philosophy of Science; George Ellis; Misplaced Intuition and Online Communities; More Reading About Japan; Visibilty / Public Comments / Domestic Violence; Ferias de Santiago; More (Clearly Deliberate); Deleted Obit Post; And then a 50 yo male posts this...; We Have Both Kinds Of Contributors

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