Index: src/org/python/core/PyFrozenSet.java
===================================================================
--- src/org/python/core/PyFrozenSet.java	(revision 4416)
+++ src/org/python/core/PyFrozenSet.java	(working copy)
@@ -1,5 +1,7 @@
 package org.python.core;
 
+import java.math.BigInteger;
+
 import org.python.expose.ExposedMethod;
 import org.python.expose.ExposedNew;
 import org.python.expose.ExposedType;
@@ -23,18 +25,35 @@
     }
 
     @ExposedNew
-    @ExposedMethod
-    final void frozenset___init__(PyObject[] args, String[] kwds) {
-        int nargs = args.length - kwds.length;
-        if (nargs > 1) {
-            throw PyBuiltinFunction.DefaultInfo.unexpectedCall(nargs, false, "FrozenSet", 0, 1);
+    public static PyObject frozenset___new__(PyNewWrapper new_, boolean init, PyType subtype,
+            PyObject[] args, String[] keywords) {
+    	
+        ArgParser ap = new ArgParser("frozenset", args, keywords, new String[] {"iterable"}, 0);
+        PyObject iterable = ap.getPyObject(0, null);
+    	PyFrozenSet fset = null;
+    	
+        if (new_.for_type == subtype) {
+        	if (iterable == null) {
+        		fset = Py.EmptyFrozenSet;
+        	} else if (iterable.getClass() == PyFrozenSet.class) {
+        		fset = (PyFrozenSet) iterable;
+        	} else {
+        		fset = new PyFrozenSet(iterable);
+        		if (fset.__len__() == 0) {
+        			fset = Py.EmptyFrozenSet;
+        		}
+        	}
+        } else {
+        	fset = new PyFrozenSetDerived(subtype);
+        	if (iterable != null) {
+        		fset._update(iterable);
+        	}
+            if (init) {
+            	((PyFrozenSetDerived)fset).dispatch__init__(subtype, args, keywords);
+            }
         }
-        if (nargs == 0) {
-            return;
-        }
 
-        PyObject o = args[0];
-        _update(o);
+        return fset;
     }
 
     @ExposedMethod(type = MethodType.BINARY)
@@ -114,6 +133,10 @@
 
     @ExposedMethod
     final PyObject frozenset_copy() {
+    	if (getClass() == PyFrozenSet.class) {
+    		return this;
+    	}
+    	// subclasses should revert to normal behavior of creating a new instance
         return baseset_copy();
     }
 
@@ -159,11 +182,11 @@
 
     @ExposedMethod
     final int frozenset___hash__() {
-        return hashCode();
+        return this._set.hashCode();
     }
 
     public int hashCode() {
-        return this._set.hashCode();
+        return frozenset___hash__();
     }
 
     public PyObject _as_immutable() {
Index: src/org/python/core/PySet.java
===================================================================
--- src/org/python/core/PySet.java	(revision 4416)
+++ src/org/python/core/PySet.java	(working copy)
@@ -1,6 +1,7 @@
 package org.python.core;
 
 import java.util.Iterator;
+import java.util.NoSuchElementException;
 
 import org.python.expose.ExposedMethod;
 import org.python.expose.ExposedNew;
@@ -35,6 +36,7 @@
             return;
         }
 
+        this._set.clear();
         PyObject o = args[0];
         _update(o);
     }
@@ -213,12 +215,7 @@
 
     @ExposedMethod
     final void set_add(PyObject o) {
-        try {
-            this._set.add(o);
-        } catch (PyException e) {
-            PyObject immutable = this.asImmutable(e, o);
-            this._set.add(immutable);
-        }
+        this._set.add(o);
     }
 
     @ExposedMethod
@@ -231,7 +228,7 @@
             b = this._set.remove(immutable);
         }
         if (!b) {
-            throw new PyException(Py.LookupError, o.toString());
+            throw new PyException(Py.KeyError, o);
         }
     }
 
@@ -248,9 +245,13 @@
     @ExposedMethod
     final PyObject set_pop() {
         Iterator iterator = this._set.iterator();
-        Object first = iterator.next();
-        this._set.remove(first);
-        return (PyObject) first;
+        try {
+        	Object first = iterator.next();
+            this._set.remove(first);
+            return (PyObject) first;
+        } catch (NoSuchElementException e) {
+        	throw new PyException(Py.KeyError, "pop from an empty set");
+        }
     }
 
     @ExposedMethod
Index: src/org/python/core/BaseSet.java
===================================================================
--- src/org/python/core/BaseSet.java	(revision 4416)
+++ src/org/python/core/BaseSet.java	(working copy)
@@ -45,17 +45,13 @@
      * @throws PyIgnoreMethodTag Ignore.
      */
     protected void _update(PyObject data) throws PyIgnoreMethodTag {
-        if(data instanceof BaseSet) {
+        if (data instanceof BaseSet) {
             // Skip the iteration if both are sets
             this._set.addAll(((BaseSet)data)._set);
             return;
         }
         for (PyObject item : data.asIterable()) {
-            try {
-                this._set.add(item);
-            } catch (PyException e) {
-                this._set.add(asImmutable(e, item));
-            }
+            this._set.add(item);
         }
     }
 
@@ -125,7 +121,7 @@
     final PyObject baseset_difference(PyObject other) {
         BaseSet bs = (other instanceof BaseSet) ? (BaseSet) other : new PySet(other);
         Set set = bs._set;
-        BaseSet o = (BaseSet) this.getType().__call__();
+        BaseSet o = BaseSet.makeNewSet(getType());
         for (Object p : this._set) {
             if (!set.contains(p)) {
                 o._set.add(p);
@@ -161,7 +157,7 @@
 
     public PyObject baseset_symmetric_difference(PyObject other) {
         BaseSet bs = (other instanceof BaseSet) ? (BaseSet) other : new PySet(other);
-        BaseSet o = (BaseSet) this.getType().__call__();
+        BaseSet o = BaseSet.makeNewSet(getType());
         for (Object p : this._set) {
             if (!bs._set.contains(p)) {
                 o._set.add(p);
@@ -227,7 +223,12 @@
     }
 
     final boolean baseset___contains__(PyObject other) {
-        return this._set.contains(other);
+    	try {
+    		return this._set.contains(other);
+	    } catch (PyException e) {
+	        PyObject immutable = this.asImmutable(e, other);
+	        return this._set.contains(immutable);
+	    }
     }
 
     public int __cmp__(PyObject other) {
@@ -322,7 +323,7 @@
     final PyObject baseset___deepcopy__(PyObject memo) {
         PyObject copy = __builtin__.__import__("copy");
         PyObject deepcopy = copy.__getattr__("deepcopy");
-        BaseSet result = (BaseSet) this.getType().__call__();
+        BaseSet result = BaseSet.makeNewSet(getType());
         memo.__setitem__(Py.newInteger(Py.id(this)), result);
         for (Object p : this._set) {
             result._set.add(deepcopy.__call__(Py.java2py(p), memo));
@@ -344,13 +345,12 @@
     }
 
     public PyObject baseset_union(PyObject other) {
-        BaseSet result = (BaseSet) this.getType().__call__(this);
+        BaseSet result = BaseSet.makeNewSet(getType(), this);
         result._update(other);
         return result;
     }
 
     public PyObject baseset_intersection(PyObject other) {
-
         PyObject little, big;
         if(!(other instanceof BaseSet)) {
             other = new PySet(other);
@@ -365,12 +365,11 @@
         }
 
         PyObject common = __builtin__.filter(big.__getattr__("__contains__"), little);
-        return other.getType().__call__(common);
+        return BaseSet.makeNewSet(getType(), common);
     }
 
     public PyObject baseset_copy() {
-        BaseSet copy = (BaseSet) this.getType().__call__();
-        copy._set = (HashSet) this._set.clone();
+        BaseSet copy = BaseSet.makeNewSet(getType(), this);
         return copy;
     }
 
@@ -428,6 +427,10 @@
     /**
      * If the exception <code>e</code> is a <code>TypeError</code>, attempt to convert
      * the object <code>value</code> into an ImmutableSet.
+     * 
+     * This is better than special-casing behavior based on isinstance, because a Python
+     * subclass can override, say, __hash__ and all of a sudden you can't assume that
+     * a non-PyFrozenSet is unhashable anymore.
      *
      * @param e     The exception thrown from a hashable operation.
      * @param value The object which was unhashable.
@@ -443,7 +446,41 @@
         throw e;
     }
 
-//    public int size() {
+    /**
+     * Create a new set of type.
+     *
+     * @param type a set type
+     * @return a new set
+     */
+    protected static BaseSet makeNewSet(PyType type) {
+        return makeNewSet(type, null);
+    }
+ 
+    /**
+     * Create a new <et of type from iterable.
+     *
+     * @param type a set type
+     * @param iterable an iterable or null
+     * @return a new set
+     */
+    protected static BaseSet makeNewSet(PyType type, PyObject iterable) {
+        BaseSet so;
+        if (type == PySet.TYPE) {
+            so = new PySet();
+        } else if (type == PyFrozenSet.TYPE) {
+            so = new PyFrozenSet();
+        } else if (Py.isSubClass(type, PySet.TYPE)) {
+            so = new PySetDerived(type);
+        } else {
+            so = new PyFrozenSetDerived(type);
+        }
+        if (iterable != null) {
+            so._update(iterable);
+        }
+        return so;
+    }
+
+ //    public int size() {
 //        return this._set.size();
 //    }
 //
Index: src/org/python/core/PySystemState.java
===================================================================
--- src/org/python/core/PySystemState.java	(revision 4416)
+++ src/org/python/core/PySystemState.java	(working copy)
@@ -549,6 +549,7 @@
         Py.EmptyObjects = new PyObject[0];
 
         Py.EmptyTuple = new PyTuple(Py.EmptyObjects);
+        Py.EmptyFrozenSet = new PyFrozenSet();
         Py.NoConversion = new PySingleton("Error");
         Py.Ellipsis = new PyEllipsis();
 
Index: src/org/python/core/Py.java
===================================================================
--- src/org/python/core/Py.java	(revision 4416)
+++ src/org/python/core/Py.java	(working copy)
@@ -61,6 +61,9 @@
     /** A zero-length array of PyObject's to pass to functions that
         expect zero-arguments **/
     public static PyObject[] EmptyObjects;
+    
+    /** A frozenset with zero elements **/
+    public static PyFrozenSet EmptyFrozenSet;
 
     /** A tuple with zero elements **/
     public static PyTuple EmptyTuple;