How can you mitigate the lack of return type polymorphism in untyped languages?
Recently I am working with Church encoding and when I look at the typical type
newtype ChurchMaybe a = ChurchMaybe { runChurchMaybe :: forall r . r -> (a -> r) -> r }
it looks like functions with existential type ( runChurchMaybe
) can behave similarly to functions that are polymorphic in return type. However, I have not fully understood the logic behind the existence of existential types. So I am probably wrong.
Now I often read that monads are less useful in untyped languages like Javascript also due to the lack of return type polymorphism. So I wondered if I could alleviate this flaw:
// JS version of Haskell read
// read :: String -> forall r . (String -> r) -> r
const read = x => cons => cons(x);
// option type
const Some = x => r => f => f(x);
const None = r => f => r;
console.log(
read(prompt("any string")) (Array.of) // [a]
);
console.log(
read(prompt("any string")) (Some) // Some(a)
);
console.log(
read(prompt("number string")) (x => Number(x)) // Number
);
const append_ = x => y => append => append(x) (y);
const all = x => y => x && y;
const any = x => y => x || y;
const add = x => y => x + y;
const semigroup = append_(true) (false)
semigroup(all); // false
semigroup(any); // true
semigroup(add); // 1
Obviously read
not polymorphic in its return type, because it always returns a lambda. However, this lambda can serve as a proxy for the actual return value, and now the context can determine what type this proxy actually creates by passing in a suitable constructor.
Although it read
can produce any type, it is append_
limited to types that have a semigroup restriction.
Of course, there is a bit of noise in the context of such functions as they return a proxy instead of the actual result.
Is this essentially the mechanism behind the term "return type polymorphism"? This subject seems to be quite complicated and I think I am missing something. Any help is appreciated.
source to share
In a comment, I made an assertion without justifying myself: I said that return polymorphism is not a meaningful concept in an untyped language. It was rude from me and I apologize for being so rude. What I had in mind was something more subtle than what I said, so please let me try to correct my bad communication by explaining in more detail what I was trying to get to. (I hope this answer is not condescending, I do not know your basic level of knowledge, so I will start from the beginning.)
When Haskellers say "return type polymorphism" they are referring to one particular effect of the type dispatch mechanism. This happens as an interaction between a dictionary jump and bi-directional output type. (I'll ignore polymorphic ones _|_
like undefined :: forall a. a
or let x = x in x :: forall a. a
. They don't really count.)
First, note that instances of a type class in Haskell are syntactic sugar for passing an explicit dictionary. By the time GHC translates your program into its intermediate intermediate representation, all the class classes are gone. They are replaced by "dictionary" entries and passed as normal explicit arguments; =>
appears at runtime ->
. So a code like
class Eq a where
(==) :: a -> a -> Bool
instance Eq Bool where
True == True = True
False == False = True
_ == _ = False
headEq :: Eq a => a -> [a] -> Bool
headEq _ [] = False
headEq x (y:_) = x == y
main = print $ headEq True [False]
converts to something like
-- The class declaration is translated into a regular record type. (D for Dictionary)
data EqD a = EqD { eq :: a -> a -> Bool }
-- The instance is translated into a top-level value of that type
eqDBool :: EqD Bool
eqDBool = EqD { eq = eq }
where eq True True = True
eq False False = True
eq _ _ = False
-- the Eq constraint is translated into a regular dictionary argument
headEq :: EqD a -> a -> [a] -> Bool
headEq _ _ [] = False
headEq eqD x (y:_) = eq eqD x y
-- the elaborator sees you're calling headEq with a ~ Bool and passes in Bool instance dictionary
main = print $ headEq eqDBool True [False]
This works because of instance coherence: each constraint has at most one "best" match instance
(unless you include IncoherentInstances
, which is usually a bad idea). At the overloaded function call node, the developer looks at the type parameter of the constraint, looks for an instance that matches that constraint — either the top level instance
or the scoped constraint — and passes it in one appropriate dictionary as an argument. (For more on the notion of instance coherence, I recommend this talk to Edg Kmett . It's pretty advanced - it took me hours to figure out his point - but it's full of insight.)
In most cases, as in headEq
, constraint type parameters can be determined by looking only at the argument types of the overloaded function, but in the case of polymorphic return values (for example, read :: Read a => String -> a
or mempty :: Monoid m => m
), the character set information must come from the calling site context. This works using the usual bidirectional type inference mechanism: GHC looks at the use of the return value, generates and resolves unification constraints to figure out its type, and then uses that type to find an instance. This creates a magical developer experience for itself: you write mempty
and the machine computes from the context you had in mind.mempty
(By the way, why is show . read :: String -> String
forbidden. show
And read
- these are methods of a class of a class whose concrete implementation is unknown without any clues about the type in which they are used.in show . read
- the one you read and then show is ambiguous, so the GHC doesn't know. how to select an instance dictionary to generate runtime code.)
So "return type polymorphism" is actually a little misleading. This is really the word for a certain type of type-oriented code generation; its Core representation is a regular function whose return type is determined by the type of its (dictionary) argument. In a language without type classes (or in a language with no types at all, like JS) you need to model class classes with explicit dictionary parameters that are manually passed by the programmer, as @ 4Castle demonstrated in yet another answer . You cannot create code generations with a type without types to be targeted with!
source to share
If I understand your question correctly, you would like to know how to implement functions that need access to methods of a type class in order for them to be polymorphic.
One way to think about class types is with lookup tables between types and implementations. For example, it Show
will map types to functions that return strings. This article explains this in more detail and also provides some alternative ways to implement type classes.
In a language that doesn't support types at all, you have to implement types as a kind of unique value that you can pass to polymorphic functions such as a string, symbol, or object reference. I prefer object reference because it means that I can implement my types as functions and be able to implement parameterized types.
Here's an example of how you could implement Read
for Maybe
and Int
:
// MACROS
const TYPE = (constructor, ...args) => Object.freeze({ constructor, args });
const TYPECLASS = (name, defaultMethods = {}) => {
const id = Symbol(name);
const typeClass = ({ constructor, args }) => {
return Object.assign({}, defaultMethods, constructor[id](...args));
};
typeClass._instance_ = (constructor, implementation) => {
constructor[id] = implementation;
};
return Object.freeze(typeClass);
};
// TYPES
const Int = () => TYPE(Int);
const Maybe = a => TYPE(Maybe, a);
// DATA CONSTRUCTORS
const Just = x => r => f => f(x);
const Nothing = r => f => r;
// TYPE CLASSES and INSTANCES
const Read = TYPECLASS('Read');
Read._instance_(Maybe, A => ({
read: str =>
str.slice(0, 5) === "Just "
? Just (Read(A).read(str.slice(5)))
: str === "Nothing"
? Nothing
: undefined
}));
Read._instance_(Int, () => ({
read: str => {
const num = parseInt(str);
return isNaN(num) ? undefined : num;
}
}));
// FUNCTIONS
const error = msg => { throw new Error(msg); };
const maybe = x => f => m => m(x)(f);
const isJust = maybe (false) (_ => true);
const fromJust = maybe (undefined) (x => x);
const read = A => str => {
const x = Read(A).read(str);
return x === undefined ? error ("read: no parse") : x;
};
const readMaybe = A => str => {
try { return Just (read (A) (str)); }
catch (e) { return Nothing; }
};
// TESTS
console.log([
fromJust (read (Maybe(Int())) ("Just 123")), // 123
read (Int()) ("123"), // 123
fromJust (readMaybe (Int()) ("abc")) // undefined
]);
source to share