diff --git a/src/main/java/com/google/devtools/build/docgen/SkylarkDocumentationCollector.java b/src/main/java/com/google/devtools/build/docgen/SkylarkDocumentationCollector.java
index f7ae83b..a2e7b64 100644
--- a/src/main/java/com/google/devtools/build/docgen/SkylarkDocumentationCollector.java
+++ b/src/main/java/com/google/devtools/build/docgen/SkylarkDocumentationCollector.java
@@ -14,6 +14,7 @@
 package com.google.devtools.build.docgen;
 
 import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.docgen.skylark.SkylarkBuiltinMethodDoc;
 import com.google.devtools.build.docgen.skylark.SkylarkJavaMethodDoc;
@@ -21,9 +22,9 @@
 import com.google.devtools.build.lib.analysis.TransitiveInfoCollection;
 import com.google.devtools.build.lib.rules.SkylarkModules;
 import com.google.devtools.build.lib.rules.SkylarkRuleContext;
-import com.google.devtools.build.lib.syntax.Environment;
 import com.google.devtools.build.lib.syntax.FuncallExpression;
 import com.google.devtools.build.lib.syntax.MethodLibrary;
+import com.google.devtools.build.lib.syntax.Runtime;
 import com.google.devtools.build.lib.syntax.SkylarkCallable;
 import com.google.devtools.build.lib.syntax.SkylarkModule;
 import com.google.devtools.build.lib.syntax.SkylarkSignature;
@@ -34,6 +35,7 @@
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.LinkedList;
+import java.util.List;
 import java.util.Map;
 import java.util.Map.Entry;
 import java.util.Set;
@@ -130,7 +132,7 @@
 
   private static Map<String, SkylarkModuleDoc> collectBuiltinModules() {
     Map<String, SkylarkModuleDoc> modules = new HashMap<>();
-    collectBuiltinDoc(modules, Environment.class.getDeclaredFields());
+    collectBuiltinDoc(modules, Runtime.class.getDeclaredFields());
     collectBuiltinDoc(modules, MethodLibrary.class.getDeclaredFields());
     for (Class<?> moduleClass : SkylarkModules.MODULES) {
       collectBuiltinDoc(modules, moduleClass.getDeclaredFields());
@@ -145,13 +147,19 @@
         Class<?> moduleClass = skylarkSignature.objectType();
         SkylarkModule skylarkModule = moduleClass.equals(Object.class)
             ? getTopLevelModule()
-            : moduleClass.getAnnotation(SkylarkModule.class);
-        if (!modules.containsKey(skylarkModule.name())) {
-          modules.put(skylarkModule.name(), new SkylarkModuleDoc(skylarkModule, moduleClass));
+            : Runtime.getCanonicalRepresentation(moduleClass).getAnnotation(SkylarkModule.class);
+        if (skylarkModule == null) {
+          // TODO(bazel-team): we currently have undocumented methods on undocumented data
+          // structures, namely java.util.List. Remove this case when we are done.
+          Preconditions.checkState(!skylarkSignature.documented());
+          Preconditions.checkState(moduleClass == List.class);
+        } else {
+          if (!modules.containsKey(skylarkModule.name())) {
+            modules.put(skylarkModule.name(), new SkylarkModuleDoc(skylarkModule, moduleClass));
+          }
+          SkylarkModuleDoc module = modules.get(skylarkModule.name());
+          module.addMethod(new SkylarkBuiltinMethodDoc(module, skylarkSignature, field.getType()));
         }
-
-        SkylarkModuleDoc module = modules.get(skylarkModule.name());
-        module.addMethod(new SkylarkBuiltinMethodDoc(module, skylarkSignature, field.getType()));
       }
     }
   }
diff --git a/src/main/java/com/google/devtools/build/docgen/skylark/SkylarkDoc.java b/src/main/java/com/google/devtools/build/docgen/skylark/SkylarkDoc.java
index 065ab68..da77f73 100644
--- a/src/main/java/com/google/devtools/build/docgen/skylark/SkylarkDoc.java
+++ b/src/main/java/com/google/devtools/build/docgen/skylark/SkylarkDoc.java
@@ -13,9 +13,9 @@
 // limitations under the License.
 package com.google.devtools.build.docgen.skylark;
 
-import com.google.devtools.build.lib.syntax.Environment.NoneType;
 import com.google.devtools.build.lib.syntax.EvalUtils;
 import com.google.devtools.build.lib.syntax.FuncallExpression;
+import com.google.devtools.build.lib.syntax.Runtime.NoneType;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkModule;
 import com.google.devtools.build.lib.syntax.SkylarkSignature;
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTargetBuilder.java b/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTargetBuilder.java
index bc1c9eb..b89cf72 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTargetBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/RuleConfiguredTargetBuilder.java
@@ -46,10 +46,10 @@
 import com.google.devtools.build.lib.rules.test.TestProvider;
 import com.google.devtools.build.lib.rules.test.TestProvider.TestParams;
 import com.google.devtools.build.lib.syntax.ClassObject;
-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.Label;
+import com.google.devtools.build.lib.syntax.Runtime;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 
@@ -420,7 +420,7 @@
         || type.equals(Boolean.class)
         || Artifact.class.isAssignableFrom(type)
         || type.equals(Label.class)
-        || type.equals(Environment.NoneType.class);
+        || type.equals(Runtime.NoneType.class);
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/packages/ImplicitOutputsFunction.java b/src/main/java/com/google/devtools/build/lib/packages/ImplicitOutputsFunction.java
index b05082a..12d02c6 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/ImplicitOutputsFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/ImplicitOutputsFunction.java
@@ -27,9 +27,9 @@
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.syntax.ClassObject;
 import com.google.devtools.build.lib.syntax.ClassObject.SkylarkClassObject;
-import com.google.devtools.build.lib.syntax.Environment;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.Label;
+import com.google.devtools.build.lib.syntax.Runtime;
 import com.google.devtools.build.lib.syntax.SkylarkCallbackFunction;
 import com.google.devtools.build.lib.util.StringUtil;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
@@ -91,7 +91,7 @@
         // since we don't yet have a build configuration.
         if (!map.isConfigurable(attrName, attrType)) {
           Object value = map.get(attrName, attrType);
-          attrValues.put(attrName, value == null ? Environment.NONE : value);
+          attrValues.put(attrName, value == null ? Runtime.NONE : value);
         }
       }
       ClassObject attrs = new SkylarkClassObject(attrValues, "Attribute '%s' either doesn't exist "
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 64e1fe6..b94147d 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
@@ -35,6 +35,7 @@
 import com.google.devtools.build.lib.syntax.BaseFunction;
 import com.google.devtools.build.lib.syntax.BuildFileAST;
 import com.google.devtools.build.lib.syntax.BuiltinFunction;
+import com.google.devtools.build.lib.syntax.ClassObject;
 import com.google.devtools.build.lib.syntax.Environment;
 import com.google.devtools.build.lib.syntax.Environment.NoSuchVariableException;
 import com.google.devtools.build.lib.syntax.EvalException;
@@ -47,6 +48,7 @@
 import com.google.devtools.build.lib.syntax.Label;
 import com.google.devtools.build.lib.syntax.MethodLibrary;
 import com.google.devtools.build.lib.syntax.ParserInputSource;
+import com.google.devtools.build.lib.syntax.Runtime;
 import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
 import com.google.devtools.build.lib.syntax.SkylarkSignature;
 import com.google.devtools.build.lib.syntax.SkylarkSignature.Param;
@@ -373,6 +375,7 @@
     threadPool.allowCoreThreadTimeOut(true);
     this.environmentExtensions = ImmutableList.copyOf(environmentExtensions);
     this.packageArguments = createPackageArguments();
+    this.nativeModule = newNativeModule();
   }
 
   /**
@@ -556,7 +559,7 @@
    * seen by the parser, because the presence of "subinclude" triggers
    * preprocessing.)
    */
-  @SkylarkSignature(name = "mocksubinclude", returnType = Environment.NoneType.class,
+  @SkylarkSignature(name = "mocksubinclude", returnType = Runtime.NoneType.class,
       doc = "implement the mocksubinclude function emitted by the PythonPreprocessor",
       mandatoryPositionals = {
         @Param(name = "label", type = Object.class,
@@ -568,7 +571,7 @@
       new BuiltinFunction.Factory("mocksubinclude") {
         public BuiltinFunction create(final PackageContext context) {
           return new BuiltinFunction("mocksubinclude", this) {
-            public Environment.NoneType invoke(Object labelO, String pathString,
+            public Runtime.NoneType invoke(Object labelO, String pathString,
                 Location loc) throws ConversionException {
               Label label = Type.LABEL.convert(labelO, "'mocksubinclude' argument",
                   context.pkgBuilder.getBuildFileLabel());
@@ -583,7 +586,7 @@
               }
 
               context.pkgBuilder.addSubinclude(label, path);
-              return Environment.NONE;
+              return Runtime.NONE;
             }
           };
         }
@@ -604,7 +607,7 @@
    * <p>Where ":env1", "env2", ... are all environment rules declared in the same package. All
    * parameters are mandatory.
    */
-  @SkylarkSignature(name = "environment_group", returnType = Environment.NoneType.class,
+  @SkylarkSignature(name = "environment_group", returnType = Runtime.NoneType.class,
       doc = "Defines a cc_library, by wrapping around the usual library "
       + "and also defining a headers target.",
       mandatoryNamedOnly = {
@@ -620,7 +623,7 @@
       new BuiltinFunction.Factory("environment_group") {
         public BuiltinFunction create(final PackageContext context) {
           return new BuiltinFunction("environment_group", this) {
-            public Environment.NoneType invoke(String name, Object environmentsO, Object defaultsO,
+            public Runtime.NoneType invoke(String name, Object environmentsO, Object defaultsO,
                 Location loc) throws EvalException, ConversionException {
               List<Label> environments = Type.LABEL_LIST.convert(environmentsO,
                   "'environment_group argument'", context.pkgBuilder.getBuildFileLabel());
@@ -630,7 +633,7 @@
               try {
                 context.pkgBuilder.addEnvironmentGroup(name, environments, defaults,
                     context.eventHandler, loc);
-                return Environment.NONE;
+                return Runtime.NONE;
               } catch (Label.SyntaxException e) {
                 throw new EvalException(loc,
                     "environment group has invalid name: " + name + ": " + e.getMessage());
@@ -646,7 +649,7 @@
    * Returns a function-value implementing "exports_files" in the specified
    * package context.
    */
-  @SkylarkSignature(name = "exports_files", returnType = Environment.NoneType.class,
+  @SkylarkSignature(name = "exports_files", returnType = Runtime.NoneType.class,
       doc = "Declare a set of files as exported",
       mandatoryPositionals = {
         @Param(name = "srcs", type = HackHackEitherList.class, generic1 = String.class,
@@ -666,7 +669,7 @@
       new BuiltinFunction.Factory("exports_files") {
         public BuiltinFunction create () {
           return new BuiltinFunction("exports_files", this) {
-            public Environment.NoneType invoke(Object srcs, Object visibility, Object licenses,
+            public Runtime.NoneType invoke(Object srcs, Object visibility, Object licenses,
                 FuncallExpression ast, Environment env)
                 throws EvalException, ConversionException {
               return callExportsFiles(srcs, visibility, licenses, ast, env);
@@ -675,7 +678,7 @@
         }
       };
 
-  static Environment.NoneType callExportsFiles(Object srcs, Object visibilityO, Object licensesO,
+  static Runtime.NoneType callExportsFiles(Object srcs, Object visibilityO, Object licensesO,
       FuncallExpression ast, Environment env) throws EvalException, ConversionException {
     Package.LegacyBuilder pkgBuilder = getContext(env, ast).pkgBuilder;
     List<String> files = Type.STRING_LIST.convert(srcs, "'exports_files' operand");
@@ -720,7 +723,7 @@
         throw new EvalException(ast.getLocation(), e.getMessage());
       }
     }
-    return Environment.NONE;
+    return Runtime.NONE;
   }
 
   /**
@@ -728,7 +731,7 @@
    * context.
    * TODO(bazel-team): Remove in favor of package.licenses.
    */
-  @SkylarkSignature(name = "licenses", returnType = Environment.NoneType.class,
+  @SkylarkSignature(name = "licenses", returnType = Runtime.NoneType.class,
       doc = "Declare the license(s) for the code in the current package.",
       mandatoryPositionals = {
         @Param(name = "license_strings", type = HackHackEitherList.class, generic1 = String.class,
@@ -738,7 +741,7 @@
       new BuiltinFunction.Factory("licenses") {
         public BuiltinFunction create(final PackageContext context) {
           return new BuiltinFunction("licenses", this) {
-            public Environment.NoneType invoke(Object licensesO, Location loc) {
+            public Runtime.NoneType invoke(Object licensesO, Location loc) {
               try {
                 License license = Type.LICENSE.convert(licensesO, "'licenses' operand");
                 context.pkgBuilder.setDefaultLicense(license);
@@ -746,7 +749,7 @@
                 context.eventHandler.handle(Event.error(loc, e.getMessage()));
                 context.pkgBuilder.setContainsErrors();
               }
-              return Environment.NONE;
+              return Runtime.NONE;
             }
           };
         }
@@ -755,9 +758,12 @@
   /**
    * Returns a function-value implementing "distribs" in the specified package
    * context.
-   * TODO(bazel-team): Remove in favor of package.distribs.
    */
-  @SkylarkSignature(name = "distribs", returnType = Environment.NoneType.class,
+  // TODO(bazel-team): Remove in favor of package.distribs.
+  // TODO(bazel-team): Remove all these new*Function-s and/or have static functions
+  // that consult the context dynamically via getContext(env, ast) since we have that,
+  // and share the functions with the native package... which requires unifying the List types.
+  @SkylarkSignature(name = "distribs", returnType = Runtime.NoneType.class,
       doc = "Declare the distribution(s) for the code in the current package.",
       mandatoryPositionals = {
         @Param(name = "distribution_strings", type = Object.class,
@@ -767,7 +773,7 @@
       new BuiltinFunction.Factory("distribs") {
         public BuiltinFunction create(final PackageContext context) {
           return new BuiltinFunction("distribs", this) {
-            public Environment.NoneType invoke(Object object, Location loc) {
+            public Runtime.NoneType invoke(Object object, Location loc) {
               try {
                 Set<DistributionType> distribs = Type.DISTRIBUTIONS.convert(object,
                     "'distribs' operand");
@@ -776,13 +782,13 @@
                 context.eventHandler.handle(Event.error(loc, e.getMessage()));
                 context.pkgBuilder.setContainsErrors();
               }
-              return Environment.NONE;
+              return Runtime.NONE;
             }
           };
         }
       };
 
-  @SkylarkSignature(name = "package_group", returnType = Environment.NoneType.class,
+  @SkylarkSignature(name = "package_group", returnType = Runtime.NoneType.class,
       doc = "Declare a set of files as exported",
       mandatoryNamedOnly = {
         @Param(name = "name", type = String.class,
@@ -800,7 +806,7 @@
       new BuiltinFunction.Factory("package_group") {
         public BuiltinFunction create() {
           return new BuiltinFunction("package_group", this) {
-            public Environment.NoneType invoke(String name, Object packages, Object includes,
+            public Runtime.NoneType invoke(String name, Object packages, Object includes,
                 FuncallExpression ast, Environment env) throws EvalException, ConversionException {
               return callPackageFunction(name, packages, includes, ast, env);
             }
@@ -808,7 +814,7 @@
         }
       };
 
-  static Environment.NoneType callPackageFunction(String name, Object packagesO, Object includesO,
+  static Runtime.NoneType callPackageFunction(String name, Object packagesO, Object includesO,
       FuncallExpression ast, Environment env) throws EvalException, ConversionException {
     PackageContext context = getContext(env, ast);
 
@@ -820,7 +826,7 @@
     try {
       context.pkgBuilder.addPackageGroup(name, packages, includes, context.eventHandler,
           ast.getLocation());
-      return Environment.NONE;
+      return Runtime.NONE;
     } catch (Label.SyntaxException e) {
       throw new EvalException(ast.getLocation(),
           "package group has invalid name: " + name + ": " + e.getMessage());
@@ -890,7 +896,7 @@
               "at least one argument must be given to the 'package' function");
         }
 
-        return Environment.NONE;
+        return Runtime.NONE;
       }
     };
   }
@@ -937,7 +943,7 @@
       final RuleFactory ruleFactory, final String ruleClass) {
     return new BuiltinFunction(ruleClass, FunctionSignature.KWARGS, BuiltinFunction.USE_AST_ENV) {
       @SuppressWarnings("unchecked")
-      public Environment.NoneType invoke(Map<String, Object> kwargs,
+      public Runtime.NoneType invoke(Map<String, Object> kwargs,
           FuncallExpression ast, Environment env)
           throws EvalException {
         env.checkLoadingPhase(ruleClass, ast.getLocation());
@@ -946,7 +952,7 @@
         } catch (RuleFactory.InvalidRuleException | Package.NameConflictException e) {
           throw new EvalException(ast.getLocation(), e.getMessage());
         }
-        return Environment.NONE;
+        return Runtime.NONE;
       }
     };
   }
@@ -1171,23 +1177,40 @@
     }
   }
 
+  private final ClassObject nativeModule;
+
+  /** @return the Skylark struct to bind to "native" */
+  public ClassObject getNativeModule() {
+    return nativeModule;
+  }
+
   /**
-   * Returns the list of native rule functions created using the {@link RuleClassProvider}
+   * Returns a native module with the functions created using the {@link RuleClassProvider}
    * of this {@link PackageFactory}.
    */
-  public ImmutableList<BaseFunction> collectNativeRuleFunctions() {
-    ImmutableList.Builder<BaseFunction> builder = ImmutableList.builder();
+  private ClassObject newNativeModule() {
+    ImmutableMap.Builder<String, Object> builder = new ImmutableMap.Builder<>();
+    for (String nativeFunction : Runtime.getFunctionNames(SkylarkNativeModule.class)) {
+      builder.put(nativeFunction, Runtime.getFunction(SkylarkNativeModule.class, nativeFunction));
+    }
     for (String ruleClass : ruleFactory.getRuleClassNames()) {
-      builder.add(newRuleFunction(ruleFactory, ruleClass));
+      builder.put(ruleClass, newRuleFunction(ruleFactory, ruleClass));
     }
-    builder.add(newPackageFunction(packageArguments));
+    builder.put("package", newPackageFunction(packageArguments));
     for (EnvironmentExtension extension : environmentExtensions) {
-      builder.addAll(extension.nativeModuleFunctions());
+      for (BaseFunction function : extension.nativeModuleFunctions()) {
+        builder.put(function.getName(), function);
+      }
     }
-    return builder.build();
+    return new ClassObject.SkylarkClassObject(builder.build(), "no native function or rule '%s'");
   }
 
   private void buildPkgEnv(Environment pkgEnv, PackageContext context, RuleFactory ruleFactory) {
+    // TODO(bazel-team): remove the naked functions that are redundant with the nativeModule,
+    // or if not possible, at least make them straight copies from the native module variant.
+    // or better, use a common Environment.Frame for these common bindings
+    // (that shares a backing ImmutableMap for the bindings?)
+    pkgEnv.update("native", nativeModule);
     pkgEnv.update("distribs", newDistribsFunction.apply(context));
     pkgEnv.update("glob", newGlobFunction.apply(context, /*async=*/false));
     pkgEnv.update("mocksubinclude", newMockSubincludeFunction.apply(context));
@@ -1269,7 +1292,7 @@
 
     pkgEnv.setImportedExtensions(imports);
     pkgEnv.updateAndPropagate(PKG_CONTEXT, context);
-    pkgEnv.updateAndPropagate(Environment.PKG_NAME, packageId.toString());
+    pkgEnv.updateAndPropagate(Runtime.PKG_NAME, packageId.toString());
 
     if (!validateAssignmentStatements(pkgEnv, buildFileAST, eventHandler)) {
       pkgBuilder.setContainsErrors();
diff --git a/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java b/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
index ee1fce3..ddbda14 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
@@ -34,12 +34,12 @@
 import com.google.devtools.build.lib.packages.RuleClass.Builder.RuleClassType;
 import com.google.devtools.build.lib.syntax.Argument;
 import com.google.devtools.build.lib.syntax.BaseFunction;
-import com.google.devtools.build.lib.syntax.Environment;
 import com.google.devtools.build.lib.syntax.FragmentClassNameResolver;
 import com.google.devtools.build.lib.syntax.FuncallExpression;
 import com.google.devtools.build.lib.syntax.GlobList;
 import com.google.devtools.build.lib.syntax.Label;
 import com.google.devtools.build.lib.syntax.Label.SyntaxException;
+import com.google.devtools.build.lib.syntax.Runtime;
 import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
 import com.google.devtools.build.lib.util.StringUtil;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -1394,7 +1394,7 @@
     for (Map.Entry<String, Object> entry : attributeValues.entrySet()) {
       String attributeName = entry.getKey();
       Object attributeValue = entry.getValue();
-      if (attributeValue == Environment.NONE) {  // Ignore all None values.
+      if (attributeValue == Runtime.NONE) {  // Ignore all None values.
         continue;
       }
       Integer attrIndex = setRuleAttributeValue(rule, eventHandler, attributeName, attributeValue);
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 1f32cbd..02752f5 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
@@ -20,6 +20,7 @@
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.FuncallExpression;
 import com.google.devtools.build.lib.syntax.GlobList;
+import com.google.devtools.build.lib.syntax.Runtime;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkModule;
 import com.google.devtools.build.lib.syntax.SkylarkSignature;
@@ -73,7 +74,7 @@
   };
 
   @SkylarkSignature(name = "package_group", objectType = SkylarkNativeModule.class,
-      returnType = Environment.NoneType.class,
+      returnType = Runtime.NoneType.class,
       doc = "This function defines a set of packages and assigns a label to the group. "
           + "The label can be referenced in <code>visibility</code> attributes.",
       mandatoryNamedOnly = {
@@ -88,7 +89,7 @@
           doc = "Other package groups that are included in this one.")},
       useAst = true, useEnvironment = true)
   private static final BuiltinFunction packageGroup = new BuiltinFunction("package_group") {
-      public Environment.NoneType invoke(String name, SkylarkList packages, SkylarkList includes,
+      public Runtime.NoneType invoke(String name, SkylarkList packages, SkylarkList includes,
                 FuncallExpression ast, Environment env) throws EvalException, ConversionException {
         env.checkLoadingPhase("native.package_group", ast.getLocation());
         return PackageFactory.callPackageFunction(name, packages, includes, ast, env);
@@ -96,7 +97,7 @@
     };
 
   @SkylarkSignature(name = "exports_files", objectType = SkylarkNativeModule.class,
-      returnType = Environment.NoneType.class,
+      returnType = Runtime.NoneType.class,
       doc = "Specifies a list of files belonging to this package that are exported to other "
           + "packages but not otherwise mentioned.",
       mandatoryPositionals = {
@@ -113,10 +114,10 @@
           doc = "Licenses to be specified.")},
       useAst = true, useEnvironment = true)
   private static final BuiltinFunction exportsFiles = new BuiltinFunction("exports_files") {
-      public Environment.NoneType invoke(SkylarkList srcs, Object visibility, Object licenses,
+      public Runtime.NoneType invoke(SkylarkList srcs, Object visibility, Object licenses,
           FuncallExpression ast, Environment env)
           throws EvalException, ConversionException {
-        env.checkLoadingPhase("native.exports_file", ast.getLocation());
+        env.checkLoadingPhase("native.exports_files", ast.getLocation());
         return PackageFactory.callExportsFiles(srcs, visibility, licenses, ast, env);
       }
     };
diff --git a/src/main/java/com/google/devtools/build/lib/packages/WorkspaceFactory.java b/src/main/java/com/google/devtools/build/lib/packages/WorkspaceFactory.java
index 4a312f7..054865f 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/WorkspaceFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/WorkspaceFactory.java
@@ -14,7 +14,7 @@
 
 package com.google.devtools.build.lib.packages;
 
-import static com.google.devtools.build.lib.syntax.Environment.NONE;
+import static com.google.devtools.build.lib.syntax.Runtime.NONE;
 
 import com.google.devtools.build.lib.cmdline.LabelValidator;
 import com.google.devtools.build.lib.events.Event;
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 635b1ed..75afd45 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
@@ -29,6 +29,7 @@
 import com.google.devtools.build.lib.syntax.EvalUtils;
 import com.google.devtools.build.lib.syntax.FuncallExpression;
 import com.google.devtools.build.lib.syntax.Label;
+import com.google.devtools.build.lib.syntax.Runtime;
 import com.google.devtools.build.lib.syntax.SkylarkCallbackFunction;
 import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
 import com.google.devtools.build.lib.syntax.SkylarkList;
@@ -100,7 +101,7 @@
           + "value is given.";
 
   private static boolean containsNonNoneKey(Map<String, Object> arguments, String key) {
-    return arguments.containsKey(key) && arguments.get(key) != Environment.NONE;
+    return arguments.containsKey(key) && arguments.get(key) != Runtime.NONE;
   }
 
   private static Attribute.Builder<?> createAttribute(
@@ -160,7 +161,7 @@
     }
 
     Object ruleClassesObj = arguments.get(ALLOW_RULES_ARG);
-    if (ruleClassesObj != null && ruleClassesObj != Environment.NONE) {
+    if (ruleClassesObj != null && ruleClassesObj != Runtime.NONE) {
       builder.allowedRuleClasses(
           castList(ruleClassesObj, String.class, "allowed rule classes for attribute definition"));
     }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/SkylarkModules.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkModules.java
index df4876c..c52c58c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkModules.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkModules.java
@@ -16,38 +16,27 @@
 
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.packages.SkylarkNativeModule;
-import com.google.devtools.build.lib.syntax.BaseFunction;
 import com.google.devtools.build.lib.syntax.Environment;
 import com.google.devtools.build.lib.syntax.EvaluationContext;
 import com.google.devtools.build.lib.syntax.MethodLibrary;
+import com.google.devtools.build.lib.syntax.Runtime;
 import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
-import com.google.devtools.build.lib.syntax.SkylarkModule;
-import com.google.devtools.build.lib.syntax.SkylarkSignature;
 import com.google.devtools.build.lib.syntax.ValidationEnvironment;
 
-import java.lang.reflect.Field;
-import java.util.Map;
-
 /**
- * A class to handle all Skylark modules, to create and setup Validation and regular Environments.
+ * The basis for a Skylark Environment with all build-related modules registered.
  */
-// TODO(bazel-team): move that to the syntax package and
-// let each extension register itself in a static { } statement.
-public class SkylarkModules {
+public final class SkylarkModules {
+
+  private SkylarkModules() { }
 
   /**
    * The list of built in Skylark modules.
    * Documentation is generated automatically for all these modules.
-   * They are also registered with the {@link ValidationEnvironment}
-   * and the {@link SkylarkEnvironment}.
-   * Note that only functions with a {@link SkylarkSignature} annotations are handled properly.
+   * They are also registered with the {@link Environment}.
    */
-  // TODO(bazel-team): find a more general, more automated way of registering classes and building
-  // initial environments. And don't give syntax.Environment and packages.MethodLibrary a special
-  // treatment, have them use the same registration mechanism as other classes currently below.
   public static final ImmutableList<Class<?>> MODULES = ImmutableList.of(
       SkylarkAttr.class,
       SkylarkCommandLine.class,
@@ -55,30 +44,6 @@
       SkylarkRuleClassFunctions.class,
       SkylarkRuleImplementationFunctions.class);
 
-  private static final ImmutableMap<Class<?>, ImmutableList<BaseFunction>> FUNCTION_MAP;
-  private static final ImmutableMap<String, Object> OBJECTS;
-
-  static {
-    try {
-      ImmutableMap.Builder<Class<?>, ImmutableList<BaseFunction>> functionMap =
-          ImmutableMap.builder();
-      ImmutableMap.Builder<String, Object> objects = ImmutableMap.builder();
-      for (Class<?> moduleClass : MODULES) {
-        if (moduleClass.isAnnotationPresent(SkylarkModule.class)) {
-          objects.put(moduleClass.getAnnotation(SkylarkModule.class).name(),
-              moduleClass.newInstance());
-        }
-        ImmutableList.Builder<BaseFunction> functions = ImmutableList.builder();
-        collectSkylarkFunctionsAndObjectsFromFields(moduleClass, functions, objects);
-        functionMap.put(moduleClass, functions.build());
-      }
-      FUNCTION_MAP = functionMap.build();
-      OBJECTS = objects.build();
-    } catch (InstantiationException | IllegalAccessException e) {
-      throw new RuntimeException(e);
-    }
-  }
-
   /**
    * Returns a new SkylarkEnvironment with the elements of the Skylark modules.
    */
@@ -96,21 +61,12 @@
 
   private static void setupEnvironment(Environment env) {
     MethodLibrary.setupMethodEnvironment(env);
-    for (Map.Entry<Class<?>, ImmutableList<BaseFunction>> entry : FUNCTION_MAP.entrySet()) {
-      for (BaseFunction function : entry.getValue()) {
-        if (function.getObjectType() != null) {
-          env.registerFunction(function.getObjectType(), function.getName(), function);
-        } else {
-          env.update(function.getName(), function);
-        }
-      }
-    }
-    for (Map.Entry<String, Object> entry : OBJECTS.entrySet()) {
-      env.update(entry.getKey(), entry.getValue());
+    for (Class<?> moduleClass : MODULES) {
+      Runtime.registerModuleGlobals(env, moduleClass);
     }
     // Even though PACKAGE_NAME has no value _now_ and will be bound later,
     // it needs to be visible for the ValidationEnvironment to be happy.
-    env.update(Environment.PKG_NAME, Environment.NONE);
+    env.update(Runtime.PKG_NAME, Runtime.NONE);
   }
 
   /**
@@ -125,31 +81,4 @@
     return EvaluationContext.newSkylarkContext(
         getNewEnvironment(eventHandler), getValidationEnvironment());
   }
-
-  /**
-   * Collects the BaseFunctions from the fields of the class of the object parameter
-   * and adds them into the builder.
-   */
-  private static void collectSkylarkFunctionsAndObjectsFromFields(Class<?> type,
-      ImmutableList.Builder<BaseFunction> functions, ImmutableMap.Builder<String, Object> objects) {
-    try {
-      for (Field field : type.getDeclaredFields()) {
-        if (field.isAnnotationPresent(SkylarkSignature.class)) {
-          // Fields in Skylark modules are sometimes private.
-          // Nevertheless they have to be annotated with SkylarkSignature.
-          field.setAccessible(true);
-          SkylarkSignature annotation = field.getAnnotation(SkylarkSignature.class);
-          Object value = field.get(null);
-          if (BaseFunction.class.isAssignableFrom(field.getType())) {
-            functions.add((BaseFunction) value);
-          } else {
-            objects.put(annotation.name(), value);
-          }
-        }
-      }
-    } catch (IllegalArgumentException | IllegalAccessException e) {
-      // This should never happen.
-      throw new RuntimeException(e);
-    }
-  }
 }
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 1ca229c..4c070b4 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
@@ -68,6 +68,7 @@
 import com.google.devtools.build.lib.syntax.FuncallExpression;
 import com.google.devtools.build.lib.syntax.FunctionSignature;
 import com.google.devtools.build.lib.syntax.Label;
+import com.google.devtools.build.lib.syntax.Runtime;
 import com.google.devtools.build.lib.syntax.SkylarkCallbackFunction;
 import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
 import com.google.devtools.build.lib.syntax.SkylarkList;
@@ -250,7 +251,7 @@
         // We'll set the name later, pass the empty string for now.
         RuleClass.Builder builder = new RuleClass.Builder("", type, true, parent);
 
-        if (attrs != Environment.NONE) {
+        if (attrs != Runtime.NONE) {
           for (Map.Entry<String, Attribute.Builder> attr : castMap(
               attrs, String.class, Attribute.Builder.class, "attrs").entrySet()) {
             Attribute.Builder<?> attrBuilder = (Attribute.Builder<?>) attr.getValue();
@@ -267,7 +268,7 @@
           builder.setOutputsDefaultExecutable();
         }
 
-        if (implicitOutputs != Environment.NONE) {
+        if (implicitOutputs != Runtime.NONE) {
           if (implicitOutputs instanceof BaseFunction) {
             BaseFunction func = (BaseFunction) implicitOutputs;
             final SkylarkCallbackFunction callback =
diff --git a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleConfiguredTargetBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleConfiguredTargetBuilder.java
index a7c9b4f..409b408 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleConfiguredTargetBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/SkylarkRuleConfiguredTargetBuilder.java
@@ -34,10 +34,10 @@
 import com.google.devtools.build.lib.syntax.BaseFunction;
 import com.google.devtools.build.lib.syntax.ClassObject;
 import com.google.devtools.build.lib.syntax.ClassObject.SkylarkClassObject;
-import com.google.devtools.build.lib.syntax.Environment;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.EvalExceptionWithStackTrace;
 import com.google.devtools.build.lib.syntax.EvalUtils;
+import com.google.devtools.build.lib.syntax.Runtime;
 import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.syntax.SkylarkType;
@@ -64,7 +64,7 @@
 
       if (ruleContext.hasErrors()) {
         return null;
-      } else if (!(target instanceof SkylarkClassObject) && target != Environment.NONE) {
+      } else if (!(target instanceof SkylarkClassObject) && target != Runtime.NONE) {
         ruleContext.ruleError("Rule implementation doesn't return a struct");
         return null;
       } else if (!expectFailure.isEmpty()) {
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 dbaf2c8..bf11515 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
@@ -44,10 +44,10 @@
 import com.google.devtools.build.lib.shell.ShellUtils;
 import com.google.devtools.build.lib.shell.ShellUtils.TokenizationException;
 import com.google.devtools.build.lib.syntax.ClassObject.SkylarkClassObject;
-import com.google.devtools.build.lib.syntax.Environment;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.FuncallExpression.FuncallException;
 import com.google.devtools.build.lib.syntax.Label;
+import com.google.devtools.build.lib.syntax.Runtime;
 import com.google.devtools.build.lib.syntax.SkylarkCallable;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkModule;
@@ -159,7 +159,7 @@
         if (artifacts.size() == 1) {
           addOutput(outputsBuilder, attrName, Iterables.getOnlyElement(artifacts));
         } else {
-          addOutput(outputsBuilder, attrName, Environment.NONE);
+          addOutput(outputsBuilder, attrName, Runtime.NONE);
         }
       } else if (type == Type.OUTPUT_LIST) {
         addOutput(outputsBuilder, attrName,
@@ -182,7 +182,7 @@
       Type<?> type = a.getType();
       Object val = ruleContext.attributes().get(a.getName(), type);
       if (type != Type.LABEL && type != Type.LABEL_LIST) {
-        attrBuilder.put(a.getPublicName(), val == null ? Environment.NONE
+        attrBuilder.put(a.getPublicName(), val == null ? Runtime.NONE
             // Attribute values should be type safe
             : SkylarkType.convertToSkylark(val, null));
         continue;
@@ -197,7 +197,7 @@
           executableBuilder.put(skyname, executable);
           executableRunfilesbuilder.put(executable, provider);
         } else {
-          executableBuilder.put(skyname, Environment.NONE);
+          executableBuilder.put(skyname, Runtime.NONE);
         }
       }
       if (a.isSingleArtifact()) {
@@ -206,7 +206,7 @@
         if (artifact != null) {
           fileBuilder.put(skyname, artifact);
         } else {
-          fileBuilder.put(skyname, Environment.NONE);
+          fileBuilder.put(skyname, Runtime.NONE);
         }
       }
       filesBuilder.put(skyname, ruleContext.getPrerequisiteArtifacts(a.getName(), mode).list());
@@ -214,7 +214,7 @@
       if (type == Type.LABEL) {
         Object prereq = ruleContext.getPrerequisite(a.getName(), mode);
         if (prereq == null) {
-          prereq = Environment.NONE;
+          prereq = Runtime.NONE;
         }
         attrBuilder.put(skyname, prereq);
       } else {
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 fb53cfd..b6417d4 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
@@ -47,10 +47,10 @@
 import com.google.devtools.build.lib.packages.Type.ConversionException;
 import com.google.devtools.build.lib.syntax.BuiltinFunction;
 import com.google.devtools.build.lib.syntax.Environment;
-import com.google.devtools.build.lib.syntax.Environment.NoneType;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.syntax.EvalUtils;
 import com.google.devtools.build.lib.syntax.Label;
+import com.google.devtools.build.lib.syntax.Runtime;
 import com.google.devtools.build.lib.syntax.SkylarkList;
 import com.google.devtools.build.lib.syntax.SkylarkNestedSet;
 import com.google.devtools.build.lib.syntax.SkylarkSignature;
@@ -90,7 +90,7 @@
       doc = "Creates an action that runs an executable or a shell command. You must specify either "
         + "<code>command</code> or <code>executable</code>.",
       objectType = SkylarkRuleContext.class,
-      returnType = Environment.NoneType.class,
+      returnType = Runtime.NoneType.class,
       mandatoryPositionals = {
         @Param(name = "self", type = SkylarkRuleContext.class, doc = "This RuleContext.")},
       mandatoryNamedOnly = {
@@ -128,7 +128,7 @@
             + "they are typicially generated by the command_helper")},
       useLocation = true)
   private static final BuiltinFunction createSpawnAction = new BuiltinFunction("action") {
-    public Environment.NoneType invoke(
+    public Runtime.NoneType invoke(
         SkylarkRuleContext ctx,
         SkylarkList outputs,
         SkylarkList inputs,
@@ -144,7 +144,7 @@
         Location loc) throws EvalException, ConversionException {
       SpawnAction.Builder builder = new SpawnAction.Builder();
       // TODO(bazel-team): builder still makes unnecessary copies of inputs, outputs and args.
-      boolean hasCommand = commandO != Environment.NONE;
+      boolean hasCommand = commandO != Runtime.NONE;
       Iterable<Artifact> actualInputs = castList(inputs, Artifact.class);
 
       builder.addInputs(actualInputs);
@@ -157,7 +157,7 @@
         builder.addArgument("");
       }
       builder.addArguments(castList(arguments, String.class));
-      if (executableO != Environment.NONE) {
+      if (executableO != Runtime.NONE) {
         if (executableO instanceof Artifact) {
           Artifact executable = (Artifact) executableO;
           builder.addInput(executable);
@@ -174,7 +174,7 @@
               + "executable but got " + EvalUtils.getDataTypeName(executableO) + " instead");
         }
       }
-      if ((commandO == Environment.NONE) == (executableO == Environment.NONE)) {
+      if ((commandO == Runtime.NONE) == (executableO == Runtime.NONE)) {
         throw new EvalException(loc, "You must specify either 'command' or 'executable' argument");
       }
       if (hasCommand) {
@@ -196,24 +196,24 @@
         // HOST configuration to the action as a precaution.
         addRequiredIndirectRunfiles(ctx, builder);
       }
-      if (mnemonicO != Environment.NONE) {
+      if (mnemonicO != Runtime.NONE) {
         builder.setMnemonic((String) mnemonicO);
       }
-      if (envO != Environment.NONE) {
+      if (envO != Runtime.NONE) {
         builder.setEnvironment(ImmutableMap.copyOf(
             castMap(envO, String.class, String.class, "env")));
       }
-      if (progressMessage != Environment.NONE) {
+      if (progressMessage != Runtime.NONE) {
         builder.setProgressMessage((String) progressMessage);
       }
       if (EvalUtils.toBoolean(useDefaultShellEnv)) {
         builder.useDefaultShellEnvironment();
       }
-      if (executionRequirementsO != Environment.NONE) {
+      if (executionRequirementsO != Runtime.NONE) {
         builder.setExecutionInfo(ImmutableMap.copyOf(castMap(
             executionRequirementsO, String.class, String.class, "execution_requirements")));
       }
-      if (inputManifestsO != Environment.NONE) {
+      if (inputManifestsO != Runtime.NONE) {
         for (Map.Entry<PathFragment, Artifact> entry : castMap(inputManifestsO,
             PathFragment.class, Artifact.class, "input manifest file map").entrySet()) {
           builder.addInputManifest(entry.getValue(), entry.getKey());
@@ -221,7 +221,7 @@
       }
       // Always register the action
       ctx.getRuleContext().registerAction(builder.build(ctx.getRuleContext()));
-      return Environment.NONE;
+      return Runtime.NONE;
     }
   };
 
@@ -322,7 +322,7 @@
       doc =
       "Creates an empty action that neither executes a command nor produces any "
       + "output, but that is useful for inserting 'extra actions'.",
-      objectType = SkylarkRuleContext.class, returnType = NoneType.class,
+      objectType = SkylarkRuleContext.class, returnType = Runtime.NoneType.class,
       mandatoryPositionals = {
           @Param(name = "self", type = SkylarkRuleContext.class, doc = "this context"),
       },
@@ -336,7 +336,7 @@
       })
   private static final BuiltinFunction createEmptyAction = new BuiltinFunction("empty_action") {
     @SuppressWarnings("unused")
-    public NoneType invoke(SkylarkRuleContext ctx, String mnemonic, SkylarkList inputs)
+    public Runtime.NoneType invoke(SkylarkRuleContext ctx, String mnemonic, SkylarkList inputs)
         throws EvalException, ConversionException {
       RuleContext ruleContext = ctx.getRuleContext();
       Action action = new PseudoAction<SpawnInfo>(generateUuid(ruleContext),
@@ -344,7 +344,7 @@
           mnemonic, SpawnInfo.spawnInfo, createEmptySpawnInfo());
       ruleContext.registerAction(action);
 
-      return Environment.NONE;
+      return Runtime.NONE;
     }
 
     private NestedSet<Artifact> convertInputs(SkylarkList inputs) {
@@ -436,7 +436,7 @@
         Class<? extends TransitiveInfoProvider> convertedClass =
             classType.asSubclass(TransitiveInfoProvider.class);
         Object result = target.getProvider(convertedClass);
-        return result == null ? Environment.NONE : result;
+        return result == null ? Runtime.NONE : result;
       } catch (ExecutionException e) {
         throw new EvalException(loc, "Unknown class type " + type);
       } catch (ClassCastException e) {
@@ -482,7 +482,7 @@
       if (!files.isEmpty()) {
         builder.addArtifacts(castList(files, Artifact.class));
       }
-      if (transitiveFiles != Environment.NONE) {
+      if (transitiveFiles != Runtime.NONE) {
         builder.addTransitiveArtifacts(((SkylarkNestedSet) transitiveFiles).getSet(Artifact.class));
       }
       return builder.build();
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunction.java
index 52a0c49..1eb86cd 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkylarkImportLookupFunction.java
@@ -22,10 +22,8 @@
 import com.google.devtools.build.lib.packages.BuildFileNotFoundException;
 import com.google.devtools.build.lib.packages.PackageFactory;
 import com.google.devtools.build.lib.packages.RuleClassProvider;
-import com.google.devtools.build.lib.packages.SkylarkNativeModule;
 import com.google.devtools.build.lib.rules.SkylarkRuleClassFunctions;
 import com.google.devtools.build.lib.skyframe.ASTFileLookupValue.ASTLookupInputException;
-import com.google.devtools.build.lib.syntax.BaseFunction;
 import com.google.devtools.build.lib.syntax.BuildFileAST;
 import com.google.devtools.build.lib.syntax.Label;
 import com.google.devtools.build.lib.syntax.Label.SyntaxException;
@@ -46,12 +44,12 @@
 public class SkylarkImportLookupFunction implements SkyFunction {
 
   private final RuleClassProvider ruleClassProvider;
-  private final ImmutableList<BaseFunction> nativeRuleFunctions;
+  private final PackageFactory packageFactory;
 
   public SkylarkImportLookupFunction(
-      RuleClassProvider ruleClassProvider, PackageFactory packageFactory) {
+    RuleClassProvider ruleClassProvider, PackageFactory packageFactory) {
     this.ruleClassProvider = ruleClassProvider;
-    this.nativeRuleFunctions = packageFactory.collectNativeRuleFunctions();
+    this.packageFactory = packageFactory;
   }
 
   @Override
@@ -181,12 +179,7 @@
     // the transitive closure of the accessible AST nodes.
     SkylarkEnvironment extensionEnv = ruleClassProvider
         .createSkylarkRuleClassEnvironment(eventHandler, ast.getContentHashCode());
-    // Adding native rules module for build extensions.
-    // TODO(bazel-team): this might not be the best place to do this.
-    for (BaseFunction function : nativeRuleFunctions) {
-        extensionEnv.registerFunction(
-            SkylarkNativeModule.class, function.getName(), function);
-    }
+    extensionEnv.update("native", packageFactory.getNativeModule());
     extensionEnv.setImportedExtensions(importMap);
     ast.exec(extensionEnv, eventHandler);
     SkylarkRuleClassFunctions.exportRuleFunctions(extensionEnv, file);
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Environment.java b/src/main/java/com/google/devtools/build/lib/syntax/Environment.java
index 3b4342a..f16d35e 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Environment.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Environment.java
@@ -17,8 +17,6 @@
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableSet;
-import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -38,45 +36,8 @@
  */
 public class Environment {
 
-  @SkylarkSignature(name = "True", returnType = Boolean.class,
-      doc = "Literal for the boolean true.")
-  private static final Boolean TRUE = true;
-
-  @SkylarkSignature(name = "False", returnType = Boolean.class,
-      doc = "Literal for the boolean false.")
-  private static final Boolean FALSE = false;
-
-  @SkylarkSignature(name = "PACKAGE_NAME", returnType = String.class,
-      doc = "The name of the package the rule or build extension is called from. "
-          + "For example, in the BUILD file <code>some/package/BUILD</code>, its value "
-          + "will be <code>some/package</code>. "
-          + "This variable is special, because its value comes from outside of the extension "
-          + "module (it comes from the BUILD file), so it can only be accessed in functions "
-          + "(transitively) called from BUILD files. For example:<br>"
-          + "<pre class=language-python>def extension():\n"
-          + "  return PACKAGE_NAME</pre>"
-          + "In this case calling <code>extension()</code> works from the BUILD file (if the "
-          + "function is loaded), but not as a top level function call in the extension module.")
-  public static final String PKG_NAME = "PACKAGE_NAME";
-
-  /**
-   * There should be only one instance of this type to allow "== None" tests.
-   */
-  @Immutable
-  public static final class NoneType {
-    @Override
-    public String toString() { return "None"; }
-    private NoneType() {}
-  }
-
-  @SkylarkSignature(name = "None", returnType = NoneType.class, doc = "Literal for the None value.")
-  public static final NoneType NONE = new NoneType();
-
   protected final Map<String, Object> env = new HashMap<>();
 
-  // BaseFunctions with namespaces. Works only in the global environment.
-  protected final Map<Class<?>, Map<String, BaseFunction>> functions = new HashMap<>();
-
   /**
    * The parent environment. For Skylark it's the global environment,
    * used for global read only variable lookup.
@@ -178,9 +139,9 @@
     // In Python 2.x, True and False are global values and can be redefined by the user.
     // In Python 3.x, they are keywords. We implement them as values, for the sake of
     // simplicity. We define them as Boolean objects.
-    update("False", FALSE);
-    update("True", TRUE);
-    update("None", NONE);
+    update("False", Runtime.FALSE);
+    update("True", Runtime.TRUE);
+    update("None", Runtime.NONE);
   }
 
   public boolean isSkylark() {
@@ -341,54 +302,6 @@
   }
 
   /**
-   * Registers a function with namespace to this global environment.
-   */
-  public void registerFunction(Class<?> nameSpace, String name, BaseFunction function) {
-    nameSpace = getCanonicalRepresentation(nameSpace);
-    Preconditions.checkArgument(parent == null);
-    if (!functions.containsKey(nameSpace)) {
-      functions.put(nameSpace, new HashMap<String, BaseFunction>());
-    }
-    functions.get(nameSpace).put(name, function);
-  }
-
-  private Map<String, BaseFunction> getNamespaceFunctions(Class<?> nameSpace) {
-    nameSpace = getCanonicalRepresentation(nameSpace);
-    Environment topLevel = this;
-    while (topLevel.parent != null) {
-      topLevel = topLevel.parent;
-    }
-    return topLevel.functions.get(nameSpace);
-  }
-
-  /**
-   * Returns the canonical representation of the given class, i.e. the super class for which any
-   * functions were registered.
-   *
-   * <p>Currently, this is only necessary for mapping the different subclasses of {@link
-   * java.util.Map} to the interface.
-   */
-  private Class<?> getCanonicalRepresentation(Class<?> clazz) {
-    return Map.class.isAssignableFrom(clazz) ? Map.class : clazz;
-  }
-
-  /**
-   * Returns the function of the namespace of the given name or null of it does not exists.
-   */
-  public BaseFunction getFunction(Class<?> nameSpace, String name) {
-    Map<String, BaseFunction> nameSpaceFunctions = getNamespaceFunctions(nameSpace);
-    return nameSpaceFunctions != null ? nameSpaceFunctions.get(name) : null;
-  }
-
-  /**
-   * Returns the function names registered with the namespace.
-   */
-  public Set<String> getFunctionNames(Class<?> nameSpace) {
-    Map<String, BaseFunction> nameSpaceFunctions = getNamespaceFunctions(nameSpace);
-    return nameSpaceFunctions != null ? nameSpaceFunctions.keySet() : ImmutableSet.<String>of();
-  }
-
-  /**
    * Return the current stack trace (list of functions).
    */
   public ImmutableList<BaseFunction> getStackTrace() {
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 e16ffa2..ca5f468 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
@@ -274,7 +274,8 @@
       return "int";
     } else if (c.equals(Boolean.class)) {
       return "bool";
-    } else if (c.equals(Void.TYPE) || c.equals(Environment.NoneType.class)) {
+    } else if (c.equals(Void.TYPE) || c.equals(Runtime.NoneType.class)) {
+      // TODO(bazel-team): no one should be seeing Void at all.
       return "NoneType";
     } else if (List.class.isAssignableFrom(c)) {
       // NB: the capital here is a subtle way to distinguish java Tuple and java List
@@ -292,6 +293,7 @@
     } else if (c.equals(SelectorValue.class)) {
       return "select";
     } else if (NestedSet.class.isAssignableFrom(c) || SkylarkNestedSet.class.isAssignableFrom(c)) {
+      // TODO(bazel-team): no one should be seeing naked NestedSet at all.
       return "set";
     } else if (ClassObject.SkylarkClassObject.class.isAssignableFrom(c)) {
       return "struct";
@@ -332,7 +334,7 @@
    * http://docs.python.org/2/library/stdtypes.html#truth-value-testing
    */
   public static boolean toBoolean(Object o) {
-    if (o == null || o == Environment.NONE) {
+    if (o == null || o == Runtime.NONE) {
       return false;
     } else if (o instanceof Boolean) {
       return (Boolean) o;
@@ -415,7 +417,7 @@
 
   /** @return true if x is Java null or Skylark None */
   public static boolean isNullOrNone(Object x) {
-    return x == null || x == Environment.NONE;
+    return x == null || x == Runtime.NONE;
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java b/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
index 73e8d10..e09dc2a 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/FuncallExpression.java
@@ -317,11 +317,11 @@
       method.setAccessible(true);
       Object result = method.invoke(obj, args);
       if (method.getReturnType().equals(Void.TYPE)) {
-        return Environment.NONE;
+        return Runtime.NONE;
       }
       if (result == null) {
         if (methodDescriptor.getAnnotation().allowReturnNones()) {
-          return Environment.NONE;
+          return Runtime.NONE;
         } else {
           throw new EvalException(loc,
               "Method invocation returned None, please contact Skylark developers: " + methodName
@@ -507,7 +507,7 @@
     // MethodLibrary.
     // For other classes, we can call the Java methods.
     BaseFunction function =
-        env.getFunction(EvalUtils.getSkylarkType(objValue.getClass()), func.getName());
+        Runtime.getFunction(EvalUtils.getSkylarkType(objValue.getClass()), func.getName());
     if (function != null) {
       if (!isNamespace(objValue.getClass())) {
         // Add self as an implicit parameter in front.
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 93a01e9..ef958d3 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
@@ -90,7 +90,7 @@
     return str.substring(start, stop);
   }
 
-  public static int getListIndex(Object key, int listSize, Location loc)
+  private static int getListIndex(Object key, int listSize, Location loc)
       throws ConversionException, EvalException {
     // Get the nth element in the list
     int index = Type.INTEGER.convert(key, "index operand");
@@ -583,7 +583,7 @@
         @Param(name = "end", type = Integer.class, noneable = true, defaultValue = "None",
             doc = "optional position at which to stop comparing.")})
   private static BuiltinFunction endswith = new BuiltinFunction(
-      "endswith", SkylarkList.tuple(0, Environment.NONE)) {
+      "endswith", SkylarkList.tuple(0, Runtime.NONE)) {
     public Boolean invoke(String self, String sub, Integer start, Object end)
         throws ConversionException {
       return pythonSubstring(self, start, end, "'end' operand of 'endswith'").endsWith(sub);
@@ -658,38 +658,57 @@
   };
 
   // slice operator
-  @SkylarkSignature(
-    name = "$slice",
-    documented = false,
-    mandatoryPositionals = {
-      @Param(name = "self", type = Object.class, doc = "This string, list or tuple."),
-      @Param(name = "start", type = Integer.class, doc = "start position of the slice."),
-      @Param(name = "end", type = Integer.class, doc = "end position of the slice.")
-    },
-    doc = "x[<code>start</code>:<code>end</code>] returns a slice or a list slice.",
-    useLocation = true,
-    useEnvironment = true
-  )
-  private static BuiltinFunction slice =
-      new BuiltinFunction("$slice") {
-        public Object invoke(
-            Object self, Integer left, Integer right, Location loc, Environment env)
-            throws EvalException, ConversionException {
-          // Substring
-          if (self instanceof String) {
-            return pythonSubstring((String) self, left, right, "");
-          }
+  @SkylarkSignature(name = "$slice", objectType = String.class,
+      documented = false,
+      mandatoryPositionals = {
+        @Param(name = "self", type = String.class, doc = "This string."),
+        @Param(name = "start", type = Integer.class, doc = "start position of the slice."),
+        @Param(name = "end", type = Integer.class, doc = "end position of the slice.")},
+      doc = "x[<code>start</code>:<code>end</code>] returns a slice or a list slice.")
+  private static BuiltinFunction stringSlice = new BuiltinFunction("$slice") {
+    public Object invoke(String self, Integer left, Integer right)
+        throws EvalException, ConversionException {
+      return pythonSubstring(self, left, right, "");
+    }
+  };
 
-          // List slice
-          List<Object> list = Type.OBJECT_LIST.convert(self, "list operand");
-          left = clampIndex(left, list.size());
-          right = clampIndex(right, list.size());
-          if (left > right) {
-            left = right;
-          }
-          return convert(list.subList(left, right), env, loc);
-        }
-      };
+  @SkylarkSignature(name = "$slice", objectType = List.class,
+      documented = false,
+      mandatoryPositionals = {
+        @Param(name = "self", type = List.class, doc = "This list or tuple."),
+        @Param(name = "start", type = Integer.class, doc = "start position of the slice."),
+        @Param(name = "end", type = Integer.class, doc = "end position of the slice.")},
+      doc = "x[<code>start</code>:<code>end</code>] returns a slice or a list slice.")
+  private static BuiltinFunction listSlice = new BuiltinFunction("$slice") {
+    public Object invoke(List<Object> self, Integer left, Integer right)
+        throws EvalException, ConversionException {
+      return sliceList(self, left, right);
+    }
+  };
+
+  @SkylarkSignature(name = "$slice", objectType = SkylarkList.class,
+      documented = false,
+      mandatoryPositionals = {
+        @Param(name = "self", type = SkylarkList.class, doc = "This list or tuple."),
+        @Param(name = "start", type = Integer.class, doc = "start position of the slice."),
+        @Param(name = "end", type = Integer.class, doc = "end position of the slice.")},
+      doc = "x[<code>start</code>:<code>end</code>] returns a slice or a list slice.",
+      useLocation = true)
+  private static BuiltinFunction skylarkListSlice = new BuiltinFunction("$slice") {
+    public Object invoke(SkylarkList self, Integer left, Integer right,
+        Location loc) throws EvalException, ConversionException {
+      return SkylarkList.list(sliceList(self.toList(), left, right), loc);
+    }
+  };
+
+  private static List<Object> sliceList(List<Object> list, Integer left, Integer right) {
+    left = clampIndex(left, list.size());
+    right = clampIndex(right, list.size());
+    if (left > right) {
+      left = right;
+    }
+    return list.subList(left, right);
+  }
 
   // supported list methods
   @SkylarkSignature(
@@ -720,7 +739,8 @@
   // This function has a SkylarkSignature but is only used by the Build language, not Skylark.
   @SkylarkSignature(
     name = "append",
-    returnType = Environment.NoneType.class,
+    objectType = List.class,
+    returnType = Runtime.NoneType.class,
     documented = false,
     doc = "Adds an item to the end of the list.",
     mandatoryPositionals = {
@@ -729,83 +749,123 @@
       @Param(name = "item", type = Object.class, doc = "Item to add at the end.")
     },
     useLocation = true,
-    useEnvironment = true
-  )
+    useEnvironment = true)
   private static BuiltinFunction append =
       new BuiltinFunction("append") {
-        public Environment.NoneType invoke(
-            List<Object> self, Object item, Location loc, Environment env)
-            throws EvalException, ConversionException {
+        public Runtime.NoneType invoke(List<Object> self, Object item,
+            Location loc, Environment env) throws EvalException, ConversionException {
+          if (env.isSkylark()) {
+            throw new EvalException(loc,
+                "function 'append' is not available in Skylark");
+          }
+          if (EvalUtils.isTuple(self)) {
+            throw new EvalException(loc,
+                "function 'append' is not defined on object of type 'Tuple'");
+          }
           self.add(item);
-          return Environment.NONE;
+          return Runtime.NONE;
         }
       };
 
   // This function has a SkylarkSignature but is only used by the Build language, not Skylark.
-  @SkylarkSignature(name = "extend", returnType = Environment.NoneType.class, documented = false,
-      doc = "Adds all items to the end of the list.",
-      mandatoryPositionals = {
-        // we use List rather than SkylarkList because this is actually for use *outside* Skylark
-        @Param(name = "self", type = List.class, doc = "This list."),
-        @Param(name = "items", type = List.class, doc = "Items to add at the end.")},
-        useLocation = true, useEnvironment = true)
-  private static BuiltinFunction extend = new BuiltinFunction("extend") {
-    public Environment.NoneType invoke(List<Object> self, List<Object> items,
-        Location loc, Environment env) throws EvalException, ConversionException {
-      self.addAll(items);
-      return Environment.NONE;
-    }
-  };
+  @SkylarkSignature(
+    name = "extend",
+    objectType = List.class,
+    returnType = Runtime.NoneType.class,
+    documented = false,
+    doc = "Adds all items to the end of the list.",
+    mandatoryPositionals = {
+      // we use List rather than SkylarkList because this is actually for use *outside* Skylark
+      @Param(name = "self", type = List.class, doc = "This list."),
+      @Param(name = "items", type = List.class, doc = "Items to add at the end.")},
+    useLocation = true,
+    useEnvironment = true)
+  private static BuiltinFunction extend =
+      new BuiltinFunction("extend") {
+        public Runtime.NoneType invoke(List<Object> self, List<Object> items,
+            Location loc, Environment env) throws EvalException, ConversionException {
+          if (env.isSkylark()) {
+            throw new EvalException(loc,
+                "function 'append' is not available in Skylark");
+          }
+          if (EvalUtils.isTuple(self)) {
+            throw new EvalException(loc,
+                "function 'extend' is not defined on object of type 'Tuple'");
+          }
+          self.addAll(items);
+          return Runtime.NONE;
+        }
+      };
 
   // dictionary access operator
-  @SkylarkSignature(name = "$index", documented = false,
-      doc = "Returns the nth element of a list or string, "
-          + "or looks up a value in a dictionary.",
+  @SkylarkSignature(name = "$index", documented = false, objectType = Map.class,
+      doc = "Looks up a value in a dictionary.",
       mandatoryPositionals = {
-        @Param(name = "self", type = Object.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)
   private static BuiltinFunction indexOperator = new BuiltinFunction("$index") {
-    public Object invoke(Object self, Object key,
+    public Object invoke(Map<?, ?> self, Object key,
         Location loc) throws EvalException, ConversionException {
-      if (self instanceof SkylarkList) {
-        SkylarkList list = (SkylarkList) self;
-        if (list.isEmpty()) {
-          throw new EvalException(loc, "List is empty");
-        }
-        int index = getListIndex(key, list.size(), loc);
-        return list.get(index);
-
-      } else if (self instanceof Map<?, ?>) {
-        Map<?, ?> dictionary = (Map<?, ?>) self;
-        if (!dictionary.containsKey(key)) {
-          throw new EvalException(loc, Printer.format("Key %r not found in dictionary", key));
-        }
-        return dictionary.get(key);
-
-      } else if (self instanceof List<?>) {
-        List<Object> list = Type.OBJECT_LIST.convert(self, "index operand");
-        if (list.isEmpty()) {
-          throw new EvalException(loc, "List is empty");
-        }
-        int index = getListIndex(key, list.size(), loc);
-        return list.get(index);
-
-      } else if (self instanceof String) {
-        String str = (String) self;
-        int index = getListIndex(key, str.length(), loc);
-        return str.substring(index, index + 1);
-
-      } else {
-        // TODO(bazel-team): This is dead code, get rid of it.
-        throw new EvalException(loc, String.format(
-            "Unsupported datatype (%s) for indexing, only works for dict and list",
-            EvalUtils.getDataTypeName(self)));
+      if (!self.containsKey(key)) {
+        throw new EvalException(loc, Printer.format("Key %r not found in dictionary", key));
       }
+      return self.get(key);
     }
   };
 
-  @SkylarkSignature(name = "values", objectType = DictModule.class,
+  // list access operator
+  @SkylarkSignature(name = "$index", documented = false, objectType = SkylarkList.class,
+      doc = "Returns the nth element of a list.",
+      mandatoryPositionals = {
+        @Param(name = "self", type = SkylarkList.class, doc = "This object."),
+        @Param(name = "key", type = Object.class, doc = "The index or key to access.")},
+      useLocation = true)
+  private static BuiltinFunction skylarkListIndexOperator = new BuiltinFunction("$index") {
+    public Object invoke(SkylarkList self, Object key,
+        Location loc) throws EvalException, ConversionException {
+      if (self.isEmpty()) {
+        throw new EvalException(loc, "List is empty");
+      }
+      int index = getListIndex(key, self.size(), loc);
+      return self.get(index);
+    }
+  };
+
+
+  // list access operator
+  @SkylarkSignature(name = "$index", documented = false, objectType = List.class,
+      doc = "Returns the nth element of a list.",
+      mandatoryPositionals = {
+        @Param(name = "self", type = List.class, doc = "This object."),
+        @Param(name = "key", type = Object.class, doc = "The index or key to access.")},
+      useLocation = true)
+  private static BuiltinFunction listIndexOperator = new BuiltinFunction("$index") {
+    public Object invoke(List<?> self, Object key,
+        Location loc) throws EvalException, ConversionException {
+      if (self.isEmpty()) {
+        throw new EvalException(loc, "List is empty");
+      }
+      int index = getListIndex(key, self.size(), loc);
+      return self.get(index);
+    }
+  };
+
+  @SkylarkSignature(name = "$index", documented = false, objectType = String.class,
+      doc = "Returns the nth element of a string.",
+      mandatoryPositionals = {
+        @Param(name = "self", type = String.class, doc = "This string."),
+        @Param(name = "key", type = Object.class, doc = "The index or key to access.")},
+      useLocation = true)
+  private static BuiltinFunction stringIndexOperator = new BuiltinFunction("$index") {
+    public Object invoke(String self, Object key,
+        Location loc) throws EvalException, ConversionException {
+      int index = getListIndex(key, self.length(), loc);
+      return self.substring(index, index + 1);
+    }
+  };
+
+  @SkylarkSignature(name = "values", objectType = Map.class,
       returnType = HackHackEitherList.class,
       doc = "Return the list of values. Dictionaries are always sorted by their keys:"
           + "<pre class=\"language-python\">"
@@ -821,7 +881,7 @@
     }
   };
 
-  @SkylarkSignature(name = "items", objectType = DictModule.class,
+  @SkylarkSignature(name = "items", objectType = Map.class,
       returnType = HackHackEitherList.class,
       doc = "Return the list of key-value tuples. Dictionaries are always sorted by their keys:"
           + "<pre class=\"language-python\">"
@@ -840,11 +900,11 @@
         List<?> item = ImmutableList.of(entries.getKey(), entries.getValue());
         list.add(env.isSkylark() ? SkylarkList.tuple(item) : item);
       }
-        return convert(list, env, loc);
-      }
-    };
+      return convert(list, env, loc);
+    }
+  };
 
-  @SkylarkSignature(name = "keys", objectType = DictModule.class,
+  @SkylarkSignature(name = "keys", objectType = Map.class,
       returnType = HackHackEitherList.class,
       doc = "Return 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]"
@@ -861,7 +921,7 @@
     }
   };
 
-  @SkylarkSignature(name = "get", objectType = DictModule.class,
+  @SkylarkSignature(name = "get", objectType = Map.class,
       doc = "Return 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.",
@@ -893,7 +953,8 @@
 
   // unary minus
   @SkylarkSignature(name = "-", returnType = Integer.class,
-      documented = false, doc = "Unary minus operator.",
+      documented = false,
+      doc = "Unary minus operator.",
       mandatoryPositionals = {
         @Param(name = "num", type = Integer.class, doc = "The number to negate.")})
   private static BuiltinFunction minus = new BuiltinFunction("-") {
@@ -1089,7 +1150,7 @@
     }
   };
 
-  @SkylarkSignature(name = "enumerate",  returnType = HackHackEitherList.class,
+  @SkylarkSignature(name = "enumerate", returnType = HackHackEitherList.class,
       doc = "Return a list of pairs (two-element tuples), with the index (int) and the item from"
           + " the input list.\n<pre class=\"language-python\">"
           + "enumerate([24, 21, 84]) == [(0, 24), (1, 21), (2, 84)]</pre>\n",
@@ -1137,7 +1198,7 @@
         throws EvalException, ConversionException, InterruptedException {
       int start;
       int stop;
-      if (stopOrNone == Environment.NONE) {
+      if (stopOrNone == Runtime.NONE) {
         start = 0;
         stop = startOrStop;
       } else {
@@ -1194,7 +1255,7 @@
       if (obj instanceof ClassObject && ((ClassObject) obj).getValue(name) != null) {
         return true;
       }
-      if (env.getFunctionNames(obj.getClass()).contains(name)) {
+      if (Runtime.getFunctionNames(obj.getClass()).contains(name)) {
         return true;
       }
 
@@ -1226,7 +1287,7 @@
         Location loc) throws EvalException, ConversionException {
       Object result = DotExpression.eval(obj, name, loc);
       if (result == null) {
-        if (defaultValue != Environment.NONE) {
+        if (defaultValue != Runtime.NONE) {
           return defaultValue;
         } else {
           throw new EvalException(loc, Printer.format("Object of type '%s' has no attribute %r",
@@ -1250,7 +1311,7 @@
       if (object instanceof ClassObject) {
         fields.addAll(((ClassObject) object).getKeys());
       }
-      fields.addAll(env.getFunctionNames(object.getClass()));
+      fields.addAll(Runtime.getFunctionNames(object.getClass()));
       try {
         fields.addAll(FuncallExpression.getMethodNames(object.getClass()));
       } catch (ExecutionException e) {
@@ -1274,7 +1335,7 @@
   @SkylarkSignature(name = "fail",
       doc = "Raises an error that cannot be intercepted. It can be used anywhere, "
           + "both in the loading phase and in the analysis phase.",
-      returnType = Environment.NoneType.class,
+      returnType = Runtime.NoneType.class,
       mandatoryPositionals = {
         @Param(name = "msg", type = String.class, doc = "Error message to display for the user")},
       optionalPositionals = {
@@ -1284,16 +1345,16 @@
                + "error reporting.")},
       useLocation = true)
   private static final BuiltinFunction fail = new BuiltinFunction("fail") {
-    public Environment.NoneType invoke(String msg, Object attr,
+    public Runtime.NoneType invoke(String msg, Object attr,
         Location loc) throws EvalException, ConversionException {
-      if (attr != Environment.NONE) {
+      if (attr != Runtime.NONE) {
         msg = String.format("attribute %s: %s", attr, msg);
       }
       throw new EvalException(loc, msg);
     }
   };
 
-  @SkylarkSignature(name = "print", returnType = Environment.NoneType.class,
+  @SkylarkSignature(name = "print", returnType = Runtime.NoneType.class,
       doc = "Prints <code>msg</code> to the console.",
       optionalNamedOnly = {
         @Param(name = "sep", type = String.class, defaultValue = "' '",
@@ -1302,7 +1363,7 @@
       extraPositionals = {@Param(name = "args", doc = "The objects to print.")},
       useLocation = true, useEnvironment = true)
   private static final BuiltinFunction print = new BuiltinFunction("print") {
-    public Environment.NoneType invoke(String sep, SkylarkList starargs,
+    public Runtime.NoneType invoke(String sep, SkylarkList starargs,
         Location loc, SkylarkEnvironment env) throws EvalException {
       String msg = Joiner.on(sep).join(Iterables.transform(starargs,
               new com.google.common.base.Function<Object, String>() {
@@ -1311,7 +1372,7 @@
                   return Printer.str(input);
                 }}));
       env.handleEvent(Event.warn(loc, msg));
-      return Environment.NONE;
+      return Runtime.NONE;
     }
   };
 
@@ -1373,7 +1434,7 @@
       + "x = [s for s in \"abc\"]  # x == [\"a\", \"b\", \"c\"]</pre>\n"
       + "Implicit concatenation of strings is not allowed; use the <code>+</code> "
       + "operator instead.")
-  public static final class StringModule {}
+  static final class StringModule {}
 
   /**
    * Skylark Dict module.
@@ -1397,82 +1458,23 @@
       + "Example:<br>"
       + "<pre class=\"language-python\">\"a\" in {\"a\" : 2, \"b\" : 5}   # evaluates as True"
       + "</pre>")
-  public static final class DictModule {}
+  static final class DictModule {}
 
-  public static final List<BaseFunction> stringFunctions =
-      ImmutableList.<BaseFunction>of(
-          capitalize,
-          count,
-          endswith,
-          find,
-          index,
-          format,
-          join,
-          lower,
-          partition,
-          replace,
-          rfind,
-          rindex,
-          rpartition,
-          rsplit,
-          slice,
-          split,
-          startswith,
-          strip,
-          title,
-          upper);
-
-  public static final List<BaseFunction> listPureFunctions = ImmutableList.<BaseFunction>of(
-      slice);
-
-  public static final List<BaseFunction> listFunctions = ImmutableList.<BaseFunction>of(
-      append, extend);
-
-  public static final List<BaseFunction> setFunctions = ImmutableList.<BaseFunction>of(union);
-
-  public static final List<BaseFunction> dictFunctions = ImmutableList.<BaseFunction>of(
-      items, get, keys, values);
-
-  private static final List<BaseFunction> pureGlobalFunctions = ImmutableList.<BaseFunction>of(
+  static final List<BaseFunction> buildGlobalFunctions = ImmutableList.<BaseFunction>of(
       bool, dict, enumerate, int_, len, list, minus, range, repr, select, sorted, str, zip);
 
-  private static final List<BaseFunction> skylarkGlobalFunctions =
+  static final List<BaseFunction> skylarkGlobalFunctions =
       ImmutableList.<BaseFunction>builder()
-      .addAll(pureGlobalFunctions)
+      .addAll(buildGlobalFunctions)
       .add(dir, fail, getattr, hasattr, print, set, struct, type)
       .build();
 
+
   /**
    * Set up a given environment for supported class methods.
    */
   public static void setupMethodEnvironment(Environment env) {
-    env.registerFunction(Map.class, indexOperator.getName(), indexOperator);
-    setupMethodEnvironment(env, Map.class, dictFunctions);
-    env.registerFunction(String.class, indexOperator.getName(), indexOperator);
-    setupMethodEnvironment(env, String.class, stringFunctions);
-    setupMethodEnvironment(env, List.class, listPureFunctions);
-    setupMethodEnvironment(env, SkylarkList.class, listPureFunctions);
-    setupMethodEnvironment(env, SkylarkNestedSet.class, setFunctions);
-    // TODO(bazel-team): Simplify when list types are unified.
-    env.registerFunction(SkylarkList.class, indexOperator.getName(), indexOperator);
-    env.registerFunction(List.class, indexOperator.getName(), indexOperator);
-    env.registerFunction(ImmutableList.class, indexOperator.getName(), indexOperator);
-
-    if (env.isSkylark()) {
-      setupMethodEnvironment(env, skylarkGlobalFunctions);
-    } else {
-      // TODO(bazel-team): listFunctions are not allowed in Skylark extensions (use += instead).
-      // It is allowed in BUILD files only for backward-compatibility.
-      setupMethodEnvironment(env, List.class, listFunctions);
-      setupMethodEnvironment(env, pureGlobalFunctions);
-    }
-  }
-
-  private static void setupMethodEnvironment(
-      Environment env, Class<?> nameSpace, Iterable<BaseFunction> functions) {
-    for (BaseFunction function : functions) {
-      env.registerFunction(nameSpace, function.getName(), function);
-    }
+    setupMethodEnvironment(env, env.isSkylark() ? skylarkGlobalFunctions : buildGlobalFunctions);
   }
 
   private static void setupMethodEnvironment(Environment env, Iterable<BaseFunction> functions) {
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Printer.java b/src/main/java/com/google/devtools/build/lib/syntax/Printer.java
index 7e5e9e0..4792b25 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Printer.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Printer.java
@@ -114,7 +114,7 @@
     } else if (o instanceof Integer || o instanceof Double) {
       append(buffer, o.toString());
 
-    } else if (o == Environment.NONE) {
+    } else if (o == Runtime.NONE) {
       append(buffer, "None");
 
     } else if (o == Boolean.TRUE) {
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
new file mode 100644
index 0000000..50ef2546
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Runtime.java
@@ -0,0 +1,176 @@
+// Copyright 2015 Google Inc. 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.base.Preconditions;
+import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
+
+import java.lang.reflect.Field;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * Global constants and support for global namespaces of runtime functions.
+ */
+public final class Runtime {
+
+  private Runtime() {}
+
+  @SkylarkSignature(name = "True", returnType = Boolean.class,
+      doc = "Literal for the boolean true.")
+  static final Boolean TRUE = true;
+
+  @SkylarkSignature(name = "False", returnType = Boolean.class,
+      doc = "Literal for the boolean false.")
+  static final Boolean FALSE = false;
+
+  /**
+   * There should be only one instance of this type to allow "== None" tests.
+   */
+  @Immutable
+  public static final class NoneType {
+    @Override
+    public String toString() { return "None"; }
+    private NoneType() {}
+  }
+
+  @SkylarkSignature(name = "None", returnType = NoneType.class,
+      doc = "Literal for the None value.")
+  public static final NoneType NONE = new NoneType();
+
+
+  @SkylarkSignature(name = "PACKAGE_NAME", returnType = String.class,
+      doc = "The name of the package the rule or build extension is called from. "
+          + "For example, in the BUILD file <code>some/package/BUILD</code>, its value "
+          + "will be <code>some/package</code>. "
+          + "This variable is special, because its value comes from outside of the extension "
+          + "module (it comes from the BUILD file), so it can only be accessed in functions "
+          + "(transitively) called from BUILD files. For example:<br>"
+          + "<pre class=language-python>def extension():\n"
+          + "  return PACKAGE_NAME</pre>"
+          + "In this case calling <code>extension()</code> works from the BUILD file (if the "
+          + "function is loaded), but not as a top level function call in the extension module.")
+  public static final String PKG_NAME = "PACKAGE_NAME";
+
+  /**
+   * Set up a given environment for supported class methods.
+   */
+  static Environment setupConstants(Environment env) throws EvalException {
+    // In Python 2.x, True and False are global values and can be redefined by the user.
+    // In Python 3.x, they are keywords. We implement them as values, for the sake of
+    // simplicity. We define them as Boolean objects.
+    return env.update("False", FALSE).update("True", TRUE).update("None", NONE);
+  }
+
+
+  /** Global registry of functions associated to a class or namespace */
+  private static final Map<Class<?>, Map<String, BaseFunction>> functions = new HashMap<>();
+
+  /**
+   * Registers a function with namespace to this global environment.
+   */
+  public static void registerFunction(Class<?> nameSpace, BaseFunction function) {
+    Preconditions.checkNotNull(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.
+   *
+   * <p>Currently, this is only necessary for mapping the different subclasses of {@link
+   * java.util.Map} to the interface.
+   */
+  public static Class<?> getCanonicalRepresentation(Class<?> clazz) {
+    if (Map.class.isAssignableFrom(clazz)) {
+      return MethodLibrary.DictModule.class;
+    }
+    if (String.class.isAssignableFrom(clazz)) {
+      return MethodLibrary.StringModule.class;
+    }
+    if (List.class.isAssignableFrom(clazz)) {
+      return List.class;
+    }
+    return clazz;
+  }
+
+  /**
+   * Registers global fields with SkylarkSignature into the specified Environment.
+   * @param env the Environment into which to register fields.
+   * @param moduleClass the Class object containing globals.
+   */
+  public static void registerModuleGlobals(Environment env, Class<?> moduleClass) {
+    try {
+      if (moduleClass.isAnnotationPresent(SkylarkModule.class)) {
+        env.update(
+            moduleClass.getAnnotation(SkylarkModule.class).name(), moduleClass.newInstance());
+      }
+      for (Field field : moduleClass.getDeclaredFields()) {
+        if (field.isAnnotationPresent(SkylarkSignature.class)) {
+          // Fields in Skylark modules are sometimes private.
+          // Nevertheless they have to be annotated with SkylarkSignature.
+          field.setAccessible(true);
+          SkylarkSignature annotation = field.getAnnotation(SkylarkSignature.class);
+          Object value = field.get(null);
+          // Ignore function factories and non-global functions
+          if (!(value instanceof BuiltinFunction.Factory
+              || (value instanceof BaseFunction
+                  && !annotation.objectType().equals(Object.class)))) {
+            env.update(annotation.name(), value);
+          }
+        }
+      }
+    } catch (IllegalAccessException | InstantiationException e) {
+      throw new AssertionError(e);
+    }
+  }
+
+  /**
+   * Returns the function of the namespace of the given name or null of it does not exists.
+   */
+  public static BaseFunction getFunction(Class<?> nameSpace, String name) {
+    Map<String, BaseFunction> nameSpaceFunctions = getNamespaceFunctions(nameSpace);
+    return nameSpaceFunctions != null ? nameSpaceFunctions.get(name) : null;
+  }
+
+  /**
+   * Returns the function names registered with the namespace.
+   */
+  public static Set<String> getFunctionNames(Class<?> nameSpace) {
+    Map<String, BaseFunction> nameSpaceFunctions = getNamespaceFunctions(nameSpace);
+    return nameSpaceFunctions != null ? nameSpaceFunctions.keySet() : ImmutableSet.<String>of();
+  }
+
+  static void setupMethodEnvironment(
+      Environment env, Iterable<BaseFunction> functions) throws EvalException {
+    for (BaseFunction function : functions) {
+      env.update(function.getName(), function);
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkEnvironment.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkEnvironment.java
index cc23817..bbf8be7 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkEnvironment.java
@@ -23,7 +23,6 @@
 
 import java.io.Serializable;
 import java.util.HashSet;
-import java.util.Map;
 import java.util.Map.Entry;
 import java.util.Set;
 
@@ -125,9 +124,6 @@
     for (Entry<String, Object> entry : env.entrySet()) {
       newEnv.env.put(entry.getKey(), entry.getValue());
     }
-    for (Map.Entry<Class<?>, Map<String, BaseFunction>> functionMap : functions.entrySet()) {
-      newEnv.functions.put(functionMap.getKey(), functionMap.getValue());
-    }
     return newEnv;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java
index d114dc7..bf3c832 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkSignatureProcessor.java
@@ -202,7 +202,7 @@
     if (iterator != null) {
       return iterator.next();
     } else if (param.defaultValue().isEmpty()) {
-      return Environment.NONE;
+      return Runtime.NONE;
     } else {
       try {
         return EvaluationContext.SKYLARK_INITIALIZATION.evalExpression(param.defaultValue());
@@ -258,6 +258,12 @@
             if (!function.isConfigured()) {
               function.configure(annotation);
             }
+            Class<?> nameSpace = function.getObjectType();
+            if (nameSpace != null) {
+              Preconditions.checkState(!(function instanceof BuiltinFunction.Factory));
+              nameSpace = Runtime.getCanonicalRepresentation(nameSpace);
+              Runtime.registerFunction(nameSpace, function);
+            }
           }
         } catch (IllegalAccessException e) {
           throw new RuntimeException(String.format(
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 020cc8c..96aaaa9 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
@@ -152,7 +152,7 @@
   // by declaring its type as TOP instead of NONE, even though at runtime,
   // we reject None from all types but NONE, and in particular from e.g. lists of Files.
   // TODO(bazel-team): resolve this inconsistency, one way or the other.
-  public static final Simple NONE = Simple.of(Environment.NoneType.class);
+  public static final Simple NONE = Simple.of(Runtime.NoneType.class);
 
   private static final class Global {}
   /** The STRING type, for strings */
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java b/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java
index f9719ae..360688d 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/UserDefinedFunction.java
@@ -80,7 +80,7 @@
     } finally {
       Profiler.instance().logSimpleTask(startTimeProfiler, ProfilerTask.SKYLARK_USER_FN, getName());
     }
-    return Environment.NONE;
+    return Runtime.NONE;
   }
 
   /**