Open yav opened 10 months ago
Not sure if this is related, but I'm trying to define functors that "extend" a common interface in different ways and a functor that generates an instantiation of one extended interface in terms of the other; Cryptol reports that the same field in their respective imports of the same extended interface cannot match:
module SymmetricCipher where
submodule Util where
swap : {a, b, c} (a -> b -> c) -> b -> a -> c
swap f x y = f y x
/** a common interface used to generate another interface and an instantiation */
interface submodule I_Common where
type Key: *
type Message: *
/** functor to "extend" the common interface */
submodule F__I_Symmetric__I_Common where
import interface submodule I_Common
interface submodule I_Symmetric where
encipher: Key -> Message -> Message
decipher: Key -> Message -> Message
/** another functor to "extend" the common interface with different fields */
submodule F__I_Iterated__I_Common where
import interface submodule I_Common
interface submodule I_Iterated where
type rounds : #
type RoundKey : *
expand_key : Key -> [rounds]RoundKey
encipher_round : RoundKey -> Message -> Message
decipher_round : RoundKey -> Message -> Message
/** functor (of the common interface) to generate a functor (of the second extended interface) to instantiate the first */
submodule F__P_Symmetric__I_Iterated where
import interface submodule I_Common
import submodule F__I_Iterated__I_Common { interface I_Common } (I_Iterated)
submodule P_Symmetric where
import interface submodule I_Iterated
import submodule Util (swap)
// Explicit type parameters are needed to avoid more "not sufficiently polymorphic" errors.
encipher k pt = foldl`{rounds} (swap`{RoundKey, Message} encipher_round) pt (expand_key k)
decipher k ct = foldl`{rounds} (swap`{RoundKey, Message} decipher_round) ct (expand_key k)
Cryptol> :r
Loading module Cryptol
Loading module SymmetricCipher
[error] at .../SymmetricCipher.cry:46:82--46:92:
Inferred type is not sufficiently polymorphic.
Quantified variable: SymmetricCipher::F_P_Symmetric__I_Iterated::P_Symmetric::I_Iterated::RoundKey
cannot match type: SymmetricCipher::F__I_Iterated__I_Common::I_Iterated::RoundKey
Context: _ -> [_] ERROR
When checking function call
where
SymmetricCipher::F__I_Iterated__I_Common::I_Iterated::RoundKey is module parameter SymmetricCipher::F__I_Iterated__I_Common::I_Iterated::RoundKey at .../SymmetricCipher.cry:26:10--26:18
SymmetricCipher::F_P_Symmetric__I_Iterated::P_Symmetric::I_Iterated::RoundKey is module parameter SymmetricCipher::F_P_Symmetric__I_Iterated::P_Symmetric::I_Iterated::RoundKey at .../SymmetricCipher.cry:39:32--39:42
Demoting the functors that import the common interface into a common functor submodule that imports this interface (and adding type constraint (fin rounds)
) convinces Cryptol to load the nested module:
module SymmetricCipher where
submodule Util where
swap : {a, b, c} (a -> b -> c) -> b -> a -> c
swap f x y = f y x
/** a common interface used to generate another interface and an instantiation */
interface submodule I_Common where
type Key: *
type Message: *
/** functor to derive all submodules from the same common interface import */
submodule F__I_Common where
import interface submodule I_Common
/** "extension" of the common interface */
interface submodule I_Symmetric where
encipher: Key -> Message -> Message
decipher: Key -> Message -> Message
/** "extension" of the common interface with different fields */
interface submodule I_Iterated where
type rounds : #
type constraint fin rounds
type RoundKey : *
expand_key : Key -> [rounds]RoundKey
encipher_round : RoundKey -> Message -> Message
decipher_round : RoundKey -> Message -> Message
/** functor (of the second extended interface) to instantiate the first extended interface */
submodule F_P_Symmetric__I_Iterated where
import interface submodule I_Iterated
import submodule Util (swap)
// Explicit type parameters are needed to avoid more "not sufficiently polymorphic" errors.
encipher k pt = foldl`{rounds} (swap`{RoundKey, Message} encipher_round) pt (expand_key k)
decipher k ct = foldl`{rounds} (swap`{RoundKey, Message} decipher_round) ct (expand_key k)
Cryptol> :r
Loading module Cryptol
Loading module SymmetricCipher
Returning to the original example and adding type constraint (fin rounds)
to interface submodule I_Iterated
reveals another error in which this type constraint does not propagate to its instantiation (alongside the original error):
[error] at .../SymmetricCipher.cry:1:1--46:95:
Failed to validate user-specified signature.
when checking the module's parameters,
we need to show that
for any type SymmetricCipher::F_P_Symmetric__I_Iterated::I_Common::Key,
SymmetricCipher::F_P_Symmetric__I_Iterated::I_Common::Message,
SymmetricCipher::F_P_Symmetric__I_Iterated::P_Symmetric::I_Iterated::RoundKey,
SymmetricCipher::F_P_Symmetric__I_Iterated::P_Symmetric::I_Iterated::rounds
assuming
• fin SymmetricCipher::F__I_Iterated__I_Common::I_Iterated::rounds
the following constraints hold:
• fin SymmetricCipher::F_P_Symmetric__I_Iterated::P_Symmetric::I_Iterated::rounds
arising from
use of expression foldl
at .../SymmetricCipher.cry:45:21--45:26
where
SymmetricCipher::F__I_Iterated__I_Common::I_Iterated::rounds is module parameter SymmetricCipher::F__I_Iterated__I_Common::I_Iterated::rounds at .../SymmetricCipher.cry:25:10--25:16
[error] at .../SymmetricCipher.cry:46:82--46:92:
Inferred type is not sufficiently polymorphic.
Quantified variable: SymmetricCipher::F_P_Symmetric__I_Iterated::P_Symmetric::I_Iterated::RoundKey
cannot match type: SymmetricCipher::F__I_Iterated__I_Common::I_Iterated::RoundKey
Context: _ -> [_] ERROR
When checking function call
where
SymmetricCipher::F__I_Iterated__I_Common::I_Iterated::RoundKey is module parameter SymmetricCipher::F__I_Iterated__I_Common::I_Iterated::RoundKey at .../SymmetricCipher.cry:27:10--27:18
SymmetricCipher::F_P_Symmetric__I_Iterated::P_Symmetric::I_Iterated::RoundKey is module parameter SymmetricCipher::F_P_Symmetric__I_Iterated::P_Symmetric::I_Iterated::RoundKey at .../SymmetricCipher.cry:40:32--40:42
Adding interface constraint (fin rounds)
to submodule F_P_Symmetric__I_Iterated
removes this new error, retaining the original.
Currently we can't import an interfaces from a functor, because the instantiation of the functor would have to happen inside the module, and the parameters of the functor cannot depend on things defined inside it. For example:
We could allow such imports as long as the instantiation does not depend on anything in the module (i.e., it could be moved outside the module).
There is a second case that it would be good to support, and where the instantiation cannot be moved outside the module, namely when we are passing through other parameters:
This requires us to change the implementation of pass through parameters, which is probably a good idea any way. Currently, this would be desugared like this:
Note that in this case we cannot move
Anon
outside the module because it depends on the parameters that came in throughJ
. To support this, we should avoid creating the local "copy" module (AnonArg
in the example), and treat this type of instantiation as its own construct.To summarize, it should be possible to use interfaces from functor instantiations as long as the instantiations only depend on externally defined modules and other parameters (and the parameter dependencies don't form loops of course).