Compiler error with higher-order types #293

praalhans · 2016-07-23T10:38:02Z

First of all, thank you for Frege! A very exciting project!

I found a compiler error, at least in the sense that it did not tell what was wrong with my source code.

Consider the following (working) example:

module bug.Example where
data Log t = LogA { message :: String,
                    integer :: Maybe t } |
             LogB { message :: String,
                    boolean :: Bool }
newtype Logger t a = Logger { runLog :: ([Log t], a) }
instance Monad (Logger t) where
  pure a = Logger ([], a)
  (Logger (xs, a)) >>= f = Logger (xs ++ xs', a')
    where (xs', a') = Logger.runLog $ f a
tell s = Logger (s, ())

Now, reversing the [Log t] and a in the tuple of Logger, and modifying the Monad code accordingly, results in the following errors:

module bug.Example where
data Log t = LogA { message :: String,
                    integer :: Maybe t } |
             LogB { message :: String,
                    boolean :: Bool }
newtype Logger t a = Logger { runLog :: (a, [Log t]) }
instance Monad (Logger t) where
  pure a = Logger (a, [])
  (Logger (a, xs)) >>= f = Logger (a', xs ++ xs')
    where (a', xs') = Logger.runLog $ f a
tell s = Logger ((), s)

Results in the following problem:

frege.runtime.Undefined: Can't adapt
Bind {Logger a (b->c), PreludeBase.TTuple2<Func.U<𝓑, 𝓒>, PreludeBase.TList<TLog<𝓐>>>, arg$1.call()}
to  Kind.U<PreludeBase.TTuple2<?, PreludeBase.TList<TLog<𝓐>>>, Func.U<𝓑, 𝓒>>
because  PreludeBase.TTuple2<Func.U<𝓑, 𝓒>, PreludeBase.TList<TLog<𝓐>>>  does not match  Kind.U<PreludeBase.TTuple2<?, PreludeBase.TList<TLog<𝓐>>>, Func.U<𝓑, 𝓒>>
    at frege.prelude.PreludeBase.error(PreludeBase.java:16095)
    at frege.compiler.gen.java.Bindings$30.call(Bindings.java:1865)
    at frege.compiler.gen.java.Bindings$30.call(Bindings.java:1863)
    at frege.run7.Thunk.call(Thunk.java:234)
    at frege.compiler.gen.java.Bindings$33.call(Bindings.java:1964)
    at frege.compiler.gen.java.Bindings$33.call(Bindings.java:1950)
    at frege.run7.Thunk.call(Thunk.java:234)
    at frege.compiler.gen.java.VarCode$5.apply(VarCode.java:568)
    at frege.compiler.gen.java.VarCode$19$5.call(VarCode.java:16376)
    at frege.compiler.gen.java.VarCode$19$5.call(VarCode.java:16374)
    at frege.run7.Thunk.call(Thunk.java:234)
    at frege.control.monad.State$IMonad_State$9.apply(State.java:1290)
    at frege.control.monad.State$IMonad_State$9.apply(State.java:1290)
    at frege.control.monad.State$IMonad_State$9$1.call(State.java:1296)
    at frege.control.monad.State$IMonad_State$9$1.call(State.java:1294)
    at frege.run7.Thunk.call(Thunk.java:234)
    at frege.compiler.gen.java.VarCode$19$2$1Let$33724$9$22$7.apply(VarCode.java:13791)
    at frege.compiler.gen.java.VarCode$19$2$1Let$33724$9$25.call(VarCode.java:15386)
    at frege.compiler.gen.java.VarCode$19$2$1Let$33724$9$25.call(VarCode.java:15382)
    at frege.run7.Thunk.call(Thunk.java:234)
    at frege.compiler.gen.java.VarCode$15.apply(VarCode.java:5215)
    at frege.compiler.gen.java.VarCode$21$3.call(VarCode.java:17015)
    at frege.compiler.gen.java.VarCode$21$3.call(VarCode.java:17013)
    at frege.run7.Thunk.call(Thunk.java:234)
    at frege.compiler.gen.java.Match$5.apply(Match.java:653)
    at frege.compiler.gen.java.VarCode$20.apply(VarCode.java:16470)
    at frege.compiler.gen.java.Match$5.apply(Match.java:653)
    at frege.compiler.gen.java.VarCode$20.apply(VarCode.java:16470)
    at frege.compiler.gen.java.VarCode$40$2.call(VarCode.java:21342)
    at frege.compiler.gen.java.VarCode$40$2.call(VarCode.java:21338)
    at frege.run7.Thunk.call(Thunk.java:234)
    at frege.compiler.gen.java.VarCode$7.apply(VarCode.java:750)
    at frege.compiler.gen.java.VarCode$46.apply(VarCode.java:23089)
    at frege.compiler.gen.java.VarCode$48$1.call(VarCode.java:23358)
    at frege.compiler.gen.java.VarCode$48$1.call(VarCode.java:23356)
    at frege.run7.Thunk.call(Thunk.java:234)
    at frege.control.monad.State$IMonad_State$9.apply(State.java:1290)
    at frege.control.monad.State$IMonad_State$9.apply(State.java:1290)
    at frege.control.monad.State$IMonad_State$9$1.call(State.java:1296)
    at frege.control.monad.State$IMonad_State$9$1.call(State.java:1294)
    at frege.run7.Thunk.call(Thunk.java:234)
    at frege.control.monad.State$IMonad_State$9.apply(State.java:1290)
    at frege.control.monad.State$IMonad_State$9$1.call(State.java:1296)
    at frege.control.monad.State$IMonad_State$9$1.call(State.java:1294)
    at frege.run7.Thunk.call(Thunk.java:234)
    at frege.control.monad.State$IMonad_State$9.apply(State.java:1290)
    at frege.control.monad.State$IMonad_State$9$1.call(State.java:1296)
    at frege.control.monad.State$IMonad_State$9$1.call(State.java:1294)
    at frege.run7.Thunk.call(Thunk.java:234)
    at frege.control.monad.State$IMonad_State$9.apply(State.java:1290)
    at frege.control.monad.State$IMonad_State$9$1.call(State.java:1296)
    at frege.control.monad.State$IMonad_State$9$1.call(State.java:1294)
    at frege.run7.Thunk.call(Thunk.java:234)
    at frege.control.monad.State$IMonad_State$9.apply(State.java:1290)
    at frege.control.monad.State$IMonad_State$9$1.call(State.java:1296)
    at frege.control.monad.State$IMonad_State$9$1.call(State.java:1294)
    at frege.run7.Thunk.call(Thunk.java:234)
    at frege.control.monad.State$IMonad_State$9.apply(State.java:1290)
    at frege.control.monad.State$IMonad_State$9$1.call(State.java:1296)
    at frege.control.monad.State$IMonad_State$9$1.call(State.java:1294)
    at frege.run7.Thunk.call(Thunk.java:234)
    at frege.control.monad.State$IMonad_State$9.apply(State.java:1290)
    at frege.control.monad.State$IMonad_State$9$1.call(State.java:1296)
    at frege.control.monad.State$IMonad_State$9$1.call(State.java:1294)
    at frege.run7.Thunk.call(Thunk.java:234)
    at frege.compiler.gen.java.InstanceCode$9.apply(InstanceCode.java:4309)
    at frege.control.monad.State$IMonad_State$9.apply(State.java:1290)
    at frege.control.monad.State$IMonad_State$9.apply(State.java:1290)
    at frege.control.monad.State$IMonad_State$9$1.call(State.java:1296)
    at frege.control.monad.State$IMonad_State$9$1.call(State.java:1294)
    at frege.run7.Thunk.call(Thunk.java:234)
    at frege.control.monad.State$IMonad_State$17.apply(State.java:1434)
    at frege.control.monad.State$TState$2.call(State.java:2175)
    at frege.control.monad.State$TState$2.call(State.java:2173)
    at frege.run7.Thunk.call(Thunk.java:234)
    at frege.compiler.passes.GenCode$12$1.apply(GenCode.java:2592)
    at frege.imp.parser.FregeParseController.runSTIO(FregeParseController.java:481)
    at frege.imp.parser.FregeParseController.parse(FregeParseController.java:807)
    at frege.imp.parser.FregeParseController.parse(FregeParseController.java:855)
    at frege.imp.builders.FregeBuilder.runParserForCompiler(FregeBuilder.java:255)
    at frege.imp.builders.FregeBuilder.compiled(FregeBuilder.java:166)
    at frege.imp.builders.FregeBuilderBase.compileNecessarySources(FregeBuilderBase.java:365)
    at frege.imp.builders.FregeBuilderBase.build(FregeBuilderBase.java:219)
    at org.eclipse.core.internal.events.BuildManager$2.run(BuildManager.java:734)
    at org.eclipse.core.runtime.SafeRunner.run(SafeRunner.java:42)
    at org.eclipse.core.internal.events.BuildManager.basicBuild(BuildManager.java:205)
    at org.eclipse.core.internal.events.BuildManager.basicBuild(BuildManager.java:245)
    at org.eclipse.core.internal.events.BuildManager$1.run(BuildManager.java:300)
    at org.eclipse.core.runtime.SafeRunner.run(SafeRunner.java:42)
    at org.eclipse.core.internal.events.BuildManager.basicBuild(BuildManager.java:303)
    at org.eclipse.core.internal.events.BuildManager.basicBuildLoop(BuildManager.java:359)
    at org.eclipse.core.internal.events.BuildManager.build(BuildManager.java:382)
    at org.eclipse.core.internal.events.AutoBuildJob.doBuild(AutoBuildJob.java:144)
    at org.eclipse.core.internal.events.AutoBuildJob.run(AutoBuildJob.java:235)
    at org.eclipse.core.internal.jobs.Worker.run(Worker.java:55)

At least a work-around exists, by swapping the elements of the tuple.

The text was updated successfully, but these errors were encountered:

Ingo60 · 2016-07-23T16:47:51Z

This is indeed a bug.
It is related to newtypes which are used as higher ranked types (here through the instantiation as Monad).

To verify this, you can try the failing example with data instead of newtype and if I am right it should work.

Unfortunately, I haven't figured out yet to full extent why some newtypes do work, while others don't. But in this case it is quite clear that the order of the type variables on the LHS is not the same as on the RHS, and this won't work with the encoding for higher ranked types in Java that is utilized in the current implementation.

yuxuanchiadm · 2018-03-25T23:36:54Z

Simplest test case I could construct. Compiler generate illegal java code:

newtype Bar a = Bar { getBar :: String }

class Foo f where
  foo :: f a -> f a -> f a

instance Foo Bar where
  foo (Bar a) (Bar b) = Bar (a ++ b)

main = println (Bar.getBar (foo (Bar "1") (Bar "2")))

Or this. Compiler failed to compile code:

newtype Bar a = Bar { getBar :: Int }

class Foo f where
  foo :: f a -> f a -> f a

instance Foo Bar where
  foo (Bar a) (Bar b) = Bar (a + b)

main = println (Bar.getBar (foo (Bar 1) (Bar 2)))

All those test case could be fixed by changing newtype to data

Edit: In the String case. Looks like compiler thinking the higher kinded type is String :: * -> * instead of Bar :: * -> *

yuxuanchiadm · 2018-03-26T00:59:56Z

So I think the fundamental problem is we treat newtype as just type alias. This usually working fine without any problem. But if we got higher kinded type and RHS and LHS of newtype declaration has different kind signature or kind signature in different order. We can't just think newtype is type alias. We need deal those as special case of newtype.

yuxuanchiadm · 2018-03-26T01:29:06Z

There would be multiple solution for this issue:

Deal those declaration as normal data declaration and warning about this mechanism if user write those code. Because the semantic of normal data type and newtype is not same https://wiki.haskell.org/Newtype (Best short term solution imo)
Keep newtype as type alias. But instead generate real data type for it. Just don't use real data type in normal case. Except we got higher kinded type. Warp value into real data type. And unwarp it soon as possible after higher kinded type is not the case. As long as we keep real data type away from pattern match. Semantic of newtype should be the same.
Since all we need to have are just const and swap functions at kind level. We simply brute force it. Prepare all those possible types up to limit. And do warp and unwarp when necessary.

yuxuanchiadm · 2018-03-26T03:43:37Z

Actually I found current implementation of newtype is some what wrong. I'll open another issue about that.

fix Frege#348

matil019 mentioned this issue Mar 19, 2018

Type-flipping newtype doesn't work with Functor #348

Closed

yuxuanchiadm mentioned this issue Mar 26, 2018

Wrong semantic of newtype #351

Open

Ingo60 closed this as completed in 2e6215c Mar 31, 2018

catull pushed a commit to catull/frege that referenced this issue Jun 28, 2018

fix Frege#293

aaa1954

fix Frege#348

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Compiler error with higher-order types #293

Compiler error with higher-order types #293

praalhans commented Jul 23, 2016

Ingo60 commented Jul 23, 2016

yuxuanchiadm commented Mar 25, 2018 •

edited

Loading

yuxuanchiadm commented Mar 26, 2018 •

edited

Loading

yuxuanchiadm commented Mar 26, 2018 •

edited

Loading

yuxuanchiadm commented Mar 26, 2018

Compiler error with higher-order types #293

Compiler error with higher-order types #293

Comments

praalhans commented Jul 23, 2016

Ingo60 commented Jul 23, 2016

yuxuanchiadm commented Mar 25, 2018 • edited Loading

yuxuanchiadm commented Mar 26, 2018 • edited Loading

yuxuanchiadm commented Mar 26, 2018 • edited Loading

yuxuanchiadm commented Mar 26, 2018

yuxuanchiadm commented Mar 25, 2018 •

edited

Loading

yuxuanchiadm commented Mar 26, 2018 •

edited

Loading

yuxuanchiadm commented Mar 26, 2018 •

edited

Loading