[Haskell-cafe] What's the term for this? Alpha-reordering? [was: Re: FreeSect -- generalised sections syntax extension

wren ng thornton wren at freegeek.org
Sun Mar 4 03:15:02 CET 2012

On 3/3/12 7:55 PM, AntC wrote:
> So is there an arbitrary greek letter term for reordering?

I'm not aware of one, in part no doubt because it's not a 
semantics-preserving transformation (that is, not in the same sense as 
that used in defining alpha, beta, eta, delta,...).

In the extension to lambda calculus I presented at NASSLLI a couple 
years back[1] it is indeed semantics-preserving. In that context I named 
it chi, because it's a chiastic transformation. Though do note that the 
calculus also supports an alternative interpretation of reordering, 
dubbed ksi (for, er, "ksiastic" transformations?). That is, when 
accounting for reordering we can either reorder the abstractions (chi) 
or we can reorder the applications (ksi); in many contexts it is 
impossible to distinguish them on pretheoretical grounds, though there 
are places where they diverge.

For the record, renaming variables is usually called "alpha-variance" 
and the alpha-equivalence relation is "modulo alpha-variance". 
("Modulus" is a noun; "modulo" is, in English, a preposition.)

[1] http://llama.freegeek.org/~wren/pubs/ccgjp_nasslli2010.pdf

Live well,

More information about the Haskell-Cafe mailing list