aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorMichael Williamson <mike@zwobble.org>2024-01-12 17:45:49 +0000
committerMichael Williamson <mike@zwobble.org>2024-01-12 17:46:02 +0000
commit5110da8dcd95fba99b7ce8f5db9a3d80cf358555 (patch)
treeedc30d230ec48f03989fcfde93a60d48d8e2d54d /src
parenteebdb565de604bcfdbecf6f51c2c4b13fac228cc (diff)
Introduce type arg as distinct from type param
Diffstat (limited to 'src')
-rw-r--r--src/main/java/org/shedlang/compiler/typechecker/TypeChecker.java13
-rw-r--r--src/main/java/org/shedlang/compiler/typechecker/TypeCheckerSubTyping.java47
-rw-r--r--src/main/java/org/shedlang/compiler/types/FunctionType.java18
-rw-r--r--src/main/java/org/shedlang/compiler/types/Type.java2
-rw-r--r--src/main/java/org/shedlang/compiler/types/TypeArg.java8
-rw-r--r--src/main/java/org/shedlang/compiler/types/TypeSubstitution.java5
-rw-r--r--src/test/java/org/shedlang/compiler/typechecker/TypeCheckerIsSubTypeTests.java77
7 files changed, 111 insertions, 59 deletions
diff --git a/src/main/java/org/shedlang/compiler/typechecker/TypeChecker.java b/src/main/java/org/shedlang/compiler/typechecker/TypeChecker.java
index 5eabbdda..ca33cf0a 100644
--- a/src/main/java/org/shedlang/compiler/typechecker/TypeChecker.java
+++ b/src/main/java/org/shedlang/compiler/typechecker/TypeChecker.java
@@ -70,11 +70,22 @@ public class TypeChecker {
TypeCheckerContext context,
FunctionType receiverType
) {
+ var typeLevelArgs = receiverType.typeLevelParams()
+ .map(typeLevelParams ->
+ typeLevelParams.stream()
+ .map(param -> new TypeArg(param))
+ .toList()
+ );
+
var constraints = TypeCheckerSubTyping.constraints(
- receiverType.typeLevelParams().orElse(List.of()),
+ typeLevelArgs.orElseGet(List::of),
context.toTypeInfos()
);
+ if (receiverType.typeLevelParams().isPresent()) {
+ receiverType = receiverType.applyTypeLevelArgs(typeLevelArgs.get());
+ }
+
if (args.positional().size() != receiverType.positionalParams().size()) {
throw new WrongNumberOfPositionalArgsError(
receiverType.positionalParams().size(),
diff --git a/src/main/java/org/shedlang/compiler/typechecker/TypeCheckerSubTyping.java b/src/main/java/org/shedlang/compiler/typechecker/TypeCheckerSubTyping.java
index dd12d06b..b17758b3 100644
--- a/src/main/java/org/shedlang/compiler/typechecker/TypeCheckerSubTyping.java
+++ b/src/main/java/org/shedlang/compiler/typechecker/TypeCheckerSubTyping.java
@@ -41,32 +41,32 @@ public class TypeCheckerSubTyping {
}
}
- static Constraints constraints(List<TypeParam> typeLevelParams, TypeInfos typeInfos) {
- return new Constraints(typeLevelParams, P.map(), typeInfos);
+ static Constraints constraints(List<TypeArg> typeLevelArgs, TypeInfos typeInfos) {
+ return new Constraints(typeLevelArgs, P.map(), typeInfos);
}
record Constraints(
- // TODO: typeLevelParams are redundant if we make typeBounds always have those params as keys?
- List<TypeParam> typeLevelParams,
- PMap<TypeParam, TypeBounds> typeBounds,
+ // TODO: typeLevelArgs are redundant if we make typeBounds always have those as keys?
+ List<TypeArg> typeLevelArgs,
+ PMap<TypeArg, TypeBounds> typeBounds,
TypeInfos typeInfos
) {
- public Constraints addLowerBound(TypeParam typeParam, Type lowerBound) {
- return updateBounds(typeParam, bounds -> bounds.addLowerBound(lowerBound));
+ public Constraints addLowerBound(TypeArg typeArg, Type lowerBound) {
+ return updateBounds(typeArg, bounds -> bounds.addLowerBound(lowerBound));
}
- public Constraints addUpperBound(TypeParam typeParam, Type upperBound) {
- return updateBounds(typeParam, bounds -> bounds.addUpperBound(upperBound));
+ public Constraints addUpperBound(TypeArg typeArg, Type upperBound) {
+ return updateBounds(typeArg, bounds -> bounds.addUpperBound(upperBound));
}
private Constraints updateBounds(
- TypeParam typeParam,
+ TypeArg typeArg,
Function<TypeBounds, TypeBounds> update
) {
- var bounds = update.apply(this.typeBounds.getOrDefault(typeParam, TypeBounds.EMPTY));
+ var bounds = update.apply(this.typeBounds.getOrDefault(typeArg, TypeBounds.EMPTY));
return new Constraints(
- this.typeLevelParams,
- this.typeBounds.plus(typeParam, bounds),
+ this.typeLevelArgs,
+ this.typeBounds.plus(typeArg, bounds),
this.typeInfos
);
}
@@ -74,11 +74,10 @@ public class TypeCheckerSubTyping {
public TypeSubstitutionMap solve(Source source) {
// TODO: handle type params that are constrained by other type params
// TODO: handle unconstrained types
- // TODO: do we need any special handling for mutual recursion (i.e. do we need separate type params for the parent call and the child call?)
- var map = this.typeLevelParams.stream()
- .map(typeParam -> {
- var typeParamBounds = this.typeBounds.getOrDefault(typeParam, TypeBounds.EMPTY);
+ var map = this.typeLevelArgs.stream()
+ .map(typeArg -> {
+ var typeParamBounds = this.typeBounds.getOrDefault(typeArg, TypeBounds.EMPTY);
var lowerBound = Types.BOTTOM;
for (var lower : typeParamBounds.lower) {
@@ -99,7 +98,7 @@ public class TypeCheckerSubTyping {
? upperBound
: lowerBound;
- return Map.entry(typeParam, inferredType);
+ return Map.entry(typeArg.param(), inferredType);
})
.collect(Collectors.toMap(x -> x.getKey(), x -> x.getValue()));
@@ -143,19 +142,19 @@ public class TypeCheckerSubTyping {
}
if (
- supertype instanceof TypeParam supertypeTypeParam &&
- constraints.typeLevelParams.contains(supertypeTypeParam)
+ supertype instanceof TypeArg supertypeTypeArg &&
+ constraints.typeLevelArgs.contains(supertypeTypeArg)
) {
- constraints = constraints.addLowerBound(supertypeTypeParam, subtype);
+ constraints = constraints.addLowerBound(supertypeTypeArg, subtype);
return Optional.of(constraints);
}
if (
- subtype instanceof TypeParam subtypeTypeParam &&
- constraints.typeLevelParams.contains(subtypeTypeParam)
+ subtype instanceof TypeArg subtypeTypeArg &&
+ constraints.typeLevelArgs.contains(subtypeTypeArg)
) {
- constraints = constraints.addUpperBound(subtypeTypeParam, supertype);
+ constraints = constraints.addUpperBound(subtypeTypeArg, supertype);
return Optional.of(constraints);
}
diff --git a/src/main/java/org/shedlang/compiler/types/FunctionType.java b/src/main/java/org/shedlang/compiler/types/FunctionType.java
index aad68885..621a2364 100644
--- a/src/main/java/org/shedlang/compiler/types/FunctionType.java
+++ b/src/main/java/org/shedlang/compiler/types/FunctionType.java
@@ -55,8 +55,12 @@ public record FunctionType(
}
public FunctionType withTypeLevelParams(List<TypeParam> typeLevelParams) {
+ return withTypeLevelParams(Optional.of(typeLevelParams));
+ }
+
+ private FunctionType withTypeLevelParams(Optional<List<TypeParam>> typeLevelParams) {
return new FunctionType(
- Optional.of(typeLevelParams),
+ typeLevelParams,
this.positionalParams,
this.namedParams,
this.effect,
@@ -74,6 +78,18 @@ public record FunctionType(
);
}
+ public FunctionType applyTypeLevelArgs(List<TypeArg> typeArgs) {
+ var typeSubstitutionMap = TypeSubstitutionMap.from(
+ this.typeLevelParams.orElseThrow(),
+ typeArgs
+ );
+
+ return TypeSubstitution.substituteFunctionType(
+ this.withTypeLevelParams(Optional.empty()),
+ typeSubstitutionMap
+ );
+ }
+
public static Builder builder() {
return new Builder(
Optional.empty(),
diff --git a/src/main/java/org/shedlang/compiler/types/Type.java b/src/main/java/org/shedlang/compiler/types/Type.java
index a2701446..d2607906 100644
--- a/src/main/java/org/shedlang/compiler/types/Type.java
+++ b/src/main/java/org/shedlang/compiler/types/Type.java
@@ -6,5 +6,5 @@ package org.shedlang.compiler.types;
* found through auxiliary data.
*/
public sealed interface Type extends TypeLevelValue
- permits BoolType, BottomType, ConstructedType, ConstructibleType, FunctionType, IntType, NamespaceType, StringType, StructType, SumType, TopType, TupleType, TypeLevelValueType, TypeParam, UnitType {
+ permits BoolType, BottomType, ConstructedType, ConstructibleType, FunctionType, IntType, NamespaceType, StringType, StructType, SumType, TopType, TupleType, TypeArg, TypeLevelValueType, TypeParam, UnitType {
}
diff --git a/src/main/java/org/shedlang/compiler/types/TypeArg.java b/src/main/java/org/shedlang/compiler/types/TypeArg.java
new file mode 100644
index 00000000..cbf80b3d
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/types/TypeArg.java
@@ -0,0 +1,8 @@
+package org.shedlang.compiler.types;
+
+public record TypeArg(TypeParam param) implements Type {
+ @Override
+ public String describe() {
+ return param.name();
+ }
+}
diff --git a/src/main/java/org/shedlang/compiler/types/TypeSubstitution.java b/src/main/java/org/shedlang/compiler/types/TypeSubstitution.java
index b0632b6c..cc7ddbc9 100644
--- a/src/main/java/org/shedlang/compiler/types/TypeSubstitution.java
+++ b/src/main/java/org/shedlang/compiler/types/TypeSubstitution.java
@@ -49,6 +49,9 @@ public class TypeSubstitution {
.toList()
);
+ case TypeArg typeArg ->
+ typeArg;
+
case TypeLevelValueType typeLevelValueType -> {
throw new UnsupportedOperationException("TODO");
}
@@ -99,7 +102,7 @@ public class TypeSubstitution {
);
}
- private static FunctionType substituteFunctionType(
+ public static FunctionType substituteFunctionType(
FunctionType functionType,
TypeSubstitutionMap map
) {
diff --git a/src/test/java/org/shedlang/compiler/typechecker/TypeCheckerIsSubTypeTests.java b/src/test/java/org/shedlang/compiler/typechecker/TypeCheckerIsSubTypeTests.java
index 8f6af248..7821c68e 100644
--- a/src/test/java/org/shedlang/compiler/typechecker/TypeCheckerIsSubTypeTests.java
+++ b/src/test/java/org/shedlang/compiler/typechecker/TypeCheckerIsSubTypeTests.java
@@ -121,45 +121,49 @@ public class TypeCheckerIsSubTypeTests {
// == Type params ==
@Test
- public void whenSupertypeIsBoundTypeParamThenLowerBoundIsAddedToType() {
+ public void whenSupertypeIsTypeArgThenLowerBoundIsAddedToTypeArg() {
var typeParam = TypeParam.forStructType(
Types.struct(NamespaceName.of("Example"), "Struct"),
"T"
);
+ var typeArg = new TypeArg(typeParam);
var constraints = TypeCheckerSubTyping.addSubtypeConstraint(
Types.INT,
- typeParam,
+ typeArg,
Sources.NULL,
- TypeCheckerSubTyping.constraints(List.of(typeParam), TypeInfos.EMPTY)
+ TypeCheckerSubTyping.constraints(List.of(typeArg), TypeInfos.EMPTY)
);
- assertThat(constraints.typeBounds().get(typeParam), allOf(
+ assertThat(constraints.typeBounds().get(typeArg), allOf(
has("lower", x -> x.lower(), isSequence(equalTo(Types.INT))),
has("upper", x -> x.upper(), isSequence())
));
}
@Test
- public void whenSubtypeIsBoundTypeParamThenUpperBoundIsAddedToType() {
+ public void whenSubtypeIsTypeArgThenUpperBoundIsAddedToTypeArg() {
var typeParam = TypeParam.forStructType(
Types.struct(NamespaceName.of("Example"), "Struct"),
"T"
);
+ var typeArg = new TypeArg(typeParam);
var constraints = TypeCheckerSubTyping.addSubtypeConstraint(
- typeParam,
+ typeArg,
Types.INT,
Sources.NULL,
- TypeCheckerSubTyping.constraints(List.of(typeParam), TypeInfos.EMPTY)
+ TypeCheckerSubTyping.constraints(List.of(typeArg), TypeInfos.EMPTY)
);
- assertThat(constraints.typeBounds().get(typeParam), allOf(
+ assertThat(constraints.typeBounds().get(typeArg), allOf(
has("lower", x -> x.lower(), isSequence()),
has("upper", x -> x.upper(), isSequence(equalTo(Types.INT)))
));
}
+ // TODO: handling of unexpected type args
+
@Test
public void whenSupertypeIsFreeTypeParamThenOtherTypesAreNotSubtype() {
var typeParam = TypeParam.forStructType(
@@ -356,17 +360,19 @@ public class TypeCheckerIsSubTypeTests {
List.of(TypeParam.forStructType(variantType2, "T")),
variantType2
);
+ var sumTypeParam = TypeParam.forSumType(sumType, "T");
+ var sumTypeArg = new TypeArg(sumTypeParam);
var typeInfos = TypeInfos.EMPTY
.addSumTypeInfo(sumType, new SumTypeInfo(P.orderedSet(
variantType1,
Types.constructedStructType(
variantTypeConstructor2,
- List.of(TypeParam.forSumType(sumType, "T"))
+ List.of(sumTypeArg)
)
)));
var constraints = TypeCheckerSubTyping.constraints(
- List.of(TypeParam.forSumType(sumType, "T")),
+ List.of(sumTypeArg),
typeInfos
);
constraints = TypeCheckerSubTyping.addSubtypeConstraint(
@@ -379,7 +385,7 @@ public class TypeCheckerIsSubTypeTests {
constraints
);
- assertThat(constraints.typeBounds().get(TypeParam.forSumType(sumType, "T")), allOf(
+ assertThat(constraints.typeBounds().get(sumTypeArg), allOf(
has("lower", x -> x.lower(), isSequence(equalTo(Types.STRING))),
has("upper", x -> x.upper(), isSequence(equalTo(Types.STRING)))
));
@@ -394,16 +400,18 @@ public class TypeCheckerIsSubTypeTests {
List.of(TypeParam.forStructType(variantType, "T")),
variantType
);
+ var sumTypeParam = TypeParam.forSumType(sumType, "T");
+ var sumTypeArg = new TypeArg(sumTypeParam);
var typeInfos = TypeInfos.EMPTY
.addSumTypeInfo(sumType, new SumTypeInfo(P.orderedSet(
Types.constructedStructType(
variantTypeConstructor,
- List.of(TypeParam.forSumType(sumType, "T"))
+ List.of(sumTypeArg)
)
)));
var constraints = TypeCheckerSubTyping.constraints(
- List.of(TypeParam.forSumType(sumType, "T")),
+ List.of(sumTypeArg),
typeInfos
);
constraints = TypeCheckerSubTyping.addSubtypeConstraint(
@@ -416,7 +424,7 @@ public class TypeCheckerIsSubTypeTests {
constraints
);
- assertThat(constraints.typeBounds().get(TypeParam.forSumType(sumType, "T")), allOf(
+ assertThat(constraints.typeBounds().get(sumTypeArg), allOf(
has("lower", x -> x.lower(), isSequence(equalTo(Types.STRING))),
has("upper", x -> x.upper(), isSequence(equalTo(Types.STRING)))
));
@@ -426,9 +434,11 @@ public class TypeCheckerIsSubTypeTests {
// == Constructed types ==
@Test
- public void constructedTypeCanBeSubtypeOfConstructedTypeWithBoundTypeParam() {
+ public void constructedTypeCanBeSubtypeOfConstructedTypeWithTypeArg() {
var namespaceName = NamespaceName.of("Example", "Project");
var sumType = Types.sum(namespaceName, "Sum");
+ var sumTypeParam = TypeParam.forSumType(sumType, "T");
+ var sumTypeArg = new TypeArg(sumTypeParam);
var structType = Types.struct(namespaceName, "Struct");
var typeConstructor = Types.typeConstructor(
List.of(TypeParam.forStructType(structType, "T")),
@@ -437,7 +447,7 @@ public class TypeCheckerIsSubTypeTests {
var typeInfos = TypeInfos.EMPTY;
var constraints = TypeCheckerSubTyping.constraints(
- List.of(TypeParam.forSumType(sumType, "T")),
+ List.of(sumTypeArg),
typeInfos
);
constraints = TypeCheckerSubTyping.addSubtypeConstraint(
@@ -447,13 +457,13 @@ public class TypeCheckerIsSubTypeTests {
),
Types.constructedStructType(
typeConstructor,
- List.of(TypeParam.forSumType(sumType, "T"))
+ List.of(sumTypeArg)
),
Sources.NULL,
constraints
);
- assertThat(constraints.typeBounds().get(TypeParam.forSumType(sumType, "T")), allOf(
+ assertThat(constraints.typeBounds().get(sumTypeArg), allOf(
has("lower", x -> x.lower(), isSequence(equalTo(Types.STRING))),
has("upper", x -> x.upper(), isSequence(equalTo(Types.STRING)))
));
@@ -581,9 +591,10 @@ public class TypeCheckerIsSubTypeTests {
Types.struct(NamespaceName.of("Example"), "Struct"),
"T"
);
+ var typeArg = new TypeArg(typeParam);
- var constraints = TypeCheckerSubTyping.constraints(List.of(typeParam), TypeInfos.EMPTY)
- .addUpperBound(typeParam, Types.INT);
+ var constraints = TypeCheckerSubTyping.constraints(List.of(typeArg), TypeInfos.EMPTY)
+ .addUpperBound(typeArg, Types.INT);
var result = constraints.solve(Sources.NULL);
assertThat(result, equalTo(TypeSubstitutionMap.of(
@@ -597,9 +608,10 @@ public class TypeCheckerIsSubTypeTests {
Types.struct(NamespaceName.of("Example"), "Struct"),
"T"
);
+ var typeArg = new TypeArg(typeParam);
- var constraints = TypeCheckerSubTyping.constraints(List.of(typeParam), TypeInfos.EMPTY)
- .addLowerBound(typeParam, Types.INT);
+ var constraints = TypeCheckerSubTyping.constraints(List.of(typeArg), TypeInfos.EMPTY)
+ .addLowerBound(typeArg, Types.INT);
var result = constraints.solve(Sources.NULL);
assertThat(result, equalTo(TypeSubstitutionMap.of(
@@ -613,10 +625,11 @@ public class TypeCheckerIsSubTypeTests {
Types.struct(NamespaceName.of("Example"), "Struct"),
"T"
);
+ var typeArg = new TypeArg(typeParam);
- var constraints = TypeCheckerSubTyping.constraints(List.of(typeParam), TypeInfos.EMPTY)
- .addLowerBound(typeParam, Types.INT)
- .addLowerBound(typeParam, Types.STRING);
+ var constraints = TypeCheckerSubTyping.constraints(List.of(typeArg), TypeInfos.EMPTY)
+ .addLowerBound(typeArg, Types.INT)
+ .addLowerBound(typeArg, Types.STRING);
var result = constraints.solve(Sources.NULL);
assertThat(result, equalTo(TypeSubstitutionMap.of(
@@ -630,6 +643,7 @@ public class TypeCheckerIsSubTypeTests {
Types.struct(NamespaceName.of("Example"), "Struct"),
"T"
);
+ var typeArg = new TypeArg(typeParam);
var namespaceName = NamespaceName.of("Example", "Project");
var sumType = Types.sum(namespaceName, "Sum");
var variantType1 = Types.struct(namespaceName, "Variant1");
@@ -640,9 +654,9 @@ public class TypeCheckerIsSubTypeTests {
variantType2
)));
- var constraints = TypeCheckerSubTyping.constraints(List.of(typeParam), typeInfos)
- .addLowerBound(typeParam, variantType1)
- .addUpperBound(typeParam, sumType);
+ var constraints = TypeCheckerSubTyping.constraints(List.of(typeArg), typeInfos)
+ .addLowerBound(typeArg, variantType1)
+ .addUpperBound(typeArg, sumType);
var result = constraints.solve(Sources.NULL);
assertThat(result, equalTo(TypeSubstitutionMap.of(
@@ -656,6 +670,7 @@ public class TypeCheckerIsSubTypeTests {
Types.struct(NamespaceName.of("Example"), "Struct"),
"T"
);
+ var typeArg = new TypeArg(typeParam);
var namespaceName = NamespaceName.of("Example", "Project");
var sumType = Types.sum(namespaceName, "Sum");
var variantType1 = Types.struct(namespaceName, "Variant1");
@@ -666,9 +681,9 @@ public class TypeCheckerIsSubTypeTests {
variantType2
)));
- var constraints = TypeCheckerSubTyping.constraints(List.of(typeParam), typeInfos)
- .addLowerBound(typeParam, sumType)
- .addUpperBound(typeParam, variantType1);
+ var constraints = TypeCheckerSubTyping.constraints(List.of(typeArg), typeInfos)
+ .addLowerBound(typeArg, sumType)
+ .addUpperBound(typeArg, variantType1);
var error = assertThrows(
// TODO: more specific error
IllegalStateException.class,