Rollback of commit f941d56acfad5f8c819c81b494f806ea74ea7fd8.

*** Reason for rollback ***

Breaks many targets, see []

*** Original change description ***

Reinstate mutable SkylarkDict

Add <String, Object> annotation to optionMap invocation in SkylarkAttr,
to make JDK 1.7 happy.

Give the visible name "aspect" to class SkylarkAspect.

--
MOS_MIGRATED_REVID=113543873
diff --git a/src/main/java/com/google/devtools/build/lib/actions/Artifact.java b/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
index 6473cdc..24bece9 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
@@ -28,7 +28,6 @@
 import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
-import com.google.devtools.build.lib.syntax.EvalUtils;
 import com.google.devtools.build.lib.syntax.Printer;
 import com.google.devtools.build.lib.util.FileType;
 import com.google.devtools.build.lib.util.Preconditions;
@@ -73,8 +72,7 @@
 @SkylarkModule(name = "File",
     doc = "This type represents a file used by the build system. It can be "
         + "either a source file or a derived file produced by a rule.")
-  public class Artifact
-    implements FileType.HasFilename, ActionInput, SkylarkValue, Comparable<Object> {
+public class Artifact implements FileType.HasFilename, ActionInput, SkylarkValue {
 
   /**
    * Compares artifact according to their exec paths. Sorts null values first.
@@ -94,15 +92,6 @@
     }
   };
 
-  @Override
-  public int compareTo(Object o) {
-    if (o instanceof Artifact) {
-      return EXEC_PATH_COMPARATOR.compare(this, (Artifact) o);
-    }
-    return EvalUtils.compareByClass(this, o);
-  }
-
-
   /** An object that can expand middleman artifacts. */
   public interface MiddlemanExpander {
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/CommandHelper.java b/src/main/java/com/google/devtools/build/lib/analysis/CommandHelper.java
index 7176011..b2523de 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/CommandHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/CommandHelper.java
@@ -25,9 +25,6 @@
 import com.google.devtools.build.lib.analysis.actions.FileWriteAction;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
-import com.google.devtools.build.lib.syntax.SkylarkDict;
-import com.google.devtools.build.lib.syntax.SkylarkList;
-import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
 import com.google.devtools.build.lib.syntax.Type;
 import com.google.devtools.build.lib.util.OS;
 import com.google.devtools.build.lib.util.Pair;
@@ -72,14 +69,14 @@
    *  A map of remote path prefixes and corresponding runfiles manifests for tools
    *  used by this rule.
    */
-  private final SkylarkDict<PathFragment, Artifact> remoteRunfileManifestMap;
+  private final ImmutableMap<PathFragment, Artifact> remoteRunfileManifestMap;
 
   /**
    * Use labelMap for heuristically expanding labels (does not include "outs")
    * This is similar to heuristic location expansion in LocationExpander
    * and should be kept in sync.
    */
-  private final SkylarkDict<Label, ImmutableCollection<Artifact>> labelMap;
+  private final ImmutableMap<Label, ImmutableCollection<Artifact>> labelMap;
 
   /**
    * The ruleContext this helper works on
@@ -89,7 +86,7 @@
   /**
    * Output executable files from the 'tools' attribute.
    */
-  private final SkylarkList<Artifact> resolvedTools;
+  private final ImmutableList<Artifact> resolvedTools;
 
   /**
    * Creates a {@link CommandHelper}.
@@ -139,21 +136,21 @@
       }
     }
 
-    this.resolvedTools = new MutableList<>(resolvedToolsBuilder.build());
-    this.remoteRunfileManifestMap = SkylarkDict.copyOf(null, remoteRunfileManifestBuilder.build());
+    this.resolvedTools = resolvedToolsBuilder.build();
+    this.remoteRunfileManifestMap = remoteRunfileManifestBuilder.build();
     ImmutableMap.Builder<Label, ImmutableCollection<Artifact>> labelMapBuilder =
         ImmutableMap.builder();
     for (Entry<Label, Collection<Artifact>> entry : tempLabelMap.entrySet()) {
       labelMapBuilder.put(entry.getKey(), ImmutableList.copyOf(entry.getValue()));
     }
-    this.labelMap = SkylarkDict.copyOf(null, labelMapBuilder.build());
+    this.labelMap = labelMapBuilder.build();
   }
 
-  public SkylarkList<Artifact> getResolvedTools() {
+  public List<Artifact> getResolvedTools() {
     return resolvedTools;
   }
 
-  public SkylarkDict<PathFragment, Artifact> getRemoteRunfileManifestMap() {
+  public ImmutableMap<PathFragment, Artifact> getRemoteRunfileManifestMap() {
     return remoteRunfileManifestMap;
   }
 
@@ -180,8 +177,7 @@
       @Nullable String attribute,
       Boolean supportLegacyExpansion,
       Boolean allowDataInLabel) {
-    LocationExpander expander = new LocationExpander(
-        ruleContext, ImmutableMap.copyOf(labelMap), allowDataInLabel);
+    LocationExpander expander = new LocationExpander(ruleContext, labelMap, allowDataInLabel);
     if (attribute != null) {
       command = expander.expandAttribute(attribute, command);
     } else {
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ConfigurationMakeVariableContext.java b/src/main/java/com/google/devtools/build/lib/analysis/ConfigurationMakeVariableContext.java
index 5629c83a..62e9b61 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ConfigurationMakeVariableContext.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ConfigurationMakeVariableContext.java
@@ -14,10 +14,10 @@
 
 package com.google.devtools.build.lib.analysis;
 
+import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.analysis.MakeVariableExpander.ExpansionException;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.packages.Package;
-import com.google.devtools.build.lib.syntax.SkylarkDict;
 
 import java.util.LinkedHashMap;
 import java.util.Map;
@@ -56,13 +56,13 @@
     return value;
   }
 
-  public SkylarkDict<String, String> collectMakeVariables() {
+  public ImmutableMap<String, String> collectMakeVariables() {
     Map<String, String> map = new LinkedHashMap<>();
     // Collect variables in the reverse order as in lookupMakeVariable
     // because each update is overwriting.
     map.putAll(pkg.getAllMakeVariables(platform));
     map.putAll(globalEnv);
     map.putAll(commandLineEnv);
-    return SkylarkDict.<String, String>copyOf(null, map);
+    return ImmutableMap.copyOf(map);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/genrule/GenRule.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/genrule/GenRule.java
index c1382c0..d9c855a 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/genrule/GenRule.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/genrule/GenRule.java
@@ -16,7 +16,6 @@
 
 import static com.google.devtools.build.lib.analysis.RunfilesProvider.withData;
 
-import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
@@ -133,13 +132,13 @@
     ruleContext.registerAction(
         new GenRuleAction(
             ruleContext.getActionOwner(),
-            ImmutableList.copyOf(commandHelper.getResolvedTools()),
+            commandHelper.getResolvedTools(),
             inputs.build(),
             filesToBuild,
             argv,
             env,
             ImmutableMap.copyOf(executionInfo),
-            ImmutableMap.copyOf(commandHelper.getRemoteRunfileManifestMap()),
+            commandHelper.getRemoteRunfileManifestMap(),
             message + ' ' + ruleContext.getLabel()));
 
     RunfilesProvider runfilesProvider = withData(
diff --git a/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java b/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
index 8fa9219..b2aa1f6 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
@@ -54,7 +54,6 @@
 import com.google.devtools.build.lib.syntax.Mutability;
 import com.google.devtools.build.lib.syntax.ParserInputSource;
 import com.google.devtools.build.lib.syntax.Runtime;
-import com.google.devtools.build.lib.syntax.SkylarkDict;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
 import com.google.devtools.build.lib.syntax.SkylarkSignatureProcessor;
@@ -848,23 +847,21 @@
       };
 
   @Nullable
-  static SkylarkDict<String, Object> callGetRuleFunction(
+  static Map<String, Object> callGetRuleFunction(
       String name, FuncallExpression ast, Environment env)
       throws EvalException, ConversionException {
     PackageContext context = getContext(env, ast);
     Target target = context.pkgBuilder.getTarget(name);
 
-    return targetDict(target, ast.getLocation(), env);
+    return targetDict(target);
   }
 
   @Nullable
-  private static SkylarkDict<String, Object> targetDict(
-      Target target, Location loc, Environment env)
-      throws NotRepresentableException, EvalException {
+  private static Map<String, Object> targetDict(Target target) throws NotRepresentableException {
     if (target == null && !(target instanceof Rule)) {
       return null;
     }
-    SkylarkDict<String, Object> values = SkylarkDict.<String, Object>of(env);
+    Map<String, Object> values = new TreeMap<>();
 
     Rule rule = (Rule) target;
     AttributeContainer cont = rule.getAttributeContainer();
@@ -884,7 +881,7 @@
         if (val == null) {
           continue;
         }
-        values.put(attr.getName(), val, loc, env);
+        values.put(attr.getName(), val);
       } catch (NotRepresentableException e) {
         throw new NotRepresentableException(
             String.format(
@@ -892,8 +889,8 @@
       }
     }
 
-    values.put("name", rule.getName(), loc, env);
-    values.put("kind", rule.getRuleClass(), loc, env);
+    values.put("name", rule.getName());
+    values.put("kind", rule.getRuleClass());
     return values;
   }
 
@@ -1014,21 +1011,18 @@
   }
 
 
-  static SkylarkDict<String, SkylarkDict<String, Object>> callGetRulesFunction(
-      FuncallExpression ast, Environment env)
-      throws EvalException {
+  static Map callGetRulesFunction(FuncallExpression ast, Environment env) throws EvalException {
     PackageContext context = getContext(env, ast);
     Collection<Target> targets = context.pkgBuilder.getTargets();
-    Location loc = ast.getLocation();
 
     // Sort by name.
-    SkylarkDict<String, SkylarkDict<String, Object>> rules =
-        SkylarkDict.<String, SkylarkDict<String, Object>>of(env);
+    Map<String, Map<String, Object>> rules = new TreeMap<>();
     for (Target t : targets) {
       if (t instanceof Rule) {
-        SkylarkDict<String, Object> m = targetDict(t, loc, env);
+        Map<String, Object> m = targetDict(t);
         Preconditions.checkNotNull(m);
-        rules.put(t.getName(), m, loc, env);
+
+        rules.put(t.getName(), m);
       }
     }
 
@@ -1341,8 +1335,8 @@
   public Preprocessor.Result preprocess(
       PackageIdentifier packageId, Path buildFile, CachingPackageLocator locator)
       throws InterruptedException, IOException {
-    byte[] buildFileBytes =
-        FileSystemUtils.readWithKnownFileSize(buildFile, buildFile.getFileSize());
+    byte[] buildFileBytes = FileSystemUtils.readWithKnownFileSize(
+        buildFile, buildFile.getFileSize());
     Globber globber = createLegacyGlobber(buildFile.getParentDirectory(), packageId, locator);
     try {
       return preprocess(buildFile, packageId, buildFileBytes, globber);
@@ -1676,7 +1670,6 @@
     SkylarkSignatureProcessor.configureSkylarkFunctions(PackageFactory.class);
   }
 
-  /** Empty EnvironmentExtension */
   public static class EmptyEnvironmentExtension implements EnvironmentExtension {
     @Override
     public void update(Environment environment) {}
diff --git a/src/main/java/com/google/devtools/build/lib/packages/SkylarkNativeModule.java b/src/main/java/com/google/devtools/build/lib/packages/SkylarkNativeModule.java
index cecb714..2f935dd 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/SkylarkNativeModule.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/SkylarkNativeModule.java
@@ -22,11 +22,12 @@
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.FuncallExpression;
 import com.google.devtools.build.lib.syntax.Runtime;
-import com.google.devtools.build.lib.syntax.SkylarkDict;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkSignatureProcessor;
 import com.google.devtools.build.lib.syntax.Type.ConversionException;
 
+import java.util.Map;
+
 /**
  * A class for the Skylark native module.
  */
@@ -111,8 +112,12 @@
         public Object invoke(String name, FuncallExpression ast, Environment env)
             throws EvalException, InterruptedException {
           env.checkLoadingPhase("native.rule", ast.getLocation());
-          SkylarkDict<String, Object> rule = PackageFactory.callGetRuleFunction(name, ast, env);
-          return rule == null ? Runtime.NONE : rule;
+          Map<String, Object> rule = PackageFactory.callGetRuleFunction(name, ast, env);
+          if (rule != null) {
+            return rule;
+          }
+
+          return Runtime.NONE;
         }
       };
 
@@ -134,7 +139,7 @@
         public Object invoke(String name, FuncallExpression ast, Environment env)
             throws EvalException, InterruptedException {
           env.checkLoadingPhase("native.existing_rule", ast.getLocation());
-          SkylarkDict<String, Object> rule = PackageFactory.callGetRuleFunction(name, ast, env);
+          Map<String, Object> rule = PackageFactory.callGetRuleFunction(name, ast, env);
           if (rule != null) {
             return rule;
           }
@@ -147,7 +152,7 @@
   @SkylarkSignature(
     name = "rules",
     objectType = SkylarkNativeModule.class,
-    returnType = SkylarkDict.class,
+    returnType = Map.class,
     doc = "Deprecated. Use existing_rules instead.",
     mandatoryPositionals = {},
     useAst = true,
@@ -155,8 +160,7 @@
   )
   private static final BuiltinFunction getRules =
       new BuiltinFunction("rules") {
-        public SkylarkDict<String, SkylarkDict<String, Object>> invoke(
-            FuncallExpression ast, Environment env)
+        public Map<?, ?> invoke(FuncallExpression ast, Environment env)
             throws EvalException, InterruptedException {
           env.checkLoadingPhase("native.rules", ast.getLocation());
           return PackageFactory.callGetRulesFunction(ast, env);
@@ -170,7 +174,7 @@
   @SkylarkSignature(
     name = "existing_rules",
     objectType = SkylarkNativeModule.class,
-    returnType = SkylarkDict.class,
+    returnType = Map.class,
     doc =
         "Returns a dict containing all the rules instantiated so far. "
             + "The map key is the name of the rule. The map value is equivalent to the "
@@ -181,8 +185,7 @@
   )
   private static final BuiltinFunction existingRules =
       new BuiltinFunction("existing_rules") {
-        public SkylarkDict<String, SkylarkDict<String, Object>> invoke(
-            FuncallExpression ast, Environment env)
+        public Map<?, ?> invoke(FuncallExpression ast, Environment env)
             throws EvalException, InterruptedException {
           env.checkLoadingPhase("native.existing_rules", ast.getLocation());
           return PackageFactory.callGetRulesFunction(ast, env);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/SkylarkAttr.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkAttr.java
index 6e22fbf..aa2fef9 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkAttr.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkAttr.java
@@ -15,6 +15,7 @@
 package com.google.devtools.build.lib.rules;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.packages.Attribute;
@@ -33,7 +34,6 @@
 import com.google.devtools.build.lib.syntax.FuncallExpression;
 import com.google.devtools.build.lib.syntax.Runtime;
 import com.google.devtools.build.lib.syntax.SkylarkCallbackFunction;
-import com.google.devtools.build.lib.syntax.SkylarkDict;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkSignatureProcessor;
 import com.google.devtools.build.lib.syntax.Type;
@@ -42,6 +42,7 @@
 import com.google.devtools.build.lib.util.FileTypeSet;
 
 import java.util.List;
+import java.util.Map;
 
 /**
  * A helper class to provide Attr module in Skylark.
@@ -105,12 +106,12 @@
       "the list of allowed values for the attribute. An error is raised if any other "
           + "value is given.";
 
-  private static boolean containsNonNoneKey(SkylarkDict<String, Object> arguments, String key) {
+  private static boolean containsNonNoneKey(Map<String, Object> arguments, String key) {
     return arguments.containsKey(key) && arguments.get(key) != Runtime.NONE;
   }
 
   private static Attribute.Builder<?> createAttribute(
-      Type<?> type, SkylarkDict<String, Object> arguments, FuncallExpression ast, Environment env)
+      Type<?> type, Map<String, Object> arguments, FuncallExpression ast, Environment env)
       throws EvalException, ConversionException {
     // We use an empty name now so that we can set it later.
     // This trick makes sense only in the context of Skylark (builtin rules should not use it).
@@ -191,7 +192,7 @@
   }
 
   private static Descriptor createAttrDescriptor(
-      SkylarkDict<String, Object> kwargs, Type<?> type, FuncallExpression ast, Environment env)
+      Map<String, Object> kwargs, Type<?> type, FuncallExpression ast, Environment env)
       throws EvalException {
     try {
       return new Descriptor(createAttribute(type, kwargs, ast, env));
@@ -230,15 +231,15 @@
         public Descriptor invoke(
             Integer defaultInt,
             Boolean mandatory,
-            SkylarkList<?> values,
+            SkylarkList values,
             FuncallExpression ast,
             Environment env)
             throws EvalException {
           // TODO(bazel-team): Replace literal strings with constants.
           env.checkLoadingPhase("attr.int", ast.getLocation());
           return createAttrDescriptor(
-              EvalUtils.<String, Object>optionMap(
-                  env, DEFAULT_ARG, defaultInt, MANDATORY_ARG, mandatory, VALUES_ARG, values),
+              EvalUtils.optionMap(
+                  DEFAULT_ARG, defaultInt, MANDATORY_ARG, mandatory, VALUES_ARG, values),
               Type.INTEGER,
               ast,
               env);
@@ -275,14 +276,14 @@
         public Descriptor invoke(
             String defaultString,
             Boolean mandatory,
-            SkylarkList<?> values,
+            SkylarkList values,
             FuncallExpression ast,
             Environment env)
             throws EvalException {
           env.checkLoadingPhase("attr.string", ast.getLocation());
           return createAttrDescriptor(
-              EvalUtils.<String, Object>optionMap(
-                  env, DEFAULT_ARG, defaultString, MANDATORY_ARG, mandatory, VALUES_ARG, values),
+              EvalUtils.optionMap(
+                  DEFAULT_ARG, defaultString, MANDATORY_ARG, mandatory, VALUES_ARG, values),
               Type.STRING,
               ast,
               env);
@@ -360,7 +361,7 @@
             Boolean executable,
             Object allowFiles,
             Boolean mandatory,
-            SkylarkList<?> providers,
+            SkylarkList providers,
             Object allowRules,
             Boolean singleFile,
             Object cfg,
@@ -369,8 +370,7 @@
             throws EvalException {
           env.checkLoadingPhase("attr.label", ast.getLocation());
           return createAttrDescriptor(
-              EvalUtils.<String, Object>optionMap(
-                  env,
+              EvalUtils.optionMap(
                   DEFAULT_ARG,
                   defaultO,
                   EXECUTABLE_ARG,
@@ -417,7 +417,7 @@
   private static BuiltinFunction stringList =
       new BuiltinFunction("string_list") {
         public Descriptor invoke(
-            SkylarkList<?> defaultList,
+            SkylarkList defaultList,
             Boolean mandatory,
             Boolean nonEmpty,
             FuncallExpression ast,
@@ -425,14 +425,8 @@
             throws EvalException {
           env.checkLoadingPhase("attr.string_list", ast.getLocation());
           return createAttrDescriptor(
-              EvalUtils.<String, Object>optionMap(
-                  env,
-                  DEFAULT_ARG,
-                  defaultList,
-                  MANDATORY_ARG,
-                  mandatory,
-                  NON_EMPTY_ARG,
-                  nonEmpty),
+              EvalUtils.optionMap(
+                  DEFAULT_ARG, defaultList, MANDATORY_ARG, mandatory, NON_EMPTY_ARG, nonEmpty),
               Type.STRING_LIST,
               ast,
               env);
@@ -463,7 +457,7 @@
   private static BuiltinFunction intList =
       new BuiltinFunction("int_list") {
         public Descriptor invoke(
-            SkylarkList<?> defaultList,
+            SkylarkList defaultList,
             Boolean mandatory,
             Boolean nonEmpty,
             FuncallExpression ast,
@@ -471,14 +465,8 @@
             throws EvalException {
           env.checkLoadingPhase("attr.int_list", ast.getLocation());
           return createAttrDescriptor(
-              EvalUtils.<String, Object>optionMap(
-                  env,
-                  DEFAULT_ARG,
-                  defaultList,
-                  MANDATORY_ARG,
-                  mandatory,
-                  NON_EMPTY_ARG,
-                  nonEmpty),
+              EvalUtils.optionMap(
+                  DEFAULT_ARG, defaultList, MANDATORY_ARG, mandatory, NON_EMPTY_ARG, nonEmpty),
               Type.INTEGER_LIST,
               ast,
               env);
@@ -559,20 +547,18 @@
             Object defaultList,
             Object allowFiles,
             Object allowRules,
-            SkylarkList<?> providers,
-            SkylarkList<?> flags,
+            SkylarkList providers,
+            SkylarkList flags,
             Boolean mandatory,
             Boolean nonEmpty,
             Object cfg,
-            SkylarkList<?> aspects,
+            SkylarkList aspects,
             FuncallExpression ast,
             Environment env)
             throws EvalException {
           env.checkLoadingPhase("attr.label_list", ast.getLocation());
-          SkylarkDict<String, Object> kwargs = EvalUtils.<String, Object>optionMap(
-              env,
-              DEFAULT_ARG,
-              defaultList,
+          ImmutableMap<String, Object> kwargs = EvalUtils.optionMap(
+              DEFAULT_ARG, defaultList,
               ALLOW_FILES_ARG,
               allowFiles,
               ALLOW_RULES_ARG,
@@ -590,13 +576,25 @@
           try {
             Attribute.Builder<?> attribute = createAttribute(
                 BuildType.LABEL_LIST, kwargs, ast, env);
-            ImmutableList<SkylarkAspect> skylarkAspects =
-                ImmutableList.copyOf(aspects.getContents(SkylarkAspect.class, "aspects"));
+
+            ImmutableList<SkylarkAspect> skylarkAspects = getSkylarkAspects(aspects);
             return new Descriptor(attribute, skylarkAspects);
-          } catch (EvalException e) {
-            throw new EvalException(ast.getLocation(), e.getMessage(), e);
+          } catch (ConversionException e) {
+            throw new EvalException(ast.getLocation(), e.getMessage());
           }
         }
+
+        protected ImmutableList<SkylarkAspect> getSkylarkAspects(SkylarkList aspects)
+            throws ConversionException {
+          ImmutableList.Builder<SkylarkAspect> aspectBuilder = ImmutableList.builder();
+          for (Object aspect : aspects) {
+            if (!(aspect instanceof SkylarkAspect)) {
+              throw new ConversionException("Expected a list of aspects for 'aspects'");
+            }
+            aspectBuilder.add((SkylarkAspect) aspect);
+          }
+          return aspectBuilder.build();
+        }
       };
 
   @SkylarkSignature(
@@ -619,8 +617,7 @@
             throws EvalException {
           env.checkLoadingPhase("attr.bool", ast.getLocation());
           return createAttrDescriptor(
-              EvalUtils.<String, Object>optionMap(
-                  env, DEFAULT_ARG, defaultO, MANDATORY_ARG, mandatory),
+              EvalUtils.optionMap(DEFAULT_ARG, defaultO, MANDATORY_ARG, mandatory),
               Type.BOOLEAN,
               ast,
               env);
@@ -656,8 +653,7 @@
             throws EvalException {
           env.checkLoadingPhase("attr.output", ast.getLocation());
           return createAttrDescriptor(
-              EvalUtils.<String, Object>optionMap(
-                  env, DEFAULT_ARG, defaultO, MANDATORY_ARG, mandatory),
+              EvalUtils.optionMap(DEFAULT_ARG, defaultO, MANDATORY_ARG, mandatory),
               BuildType.OUTPUT,
               ast,
               env);
@@ -698,14 +694,8 @@
             throws EvalException {
           env.checkLoadingPhase("attr.output_list", ast.getLocation());
           return createAttrDescriptor(
-              EvalUtils.<String, Object>optionMap(
-                  env,
-                  DEFAULT_ARG,
-                  defaultList,
-                  MANDATORY_ARG,
-                  mandatory,
-                  NON_EMPTY_ARG,
-                  nonEmpty),
+              EvalUtils.optionMap(
+                  DEFAULT_ARG, defaultList, MANDATORY_ARG, mandatory, NON_EMPTY_ARG, nonEmpty),
               BuildType.OUTPUT_LIST,
               ast,
               env);
@@ -720,7 +710,7 @@
     objectType = SkylarkAttr.class,
     returnType = Descriptor.class,
     optionalNamedOnly = {
-      @Param(name = DEFAULT_ARG, type = SkylarkDict.class, defaultValue = "{}", doc = DEFAULT_DOC),
+      @Param(name = DEFAULT_ARG, type = Map.class, defaultValue = "{}", doc = DEFAULT_DOC),
       @Param(name = MANDATORY_ARG, type = Boolean.class, defaultValue = "False", doc = MANDATORY_DOC
       ),
       @Param(name = NON_EMPTY_ARG, type = Boolean.class, defaultValue = "False", doc = NON_EMPTY_DOC
@@ -732,7 +722,7 @@
   private static BuiltinFunction stringDict =
       new BuiltinFunction("string_dict") {
         public Descriptor invoke(
-            SkylarkDict<?, ?> defaultO,
+            Map<?, ?> defaultO,
             Boolean mandatory,
             Boolean nonEmpty,
             FuncallExpression ast,
@@ -740,8 +730,8 @@
             throws EvalException {
           env.checkLoadingPhase("attr.string_dict", ast.getLocation());
           return createAttrDescriptor(
-              EvalUtils.<String, Object>optionMap(
-                  env, DEFAULT_ARG, defaultO, MANDATORY_ARG, mandatory, NON_EMPTY_ARG, nonEmpty),
+              EvalUtils.optionMap(
+                  DEFAULT_ARG, defaultO, MANDATORY_ARG, mandatory, NON_EMPTY_ARG, nonEmpty),
               Type.STRING_DICT,
               ast,
               env);
@@ -756,7 +746,7 @@
     objectType = SkylarkAttr.class,
     returnType = Descriptor.class,
     optionalNamedOnly = {
-      @Param(name = DEFAULT_ARG, type = SkylarkDict.class, defaultValue = "{}", doc = DEFAULT_DOC),
+      @Param(name = DEFAULT_ARG, type = Map.class, defaultValue = "{}", doc = DEFAULT_DOC),
       @Param(name = MANDATORY_ARG, type = Boolean.class, defaultValue = "False", doc = MANDATORY_DOC
       ),
       @Param(name = NON_EMPTY_ARG, type = Boolean.class, defaultValue = "False", doc = NON_EMPTY_DOC
@@ -768,7 +758,7 @@
   private static BuiltinFunction stringListDict =
       new BuiltinFunction("string_list_dict") {
         public Descriptor invoke(
-            SkylarkDict<?, ?> defaultO,
+            Map<?, ?> defaultO,
             Boolean mandatory,
             Boolean nonEmpty,
             FuncallExpression ast,
@@ -776,8 +766,8 @@
             throws EvalException {
           env.checkLoadingPhase("attr.string_list_dict", ast.getLocation());
           return createAttrDescriptor(
-              EvalUtils.<String, Object>optionMap(
-                  env, DEFAULT_ARG, defaultO, MANDATORY_ARG, mandatory, NON_EMPTY_ARG, nonEmpty),
+              EvalUtils.optionMap(
+                  DEFAULT_ARG, defaultO, MANDATORY_ARG, mandatory, NON_EMPTY_ARG, nonEmpty),
               Type.STRING_LIST_DICT,
               ast,
               env);
@@ -806,8 +796,7 @@
             throws EvalException {
           env.checkLoadingPhase("attr.license", ast.getLocation());
           return createAttrDescriptor(
-              EvalUtils.<String, Object>optionMap(
-                  env, DEFAULT_ARG, defaultO, MANDATORY_ARG, mandatory),
+              EvalUtils.optionMap(DEFAULT_ARG, defaultO, MANDATORY_ARG, mandatory),
               BuildType.LICENSE,
               ast,
               env);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleClassFunctions.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleClassFunctions.java
index 4ff90d9..5fb0bc5 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleClassFunctions.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleClassFunctions.java
@@ -69,7 +69,6 @@
 import com.google.devtools.build.lib.packages.TargetUtils;
 import com.google.devtools.build.lib.packages.TestSize;
 import com.google.devtools.build.lib.rules.SkylarkAttr.Descriptor;
-import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkSignature;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkSignature.Param;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
@@ -86,7 +85,6 @@
 import com.google.devtools.build.lib.syntax.Printer;
 import com.google.devtools.build.lib.syntax.Runtime;
 import com.google.devtools.build.lib.syntax.SkylarkCallbackFunction;
-import com.google.devtools.build.lib.syntax.SkylarkDict;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.syntax.SkylarkSignatureProcessor;
@@ -226,8 +224,7 @@
             doc = "Whether this rule is a test rule. "
             + "If True, the rule must end with <code>_test</code> (otherwise it must not), "
             + "and there must be an action that generates <code>ctx.outputs.executable</code>."),
-        @Param(name = "attrs", type = SkylarkDict.class, noneable = true, defaultValue = "None",
-            doc =
+        @Param(name = "attrs", type = Map.class, noneable = true, defaultValue = "None", doc =
             "dictionary to declare all the attributes of the rule. It maps from an attribute name "
             + "to an attribute object (see <a href=\"attr.html\">attr</a> module). "
             + "Attributes starting with <code>_</code> are private, and can be used to add "
@@ -236,7 +233,7 @@
             + "<code>deprecation</code>, <code>tags</code>, <code>testonly</code>, and "
             + "<code>features</code> are implicitly added and might be overriden."),
             // TODO(bazel-team): need to give the types of these builtin attributes
-        @Param(name = "outputs", type = SkylarkDict.class, callbackEnabled = true, noneable = true,
+        @Param(name = "outputs", type = Map.class, callbackEnabled = true, noneable = true,
             defaultValue = "None", doc = "outputs of this rule. "
             + "It is a dictionary mapping from string to a template name. "
             + "For example: <code>{\"ext\": \"%{name}.ext\"}</code>. <br>"
@@ -365,7 +362,7 @@
         doc = "List of attribute names.  The aspect propagates along dependencies specified by "
         + " attributes of a target with this name"
       ),
-      @Param(name = "attrs", type = SkylarkDict.class, noneable = true, defaultValue = "None",
+      @Param(name = "attrs", type = Map.class, noneable = true, defaultValue = "None",
         doc = "dictionary to declare all the attributes of the aspect.  "
         + "It maps from an attribute name to an attribute object "
         + "(see <a href=\"attr.html\">attr</a> module). "
@@ -709,7 +706,6 @@
   /**
    * A Skylark value that is a result of 'aspect(..)' function call.
    */
-  @SkylarkModule(name = "aspect", doc = "", documented = false)
   public static final class SkylarkAspect implements SkylarkValue {
     private final BaseFunction implementation;
     private final ImmutableList<String> attributeAspects;
@@ -852,12 +848,10 @@
       return aspectDefinition;
     }
 
-    @Override
     public Label getExtensionLabel() {
       return extensionLabel;
     }
 
-    @Override
     public String getExportedName() {
       return exportedName;
     }
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 32f8125..c57f48e 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
@@ -52,7 +52,6 @@
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.FuncallExpression.FuncallException;
 import com.google.devtools.build.lib.syntax.Runtime;
-import com.google.devtools.build.lib.syntax.SkylarkDict;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
 import com.google.devtools.build.lib.syntax.SkylarkType;
@@ -153,7 +152,7 @@
 
   private final FragmentCollection hostFragments;
 
-  private final SkylarkDict<String, String> makeVariables;
+  private final ImmutableMap<String, String> makeVariables;
   private final SkylarkRuleAttributesCollection attributesCollection;
   private final SkylarkRuleAttributesCollection ruleAttributesCollection;
 
@@ -518,7 +517,7 @@
 
   @SkylarkCallable(structField = true,
       doc = "Dictionary (String to String) of configuration variables")
-  public SkylarkDict<String, String> var() {
+  public ImmutableMap<String, String> var() {
     return makeVariables;
   }
 
@@ -528,7 +527,7 @@
   }
 
   @SkylarkCallable(doc = "Splits a shell command to a list of tokens.", documented = false)
-  public MutableList<String> tokenize(String optionString) throws FuncallException {
+  public MutableList tokenize(String optionString) throws FuncallException {
     List<String> options = new ArrayList<>();
     try {
       ShellUtils.tokenize(options, optionString);
@@ -545,8 +544,7 @@
           + "Deprecated.",
     documented = false
   )
-  public String expand(
-      @Nullable String expression, SkylarkList<Object> artifacts, Label labelResolver)
+  public String expand(@Nullable String expression, SkylarkList artifacts, Label labelResolver)
       throws EvalException, FuncallException {
     try {
       Map<Label, Iterable<Artifact>> labelMap = new HashMap<>();
@@ -598,7 +596,7 @@
   }
 
   @SkylarkCallable(documented = false)
-  public boolean checkPlaceholders(String template, SkylarkList<Object> allowedPlaceholders)
+  public boolean checkPlaceholders(String template, SkylarkList allowedPlaceholders)
       throws EvalException {
     List<String> actualPlaceHolders = new LinkedList<>();
     Set<String> allowedPlaceholderSet =
diff --git a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleImplementationFunctions.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleImplementationFunctions.java
index 7b69e37..d04f7e5 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleImplementationFunctions.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleImplementationFunctions.java
@@ -52,7 +52,6 @@
 import com.google.devtools.build.lib.syntax.EvalUtils;
 import com.google.devtools.build.lib.syntax.Printer;
 import com.google.devtools.build.lib.syntax.Runtime;
-import com.google.devtools.build.lib.syntax.SkylarkDict;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
 import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
@@ -144,8 +143,8 @@
         defaultValue = "None",
         doc =
             "shell command to execute. It is usually preferable to "
-                + "use <code>executable</code> instead. "
-                + "Arguments are available with <code>$1</code>, <code>$2</code>, etc."
+                + "use <code>executable</code> instead. Arguments are available with "
+                + "<code>$1</code>, <code>$2</code>, etc."
       ),
       @Param(
         name = "progress_message",
@@ -164,14 +163,14 @@
       ),
       @Param(
         name = "env",
-        type = SkylarkDict.class,
+        type = Map.class,
         noneable = true,
         defaultValue = "None",
         doc = "sets the dictionary of environment variables"
       ),
       @Param(
         name = "execution_requirements",
-        type = SkylarkDict.class,
+        type = Map.class,
         noneable = true,
         defaultValue = "None",
         doc =
@@ -180,7 +179,7 @@
       ),
       @Param(
         name = "input_manifests",
-        type = SkylarkDict.class,
+        type = Map.class,
         noneable = true,
         defaultValue = "None",
         doc =
@@ -204,7 +203,7 @@
             Boolean useDefaultShellEnv,
             Object envO,
             Object executionRequirementsO,
-            Object inputManifests,
+            Object inputManifestsO,
             Location loc)
             throws EvalException, ConversionException {
           SpawnAction.Builder builder = new SpawnAction.Builder();
@@ -290,11 +289,14 @@
                         String.class,
                         "execution_requirements")));
           }
-          if (inputManifests instanceof SkylarkDict) {
+          if (inputManifestsO != Runtime.NONE) {
             for (Map.Entry<PathFragment, Artifact> entry :
-                     ((SkylarkDict<?, ?>) inputManifests)
-                     .getContents(PathFragment.class, Artifact.class, "input manifest file map")
-                     .entrySet()) {
+                castMap(
+                        inputManifestsO,
+                        PathFragment.class,
+                        Artifact.class,
+                        "input manifest file map")
+                    .entrySet()) {
               builder.addInputManifest(entry.getValue(), entry.getKey());
             }
           }
@@ -457,7 +459,7 @@
             doc = "the template file"),
         @Param(name = "output", type = Artifact.class,
             doc = "the output file"),
-        @Param(name = "substitutions", type = SkylarkDict.class,
+        @Param(name = "substitutions", type = Map.class,
             doc = "substitutions to make when expanding the template")},
       optionalNamedOnly = {
         @Param(name = "executable", type = Boolean.class,
@@ -465,23 +467,23 @@
   private static final BuiltinFunction createTemplateAction =
       new BuiltinFunction("template_action", Arrays.<Object>asList(false)) {
         public TemplateExpansionAction invoke(SkylarkRuleContext ctx,
-            Artifact template, Artifact output, SkylarkDict<?, ?> substitutions, Boolean executable)
+            Artifact template, Artifact output, Map<?, ?> substitutionsO, Boolean executable)
             throws EvalException, ConversionException {
-          ImmutableList.Builder<Substitution> substitutionsBuilder = ImmutableList.builder();
-          for (Map.Entry<String, String> substitution : substitutions.getContents(
-              String.class, String.class, "substitutions").entrySet()) {
+          ImmutableList.Builder<Substitution> substitutions = ImmutableList.builder();
+          for (Map.Entry<String, String> substitution : castMap(
+              substitutionsO, String.class, String.class, "substitutions").entrySet()) {
             // ParserInputSource.create(Path) uses Latin1 when reading BUILD files, which might
             // contain UTF-8 encoded symbols as part of template substitution.
             // As a quick fix, the substitution values are corrected before being passed on.
             // In the long term, fixing ParserInputSource.create(Path) would be a better approach.
-            substitutionsBuilder.add(Substitution.of(
+            substitutions.add(Substitution.of(
                 substitution.getKey(), convertLatin1ToUtf8(substitution.getValue())));
           }
           TemplateExpansionAction action = new TemplateExpansionAction(
               ctx.getRuleContext().getActionOwner(),
               template,
               output,
-              substitutionsBuilder.build(),
+              substitutions.build(),
               executable);
           ctx.getRuleContext().registerAction(action);
           return action;
@@ -572,8 +574,7 @@
 
   // TODO(bazel-team): find a better way to typecheck this argument.
   @SuppressWarnings("unchecked")
-  private static Map<Label, Iterable<Artifact>> checkLabelDict(
-      Map<?, ?> labelDict, Location loc)
+  private static Map<Label, Iterable<Artifact>> checkLabelDict(Map<?, ?> labelDict, Location loc)
       throws EvalException {
     for (Map.Entry<?, ?> entry : labelDict.entrySet()) {
       Object key = entry.getKey();
@@ -632,7 +633,7 @@
       ),
       @Param(
         name = "make_variables",
-        type = SkylarkDict.class, // dict(string, string)
+        type = Map.class, // dict(string, string)
         noneable = true,
         doc = "make variables to expand, or None"
       ),
@@ -645,7 +646,7 @@
       ),
       @Param(
         name = "label_dict",
-        type = SkylarkDict.class,
+        type = Map.class,
         defaultValue = "{}",
         doc =
             "dictionary of resolved labels and the corresponding list of Files "
@@ -657,24 +658,24 @@
   private static final BuiltinFunction resolveCommand =
       new BuiltinFunction("resolve_command") {
         @SuppressWarnings("unchecked")
-        public Tuple<Object> invoke(
+        public Tuple invoke(
             SkylarkRuleContext ctx,
             String command,
             Object attributeO,
             Boolean expandLocations,
             Object makeVariablesO,
             SkylarkList tools,
-            SkylarkDict<?, ?> labelDict,
+            Map<?, ?> labelDictM,
             Location loc,
             Environment env)
             throws ConversionException, EvalException {
           Label ruleLabel = ctx.getLabel();
-          Map<Label, Iterable<Artifact>> labelDictM = checkLabelDict(labelDict, loc);
+          Map<Label, Iterable<Artifact>> labelDict = checkLabelDict(labelDictM, loc);
           // The best way to fix this probably is to convert CommandHelper to Skylark.
           CommandHelper helper = new CommandHelper(
               ctx.getRuleContext(),
               tools.getContents(TransitiveInfoCollection.class, "tools"),
-              ImmutableMap.copyOf(labelDictM));
+              ImmutableMap.copyOf(labelDict));
           String attribute = Type.STRING.convertOptional(attributeO, "attribute", ruleLabel);
           if (expandLocations) {
             command = helper.resolveCommandAndExpandLabels(
@@ -688,7 +689,7 @@
           List<Artifact> inputs = new ArrayList<>();
           inputs.addAll(helper.getResolvedTools());
           List<String> argv = helper.buildCommandLine(command, inputs, SCRIPT_SUFFIX);
-          return Tuple.<Object>of(
+          return Tuple.of(
               new MutableList(inputs, env),
               new MutableList(argv, env),
               helper.getRemoteRunfileManifestMap());
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/AbstractComprehension.java b/src/main/java/com/google/devtools/build/lib/syntax/AbstractComprehension.java
index b5680bf..9ceb880 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/AbstractComprehension.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/AbstractComprehension.java
@@ -315,7 +315,7 @@
 
   @Override
   Object doEval(Environment env) throws EvalException, InterruptedException {
-    OutputCollector collector = createCollector(env);
+    OutputCollector collector = createCollector();
     evalStep(env, collector, 0);
     return collector.getResult(env);
   }
@@ -375,7 +375,7 @@
    */
   abstract String printExpressions();
 
-  abstract OutputCollector createCollector(Environment env);
+  abstract OutputCollector createCollector();
 
   /**
    * Add byte code which initializes the collection and returns the variable it is saved in.
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 942bf92..0104a51 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
@@ -15,6 +15,7 @@
 
 import com.google.common.base.Joiner;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Ordering;
 import com.google.common.collect.Sets;
@@ -29,6 +30,7 @@
 import net.bytebuddy.implementation.bytecode.StackManipulation;
 
 import java.util.ArrayList;
+import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.Objects;
@@ -203,7 +205,7 @@
    */
   public Object[] processArguments(List<Object> args,
       @Nullable Map<String, Object> kwargs,
-      @Nullable Location loc, @Nullable Environment env)
+      @Nullable Location loc)
       throws EvalException {
 
     Object[] arguments = new Object[getArgArraySize()];
@@ -239,7 +241,7 @@
             Tuple.copyOf(args.subList(numPositionalParams, numPositionalArgs));
         numPositionalArgs = numPositionalParams; // clip numPositionalArgs
       } else {
-        arguments[starParamIndex] = Tuple.empty();
+        arguments[starParamIndex] = Tuple.EMPTY;
       }
     } else if (numPositionalArgs > numPositionalParams) {
       throw new EvalException(loc,
@@ -278,7 +280,7 @@
       // If there's a kwParam, it's empty.
       if (hasKwParam) {
         // TODO(bazel-team): create a fresh mutable dict, like Python does
-        arguments[kwParamIndex] = SkylarkDict.of(env);
+        arguments[kwParamIndex] = ImmutableMap.<String, Object>of();
       }
     } else if (hasKwParam && numNamedParams == 0) {
       // Easy case (2b): there are no named parameters, but there is a **kwParam.
@@ -286,12 +288,11 @@
       // Note that *starParam and **kwParam themselves don't count as named.
       // Also note that no named parameters means no mandatory parameters that weren't passed,
       // and no missing optional parameters for which to use a default. Thus, no loops.
-      // NB: not 2a means kwarg isn't null
-      arguments[kwParamIndex] = SkylarkDict.copyOf(env, kwargs);
+      // TODO(bazel-team): create a fresh mutable dict, like Python does
+      arguments[kwParamIndex] = kwargs; // NB: not 2a means kwarg isn't null
     } else {
       // Hard general case (2c): some keyword arguments may correspond to named parameters
-      SkylarkDict<String, Object> kwArg = hasKwParam
-          ? SkylarkDict.<String, Object>of(env) : SkylarkDict.<String, Object>empty();
+      HashMap<String, Object> kwArg = hasKwParam ? new HashMap<String, Object>() : null;
 
       // For nicer stabler error messages, start by checking against
       // an argument being provided both as positional argument and as keyword argument.
@@ -326,12 +327,12 @@
             throw new EvalException(loc, String.format(
                 "%s got multiple values for keyword argument '%s'", this, keyword));
           }
-          kwArg.put(keyword, value, loc, env);
+          kwArg.put(keyword, value);
         }
       }
       if (hasKwParam) {
         // TODO(bazel-team): create a fresh mutable dict, like Python does
-        arguments[kwParamIndex] = SkylarkDict.copyOf(env, kwArg);
+        arguments[kwParamIndex] = ImmutableMap.copyOf(kwArg);
       }
 
       // Check that all mandatory parameters were filled in general case 2c.
@@ -437,7 +438,7 @@
     // ast is null when called from Java (as there's no Skylark call site).
     Location loc = ast == null ? Location.BUILTIN : ast.getLocation();
 
-    Object[] arguments = processArguments(args, kwargs, loc, env);
+    Object[] arguments = processArguments(args, kwargs, loc);
     canonicalizeArguments(arguments, loc);
 
     return call(arguments, ast, env);
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 a31b037..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
@@ -16,6 +16,7 @@
 import static com.google.devtools.build.lib.syntax.compiler.ByteCodeUtils.append;
 
 import com.google.common.base.Strings;
+import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.syntax.ClassObject.SkylarkClassObject;
@@ -36,10 +37,13 @@
 import net.bytebuddy.implementation.bytecode.StackManipulation;
 
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.Collections;
 import java.util.EnumSet;
 import java.util.IllegalFormatException;
+import java.util.LinkedHashMap;
 import java.util.List;
+import java.util.Map;
 
 /**
  * Syntax node for a binary operator expression.
@@ -104,8 +108,10 @@
         }
       }
       return false;
-    } else if (rval instanceof SkylarkDict) {
-      return ((SkylarkDict<?, ?>) rval).containsKey(lval);
+    } else if (rval instanceof Collection<?>) {
+      return ((Collection<?>) rval).contains(lval);
+    } else if (rval instanceof Map<?, ?>) {
+      return ((Map<?, ?>) rval).containsKey(lval);
     } else if (rval instanceof SkylarkNestedSet) {
       return ((SkylarkNestedSet) rval).expandedSet().contains(lval);
     } else if (rval instanceof String) {
@@ -334,8 +340,13 @@
       return MutableList.concat((MutableList) lval, (MutableList) rval, env);
     }
 
-    if (lval instanceof SkylarkDict && rval instanceof SkylarkDict) {
-      return SkylarkDict.plus((SkylarkDict<?, ?>) lval, (SkylarkDict<?, ?>) rval, env);
+    if (lval instanceof Map<?, ?> && rval instanceof Map<?, ?>) {
+      Map<?, ?> ldict = (Map<?, ?>) lval;
+      Map<?, ?> rdict = (Map<?, ?>) rval;
+      Map<Object, Object> result = new LinkedHashMap<>(ldict.size() + rdict.size());
+      result.putAll(ldict);
+      result.putAll(rdict);
+      return ImmutableMap.copyOf(result);
     }
 
     if (lval instanceof SkylarkClassObject && rval instanceof SkylarkClassObject) {
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/DictComprehension.java b/src/main/java/com/google/devtools/build/lib/syntax/DictComprehension.java
index 349e8f5..c85cc23 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/DictComprehension.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/DictComprehension.java
@@ -25,8 +25,10 @@
 
 import net.bytebuddy.implementation.bytecode.ByteCodeAppender;
 import net.bytebuddy.implementation.bytecode.Duplication;
+import net.bytebuddy.implementation.bytecode.Removal;
 
 import java.util.ArrayList;
+import java.util.LinkedHashMap;
 import java.util.List;
 import java.util.Map;
 
@@ -49,14 +51,14 @@
   }
 
   @Override
-  OutputCollector createCollector(Environment env) {
-    return new DictOutputCollector(env);
+  OutputCollector createCollector() {
+    return new DictOutputCollector();
   }
 
   @Override
   InternalVariable compileInitialization(VariableScope scope, List<ByteCodeAppender> code) {
     InternalVariable dict = scope.freshVariable(ImmutableMap.class);
-    append(code, scope.loadEnvironment(), ByteCodeMethodCalls.BCSkylarkDict.of);
+    append(code, ByteCodeMethodCalls.BCImmutableMap.builder);
     code.add(dict.store());
     return dict;
   }
@@ -73,16 +75,14 @@
     code.add(keyExpression.compile(scope, debugInfo));
     append(code, Duplication.SINGLE, EvalUtils.checkValidDictKey);
     code.add(valueExpression.compile(scope, debugInfo));
-    append(code,
-        debugInfo.add(this).loadLocation,
-        scope.loadEnvironment(),
-        ByteCodeMethodCalls.BCSkylarkDict.put);
+    append(code, ByteCodeMethodCalls.BCImmutableMap.Builder.put, Removal.SINGLE);
     return ByteCodeUtils.compoundAppender(code);
   }
 
   @Override
   ByteCodeAppender compileBuilding(VariableScope scope, InternalVariable collection) {
-    return new ByteCodeAppender.Simple(collection.load());
+    return new ByteCodeAppender.Simple(
+        collection.load(), ByteCodeMethodCalls.BCImmutableMap.Builder.build);
   }
 
   /**
@@ -90,23 +90,23 @@
    * provides access to the resulting {@link Map}.
    */
   private final class DictOutputCollector implements OutputCollector {
-    private final SkylarkDict<Object, Object> result;
+    private final Map<Object, Object> result;
 
-    DictOutputCollector(Environment env) {
+    DictOutputCollector() {
       // We want to keep the iteration order
-      result = SkylarkDict.<Object, Object>of(env);
+      result = new LinkedHashMap<>();
     }
 
     @Override
     public void evaluateAndCollect(Environment env) throws EvalException, InterruptedException {
       Object key = keyExpression.eval(env);
       EvalUtils.checkValidDictKey(key);
-      result.put(key, valueExpression.eval(env), getLocation(), env);
+      result.put(key, valueExpression.eval(env));
     }
 
     @Override
     public Object getResult(Environment env) throws EvalException {
-      return result;
+      return ImmutableMap.copyOf(result);
     }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/DictionaryLiteral.java b/src/main/java/com/google/devtools/build/lib/syntax/DictionaryLiteral.java
index 3ab3126..8a223ed 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/DictionaryLiteral.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/DictionaryLiteral.java
@@ -16,7 +16,7 @@
 import static com.google.devtools.build.lib.syntax.compiler.ByteCodeUtils.append;
 
 import com.google.common.collect.ImmutableList;
-import com.google.devtools.build.lib.events.Location;
+import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.syntax.compiler.ByteCodeMethodCalls;
 import com.google.devtools.build.lib.syntax.compiler.ByteCodeUtils;
 import com.google.devtools.build.lib.syntax.compiler.DebugInfo;
@@ -26,7 +26,9 @@
 import net.bytebuddy.implementation.bytecode.Duplication;
 
 import java.util.ArrayList;
+import java.util.LinkedHashMap;
 import java.util.List;
+import java.util.Map;
 
 /**
  * Syntax node for dictionary literals.
@@ -79,17 +81,18 @@
 
   @Override
   Object doEval(Environment env) throws EvalException, InterruptedException {
-    SkylarkDict<Object, Object> dict = SkylarkDict.<Object, Object>of(env);
-    Location loc = getLocation();
+    // We need LinkedHashMap to maintain the order during iteration (e.g. for loops)
+    Map<Object, Object> map = new LinkedHashMap<>();
     for (DictionaryEntryLiteral entry : entries) {
       if (entry == null) {
-        throw new EvalException(loc, "null expression in " + this);
+        throw new EvalException(getLocation(), "null expression in " + this);
       }
       Object key = entry.key.eval(env);
+      EvalUtils.checkValidDictKey(key);
       Object val = entry.value.eval(env);
-      dict.put(key, val, loc, env);
+      map.put(key, val);
     }
-    return dict;
+    return ImmutableMap.copyOf(map);
   }
 
   @Override
@@ -126,18 +129,16 @@
   @Override
   ByteCodeAppender compile(VariableScope scope, DebugInfo debugInfo) throws EvalException {
     List<ByteCodeAppender> code = new ArrayList<>();
-    append(code, scope.loadEnvironment());
-    append(code, ByteCodeMethodCalls.BCSkylarkDict.of);
+    append(code, ByteCodeMethodCalls.BCImmutableMap.builder);
+
     for (DictionaryEntryLiteral entry : entries) {
-      append(code, Duplication.SINGLE); // duplicate the dict
       code.add(entry.key.compile(scope, debugInfo));
       append(code, Duplication.SINGLE, EvalUtils.checkValidDictKey);
       code.add(entry.value.compile(scope, debugInfo));
-      append(code,
-          debugInfo.add(this).loadLocation,
-          scope.loadEnvironment(),
-          ByteCodeMethodCalls.BCSkylarkDict.put);
+      // add it to the builder which is already on the stack and returns itself
+      append(code, ByteCodeMethodCalls.BCImmutableMap.Builder.put);
     }
+    append(code, ByteCodeMethodCalls.BCImmutableMap.Builder.build);
     return ByteCodeUtils.compoundAppender(code);
   }
 }
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 c462098..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
@@ -33,6 +33,7 @@
 import java.util.Collection;
 import java.util.List;
 import java.util.Map;
+import java.util.Set;
 
 /**
  * Utilities used by the evaluator.
@@ -82,21 +83,17 @@
       try {
         return ((Comparable<Object>) o1).compareTo(o2);
       } catch (ClassCastException e) {
-        return compareByClass(o1, o2);
+        try {
+          // Different types -> let the class names decide
+          return o1.getClass().getName().compareTo(o2.getClass().getName());
+        } catch (NullPointerException ex) {
+          throw new ComparisonException(
+              "Cannot compare " + getDataTypeName(o1) + " with " + EvalUtils.getDataTypeName(o2));
+        }
       }
     }
   };
 
-  public static final int compareByClass(Object o1, Object o2) {
-    try {
-      // Different types -> let the class names decide
-      return o1.getClass().getName().compareTo(o2.getClass().getName());
-    } catch (NullPointerException ex) {
-      throw new ComparisonException(
-          "Cannot compare " + getDataTypeName(o1) + " with " + EvalUtils.getDataTypeName(o2));
-    }
-  }
-
   public static final StackManipulation checkValidDictKey =
       ByteCodeUtils.invoke(EvalUtils.class, "checkValidDictKey", Object.class);
 
@@ -208,25 +205,30 @@
    * @return a super-class of c to be used in validation-time type inference.
    */
   public static Class<?> getSkylarkType(Class<?> c) {
-    // TODO(bazel-team): replace these with SkylarkValue-s
-    if (String.class.equals(c)
-        || Boolean.class.equals(c)
-        || Integer.class.equals(c)
-        || Iterable.class.equals(c)
-        || Class.class.equals(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;
+    } else if (Map.class.isAssignableFrom(c)) {
+      return Map.class;
+    } else if (NestedSet.class.isAssignableFrom(c)) {
+      // This could be removed probably
+      return NestedSet.class;
+    } else if (Set.class.isAssignableFrom(c)) {
+      return Set.class;
+    } else {
+      // TODO(bazel-team): also unify all implementations of ClassObject,
+      // that we used to all print the same as "struct"?
+      //
+      // Check if one of the superclasses or implemented interfaces has the SkylarkModule
+      // annotation. If yes return that class.
+      Class<?> parent = getParentWithSkylarkModule(c);
+      if (parent != null) {
+        return parent;
+      }
     }
-    // TODO(bazel-team): also unify all implementations of ClassObject,
-    // that we used to all print the same as "struct"?
-    //
-    // Check if one of the superclasses or implemented interfaces has the SkylarkModule
-    // annotation. If yes return that class.
-    Class<?> parent = getParentWithSkylarkModule(c);
-    if (parent != null) {
-      return parent;
-    }
-    Preconditions.checkArgument(SkylarkValue.class.isAssignableFrom(c),
-        "%s is not allowed as a Skylark value", c);
     return c;
   }
 
@@ -281,10 +283,8 @@
       return "int";
     } else if (c.equals(Boolean.class)) {
       return "bool";
-    } else if (List.class.isAssignableFrom(c)) { // This is a Java List that isn't a SkylarkList
-      return "List"; // This case shouldn't happen in normal code, but we keep it for debugging.
-    } else if (Map.class.isAssignableFrom(c)) { // This is a Java Map that isn't a SkylarkDict
-      return "Map"; // This case shouldn't happen in normal code, but we keep it for debugging.
+    } else if (Map.class.isAssignableFrom(c)) {
+      return "dict";
     } else if (BaseFunction.class.isAssignableFrom(c)) {
       return "function";
     } else if (c.equals(SelectorValue.class)) {
@@ -416,9 +416,8 @@
   }
 
   /**
-   * Build a SkylarkDict of kwarg arguments from a list, removing null-s or None-s.
+   * Build a map of kwarg arguments from a list, removing null-s or None-s.
    *
-   * @param env the Environment in which this map can be mutated.
    * @param init a series of key, value pairs (as consecutive arguments)
    *   as in {@code optionMap(k1, v1, k2, v2, k3, v3)}
    *   where each key is a String, each value is an arbitrary Objet.
@@ -430,16 +429,16 @@
    * Keys cannot be null.
    */
   @SuppressWarnings("unchecked")
-  public static <K, V> SkylarkDict<K, V> optionMap(Environment env, Object... init) {
-    ImmutableMap.Builder<K, V> b = new ImmutableMap.Builder<>();
+  public static ImmutableMap<String, Object> optionMap(Object... init) {
+    ImmutableMap.Builder<String, Object> b = new ImmutableMap.Builder<>();
     Preconditions.checkState(init.length % 2 == 0);
     for (int i = init.length - 2; i >= 0; i -= 2) {
-      K key = (K) Preconditions.checkNotNull(init[i]);
-      V value = (V) init[i + 1];
+      String key = (String) Preconditions.checkNotNull(init[i]);
+      Object value = init[i + 1];
       if (!isNullOrNone(value)) {
         b.put(key, value);
       }
     }
-    return SkylarkDict.<K, V>copyOf(env, b.build());
+    return b.build();
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/FunctionSignature.java b/src/main/java/com/google/devtools/build/lib/syntax/FunctionSignature.java
index b858d35..0296326 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/FunctionSignature.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/FunctionSignature.java
@@ -27,6 +27,7 @@
 import java.util.Arrays;
 import java.util.HashSet;
 import java.util.List;
+import java.util.Map;
 import java.util.Set;
 
 import javax.annotation.Nullable;
@@ -149,7 +150,7 @@
         parameters.add(Tuple.class);
       }
       if (hasKwArg()) {
-        parameters.add(SkylarkDict.class);
+        parameters.add(Map.class);
       }
 
       return parameters;
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/LValue.java b/src/main/java/com/google/devtools/build/lib/syntax/LValue.java
index 729dd0c..1f031d9 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/LValue.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/LValue.java
@@ -16,6 +16,7 @@
 
 import static com.google.devtools.build.lib.syntax.compiler.ByteCodeUtils.append;
 
+import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.syntax.compiler.ByteCodeUtils;
 import com.google.devtools.build.lib.syntax.compiler.DebugInfo.AstAccessors;
@@ -31,7 +32,9 @@
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Iterator;
+import java.util.LinkedHashMap;
 import java.util.List;
+import java.util.Map;
 
 /**
  * Class representing an LValue.
@@ -103,20 +106,23 @@
 
   // Since dict is still immutable, the expression 'a[x] = b' creates a new dictionary and
   // assigns it to 'a'.
-  @SuppressWarnings("unchecked")
+  // TODO(bazel-team): make dict mutable - this function should be O(1) instead of O(n).
   private static void assignItem(
       Environment env, Location loc, Identifier ident, Object key, Object value)
       throws EvalException, InterruptedException {
     Object o = ident.eval(env);
-    if (!(o instanceof SkylarkDict)) {
+    if (!(o instanceof Map)) {
       throw new EvalException(
           loc,
           "can only assign an element in a dictionary, not in a '"
               + EvalUtils.getDataTypeName(o)
               + "'");
     }
-    SkylarkDict<Object, Object> dict = (SkylarkDict<Object, Object>) o;
-    dict.put(key, value, loc, env);
+    Map<?, ?> dict = (Map<?, ?>) o;
+    Map<Object, Object> result = new LinkedHashMap<>(dict.size() + 1);
+    result.putAll(dict);
+    result.put(key, value);
+    env.update(ident.getName(), ImmutableMap.copyOf(result));
   }
 
   /**
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 cfcbe12..749b056 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
@@ -48,7 +48,7 @@
   }
 
   @Override
-  OutputCollector createCollector(Environment env) {
+  OutputCollector createCollector() {
     return new ListOutputCollector();
   }
 
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 52231c9..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
@@ -35,11 +35,13 @@
 import java.util.ArrayList;
 import java.util.Comparator;
 import java.util.Iterator;
+import java.util.LinkedHashMap;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
 import java.util.NoSuchElementException;
 import java.util.Set;
+import java.util.TreeMap;
 import java.util.TreeSet;
 import java.util.concurrent.ExecutionException;
 import java.util.regex.Matcher;
@@ -105,7 +107,7 @@
         @Param(name = "self", type = String.class, doc = "This string, a separator."),
         @Param(name = "elements", type = SkylarkList.class, doc = "The objects to join.")})
   private static BuiltinFunction join = new BuiltinFunction("join") {
-    public String invoke(String self, SkylarkList<?> elements) throws ConversionException {
+    public String invoke(String self, SkylarkList elements) throws ConversionException {
       return Joiner.on(self).join(elements);
     }
   };
@@ -281,13 +283,13 @@
       useEnvironment = true,
       useLocation = true)
   private static BuiltinFunction split = new BuiltinFunction("split") {
-    public MutableList<String> invoke(String self, String sep, Object maxSplitO, Location loc,
+    public MutableList invoke(String self, String sep, Object maxSplitO, Location loc,
         Environment env) throws ConversionException, EvalException {
       int maxSplit = Type.INTEGER.convertOptional(
           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 MutableList.of(env, ss);
+      return MutableList.of(env, (Object[]) ss);
     }
   };
 
@@ -306,11 +308,13 @@
       useLocation = true)
   private static BuiltinFunction rsplit = new BuiltinFunction("rsplit") {
     @SuppressWarnings("unused")
-    public MutableList<String> invoke(
+    public MutableList invoke(
         String self, String sep, Object maxSplitO, Location loc, Environment env)
         throws ConversionException, EvalException {
       int maxSplit =
           Type.INTEGER.convertOptional(maxSplitO, "'split' argument of 'split'", null, -1);
+      List<String> result;
+
       try {
         return stringRSplit(self, sep, maxSplit, env);
       } catch (IllegalArgumentException ex) {
@@ -331,7 +335,7 @@
    * @return A list of words
    * @throws IllegalArgumentException
    */
-  private static MutableList<String> stringRSplit(
+  private static MutableList stringRSplit(
       String input, String separator, int maxSplits, Environment env)
       throws IllegalArgumentException {
     if (separator.isEmpty()) {
@@ -381,7 +385,7 @@
       useLocation = true)
   private static BuiltinFunction partition = new BuiltinFunction("partition") {
     @SuppressWarnings("unused")
-    public MutableList<String> invoke(String self, String sep, Location loc, Environment env)
+    public MutableList invoke(String self, String sep, Location loc, Environment env)
         throws EvalException {
       return partitionWrapper(self, sep, true, env, loc);
     }
@@ -401,7 +405,7 @@
       useLocation = true)
   private static BuiltinFunction rpartition = new BuiltinFunction("rpartition") {
     @SuppressWarnings("unused")
-    public MutableList<String> invoke(String self, String sep, Location loc, Environment env)
+    public MutableList invoke(String self, String sep, Location loc, Environment env)
         throws EvalException {
       return partitionWrapper(self, sep, false, env, loc);
     }
@@ -419,8 +423,7 @@
    * @param loc The location that is used for potential exceptions
    * @return A list with three elements
    */
-  private static MutableList<String> partitionWrapper(
-      String self, String separator, boolean forward,
+  private static MutableList partitionWrapper(String self, String separator, boolean forward,
       Environment env, Location loc) throws EvalException {
     try {
       return new MutableList(stringPartition(self, separator, forward), env);
@@ -649,7 +652,7 @@
               doc = "Whether the line breaks should be included in the resulting list.")})
   private static BuiltinFunction splitLines = new BuiltinFunction("splitlines") {
     @SuppressWarnings("unused")
-    public MutableList<String> invoke(String self, Boolean keepEnds) throws EvalException {
+    public MutableList invoke(String self, Boolean keepEnds) throws EvalException {
       List<String> result = new ArrayList<>();
       Matcher matcher = SPLIT_LINES_PATTERN.matcher(self);
       while (matcher.find()) {
@@ -887,16 +890,13 @@
           @Param(name = "args", type = SkylarkList.class, defaultValue = "()",
               doc = "List of arguments"),
       },
-      extraKeywords = {@Param(name = "kwargs", type = SkylarkDict.class, defaultValue = "{}",
-            doc = "Dictionary of arguments")},
+      extraKeywords = {@Param(name = "kwargs", doc = "Dictionary of arguments")},
       useLocation = true)
   private static BuiltinFunction format = new BuiltinFunction("format") {
     @SuppressWarnings("unused")
-    public String invoke(String self, SkylarkList<Object> args, SkylarkDict<?, ?> kwargs,
-        Location loc)
+    public String invoke(String self, SkylarkList args, Map<String, Object> kwargs, Location loc)
         throws ConversionException, EvalException {
-      return new FormatParser(loc).format(
-          self, args.getImmutableList(), kwargs.getContents(String.class, Object.class, "kwargs"));
+      return new FormatParser(loc).format(self, args.getImmutableList(), kwargs);
     }
   };
 
@@ -977,8 +977,8 @@
   private static BuiltinFunction mutableListSlice =
       new BuiltinFunction("$slice") {
         @SuppressWarnings("unused") // Accessed via Reflection.
-        public MutableList<Object> invoke(
-            MutableList<Object> self, Object start, Object end, Integer step, Location loc,
+        public MutableList invoke(
+            MutableList self, Object start, Object end, Integer step, Location loc,
             Environment env)
             throws EvalException, ConversionException {
           return new MutableList(sliceList(self, start, end, step, loc), env);
@@ -1006,8 +1006,7 @@
   private static BuiltinFunction tupleSlice =
       new BuiltinFunction("$slice") {
         @SuppressWarnings("unused") // Accessed via Reflection.
-        public Tuple<Object> invoke(
-            Tuple<Object> self, Object start, Object end, Integer step, Location loc)
+        public Tuple invoke(Tuple self, Object start, Object end, Integer step, Location loc)
             throws EvalException, ConversionException {
           return Tuple.copyOf(sliceList(self, start, end, step, loc));
         }
@@ -1093,7 +1092,7 @@
   )
   private static BuiltinFunction min = new BuiltinFunction("min") {
     @SuppressWarnings("unused") // Accessed via Reflection.
-    public Object invoke(SkylarkList<?> args, Location loc) throws EvalException {
+    public Object invoke(SkylarkList args, Location loc) throws EvalException {
       return findExtreme(args, EvalUtils.SKYLARK_COMPARATOR.reverse(), loc);
     }
   };
@@ -1111,7 +1110,7 @@
   )
   private static BuiltinFunction max = new BuiltinFunction("max") {
     @SuppressWarnings("unused") // Accessed via Reflection.
-    public Object invoke(SkylarkList<?> args, Location loc) throws EvalException {
+    public Object invoke(SkylarkList args, Location loc) throws EvalException {
       return findExtreme(args, EvalUtils.SKYLARK_COMPARATOR, loc);
     }
   };
@@ -1119,7 +1118,7 @@
   /**
    * Returns the maximum element from this list, as determined by maxOrdering.
    */
-  private static Object findExtreme(SkylarkList<?> args, Ordering<Object> maxOrdering, Location loc)
+  private static Object findExtreme(SkylarkList args, Ordering<Object> maxOrdering, Location loc)
       throws EvalException {
     // Args can either be a list of elements or a list whose first element is a non-empty iterable
     // of elements.
@@ -1134,7 +1133,7 @@
    * This method returns the first element of the list, if that particular element is an
    * Iterable<?>. Otherwise, it will return the entire list.
    */
-  private static Iterable<?> getIterable(SkylarkList<?> list, Location loc) throws EvalException {
+  private static Iterable<?> getIterable(SkylarkList list, Location loc) throws EvalException {
     return (list.size() == 1) ? EvalUtils.toIterable(list.get(0), loc) : list;
   }
 
@@ -1196,7 +1195,7 @@
   )
   private static BuiltinFunction sorted =
       new BuiltinFunction("sorted") {
-        public <E> MutableList<E> invoke(Object self, Location loc, Environment env)
+        public MutableList invoke(Object self, Location loc, Environment env)
             throws EvalException, ConversionException {
           try {
             return new MutableList(
@@ -1225,10 +1224,10 @@
   private static BuiltinFunction reversed =
       new BuiltinFunction("reversed") {
         @SuppressWarnings("unused") // Accessed via Reflection.
-        public MutableList<?> invoke(Object sequence, Location loc, Environment env)
+        public MutableList invoke(Object sequence, Location loc, Environment env)
             throws EvalException {
           // We only allow lists and strings.
-          if (sequence instanceof SkylarkDict) {
+          if (sequence instanceof Map) {
             throw new EvalException(
                 loc, "Argument to reversed() must be a sequence, not a dictionary.");
           } else if (sequence instanceof NestedSet || sequence instanceof SkylarkNestedSet) {
@@ -1255,7 +1254,7 @@
     useEnvironment = true)
   private static BuiltinFunction append =
       new BuiltinFunction("append") {
-        public Runtime.NoneType invoke(MutableList<Object> self, Object item,
+        public Runtime.NoneType invoke(MutableList self, Object item,
             Location loc, Environment env) throws EvalException, ConversionException {
           self.add(item, loc, env);
           return Runtime.NONE;
@@ -1274,7 +1273,7 @@
     useEnvironment = true)
   private static BuiltinFunction extend =
       new BuiltinFunction("extend") {
-        public Runtime.NoneType invoke(MutableList<Object> self, SkylarkList<Object> items,
+        public Runtime.NoneType invoke(MutableList self, SkylarkList items,
             Location loc, Environment env) throws EvalException, ConversionException {
           self.addAll(items, loc, env);
           return Runtime.NONE;
@@ -1296,7 +1295,7 @@
   )
   private static BuiltinFunction listIndex =
       new BuiltinFunction("index") {
-        public Integer invoke(MutableList<?> self, Object x, Location loc) throws EvalException {
+        public Integer invoke(MutableList self, Object x, Location loc) throws EvalException {
           int i = 0;
           for (Object obj : self) {
             if (obj.equals(x)) {
@@ -1324,7 +1323,7 @@
   )
   private static BuiltinFunction listRemove =
       new BuiltinFunction("remove") {
-        public Runtime.NoneType invoke(MutableList<?> self, Object x, Location loc, Environment env)
+        public Runtime.NoneType invoke(MutableList self, Object x, Location loc, Environment env)
             throws EvalException {
           for (int i = 0; i < self.size(); i++) {
             if (self.get(i).equals(x)) {
@@ -1360,7 +1359,7 @@
   )
   private static BuiltinFunction listPop =
       new BuiltinFunction("pop") {
-        public Object invoke(MutableList<?> self, Object i, Location loc, Environment env)
+        public Object invoke(MutableList self, Object i, Location loc, Environment env)
             throws EvalException {
           int arg = i == Runtime.NONE ? -1 : (Integer) i;
           int index = getListIndex(arg, self.size(), loc);
@@ -1371,14 +1370,14 @@
       };
 
   // dictionary access operator
-  @SkylarkSignature(name = "$index", documented = false, objectType = SkylarkDict.class,
+  @SkylarkSignature(name = "$index", documented = false, objectType = Map.class,
       doc = "Looks up a value in a dictionary.",
       mandatoryPositionals = {
-        @Param(name = "self", type = SkylarkDict.class, doc = "This object."),
+        @Param(name = "self", type = Map.class, doc = "This object."),
         @Param(name = "key", type = Object.class, doc = "The index or key to access.")},
       useLocation = true, useEnvironment = true)
   private static BuiltinFunction dictIndexOperator = new BuiltinFunction("$index") {
-      public Object invoke(SkylarkDict<?, ?> self, Object key,
+    public Object invoke(Map<?, ?> self, Object key,
         Location loc, Environment env) throws EvalException, ConversionException {
       if (!self.containsKey(key)) {
         throw new EvalException(loc, Printer.format("Key %r not found in dictionary", key));
@@ -1402,7 +1401,7 @@
   )
   private static BuiltinFunction listIndexOperator =
       new BuiltinFunction("$index") {
-        public Object invoke(MutableList<?> self, Integer key, Location loc, Environment env)
+        public Object invoke(MutableList self, Integer key, Location loc, Environment env)
             throws EvalException, ConversionException {
           if (self.isEmpty()) {
             throw new EvalException(loc, "List is empty");
@@ -1427,7 +1426,7 @@
   )
   private static BuiltinFunction tupleIndexOperator =
       new BuiltinFunction("$index") {
-        public Object invoke(Tuple<?> self, Integer key, Location loc, Environment env)
+        public Object invoke(Tuple self, Integer key, Location loc, Environment env)
             throws EvalException, ConversionException {
           if (self.isEmpty()) {
             throw new EvalException(loc, "tuple is empty");
@@ -1457,61 +1456,62 @@
         }
       };
 
-  @SkylarkSignature(name = "values", objectType = SkylarkDict.class,
+  @SkylarkSignature(name = "values", objectType = Map.class,
       returnType = MutableList.class,
       doc = "Returns the list of values. Dictionaries are always sorted by their keys:"
           + "<pre class=\"language-python\">"
           + "{2: \"a\", 4: \"b\", 1: \"c\"}.values() == [\"c\", \"a\", \"b\"]</pre>\n",
-      mandatoryPositionals = {@Param(name = "self", type = SkylarkDict.class, doc = "This dict.")},
+      mandatoryPositionals = {@Param(name = "self", type = Map.class, doc = "This dict.")},
       useEnvironment = true)
   private static BuiltinFunction values = new BuiltinFunction("values") {
-    public MutableList<?> invoke(SkylarkDict<?, ?> self,
+    public MutableList invoke(Map<?, ?> self,
         Environment env) throws EvalException, ConversionException {
-      return new MutableList(self.values(), env);
+      // Use a TreeMap to ensure consistent ordering.
+      Map<?, ?> dict = new TreeMap<>(self);
+      return new MutableList(dict.values(), env);
     }
   };
 
-  @SkylarkSignature(name = "items", objectType = SkylarkDict.class,
+  @SkylarkSignature(name = "items", objectType = Map.class,
       returnType = MutableList.class,
       doc = "Returns the list of key-value tuples. Dictionaries are always sorted by their keys:"
           + "<pre class=\"language-python\">"
           + "{2: \"a\", 4: \"b\", 1: \"c\"}.items() == [(1, \"c\"), (2, \"a\"), (4, \"b\")]"
           + "</pre>\n",
       mandatoryPositionals = {
-        @Param(name = "self", type = SkylarkDict.class, doc = "This dict.")},
+        @Param(name = "self", type = Map.class, doc = "This dict.")},
       useEnvironment = true)
   private static BuiltinFunction items = new BuiltinFunction("items") {
-    public MutableList<?> invoke(SkylarkDict<?, ?> self,
+    public MutableList invoke(Map<?, ?> self,
         Environment env) throws EvalException, ConversionException {
-      List<Object> list = Lists.newArrayListWithCapacity(self.size());
-      for (Map.Entry<?, ?> entries : self.entrySet()) {
+      // Use a TreeMap to ensure consistent ordering.
+      Map<?, ?> dict = new TreeMap<>(self);
+      List<Object> list = Lists.newArrayListWithCapacity(dict.size());
+      for (Map.Entry<?, ?> entries : dict.entrySet()) {
         list.add(Tuple.of(entries.getKey(), entries.getValue()));
       }
       return new MutableList(list, env);
     }
   };
 
-  @SkylarkSignature(name = "keys", objectType = SkylarkDict.class,
+  @SkylarkSignature(name = "keys", objectType = Map.class,
       returnType = MutableList.class,
       doc = "Returns the list of keys. Dictionaries are always sorted by their keys:"
           + "<pre class=\"language-python\">{2: \"a\", 4: \"b\", 1: \"c\"}.keys() == [1, 2, 4]"
           + "</pre>\n",
       mandatoryPositionals = {
-        @Param(name = "self", type = SkylarkDict.class, doc = "This dict.")},
+        @Param(name = "self", type = Map.class, doc = "This dict.")},
       useEnvironment = true)
+  // Skylark will only call this on a dict; and
+  // allowed keys are all Comparable... if not mutually, it's OK to get a runtime exception.
   private static BuiltinFunction keys = new BuiltinFunction("keys") {
-    // Skylark will only call this on a dict; and
-    // allowed keys are all Comparable... if not mutually, it's OK to get a runtime exception.
-    @SuppressWarnings("unchecked")
-    public MutableList<?> invoke(SkylarkDict<?, ?> self,
+    public MutableList invoke(Map<Comparable<?>, ?> dict,
         Environment env) throws EvalException {
-      return new MutableList(
-          Ordering.natural().sortedCopy((Set<Comparable<?>>) (Set<?>) self.keySet()),
-          env);
+      return new MutableList(Ordering.natural().sortedCopy(dict.keySet()), env);
     }
   };
 
-  @SkylarkSignature(name = "get", objectType = SkylarkDict.class,
+  @SkylarkSignature(name = "get", objectType = Map.class,
       doc = "Returns the value for <code>key</code> if <code>key</code> is in the dictionary, "
           + "else <code>default</code>. If <code>default</code> is not given, it defaults to "
           + "<code>None</code>, so that this method never throws an error.",
@@ -1522,7 +1522,7 @@
         @Param(name = "default", defaultValue = "None",
             doc = "The default value to use (instead of None) if the key is not found.")})
   private static BuiltinFunction get = new BuiltinFunction("get") {
-    public Object invoke(SkylarkDict<?, ?> self, Object key, Object defaultValue) {
+    public Object invoke(Map<?, ?> self, Object key, Object defaultValue) {
       if (self.containsKey(key)) {
         return self.get(key);
       }
@@ -1555,7 +1555,7 @@
       mandatoryPositionals = {@Param(name = "x", doc = "The object to convert.")},
       useLocation = true, useEnvironment = true)
   private static BuiltinFunction list = new BuiltinFunction("list") {
-    public MutableList<?> invoke(Object x, Location loc, Environment env) throws EvalException {
+    public MutableList invoke(Object x, Location loc, Environment env) throws EvalException {
       return new MutableList(EvalUtils.toCollection(x, loc), env);
     }
   };
@@ -1646,8 +1646,8 @@
         @Param(name = "kwargs", doc = "the struct attributes")},
       useLocation = true)
   private static BuiltinFunction struct = new BuiltinFunction("struct") {
-    @SuppressWarnings("unchecked")
-    public SkylarkClassObject invoke(SkylarkDict<String, Object> kwargs, Location loc)
+      @SuppressWarnings("unchecked")
+    public SkylarkClassObject invoke(Map<String, Object> kwargs, Location loc)
         throws EvalException {
       return new SkylarkClassObject(kwargs, loc);
     }
@@ -1684,7 +1684,7 @@
 
   @SkylarkSignature(
     name = "dict",
-    returnType = SkylarkDict.class,
+    returnType = Map.class,
     doc =
         "Creates a <a href=\"#modules.dict\">dictionary</a> from an optional positional "
             + "argument and an optional set of keyword arguments. Values from the keyword argument "
@@ -1701,26 +1701,28 @@
       ),
     },
     extraKeywords = {@Param(name = "kwargs", doc = "Dictionary of additional entries.")},
-    useLocation = true, useEnvironment = true
+    useLocation = true
   )
   private static final BuiltinFunction dict =
       new BuiltinFunction("dict") {
-        public SkylarkDict invoke(Object args, SkylarkDict<String, Object> kwargs,
-            Location loc, Environment env)
+        @SuppressWarnings("unused")
+        public Map<Object, Object> invoke(Object args, Map<Object, Object> kwargs, Location loc)
             throws EvalException {
-          SkylarkDict<Object, Object> argsDict = (args instanceof SkylarkDict)
-              ? (SkylarkDict<Object, Object>) args : getDictFromArgs(args, loc, env);
-          return SkylarkDict.plus(argsDict, kwargs, env);
+          Map<Object, Object> result =
+              (args instanceof Map<?, ?>)
+                  // Do not remove <Object, Object>: workaround for Java 7 type inference.
+                  ? new LinkedHashMap<Object, Object>((Map<?, ?>) args)
+                  : getMapFromArgs(args, loc);
+          result.putAll(kwargs);
+          return result;
         }
 
-        private SkylarkDict<Object, Object> getDictFromArgs(
-            Object args, Location loc, Environment env)
-            throws EvalException {
-          SkylarkDict<Object, Object> result = SkylarkDict.of(env);
+        private Map<Object, Object> getMapFromArgs(Object args, Location loc) throws EvalException {
+          Map<Object, Object> result = new LinkedHashMap<>();
           int pos = 0;
           for (Object element : Type.OBJECT_LIST.convert(args, "parameter args in dict()")) {
             List<Object> pair = convertToPair(element, pos, loc);
-            result.put(pair.get(0), pair.get(1), loc, env);
+            result.put(pair.get(0), pair.get(1));
             ++pos;
           }
           return result;
@@ -1755,7 +1757,7 @@
           + "the input set as well as all additional elements.",
       mandatoryPositionals = {
         @Param(name = "input", type = SkylarkNestedSet.class, doc = "The input set"),
-        @Param(name = "new_elements", type = Iterable.class, doc = "The elements to be added")},
+        @Param(name = "newElements", type = Iterable.class, doc = "The elements to be added")},
       useLocation = true)
   private static final BuiltinFunction union = new BuiltinFunction("union") {
     @SuppressWarnings("unused")
@@ -1774,10 +1776,10 @@
       },
       useEnvironment = true)
   private static BuiltinFunction enumerate = new BuiltinFunction("enumerate") {
-    public MutableList<?> invoke(SkylarkList<?> input, Environment env)
+    public MutableList invoke(SkylarkList input, Environment env)
         throws EvalException, ConversionException {
       int count = 0;
-      List<SkylarkList<?>> result = Lists.newArrayList();
+      List<SkylarkList> result = Lists.newArrayList();
       for (Object obj : input) {
         result.add(Tuple.of(count, obj));
         count++;
@@ -1807,7 +1809,7 @@
       useLocation = true,
       useEnvironment = true)
   private static final BuiltinFunction range = new BuiltinFunction("range") {
-      public MutableList<?> invoke(Integer startOrStop, Object stopOrNone, Integer step,
+      public MutableList invoke(Integer startOrStop, Object stopOrNone, Integer step,
           Location loc, Environment env)
         throws EvalException, ConversionException {
       int start;
@@ -1845,9 +1847,9 @@
   @SkylarkSignature(name = "select",
       doc = "Creates a SelectorValue from the dict parameter.",
       mandatoryPositionals = {
-        @Param(name = "x", type = SkylarkDict.class, doc = "The parameter to convert.")})
+        @Param(name = "x", type = Map.class, doc = "The parameter to convert.")})
   private static final BuiltinFunction select = new BuiltinFunction("select") {
-    public Object invoke(SkylarkDict<?, ?> dict) throws EvalException {
+    public Object invoke(Map<?, ?> dict) throws EvalException {
       return SelectorList
           .of(new SelectorValue(dict));
     }
@@ -1919,7 +1921,7 @@
       mandatoryPositionals = {@Param(name = "x", doc = "The object to check.")},
       useLocation = true, useEnvironment = true)
   private static final BuiltinFunction dir = new BuiltinFunction("dir") {
-    public MutableList<?> invoke(Object object,
+    public MutableList invoke(Object object,
         Location loc, Environment env) throws EvalException, ConversionException {
       // Order the fields alphabetically.
       Set<String> fields = new TreeSet<>();
@@ -1980,7 +1982,7 @@
       extraPositionals = {@Param(name = "args", doc = "The objects to print.")},
       useLocation = true, useEnvironment = true)
   private static final BuiltinFunction print = new BuiltinFunction("print") {
-    public Runtime.NoneType invoke(String sep, SkylarkList<?> starargs,
+    public Runtime.NoneType invoke(String sep, SkylarkList starargs,
         Location loc, Environment env) throws EvalException {
       String msg = Joiner.on(sep).join(Iterables.transform(starargs,
               new com.google.common.base.Function<Object, String>() {
@@ -2006,13 +2008,13 @@
       extraPositionals = {@Param(name = "args", doc = "lists to zip")},
       returnType = MutableList.class, useLocation = true, useEnvironment = true)
   private static final BuiltinFunction zip = new BuiltinFunction("zip") {
-    public MutableList<?> invoke(SkylarkList<?> args, Location loc, Environment env)
+    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<Tuple<?>> result = new ArrayList<>();
+      List<Tuple> result = new ArrayList<>();
       boolean allHasNext;
       do {
         allHasNext = !args.isEmpty();
@@ -2059,6 +2061,29 @@
   )
   static final class StringModule {}
 
+  /**
+   * Skylark Dict module.
+   */
+  @SkylarkModule(name = "dict", doc =
+      "A language built-in type to support dicts. "
+      + "Example of dict literal:<br>"
+      + "<pre class=\"language-python\">d = {\"a\": 2, \"b\": 5}</pre>"
+      + "Use brackets to access elements:<br>"
+      + "<pre class=\"language-python\">e = d[\"a\"]   # e == 2</pre>"
+      + "Dicts support the <code>+</code> operator to concatenate two dicts. In case of multiple "
+      + "keys the second one overrides the first one. Examples:<br>"
+      + "<pre class=\"language-python\">"
+      + "d = {\"a\" : 1} + {\"b\" : 2}   # d == {\"a\" : 1, \"b\" : 2}\n"
+      + "d += {\"c\" : 3}              # d == {\"a\" : 1, \"b\" : 2, \"c\" : 3}\n"
+      + "d = d + {\"c\" : 5}           # d == {\"a\" : 1, \"b\" : 2, \"c\" : 5}</pre>"
+      + "Since the language doesn't have mutable objects <code>d[\"a\"] = 5</code> automatically "
+      + "translates to <code>d = d + {\"a\" : 5}</code>.<br>"
+      + "Iterating on a dict is equivalent to iterating on its keys (in sorted order).<br>"
+      + "Dicts support the <code>in</code> operator, testing membership in the keyset of the dict. "
+      + "Example:<br>"
+      + "<pre class=\"language-python\">\"a\" in {\"a\" : 2, \"b\" : 5}   # evaluates as True"
+      + "</pre>")
+  static final class DictModule {}
 
   static final List<BaseFunction> buildGlobalFunctions =
       ImmutableList.<BaseFunction>of(
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 f4b55ad..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
@@ -26,6 +26,7 @@
 
 import java.lang.reflect.Field;
 import java.util.HashMap;
+import java.util.List;
 import java.util.Map;
 import java.util.Set;
 
@@ -119,15 +120,20 @@
    */
   public static void registerFunction(Class<?> nameSpace, BaseFunction function) {
     Preconditions.checkNotNull(nameSpace);
-    Preconditions.checkArgument(nameSpace.equals(getCanonicalRepresentation(nameSpace)));
-    Preconditions.checkArgument(
-        getCanonicalRepresentation(function.getObjectType()).equals(nameSpace));
+    // TODO(bazel-team): fix our code so that the two checks below work.
+    // Preconditions.checkArgument(function.getObjectType().equals(nameSpace));
+    // Preconditions.checkArgument(nameSpace.equals(getCanonicalRepresentation(nameSpace)));
+    nameSpace = getCanonicalRepresentation(nameSpace);
     if (!functions.containsKey(nameSpace)) {
       functions.put(nameSpace, new HashMap<String, BaseFunction>());
     }
     functions.get(nameSpace).put(function.getName(), function);
   }
 
+  static Map<String, BaseFunction> getNamespaceFunctions(Class<?> nameSpace) {
+    return functions.get(getCanonicalRepresentation(nameSpace));
+  }
+
   /**
    * Returns the canonical representation of the given class, i.e. the super class for which any
    * functions were registered.
@@ -137,15 +143,18 @@
    */
   // 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;
     }
-    return EvalUtils.getSkylarkType(clazz);
-  }
-
-
-  static Map<String, BaseFunction> getNamespaceFunctions(Class<?> nameSpace) {
-    return functions.get(getCanonicalRepresentation(nameSpace));
+    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/SkylarkDict.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkDict.java
deleted file mode 100644
index 3a856b2..0000000
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkDict.java
+++ /dev/null
@@ -1,203 +0,0 @@
-// 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.common.collect.ImmutableMap;
-import com.google.devtools.build.lib.events.Location;
-import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
-import com.google.devtools.build.lib.syntax.SkylarkMutable.MutableMap;
-
-import java.util.Map;
-import java.util.TreeMap;
-
-import javax.annotation.Nullable;
-
-/**
- * Skylark Dict module.
- */
-@SkylarkModule(name = "dict", doc =
-    "A language built-in type to support dicts. "
-    + "Example of dict literal:<br>"
-    + "<pre class=\"language-python\">d = {\"a\": 2, \"b\": 5}</pre>"
-    + "Use brackets to access elements:<br>"
-    + "<pre class=\"language-python\">e = d[\"a\"]   # e == 2</pre>"
-    + "Dicts support the <code>+</code> operator to concatenate two dicts. In case of multiple "
-    + "keys the second one overrides the first one. Examples:<br>"
-    + "<pre class=\"language-python\">"
-    + "d = {\"a\" : 1} + {\"b\" : 2}   # d == {\"a\" : 1, \"b\" : 2}\n"
-    + "d += {\"c\" : 3}              # d == {\"a\" : 1, \"b\" : 2, \"c\" : 3}\n"
-    + "d = d + {\"c\" : 5}           # d == {\"a\" : 1, \"b\" : 2, \"c\" : 5}</pre>"
-    + "Iterating on a dict is equivalent to iterating on its keys (in sorted order).<br>"
-    + "Dicts support the <code>in</code> operator, testing membership in the keyset of the dict. "
-    + "Example:<br>"
-    + "<pre class=\"language-python\">\"a\" in {\"a\" : 2, \"b\" : 5}   # evaluates as True"
-    + "</pre>")
-public final class SkylarkDict<K, V>
-    extends MutableMap<K, V> implements Map<K, V> {
-
-  private TreeMap<K, V> contents = new TreeMap<>(EvalUtils.SKYLARK_COMPARATOR);
-
-  private Mutability mutability;
-
-  @Override
-  public Mutability mutability() {
-    return mutability;
-  }
-
-  private SkylarkDict(@Nullable Environment env) {
-    mutability = env == null ? Mutability.IMMUTABLE : env.mutability();
-  }
-
-  /** @return a dict mutable in given environment only */
-  public static <K, V> SkylarkDict<K, V> of(@Nullable Environment env) {
-    return new SkylarkDict<K, V>(env);
-  }
-
-  /** @return a dict mutable in given environment only, with given initial key and value */
-  public static <K, V> SkylarkDict<K, V> of(@Nullable Environment env, K k, V v) {
-    return SkylarkDict.<K, V>of(env).putUnsafe(k, v);
-  }
-
-  /** @return a dict mutable in given environment only, with two given initial key value pairs */
-  public static <K, V> SkylarkDict<K, V> of(
-      @Nullable Environment env, K k1, V v1, K k2, V v2) {
-    return SkylarkDict.<K, V>of(env).putUnsafe(k1, v1).putUnsafe(k2, v2);
-  }
-
-  /** @return a dict mutable in given environment only, with contents copied from given map */
-  public static <K, V> SkylarkDict<K, V> copyOf(
-      @Nullable Environment env, Map<? extends K, ? extends V> m) {
-    return SkylarkDict.<K, V>of(env).putAllUnsafe(m);
-  }
-
-  private SkylarkDict<K, V> putUnsafe(K k, V v) {
-    contents.put(k, v);
-    return this;
-  }
-
-  private <KK extends K, VV extends V> SkylarkDict putAllUnsafe(Map<KK, VV> m) {
-    for (Map.Entry<KK, VV> e : m.entrySet()) {
-      contents.put(e.getKey(), e.getValue());
-    }
-    return this;
-  }
-
-  /**
-   * 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.ImmutableMap}.
-   */
-  @Override
-  protected Map<K, V> getContentsUnsafe() {
-    return contents;
-  }
-
-  public void put(K k, V v, Location loc, Environment env) throws EvalException {
-    checkMutable(loc, env);
-    EvalUtils.checkValidDictKey(k);
-    contents.put(k, v);
-  }
-
-  public void putAll(Map<? extends K, ? extends V> m, Location loc, Environment env)
-      throws EvalException {
-    checkMutable(loc, env);
-    putAllUnsafe(m);
-  }
-
-  // Other methods
-  @Override
-  public void write(Appendable buffer, char quotationMark) {
-    Printer.printList(buffer, entrySet(), "{", ", ", "}", null, quotationMark);
-  }
-
-  /**
-   * Cast a {@code SkylarkDict<?>} to a {@code SkylarkDict<K, V>}
-   * after checking its current contents.
-   * @param dict the SkylarkDict to cast
-   * @param keyType the expected class of keys
-   * @param valueType the expected class of values
-   * @param description a description of the argument being converted, or null, for debugging
-   */
-  @SuppressWarnings("unchecked")
-  public static <KeyType, ValueType> SkylarkDict<KeyType, ValueType> castDict(
-      SkylarkDict<?, ?> dict,
-      Class<KeyType> keyType,
-      Class<ValueType> valueType,
-      @Nullable String description)
-      throws EvalException {
-    Object keyDescription = description == null
-        ? null : Printer.formattable("'%s' key", description);
-    Object valueDescription = description == null
-        ? null : Printer.formattable("'%s' value", description);
-    for (Map.Entry<?, ?> e : dict.entrySet()) {
-      SkylarkType.checkType(e.getKey(), keyType, keyDescription);
-      SkylarkType.checkType(e.getValue(), valueType, valueDescription);
-    }
-    return (SkylarkDict<KeyType, ValueType>) dict;
-  }
-
-  /**
-   * Cast a SkylarkDict to a {@code Map<K, V>} after checking its current contents.
-   * Treat None as meaning the empty ImmutableMap.
-   * @param obj the Object to cast. null and None are treated as an empty list.
-   * @param keyType the expected class of keys
-   * @param valueType the expected class of values
-   * @param description a description of the argument being converted, or null, for debugging
-   */
-  public static <K, V> Map<K, V> castSkylarkDictOrNoneToMap(
-      Object obj, Class<K> keyType, Class<V> valueType, @Nullable String description)
-      throws EvalException {
-    if (EvalUtils.isNullOrNone(obj)) {
-      return ImmutableMap.of();
-    }
-    if (obj instanceof SkylarkDict) {
-      return ((SkylarkDict<?, ?>) obj).getContents(keyType, valueType, description);
-    }
-    throw new EvalException(null,
-        Printer.format("Illegal argument: %s is not of expected type dict or NoneType",
-            description == null ? Printer.repr(obj) : String.format("'%s'", description)));
-  }
-
-  /**
-   * Cast a SkylarkDict to a {@code Map<K, V>} after checking its current contents.
-   * @param keyType the expected class of keys
-   * @param valueType the expected class of values
-   * @param description a description of the argument being converted, or null, for debugging
-   */
-  public <KeyType, ValueType> Map<KeyType, ValueType> getContents(
-      Class<KeyType> keyType, Class<ValueType> valueType, @Nullable String description)
-      throws EvalException {
-    return castDict(this, keyType, valueType, description);
-  }
-
-  public static <K, V> SkylarkDict<K, V> plus(
-      SkylarkDict<? extends K, ? extends V> left,
-      SkylarkDict<? extends K, ? extends V> right,
-      @Nullable Environment env) {
-    SkylarkDict<K, V> result = SkylarkDict.<K, V>of(env);
-    result.putAllUnsafe(left);
-    result.putAllUnsafe(right);
-    return result;
-  }
-
-  private static final SkylarkDict<?, ?> EMPTY = of(null);
-
-  public static <K, V> SkylarkDict<K, V> empty() {
-    return (SkylarkDict<K, V>) EMPTY;
-  }
-}
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 102cd31..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
@@ -35,13 +35,13 @@
  */
 @SkylarkModule(name = "sequence", documented = false,
     doc = "common type of lists and tuples")
-  public abstract class SkylarkList<E>
-    extends MutableCollection<E> implements List<E>, RandomAccess {
+  public abstract class SkylarkList
+    extends MutableCollection<Object> implements List<Object>, RandomAccess {
 
   /**
    * Returns an ImmutableList object with the current underlying contents of this SkylarkList.
    */
-  public abstract ImmutableList<E> getImmutableList();
+  public abstract ImmutableList<Object> getImmutableList();
 
   /**
    * Returns a List object with the current underlying contents of this SkylarkList.
@@ -49,7 +49,8 @@
    * Indeed it can sometimes be a {@link GlobList}.
    */
   // TODO(bazel-team): move GlobList out of Skylark, into an extension.
-  public abstract List<E> getContents();
+  @Override
+  public abstract List<Object> getContents();
 
   /**
    * The underlying contents are a (usually) mutable data structure.
@@ -60,7 +61,7 @@
    * it need not be an instance of {@link com.google.common.collect.ImmutableList}.
    */
   @Override
-  protected abstract List<E> getContentsUnsafe();
+  protected abstract List<Object> getContentsUnsafe();
 
   /**
    * Returns true if this list is a tuple.
@@ -69,7 +70,7 @@
 
   // A SkylarkList forwards all read-only access to the getContentsUnsafe().
   @Override
-  public final E get(int i) {
+  public final Object get(int i) {
     return getContentsUnsafe().get(i);
   }
 
@@ -84,12 +85,12 @@
   }
 
   @Override
-  public ListIterator<E> listIterator() {
+  public ListIterator<Object> listIterator() {
     return getContentsUnsafe().listIterator();
   }
 
   @Override
-  public ListIterator<E> listIterator(int index) {
+  public ListIterator<Object> listIterator(int index) {
     return getContentsUnsafe().listIterator(index);
   }
 
@@ -97,28 +98,28 @@
   // to prevent subsequent mutation. To get a mutable SkylarkList,
   // use a method that takes an Environment into account.
   @Override
-  public List<E> subList(int fromIndex, int toIndex) {
+  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, E element) {
+  public void add(int index, Object element) {
     throw new UnsupportedOperationException();
   }
 
   @Override
-  public boolean addAll(int index, Collection<? extends E> elements) {
+  public boolean addAll(int index, Collection<?> elements) {
     throw new UnsupportedOperationException();
   }
 
   @Override
-  public E remove(int index) {
+  public Object remove(int index) {
     throw new UnsupportedOperationException();
   }
 
   @Override
-  public E set(int index, E element) {
+  public Object set(int index, Object element) {
     throw new UnsupportedOperationException();
   }
 
@@ -154,9 +155,14 @@
   public static <TYPE> List<TYPE> castList(
       List<?> list, Class<TYPE> type, @Nullable String description)
       throws EvalException {
-    Object desc = description == null ? null : Printer.formattable("'%s' element", description);
     for (Object value : list) {
-      SkylarkType.checkType(value, type, desc);
+      if (!type.isInstance(value)) {
+        throw new EvalException(null,
+            Printer.format("Illegal argument: expected type %r %sbut got type %s instead",
+                type,
+                description == null ? "" : String.format("for '%s' element ", description),
+                EvalUtils.getDataTypeName(value)));
+      }
     }
     return (List<TYPE>) list;
   }
@@ -175,7 +181,7 @@
       return ImmutableList.of();
     }
     if (obj instanceof SkylarkList) {
-      return ((SkylarkList<?>) obj).getContents(type, description);
+      return ((SkylarkList) obj).getContents(type, description);
     }
     throw new EvalException(null,
         Printer.format("Illegal argument: %s is not of expected type list or NoneType",
@@ -212,15 +218,15 @@
             + "['a', 'b', 'c', 'd'][3:0:-1]  # ['d', 'c', 'b']</pre>"
             + "Lists are mutable, as in Python."
   )
-  public static final class MutableList<E> extends SkylarkList<E> {
+  public static final class MutableList extends SkylarkList {
 
-    private final ArrayList<E> contents = new ArrayList<>();
+    private final ArrayList<Object> contents = new ArrayList<>();
 
     // Treat GlobList specially: external code depends on it.
     // TODO(bazel-team): make data structures *and binary operators* extensible
     // (via e.g. interface classes for each binary operator) so that GlobList
     // can be implemented outside of the core of Skylark.
-    @Nullable private GlobList<E> globList;
+    @Nullable private GlobList<?> globList;
 
     private final Mutability mutability;
 
@@ -230,12 +236,11 @@
      * @param mutability a Mutability context
      * @return a MutableList containing the elements
      */
-    @SuppressWarnings("unchecked")
-    MutableList(Iterable<? extends E> contents, Mutability mutability) {
+    MutableList(Iterable<?> contents, Mutability mutability) {
       super();
       addAllUnsafe(contents);
-      if (contents instanceof GlobList) {
-        globList = (GlobList<E>) contents;
+      if (contents instanceof GlobList<?>) {
+        globList = (GlobList<?>) contents;
       }
       this.mutability = mutability;
     }
@@ -246,7 +251,7 @@
      * @param env an Environment from which to inherit Mutability, or null for immutable
      * @return a MutableList containing the elements
      */
-    public MutableList(Iterable<? extends E> contents, @Nullable Environment env) {
+    public MutableList(Iterable<?> contents, @Nullable Environment env) {
       this(contents, env == null ? Mutability.IMMUTABLE : env.mutability());
     }
 
@@ -255,7 +260,7 @@
      * @param contents the contents of the list
      * @return an actually immutable MutableList containing the elements
      */
-    public MutableList(Iterable<? extends E> contents) {
+    public MutableList(Iterable<?> contents) {
       this(contents, Mutability.IMMUTABLE);
     }
 
@@ -272,7 +277,7 @@
      * @param contents the contents of the list
      * @return a Skylark list containing the specified arguments as elements.
      */
-    public static <E> MutableList<E> of(@Nullable Environment env, E... contents) {
+    public static MutableList of(@Nullable Environment env, Object... contents) {
       return new MutableList(ImmutableList.copyOf(contents), env);
     }
 
@@ -281,8 +286,8 @@
      * @param elements the elements to add
      * Assumes that you already checked for Mutability.
      */
-    private void addAllUnsafe(Iterable<? extends E> elements) {
-      for (E elem : elements) {
+    private void addAllUnsafe(Iterable<?> elements) {
+      for (Object elem : elements) {
         contents.add(elem);
       }
     }
@@ -293,7 +298,7 @@
       globList = null; // If you're going to mutate it, invalidate the underlying GlobList.
     }
 
-    @Nullable public GlobList<E> getGlobList() {
+    @Nullable public GlobList<?> getGlobList() {
       return globList;
     }
 
@@ -302,15 +307,15 @@
      */
     @Override
     @SuppressWarnings("unchecked")
-    public List<E> getContents() {
+    public List<Object> getContents() {
       if (globList != null) {
-        return globList;
+        return (List<Object>) (List<?>) globList;
       }
       return getImmutableList();
     }
 
     @Override
-    protected List<E> getContentsUnsafe() {
+    protected List<Object> getContentsUnsafe() {
       return contents;
     }
 
@@ -331,10 +336,7 @@
      * @param env the Environment in which to create a new list
      * @return a new MutableList
      */
-    public static <E> MutableList<E> concat(
-        MutableList<? extends E> left,
-        MutableList<? extends E> right,
-        Environment env) {
+    public static MutableList concat(MutableList left, MutableList right, Environment env) {
       if (left.getGlobList() == null && right.getGlobList() == null) {
         return new MutableList(Iterables.concat(left, right), env);
       }
@@ -348,7 +350,7 @@
      * @param loc the Location at which to report any error
      * @param env the Environment requesting the modification
      */
-    public void add(E element, Location loc, Environment env) throws EvalException {
+    public void add(Object element, Location loc, Environment env) throws EvalException {
       checkMutable(loc, env);
       contents.add(element);
     }
@@ -364,14 +366,13 @@
      * @param loc the Location at which to report any error
      * @param env the Environment requesting the modification
      */
-    public void addAll(Iterable<? extends E> elements, Location loc, Environment env)
-        throws EvalException {
+    public void addAll(Iterable<?> elements, Location loc, Environment env) throws EvalException {
       checkMutable(loc, env);
       addAllUnsafe(elements);
     }
 
     @Override
-    public ImmutableList<E> getImmutableList() {
+    public ImmutableList<Object> getImmutableList() {
       return ImmutableList.copyOf(contents);
     }
 
@@ -417,11 +418,11 @@
             + "Tuples are immutable, therefore <code>x[1] = \"a\"</code> is not supported."
   )
   @Immutable
-  public static final class Tuple<E> extends SkylarkList<E> {
+  public static final class Tuple extends SkylarkList {
 
-    private final ImmutableList<E> contents;
+    private final ImmutableList<Object> contents;
 
-    private Tuple(ImmutableList<E> contents) {
+    private Tuple(ImmutableList<Object> contents) {
       super();
       this.contents = contents;
     }
@@ -434,19 +435,14 @@
     /**
      * THE empty Skylark tuple.
      */
-    private static final Tuple<?> EMPTY = new Tuple<>(ImmutableList.of());
-
-    @SuppressWarnings("unchecked")
-    public static final <E> Tuple<E> empty() {
-      return (Tuple<E>) EMPTY;
-    }
+    public static final Tuple EMPTY = new Tuple(ImmutableList.of());
 
     /**
      * Creates a Tuple from an ImmutableList.
      */
-    public static<E> Tuple<E> create(ImmutableList<E> contents) {
+    public static Tuple create(ImmutableList<Object> contents) {
       if (contents.isEmpty()) {
-        return empty();
+        return EMPTY;
       }
       return new Tuple(contents);
     }
@@ -454,8 +450,9 @@
     /**
      * Creates a Tuple from an Iterable.
      */
-    public static <E> Tuple<E> copyOf(Iterable<? extends E> contents) {
-      return create(ImmutableList.<E>copyOf(contents));
+    public static Tuple copyOf(Iterable<?> contents) {
+      // Do not remove <Object>: workaround for Java 7 type inference.
+      return create(ImmutableList.<Object>copyOf(contents));
     }
 
     /**
@@ -463,22 +460,22 @@
      * @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 <E> Tuple<E> of(E... elements) {
+    public static Tuple of(Object... elements) {
       return Tuple.create(ImmutableList.copyOf(elements));
     }
 
     @Override
-    public ImmutableList<E> getImmutableList() {
+    public ImmutableList<Object> getImmutableList() {
       return contents;
     }
 
     @Override
-    public List<E> getContents() {
+    public List<Object> getContents() {
       return contents;
     }
 
     @Override
-    protected List<E> getContentsUnsafe() {
+    protected List<Object> getContentsUnsafe() {
       return contents;
     }
 
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
index dd9b91a..afa107a 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkMutable.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkMutable.java
@@ -21,8 +21,6 @@
 
 import java.util.Collection;
 import java.util.Iterator;
-import java.util.Map;
-import java.util.Set;
 
 import javax.annotation.Nullable;
 
@@ -46,11 +44,6 @@
   }
 
   @Override
-  public boolean isImmutable() {
-    return !mutability().isMutable();
-  }
-
-  @Override
   public String toString() {
     return Printer.repr(this);
   }
@@ -60,6 +53,16 @@
     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}
@@ -152,95 +155,4 @@
       return getContentsUnsafe().hashCode();
     }
   }
-
-  abstract static class MutableMap<K, V> extends SkylarkMutable implements Map<K, V> {
-
-    MutableMap() {}
-
-    /**
-     * 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}.
-     */
-    protected abstract Map<K, V> getContentsUnsafe();
-
-    // A SkylarkDict forwards all read-only access to the contents.
-    @Override
-    public final V get(Object key) {
-      return getContentsUnsafe().get(key);
-    }
-
-    @Override
-    public boolean containsKey(Object key) {
-      return getContentsUnsafe().containsKey(key);
-    }
-
-    @Override
-    public boolean containsValue(Object value) {
-      return getContentsUnsafe().containsValue(value);
-    }
-
-    @Override
-      public Set<Map.Entry<K, V>> entrySet() {
-      return getContentsUnsafe().entrySet();
-    }
-
-    @Override
-    public Set<K> keySet() {
-      return getContentsUnsafe().keySet();
-    }
-
-    @Override
-    public Collection<V> values() {
-      return getContentsUnsafe().values();
-    }
-
-    @Override
-    public int size() {
-      return getContentsUnsafe().size();
-    }
-
-    @Override
-    public boolean isEmpty() {
-      return getContentsUnsafe().isEmpty();
-    }
-
-    // Disable all mutation interfaces without a mutation context.
-
-    @Deprecated
-    @Override
-    public final V put(K key, V value) {
-      throw new UnsupportedOperationException();
-    }
-
-    @Deprecated
-    @Override
-    public final void putAll(Map<? extends K, ? extends V> map) {
-      throw new UnsupportedOperationException();
-    }
-
-    @Deprecated
-    @Override
-    public final V remove(Object key) {
-      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/main/java/com/google/devtools/build/lib/syntax/SkylarkNestedSet.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkNestedSet.java
index f3e8c59..b00413c 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkNestedSet.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkNestedSet.java
@@ -183,7 +183,7 @@
   private static SkylarkType checkType(SkylarkType builderType, SkylarkType itemType, Location loc)
       throws EvalException {
     if (SkylarkType.intersection(
-        SkylarkType.Union.of(SkylarkType.DICT, SkylarkType.LIST, SkylarkType.STRUCT),
+        SkylarkType.Union.of(SkylarkType.MAP, SkylarkType.LIST, SkylarkType.STRUCT),
         itemType) != SkylarkType.BOTTOM) {
       throw new EvalException(
           loc, String.format("sets cannot contain items of type '%s'", itemType));
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 3f4d641..9fc24c0 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
@@ -174,8 +174,8 @@
   /** The FUNCTION type, that contains all functions, otherwise dynamically typed at call-time */
   public static final SkylarkFunctionType FUNCTION = new SkylarkFunctionType("unknown", TOP);
 
-  /** The DICT type, that contains SkylarkDict */
-  public static final Simple DICT = Simple.of(SkylarkDict.class);
+  /** The MAP type, that contains all Map's, and the generic combinator for maps */
+  public static final Simple MAP = Simple.of(Map.class);
 
   /** The SEQUENCE type, that contains lists and tuples */
   // TODO(bazel-team): this was added for backward compatibility with the BUILD language,
@@ -715,13 +715,13 @@
    */
   public static Object convertToSkylark(Object object, @Nullable Environment env) {
     if (object instanceof List && !(object instanceof SkylarkList)) {
-      return new MutableList<>((List<?>) object, env);
+      return new MutableList((List<?>) object, env);
     }
     if (object instanceof SkylarkValue) {
       return object;
     }
-    if (object instanceof Map) {
-      return SkylarkDict.<Object, Object>copyOf(env, (Map<?, ?>) object);
+    if (object instanceof List) {
+      return new MutableList((List<?>) object, env);
     }
     // TODO(bazel-team): ensure everything is a SkylarkValue at all times.
     // Preconditions.checkArgument(EvalUtils.isSkylarkAcceptable(
@@ -731,15 +731,4 @@
     //    object.getClass());
     return object;
   }
-
-  public static void checkType(Object object, Class<?> type, @Nullable Object description)
-      throws EvalException {
-    if (!type.isInstance(object)) {
-      throw new EvalException(null,
-          Printer.format("Illegal argument: expected type %r %sbut got type %s instead",
-              type,
-              description == null ? "" : String.format("for %s ", description),
-              EvalUtils.getDataTypeName(object)));
-      }
-  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/compiler/ByteCodeMethodCalls.java b/src/main/java/com/google/devtools/build/lib/syntax/compiler/ByteCodeMethodCalls.java
index 28bd503..55e9cc1 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/compiler/ByteCodeMethodCalls.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/compiler/ByteCodeMethodCalls.java
@@ -15,9 +15,6 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
-import com.google.devtools.build.lib.events.Location;
-import com.google.devtools.build.lib.syntax.Environment;
-import com.google.devtools.build.lib.syntax.SkylarkDict;
 
 import net.bytebuddy.implementation.bytecode.StackManipulation;
 
@@ -74,21 +71,6 @@
   }
 
   /**
-   * Byte code invocations for {@link SkylarkDict}.
-   */
-  public static class BCSkylarkDict {
-    public static final StackManipulation of =
-        ByteCodeUtils.invoke(SkylarkDict.class, "of", Environment.class);
-
-    public static final StackManipulation copyOf =
-        ByteCodeUtils.invoke(SkylarkDict.class, "copyOf", Environment.class, Map.class);
-
-    public static final StackManipulation put =
-        ByteCodeUtils.invoke(SkylarkDict.class, "put",
-            Object.class, Object.class, Location.class, Environment.class);
-  }
-
-  /**
    * Byte code invocations for {@link ImmutableList}.
    */
   public static class BCImmutableList {
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java
index 6fedcee..717a132 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleClassFunctionsTest.java
@@ -199,7 +199,7 @@
   @Test
   public void testLabelListWithAspectsError() throws Exception {
     checkErrorContains(
-        "Illegal argument: expected type aspect for 'aspects' element but got type int instead",
+        "Expected a list of aspects for 'aspects'",
         "def _impl(target, ctx):",
         "   pass",
         "my_aspect = aspect(implementation = _impl)",
diff --git a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleContextTest.java b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleContextTest.java
index 98cfe8d..e46c55f 100644
--- a/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleContextTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skylark/SkylarkRuleContextTest.java
@@ -22,6 +22,7 @@
 import static org.junit.Assert.fail;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.analysis.FileConfiguredTarget;
@@ -32,7 +33,6 @@
 import com.google.devtools.build.lib.rules.java.JavaSourceJarsProvider;
 import com.google.devtools.build.lib.rules.python.PythonSourcesProvider;
 import com.google.devtools.build.lib.skylark.util.SkylarkTestCase;
-import com.google.devtools.build.lib.syntax.SkylarkDict;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.testutil.TestConstants;
@@ -559,7 +559,7 @@
   public void testSkylarkRuleContextGetDefaultShellEnv() throws Exception {
     SkylarkRuleContext ruleContext = createRuleContext("//foo:foo");
     Object result = evalRuleContextCode(ruleContext, "ruleContext.configuration.default_shell_env");
-    assertThat(result).isInstanceOf(SkylarkDict.class);
+    assertThat(result).isInstanceOf(ImmutableMap.class);
   }
 
   @Test
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 10c7a6c..961a2cb 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
@@ -38,7 +38,6 @@
 import com.google.devtools.build.lib.skylarkinterface.SkylarkSignature;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkSignature.Param;
 import com.google.devtools.build.lib.syntax.BuiltinFunction;
-import com.google.devtools.build.lib.syntax.Environment;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.EvalUtils;
 import com.google.devtools.build.lib.syntax.Printer;
@@ -70,8 +69,7 @@
     mandatoryPositionals = {@Param(name = "mandatory", doc = "")},
     optionalPositionals = {@Param(name = "optional", doc = "")},
     mandatoryNamedOnly = {@Param(name = "mandatory_key", doc = "")},
-    optionalNamedOnly = {@Param(name = "optional_key", doc = "", defaultValue = "'x'")},
-    useEnvironment = true
+    optionalNamedOnly = {@Param(name = "optional_key", doc = "", defaultValue = "'x'")}
   )
   private BuiltinFunction mockFunc;
 
@@ -124,10 +122,8 @@
         new BuiltinFunction("mock") {
           @SuppressWarnings("unused")
           public Object invoke(
-              Object mandatory, Object optional, Object mandatoryKey, Object optionalKey,
-              Environment env) {
+              Object mandatory, Object optional, Object mandatoryKey, Object optionalKey) {
             return EvalUtils.optionMap(
-                env,
                 "mandatory",
                 mandatory,
                 "optional",
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 cd0129d..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
@@ -26,6 +26,8 @@
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
 
+import java.util.LinkedHashMap;
+import java.util.Map;
 import java.util.TreeMap;
 
 /**
@@ -35,8 +37,8 @@
 @RunWith(JUnit4.class)
 public class EvalUtilsTest {
 
-  private static SkylarkDict<Object, Object> makeDict() {
-    return SkylarkDict.<Object, Object>of(null);
+  private static Map<Object, Object> makeDict() {
+    return new LinkedHashMap<>();
   }
 
   @Test
@@ -77,7 +79,7 @@
     map.put("test", 7);
     map.put(-1, 2);
     map.put("4", 6);
-    map.put(true, 1);
+    map.put(2.0, 1);
     map.put(Runtime.NONE, 0);
 
     int expected = 0;
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTest.java b/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTest.java
index 4396608..7a10338 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTest.java
@@ -259,7 +259,7 @@
           final Map<String, Object> kwargs,
           FuncallExpression ast,
           Environment env) {
-        return SkylarkDict.copyOf(env, kwargs);
+        return kwargs;
       }
     };
 
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java b/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java
index 7bbe8ea..a894ddf 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java
@@ -418,8 +418,8 @@
   public void testBuiltinFunctionErrorMessage() throws Exception {
     new BothModesTest()
         .testIfErrorContains(
-            "Method set.union(new_elements: Iterable) is not applicable for arguments (string): "
-                + "'new_elements' is string, but should be Iterable",
+            "Method set.union(newElements: Iterable) is not applicable for arguments (string): "
+                + "'newElements' is string, but should be Iterable",
             "set([]).union('a')")
         .testIfErrorContains(
             "Method string.startswith(sub: string, start: int, end: int or NoneType) is not "
@@ -1347,8 +1347,8 @@
     new BothModesTest()
         .testIfErrorContains("insufficient arguments received by union", "set(['a']).union()")
         .testIfErrorContains(
-            "Method set.union(new_elements: Iterable) is not applicable for arguments (string): "
-                + "'new_elements' is string, but should be Iterable",
+            "Method set.union(newElements: Iterable) is not applicable for arguments (string): "
+                + "'newElements' is string, but should be Iterable",
             "set(['a']).union('b')");
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
index 7ee189c..6aae5c1 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
@@ -132,7 +132,6 @@
     }
   }
 
-  @SkylarkModule(name = "MockClassObject", doc = "", documented = false)
   static final class MockClassObject implements ClassObject {
     @Override
     public Object getValue(String name) {
@@ -836,11 +835,11 @@
   }
 
   @Test
-  public void testDictAssignmentAsLValueSideEffects() throws Exception {
+  public void testDictAssignmentAsLValueNoSideEffects() throws Exception {
     new SkylarkTest().setUp("def func(d):",
         "  d['b'] = 2",
         "d = {'a' : 1}",
-        "func(d)").testLookup("d", SkylarkDict.of(null, "a", 1, "b", 2));
+        "func(d)").testLookup("d", ImmutableMap.of("a", 1));
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/ValidationTest.java b/src/test/java/com/google/devtools/build/lib/syntax/ValidationTest.java
index c44e5c9..4c6eb6a 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/ValidationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/ValidationTest.java
@@ -284,7 +284,7 @@
 
   @Test
   public void testParentWithSkylarkModule() throws Exception {
-    Class<?> emptyTupleClass = Tuple.empty().getClass();
+    Class<?> emptyTupleClass = Tuple.EMPTY.getClass();
     Class<?> tupleClass = Tuple.of(1, "a", "b").getClass();
     Class<?> mutableListClass = new MutableList(Tuple.of(1, 2, 3), env).getClass();
 
@@ -311,7 +311,7 @@
   @Test
   public void testSkylarkTypeEquivalence() throws Exception {
     // All subclasses of SkylarkList are made equivalent
-    Class<?> emptyTupleClass = Tuple.empty().getClass();
+    Class<?> emptyTupleClass = Tuple.EMPTY.getClass();
     Class<?> tupleClass = Tuple.of(1, "a", "b").getClass();
     Class<?> mutableListClass = new MutableList(Tuple.of(1, 2, 3), env).getClass();
 
@@ -322,14 +322,8 @@
 
     // Also for ClassObject
     assertThat(SkylarkType.of(ClassObject.SkylarkClassObject.class)).isEqualTo(SkylarkType.STRUCT);
-    try {
-      SkylarkType.of(ClassObject.class);
-      throw new Exception("foo");
-    } catch (Exception e) {
-      assertThat(e.getMessage()).contains(
-          "interface com.google.devtools.build.lib.syntax.ClassObject "
-          + "is not allowed as a Skylark value");
-    }
+    // TODO(bazel-team): fix that?
+    assertThat(SkylarkType.of(ClassObject.class)).isNotEqualTo(SkylarkType.STRUCT);
 
     // Also test for these bazel classes, to avoid some regression.
     // TODO(bazel-team): move to some other place to remove dependency of syntax tests on Artifact?
@@ -348,17 +342,17 @@
     assertThat(SkylarkType.LIST.includes(combo1)).isTrue();
 
     SkylarkType union1 =
-        SkylarkType.Union.of(SkylarkType.DICT, SkylarkType.LIST, SkylarkType.STRUCT);
-    assertThat(union1.includes(SkylarkType.DICT)).isTrue();
+        SkylarkType.Union.of(SkylarkType.MAP, SkylarkType.LIST, SkylarkType.STRUCT);
+    assertThat(union1.includes(SkylarkType.MAP)).isTrue();
     assertThat(union1.includes(SkylarkType.STRUCT)).isTrue();
     assertThat(union1.includes(combo1)).isTrue();
     assertThat(union1.includes(SkylarkType.STRING)).isFalse();
 
     SkylarkType union2 =
         SkylarkType.Union.of(
-            SkylarkType.LIST, SkylarkType.DICT, SkylarkType.STRING, SkylarkType.INT);
+            SkylarkType.LIST, SkylarkType.MAP, SkylarkType.STRING, SkylarkType.INT);
     SkylarkType inter1 = SkylarkType.intersection(union1, union2);
-    assertThat(inter1.includes(SkylarkType.DICT)).isTrue();
+    assertThat(inter1.includes(SkylarkType.MAP)).isTrue();
     assertThat(inter1.includes(SkylarkType.LIST)).isTrue();
     assertThat(inter1.includes(combo1)).isTrue();
     assertThat(inter1.includes(SkylarkType.INT)).isFalse();