From 5110da8dcd95fba99b7ce8f5db9a3d80cf358555 Mon Sep 17 00:00:00 2001 From: Michael Williamson Date: Fri, 12 Jan 2024 17:45:49 +0000 Subject: Introduce type arg as distinct from type param --- .../shedlang/compiler/typechecker/TypeChecker.java | 13 +++- .../compiler/typechecker/TypeCheckerSubTyping.java | 47 +++++++------ .../org/shedlang/compiler/types/FunctionType.java | 18 ++++- .../java/org/shedlang/compiler/types/Type.java | 2 +- .../java/org/shedlang/compiler/types/TypeArg.java | 8 +++ .../shedlang/compiler/types/TypeSubstitution.java | 5 +- .../typechecker/TypeCheckerIsSubTypeTests.java | 77 +++++++++++++--------- 7 files changed, 111 insertions(+), 59 deletions(-) create mode 100644 src/main/java/org/shedlang/compiler/types/TypeArg.java (limited to 'src') 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 typeLevelParams, TypeInfos typeInfos) { - return new Constraints(typeLevelParams, P.map(), typeInfos); + static Constraints constraints(List 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 typeLevelParams, - PMap typeBounds, + // TODO: typeLevelArgs are redundant if we make typeBounds always have those as keys? + List typeLevelArgs, + PMap 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 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 typeLevelParams) { + return withTypeLevelParams(Optional.of(typeLevelParams)); + } + + private FunctionType withTypeLevelParams(Optional> 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 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, -- cgit v1.2.3