diff --git a/src/test/java/com/google/devtools/build/docgen/SkylarkDocumentationTest.java b/src/test/java/com/google/devtools/build/docgen/SkylarkDocumentationTest.java
index 4341cd0..d943a5e 100644
--- a/src/test/java/com/google/devtools/build/docgen/SkylarkDocumentationTest.java
+++ b/src/test/java/com/google/devtools/build/docgen/SkylarkDocumentationTest.java
@@ -27,8 +27,8 @@
 import com.google.devtools.build.lib.skylarkinterface.SkylarkGlobalLibrary;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
+import com.google.devtools.build.lib.syntax.Sequence;
 import com.google.devtools.build.lib.syntax.SkylarkDict;
-import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.syntax.StarlarkList;
 import com.google.devtools.build.lib.syntax.Tuple;
@@ -142,17 +142,16 @@
   @SkylarkModule(name = "MockClassF", doc = "MockClassF")
   private static class MockClassF implements SkylarkValue {
     @SkylarkCallable(
-      name = "test",
-      doc = "MockClassF#test",
-      parameters = {
-        @Param(name = "a", named = false, positional = true),
-        @Param(name = "b", named = true, positional = true),
-        @Param(name = "c", named = true, positional = false),
-        @Param(name = "d", named = true, positional = false, defaultValue = "1"),
-      },
-      extraPositionals = @Param(name = "myArgs")
-    )
-    public Integer test(int a, int b, int c, int d, SkylarkList<?> args) {
+        name = "test",
+        doc = "MockClassF#test",
+        parameters = {
+          @Param(name = "a", named = false, positional = true),
+          @Param(name = "b", named = true, positional = true),
+          @Param(name = "c", named = true, positional = false),
+          @Param(name = "d", named = true, positional = false, defaultValue = "1"),
+        },
+        extraPositionals = @Param(name = "myArgs"))
+    public Integer test(int a, int b, int c, int d, Sequence<?> args) {
       return 0;
     }
   }
@@ -180,18 +179,17 @@
   @SkylarkModule(name = "MockClassH", doc = "MockClassH")
   private static class MockClassH implements SkylarkValue {
     @SkylarkCallable(
-      name = "test",
-      doc = "MockClassH#test",
-      parameters = {
-        @Param(name = "a", named = false, positional = true),
-        @Param(name = "b", named = true, positional = true),
-        @Param(name = "c", named = true, positional = false),
-        @Param(name = "d", named = true, positional = false, defaultValue = "1"),
-      },
-      extraPositionals = @Param(name = "myArgs"),
-      extraKeywords = @Param(name = "myKwargs")
-    )
-    public Integer test(int a, int b, int c, int d, SkylarkList<?> args, SkylarkDict<?, ?> kwargs) {
+        name = "test",
+        doc = "MockClassH#test",
+        parameters = {
+          @Param(name = "a", named = false, positional = true),
+          @Param(name = "b", named = true, positional = true),
+          @Param(name = "c", named = true, positional = false),
+          @Param(name = "d", named = true, positional = false, defaultValue = "1"),
+        },
+        extraPositionals = @Param(name = "myArgs"),
+        extraKeywords = @Param(name = "myKwargs"))
+    public Integer test(int a, int b, int c, int d, Sequence<?> args, SkylarkDict<?, ?> kwargs) {
       return 0;
     }
   }
@@ -208,15 +206,14 @@
         name = "MockGlobalCallable",
         doc = "GlobalCallable documentation",
         parameters = {
-            @Param(name = "a", named = false, positional = true),
-            @Param(name = "b", named = true, positional = true),
-            @Param(name = "c", named = true, positional = false),
-            @Param(name = "d", named = true, positional = false, defaultValue = "1"),
+          @Param(name = "a", named = false, positional = true),
+          @Param(name = "b", named = true, positional = true),
+          @Param(name = "c", named = true, positional = false),
+          @Param(name = "d", named = true, positional = false, defaultValue = "1"),
         },
         extraPositionals = @Param(name = "myArgs"),
-        extraKeywords = @Param(name = "myKwargs")
-    )
-    public Integer test(int a, int b, int c, int d, SkylarkList<?> args, SkylarkDict<?, ?> kwargs) {
+        extraKeywords = @Param(name = "myKwargs"))
+    public Integer test(int a, int b, int c, int d, Sequence<?> args, SkylarkDict<?, ?> kwargs) {
       return 0;
     }
   }
@@ -248,7 +245,7 @@
     }
 
     @SkylarkCallable(name = "skylark", doc = "skylark")
-    public SkylarkList<Integer> getSkylarkList() {
+    public Sequence<Integer> getSkylarkList() {
       return null;
     }
   }
diff --git a/src/test/java/com/google/devtools/build/lib/rules/cpp/SkylarkCcCommonTest.java b/src/test/java/com/google/devtools/build/lib/rules/cpp/SkylarkCcCommonTest.java
index fa2cddc..eb72b8a 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/cpp/SkylarkCcCommonTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/cpp/SkylarkCcCommonTest.java
@@ -52,8 +52,8 @@
 import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.StringValueParser;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.EvalUtils;
+import com.google.devtools.build.lib.syntax.Sequence;
 import com.google.devtools.build.lib.syntax.SkylarkDict;
-import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.syntax.Starlark;
 import com.google.devtools.build.lib.syntax.StarlarkList;
@@ -271,8 +271,8 @@
 
     ConfiguredTarget r = getConfiguredTarget("//a:r");
     @SuppressWarnings("unchecked")
-    SkylarkList<String> requirements =
-        (SkylarkList<String>) getMyInfoFromTarget(r).getValue("requirements");
+    Sequence<String> requirements =
+        (Sequence<String>) getMyInfoFromTarget(r).getValue("requirements");
     assertThat(requirements).containsExactly("requires-yolo");
   }
 
@@ -386,8 +386,8 @@
 
     ConfiguredTarget r = getConfiguredTarget("//a:r");
     @SuppressWarnings("unchecked")
-    SkylarkList<String> commandLine =
-        (SkylarkList<String>) getMyInfoFromTarget(r).getValue("command_line");
+    Sequence<String> commandLine =
+        (Sequence<String>) getMyInfoFromTarget(r).getValue("command_line");
     RuleContext ruleContext = getRuleContext(r);
     CcToolchainProvider toolchain =
         CppHelper.getToolchain(
@@ -987,7 +987,7 @@
         .doesNotContain("-i_dont_want_to_see_this_on_archiver_command_line");
   }
 
-  private SkylarkList<String> commandLineForVariables(String actionName, String... variables)
+  private Sequence<String> commandLineForVariables(String actionName, String... variables)
       throws Exception {
     return commandLineForVariables(actionName, 0, variables);
   }
@@ -995,7 +995,7 @@
   // This method is only there to change the package to fix multiple runs of this method in a single
   // test.
   // TODO(b/109917616): Remove pkgSuffix argument when bzl files are not cached within single test
-  private SkylarkList<String> commandLineForVariables(
+  private Sequence<String> commandLineForVariables(
       String actionName, int pkgSuffix, String... variables) throws Exception {
     scratch.file(
         "a" + pkgSuffix + "/BUILD",
@@ -1033,8 +1033,7 @@
       return null;
     }
     @SuppressWarnings("unchecked")
-    SkylarkList<String> result =
-        (SkylarkList<String>) getMyInfoFromTarget(r).getValue("command_line");
+    Sequence<String> result = (Sequence<String>) getMyInfoFromTarget(r).getValue("command_line");
     return result;
   }
 
@@ -1336,8 +1335,8 @@
 
     StructImpl info = ((StructImpl) getMyInfoFromTarget(a).getValue("info"));
     @SuppressWarnings("unchecked")
-    SkylarkList<String> userLinkFlags =
-        (SkylarkList<String>) info.getValue("user_link_flags", SkylarkList.class);
+    Sequence<String> userLinkFlags =
+        (Sequence<String>) info.getValue("user_link_flags", Sequence.class);
     assertThat(userLinkFlags.getImmutableList())
         .containsExactly("-la", "-lc2", "-DEP2_LINKOPT", "-lc1", "-lc2", "-DEP1_LINKOPT");
     SkylarkNestedSet additionalInputs = info.getValue("additional_inputs", SkylarkNestedSet.class);
@@ -5440,8 +5439,8 @@
     ConfiguredTarget target = getConfiguredTarget("//foo:skylark_lib");
     assertThat(target).isNotNull();
     @SuppressWarnings("unchecked")
-    SkylarkList<LibraryToLink> libraries =
-        (SkylarkList<LibraryToLink>) getMyInfoFromTarget(target).getValue("libraries");
+    Sequence<LibraryToLink> libraries =
+        (Sequence<LibraryToLink>) getMyInfoFromTarget(target).getValue("libraries");
     assertThat(
             libraries.stream()
                 .map(x -> x.getResolvedSymlinkDynamicLibrary().getFilename())
diff --git a/src/test/java/com/google/devtools/build/lib/rules/java/JavaSkylarkApiTest.java b/src/test/java/com/google/devtools/build/lib/rules/java/JavaSkylarkApiTest.java
index f370e48..087a09b 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/java/JavaSkylarkApiTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/java/JavaSkylarkApiTest.java
@@ -32,7 +32,7 @@
 import com.google.devtools.build.lib.packages.SkylarkProvider.SkylarkKey;
 import com.google.devtools.build.lib.packages.StructImpl;
 import com.google.devtools.build.lib.rules.java.JavaRuleOutputJarsProvider.OutputJar;
-import com.google.devtools.build.lib.syntax.SkylarkList;
+import com.google.devtools.build.lib.syntax.Sequence;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.testutil.TestConstants;
 import com.google.devtools.build.lib.util.FileType;
@@ -322,7 +322,7 @@
     SkylarkNestedSet compileJars = ((SkylarkNestedSet) info.getValue("compile_jars"));
     SkylarkNestedSet fullCompileJars = ((SkylarkNestedSet) info.getValue("full_compile_jars"));
     @SuppressWarnings("unchecked")
-    SkylarkList<Artifact> sourceJars = ((SkylarkList<Artifact>) info.getValue("source_jars"));
+    Sequence<Artifact> sourceJars = ((Sequence<Artifact>) info.getValue("source_jars"));
     JavaRuleOutputJarsProvider outputs = ((JavaRuleOutputJarsProvider) info.getValue("outputs"));
 
     assertThat(artifactFilesNames(transitiveRuntimeJars.toCollection(Artifact.class)))
@@ -593,7 +593,7 @@
 
     ConfiguredTarget configuredTarget = getConfiguredTarget("//java/test:custom");
     JavaInfo info = configuredTarget.get(JavaInfo.PROVIDER);
-    SkylarkList<Artifact> sourceJars = info.getSourceJars();
+    Sequence<Artifact> sourceJars = info.getSourceJars();
     NestedSet<Artifact> transitiveSourceJars =
         info.getTransitiveSourceJars().getSet(Artifact.class);
     assertThat(artifactFilesNames(sourceJars)).containsExactly("libcustom-src.jar");
@@ -665,7 +665,7 @@
 
     ConfiguredTarget configuredTarget = getConfiguredTarget("//java/test:custom");
     JavaInfo info = configuredTarget.get(JavaInfo.PROVIDER);
-    SkylarkList<Artifact> sourceJars = info.getSourceJars();
+    Sequence<Artifact> sourceJars = info.getSourceJars();
     NestedSet<Artifact> transitiveSourceJars =
         info.getTransitiveSourceJars().getSet(Artifact.class);
     assertThat(artifactFilesNames(sourceJars))
@@ -717,7 +717,7 @@
 
     ConfiguredTarget configuredTarget = getConfiguredTarget("//java/test:custom");
     JavaInfo info = configuredTarget.get(JavaInfo.PROVIDER);
-    SkylarkList<Artifact> sourceJars = info.getSourceJars();
+    Sequence<Artifact> sourceJars = info.getSourceJars();
     assertThat(artifactFilesNames(sourceJars)).containsExactly("libcustom-src.jar");
     JavaRuleOutputJarsProvider outputJars = info.getOutputJars();
     assertThat(outputJars.getOutputJars()).hasSize(1);
@@ -771,7 +771,7 @@
 
     ConfiguredTarget configuredTarget = getConfiguredTarget("//java/test:custom");
     JavaInfo info = configuredTarget.get(JavaInfo.PROVIDER);
-    SkylarkList<Artifact> sourceJars = info.getSourceJars();
+    Sequence<Artifact> sourceJars = info.getSourceJars();
     assertThat(artifactFilesNames(sourceJars)).containsExactly("libcustom-src.jar");
     JavaRuleOutputJarsProvider outputJars = info.getOutputJars();
     assertThat(outputJars.getOutputJars()).hasSize(1);
@@ -827,7 +827,7 @@
 
     ConfiguredTarget configuredTarget = getConfiguredTarget("//java/test:custom");
     JavaInfo info = configuredTarget.get(JavaInfo.PROVIDER);
-    SkylarkList<Artifact> sourceJars = info.getSourceJars();
+    Sequence<Artifact> sourceJars = info.getSourceJars();
     assertThat(artifactFilesNames(sourceJars)).containsExactly("libcustom-mysrc.jar");
     JavaRuleOutputJarsProvider outputJars = info.getOutputJars();
     assertThat(outputJars.getOutputJars()).hasSize(1);
@@ -1349,7 +1349,7 @@
                 new SkylarkKey(
                     Label.parseAbsolute("//foo:extension.bzl", ImmutableMap.of()), "result"));
     @SuppressWarnings("unchecked")
-    SkylarkList<Artifact> sourceJars = (SkylarkList<Artifact>) (info.getValue("source_jars"));
+    Sequence<Artifact> sourceJars = (Sequence<Artifact>) (info.getValue("source_jars"));
     assertThat(prettyArtifactNames(sourceJars)).containsExactly("foo/libmy_java_lib_a-src.jar");
 
     assertThat(prettyArtifactNames(sourceJars)).doesNotContain("foo/libmy_java_lib_b-src.jar");
@@ -2165,8 +2165,7 @@
 
     ConfiguredTarget r = getConfiguredTarget("//a:r");
     @SuppressWarnings("unchecked") // Use an extra variable in order to suppress the warning.
-    SkylarkList<String> javacopts =
-        (SkylarkList<String>) getMyInfoFromTarget(r).getValue("javac_opts");
+    Sequence<String> javacopts = (Sequence<String>) getMyInfoFromTarget(r).getValue("javac_opts");
     assertThat(String.join(" ", javacopts)).contains("-source 6 -target 6");
   }
 
@@ -2192,8 +2191,7 @@
 
     ConfiguredTarget r = getConfiguredTarget("//a:r");
     @SuppressWarnings("unchecked") // Use an extra variable in order to suppress the warning.
-    SkylarkList<String> javacopts =
-        (SkylarkList<String>) getMyInfoFromTarget(r).getValue("javac_opts");
+    Sequence<String> javacopts = (Sequence<String>) getMyInfoFromTarget(r).getValue("javac_opts");
     assertThat(String.join(" ", javacopts)).contains("-source 6 -target 6");
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/rules/platform/ConstraintCollectionApiTest.java b/src/test/java/com/google/devtools/build/lib/rules/platform/ConstraintCollectionApiTest.java
index de693ed..18f7309 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/platform/ConstraintCollectionApiTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/platform/ConstraintCollectionApiTest.java
@@ -25,7 +25,7 @@
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.packages.SkylarkProvider.SkylarkKey;
 import com.google.devtools.build.lib.packages.StructImpl;
-import com.google.devtools.build.lib.syntax.SkylarkList;
+import com.google.devtools.build.lib.syntax.Sequence;
 import java.util.Collection;
 import java.util.Set;
 import java.util.stream.Collectors;
@@ -168,8 +168,8 @@
         .isEqualTo(Label.parseAbsoluteUnchecked("//foo:value1"));
 
     @SuppressWarnings("unchecked")
-    SkylarkList<ConstraintSettingInfo> usedConstraints =
-        (SkylarkList<ConstraintSettingInfo>) info.getValue("used_constraints");
+    Sequence<ConstraintSettingInfo> usedConstraints =
+        (Sequence<ConstraintSettingInfo>) info.getValue("used_constraints");
     assertThat(usedConstraints).isNotNull();
     assertThat(usedConstraints)
         .containsExactly(
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkActionProviderTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkActionProviderTest.java
index befdd40..ddff11d 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkActionProviderTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkActionProviderTest.java
@@ -26,8 +26,8 @@
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.packages.SkylarkProvider.SkylarkKey;
 import com.google.devtools.build.lib.packages.StructImpl;
+import com.google.devtools.build.lib.syntax.Sequence;
 import com.google.devtools.build.lib.syntax.SkylarkDict;
-import com.google.devtools.build.lib.syntax.SkylarkList;
 import java.util.List;
 import java.util.stream.Collectors;
 import org.junit.Test;
@@ -66,8 +66,8 @@
     StructImpl fooProvider = (StructImpl) configuredAspect.get(fooKey);
     assertThat(fooProvider.getValue("actions")).isNotNull();
     @SuppressWarnings("unchecked")
-    SkylarkList<ActionAnalysisMetadata> actions =
-        (SkylarkList<ActionAnalysisMetadata>) fooProvider.getValue("actions");
+    Sequence<ActionAnalysisMetadata> actions =
+        (Sequence<ActionAnalysisMetadata>) fooProvider.getValue("actions");
     assertThat(actions).isNotEmpty();
 
     ActionAnalysisMetadata action = actions.get(0);
@@ -121,37 +121,34 @@
     StructImpl fooProvider = (StructImpl) configuredAspect.get(fooKey);
     assertThat(fooProvider.getValue("actions")).isNotNull();
 
-    SkylarkList<ActionAnalysisMetadata> actions =
-        (SkylarkList<ActionAnalysisMetadata>) fooProvider.getValue("actions");
+    Sequence<ActionAnalysisMetadata> actions =
+        (Sequence<ActionAnalysisMetadata>) fooProvider.getValue("actions");
     assertThat(actions).hasSize(2);
 
-    SkylarkList<String> mnemonics =
-        (SkylarkList<String>) fooProvider.getValue("mnemonics");
+    Sequence<String> mnemonics = (Sequence<String>) fooProvider.getValue("mnemonics");
     assertThat(mnemonics).containsExactly("MyAction0", "MyAction1");
 
-    SkylarkList<SkylarkDict<String, String>> envs =
-        (SkylarkList<SkylarkDict<String, String>>) fooProvider.getValue("envs");
+    Sequence<SkylarkDict<String, String>> envs =
+        (Sequence<SkylarkDict<String, String>>) fooProvider.getValue("envs");
     assertThat(envs).containsExactly(
         SkylarkDict.of(null, "foo", "bar", "pet", "puppy"),
         SkylarkDict.of(null, "pet", "bunny"));
 
-    SkylarkList<SkylarkList<Artifact>> inputs =
-        (SkylarkList<SkylarkList<Artifact>>) fooProvider.getValue("inputs");
+    Sequence<Sequence<Artifact>> inputs =
+        (Sequence<Sequence<Artifact>>) fooProvider.getValue("inputs");
     assertThat(flattenArtifactNames(inputs)).containsExactly("executable");
 
-    SkylarkList<SkylarkList<Artifact>> outputs =
-        (SkylarkList<SkylarkList<Artifact>>) fooProvider.getValue("outputs");
+    Sequence<Sequence<Artifact>> outputs =
+        (Sequence<Sequence<Artifact>>) fooProvider.getValue("outputs");
     assertThat(flattenArtifactNames(outputs)).containsExactly("myfile0", "executable", "myfile1");
 
-    SkylarkList<SkylarkList<String>> argv =
-        (SkylarkList<SkylarkList<String>>) fooProvider.getValue("argv");
+    Sequence<Sequence<String>> argv = (Sequence<Sequence<String>>) fooProvider.getValue("argv");
     assertThat(argv.get(0)).hasSize(1);
     assertThat(argv.get(0).get(0)).endsWith("executable");
     assertThat(argv.get(1)).contains("fakecmd");
   }
 
-  private static List<String> flattenArtifactNames(
-      SkylarkList<SkylarkList<Artifact>> artifactLists) {
+  private static List<String> flattenArtifactNames(Sequence<Sequence<Artifact>> artifactLists) {
     return artifactLists.stream()
         .flatMap(artifacts -> artifacts.stream())
         .map(artifact -> artifact.getFilename())
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkDefinedAspectsTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkDefinedAspectsTest.java
index 379fbce..5314287 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkDefinedAspectsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkDefinedAspectsTest.java
@@ -45,7 +45,7 @@
 import com.google.devtools.build.lib.rules.java.JavaConfiguration;
 import com.google.devtools.build.lib.rules.objc.ObjcProtoProvider;
 import com.google.devtools.build.lib.skyframe.AspectValue;
-import com.google.devtools.build.lib.syntax.SkylarkList;
+import com.google.devtools.build.lib.syntax.Sequence;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import java.util.Arrays;
@@ -1945,7 +1945,7 @@
         "r2(name = 'r2', dep = ':r1')");
     AnalysisResult analysisResult = update("//test:r2");
     ConfiguredTarget target = Iterables.getOnlyElement(analysisResult.getTargetsToBuild());
-    SkylarkList<?> result = (SkylarkList) target.get("result");
+    Sequence<?> result = (Sequence) target.get("result");
 
     // "yes" means that aspect a2 sees a1's providers.
     assertThat(result)
@@ -2009,7 +2009,7 @@
         "rcollect(name = 'rcollect', deps = [':r1', ':r2'])");
     AnalysisResult analysisResult = update("//test:rcollect");
     ConfiguredTarget target = Iterables.getOnlyElement(analysisResult.getTargetsToBuild());
-    SkylarkList<?> result = (SkylarkList) target.get("result");
+    Sequence<?> result = (Sequence) target.get("result");
     assertThat(result)
         .containsExactly(
             "//test:r0[\"//test:aspect.bzl%a1\", \"//test:aspect.bzl%a3\"]=a1p",
@@ -2059,7 +2059,7 @@
         "r2(name = 'r2', dep = ':r1')");
     AnalysisResult analysisResult = update("//test:r2");
     ConfiguredTarget target = Iterables.getOnlyElement(analysisResult.getTargetsToBuild());
-    SkylarkList<?> result = (SkylarkList) target.get("result");
+    Sequence<?> result = (Sequence) target.get("result");
     // "yes" means that aspect a2 sees a1's providers.
     assertThat(result)
         .containsExactly(
@@ -2102,7 +2102,7 @@
         "r2(name = 'r2', dep = ':r1')");
     AnalysisResult analysisResult = update("//test:r2");
     ConfiguredTarget target = Iterables.getOnlyElement(analysisResult.getTargetsToBuild());
-    SkylarkList<?> result = (SkylarkList<?>) target.get("result");
+    Sequence<?> result = (Sequence<?>) target.get("result");
 
     // "yes" means that aspect a2 sees a1's providers.
     assertThat(result)
@@ -2141,7 +2141,7 @@
         "r(name = 'r2', dep = ':r1')");
     AnalysisResult analysisResult = update("//test:r2");
     ConfiguredTarget target = Iterables.getOnlyElement(analysisResult.getTargetsToBuild());
-    SkylarkList<?> result = (SkylarkList<?>) target.get("result");
+    Sequence<?> result = (Sequence<?>) target.get("result");
 
     assertThat(result)
         .containsExactly(
@@ -2343,7 +2343,7 @@
     SkylarkKey p3 =
         new SkylarkKey(Label.parseAbsolute("//test:aspect.bzl", ImmutableMap.of()), "p3");
     StructImpl p3Provider = (StructImpl) configuredAspect.get(p3);
-    assertThat((SkylarkList<?>) p3Provider.getValue("value"))
+    assertThat((Sequence<?>) p3Provider.getValue("value"))
         .containsExactly(
             "//test:r0_1=True",
             "//test:r0_2=True",
@@ -2406,7 +2406,7 @@
     SkylarkKey pCollector =
         new SkylarkKey(Label.parseAbsolute("//test:aspect.bzl", ImmutableMap.of()), "PCollector");
     StructImpl pCollectorProvider = (StructImpl) configuredTarget.get(pCollector);
-    assertThat((SkylarkList<?>) pCollectorProvider.getValue("result"))
+    assertThat((Sequence<?>) pCollectorProvider.getValue("result"))
         .containsExactly("//test:r1", "//test:r0", "//test:r0+PAspect");
   }
 
@@ -2686,7 +2686,7 @@
         "r2(name = 'r2', dep = ':r1')");
     AnalysisResult analysisResult = update("//test:r2");
     ConfiguredTarget target = Iterables.getOnlyElement(analysisResult.getTargetsToBuild());
-    SkylarkList<?> result = (SkylarkList<?>) target.get("result");
+    Sequence<?> result = (Sequence<?>) target.get("result");
 
     // We should see both the action from the 'r0' rule, and the action from the 'a1' aspect
     assertThat(result).hasSize(2);
@@ -2890,12 +2890,12 @@
     StructImpl rootInfoWithFiles = (StructImpl) targetWithFiles.get(rootInfoKey);
     // With apply_to_generating_rules=True, the aspect should have traversed :beta_output and
     // applied to both :beta and :charlie.
-    assertThat(rootInfoWithFiles.getValue("from_aspect", SkylarkList.class))
+    assertThat(rootInfoWithFiles.getValue("from_aspect", Sequence.class))
         .containsExactly(
             Label.parseAbsolute("//test:charlie", ImmutableMap.of()),
             Label.parseAbsolute("//test:beta", ImmutableMap.of()),
             Label.parseAbsolute("//test:alpha", ImmutableMap.of()));
-    assertThat(rootInfoWithFiles.getValue("non_aspect", SkylarkList.class))
+    assertThat(rootInfoWithFiles.getValue("non_aspect", Sequence.class))
         .containsExactly(Label.parseAbsolute("//test:alpha", ImmutableMap.of()));
 
     AnalysisResult analysisResultNoFiles = update("//test:test_no_files");
@@ -2904,9 +2904,9 @@
     StructImpl rootInfoNoFiles = (StructImpl) targetNoFiles.get(rootInfoKey);
     // With apply_to_generating_rules=False, the aspect should have only accessed :alpha, as it
     // must have stopped before :beta_output.
-    assertThat(rootInfoNoFiles.getValue("from_aspect", SkylarkList.class))
+    assertThat(rootInfoNoFiles.getValue("from_aspect", Sequence.class))
         .containsExactly(Label.parseAbsolute("//test:alpha", ImmutableMap.of()));
-    assertThat(rootInfoWithFiles.getValue("non_aspect", SkylarkList.class))
+    assertThat(rootInfoWithFiles.getValue("non_aspect", Sequence.class))
         .containsExactly(Label.parseAbsolute("//test:alpha", ImmutableMap.of()));
   }
 
@@ -3004,13 +3004,13 @@
     StructImpl rootInfo = (StructImpl) target.get(rootInfoKey);
     StructImpl depInfo = (StructImpl) target.get(depInfoKey);
 
-    assertThat(rootInfo.getValue("both_labels", SkylarkList.class))
+    assertThat(rootInfo.getValue("both_labels", Sequence.class))
         .containsExactly(
             Label.parseAbsolute("//test:alpha", ImmutableMap.of()),
             Label.parseAbsolute("//test:beta_output", ImmutableMap.of()),
             Label.parseAbsolute("//test:charlie", ImmutableMap.of()));
-    assertThat(rootInfo.getValue("root_only_labels", SkylarkList.class)).isEmpty();
-    assertThat(depInfo.getValue("labels", SkylarkList.class))
+    assertThat(rootInfo.getValue("root_only_labels", Sequence.class)).isEmpty();
+    assertThat(depInfo.getValue("labels", Sequence.class))
         .containsExactly(
             Label.parseAbsolute("//test:alpha", ImmutableMap.of()),
             Label.parseAbsolute("//test:beta", ImmutableMap.of()),
@@ -3032,10 +3032,10 @@
     StructImpl rootInfo = (StructImpl) target.get(rootInfoKey);
     StructImpl depInfo = (StructImpl) target.get(depInfoKey);
 
-    assertThat(rootInfo.getValue("both_labels", SkylarkList.class))
+    assertThat(rootInfo.getValue("both_labels", Sequence.class))
         .containsExactly(Label.parseAbsolute("//test:alpha", ImmutableMap.of()));
-    assertThat(rootInfo.getValue("root_only_labels", SkylarkList.class)).isEmpty();
-    assertThat(depInfo.getValue("labels", SkylarkList.class))
+    assertThat(rootInfo.getValue("root_only_labels", Sequence.class)).isEmpty();
+    assertThat(depInfo.getValue("labels", Sequence.class))
         .containsExactly(Label.parseAbsolute("//test:alpha", ImmutableMap.of()));
   }
 
@@ -3054,13 +3054,13 @@
     StructImpl rootInfo = (StructImpl) target.get(rootInfoKey);
     StructImpl depInfo = (StructImpl) target.get(depInfoKey);
 
-    assertThat(rootInfo.getValue("both_labels", SkylarkList.class))
+    assertThat(rootInfo.getValue("both_labels", Sequence.class))
         .containsExactly(Label.parseAbsolute("//test:alpha", ImmutableMap.of()));
-    assertThat(rootInfo.getValue("root_only_labels", SkylarkList.class))
+    assertThat(rootInfo.getValue("root_only_labels", Sequence.class))
         .containsExactly(
             Label.parseAbsolute("//test:beta_output", ImmutableMap.of()),
             Label.parseAbsolute("//test:charlie", ImmutableMap.of()));
-    assertThat(depInfo.getValue("labels", SkylarkList.class))
+    assertThat(depInfo.getValue("labels", Sequence.class))
         .containsExactly(Label.parseAbsolute("//test:alpha", ImmutableMap.of()));
   }
 
@@ -3079,10 +3079,10 @@
     StructImpl rootInfo = (StructImpl) target.get(rootInfoKey);
     StructImpl depInfo = (StructImpl) target.get(depInfoKey);
 
-    assertThat(rootInfo.getValue("both_labels", SkylarkList.class))
+    assertThat(rootInfo.getValue("both_labels", Sequence.class))
         .containsExactly(Label.parseAbsolute("//test:alpha", ImmutableMap.of()));
-    assertThat(rootInfo.getValue("root_only_labels", SkylarkList.class)).isEmpty();
-    assertThat(depInfo.getValue("labels", SkylarkList.class))
+    assertThat(rootInfo.getValue("root_only_labels", Sequence.class)).isEmpty();
+    assertThat(depInfo.getValue("labels", Sequence.class))
         .containsExactly(
             Label.parseAbsolute("//test:alpha", ImmutableMap.of()),
             Label.parseAbsolute("//test:beta", ImmutableMap.of()),
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkIntegrationTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkIntegrationTest.java
index 820eccc..433b989 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkIntegrationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkIntegrationTest.java
@@ -55,7 +55,7 @@
 import com.google.devtools.build.lib.skyframe.PackageFunction;
 import com.google.devtools.build.lib.skyframe.SkyFunctions;
 import com.google.devtools.build.lib.skyframe.SkylarkImportLookupFunction;
-import com.google.devtools.build.lib.syntax.SkylarkList;
+import com.google.devtools.build.lib.syntax.Sequence;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.syntax.Starlark;
 import com.google.devtools.build.lib.syntax.StarlarkList;
@@ -294,7 +294,7 @@
         .containsExactlyElementsIn(hiddenTopLevelArtifacts);
     assertThat(myInfo.getValue("has_key1")).isEqualTo(Boolean.TRUE);
     assertThat(myInfo.getValue("has_key2")).isEqualTo(Boolean.FALSE);
-    assertThat((SkylarkList) myInfo.getValue("all_keys"))
+    assertThat((Sequence) myInfo.getValue("all_keys"))
         .containsExactly(
             OutputGroupInfo.HIDDEN_TOP_LEVEL,
             OutputGroupInfo.COMPILATION_PREREQUISITES,
@@ -2225,8 +2225,8 @@
     StructImpl outerDepInfo = (StructImpl) outerTarget.get(myDepKey);
     StructImpl innerInfo = (StructImpl) outerDepInfo.getValue("info");
 
-    assertThat((SkylarkList) outerInfo.getValue("copts")).containsExactly("yeehaw");
-    assertThat((SkylarkList) innerInfo.getValue("copts")).containsExactly("cowabunga");
+    assertThat((Sequence) outerInfo.getValue("copts")).containsExactly("yeehaw");
+    assertThat((Sequence) innerInfo.getValue("copts")).containsExactly("cowabunga");
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleContextTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleContextTest.java
index 423f92e..fe8fc13 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleContextTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleContextTest.java
@@ -47,8 +47,8 @@
 import com.google.devtools.build.lib.rules.java.JavaSourceJarsProvider;
 import com.google.devtools.build.lib.rules.python.PyProviderUtils;
 import com.google.devtools.build.lib.skylark.util.SkylarkTestCase;
+import com.google.devtools.build.lib.syntax.Sequence;
 import com.google.devtools.build.lib.syntax.SkylarkDict;
-import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.syntax.Starlark;
 import com.google.devtools.build.lib.syntax.StarlarkList;
@@ -458,8 +458,8 @@
   }
 
   private void assertArtifactList(Object result, List<String> artifacts) {
-    assertThat(result).isInstanceOf(SkylarkList.class);
-    SkylarkList<?> resultList = (SkylarkList) result;
+    assertThat(result).isInstanceOf(Sequence.class);
+    Sequence<?> resultList = (Sequence) result;
     assertThat(resultList).hasSize(artifacts.size());
     int i = 0;
     for (String artifact : artifacts) {
@@ -473,7 +473,7 @@
     setRuleContext(ruleContext);
     Object result = eval("ruleContext.attr.srcs");
     // Check for a known provider
-    TransitiveInfoCollection tic1 = (TransitiveInfoCollection) ((SkylarkList) result).get(0);
+    TransitiveInfoCollection tic1 = (TransitiveInfoCollection) ((Sequence) result).get(0);
     assertThat(JavaInfo.getProvider(JavaSourceJarsProvider.class, tic1)).isNotNull();
     // Check an unimplemented provider too
     assertThat(PyProviderUtils.hasLegacyProvider(tic1)).isFalse();
@@ -494,7 +494,7 @@
     SkylarkRuleContext ruleContext = createRuleContext("//foo:foo");
     setRuleContext(ruleContext);
     Object result = eval("ruleContext.attr.outs");
-    assertThat(result).isInstanceOf(SkylarkList.class);
+    assertThat(result).isInstanceOf(Sequence.class);
   }
 
   @Test
@@ -646,7 +646,7 @@
     SkylarkRuleContext ruleContext = createRuleContext("//foo:foo");
     setRuleContext(ruleContext);
     Object result = eval("ruleContext.attr.outs");
-    assertThat(((SkylarkList) result)).hasSize(1);
+    assertThat(((Sequence) result)).hasSize(1);
   }
 
   @Test
@@ -654,7 +654,7 @@
     SkylarkRuleContext ruleContext = createRuleContext("//foo:foo");
     setRuleContext(ruleContext);
     Object result = eval("ruleContext.attr.outs");
-    assertThat(((SkylarkList) result)).hasSize(1);
+    assertThat(((Sequence) result)).hasSize(1);
   }
 
   @Test
@@ -865,14 +865,14 @@
   public void testFeatures() throws Exception {
     setRuleContext(createRuleContext("//foo:cc_with_features"));
     Object result = eval("ruleContext.features");
-    assertThat((SkylarkList) result).containsExactly("cc_include_scanning", "f1", "f2");
+    assertThat((Sequence) result).containsExactly("cc_include_scanning", "f1", "f2");
   }
 
   @Test
   public void testDisabledFeatures() throws Exception {
     setRuleContext(createRuleContext("//foo:cc_with_features"));
     Object result = eval("ruleContext.disabled_features");
-    assertThat((SkylarkList) result).containsExactly("f3");
+    assertThat((Sequence) result).containsExactly("f3");
   }
 
   @Test
@@ -1571,19 +1571,19 @@
     setRuleContext(createRuleContext("//test:foo"));
     Object filenames =
         eval("[f.short_path for f in ruleContext.attr.dep.default_runfiles.files.to_list()]");
-    assertThat(filenames).isInstanceOf(SkylarkList.class);
-    SkylarkList<?> filenamesList = (SkylarkList) filenames;
+    assertThat(filenames).isInstanceOf(Sequence.class);
+    Sequence<?> filenamesList = (Sequence) filenames;
     assertThat(filenamesList).containsAtLeast("test/lib.py", "test/lib2.py");
     Object emptyFilenames = eval("ruleContext.attr.dep.default_runfiles.empty_filenames.to_list()");
-    assertThat(emptyFilenames).isInstanceOf(SkylarkList.class);
-    SkylarkList<?> emptyFilenamesList = (SkylarkList) emptyFilenames;
+    assertThat(emptyFilenames).isInstanceOf(Sequence.class);
+    Sequence<?> emptyFilenamesList = (Sequence) emptyFilenames;
     assertThat(emptyFilenamesList).containsExactly("test/__init__.py");
 
     setRuleContext(createRuleContext("//test:foo_with_init"));
     Object noEmptyFilenames =
         eval("ruleContext.attr.dep.default_runfiles.empty_filenames.to_list()");
-    assertThat(noEmptyFilenames).isInstanceOf(SkylarkList.class);
-    SkylarkList<?> noEmptyFilenamesList = (SkylarkList) noEmptyFilenames;
+    assertThat(noEmptyFilenames).isInstanceOf(Sequence.class);
+    Sequence<?> noEmptyFilenamesList = (Sequence) noEmptyFilenames;
     assertThat(noEmptyFilenamesList).isEmpty();
   }
 
@@ -1622,15 +1622,15 @@
     setRuleContext(createRuleContext("//test:test_with_symlink"));
     Object symlinkPaths =
         eval("[s.path for s in ruleContext.attr.data[0].data_runfiles.symlinks.to_list()]");
-    assertThat(symlinkPaths).isInstanceOf(SkylarkList.class);
-    SkylarkList<?> symlinkPathsList = (SkylarkList) symlinkPaths;
+    assertThat(symlinkPaths).isInstanceOf(Sequence.class);
+    Sequence<?> symlinkPathsList = (Sequence) symlinkPaths;
     assertThat(symlinkPathsList).containsExactly("symlink_test/a.py").inOrder();
     Object symlinkFilenames =
         eval(
             "[s.target_file.short_path for s in"
                 + " ruleContext.attr.data[0].data_runfiles.symlinks.to_list()]");
-    assertThat(symlinkFilenames).isInstanceOf(SkylarkList.class);
-    SkylarkList<?> symlinkFilenamesList = (SkylarkList) symlinkFilenames;
+    assertThat(symlinkFilenames).isInstanceOf(Sequence.class);
+    Sequence<?> symlinkFilenamesList = (Sequence) symlinkFilenames;
     assertThat(symlinkFilenamesList).containsExactly("test/a.py").inOrder();
   }
 
@@ -1668,15 +1668,15 @@
     setRuleContext(createRuleContext("//test:test_with_symlink"));
     Object symlinkPaths =
         eval("[s.path for s in ruleContext.attr.data[0].data_runfiles.symlinks.to_list()]");
-    assertThat(symlinkPaths).isInstanceOf(SkylarkList.class);
-    SkylarkList<?> symlinkPathsList = (SkylarkList) symlinkPaths;
+    assertThat(symlinkPaths).isInstanceOf(Sequence.class);
+    Sequence<?> symlinkPathsList = (Sequence) symlinkPaths;
     assertThat(symlinkPathsList).containsExactly("symlink_test/a.py").inOrder();
     Object symlinkFilenames =
         eval(
             "[s.target_file.short_path for s in"
                 + " ruleContext.attr.data[0].data_runfiles.symlinks.to_list()]");
-    assertThat(symlinkFilenames).isInstanceOf(SkylarkList.class);
-    SkylarkList<?> symlinkFilenamesList = (SkylarkList) symlinkFilenames;
+    assertThat(symlinkFilenames).isInstanceOf(Sequence.class);
+    Sequence<?> symlinkFilenamesList = (Sequence) symlinkFilenames;
     assertThat(symlinkFilenamesList).containsExactly("test/a.py").inOrder();
   }
 
@@ -1715,15 +1715,15 @@
     setRuleContext(createRuleContext("//test:test_with_root_symlink"));
     Object rootSymlinkPaths =
         eval("[s.path for s in ruleContext.attr.data[0].data_runfiles.root_symlinks.to_list()]");
-    assertThat(rootSymlinkPaths).isInstanceOf(SkylarkList.class);
-    SkylarkList<?> rootSymlinkPathsList = (SkylarkList) rootSymlinkPaths;
+    assertThat(rootSymlinkPaths).isInstanceOf(Sequence.class);
+    Sequence<?> rootSymlinkPathsList = (Sequence) rootSymlinkPaths;
     assertThat(rootSymlinkPathsList).containsExactly("root_symlink_test/a.py").inOrder();
     Object rootSymlinkFilenames =
         eval(
             "[s.target_file.short_path for s in"
                 + " ruleContext.attr.data[0].data_runfiles.root_symlinks.to_list()]");
-    assertThat(rootSymlinkFilenames).isInstanceOf(SkylarkList.class);
-    SkylarkList<?> rootSymlinkFilenamesList = (SkylarkList) rootSymlinkFilenames;
+    assertThat(rootSymlinkFilenames).isInstanceOf(Sequence.class);
+    Sequence<?> rootSymlinkFilenamesList = (Sequence) rootSymlinkFilenames;
     assertThat(rootSymlinkFilenamesList).containsExactly("test/a.py").inOrder();
   }
 
@@ -1761,15 +1761,15 @@
     setRuleContext(createRuleContext("//test:test_with_root_symlink"));
     Object rootSymlinkPaths =
         eval("[s.path for s in ruleContext.attr.data[0].data_runfiles.root_symlinks.to_list()]");
-    assertThat(rootSymlinkPaths).isInstanceOf(SkylarkList.class);
-    SkylarkList<?> rootSymlinkPathsList = (SkylarkList) rootSymlinkPaths;
+    assertThat(rootSymlinkPaths).isInstanceOf(Sequence.class);
+    Sequence<?> rootSymlinkPathsList = (Sequence) rootSymlinkPaths;
     assertThat(rootSymlinkPathsList).containsExactly("root_symlink_test/a.py").inOrder();
     Object rootSymlinkFilenames =
         eval(
             "[s.target_file.short_path for s in"
                 + " ruleContext.attr.data[0].data_runfiles.root_symlinks.to_list()]");
-    assertThat(rootSymlinkFilenames).isInstanceOf(SkylarkList.class);
-    SkylarkList<?> rootSymlinkFilenamesList = (SkylarkList) rootSymlinkFilenames;
+    assertThat(rootSymlinkFilenames).isInstanceOf(Sequence.class);
+    Sequence<?> rootSymlinkFilenamesList = (Sequence) rootSymlinkFilenames;
     assertThat(rootSymlinkFilenamesList).containsExactly("test/a.py").inOrder();
   }
 
@@ -2445,7 +2445,7 @@
         new SkylarkKey(Label.parseAbsolute("//a:a.bzl", ImmutableMap.of()), "key_provider");
 
     SkylarkInfo keyInfo = (SkylarkInfo) a.get(key);
-    SkylarkList<?> keys = (SkylarkList) keyInfo.getValue("keys");
+    Sequence<?> keys = (Sequence) keyInfo.getValue("keys");
     assertThat(keys).containsExactly("c", "b", "a", "f", "e", "d").inOrder();
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleImplementationFunctionsTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleImplementationFunctionsTest.java
index 8e67867..e01f42a 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleImplementationFunctionsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleImplementationFunctionsTest.java
@@ -61,7 +61,7 @@
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.EvalUtils;
 import com.google.devtools.build.lib.syntax.Printer;
-import com.google.devtools.build.lib.syntax.SkylarkList;
+import com.google.devtools.build.lib.syntax.Sequence;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.syntax.Starlark;
 import com.google.devtools.build.lib.syntax.StarlarkList;
@@ -2912,7 +2912,7 @@
         "directory = ruleContext.actions.declare_directory('dir')",
         "def _short_path(f): return f.short_path", // For easier assertions
         "args.add_all([directory], map_each=_short_path)");
-    SkylarkList<?> result = (SkylarkList<?>) eval("args, directory");
+    Sequence<?> result = (Sequence<?>) eval("args, directory");
     Args args = (Args) result.get(0);
     Artifact directory = (Artifact) result.get(1);
     CommandLine commandLine = args.build();
@@ -2939,7 +2939,7 @@
         "def _short_path(f): return f.short_path", // For easier assertions
         "args.add_all([directory], map_each=_short_path, expand_directories=True)",
         "args.add_all([directory], map_each=_short_path, expand_directories=False)");
-    SkylarkList<?> result = (SkylarkList<?>) eval("args, directory");
+    Sequence<?> result = (Sequence<?>) eval("args, directory");
     Args args = (Args) result.get(0);
     Artifact directory = (Artifact) result.get(1);
     CommandLine commandLine = args.build();
@@ -2974,7 +2974,7 @@
         "args.add_all([directory])",
         "params = ruleContext.actions.declare_file('params')",
         "ruleContext.actions.write(params, args)");
-    SkylarkList<?> result = (SkylarkList<?>) eval("params, directory");
+    Sequence<?> result = (Sequence<?>) eval("params, directory");
     Artifact params = (Artifact) result.get(0);
     Artifact directory = (Artifact) result.get(1);
     ActionAnalysisMetadata action =
diff --git a/src/test/java/com/google/devtools/build/lib/skylarkdebug/server/SkylarkDebugServerTest.java b/src/test/java/com/google/devtools/build/lib/skylarkdebug/server/SkylarkDebugServerTest.java
index 244d541..a0ee468 100644
--- a/src/test/java/com/google/devtools/build/lib/skylarkdebug/server/SkylarkDebugServerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylarkdebug/server/SkylarkDebugServerTest.java
@@ -42,7 +42,7 @@
 import com.google.devtools.build.lib.syntax.EvalUtils;
 import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.syntax.ParserInput;
-import com.google.devtools.build.lib.syntax.SkylarkList;
+import com.google.devtools.build.lib.syntax.Sequence;
 import com.google.devtools.build.lib.syntax.Starlark;
 import com.google.devtools.build.lib.syntax.StarlarkFile;
 import com.google.devtools.build.lib.syntax.StarlarkThread;
@@ -367,7 +367,7 @@
                 Scope.newBuilder()
                     .setName("global")
                     .addBinding(
-                        getValueProto("x", SkylarkList.createImmutable(ImmutableList.of(1, 2, 3)))))
+                        getValueProto("x", Sequence.createImmutable(ImmutableList.of(1, 2, 3)))))
             .build());
   }
 
@@ -391,7 +391,7 @@
     Value xValue = frames.getFrame(0).getScope(0).getBinding(0);
 
     assertValuesEqualIgnoringId(
-        xValue, getValueProto("x", SkylarkList.createImmutable(ImmutableList.of(1, 2, 3))));
+        xValue, getValueProto("x", Sequence.createImmutable(ImmutableList.of(1, 2, 3))));
 
     List<Value> children = getChildren(xValue);
 
@@ -522,7 +522,7 @@
 
     ListFramesResponse frames = listFrames(threadId);
     assertThat(frames.getFrame(0).getScope(0).getBindingList())
-        .contains(getValueProto("x", SkylarkList.createImmutable(ImmutableList.of(5, 6))));
+        .contains(getValueProto("x", Sequence.createImmutable(ImmutableList.of(5, 6))));
   }
 
   @Test
@@ -556,7 +556,7 @@
 
     ListFramesResponse frames = listFrames(threadId);
     assertThat(frames.getFrame(0).getScope(0).getBindingList())
-        .contains(getValueProto("x", SkylarkList.createImmutable(ImmutableList.of(1, 2, 3, 4))));
+        .contains(getValueProto("x", Sequence.createImmutable(ImmutableList.of(1, 2, 3, 4))));
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/skylarkinterface/processor/testsources/GoldenCase.java b/src/test/java/com/google/devtools/build/lib/skylarkinterface/processor/testsources/GoldenCase.java
index a3200bf..a2214dc 100644
--- a/src/test/java/com/google/devtools/build/lib/skylarkinterface/processor/testsources/GoldenCase.java
+++ b/src/test/java/com/google/devtools/build/lib/skylarkinterface/processor/testsources/GoldenCase.java
@@ -20,8 +20,8 @@
 import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
 import com.google.devtools.build.lib.syntax.FuncallExpression;
+import com.google.devtools.build.lib.syntax.Sequence;
 import com.google.devtools.build.lib.syntax.SkylarkDict;
-import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.StarlarkSemantics;
 import com.google.devtools.build.lib.syntax.StarlarkThread;
 
@@ -193,11 +193,7 @@
       extraKeywords = @Param(name = "kwargs"),
       useStarlarkThread = true)
   public String twoArgMethodWithParamsAndInfoAndKwargs(
-      String one,
-      Integer two,
-      SkylarkList<?> args,
-      SkylarkDict<?, ?> kwargs,
-      StarlarkThread thread) {
+      String one, Integer two, Sequence<?> args, SkylarkDict<?, ?> kwargs, StarlarkThread thread) {
     return "yar";
   }
 
@@ -230,10 +226,10 @@
       name = "method_with_list_and_dict",
       documented = false,
       parameters = {
-        @Param(name = "one", type = SkylarkList.class, named = true),
+        @Param(name = "one", type = Sequence.class, named = true),
         @Param(name = "two", type = SkylarkDict.class, named = true),
       })
-  public String methodWithListandDict(SkylarkList<?> one, SkylarkDict<?, ?> two) {
+  public String methodWithListandDict(Sequence<?> one, SkylarkDict<?, ?> two) {
     return "bar";
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/skylarkinterface/processor/testsources/SpecifiedGenericType.java b/src/test/java/com/google/devtools/build/lib/skylarkinterface/processor/testsources/SpecifiedGenericType.java
index 0d0755c..19dbae0 100644
--- a/src/test/java/com/google/devtools/build/lib/skylarkinterface/processor/testsources/SpecifiedGenericType.java
+++ b/src/test/java/com/google/devtools/build/lib/skylarkinterface/processor/testsources/SpecifiedGenericType.java
@@ -17,8 +17,8 @@
 import com.google.devtools.build.lib.skylarkinterface.Param;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
+import com.google.devtools.build.lib.syntax.Sequence;
 import com.google.devtools.build.lib.syntax.SkylarkDict;
-import com.google.devtools.build.lib.syntax.SkylarkList;
 
 /**
  * Test case for a SkylarkCallable method which has a parameter with an unsafely specified generic
@@ -31,7 +31,7 @@
       name = "specified_generic_type",
       documented = false,
       parameters = {
-        @Param(name = "one", type = SkylarkList.class, named = true),
+        @Param(name = "one", type = Sequence.class, named = true),
       })
   public String specifiedGenericType(SkylarkDict<?, String> one) {
     return "bar";
diff --git a/src/test/java/com/google/devtools/build/lib/skylarkinterface/processor/testsources/StructFieldWithExtraArgs.java b/src/test/java/com/google/devtools/build/lib/skylarkinterface/processor/testsources/StructFieldWithExtraArgs.java
index 1472480..f3b1f04 100644
--- a/src/test/java/com/google/devtools/build/lib/skylarkinterface/processor/testsources/StructFieldWithExtraArgs.java
+++ b/src/test/java/com/google/devtools/build/lib/skylarkinterface/processor/testsources/StructFieldWithExtraArgs.java
@@ -17,18 +17,17 @@
 import com.google.devtools.build.lib.skylarkinterface.Param;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
-import com.google.devtools.build.lib.syntax.SkylarkList;
+import com.google.devtools.build.lib.syntax.Sequence;
 
 /** Test case which verifies a struct field method cannot specify extraArgs. */
 public class StructFieldWithExtraArgs implements SkylarkValue {
 
   @SkylarkCallable(
-    name = "struct_field_method_with_extra_args",
-    documented = false,
-    structField = true,
-    extraPositionals = @Param(name = "args")
-  )
-  public String structFieldMethodWithExtraArgs(SkylarkList<?> args) {
+      name = "struct_field_method_with_extra_args",
+      documented = false,
+      structField = true,
+      extraPositionals = @Param(name = "args"))
+  public String structFieldMethodWithExtraArgs(Sequence<?> args) {
     return "Cat.";
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/skylarkinterface/processor/testsources/ToggledKwargsParam.java b/src/test/java/com/google/devtools/build/lib/skylarkinterface/processor/testsources/ToggledKwargsParam.java
index d0eded9..0ba4095 100644
--- a/src/test/java/com/google/devtools/build/lib/skylarkinterface/processor/testsources/ToggledKwargsParam.java
+++ b/src/test/java/com/google/devtools/build/lib/skylarkinterface/processor/testsources/ToggledKwargsParam.java
@@ -17,8 +17,8 @@
 import com.google.devtools.build.lib.skylarkinterface.Param;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
+import com.google.devtools.build.lib.syntax.Sequence;
 import com.google.devtools.build.lib.syntax.SkylarkDict;
-import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.StarlarkSemantics.FlagIdentifier;
 import com.google.devtools.build.lib.syntax.StarlarkThread;
 
@@ -42,11 +42,7 @@
               enableOnlyWithFlag = FlagIdentifier.EXPERIMENTAL_BUILD_SETTING_API),
       useStarlarkThread = true)
   public String toggledKwargsMethod(
-      String one,
-      Integer two,
-      SkylarkList<?> args,
-      SkylarkDict<?, ?> kwargs,
-      StarlarkThread thread) {
+      String one, Integer two, Sequence<?> args, SkylarkDict<?, ?> kwargs, StarlarkThread thread) {
     return "cat";
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/BaseFunctionTest.java b/src/test/java/com/google/devtools/build/lib/syntax/BaseFunctionTest.java
index 79eeaa7..4b5edb5 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/BaseFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/BaseFunctionTest.java
@@ -33,8 +33,8 @@
 public class BaseFunctionTest extends EvaluationTestCase {
 
   /**
-   * Handy implementation of {@link BaseFunction} that returns all its args as a list.
-   * (We'd use SkylarkList.tuple, but it can't handle null.)
+   * Handy implementation of {@link BaseFunction} that returns all its args as a list. (We'd use
+   * Sequence.tuple, but it can't handle null.)
    */
   private static class TestingBaseFunction extends BaseFunction {
     TestingBaseFunction(FunctionSignature signature) {
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
index de86116..ff07322 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
@@ -227,55 +227,49 @@
     }
 
     @SkylarkCallable(
-      name = "with_params",
-      documented = false,
-      parameters = {
-        @Param(name = "pos1"),
-        @Param(name = "pos2", defaultValue = "False", type = Boolean.class),
-        @Param(
-          name = "posOrNamed",
-          defaultValue = "False",
-          type = Boolean.class,
-          positional = true,
-          named = true
-        ),
-        @Param(name = "named", type = Boolean.class, positional = false, named = true),
-        @Param(
-          name = "optionalNamed",
-          type = Boolean.class,
-          defaultValue = "False",
-          positional = false,
-          named = true
-        ),
-        @Param(
-          name = "nonNoneable",
-          type = Object.class,
-          defaultValue = "\"a\"",
-          positional = false,
-          named = true
-        ),
-        @Param(
-          name = "noneable",
-          type = Integer.class,
-          defaultValue = "None",
-          noneable = true,
-          positional = false,
-          named = true
-        ),
-        @Param(
-          name = "multi",
-          allowedTypes = {
-            @ParamType(type = String.class),
-            @ParamType(type = Integer.class),
-            @ParamType(type = SkylarkList.class, generic1 = Integer.class),
-          },
-          defaultValue = "None",
-          noneable = true,
-          positional = false,
-          named = true
-        )
-      }
-    )
+        name = "with_params",
+        documented = false,
+        parameters = {
+          @Param(name = "pos1"),
+          @Param(name = "pos2", defaultValue = "False", type = Boolean.class),
+          @Param(
+              name = "posOrNamed",
+              defaultValue = "False",
+              type = Boolean.class,
+              positional = true,
+              named = true),
+          @Param(name = "named", type = Boolean.class, positional = false, named = true),
+          @Param(
+              name = "optionalNamed",
+              type = Boolean.class,
+              defaultValue = "False",
+              positional = false,
+              named = true),
+          @Param(
+              name = "nonNoneable",
+              type = Object.class,
+              defaultValue = "\"a\"",
+              positional = false,
+              named = true),
+          @Param(
+              name = "noneable",
+              type = Integer.class,
+              defaultValue = "None",
+              noneable = true,
+              positional = false,
+              named = true),
+          @Param(
+              name = "multi",
+              allowedTypes = {
+                @ParamType(type = String.class),
+                @ParamType(type = Integer.class),
+                @ParamType(type = Sequence.class, generic1 = Integer.class),
+              },
+              defaultValue = "None",
+              noneable = true,
+              positional = false,
+              named = true)
+        })
     public String withParams(
         Integer pos1,
         boolean pos2,
@@ -359,7 +353,7 @@
               allowedTypes = {
                 @ParamType(type = String.class),
                 @ParamType(type = Integer.class),
-                @ParamType(type = SkylarkList.class, generic1 = Integer.class),
+                @ParamType(type = Sequence.class, generic1 = Integer.class),
               },
               defaultValue = "None",
               noneable = true,
@@ -428,7 +422,7 @@
         extraPositionals = @Param(name = "args"),
         useStarlarkThread = true)
     public String withArgsAndThread(
-        Integer pos1, boolean pos2, boolean named, SkylarkList<?> args, StarlarkThread thread) {
+        Integer pos1, boolean pos2, boolean named, Sequence<?> args, StarlarkThread thread) {
       String argsString =
           "args(" + args.stream().map(Printer::debugPrint).collect(joining(", ")) + ")";
       return "with_args_and_thread("
@@ -468,15 +462,14 @@
     }
 
     @SkylarkCallable(
-      name = "with_args_and_kwargs",
-      documented = false,
-      parameters = {
-        @Param(name = "foo", named = true, positional = true, type = String.class),
-      },
-      extraPositionals = @Param(name = "args"),
-      extraKeywords = @Param(name = "kwargs")
-    )
-    public String withArgsAndKwargs(String foo, SkylarkList<?> args, SkylarkDict<?, ?> kwargs)
+        name = "with_args_and_kwargs",
+        documented = false,
+        parameters = {
+          @Param(name = "foo", named = true, positional = true, type = String.class),
+        },
+        extraPositionals = @Param(name = "args"),
+        extraKeywords = @Param(name = "kwargs"))
+    public String withArgsAndKwargs(String foo, Sequence<?> args, SkylarkDict<?, ?> kwargs)
         throws EvalException {
       String argsString =
           "args(" + args.stream().map(Printer::debugPrint).collect(joining(", ")) + ")";
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkListTest.java b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkListTest.java
index d31a7e0..f7eeb0b 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkListTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkListTest.java
@@ -24,9 +24,7 @@
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
 
-/**
- * Tests for SkylarkList.
- */
+/** Tests for Sequence. */
 @RunWith(JUnit4.class)
 public class SkylarkListTest extends EvaluationTestCase {
 
@@ -64,8 +62,8 @@
   }
 
   @SuppressWarnings("unchecked")
-  private SkylarkList<Object> listEval(String... input) throws Exception {
-    return (SkylarkList<Object>) eval(input);
+  private Sequence<Object> listEval(String... input) throws Exception {
+    return (Sequence<Object>) eval(input);
   }
 
   @Test
@@ -156,8 +154,7 @@
 
   @Test
   public void testListConcat() throws Exception {
-    assertThat(eval("[1, 2] + [3, 4]"))
-        .isEqualTo(SkylarkList.createImmutable(Tuple.of(1, 2, 3, 4)));
+    assertThat(eval("[1, 2] + [3, 4]")).isEqualTo(Sequence.createImmutable(Tuple.of(1, 2, 3, 4)));
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/StarlarkFileTest.java b/src/test/java/com/google/devtools/build/lib/syntax/StarlarkFileTest.java
index feb49ae..0d1fafe 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/StarlarkFileTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/StarlarkFileTest.java
@@ -58,7 +58,7 @@
     // input1.BUILD contains:
     // x = [1,2,'foo',4] + [1,2, "%s%d" % ('foo', 1)]
     assertThat(thread.moduleLookup("x"))
-        .isEqualTo(SkylarkList.createImmutable(Tuple.of(1, 2, "foo", 4, 1, 2, "foo1")));
+        .isEqualTo(Sequence.createImmutable(Tuple.of(1, 2, "foo", 4, 1, 2, "foo1")));
   }
 
   @Test