|
[Oct. 19th, 2003|05:31 pm]
Jason
|
Question for the types crowd:
Let Δ be the type of functions f : nat -> nat such that f(x) <= x. This can be thought of as the infinite product type 1 x 2 x 3 x 4 x ... or a dependent product or whatever you prefer.
Now the idea of having a type operator which is somehow "a thing that takes τ to Δ x exp(τ)" where exp is to be read as, yes, the exponential function, is not such a crazy thing if we think of power series. Say Δ(i) is the "ith truncation" of Δ (i + 1) x (i + 2) x ... So we could say
Δ x exp(τ) = Σi Δ(i) x τi
(to reflect the power series exp(x) = 1 + x + x^2/2! + x^3/3! + ...)
Now we also have a nice power series for -ln(1-x),
1 + x + x^2/2 + x^3 / 3
And moreover -ln(1-x) = ln(1/(1-x)), and α list is a reasonable interpretation of 1/(1-α) since it is the type solution of β = 1 + α x β just as 1/(1-x) is the solution of y = 1 + xy.
In this way we can come up with a reasonable interpretation in types of Δ x ln(τ list), as
Σi Δ'(i) x τi
where Δ'(i) is the infinite product 1 x 2 x 3 x 4 x ... with the ith term absent.
Given all this nonsense, one might therefore hope, by way of hand-waving and "algebra", that the type
Δ x (Δ x σ -> τ list)
(where the arrow is the function type constructor, think of it as an exponentiation) might somehow be related to the type
Δ x exp(Δ x ln(τ list) x σ)
Ideally by an isomorphism, but I doubt things work out that cleanly. Any ideas how to do this? I have this vague feeling that someone already did this sort of thing in the literature. |
|
