[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 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.)
More information about the Haskell-Cafe