diff --git a/src/main/java/com/google/devtools/build/docgen/skylark/SkylarkDoc.java b/src/main/java/com/google/devtools/build/docgen/skylark/SkylarkDoc.java
index da77f73..a672165 100644
--- a/src/main/java/com/google/devtools/build/docgen/skylark/SkylarkDoc.java
+++ b/src/main/java/com/google/devtools/build/docgen/skylark/SkylarkDoc.java
@@ -17,6 +17,7 @@
 import com.google.devtools.build.lib.syntax.FuncallExpression;
 import com.google.devtools.build.lib.syntax.Runtime.NoneType;
 import com.google.devtools.build.lib.syntax.SkylarkList;
+import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
 import com.google.devtools.build.lib.syntax.SkylarkModule;
 import com.google.devtools.build.lib.syntax.SkylarkSignature;
 import com.google.devtools.build.lib.syntax.SkylarkSignature.Param;
@@ -54,6 +55,8 @@
       return "<a class=\"anchor\" href=\"string.html\">string</a>";
     } else if (Map.class.isAssignableFrom(type)) {
       return "<a class=\"anchor\" href=\"dict.html\">dict</a>";
+    } else if (Tuple.class.isAssignableFrom(type)) {
+      return "<a class=\"anchor\" href=\"list.html\">tuple</a>";
     } else if (List.class.isAssignableFrom(type) || SkylarkList.class.isAssignableFrom(type)
         || type == HackHackEitherList.class) {
       // Annotated Java methods can return simple java.util.Lists (which get auto-converted).
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTargetBuilder.java b/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTargetBuilder.java
index b89cf72..7903587 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTargetBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTargetBuilder.java
@@ -381,8 +381,7 @@
       return;
     } else if (object instanceof SkylarkList) {
       SkylarkList list = (SkylarkList) object;
-      if (list == SkylarkList.EMPTY_LIST
-          || isSimpleSkylarkObjectSafe(list.getContentType().getType())) {
+      if (list.isEmpty()) {
         // Try not to iterate over the list if avoidable.
         return;
       }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/Type.java b/src/main/java/com/google/devtools/build/lib/packages/Type.java
index 2c7c706..0f95601 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/Type.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/Type.java
@@ -993,7 +993,7 @@
     public List<Object> convert(Object x, String what, Object context)
         throws ConversionException {
       if (x instanceof SkylarkList) {
-        return ((SkylarkList) x).toList();
+        return ((SkylarkList) x).getList();
       } else if (x instanceof List) {
         return (List<Object>) x;
       } else if (x instanceof Iterable) {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/SkylarkCommandLine.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkCommandLine.java
index a262486..1a5319c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkCommandLine.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkCommandLine.java
@@ -19,7 +19,8 @@
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.syntax.BuiltinFunction;
-import com.google.devtools.build.lib.syntax.SkylarkList;
+import com.google.devtools.build.lib.syntax.Environment;
+import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
 import com.google.devtools.build.lib.syntax.SkylarkModule;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.syntax.SkylarkSignature;
@@ -53,17 +54,19 @@
   @SkylarkSignature(name = "template",
       doc = "Transforms a set of files to a list of strings using the template string.",
       objectType = SkylarkCommandLine.class,
-      returnType = SkylarkList.class,
+      returnType = MutableList.class,
       mandatoryPositionals = {
       @Param(name = "items", type = SkylarkNestedSet.class, generic1 = Artifact.class,
           doc = "The set of structs to transform."),
       @Param(name = "template", type = String.class,
           doc = "The template to use for the transformation, <code>%{path}</code> and "
               + "<code>%{short_path}</code> being substituted with the corresponding fields of each"
-              + " file.")})
+              + " file.")},
+      useEnvironment = true)
   private static BuiltinFunction template = new BuiltinFunction("template") {
-    public SkylarkList invoke(final SkylarkNestedSet items, final String template) {
-      return SkylarkList.lazyList(Iterables.transform(items, new Function<Object, String>() {
+    public MutableList invoke(final SkylarkNestedSet items, final String template,
+        Environment env) {
+      return new MutableList(Iterables.transform(items, new Function<Object, String>() {
         @Override
         public String apply(Object input) {
           Artifact artifact = (Artifact) input;
@@ -71,7 +74,7 @@
               .replace("%{path}", artifact.getExecPathString())
               .replace("%{short_path}", artifact.getRootRelativePathString());
         }
-      }), String.class);
+      }), env);
     }
   };
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleContext.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleContext.java
index 5c13375..bc2bbe4 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleContext.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleContext.java
@@ -31,7 +31,6 @@
 import com.google.devtools.build.lib.analysis.MakeVariableExpander.ExpansionException;
 import com.google.devtools.build.lib.analysis.RuleConfiguredTarget.Mode;
 import com.google.devtools.build.lib.analysis.RuleContext;
-import com.google.devtools.build.lib.analysis.TransitiveInfoCollection;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.config.FragmentCollection;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
@@ -50,7 +49,7 @@
 import com.google.devtools.build.lib.syntax.Label;
 import com.google.devtools.build.lib.syntax.Runtime;
 import com.google.devtools.build.lib.syntax.SkylarkCallable;
-import com.google.devtools.build.lib.syntax.SkylarkList;
+import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
 import com.google.devtools.build.lib.syntax.SkylarkModule;
 import com.google.devtools.build.lib.syntax.SkylarkType;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -167,8 +166,7 @@
           addOutput(outputsBuilder, attrName, Runtime.NONE);
         }
       } else if (type == Type.OUTPUT_LIST) {
-        addOutput(outputsBuilder, attrName,
-            SkylarkList.list(artifacts, Artifact.class));
+        addOutput(outputsBuilder, attrName, new MutableList(artifacts));
       } else {
         throw new IllegalArgumentException(
             "Type of " + attrName + "(" + type + ") is not output type ");
@@ -227,7 +225,7 @@
         attrBuilder.put(skyname, prereq);
       } else {
         // Type.LABEL_LIST
-        attrBuilder.put(skyname, SkylarkList.list(allPrereq, TransitiveInfoCollection.class));
+        attrBuilder.put(skyname, new MutableList(allPrereq));
       }
     }
     attrObject =
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java b/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java
index f8ebe6b..43c25aa 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/BaseFunction.java
@@ -22,6 +22,7 @@
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.packages.Type.ConversionException;
+import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
 
 import java.util.ArrayList;
 import java.util.HashMap;
@@ -231,11 +232,11 @@
       // and this is actually the same as in Python.
       int starParamIndex = numNamedParams;
       if (numPositionalArgs > numPositionalParams) {
-        arguments[starParamIndex] = SkylarkList.tuple(
-            args.subList(numPositionalParams, numPositionalArgs));
+        arguments[starParamIndex] =
+            Tuple.copyOf(args.subList(numPositionalParams, numPositionalArgs));
         numPositionalArgs = numPositionalParams; // clip numPositionalArgs
       } else {
-        arguments[starParamIndex] = SkylarkList.EMPTY_TUPLE;
+        arguments[starParamIndex] = Tuple.EMPTY;
       }
     } else if (numPositionalArgs > numPositionalParams) {
       throw new EvalException(loc,
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java b/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java
index 7ba3d24..cf98c53 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java
@@ -15,8 +15,11 @@
 
 import com.google.common.base.Strings;
 import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
 import com.google.devtools.build.lib.syntax.ClassObject.SkylarkClassObject;
+import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
+import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
 
 import java.util.Collection;
 import java.util.Collections;
@@ -122,7 +125,7 @@
 
     switch (operator) {
       case PLUS:
-        return plus(lval, rval);
+        return plus(lval, rval, env);
 
       case PIPE:
         if (lval instanceof SkylarkNestedSet) {
@@ -197,11 +200,8 @@
               }
               /* string % list: fall thru */
             }
-            if (rval instanceof SkylarkList) {
-              SkylarkList rlist = (SkylarkList) rval;
-              if (rlist.isTuple()) {
-                return Printer.formatToString(pattern, rlist.toList());
-              }
+            if (rval instanceof Tuple) {
+              return Printer.formatToString(pattern, ((Tuple) rval).getList());
             }
 
             return Printer.formatToString(pattern, Collections.singletonList(rval));
@@ -247,7 +247,7 @@
             operator, EvalUtils.getDataTypeName(lval), EvalUtils.getDataTypeName(rval)));
   }
 
-  private Object plus(Object lval, Object rval) throws EvalException {
+  private Object plus(Object lval, Object rval, Environment env) throws EvalException {
     // int + int
     if (lval instanceof Integer && rval instanceof Integer) {
       return ((Integer) lval).intValue() + ((Integer) rval).intValue();
@@ -264,8 +264,8 @@
       List<?> rlist = (List<?>) rval;
       if (EvalUtils.isTuple(llist) != EvalUtils.isTuple(rlist)) {
         throw new EvalException(getLocation(), "can only concatenate "
-            + EvalUtils.getDataTypeName(rlist) + " (not \"" + EvalUtils.getDataTypeName(llist)
-            + "\") to " + EvalUtils.getDataTypeName(rlist));
+            + EvalUtils.getDataTypeName(llist) + " (not \"" + EvalUtils.getDataTypeName(rlist)
+            + "\") to " + EvalUtils.getDataTypeName(llist));
       }
       if (llist instanceof GlobList<?> || rlist instanceof GlobList<?>) {
         return GlobList.concat(llist, rlist);
@@ -283,10 +283,21 @@
     }
 
     if ((lval instanceof SkylarkList || lval instanceof List<?>)
-        && (rval instanceof SkylarkList || rval instanceof List<?>)) {
-      SkylarkList left = (SkylarkList) SkylarkType.convertToSkylark(lval, getLocation());
-      SkylarkList right = (SkylarkList) SkylarkType.convertToSkylark(rval, getLocation());
-      return SkylarkList.concat(left, right, getLocation());
+        && ((rval instanceof SkylarkList || rval instanceof List<?>))) {
+      SkylarkList left = (SkylarkList) SkylarkType.convertToSkylark(lval, env);
+      SkylarkList right = (SkylarkList) SkylarkType.convertToSkylark(rval, env);
+      boolean isImmutable = left.isTuple();
+      if (isImmutable != right.isTuple()) {
+        throw new EvalException(getLocation(), "can only concatenate "
+            + EvalUtils.getDataTypeName(left) + " (not \"" + EvalUtils.getDataTypeName(right)
+            + "\") to " + EvalUtils.getDataTypeName(left));
+      }
+      Iterable<Object> concatenated = Iterables.concat(left, right);
+      if (isImmutable) {
+        return Tuple.copyOf(concatenated);
+      } else {
+        return new MutableList(concatenated, env);
+      }
     }
 
     if (lval instanceof Map<?, ?> && rval instanceof Map<?, ?>) {
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/DotExpression.java b/src/main/java/com/google/devtools/build/lib/syntax/DotExpression.java
index f930cb3..3c7333b 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/DotExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/DotExpression.java
@@ -51,7 +51,7 @@
   Object doEval(Environment env) throws EvalException, InterruptedException {
     Object objValue = obj.eval(env);
     String name = field.getName();
-    Object result = eval(objValue, name, getLocation());
+    Object result = eval(objValue, name, getLocation(), env);
     if (result == null) {
       if (objValue instanceof ClassObject) {
         String customErrorMessage = ((ClassObject) objValue).errorMessage(name);
@@ -68,7 +68,8 @@
   /**
    * Returns the field of the given name of the struct objValue, or null if no such field exists.
    */
-  public static Object eval(Object objValue, String name, Location loc) throws EvalException {
+  public static Object eval(Object objValue, String name,
+      Location loc, Environment env) throws EvalException {
     if (objValue instanceof ClassObject) {
       Object result = null;
       try {
@@ -79,7 +80,7 @@
       // ClassObjects may have fields that are annotated with @SkylarkCallable.
       // Since getValue() does not know about those, we cannot expect that result is a valid object.
       if (result != null) {
-        result = SkylarkType.convertToSkylark(result, loc);
+        result = SkylarkType.convertToSkylark(result, env);
         // If we access NestedSets using ClassObject.getValue() we won't know the generic type,
         // so we have to disable it. This should not happen.
         SkylarkType.checkTypeAllowedInSkylark(result, loc);
@@ -92,7 +93,7 @@
     if (methods != null && !methods.isEmpty()) {
       MethodDescriptor method = Iterables.getOnlyElement(methods);
       if (method.getAnnotation().structField()) {
-        return FuncallExpression.callMethod(method, name, objValue, new Object[] {}, loc);
+        return FuncallExpression.callMethod(method, name, objValue, new Object[] {}, loc, env);
       }
     }
     return null;
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java b/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
index dd59ec9..eb26e38 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
@@ -68,15 +68,11 @@
     @Override
     @SuppressWarnings("unchecked")
     public int compare(Object o1, Object o2) {
-      Location loc = null;
-      try {
-        o1 = SkylarkType.convertToSkylark(o1, loc);
-        o2 = SkylarkType.convertToSkylark(o2, loc);
-      } catch (EvalException e) {
-        throw new ComparisonException(e.getMessage());
-      }
+      o1 = SkylarkType.convertToSkylark(o1, /*env=*/ null);
+      o2 = SkylarkType.convertToSkylark(o2, /*env=*/ null);
 
-      if (o1 instanceof SkylarkList && o2 instanceof SkylarkList) {
+      if (o1 instanceof SkylarkList && o2 instanceof SkylarkList
+          && ((SkylarkList) o1).isTuple() == ((SkylarkList) o2).isTuple()) {
         return compareLists((SkylarkList) o1, (SkylarkList) o2);
       }
       try {
@@ -225,8 +221,6 @@
       return ImmutableList.class;
     } else if (List.class.isAssignableFrom(c)) {
       return List.class;
-    } else if (SkylarkList.class.isAssignableFrom(c)) {
-      return SkylarkList.class;
     } else if (Map.class.isAssignableFrom(c)) {
       return Map.class;
     } else if (NestedSet.class.isAssignableFrom(c)) {
@@ -266,7 +260,7 @@
       if (list.isTuple()) {
         return "tuple";
       } else {
-        return "list" + (full ? " of " + list.getContentType() + "s" : "");
+        return "list";
       }
     } else if (object instanceof SkylarkNestedSet) {
       SkylarkNestedSet set = (SkylarkNestedSet) object;
@@ -289,7 +283,11 @@
    * when the given class identifies a Skylark name space.
    */
   public static String getDataTypeNameFromClass(Class<?> c, boolean highlightNameSpaces) {
-    if (c.equals(Object.class)) {
+    if (c.isAnnotationPresent(SkylarkModule.class)) {
+      SkylarkModule module = c.getAnnotation(SkylarkModule.class);
+      return c.getAnnotation(SkylarkModule.class).name()
+          + ((module.namespace() && highlightNameSpaces) ? " (a language module)" : "");
+    } else if (c.equals(Object.class)) {
       return "unknown";
     } else if (c.equals(String.class)) {
       return "string";
@@ -297,13 +295,10 @@
       return "int";
     } else if (c.equals(Boolean.class)) {
       return "bool";
-    } else if (c.equals(Void.TYPE) || c.equals(Runtime.NoneType.class)) {
-      // TODO(bazel-team): no one should be seeing Void at all.
-      return "NoneType";
     } else if (List.class.isAssignableFrom(c)) {
-      // NB: the capital here is a subtle way to distinguish java Tuple and java List
-      // from native SkylarkList tuple and list.
-      // TODO(bazel-team): refactor SkylarkList and use it everywhere.
+      // NB: the capital here is a subtle way to distinguish java List and Tuple (ImmutableList)
+      // from native SkylarkList list and tuple.
+      // TODO(bazel-team): use SkylarkList everywhere instead of java List.
       return isTuple(c) ? "Tuple" : "List";
     } else if (Map.class.isAssignableFrom(c)) {
       return "dict";
@@ -316,13 +311,6 @@
       return "set";
     } else if (ClassObject.SkylarkClassObject.class.isAssignableFrom(c)) {
       return "struct";
-    } else if (SkylarkList.class.isAssignableFrom(c)) {
-      // TODO(bazel-team): Refactor the class hierarchy so we can distinguish list and tuple types.
-      return "list";
-    } else if (c.isAnnotationPresent(SkylarkModule.class)) {
-      SkylarkModule module = c.getAnnotation(SkylarkModule.class);
-      return c.getAnnotation(SkylarkModule.class).name()
-          + ((module.namespace() && highlightNameSpaces) ? " (a language module)" : "");
     } else {
       if (c.getSimpleName().isEmpty()) {
         return c.getName();
@@ -381,7 +369,7 @@
     if (o instanceof Collection) {
       return (Collection<Object>) o;
     } else if (o instanceof SkylarkList) {
-      return ((SkylarkList) o).toList();
+      return ((SkylarkList) o).getList();
     } else if (o instanceof Map<?, ?>) {
       Map<Comparable<?>, Object> dict = (Map<Comparable<?>, Object>) o;
       // For dictionaries we iterate through the keys only
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java b/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
index cf16b68..4f26277 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
@@ -318,7 +318,7 @@
   }
 
   static Object callMethod(MethodDescriptor methodDescriptor, String methodName, Object obj,
-      Object[] args, Location loc) throws EvalException {
+      Object[] args, Location loc, Environment env) throws EvalException {
     try {
       Method method = methodDescriptor.getMethod();
       if (obj == null && !Modifier.isStatic(method.getModifiers())) {
@@ -340,7 +340,7 @@
               + Printer.listString(ImmutableList.copyOf(args), "(", ", ", ")", null));
         }
       }
-      result = SkylarkType.convertToSkylark(result, method);
+      result = SkylarkType.convertToSkylark(result, method, env);
       if (result != null && !EvalUtils.isSkylarkAcceptable(result.getClass())) {
         throw new EvalException(loc, Printer.format(
             "Method '%s' returns an object of invalid type %r", methodName, result.getClass()));
@@ -464,7 +464,7 @@
         value = SkylarkType.convertFromSkylark(value);
       } else if (conversion == ArgConversion.TO_SKYLARK) {
         // We try to auto convert the type if we can.
-        value = SkylarkType.convertToSkylark(value, getLocation());
+        value = SkylarkType.convertToSkylark(value, env);
         // We call into Skylark so we need to be sure that the caller uses the appropriate types.
         SkylarkType.checkTypeAllowedInSkylark(value, getLocation());
       } // else NO_CONVERSION
@@ -565,7 +565,7 @@
                 + "\nwhile calling method '%s' for type %s",
                 name, EvalUtils.getDataTypeNameFromClass(objClass)));
       }
-      return callMethod(method, name, obj, args.toArray(), getLocation());
+      return callMethod(method, name, obj, args.toArray(), getLocation(), env);
     } else {
       throw new EvalException(
           getLocation(),
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/ListComprehension.java b/src/main/java/com/google/devtools/build/lib/syntax/ListComprehension.java
index 144d002..6460bbc 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/ListComprehension.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/ListComprehension.java
@@ -15,6 +15,7 @@
 package com.google.devtools.build.lib.syntax;
 
 import com.google.devtools.build.lib.events.Location;
+import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
 
 import java.io.Serializable;
 import java.util.ArrayList;
@@ -219,7 +220,7 @@
   Object doEval(Environment env) throws EvalException, InterruptedException {
     List<Object> result = new ArrayList<>();
     evalStep(env, result, 0);
-    return env.isSkylark() ? SkylarkList.list(result, getLocation()) : result;
+    return env.isSkylark() ? new MutableList(result, env) : result;
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/ListLiteral.java b/src/main/java/com/google/devtools/build/lib/syntax/ListLiteral.java
index 5e33204..36f4829 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/ListLiteral.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/ListLiteral.java
@@ -13,6 +13,9 @@
 // limitations under the License.
 package com.google.devtools.build.lib.syntax;
 
+import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
+import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
+
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.List;
@@ -108,8 +111,7 @@
       result.add(expr.eval(env));
     }
     if (env.isSkylark()) {
-      return isTuple()
-          ? SkylarkList.tuple(result) : SkylarkList.list(result, getLocation());
+      return isTuple() ? Tuple.copyOf(result) : new MutableList(result, env);
     } else {
       return EvalUtils.makeSequence(result, isTuple());
     }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java b/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
index 18ed1c7..a6ef07d 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
@@ -25,6 +25,8 @@
 import com.google.devtools.build.lib.packages.Type;
 import com.google.devtools.build.lib.packages.Type.ConversionException;
 import com.google.devtools.build.lib.syntax.ClassObject.SkylarkClassObject;
+import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
+import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
 import com.google.devtools.build.lib.syntax.SkylarkSignature.Param;
 import com.google.devtools.build.lib.syntax.SkylarkSignatureProcessor.HackHackEitherList;
 
@@ -190,7 +192,7 @@
           maxSplitO, "'split' argument of 'split'", /*label*/null, -2);
       // + 1 because the last result is the remainder, and default of -2 so that after +1 it's -1
       String[] ss = Pattern.compile(sep, Pattern.LITERAL).split(self, maxSplit + 1);
-      return convert(Arrays.<String>asList(ss), env, loc);
+      return convert(Arrays.<String>asList(ss), env);
     }
   };
 
@@ -221,7 +223,7 @@
         throw new EvalException(loc, ex);
       }
 
-      return convert(result, env, loc);
+      return convert(result, env);
     }
   };
 
@@ -327,7 +329,7 @@
   private static Object partitionWrapper(String self, String separator, boolean forward,
       Environment env, Location loc) throws EvalException {
     try {
-      return convert(stringPartition(self, separator, forward), env, loc);
+      return convert(stringPartition(self, separator, forward), env);
     } catch (IllegalArgumentException ex) {
       throw new EvalException(loc, ex);
     }
@@ -604,8 +606,7 @@
             doc = "Test beginning at this position."),
         @Param(name = "end", type = Integer.class, noneable = true, defaultValue = "None",
             doc = "optional position at which to stop comparing.")})
-  private static BuiltinFunction endswith = new BuiltinFunction(
-      "endswith", SkylarkList.tuple(0, Runtime.NONE)) {
+  private static BuiltinFunction endswith = new BuiltinFunction("endswith") {
     public Boolean invoke(String self, String sub, Integer start, Object end)
         throws ConversionException {
       return pythonSubstring(self, start, end, "'end' operand of 'endswith'").endsWith(sub);
@@ -708,20 +709,35 @@
     }
   };
 
-  @SkylarkSignature(name = "$slice", objectType = SkylarkList.class,
+  @SkylarkSignature(name = "$slice", objectType = MutableList.class, returnType = MutableList.class,
       documented = false,
       mandatoryPositionals = {
-        @Param(name = "self", type = SkylarkList.class, doc = "This list or tuple."),
+        @Param(name = "self", type = MutableList.class, doc = "This list."),
         @Param(name = "start", type = Integer.class, doc = "start position of the slice."),
         @Param(name = "end", type = Integer.class, doc = "end position of the slice.")},
       doc = "x[<code>start</code>:<code>end</code>] returns a slice or a list slice.",
-      useLocation = true)
-  private static BuiltinFunction skylarkListSlice = new BuiltinFunction("$slice") {
-    public Object invoke(SkylarkList self, Integer left, Integer right,
-        Location loc) throws EvalException, ConversionException {
-      return SkylarkList.list(sliceList(self.toList(), left, right), loc);
-    }
-  };
+      useEnvironment = true)
+  private static BuiltinFunction mutableListSlice = new BuiltinFunction("$slice") {
+      public MutableList invoke(MutableList self, Integer left, Integer right,
+          Environment env) throws EvalException, ConversionException {
+        return new MutableList(sliceList(self.getList(), left, right), env);
+      }
+    };
+
+  @SkylarkSignature(name = "$slice", objectType = Tuple.class, returnType = Tuple.class,
+      documented = false,
+      mandatoryPositionals = {
+        @Param(name = "self", type = Tuple.class, doc = "This tuple."),
+        @Param(name = "start", type = Integer.class, doc = "start position of the slice."),
+        @Param(name = "end", type = Integer.class, doc = "end position of the slice.")},
+      doc = "x[<code>start</code>:<code>end</code>] returns a slice or a list slice.",
+      useEnvironment = true)
+  private static BuiltinFunction tupleSlice = new BuiltinFunction("$slice") {
+      public Tuple invoke(Tuple self, Integer left, Integer right,
+          Environment env) throws EvalException, ConversionException {
+        return Tuple.copyOf(sliceList(self.getList(), left, right));
+      }
+    };
 
   private static List<Object> sliceList(List<Object> list, Integer left, Integer right) {
     left = clampIndex(left, list.size());
@@ -751,7 +767,7 @@
             Collection<?> col =
                 Ordering.from(EvalUtils.SKYLARK_COMPARATOR)
                     .sortedCopy(EvalUtils.toCollection(self, loc));
-            return convert(col, env, loc);
+            return convert(col, env);
           } catch (EvalUtils.ComparisonException e) {
             throw new EvalException(loc, e);
           }
@@ -776,10 +792,6 @@
       new BuiltinFunction("append") {
         public Runtime.NoneType invoke(List<Object> self, Object item,
             Location loc, Environment env) throws EvalException, ConversionException {
-          if (env.isCallerSkylark()) {
-            throw new EvalException(loc,
-                "function 'append' is not available in Skylark");
-          }
           if (EvalUtils.isTuple(self)) {
             throw new EvalException(loc,
                 "function 'append' is not defined on object of type 'Tuple'");
@@ -789,6 +801,27 @@
         }
       };
 
+  @SkylarkSignature(
+    name = "append",
+    objectType = MutableList.class,
+    returnType = Runtime.NoneType.class,
+    documented = false,
+    doc = "Adds an item to the end of the list.",
+    mandatoryPositionals = {
+      @Param(name = "self", type = MutableList.class, doc = "This list."),
+      @Param(name = "item", type = Object.class, doc = "Item to add at the end.")
+    },
+    useLocation = true,
+    useEnvironment = true)
+  private static BuiltinFunction skylarkAppend =
+      new BuiltinFunction("append") {
+        public Runtime.NoneType invoke(MutableList self, Object item,
+            Location loc, Environment env) throws EvalException, ConversionException {
+          self.add(item, loc, env);
+          return Runtime.NONE;
+        }
+      };
+
   // This function has a SkylarkSignature but is only used by the Build language, not Skylark.
   @SkylarkSignature(
     name = "extend",
@@ -802,14 +835,10 @@
       @Param(name = "items", type = List.class, doc = "Items to add at the end.")},
     useLocation = true,
     useEnvironment = true)
-  private static BuiltinFunction extend =
+  private static BuiltinFunction skylarkExtend =
       new BuiltinFunction("extend") {
         public Runtime.NoneType invoke(List<Object> self, List<Object> items,
             Location loc, Environment env) throws EvalException, ConversionException {
-          if (env.isCallerSkylark()) {
-            throw new EvalException(loc,
-                "function 'append' is not available in Skylark");
-          }
           if (EvalUtils.isTuple(self)) {
             throw new EvalException(loc,
                 "function 'extend' is not defined on object of type 'Tuple'");
@@ -819,6 +848,26 @@
         }
       };
 
+  @SkylarkSignature(
+    name = "extend",
+    objectType = MutableList.class,
+    returnType = Runtime.NoneType.class,
+    documented = false,
+    doc = "Adds all items to the end of the list.",
+    mandatoryPositionals = {
+      @Param(name = "self", type = MutableList.class, doc = "This list."),
+      @Param(name = "items", type = SkylarkList.class, doc = "Items to add at the end.")},
+    useLocation = true,
+    useEnvironment = true)
+  private static BuiltinFunction extend =
+      new BuiltinFunction("extend") {
+        public Runtime.NoneType invoke(MutableList self, SkylarkList items,
+            Location loc, Environment env) throws EvalException, ConversionException {
+          self.addAll(items, loc, env);
+          return Runtime.NONE;
+        }
+      };
+
   // dictionary access operator
   @SkylarkSignature(name = "$index", documented = false, objectType = Map.class,
       doc = "Looks up a value in a dictionary.",
@@ -837,23 +886,40 @@
   };
 
   // list access operator
-  @SkylarkSignature(name = "$index", documented = false, objectType = SkylarkList.class,
+  @SkylarkSignature(name = "$index", documented = false, objectType = MutableList.class,
       doc = "Returns the nth element of a list.",
       mandatoryPositionals = {
-        @Param(name = "self", type = SkylarkList.class, doc = "This object."),
+        @Param(name = "self", type = MutableList.class, doc = "This list."),
         @Param(name = "key", type = Object.class, doc = "The index or key to access.")},
       useLocation = true)
-  private static BuiltinFunction skylarkListIndexOperator = new BuiltinFunction("$index") {
-    public Object invoke(SkylarkList self, Object key,
-        Location loc) throws EvalException, ConversionException {
-      if (self.isEmpty()) {
-        throw new EvalException(loc, "List is empty");
+  private static BuiltinFunction mutableListIndexOperator = new BuiltinFunction("$index") {
+      public Object invoke(MutableList self, Object key,
+          Location loc) throws EvalException, ConversionException {
+        if (self.isEmpty()) {
+          throw new EvalException(loc, "List is empty");
+        }
+        int index = getListIndex(key, self.size(), loc);
+        return self.getList().get(index);
       }
-      int index = getListIndex(key, self.size(), loc);
-      return self.get(index);
-    }
-  };
+    };
 
+  // tuple access operator
+  @SkylarkSignature(name = "$index", documented = false, objectType = Tuple.class,
+      doc = "Returns the nth element of a list.",
+      mandatoryPositionals = {
+        @Param(name = "self", type = Tuple.class, doc = "This tuple."),
+        @Param(name = "key", type = Object.class, doc = "The index or key to access.")},
+      useLocation = true)
+  private static BuiltinFunction tupleIndexOperator = new BuiltinFunction("$index") {
+      public Object invoke(Tuple self, Object key,
+          Location loc) throws EvalException, ConversionException {
+        if (self.isEmpty()) {
+          throw new EvalException(loc, "Tuple is empty");
+        }
+        int index = getListIndex(key, self.size(), loc);
+        return self.getList().get(index);
+      }
+    };
 
   // list access operator
   @SkylarkSignature(name = "$index", documented = false, objectType = List.class,
@@ -899,7 +965,7 @@
         Location loc, Environment env) throws EvalException, ConversionException {
       // Use a TreeMap to ensure consistent ordering.
       Map<?, ?> dict = new TreeMap<>(self);
-      return convert(dict.values(), env, loc);
+      return convert(dict.values(), env);
     }
   };
 
@@ -920,9 +986,9 @@
       List<Object> list = Lists.newArrayListWithCapacity(dict.size());
       for (Map.Entry<?, ?> entries : dict.entrySet()) {
         List<?> item = ImmutableList.of(entries.getKey(), entries.getValue());
-        list.add(env.isCallerSkylark() ? SkylarkList.tuple(item) : item);
+        list.add(env.isCallerSkylark() ? Tuple.copyOf(item) : item);
       }
-      return convert(list, env, loc);
+      return convert(list, env);
     }
   };
 
@@ -939,7 +1005,7 @@
   private static BuiltinFunction keys = new BuiltinFunction("keys") {
     public Object invoke(Map<Comparable<?>, ?> dict,
         Location loc, Environment env) throws EvalException {
-      return convert(Ordering.natural().sortedCopy(dict.keySet()), env, loc);
+      return convert(Ordering.natural().sortedCopy(dict.keySet()), env);
     }
   };
 
@@ -964,10 +1030,10 @@
 
   // TODO(bazel-team): Use the same type for both Skylark and BUILD files.
   @SuppressWarnings("unchecked")
-  private static Iterable<Object> convert(Collection<?> list, Environment env, Location loc)
+  private static Iterable<Object> convert(Collection<?> list, Environment env)
       throws EvalException {
     if (env.isCallerSkylark()) {
-      return SkylarkList.list(list, loc);
+      return new MutableList(list, env);
     } else {
       return Lists.newArrayList(list);
     }
@@ -985,16 +1051,16 @@
     }
   };
 
-  @SkylarkSignature(name = "list", returnType = SkylarkList.class,
+  @SkylarkSignature(name = "list", returnType = MutableList.class,
       doc = "Converts a collection (e.g. set or dictionary) to a list."
         + "<pre class=\"language-python\">list([1, 2]) == [1, 2]\n"
         + "list(set([2, 3, 2])) == [2, 3]\n"
         + "list({5: \"a\", 2: \"b\", 4: \"c\"}) == [2, 4, 5]</pre>",
       mandatoryPositionals = {@Param(name = "x", doc = "The object to convert.")},
-      useLocation = true)
+      useLocation = true, useEnvironment = true)
   private static BuiltinFunction list = new BuiltinFunction("list") {
-    public SkylarkList invoke(Object x, Location loc) throws EvalException {
-      return SkylarkList.list(EvalUtils.toCollection(x, loc), loc);
+    public MutableList invoke(Object x, Location loc, Environment env) throws EvalException {
+      return new MutableList(EvalUtils.toCollection(x, loc), env);
     }
   };
 
@@ -1187,10 +1253,10 @@
       int count = 0;
       List<SkylarkList> result = Lists.newArrayList();
       for (Object obj : Type.OBJECT_LIST.convert(input, "input")) {
-        result.add(SkylarkList.tuple(count, obj));
+        result.add(Tuple.of(count, obj));
         count++;
       }
-      return convert(result, env, loc);
+      return convert(result, env);
     }
   };
 
@@ -1242,7 +1308,7 @@
           start += step;
         }
       }
-      return convert(result, env, loc);
+      return convert(result, env);
     }
   };
 
@@ -1303,11 +1369,11 @@
         @Param(name = "default", defaultValue = "None",
             doc = "The default value to return in case the struct "
             + "doesn't have an attribute of the given name.")},
-      useLocation = true)
+      useLocation = true, useEnvironment = true)
   private static final BuiltinFunction getattr = new BuiltinFunction("getattr") {
     public Object invoke(Object obj, String name, Object defaultValue,
-        Location loc) throws EvalException, ConversionException {
-      Object result = DotExpression.eval(obj, name, loc);
+        Location loc, Environment env) throws EvalException, ConversionException {
+      Object result = DotExpression.eval(obj, name, loc, env);
       if (result == null) {
         if (defaultValue != Runtime.NONE) {
           return defaultValue;
@@ -1340,7 +1406,7 @@
         // This shouldn't happen
         throw new EvalException(loc, e.getMessage());
       }
-      return SkylarkList.list(fields, String.class);
+      return new MutableList(fields, env);
     }
   };
 
@@ -1409,15 +1475,15 @@
           + "zip([1, 2], [3, 4])  # == [(1, 3), (2, 4)]\n"
           + "zip([1, 2], [3, 4, 5])  # == [(1, 3), (2, 4)]</pre>",
       extraPositionals = {@Param(name = "args", doc = "lists to zip")},
-      returnType = SkylarkList.class, useLocation = true)
+      returnType = MutableList.class, useLocation = true, useEnvironment = true)
   private static final BuiltinFunction zip = new BuiltinFunction("zip") {
-    public SkylarkList invoke(SkylarkList args, Location loc)
+    public MutableList invoke(SkylarkList args, Location loc, Environment env)
         throws EvalException {
       Iterator<?>[] iterators = new Iterator<?>[args.size()];
       for (int i = 0; i < args.size(); i++) {
         iterators[i] = EvalUtils.toIterable(args.get(i), loc).iterator();
       }
-      List<SkylarkList> result = new ArrayList<SkylarkList>();
+      List<Tuple> result = new ArrayList<>();
       boolean allHasNext;
       do {
         allHasNext = !args.isEmpty();
@@ -1430,10 +1496,10 @@
           }
         }
         if (allHasNext) {
-          result.add(SkylarkList.tuple(elem));
+          result.add(Tuple.copyOf(elem));
         }
       } while (allHasNext);
-      return SkylarkList.list(result, loc);
+      return new MutableList(result, env);
     }
   };
 
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Mutability.java b/src/main/java/com/google/devtools/build/lib/syntax/Mutability.java
index a742b7f..31ec345 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Mutability.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Mutability.java
@@ -93,6 +93,15 @@
   }
 
   /**
+   * Freezes this Mutability
+   * @return it in fluent style.
+   */
+  public Mutability freeze() {
+    close();
+    return this;
+  }
+
+  /**
    * A MutabilityException will be thrown when the user attempts to mutate an object he shouldn't.
    */
   static class MutabilityException extends Exception {
@@ -137,4 +146,6 @@
       throw new AssertionError("trying to mutate an object from a different context");
     }
   }
+
+  public static final Mutability IMMUTABLE = create("IMMUTABLE").freeze();
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Printer.java b/src/main/java/com/google/devtools/build/lib/syntax/Printer.java
index bc00795..b4af645 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Printer.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Printer.java
@@ -15,6 +15,7 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Lists;
+import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
 import com.google.devtools.build.lib.vfs.PathFragment;
 
 import java.io.IOException;
@@ -427,7 +428,7 @@
           if (a >= argLength) {
             throw new MissingFormatWidthException("not enough arguments for format pattern "
                 + repr(pattern) + ": "
-                + repr(SkylarkList.tuple(arguments)));
+                + repr(Tuple.copyOf(arguments)));
           }
           Object argument = arguments.get(a++);
           switch (directive) {
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java b/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java
index 098836a..ca83d65 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java
@@ -42,6 +42,8 @@
   /**
    * There should be only one instance of this type to allow "== None" tests.
    */
+  @SkylarkModule(name = "NoneType", documented = false,
+    doc = "Unit type, containing the unique value None")
   @Immutable
   public static final class NoneType implements SkylarkValue {
     private NoneType() {}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkList.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkList.java
index 282a7af..2da6f78 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkList.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkList.java
@@ -14,68 +14,72 @@
 
 package com.google.devtools.build.lib.syntax;
 
-import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.Iterables;
-import com.google.common.collect.Lists;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.events.Location;
+import com.google.devtools.build.lib.syntax.Mutability.Freezable;
+import com.google.devtools.build.lib.syntax.Mutability.MutabilityException;
 
-import java.util.Collection;
+import java.util.ArrayList;
 import java.util.Iterator;
 import java.util.List;
 
+import javax.annotation.Nullable;
+
 /**
  * A class to handle lists and tuples in Skylark.
  */
-@SkylarkModule(name = "list",
-    doc = "A language built-in type to support lists. Example of list literal:<br>"
-        + "<pre class=language-python>x = [1, 2, 3]</pre>"
-        + "Accessing elements is possible using indexing (starts from <code>0</code>):<br>"
-        + "<pre class=language-python>e = x[1]   # e == 2</pre>"
-        + "Lists support the <code>+</code> operator to concatenate two lists. Example:<br>"
-        + "<pre class=language-python>x = [1, 2] + [3, 4]   # x == [1, 2, 3, 4]\n"
-        + "x = [\"a\", \"b\"]\n"
-        + "x += [\"c\"]            # x == [\"a\", \"b\", \"c\"]</pre>"
-        + "List elements have to be of the same type, <code>[1, 2, \"c\"]</code> results in an "
-        + "error. Lists - just like everything - are immutable, therefore <code>x[1] = \"a\""
-        + "</code> is not supported.")
-// TODO(bazel-team): should we instead have it implement List<Object> like ImmutableList does?
+@SkylarkModule(name = "sequence", documented = false,
+    doc = "common type of lists and tuples")
 public abstract class SkylarkList implements Iterable<Object>, SkylarkValue {
 
-  private final boolean tuple;
-  private final SkylarkType contentType;
-
-  private SkylarkList(boolean tuple, SkylarkType contentType) {
-    this.tuple = tuple;
-    this.contentType = contentType;
-  }
+  /**
+   * Returns the List object underlying this SkylarkList.
+   * Mutating it (if mutable) will actually mutate the contents of the list.
+   */
+  // TODO(bazel-team): make this public no more.
+  public abstract List<Object> getList();
 
   /**
-   * The size of the list.
+   * Returns an ImmutableList object with the current underlying contents of this SkylarkList.
    */
-  public abstract int size();
-
-  /**
-   * Returns true if the list is empty.
-   */
-  public abstract boolean isEmpty();
-
-  /**
-   * Returns the i-th element of the list.
-   */
-  public abstract Object get(int i);
+  public abstract ImmutableList<Object> getImmutableList();
 
   /**
    * Returns true if this list is a tuple.
    */
-  public boolean isTuple() {
-    return tuple;
+  public abstract boolean isTuple();
+
+  /**
+   * The size of the list.
+   */
+  public final int size() {
+    return getList().size();
   }
 
-  @VisibleForTesting
-  public SkylarkType getContentType() {
-    return contentType;
+  /**
+   * Returns true if the list is empty.
+   */
+  public final boolean isEmpty() {
+    return getList().isEmpty();
+  }
+
+  /**
+   * Returns the i-th element of the list.
+   */
+  public final Object get(int i) {
+    return getList().get(i);
+  }
+
+  @Override
+  public void write(Appendable buffer, char quotationMark) {
+    Printer.printList(buffer, getList(), isTuple(), quotationMark);
+  }
+
+  @Override
+  public final Iterator<Object> iterator() {
+    return getList().iterator();
   }
 
   @Override
@@ -85,349 +89,233 @@
 
   @Override
   public boolean equals(Object object) {
-    if (this == object) {
-      return true;
-    }
-    if (!(object instanceof SkylarkList)) {
-      return false;
-    }
-    SkylarkList other = (SkylarkList) object;
-    if (this.isTuple() != other.isTuple()) {
-      return false;
-    }
-    return toList().equals(other.toList());
+    return (this == object)
+        || ((this.getClass() == object.getClass())
+            && getList().equals(((SkylarkList) object).getList()));
   }
 
   @Override
   public int hashCode() {
-    return SkylarkList.class.hashCode()
-        + Boolean.valueOf(isTuple()).hashCode()
-        + 31 * toList().hashCode();
+    return getClass().hashCode() + 31 * getList().hashCode();
   }
 
-  // TODO(bazel-team): we should be very careful using this method. Check and remove
-  // auto conversions on the Java-Skylark interface if possible.
-  /**
-   * Returns a mutable Java list copy of this SkylarkList if it's a list or an
-   * immutable copy if it's a tuple.
-   */
-  public abstract List<Object> toList();
-
   @SuppressWarnings("unchecked")
   public <T> Iterable<T> to(Class<T> type) {
-    Preconditions.checkArgument(this == EMPTY_LIST || contentType.canBeCastTo(type));
+    for (Object value : getList()) {
+      Preconditions.checkArgument(
+          type.isInstance(value),
+          Printer.formattable("list element %r is not of type %r", value, type));
+    }
     return (Iterable<T>) this;
   }
 
-  private static final class EmptySkylarkList extends SkylarkList {
-    private EmptySkylarkList(boolean tuple) {
-      super(tuple, SkylarkType.TOP);
+  /**
+   * A class for mutable lists.
+   */
+  @SkylarkModule(name = "list",
+      doc = "A language built-in type to support lists. Example of list literal:<br>"
+      + "<pre class=language-python>x = [1, 2, 3]</pre>"
+      + "Accessing elements is possible using indexing (starts from <code>0</code>):<br>"
+      + "<pre class=language-python>e = x[1]   # e == 2</pre>"
+      + "Lists support the <code>+</code> operator to concatenate two lists. Example:<br>"
+      + "<pre class=language-python>x = [1, 2] + [3, 4]   # x == [1, 2, 3, 4]\n"
+      + "x = [\"a\", \"b\"]\n"
+      + "x += [\"c\"]            # x == [\"a\", \"b\", \"c\"]</pre>"
+      + "Lists are mutable, as in Python.")
+  public static final class MutableList extends SkylarkList implements Freezable {
+
+    private final ArrayList<Object> contents = new ArrayList<>();
+
+    private final Mutability mutability;
+
+    /**
+     * Creates a MutableList from contents and a Mutability.
+     * @param contents the contents of the list
+     * @param mutability a Mutability context
+     * @return a MutableList containing the elements
+     */
+    MutableList(Iterable<?> contents, Mutability mutability) {
+      super();
+      addAll(contents);
+      this.mutability = mutability;
+    }
+
+    /**
+     * Creates a MutableList from contents and an Environment.
+     * @param contents the contents of the list
+     * @param env an Environment from which to inherit Mutability, or null for immutable
+     * @return a MutableList containing the elements
+     */
+    public MutableList(Iterable<?> contents, @Nullable Environment env) {
+      this(contents, env == null ? Mutability.IMMUTABLE : env.mutability());
+    }
+
+    /**
+     * Creates a MutableList from contents and an Environment.
+     * @param contents the contents of the list
+     * @return an actually immutable MutableList containing the elements
+     */
+    public MutableList(Iterable<?> contents) {
+      this(contents, Mutability.IMMUTABLE);
+    }
+
+    /**
+     * Adds one element at the end of the MutableList.
+     * @param element the element to add
+     */
+    private void add(Object element) {
+      this.contents.add(element);
+    }
+
+    /**
+     * Adds all the elements at the end of the MutableList.
+     * @param elements the elements to add
+     */
+    private void addAll(Iterable<?> elements) {
+      for (Object elem : elements) {
+        add(elem);
+      }
+    }
+
+    private void checkMutable(Location loc, Environment env) throws EvalException {
+      try {
+        Mutability.checkMutable(this, env);
+      } catch (MutabilityException ex) {
+        throw new EvalException(loc, ex);
+      }
+    }
+
+    /**
+     * Adds one element at the end of the MutableList.
+     * @param element the element to add
+     * @param loc the Location at which to report any error
+     * @param env the Environment requesting the modification
+     */
+    public void add(Object element, Location loc, Environment env) throws EvalException {
+      checkMutable(loc, env);
+      add(element);
+    }
+
+    /**
+     * Adds all the elements at the end of the MutableList.
+     * @param elements the elements to add
+     * @param loc the Location at which to report any error
+     * @param env the Environment requesting the modification
+     */
+    public void addAll(Iterable<?> elements, Location loc, Environment env) throws EvalException {
+      checkMutable(loc, env);
+      addAll(elements);
+    }
+
+
+    @Override
+    public List<Object> getList() {
+      return contents;
     }
 
     @Override
-    public Iterator<Object> iterator() {
-      return ImmutableList.of().iterator();
+    public ImmutableList<Object> getImmutableList() {
+      return ImmutableList.copyOf(contents);
     }
 
     @Override
-    public int size() {
-      return 0;
+    public Mutability mutability() {
+      return mutability;
     }
 
     @Override
-    public boolean isEmpty() {
+    public boolean isTuple() {
+      return false;
+    }
+
+    @Override
+    public boolean isImmutable() {
+      return false;
+    }
+
+    /**
+     * An empty IMMUTABLE MutableList.
+     */
+    public static final MutableList EMPTY = new MutableList(Tuple.EMPTY);
+  }
+
+  /**
+   * An immutable tuple, e.g. in (1, 2, 3)
+   */
+  @SkylarkModule(name = "tuple",
+      doc = "A language built-in type to support tuples. Example of tuple literal:<br>"
+      + "<pre class=language-python>x = (1, 2, 3)</pre>"
+      + "Accessing elements is possible using indexing (starts from <code>0</code>):<br>"
+      + "<pre class=language-python>e = x[1]   # e == 2</pre>"
+      + "Lists support the <code>+</code> operator to concatenate two tuples. Example:<br>"
+      + "<pre class=language-python>x = (1, 2) + (3, 4)   # x == (1, 2, 3, 4)\n"
+      + "x = (\"a\", \"b\")\n"
+      + "x += (\"c\",)            # x == (\"a\", \"b\", \"c\")</pre>"
+      + "Tuples are immutable, therefore <code>x[1] = \"a\"</code> is not supported.")
+  @Immutable
+  public static final class Tuple extends SkylarkList {
+
+    private final ImmutableList<Object> contents;
+
+    private Tuple(ImmutableList<Object> contents) {
+      super();
+      this.contents = contents;
+    }
+
+    /**
+     * THE empty Skylark tuple.
+     */
+    public static final Tuple EMPTY = new Tuple(ImmutableList.of());
+
+    /**
+     * Creates a Tuple from an ImmutableList.
+     */
+    public static Tuple create(ImmutableList<Object> contents) {
+      if (contents.isEmpty()) {
+        return EMPTY;
+      }
+      return new Tuple(contents);
+    }
+
+    /**
+     * Creates a Tuple from an Iterable.
+     */
+    public static Tuple copyOf(Iterable<?> contents) {
+      return create(ImmutableList.copyOf(contents));
+    }
+
+    /**
+     * Builds a Skylark tuple from a variable number of arguments.
+     * @param elements a variable number of arguments (or an Array of Object-s)
+     * @return a Skylark tuple containing the specified arguments as elements.
+     */
+    public static Tuple of(Object... elements) {
+      return Tuple.create(ImmutableList.copyOf(elements));
+    }
+
+    @Override
+    public List<Object> getList() {
+      return contents;
+    }
+
+    @Override
+    public ImmutableList<Object> getImmutableList() {
+      return contents;
+    }
+
+    @Override
+    public boolean isTuple() {
       return true;
     }
 
     @Override
-    public Object get(int i) {
-      throw new UnsupportedOperationException();
-    }
-
-    @Override
-    public List<Object> toList() {
-      return isTuple() ? ImmutableList.of() : Lists.newArrayList();
-    }
-
-    @Override
-    public String toString() {
-      return isTuple() ? "()" : "[]";
-    }
-  }
-
-  /**
-   * An empty Skylark list.
-   */
-  public static final SkylarkList EMPTY_LIST = new EmptySkylarkList(false);
-
-  /**
-   * An empty Skylark tuple.
-   */
-  public static final SkylarkList EMPTY_TUPLE = new EmptySkylarkList(true);
-
-  private static final class SimpleSkylarkList extends SkylarkList {
-    private final ImmutableList<Object> list;
-
-    private SimpleSkylarkList(ImmutableList<Object> list, boolean tuple, SkylarkType contentType) {
-      super(tuple, contentType);
-      this.list = Preconditions.checkNotNull(list);
-    }
-
-    @Override
-    public Iterator<Object> iterator() {
-      return list.iterator();
-    }
-
-    @Override
-    public int size() {
-      return list.size();
-    }
-
-    @Override
-    public boolean isEmpty() {
-      return list.isEmpty();
-    }
-
-    @Override
-    public Object get(int i) {
-      return list.get(i);
-    }
-
-    @Override
-    public List<Object> toList() {
-      return isTuple() ? list : Lists.newArrayList(list);
-    }
-  }
-
-  /**
-   * A Skylark list to support lazy iteration (i.e. we only call iterator on the object this
-   * list masks when it's absolutely necessary). This is useful if iteration is expensive
-   * (e.g. NestedSet-s). Size(), get() and isEmpty() are expensive operations but
-   * concatenation is quick.
-   */
-  private static final class LazySkylarkList extends SkylarkList {
-    private final Iterable<Object> iterable;
-    private ImmutableList<Object> list = null;
-
-    private LazySkylarkList(Iterable<Object> iterable, boolean tuple, SkylarkType contentType) {
-      super(tuple, contentType);
-      this.iterable = Preconditions.checkNotNull(iterable);
-    }
-
-    @Override
-    public Iterator<Object> iterator() {
-      return iterable.iterator();
-    }
-
-    @Override
-    public int size() {
-      return Iterables.size(iterable);
-    }
-
-    @Override
-    public boolean isEmpty() {
-      return Iterables.isEmpty(iterable);
-    }
-
-    @Override
-    public Object get(int i) {
-      return getList().get(i);
-    }
-
-    @Override
-    public List<Object> toList() {
-      ImmutableList<Object> result = getList();
-      return isTuple() ? result : Lists.newArrayList(result);
-    }
-
-    private ImmutableList<Object> getList() {
-      if (list == null) {
-        list = ImmutableList.copyOf(iterable);
+    public boolean isImmutable() {
+      for (Object item : this) {
+        if (!EvalUtils.isImmutable(item)) {
+          return false;
+        }
       }
-      return list;
+      return true;
     }
   }
-
-  /**
-   * A Skylark list to support quick concatenation of lists. Concatenation is O(1),
-   * size(), isEmpty() is O(n), get() is O(h).
-   */
-  private static final class ConcatenatedSkylarkList extends SkylarkList {
-    private final SkylarkList left;
-    private final SkylarkList right;
-
-    private ConcatenatedSkylarkList(
-        SkylarkList left, SkylarkList right, boolean tuple, SkylarkType contentType) {
-      super(tuple, contentType);
-      this.left = Preconditions.checkNotNull(left);
-      this.right = Preconditions.checkNotNull(right);
-    }
-
-    @Override
-    public Iterator<Object> iterator() {
-      return Iterables.concat(left, right).iterator();
-    }
-
-    @Override
-    public int size() {
-      // We shouldn't evaluate the size function until it's necessary, because it can be expensive
-      // for lazy lists (e.g. lists containing a NestedSet).
-      // TODO(bazel-team): make this class more clever to store the size and empty parameters
-      // for every non-LazySkylarkList member.
-      return left.size() + right.size();
-    }
-
-    @Override
-    public boolean isEmpty() {
-      return left.isEmpty() && right.isEmpty();
-    }
-
-    @Override
-    public Object get(int i) {
-      int leftSize = left.size();
-      if (i < leftSize) {
-        return left.get(i);
-      } else {
-        return right.get(i - leftSize);
-      }
-    }
-
-    @Override
-    public List<Object> toList() {
-      List<Object> result = ImmutableList.<Object>builder().addAll(left).addAll(right).build();
-      return isTuple() ? result : Lists.newArrayList(result);
-    }
-  }
-
-  /**
-   * @param elements the contents of the list
-   * @param contentType a SkylarkType for the contents of the list
-   * @return a Skylark list containing elements without a type check
-   * Only use if you already know for sure all elements are of the specified type.
-   */
-  public static SkylarkList list(Collection<?> elements, SkylarkType contentType) {
-    if (elements.isEmpty()) {
-      return EMPTY_LIST;
-    }
-    return new SimpleSkylarkList(ImmutableList.copyOf(elements), false, contentType);
-  }
-
-  /**
-   * @param elements the contents of the list
-   * @param contentType a Java class for the contents of the list
-   * @return a Skylark list containing elements without a type check
-   * Only use if you already know for sure all elements are of the specified type.
-   */
-  @SuppressWarnings("unchecked")
-  public static SkylarkList list(Collection<?> elements, Class<?> contentType) {
-    return list(elements, SkylarkType.of(contentType));
-  }
-
-  /**
-   * @param elements the contents of the list
-   * @param contentType a SkylarkType for the contents of the list
-   * @return a Skylark list without a type check and without creating an immutable copy
-   * Therefore the iterable containing elements must be immutable
-   * (which is not checked here so callers must be extra careful).
-   * This way it's possibly to create a SkylarkList without requesting the original iterator.
-   * This can be useful for nested set - list conversions.
-   * Only use if you already know for sure all elements are of the specified type.
-   */
-  @SuppressWarnings("unchecked")
-  public static SkylarkList lazyList(Iterable<?> elements, SkylarkType contentType) {
-    return new LazySkylarkList((Iterable<Object>) elements, false, contentType);
-  }
-
-  /**
-   * @param elements the contents of the list
-   * @param contentType a Java class for the contents of the list
-   * @return a Skylark list without a type check and without creating an immutable copy
-   * Therefore the iterable containing elements must be immutable
-   * (which is not checked here so callers must be extra careful).
-   * This way it's possibly to create a SkylarkList without requesting the original iterator.
-   * This can be useful for nested set - list conversions.
-   * Only use if you already know for sure all elements are of the specified type.
-   */
-  @SuppressWarnings("unchecked")
-  public static SkylarkList lazyList(Iterable<?> elements, Class<?> contentType) {
-    return lazyList(elements, SkylarkType.of(contentType));
-  }
-
-  /**
-   * @param elements the contents of the list
-   * @return a Skylark list containing elements
-   * @throws EvalException in case the list is not monomorphic
-   */
-  public static SkylarkList list(Collection<?> elements, Location loc) throws EvalException {
-    if (elements.isEmpty()) {
-      return EMPTY_LIST;
-    }
-    return new SimpleSkylarkList(ImmutableList.copyOf(elements), false, getContentType(elements));
-  }
-
-  private static SkylarkType getContentType(Collection<?> elements)
-      throws EvalException {
-    SkylarkType type = SkylarkType.TOP;
-    for (Object element : elements) {
-      SkylarkType elementType = SkylarkType.typeOf(element);
-      type = SkylarkType.intersection(type, elementType);
-    }
-    return type;
-  }
-
-  /**
-   * Returns a Skylark list created from Skylark lists left and right. Throws an exception
-   * if they are not of the same generic type.
-   */
-  public static SkylarkList concat(SkylarkList left, SkylarkList right, Location loc)
-      throws EvalException {
-    if (left.isTuple() != right.isTuple()) {
-      throw new EvalException(loc, "cannot concatenate lists and tuples");
-    }
-    if (left == EMPTY_LIST) {
-      return right;
-    }
-    if (right == EMPTY_LIST) {
-      return left;
-    }
-    SkylarkType type = SkylarkType.intersection(left.contentType, right.contentType);
-    return new ConcatenatedSkylarkList(left, right, left.isTuple(), type);
-  }
-
-  /**
-   * Build a Skylark tuple from a Java List
-   * @param elements a List of objects
-   * @return a Skylark tuple containing the specified List of objects as elements.
-   */
-  public static SkylarkList tuple(List<?> elements) {
-    // Tuple elements do not have to have the same type.
-    return new SimpleSkylarkList(ImmutableList.copyOf(elements), true, SkylarkType.TOP);
-  }
-
-  /**
-   * Build a Skylark tuple from a variable number of arguments
-   * @param elements a variable number of arguments (or an array of objects)
-   * @return a Skylark tuple containing the specified arguments as elements.
-   */
-  public static SkylarkList tuple(Object... elements) {
-    return new SimpleSkylarkList(ImmutableList.copyOf(elements), true, SkylarkType.TOP);
-  }
-
-  @Override
-  public boolean isImmutable() {
-    if (!isTuple()) {
-      return false;
-    }
-    for (Object item : this) {
-      if (!EvalUtils.isImmutable(item)) {
-        return false;
-      }
-    }
-    return true;
-  }
-
-  @Override
-  public void write(Appendable buffer, char quotationMark) {
-    Printer.printList(buffer, toList(), isTuple(), quotationMark);
-  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkType.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkType.java
index 498c66e..21db288 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkType.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkType.java
@@ -24,6 +24,8 @@
 import com.google.common.collect.Interners;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.events.Location;
+import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
+import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
 
 import java.io.Serializable;
 import java.lang.reflect.Method;
@@ -174,16 +176,26 @@
   /** The MAP type, that contains all Map's, and the generic combinator for maps */
   public static final Simple MAP = Simple.of(Map.class);
 
-  /** The LIST type, that contains all SkylarkList's, and the generic combinator for them */
-  public static final Simple LIST = Simple.of(SkylarkList.class);
+  /** The SEQUENCE type, that contains lists and tuples */
+  // TODO(bazel-team): this was added for backward compatibility with the BUILD language,
+  // that doesn't make a difference between list and tuple, so that functions can be declared
+  // that keep not making the difference. Going forward, though, we should investigate whether
+  // we ever want to use this type, and if not, make sure no existing client code uses it.
+  public static final Simple SEQUENCE = Simple.of(SkylarkList.class);
 
-  /** The STRING_LIST type, a SkylarkList of strings */
+  /** The LIST type, that contains all MutableList-s */
+  public static final Simple LIST = Simple.of(MutableList.class);
+
+  /** The TUPLE type, that contains all Tuple-s */
+  public static final Simple TUPLE = Simple.of(Tuple.class);
+
+  /** The STRING_LIST type, a MutableList of strings */
   public static final SkylarkType STRING_LIST = Combination.of(LIST, STRING);
 
-  /** The INT_LIST type, a SkylarkList of integers */
+  /** The INT_LIST type, a MutableList of integers */
   public static final SkylarkType INT_LIST = Combination.of(LIST, INT);
 
-  /** The SET type, that contains all SkylarkList's, and the generic combinator for them */
+  /** The SET type, that contains all SkylarkNestedSet-s, and the generic combinator for them */
   public static final Simple SET = Simple.of(SkylarkNestedSet.class);
 
 
@@ -314,15 +326,26 @@
       // For now, we only accept generics with a single covariant parameter
       if (genericType.equals(other)) {
         return this;
-      } else if (other instanceof Combination
-          && genericType.equals(((Combination) other).getGenericType())
-          && argType.includes(((Combination) other).getArgType())) {
-        return other;
-      } else if ((LIST.equals(other) || SET.equals(other)) && genericType.equals(other)) {
-        return this;
-      } else {
-        return BOTTOM;
       }
+      if (other instanceof Combination) {
+        SkylarkType generic = genericType.intersectWith(((Combination) other).getGenericType());
+        if (generic == BOTTOM) {
+          return BOTTOM;
+        }
+        SkylarkType arg = intersection(argType, ((Combination) other).getArgType());
+        if (arg == BOTTOM) {
+          return BOTTOM;
+        }
+        return Combination.of(generic, arg);
+      }
+      if (other instanceof Simple) {
+        SkylarkType generic = genericType.intersectWith(other);
+        if (generic == BOTTOM) {
+          return BOTTOM;
+        }
+        return SkylarkType.of(generic, getArgType());
+      }
+      return BOTTOM;
     }
 
     @Override public boolean equals(Object other) {
@@ -477,9 +500,7 @@
   }
 
   public static SkylarkType of(Class<?> type) {
-    if (SkylarkList.class.isAssignableFrom(type)) {
-      return LIST;
-    } else if (SkylarkNestedSet.class.isAssignableFrom(type)) {
+    if (SkylarkNestedSet.class.isAssignableFrom(type)) {
       return SET;
     } else if (BaseFunction.class.isAssignableFrom(type)) {
       return new SkylarkFunctionType("unknown", TOP);
@@ -550,8 +571,6 @@
   public static SkylarkType typeOf(Object value) {
     if (value == null) {
       return BOTTOM;
-    } else if (value instanceof SkylarkList) {
-      return of(LIST, ((SkylarkList) value).getContentType());
     } else if (value instanceof SkylarkNestedSet) {
       return of(SET, ((SkylarkNestedSet) value).getContentType());
     } else {
@@ -560,9 +579,7 @@
   }
 
   public static SkylarkType getGenericArgType(Object value) {
-    if (value instanceof SkylarkList) {
-      return ((SkylarkList) value).getContentType();
-    } else if (value instanceof SkylarkNestedSet) {
+    if (value instanceof SkylarkNestedSet) {
       return ((SkylarkNestedSet) value).getContentType();
     } else {
       return TOP;
@@ -584,7 +601,7 @@
   static void checkTypeAllowedInSkylark(Object object, Location loc) throws EvalException {
     if (!isTypeAllowedInSkylark(object)) {
       throw new EvalException(loc,
-          "Type is not allowed in Skylark: "
+                    "Type is not allowed in Skylark: "
           + object.getClass().getSimpleName());
     }
   }
@@ -713,21 +730,22 @@
   /**
    * Converts an object retrieved from a Java method to a Skylark-compatible type.
    */
-  static Object convertToSkylark(Object object, Method method) {
+  static Object convertToSkylark(Object object, Method method, @Nullable Environment env) {
     if (object instanceof NestedSet<?>) {
       return new SkylarkNestedSet(getGenericTypeFromMethod(method), (NestedSet<?>) object);
-    } else if (object instanceof List<?>) {
-      return SkylarkList.list((List<?>) object, getGenericTypeFromMethod(method));
     }
-    return object;
+    return convertToSkylark(object, env);
   }
 
   /**
    * Converts an object to a Skylark-compatible type if possible.
    */
-  public static Object convertToSkylark(Object object, Location loc) throws EvalException {
+  public static Object convertToSkylark(Object object, @Nullable Environment env) {
     if (object instanceof List<?>) {
-      return SkylarkList.list((List<?>) object, loc);
+      List<?> list = (List<?>) object;
+      // TODO(bazel-team): shouldn't we convert an ImmutableList into a Tuple?
+      // problem: we treat them sometimes as a tuple, sometimes as a list.
+      return new MutableList(list, env);
     }
     return object;
   }
@@ -737,7 +755,7 @@
    */
   public static Object convertFromSkylark(Object value) {
     if (value instanceof SkylarkList) {
-      return ((SkylarkList) value).toList();
+      return ((SkylarkList) value).getList();
     }
     return value;
   }