is Delayed/not Delayed known at type inference time?
Geoffrey Irving
The current interpreter uses runtime information in its evaluation of
the argument transformers during function application. In
Interp::apply, we have
o <- maybe
(execError loc ("unresolved overload:" <+> quoted (prettyap f tl)))
return =<< liftInfer (Infer.lookupOver f tl)
-- determine type transform for this argument, and evaluate
let tt = map fst $ overArgs o
-- we throw away the type because we can reconstruct it later with argType
a <- ae (tt !! length args)
Here f is the actual function variable, which is only known at
runtime. tt is the important bit: it determines whether the argument
of the function is evaluated immediately or passed as a delay slot.
As written, tt depends on f, which would be very bad for transition to
a real backend if the dependency is real.
Looking at Infer.hs, it doesn't look like we're enforcing what I think
we should be. I.e., the following code should fail to type check, but
it runs without complaint:
import base
main = exit 0
f :: Delayed a -> a
f x = x ()
g :: Bool -> a -> a
g c x = (if c then f else id) x
Does this mean that argument transformers need to be part of the type
in a way they currently aren't?
Geoffrey
Dylan Simon
I think I understand the issue now, though don't have an answer yet. In the
current design, you can effectively make a function:
delayIf :: Bool -> Delayed? a -> a
that actually does that. That's neat, but I can see how it would be bad for
doing type inference before runtime.
However, we also wanted to be able to have overloads like:
f :: Bool -> Bool
f :: Delayed Int -> Int
Is this still going to be okay?
Type inference is willing to generate a type "f & g" where one is delayed and
one is not. Is this what we want to disallow?
Mail note: Neither of our mail clients is setting a reply-to. I've set mine
to the list for this message. Better?
Geoffrey Irving
That will be fine, since if you know the type of the argument you know
the transform. If you have a variable of type
(Bool -> Bool) | (Delayed Int -> Int)
and you apply it to a value of type t, the value should be delayed iff
its type is Int. Thus, we may want to change (FunArrow t t) to
(FunArrow Trans t t).
> Type inference is willing to generate a type "f & g" where one is delayed and
> one is not. Is this what we want to disallow?
Yes. The test case which should fail is attached if you want to play with it.
> Mail note: Neither of our mail clients is setting a reply-to. I've set mine
> to the list for this message. Better?
That didn't make any difference. I'll glance at the mailing list
settings to see if the issue is there.
Geoffrey
Dylan Simon
f :: Delayed a -> a
f x = force x
g :: Delayed a -> a
g x = f x
To the naive coder, it's a bit confusing why it doesn't. Implementationally,
it seems like it's just an implicit overload that "Delayed" can mean already
"Delay".
Geoffrey Irving
Unfortunately, I don't see how to fix that without compromising
uniformity. We'd need to set up an isomorphism of the form
() -> a == () -> () -> a
Geoffrey
Dylan Simon
> On Sat, Apr 30, 2011 at 4:12 PM, Dylan Simon <dylan-...@dylex.net> wrote:
> > On the subject of Delayed, I wonder whether we can make this work:
> >
> > ? ? ? ?f x = force x
> >
> > ? ? ? ?g :: Delayed a -> a
> > ? ? ? ?g x = f x
> >
> > To the naive coder, it's a bit confusing why it doesn't. ?Implementationally,
> > it seems like it's just an implicit overload that "Delayed" can mean already
> > "Delay".
>
> Unfortunately, I don't see how to fix that without compromising
> uniformity. We'd need to set up an isomorphism of the form
>
> () -> a == () -> () -> a
Couldn't we just say that any definition with "Delayed a" creates two
overloads, one with (Delayed, a) and one with (NoTrans, (() -> a))?
Geoffrey Irving
No, because that would break code like this:
(if c then (() -> 1) else (() -> 2)) ()
The user almost certainly expects the anonymous functions to pass
through the if without being evaluated.
Geoffrey
Dylan Simon
> On Sat, Apr 30, 2011 at 4:19 PM, Dylan Simon <dylan-...@dylex.net> wrote:
> > From Geoffrey Irving <irv...@naml.us>, Sat, Apr 30, 2011 at 04:16:04PM -0700:
> >> On Sat, Apr 30, 2011 at 4:12 PM, Dylan Simon <dylan-...@dylex.net> wrote:
> >> > On the subject of Delayed, I wonder whether we can make this work:
> >> >
> >> > ? ? ? ?f :: Delayed a -> a
> >> > ? ? ? ?f x = force x
> >> >
> >> > ? ? ? ?g :: Delayed a -> a
> >> > ? ? ? ?g x = f x
> >> >
> >> > To the naive coder, it's a bit confusing why it doesn't. ?Implementationally,
> >> > it seems like it's just an implicit overload that "Delayed" can mean already
> >> > "Delay".
> >>
> >> Unfortunately, I don't see how to fix that without compromising
> >>
> >> ? ? () -> a ?== ?() -> () -> a
> >
> > Couldn't we just say that any definition with "Delayed a" creates two
> > overloads, one with (Delayed, a) and one with (NoTrans, (() -> a))?
>
> No, because that would break code like this:
>
> (if c then (() -> 1) else (() -> 2)) ()
>
> The user almost certainly expects the anonymous functions to pass
> through the if without being evaluated.
Well, we could have an explicit, reserved, abstract type Delay a, created only
by calling Delayed, that is not synonymous with () -> a, and a builtin "force"
function. (Sorry if we've been over this all before -- it was a while ago.)
Geoffrey Irving
Yes, that would work. It also avoids the need to internally create
two overloads. I think I agree with you that having delay be
idempotent would be less surprising that the current setup, and the
uniformity with () -> a isn't very important.
Geoffrey
Dylan Simon
> > The current interpreter uses runtime information in its evaluation of
> > the argument transformers during function application. In
> > Interp::apply, we have
> >
> > o <- maybe
> > (execError loc ("unresolved overload:" <+> quoted (prettyap f tl)))
> > return =<< liftInfer (Infer.lookupOver f tl)
> > -- determine type transform for this argument, and evaluate
> > let tt = map fst $ overArgs o
> > -- we throw away the type because we can reconstruct it later with argType
> > a <- ae (tt !! length args)
> >
> > Here f is the actual function variable, which is only known at
> > runtime. tt is the important bit: it determines whether the argument
> > of the function is evaluated immediately or passed as a delay slot.
> > As written, tt depends on f, which would be very bad for transition to
> > a real backend if the dependency is real.
So, I went to go fix this in Interp using my code from Infer to get the trans
and ran into a problem.
We are inferring:
fold :: (||) -> Bool -> Maybe Bool -> Bool
Which means that type inference thinks there's a NoTrans on the (Maybe Bool).
At runtime, however, it decides there's a Delay there (which results in a
segfault).
It seems like type inference is getting it wrong, so I'll try to figure out
why.
That said, imagine a function like fold1 (||) [Bool]. Perhaps by the proper
rules, this is not allowed because (||) is not a -> a -> a. But could you
make an overload for fold1 :: (a -> Delayed a -> a) -> [Delayed a] to fix
this?
Geoffrey Irving
I think we want to
1. allow fold1 (||) [Bool], and have it automatically do the right
thing. I.e., we generate an internal overload of the form (a ->
Delayed a -> a) -> [a] -> a.
2. possibly allow the user to overload based on whether a function
delays or not.
I'm not sure if (2) is feasible, but at least (1) should be. Hmm.
Actually, I suppose fold1 (||) [Bool] wouldn't be what you normally
want, since foldr is the right variant in that case.
A third option would be to only generate one overload and cast (||) to
be nondelaying when it's passed to fold1. This seems like an
unpleasantly surprising approach.
In what you did so far, did you change FunArrow to include a Trans?
Geoffrey
Dylan Simon
> On Sun, May 1, 2011 at 7:46 AM, Dylan Simon <dylan-...@dylex.net> wrote:
> > From Dylan Simon <dylan-...@dylex.net>, Sat, Apr 30, 2011 at 05:48:07PM -0400:
> >> > The current interpreter uses runtime information in its evaluation of
> >> > Interp::apply, we have
> >> >
> >> > ? ? o <- maybe
> >> > ? ? ? (execError loc ("unresolved overload:" <+> quoted (prettyap f tl)))
> >> > ? ? ? return =<< liftInfer (Infer.lookupOver f tl)
> >> > ? ? -- determine type transform for this argument, and evaluate
> >> > ? ? let tt = map fst $ overArgs o
> >> > ? ? -- we throw away the type because we can reconstruct it later with argType
> >> > ? ? a <- ae (tt !! length args)
> >> >
> >> > Here f is the actual function variable, which is only known at
> >> > of the function is evaluated immediately or passed as a delay slot.
> >> > As written, tt depends on f, which would be very bad for transition to
> >> > a real backend if the dependency is real.
> >
> > So, I went to go fix this in Interp using my code from Infer to get the trans
> > and ran into a problem.
> >
> > We are inferring:
> >
> >
> > Which means that type inference thinks there's a NoTrans on the (Maybe Bool).
> > At runtime, however, it decides there's a Delay there (which results in a
> > segfault).
> >
> > It seems like type inference is getting it wrong, so I'll try to figure out
> > why.
> >
> > rules, this is not allowed because (||) is not a -> a -> a. ?But could you
> > make an overload for fold1 :: (a -> Delayed a -> a) -> [Delayed a] to fix
> > this?
>
> I think we want to
>
> 1. allow fold1 (||) [Bool], and have it automatically do the right
> thing. I.e., we generate an internal overload of the form (a ->
> Delayed a -> a) -> [a] -> a.
does that mean (a -> Delayed a -> a) -> [Delayed a] -> a, or is the delay just
ignored here (effectively using (||) :: Bool -> Bool -> Bool).
> 2. possibly allow the user to overload based on whether a function
> delays or not.
You mean, based on whether a function you're passing as an argument delays or
not? Like, if it's in a contra-variant position?
> I'm not sure if (2) is feasible, but at least (1) should be. Hmm.
> Actually, I suppose fold1 (||) [Bool] wouldn't be what you normally
> want, since foldr is the right variant in that case.
>
> A third option would be to only generate one overload and cast (||) to
> be nondelaying when it's passed to fold1. This seems like an
> unpleasantly surprising approach.
>
> In what you did so far, did you change FunArrow to include a Trans?
No, I only changed Infer.apply (typeApply) to return (Trans, TypeVal), though
haven't followed this through all the way, so that might end up being
necessary, too.
Dylan Simon
> >
> > 1. allow fold1 (||) [Bool], and have it automatically do the right
> > thing. I.e., we generate an internal overload of the form (a ->
> > Delayed a -> a) -> [a] -> a.
>
> does that mean (a -> Delayed a -> a) -> [Delayed a] -> a, or is the delay just
> ignored here (effectively using (||) :: Bool -> Bool -> Bool).
>
> > 2. possibly allow the user to overload based on whether a function
> > delays or not.
>
> You mean, based on whether a function you're passing as an argument delays or
> not? Like, if it's in a contra-variant position?
>
> > I'm not sure if (2) is feasible, but at least (1) should be. Hmm.
> > Actually, I suppose fold1 (||) [Bool] wouldn't be what you normally
> > want, since foldr is the right variant in that case.
> >
> > A third option would be to only generate one overload and cast (||) to
> > be nondelaying when it's passed to fold1. This seems like an
> > unpleasantly surprising approach.
> >
> > In what you did so far, did you change FunArrow to include a Trans?
>
> No, I only changed Infer.apply (typeApply) to return (Trans, TypeVal), though
> haven't followed this through all the way, so that might end up being
> necessary, too.
Actually, no I don't know whether any of these make sense. You can't have an
argument of type [Delayed a] -- we have no way of delaying things inside
boxes. It would have to go back to its construction, which seems to violate
the inference principles. And (Delayed [a]), while possible, makes no sense
and doesn't help anything. I'm not sure we have any sensible way to pass
functions with delayed arguments into other functions at the moment.
If we make a special Delay constructor and say "Delayed = trans or Delay",
then we could write special functions like:
fold :: (a -> Delay b -> a) -> a -> [Delay b] -> a
to deal with this... Aside from that, I don't see how to fix this. Even
throwing away the Delayed annotation when it's passed to another function
doesn't work, because then you get the wrong type at runtime, and would have
to construct a new non-delayed wrapper function to pass in instead.
Maybe Delayed needs rethinking. Currently it seems we have to treat it like a
real constructor, and just disallow passing (||) to the normal fold.
Geoffrey Irving
I'm confident that at least in theory it should all fall out if we
make the transform part of the function type. A duck function type
will become a map of the form
Type -> (Trans, Type)
I.e., given the type of the input argument, the function type gives
you (1) the argument transform and (2) the type of the result. It's
fine that the transform depends on the argument type, since we know
the type of the argument without evaluating it. We'll add Trans to
FunArrow, giving
data TypeFun t of
FunArrow t Trans t
FunClosure Var (List t)
FunArrows with different transforms are incompatible types, so
reduceFuns in TypeSet will reject their union. For now, let's put
aside the idea of automatically generating overloads, so fold (||)
will be rejected as you say. In the case of fold (||) it seems like
nothing automatic will do the right thing, which means we shouldn't
try to do anything automatic.
In fact I think making reduceFuns and intersect in TypeSet do the
right thing for Trans-argumented function types probably gets one most
of the way there. The other major component is the function (either
in TypeSet or Infer) that takes a function type and an argument and
produces it's Trans...never mind, that's Infer.apply, and you already
did that part. Cool. Seems like we're almost there.
Geoffrey
Dylan Simon
> On Sun, May 1, 2011 at 12:55 PM, Dylan Simon <dylan-...@dylex.net> wrote:
> >> > I think we want to
> >> >
> >> > 1. allow fold1 (||) [Bool], and have it automatically do the right
> >> > Delayed a -> a) -> [a] -> a.
> >>
> >> does that mean (a -> Delayed a -> a) -> [Delayed a] -> a, or is the delay just
> >> ignored here (effectively using (||) :: Bool -> Bool -> Bool).
> >>
> >> > 2. possibly allow the user to overload based on whether a function
> >> > delays or not.
> >>
> >> You mean, based on whether a function you're passing as an argument delays or
> >>
> >> > I'm not sure if (2) is feasible, but at least (1) should be. ?Hmm.
> >> > Actually, I suppose fold1 (||) [Bool] wouldn't be what you normally
> >> > want, since foldr is the right variant in that case.
> >> >
> >> > A third option would be to only generate one overload and cast (||) to
> >> > unpleasantly surprising approach.
> >> >
> >> > In what you did so far, did you change FunArrow to include a Trans?
> >>
> >> No, I only changed Infer.apply (typeApply) to return (Trans, TypeVal), though
> >> haven't followed this through all the way, so that might end up being
> >> necessary, too.
> >
> > argument of type [Delayed a] -- we have no way of delaying things inside
> > the inference principles. ?And (Delayed [a]), while possible, makes no sense
> > and doesn't help anything. ?I'm not sure we have any sensible way to pass
> > functions with delayed arguments into other functions at the moment.
> >
> > If we make a special Delay constructor and say "Delayed = trans or Delay",
> > then we could write special functions like:
> > to deal with this... ?Aside from that, I don't see how to fix this. ?Even
> > throwing away the Delayed annotation when it's passed to another function
> > doesn't work, because then you get the wrong type at runtime, and would have
> > to construct a new non-delayed wrapper function to pass in instead.
> >
> > real constructor, and just disallow passing (||) to the normal fold.
>
> I'm confident that at least in theory it should all fall out if we
> make the transform part of the function type. A duck function type
> will become a map of the form
>
> Type -> (Trans, Type)
>
> I.e., given the type of the input argument, the function type gives
> you (1) the argument transform and (2) the type of the result. It's
> fine that the transform depends on the argument type, since we know
> the type of the argument without evaluating it. We'll add Trans to
> FunArrow, giving
>
> data TypeFun t of
> FunArrow t Trans t
> FunClosure Var (List t)
>
> FunArrows with different transforms are incompatible types, so
> reduceFuns in TypeSet will reject their union. For now, let's put
> aside the idea of automatically generating overloads, so fold (||)
> will be rejected as you say. In the case of fold (||) it seems like
> nothing automatic will do the right thing, which means we shouldn't
> try to do anything automatic.
Okay. I guess as long as that's settled I think I'm clear enough to move
forward. We will have to decide eventually whether the right way to achieve
fold (||) is to have a fold overload that takes delaying functions (and
ignores the delaying or takes pre-delayed arguments), or an un-delay functor
that converts (||) to a non-delaying version.
This will probably pull Trans annotations out of the overload definition since
they needn't only apply to overloads. It would also allow lambdas to delay
(and make it annoying if they couldn't), so we might want to revisit syntax at
some point, too.
> In fact I think making reduceFuns and intersect in TypeSet do the
> right thing for Trans-argumented function types probably gets one most
> of the way there. The other major component is the function (either
> in TypeSet or Infer) that takes a function type and an argument and
> produces it's Trans...never mind, that's Infer.apply, and you already
> did that part. Cool. Seems like we're almost there.
>
> Geoffrey
>
> --
> To unsubscribe send email to duck-lang+...@googlegroups.com.
> More info at http://groups.google.com/group/duck-lang.
>
Dylan Simon
fold (||) one. The fix I put in looks strange:
fold (x -> y -> x || y) False (Just True)
But of course this just removes the Delayed on the function being passed in.
This also works as an overload (added in delay.duck):
fold :: (a -> Delayed b -> a) -> a -> List b -> a
-- exact same definition as normal fold
I'll next think about possible syntax for delaying lambdas like (Delayed x ->
force x). Making Delayed not look like a type constructor might be a good
thing, perhaps. I also want Delayed to imply Delay or Delayed, and make Delay
special.
But, I'm happy to focus on more pressing issues first if there are some.
Geoffrey Irving
Very cool. Pondering Delay a bit more while it's fresh seems worthwhile.
The next step towards a backend is to streamline our representation of closures and overloads a bit more; I'll start a new thread on that once I get home.
Geoffrey