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 8676c36..fc1fe9a 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
@@ -454,19 +454,11 @@
 
     // string % tuple, string % dict, string % anything-else
     if (lval instanceof String) {
+      String pattern = (String) lval;
       try {
-        String pattern = (String) lval;
-        if (rval instanceof List<?>) {
-          List<?> rlist = (List<?>) rval;
-          if (EvalUtils.isTuple(rlist)) {
-            return Printer.formatToString(pattern, rlist);
-          }
-          /* string % list: fall thru */
-        }
         if (rval instanceof Tuple) {
-          return Printer.formatToString(pattern, ((Tuple) rval).getList());
+          return Printer.formatToString(pattern, (Tuple) rval);
         }
-
         return Printer.formatToString(pattern, Collections.singletonList(rval));
       } catch (IllegalFormatException e) {
         throw new EvalException(location, e.getMessage());
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 b3b1d9e..0d001d3 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
@@ -23,6 +23,7 @@
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
+import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
 import com.google.devtools.build.lib.syntax.compiler.ByteCodeUtils;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -93,28 +94,6 @@
     }
   };
 
-  /**
-   * @return true if the specified sequence is a tuple; false if it's a modifiable list.
-   */
-  public static boolean isTuple(List<?> l) {
-    return isTuple(l.getClass());
-  }
-
-  public static boolean isTuple(Class<?> c) {
-    Preconditions.checkState(List.class.isAssignableFrom(c));
-    return ImmutableList.class.isAssignableFrom(c);
-  }
-
-  public static boolean isTuple(Object o) {
-    if (o instanceof SkylarkList) {
-      return ((SkylarkList) o).isTuple(); // tuples are immutable, lists are not.
-    }
-    if (o instanceof List<?>) {
-      return isTuple(o.getClass());
-    }
-    return false;
-  }
-
   public static final StackManipulation checkValidDictKey =
       ByteCodeUtils.invoke(EvalUtils.class, "checkValidDictKey", Object.class);
 
@@ -137,22 +116,24 @@
    * @param o an Object
    * @return true if the object is known to be an immutable value.
    */
+  // NB: This is used as the basis for accepting objects in SkylarkNestedSet-s,
+  // as well as for accepting objects as keys for Skylark dict-s.
   public static boolean isImmutable(Object o) {
+    if (o instanceof Tuple) {
+      for (Object item : (Tuple) o) {
+        if (!isImmutable(item)) {
+          return false;
+        }
+      }
+      return true;
+    }
+    if (o instanceof SkylarkMutable) {
+      return false;
+    }
     if (o instanceof SkylarkValue) {
       return ((SkylarkValue) o).isImmutable();
     }
-    if (!(o instanceof List<?>)) {
-      return isImmutable(o.getClass());
-    }
-    if (!isTuple((List<?>) o)) {
-      return false;
-    }
-    for (Object item : (List<?>) o) {
-      if (!isImmutable(item)) {
-        return false;
-      }
-    }
-    return true;
+    return isImmutable(o.getClass());
   }
 
   /**
@@ -224,7 +205,9 @@
    * @return a super-class of c to be used in validation-time type inference.
    */
   public static Class<?> getSkylarkType(Class<?> c) {
-    if (ImmutableList.class.isAssignableFrom(c)) {
+    if (SkylarkList.class.isAssignableFrom(c)) {
+      return c;
+    } else if (ImmutableList.class.isAssignableFrom(c)) {
       return ImmutableList.class;
     } else if (List.class.isAssignableFrom(c)) {
       return List.class;
@@ -260,24 +243,19 @@
    * Returns a pretty name for the datatype of object {@code object} in Skylark
    * or the BUILD language, with full details if the {@code full} boolean is true.
    */
-  public static String getDataTypeName(Object object, boolean full) {
+  public static String getDataTypeName(Object object, boolean fullDetails) {
     Preconditions.checkNotNull(object);
-    if (object instanceof SkylarkList) {
-      SkylarkList list = (SkylarkList) object;
-      if (list.isTuple()) {
-        return "tuple";
-      } else {
-        return "list";
+    if (fullDetails) {
+      if (object instanceof SkylarkNestedSet) {
+        SkylarkNestedSet set = (SkylarkNestedSet) object;
+        return "set of " + set.getContentType() + "s";
       }
-    } else if (object instanceof SkylarkNestedSet) {
-      SkylarkNestedSet set = (SkylarkNestedSet) object;
-      return "set" + (full ? " of " + set.getContentType() + "s" : "");
-    } else if (object instanceof SelectorList) {
-      SelectorList list = (SelectorList) object;
-      return "select" + (full ? " of " + getDataTypeNameFromClass(list.getType()) : "");
-    } else {
-      return getDataTypeNameFromClass(object.getClass());
+      if (object instanceof SelectorList) {
+        SelectorList list = (SelectorList) object;
+        return "select of " + getDataTypeNameFromClass(list.getType());
+      }
     }
+    return getDataTypeNameFromClass(object.getClass());
   }
 
   /**
@@ -305,11 +283,6 @@
       return "int";
     } else if (c.equals(Boolean.class)) {
       return "bool";
-    } else if (List.class.isAssignableFrom(c)) {
-      // 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";
     } else if (BaseFunction.class.isAssignableFrom(c)) {
@@ -330,13 +303,6 @@
     }
   }
 
-  /**
-   * Returns a sequence of the appropriate list/tuple datatype for 'seq', based on 'isTuple'.
-   */
-  public static List<?> makeSequence(List<?> seq, boolean isTuple) {
-    return isTuple ? ImmutableList.copyOf(seq) : seq;
-  }
-
   public static Object checkNotNull(Expression expr, Object obj) throws EvalException {
     if (obj == null) {
       throw new EvalException(expr.getLocation(),
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 08455bd..b552c11 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
@@ -981,7 +981,7 @@
             MutableList self, Object start, Object end, Integer step, Location loc,
             Environment env)
             throws EvalException, ConversionException {
-          return new MutableList(sliceList(self.getList(), start, end, step, loc), env);
+          return new MutableList(sliceList(self, start, end, step, loc), env);
         }
       };
 
@@ -1008,7 +1008,7 @@
         @SuppressWarnings("unused") // Accessed via Reflection.
         public Tuple invoke(Tuple self, Object start, Object end, Integer step, Location loc)
             throws EvalException, ConversionException {
-          return Tuple.copyOf(sliceList(self.getList(), start, end, step, loc));
+          return Tuple.copyOf(sliceList(self, start, end, step, loc));
         }
       };
 
@@ -1407,7 +1407,7 @@
             throw new EvalException(loc, "List is empty");
           }
           int index = getListIndex(key, self.size(), loc);
-          return SkylarkType.convertToSkylark(self.getList().get(index), env);
+          return SkylarkType.convertToSkylark(self.get(index), env);
         }
       };
 
@@ -1432,7 +1432,7 @@
             throw new EvalException(loc, "tuple is empty");
           }
           int index = getListIndex(key, self.size(), loc);
-          return SkylarkType.convertToSkylark(self.getList().get(index), env);
+          return SkylarkType.convertToSkylark(self.get(index), env);
         }
       };
 
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 98a483b..88abe13 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
@@ -143,7 +143,7 @@
 
     } else if (o instanceof List<?>) {
       List<?> seq = (List<?>) o;
-      printList(buffer, seq, EvalUtils.isTuple(seq), quotationMark);
+      printList(buffer, seq, false, quotationMark);
 
     } else if (o instanceof Map<?, ?>) {
       Map<?, ?> dict = (Map<?, ?>) o;
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 09d0abd..b24e188 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
@@ -141,16 +141,19 @@
    * <p>Currently, this is only necessary for mapping the different subclasses of {@link
    * java.util.Map} to the interface.
    */
+  // TODO(bazel-team): make everything a SkylarkValue, and remove this function.
   public static Class<?> getCanonicalRepresentation(Class<?> clazz) {
+    if (SkylarkValue.class.isAssignableFrom(clazz)) {
+      return clazz;
+    }
     if (Map.class.isAssignableFrom(clazz)) {
       return MethodLibrary.DictModule.class;
     }
     if (String.class.isAssignableFrom(clazz)) {
       return MethodLibrary.StringModule.class;
     }
-    if (List.class.isAssignableFrom(clazz)) {
-      return List.class;
-    }
+    Preconditions.checkArgument(
+        !List.class.isAssignableFrom(clazz), "invalid non-SkylarkList list class");
     return clazz;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SelectorList.java b/src/main/java/com/google/devtools/build/lib/syntax/SelectorList.java
index 4d76524..0feb423 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SelectorList.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SelectorList.java
@@ -13,9 +13,10 @@
 // limitations under the License.
 package com.google.devtools.build.lib.syntax;
 
-import com.google.common.base.Joiner;
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.events.Location;
+import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
+import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
 
 import java.util.ArrayList;
 import java.util.List;
@@ -37,7 +38,10 @@
  *   )
  * </pre>
  */
-public final class SelectorList {
+@SkylarkModule(name = "select",
+    doc = "A selector between configuration-dependent entities.",
+    documented = false)
+public final class SelectorList implements SkylarkValue {
   // TODO(build-team): Selectors are currently split between .packages and .syntax . They should
   // really all be in .packages, but then we'd need to figure out a way how to extend binary
   // operators, which is a non-trivial problem.
@@ -129,6 +133,16 @@
 
   @Override
   public String toString() {
-    return Joiner.on(" + ").join(elements);
+    return Printer.repr(this);
+  }
+
+  @Override
+  public void write(Appendable buffer, char quotationMark) {
+    Printer.printList(buffer, elements, "", " + ", "", null, quotationMark);
+  }
+
+  @Override
+  public boolean isImmutable() {
+    return false;
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SelectorValue.java b/src/main/java/com/google/devtools/build/lib/syntax/SelectorValue.java
index d4c9366..e9dcb1d 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SelectorValue.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SelectorValue.java
@@ -15,6 +15,9 @@
 
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
+import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
+import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
 
 import java.util.Map;
 import java.util.TreeMap;
@@ -31,7 +34,10 @@
  *       })
  * </pre>
  */
-public final class SelectorValue {
+@SkylarkModule(name = "selector",
+    doc = "A selector between configuration-dependent entities.",
+    documented = false)
+public final class SelectorValue implements SkylarkValue {
   // TODO(bazel-team): Selectors are currently split between .packages and .syntax . They should
   // really all be in .packages, but then we'd need to figure out a way how to extend binary
   // operators, which is a non-trivial problem.
@@ -58,6 +64,16 @@
 
   @Override
   public String toString() {
-    return "selector({...})";
+    return Printer.repr(this);
+  }
+
+  @Override
+  public void write(Appendable buffer, char quotationMark) {
+    Printer.formatTo(buffer, "selector(%r)", Tuple.of(dictionary));
+  }
+
+  @Override
+  public boolean isImmutable() {
+    return false;
   }
 }
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 5c66f81..fddebba 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
@@ -19,14 +19,14 @@
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
-import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
-import com.google.devtools.build.lib.syntax.Mutability.Freezable;
-import com.google.devtools.build.lib.syntax.Mutability.MutabilityException;
+import com.google.devtools.build.lib.syntax.SkylarkMutable.MutableCollection;
 
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.Collections;
-import java.util.Iterator;
 import java.util.List;
+import java.util.ListIterator;
+import java.util.RandomAccess;
 
 import javax.annotation.Nullable;
 
@@ -35,13 +35,8 @@
  */
 @SkylarkModule(name = "sequence", documented = false,
     doc = "common type of lists and tuples")
-public abstract class SkylarkList implements Iterable<Object>, SkylarkValue {
-
-  /**
-   * Returns the List object underlying this SkylarkList.
-   * Mutating it (if mutable) will actually mutate the contents of the list.
-   */
-  protected abstract List<Object> getList();
+  public abstract class SkylarkList
+    extends MutableCollection<Object> implements List<Object>, RandomAccess {
 
   /**
    * Returns an ImmutableList object with the current underlying contents of this SkylarkList.
@@ -50,64 +45,104 @@
 
   /**
    * Returns a List object with the current underlying contents of this SkylarkList.
-   * This object must not be modified, but may not be an ImmutableList.
-   * It may notably be a GlobList, where appropriate.
+   * This object must not be mutated, but need not be an {@link ImmutableList}.
+   * Indeed it can sometimes be a {@link GlobList}.
    */
-  // TODO(bazel-team): move GlobList out of Skylark, into an extension,
-  // and maybe get rid of this method?
-  protected abstract List<Object> getContents();
+  // TODO(bazel-team): move GlobList out of Skylark, into an extension.
+  @Override
+  public abstract List<Object> getContents();
+
+  /**
+   * The underlying contents are a (usually) mutable data structure.
+   * Read access is forwarded to these contents.
+   * This object must not be modified outside an {@link Environment}
+   * with a correct matching {@link Mutability},
+   * which should be checked beforehand using {@link #checkMutable}.
+   * it need not be an instance of {@link com.google.common.collect.ImmutableList}.
+   */
+  @Override
+  protected abstract List<Object> getContentsUnsafe();
 
   /**
    * Returns true if this list is a tuple.
    */
   public abstract boolean isTuple();
 
-  /**
-   * The size of the list.
-   */
-  public final int size() {
-    return getList().size();
-  }
-
-  /**
-   * Returns true if the list is empty.
-   */
-  public final boolean isEmpty() {
-    return getList().isEmpty();
-  }
-
-  /**
-   * Returns the i-th element of the list.
-   */
+  // A SkylarkList forwards all read-only access to the getContentsUnsafe().
+  @Override
   public final Object get(int i) {
-    return getList().get(i);
+    return getContentsUnsafe().get(i);
   }
 
   @Override
+  public int indexOf(Object element) {
+    return getContentsUnsafe().indexOf(element);
+  }
+
+  @Override
+  public int lastIndexOf(Object element) {
+    return getContentsUnsafe().lastIndexOf(element);
+  }
+
+  @Override
+  public ListIterator<Object> listIterator() {
+    return getContentsUnsafe().listIterator();
+  }
+
+  @Override
+  public ListIterator<Object> listIterator(int index) {
+    return getContentsUnsafe().listIterator(index);
+  }
+
+  // For subList, use the immutable getContents() rather than getContentsUnsafe,
+  // to prevent subsequent mutation. To get a mutable SkylarkList,
+  // use a method that takes an Environment into account.
+  @Override
+  public List<Object> subList(int fromIndex, int toIndex) {
+    return getContents().subList(fromIndex, toIndex);
+  }
+
+  // A SkylarkList disables all direct mutation methods.
+  @Override
+  public void add(int index, Object element) {
+    throw new UnsupportedOperationException();
+  }
+
+  @Override
+  public boolean addAll(int index, Collection<?> elements) {
+    throw new UnsupportedOperationException();
+  }
+
+  @Override
+  public Object remove(int index) {
+    throw new UnsupportedOperationException();
+  }
+
+  @Override
+  public Object set(int index, Object element) {
+    throw new UnsupportedOperationException();
+  }
+
+  // Other methods
+  @Override
   public void write(Appendable buffer, char quotationMark) {
-    Printer.printList(buffer, getList(), isTuple(), quotationMark);
+    Printer.printList(buffer, getContentsUnsafe(), isTuple(), quotationMark);
   }
 
-  @Override
-  public final Iterator<Object> iterator() {
-    return getList().iterator();
-  }
-
-  @Override
-  public String toString() {
-    return Printer.repr(this);
-  }
-
+  // Note that the following two functions slightly violate the Java List protocol,
+  // in that it does NOT consider that a SkylarkList .equals() an arbitrary List with same contents.
+  // This is because we use .equals() to model skylark equality, which like Python
+  // distinguishes a MutableList from a Tuple.
   @Override
   public boolean equals(Object object) {
     return (this == object)
         || ((this.getClass() == object.getClass())
-            && getList().equals(((SkylarkList) object).getList()));
+            && getContentsUnsafe().equals(((SkylarkList) object).getContentsUnsafe()));
   }
 
   @Override
   public int hashCode() {
-    return getClass().hashCode() + 31 * getList().hashCode();
+    return getClass().hashCode() + 31 * getContentsUnsafe().hashCode();
   }
 
   /**
@@ -160,10 +195,9 @@
    */
   public <TYPE> List<TYPE> getContents(Class<TYPE> type, @Nullable String description)
       throws EvalException {
-    return castList(getContents(), type, description);
+    return castList(getContentsUnsafe(), type, description);
   }
 
-
   /**
    * A class for mutable lists.
    */
@@ -184,7 +218,7 @@
             + "['a', 'b', 'c', 'd'][3:0:-1]  # ['d', 'c', 'b']</pre>"
             + "Lists are mutable, as in Python."
   )
-  public static final class MutableList extends SkylarkList implements Freezable {
+  public static final class MutableList extends SkylarkList {
 
     private final ArrayList<Object> contents = new ArrayList<>();
 
@@ -204,7 +238,7 @@
      */
     MutableList(Iterable<?> contents, Mutability mutability) {
       super();
-      addAll(contents);
+      addAllUnsafe(contents);
       if (contents instanceof GlobList<?>) {
         globList = (GlobList<?>) contents;
       }
@@ -248,29 +282,19 @@
     }
 
     /**
-     * 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
+     * Assumes that you already checked for Mutability.
      */
-    private void addAll(Iterable<?> elements) {
+    private void addAllUnsafe(Iterable<?> elements) {
       for (Object elem : elements) {
-        add(elem);
+        contents.add(elem);
       }
     }
 
-    private void checkMutable(Location loc, Environment env) throws EvalException {
-      try {
-        Mutability.checkMutable(this, env);
-      } catch (MutabilityException ex) {
-        throw new EvalException(loc, ex);
-      }
+    @Override
+    protected void checkMutable(Location loc, Environment env) throws EvalException {
+      super.checkMutable(loc, env);
       globList = null; // If you're going to mutate it, invalidate the underlying GlobList.
     }
 
@@ -290,10 +314,15 @@
       return getImmutableList();
     }
 
+    @Override
+    protected List<Object> getContentsUnsafe() {
+      return contents;
+    }
+
     /**
      * @return the GlobList if there is one, otherwise the regular contents.
      */
-    private List<?> getContentsUnsafe() {
+    private List<?> getGlobListOrContentsUnsafe() {
       if (globList != null) {
         return globList;
       }
@@ -312,7 +341,7 @@
         return new MutableList(Iterables.concat(left, right), env);
       }
       return new MutableList(GlobList.concat(
-          left.getContentsUnsafe(), right.getContentsUnsafe()), env);
+          left.getGlobListOrContentsUnsafe(), right.getGlobListOrContentsUnsafe()), env);
     }
 
     /**
@@ -323,7 +352,7 @@
      */
     public void add(Object element, Location loc, Environment env) throws EvalException {
       checkMutable(loc, env);
-      add(element);
+      contents.add(element);
     }
 
     public void remove(int index, Location loc, Environment env) throws EvalException {
@@ -339,13 +368,7 @@
      */
     public void addAll(Iterable<?> elements, Location loc, Environment env) throws EvalException {
       checkMutable(loc, env);
-      addAll(elements);
-    }
-
-
-    @Override
-    public List<Object> getList() {
-      return contents;
+      addAllUnsafe(elements);
     }
 
     @Override
@@ -404,6 +427,11 @@
       this.contents = contents;
     }
 
+    @Override
+    public Mutability mutability() {
+      return Mutability.IMMUTABLE;
+    }
+
     /**
      * THE empty Skylark tuple.
      */
@@ -437,11 +465,6 @@
     }
 
     @Override
-    public List<Object> getList() {
-      return contents;
-    }
-
-    @Override
     public ImmutableList<Object> getImmutableList() {
       return contents;
     }
@@ -452,6 +475,11 @@
     }
 
     @Override
+    protected List<Object> getContentsUnsafe() {
+      return contents;
+    }
+
+    @Override
     public boolean isTuple() {
       return true;
     }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkMutable.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkMutable.java
new file mode 100644
index 0000000..afa107a
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkMutable.java
@@ -0,0 +1,158 @@
+// Copyright 2016 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.devtools.build.lib.syntax;
+
+import com.google.devtools.build.lib.events.Location;
+import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
+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.Iterator;
+
+import javax.annotation.Nullable;
+
+/**
+ * Base class for data structures that are only mutable with a proper Mutability.
+ */
+abstract class SkylarkMutable implements Freezable, SkylarkValue {
+
+  protected SkylarkMutable() {}
+
+  /**
+   * Check whether this object is mutable in the current evaluation Environment.
+   * @throws EvalException if the object was not mutable.
+   */
+  protected void checkMutable(Location loc, Environment env) throws EvalException {
+    try {
+      Mutability.checkMutable(this, env);
+    } catch (MutabilityException ex) {
+      throw new EvalException(loc, ex);
+    }
+  }
+
+  @Override
+  public String toString() {
+    return Printer.repr(this);
+  }
+
+  abstract static class MutableCollection<E> extends SkylarkMutable implements Collection<E> {
+
+    protected MutableCollection() {}
+
+    /**
+     * Return the underlying contents of this collection,
+     * that may be of a more specific class with its own methods.
+     * This object MUST NOT be mutated.
+     * If possible, the implementation should make this object effectively immutable,
+     * by throwing {@link UnsupportedOperationException} if attemptedly mutated;
+     * but it need not be an instance of {@link com.google.common.collect.ImmutableCollection}.
+     */
+    public abstract Collection<Object> getContents();
+
+    /**
+     * The underlying contents is a (usually) mutable data structure.
+     * Read access is forwarded to these contents.
+     * This object must not be modified outside an {@link Environment}
+     * with a correct matching {@link Mutability},
+     * which should be checked beforehand using {@link #checkMutable}.
+     * it need not be an instance of {@link com.google.common.collect.ImmutableCollection}.
+     */
+    protected abstract Collection<E> getContentsUnsafe();
+
+    @Override
+    public Iterator<E> iterator() {
+      return getContentsUnsafe().iterator();
+    };
+
+    @Override
+    public int size() {
+      return getContentsUnsafe().size();
+    }
+
+    @Override
+    public final Object[] toArray() {
+      return getContentsUnsafe().toArray();
+    }
+
+    @Override
+    public final <Object> Object[] toArray(Object[] other) {
+      return getContentsUnsafe().toArray(other);
+    }
+
+    @Override
+    public boolean isEmpty() {
+      return getContentsUnsafe().isEmpty();
+    }
+
+    @Override
+    public final boolean contains(@Nullable Object object) {
+      return getContentsUnsafe().contains(object);
+    }
+
+    @Override
+    public final boolean containsAll(Collection<?> collection) {
+      return getContentsUnsafe().containsAll(collection);
+    }
+
+    // Disable all mutation interfaces without a mutation context.
+
+    @Deprecated
+    @Override
+    public final boolean add(E element) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Deprecated
+    @Override
+    public final boolean addAll(Collection<? extends E> collection) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Deprecated
+    @Override
+    public final boolean remove(Object object) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Deprecated
+    @Override
+    public final boolean removeAll(Collection<?> collection) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Deprecated
+    @Override
+    public final boolean retainAll(Collection<?> collection) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Deprecated
+    @Override
+    public final void clear() {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public boolean equals(Object o) {
+      return getContentsUnsafe().equals(o);
+    }
+
+    @Override
+    public int hashCode() {
+      return getContentsUnsafe().hashCode();
+    }
+  }
+}
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 553fc5e..709557a 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
@@ -235,7 +235,8 @@
                 ruleContext.getRuleContext().getAnalysisEnvironment().getRegisteredActions());
     assertArtifactFilenames(action.getInputs(), "a.txt", "b.img");
     assertArtifactFilenames(action.getOutputs(), "a.txt", "b.img");
-    MoreAsserts.assertContainsSublist(action.getArguments(), "-c", "dummy_command", "", "--a", "--b");
+    MoreAsserts.assertContainsSublist(action.getArguments(),
+        "-c", "dummy_command", "", "--a", "--b");
     assertEquals("DummyMnemonic", action.getMnemonic());
     assertEquals("dummy_message", action.getProgressMessage());
     assertEquals(targetConfig.getLocalShellEnvironment(), action.getEnvironment());
@@ -502,7 +503,7 @@
         "  command='I got the $(HELLO) on a $(DAVE)', ",
         "  make_variables={'HELLO': 'World', 'DAVE': type('')})");
     @SuppressWarnings("unchecked")
-    List<String> argv = (List<String>) (List<?>) ((MutableList) lookup("argv")).getList();
+    List<String> argv = (List<String>) (List<?>) (MutableList) lookup("argv");
     assertThat(argv).hasSize(3);
     assertMatches("argv[0]", "^.*/bash$", argv.get(0));
     assertThat(argv.get(1)).isEqualTo("-c");
@@ -516,7 +517,7 @@
         "inputs, argv, manifests = ruleContext.resolve_command(",
         "   tools=ruleContext.attr.tools)");
     @SuppressWarnings("unchecked")
-    List<Artifact> inputs = (List<Artifact>) (List<?>) ((MutableList) lookup("inputs")).getList();
+    List<Artifact> inputs = (List<Artifact>) (List<?>) (MutableList) lookup("inputs");
     assertArtifactFilenames(inputs, "mytool.sh", "mytool", "foo_Smytool-runfiles", "t.exe");
     Map<?, ?> manifests = (Map<?, ?>) lookup("manifests");
     assertThat(manifests).hasSize(1);
@@ -537,7 +538,7 @@
         "    attribute='cmd', expand_locations=True, label_dict=label_dict)",
         "inputs, argv, manifests = foo()");
     @SuppressWarnings("unchecked")
-    List<String> argv = (List<String>) (List<?>) ((MutableList) lookup("argv")).getList();
+    List<String> argv = (List<String>) (List<?>) (MutableList) lookup("argv");
     assertThat(argv).hasSize(3);
     assertMatches("argv[0]", "^.*/bash$", argv.get(0));
     assertThat(argv.get(1)).isEqualTo("-c");
@@ -555,7 +556,7 @@
         "    command=s)",
         "argv = foo()[1]");
     @SuppressWarnings("unchecked")
-    List<String> argv = (List<String>) (List<?>) ((MutableList) lookup("argv")).getList();
+    List<String> argv = (List<String>) (List<?>) (MutableList) lookup("argv");
     assertThat(argv).hasSize(2);
     assertMatches("argv[0]", "^.*/bash$", argv.get(0));
     assertMatches("argv[1]", "^.*/resolve_me[.]script[.]sh$", argv.get(1));
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/EvalUtilsTest.java b/src/test/java/com/google/devtools/build/lib/syntax/EvalUtilsTest.java
index f5cb497..4989cbd 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/EvalUtilsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/EvalUtilsTest.java
@@ -19,13 +19,14 @@
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertTrue;
 
+import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
+import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
+
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
 
-import java.util.Arrays;
 import java.util.LinkedHashMap;
-import java.util.List;
 import java.util.Map;
 import java.util.TreeMap;
 
@@ -36,14 +37,6 @@
 @RunWith(JUnit4.class)
 public class EvalUtilsTest {
 
-  private static List<?> makeList(Object... args) {
-    return EvalUtils.makeSequence(Arrays.<Object>asList(args), false);
-  }
-
-  private static List<?> makeTuple(Object... args) {
-    return EvalUtils.makeSequence(Arrays.<Object>asList(args), true);
-  }
-
   private static Map<Object, Object> makeDict() {
     return new LinkedHashMap<>();
   }
@@ -62,8 +55,8 @@
   public void testDataTypeNames() throws Exception {
     assertEquals("string", EvalUtils.getDataTypeName("foo"));
     assertEquals("int", EvalUtils.getDataTypeName(3));
-    assertEquals("Tuple", EvalUtils.getDataTypeName(makeTuple(1, 2, 3)));
-    assertEquals("List",  EvalUtils.getDataTypeName(makeList(1, 2, 3)));
+    assertEquals("tuple", EvalUtils.getDataTypeName(Tuple.of(1, 2, 3)));
+    assertEquals("list",  EvalUtils.getDataTypeName(MutableList.of(null, 1, 2, 3)));
     assertEquals("dict",  EvalUtils.getDataTypeName(makeDict()));
     assertEquals("NoneType", EvalUtils.getDataTypeName(Runtime.NONE));
   }
@@ -72,8 +65,8 @@
   public void testDatatypeMutability() throws Exception {
     assertTrue(EvalUtils.isImmutable("foo"));
     assertTrue(EvalUtils.isImmutable(3));
-    assertTrue(EvalUtils.isImmutable(makeTuple(1, 2, 3)));
-    assertFalse(EvalUtils.isImmutable(makeList(1, 2, 3)));
+    assertTrue(EvalUtils.isImmutable(Tuple.of(1, 2, 3)));
+    assertFalse(EvalUtils.isImmutable(MutableList.of(null, 1, 2, 3)));
     assertFalse(EvalUtils.isImmutable(makeDict()));
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/PrinterTest.java b/src/test/java/com/google/devtools/build/lib/syntax/PrinterTest.java
index 19bd520..2807b1b 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/PrinterTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/PrinterTest.java
@@ -22,6 +22,8 @@
 import com.google.common.base.Strings;
 import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
+import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
 
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -41,14 +43,6 @@
 @RunWith(JUnit4.class)
 public class PrinterTest {
 
-  private static List<?> makeList(Object... args) {
-    return EvalUtils.makeSequence(Arrays.<Object>asList(args), false);
-  }
-
-  private static List<?> makeTuple(Object... args) {
-    return EvalUtils.makeSequence(Arrays.<Object>asList(args), true);
-  }
-
   @Test
   public void testPrinter() throws Exception {
     // Note that prettyPrintValue and printValue only differ on behaviour of
@@ -68,22 +62,22 @@
     assertEquals("\"//x:x\"", Printer.repr(
         Label.parseAbsolute("//x")));
 
-    List<?> list = makeList("foo", "bar");
-    List<?> tuple = makeTuple("foo", "bar");
+    List<?> list = MutableList.of(null, "foo", "bar");
+    List<?> tuple = Tuple.of("foo", "bar");
 
     assertEquals("(1, [\"foo\", \"bar\"], 3)",
-                 Printer.str(makeTuple(1, list, 3)));
+                 Printer.str(Tuple.of(1, list, 3)));
     assertEquals("(1, [\"foo\", \"bar\"], 3)",
-                 Printer.repr(makeTuple(1, list, 3)));
+                 Printer.repr(Tuple.of(1, list, 3)));
     assertEquals("[1, (\"foo\", \"bar\"), 3]",
-                 Printer.str(makeList(1, tuple, 3)));
+                 Printer.str(MutableList.of(null, 1, tuple, 3)));
     assertEquals("[1, (\"foo\", \"bar\"), 3]",
-                 Printer.repr(makeList(1, tuple, 3)));
+                 Printer.repr(MutableList.of(null, 1, tuple, 3)));
 
     Map<Object, Object> dict = ImmutableMap.<Object, Object>of(
         1, tuple,
         2, list,
-        "foo", makeList());
+        "foo", MutableList.of(null));
     assertEquals("{1: (\"foo\", \"bar\"), 2: [\"foo\", \"bar\"], \"foo\": []}",
                 Printer.str(dict));
     assertEquals("{1: (\"foo\", \"bar\"), 2: [\"foo\", \"bar\"], \"foo\": []}",
@@ -112,12 +106,12 @@
 
   @Test
   public void testFormatPositional() throws Exception {
-    assertEquals("foo 3", Printer.formatToString("%s %d", makeTuple("foo", 3)));
+    assertEquals("foo 3", Printer.formatToString("%s %d", Tuple.of("foo", 3)));
     assertEquals("foo 3", Printer.format("%s %d", "foo", 3));
 
     // Note: formatToString doesn't perform scalar x -> (x) conversion;
     // The %-operator is responsible for that.
-    assertThat(Printer.formatToString("", makeTuple())).isEmpty();
+    assertThat(Printer.formatToString("", Tuple.of())).isEmpty();
     assertEquals("foo", Printer.format("%s", "foo"));
     assertEquals("3.14159", Printer.format("%s", 3.14159));
     checkFormatPositionalFails("not all arguments converted during string formatting",
@@ -127,10 +121,10 @@
         "%%s", "foo");
     checkFormatPositionalFails("unsupported format character \" \" at index 1 in \"% %s\"",
         "% %s", "foo");
-    assertEquals("[1, 2, 3]", Printer.format("%s", makeList(1, 2, 3)));
-    assertEquals("(1, 2, 3)", Printer.format("%s", makeTuple(1, 2, 3)));
-    assertEquals("[]", Printer.format("%s", makeList()));
-    assertEquals("()", Printer.format("%s", makeTuple()));
+    assertEquals("[1, 2, 3]", Printer.format("%s", MutableList.of(null, 1, 2, 3)));
+    assertEquals("(1, 2, 3)", Printer.format("%s", Tuple.of(1, 2, 3)));
+    assertEquals("[]", Printer.format("%s", MutableList.of(null)));
+    assertEquals("()", Printer.format("%s", Tuple.of()));
     assertEquals("% 1 \"2\" 3", Printer.format("%% %d %r %s", 1, "2", "3"));
 
     checkFormatPositionalFails(
@@ -153,16 +147,18 @@
     assertEquals("\"", Printer.str("\"", '\''));
     assertEquals("'\"'", Printer.repr("\"", '\''));
 
-    List<?> list = makeList("foo", "bar");
-    List<?> tuple = makeTuple("foo", "bar");
+    List<?> list = MutableList.of(null, "foo", "bar");
+    List<?> tuple = Tuple.of("foo", "bar");
 
-    assertThat(Printer.str(makeTuple(1, list, 3), '\'')).isEqualTo("(1, ['foo', 'bar'], 3)");
-    assertThat(Printer.repr(makeTuple(1, list, 3), '\'')).isEqualTo("(1, ['foo', 'bar'], 3)");
-    assertThat(Printer.str(makeList(1, tuple, 3), '\'')).isEqualTo("[1, ('foo', 'bar'), 3]");
-    assertThat(Printer.repr(makeList(1, tuple, 3), '\'')).isEqualTo("[1, ('foo', 'bar'), 3]");
+    assertThat(Printer.str(Tuple.of(1, list, 3), '\'')).isEqualTo("(1, ['foo', 'bar'], 3)");
+    assertThat(Printer.repr(Tuple.of(1, list, 3), '\'')).isEqualTo("(1, ['foo', 'bar'], 3)");
+    assertThat(Printer.str(MutableList.of(null, 1, tuple, 3), '\''))
+        .isEqualTo("[1, ('foo', 'bar'), 3]");
+    assertThat(Printer.repr(MutableList.of(null, 1, tuple, 3), '\''))
+        .isEqualTo("[1, ('foo', 'bar'), 3]");
 
     Map<Object, Object> dict =
-        ImmutableMap.<Object, Object>of(1, tuple, 2, list, "foo", makeList());
+        ImmutableMap.<Object, Object>of(1, tuple, 2, list, "foo", MutableList.of(null));
 
     assertThat(Printer.str(dict, '\''))
         .isEqualTo("{1: ('foo', 'bar'), 2: ['foo', 'bar'], 'foo': []}");
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/TypeTest.java b/src/test/java/com/google/devtools/build/lib/syntax/TypeTest.java
index 48c27e5..b5f2bd8 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/TypeTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/TypeTest.java
@@ -27,6 +27,8 @@
 import com.google.devtools.build.lib.packages.BuildType;
 import com.google.devtools.build.lib.packages.License;
 import com.google.devtools.build.lib.packages.TriState;
+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.Type.ConversionException;
 import com.google.devtools.build.lib.testutil.MoreAsserts;
 
@@ -292,14 +294,13 @@
 
   @Test
   public void testStringDictBadElements() throws Exception {
-    Object input = ImmutableMap.of("foo", Arrays.asList("bar", "baz"),
-        "wiz", "bang");
+    Object input = ImmutableMap.of("foo", MutableList.of(null, "bar", "baz"), "wiz", "bang");
     try {
       Type.STRING_DICT.convert(input, null);
       fail();
     } catch (Type.ConversionException e) {
       assertThat(e).hasMessage("expected value of type 'string' for dict value element, "
-          + "but got [\"bar\", \"baz\"] (List)");
+          + "but got [\"bar\", \"baz\"] (list)");
     }
   }
 
@@ -489,14 +490,13 @@
 
   @Test
   public void testStringListDictBadElements1() throws Exception {
-    Object input = ImmutableMap.of(Arrays.asList("foo"), Arrays.asList("bang"),
-                                   "wiz", Arrays.asList("bang"));
+    Object input = ImmutableMap.of(Tuple.of("foo"), Tuple.of("bang"), "wiz", Tuple.of("bang"));
     try {
       Type.STRING_LIST_DICT.convert(input, null);
       fail();
     } catch (Type.ConversionException e) {
       assertThat(e).hasMessage("expected value of type 'string' for dict key element, but got "
-          + "[\"foo\"] (List)");
+          + "(\"foo\",) (tuple)");
     }
   }
 
@@ -529,28 +529,25 @@
 
   @Test
   public void testStringDictUnaryBadSecondElement() throws Exception {
-    Object input = ImmutableMap.of("foo", "bar",
-                                   "wiz", Arrays.asList("bang"));
+    Object input = ImmutableMap.of("foo", "bar", "wiz", MutableList.of(null, "bang"));
     try {
       Type.STRING_DICT_UNARY.convert(input, null, currentRule);
       fail();
     } catch (Type.ConversionException e) {
       assertThat(e).hasMessage("expected value of type 'string' for dict value element, but got "
-          + "[\"bang\"] (List)");
+          + "[\"bang\"] (list)");
     }
   }
 
   @Test
   public void testStringDictUnaryBadElements1() throws Exception {
-    Object input = ImmutableMap.of("foo", "bar",
-                                   Arrays.asList("foo", "bar"),
-                                   Arrays.<Object>asList("wiz", "bang"));
+    Object input = ImmutableMap.of("foo", "bar", Tuple.of("foo", "bar"), Tuple.of("wiz", "bang"));
     try {
       Type.STRING_DICT_UNARY.convert(input, null);
       fail();
     } catch (Type.ConversionException e) {
       assertThat(e).hasMessage("expected value of type 'string' for dict key element, but got "
-          + "[\"foo\", \"bar\"] (List)");
+          + "(\"foo\", \"bar\") (tuple)");
     }
   }