Implementing precursor in Python

 

 

In Part 1 of this series I explained why the Python interpretation of super() is flawed and how it limits the user of super() to carefully controlled situations.  In Part 2, I discussed the theoretical principles behind super(), and how it can be implemented in Python based on these principles.

The sample implementation uses inspection to find out the required information about the caller of the precursor(), precursor_of(), and static_super() functions.  This is inefficient, but is easily implemented using available Python features.  A better implementation, like that of the existing super(), would be done in the Python compiler.

 This post explains the sample implementation; if you are familiar with the Python compiler, I would like to encourage you to  create an implementation that is as fast as super().

We start with the best version (the one that best fits the theoretical principles), which is the precursor, in https://github.com/yishaif/parseltongue/blob/main/extensions/super/precursor.py.

Assuming that the precursor call was made according to the rules, from a method of some class, where the method overrides an implementation in one or more superclasses, we need to find which is the class in which the method that called precursor was implemented.  This is complicated by the fact that the method implementation may be overridden in one or more subclasses, so we can't access the method implementation from the target object (that would give us the method implementation that is first on the MRO list).  The only way to get this information (without delving into the compiler) is to use runtime inspection of the call stack.

This is done by the function find_static_caller.  It first inspects the calling frame, which it gets as an argument.  (This is computed in the function precursor, using the expression inspect.getouterframes(inspect.currentframe())[1].)  The calling frame is the one corresponding to the calling method.  From that frame we extract the compiled code, the method name, and the actual arguments passed to the method.  As a sanity check, we assert that there is at least one argument, which would be the target of the call (usually, but not necessarily, called self).  The most tricky part is finding the particular method implementation that called precursor.  This is done by looping over the MRO to find an implementation of the same method (by name) whose compiled code is identical to the code object we extracted from the calling frame.  If we find it, we return the method target (as a convenience), and, more importantly, the calling class.  If we don't find the calling class, we fail with an exception.

The precursor function uses this information to find the superclass implementation that needs to be called.  It does this by getting the list of base classes of the calling class, verifying that there is only one base class, and calling the method implementation in that superclass.  The method may or may not have been defined in that class; if it hasn't, the method implementation called with be the same one that would be called on an object of that base class.

If there are multiple base classes, precursor_of must be called instead of precursor, to provide an explicit superclass whose implementation is to be called.  The details are similar to that of precursor, except that precursor_of checks that its argument is indeed a class that is a superclass of the calling class, and returns a function that calls the method implementation in the specified class.

As I said in Part 2 of this series, it is wrong to call a different method from a middle class in the hierarchy; only the implementation belonging to the actual class of the target object can be responsible for maintaining the method contract.  However, if you really want to do that (at your own risk!), you can use the implementation of static_super in https://github.com/yishaif/parseltongue/blob/main/extensions/super/static_super.py.

This implementation is similar to that of precursor.  However, instead of directly calling the precursor method, it needs to return an object on which you can call the method of your choice.  This object will belong to the SuperCaller class.  This class is initialized by with the target object and the superclass containing the implementation of the method to be called.  When a method is invoked on that object, the __getattr__ method will be called to find the implementation, since this class has no regular methods.  This method attempts to find such an implementation in the given superclass (using the expression getattr(self.cls, method)), and, if successful, returns a function that will invoke this implementation with the given target object and any other arguments it is given (this uses the convenience function functools.partial).

What's Wrong with Python's super()?

This is Part 1: the problem.

Jump to Part 2: the solution.

Jump to Part 3: the implementation.

 

#Inheritance is one of the basic mechanisms of object-oriented programming.  Loosely speaking, it allows a subclass to extend the behavior of one or more superclasses by adding fields and overriding methods.  Often, the extended functionality of a method is quite similar to the version in the superclass being overridden; in such cases, it makes sense to utilize the original version rather than copying its code to the subclass.  However, the normal method-calling mechanism in most object-oriented languages (C++ being a notable exception) is dynamic binding, in which the implementation of a method chosen by the run-time system is based on the actual type of the receiver object, rather than its declared type (which may be a supertype of the actual type).  It is therefore necessary to provide a special mechanism to call the overridden implementation, and this is called super in many languages, including Java and #Python.

This is a relatively simple mechanism in languages (such as Java) that only support single inheritance, but things get more complex in languages (such as Python) with multiple inheritance.

As an example, consider a set of classes that represent elements of a document, such as headings, paragraphs, lists, and so on.  The top of the inheritance hierarchy could be a class called DocumentElement.  Classes such as Document, Heading, Paragraph, and List would inherit from DocumentElement.

Some document elements contain other elements; for example, a heading (such as a chapter or a section) contains the elements under that heading, and a list contains the list items.  In addition, we may want to endow some document elements with associated properties.  We can use two mixin classes to selectively make document elements containers or property owners; these could be classes such as:

class ContainerMixin:
    def __init__(self):
        self.contents = []

    def add_contents(self, *contents):
        self.contents.extend(contents)


class PropertyMixin:
    def __init__(self):
        self.properties = {}

    def add_properties(self, **properties):
        self.properties.update(properties)

If a document is supposed to have both contents and properties, the class would be declared like this:

class Document(DocumentElement,
               ContainerMixin,
               PropertyMixin):
    def __init__(self):
        super().__init__()

Since neither ContainerMixin nor PropertyMixin have any superclasses other than the default object, you would think that they don't need to call super().__init__(), right?  Wrong!  The super().__init__() call in Document calls the __init__ method of ContainerMixin, but the __init__ method of PropertyMixin will not be called, and its properties field will not be initialized.  This will happen if
the __init__ method of ContainerMixin calls super().__init__(); that call will invoke the __init__ method of PropertyMixin, even though PropertyMixin is not a superclass of ContainerMixin , or in any way related to it.  This is surprising to those used to other languages, such as Java, in which a super call always invokes a method of a superclass.

The Python super() function actually returns a proxy object, which contains the list of superclasses of the receiver object; this is sorted according to the Method Resolution Order, or MRO.  Method calls on this object will invoke the specified method implementations in the MRO classes, in order.  Because the actual object on which the original method is called can belong to any subclass of Document, even those defined later, and this subclass may inherit from arbitrary additional classes, it is impossible to predict what will be called when you write the code for any potential superclass.  This seems to imply that you must always call super().__init__() (or any other method), unless you know your class will never be subclassed.

Unfortunately, this won't work in general.  Suppose, for example, that the __init__ methods of the mixin classes take arguments:

class ContainerMixin:
    def __init__(self, *contents):
       self.contents = contents

class PropertyMixin:
    def __init__(self, **properties):
        self.properties = properties

We may decide to ignore these, since all are optional, but this may not be true in general.  What can we do if we want to accept the contents and properties arguments in the Document class and pass each to the appropriate mixin?

There is a workaround, but it doesn't work all cases.  The trick is to use the 2-argument form of super().  The first argument is one of the receiver object's superclasses, and the second is the object itself.  When using this form of super(), the implementation that will be invoked for the method call will be the one from the class that follows the given superclass on the MRO list.  The code will look like this:

class Document(DocumentElement,
               ContainerMixin,
               PropertyMixin):
    def __init__(self, *contents, **properties):
        super().__init__(*contents)
        super(ContainerMixin, self).__init__(**properties)

The first super() call, without arguments, will call the first __init__ method of the first superclass on the MRO (that is, one that follows the Document class itself) that provides such a method.  If you execute the command print(Document.__mro__), you will see the following output:

(<class '__main__.Document'>,
 <class '__main__.DocumentElement'>,
 <class '__main__.ContainerMixin'>,
 <class '__main__.PropertyMixin'>,
 <class 'object'>)

The first superclass is DocumentElement, which has no __init__ method.  The following one is ContainerMixin, which does, and therefore this is the implementation invoked, with the arguments from contents.

The second super call has ContainerMixin as its first argument.  The implementation invoked is therefore searched on the MRO starting with the following class, PropertyMixin, and this indeed accepts the properties argument.

This behavior means that the first super call could also have been written as:
        super(DocumentElement, self).__init__(*contents)

The reason that Python searches the MRO from the class after the one given as the first argument is to make it easy to invoke the default behavior by using the actual class of the object as the first argument.  Indeed, before Python 3, super required at least one argument, and so this was the common pattern.  The first super call in our example would have had to be written this way:

super(Document, self).__init__(*contents)

Note that this assumes that the actual type of the object is Document, but in fact it could be any subtype of this class, in which case the MRO will be different, with different classes following DocumentElement and ContainerMixin on it.  For example, if SomeMixin has an __init__ method that doesn't call super, the following class definition will not call PropertyMixin.__init__():

class MyDocument(Document, SomeMixin, PropertyMixin):
    pass

This definition has the effect of putting SomeMixin before PropertyMixin in the MRO of MyDocument,  so that the call super(ContainerMixin, self).__init__(**properties) in Document actually calls the __init__ method of SomeMixin, not that of PropertyMixin.

This may seem strange: why put PropertyMixin in the superclass list at all, given that Document already inherits from it?  But sometimes this is necessary in order to give precedence to methods of one class over another.

This behavior is unpredictable, and therefore dangerous, from the point of view of the developer who writes the super() call.  While the developers of a class must know the internals of all classes they inherit from, they have no way of knowing anything about subclasses of their class; such subclasses may be created at any future time by other people.

All the examples above used the __init__ method,  but, of course, the same issues apply to any method of the class.

Because of these issues, you will find a lot of opinions that state that classes must be designed together in order to make the correct use super() possible by subclasses.  Some will tell you that all superclasses that are designed to work together must have exactly the same signature for each method; others recommend using the most permissive signature (*args, **kwargs), and passing all arguments to all super methods.  Each of these has its own issues, and in any case severely limit the design if super() is to be supported.

The upshot of this is that the super mechanism in Python is flawed because it is unpredictable.  It is impossible in general to guarantee the behavior we want using this mechanism.  This stems from the absence of a good theoretical basis for this implementation of the super feature.

What is a sound theoretical basis?  I have mentioned Design by Contract in several previous posts, and it also explains how super calls need to be treated.  More on this in the next post!

Functional Programming in Mainstream Languages, Part 7: Higher-Order Functions in Haskell

(Jump to Table of Contents)

I will finish the survey of higher-order functions in mainstream languages with Haskell, a fully-functional language.  (There's a lot of talk about the imperative features of Haskell, but don't let that mislead you; Haskell is truly functional.)  Haskell comes from a different tradition, and its notation may take some getting used to.  However, if you are really into functional programming, you can do amazing things with very short Haskell programs, which (unlike APL, for example) are still comprehensible if you understand the idioms.

Of all the languages I surveyed before, Scala is closest in spirit to Haskell, so I will contrast Haskell with Scala instead of Java 8 as I've been doing before.  Unlike all other examples we saw before, type declarations in Haskell are separate from value definitions, and are optional in most cases, since the compiler performs extensive type inference.  In all the examples below I will give the type declarations explicitly, but they are not required.  In fact, the way I produced them was by copying them from the compiler warnings.  They are shown in a different color to emphasize the fact that you don't need to write them yourself.

In Haskell, curried functions are the norm, and the syntax makes it easiest to write curried functions.  In fact, each function in Haskell always has a single argument, although it is possible to simulate multiple arguments using tuples, as I will show below.  But first, here is the curried version:

Scala

def makeAdder = (x: Int) => (y: Int) => x + y def increment = makeAdder(1) def res = increment(4)

Haksell

makeAdder :: (Num a) => a -> a -> a makeAdder x y = x + y increment :: (Num a) => a -> a increment = makeAdder 1 res :: Integer res = increment 4

The most striking syntactic feature is that function arguments do not need to be enclosed in parentheses.  This is actually the norm in the lambda calculus and derivative notations, and is very convenient given that each function can only have a single argument.  It is possible to use lambda notation (which we will see below) to define makeAdder, but it isn't necessary in this case.

The makeAdder function in Haskell, unlike all the other examples we saw before, is exactly equivalent to the function +; both are curried and take one argument.  Thus, the above code is equivalent to the following:

Haksell

increment :: (Num a) => a -> a increment = (+) 1 res :: Integer res = increment 4

The parentheses around the plus symbol are required since by default Haskell binary operators use the common mathematical notation where they have two arguments surrounding the operator symbol.  (This is just syntax, it doesn't change the fact that the functions are curried.)

Looking at the types, from the simplest (the last) to the most complicated (the first), we see that the type of res is simply Integer.  However, if we give increment an argument of a different type, the result will be the corresponding type:

Haksell

real :: Double real = increment 0.5

This is possible since the type of the increment function is parameterized.  Before the double arrow (=>) is a type constraint; we'll look at that in a minute.  The type of increment is a -> a, where a is a type parameter.  This means that the function takes one argument of type a, and returns a result of the same type.  However, the function applies the + operator to its argument (indirectly through makeAdder), and therefore the type a must be appropriate as an argument to +.  This is the purpose of the type constraint (Num a); it restricts a to be a numeric type, which (among other operations) supports +.

Both Integer and Double are numeric types, so the type of increment includes both Integer -> Integer and Double -> Double.  When functions of such parameterized types are applied to actual arguments, it may be possible to deduce an actual type for the type parameters, as happened in the two examples above.

The type of makeAdder is more of the same: a -> a -> a is the type of a function that takes a single argument of type a, and returns a function of type a -> a, that is, a function (like increment) that takes a single argument of type a and returns a result of the same type.  Again, this has the constraint that a must be a numeric type.

As is usual in type theory, the -> type constructor is right-associative, so that the type a -> a -> a is the same as a -> (a -> a).  With curried functions, this is often what you want, since curried functions take one argument and return a function.  Of course, if this argument is itself a function (which is not unusual), you will need to put parentheses around its type.

In contrast, function application binds to the left; for example, makeAdder 1 4 is the same as (makeAdder 1) 4, which is the same computation as our increment 4 above and returns 5.  The reason for making function application left-associative is the same as that for making the type operator right-associative: this is the common case with curried functions.

If you really want the uncurried version of makeAdder, you would use a tuple containing the two arguments.  Tuples are written using the conventional mathematical notation of a sequence of comma-separated values inside parentheses: (1, 4).  Here is the uncurried version, which can simply be called add:

Haksell

add :: (Num a) => (a, a) -> a add (x, y) = x + y

As you can see, the type now represents a function that takes a tuple containing two elements of type a, and returns a result of type a.  A very useful feature of Haskell, common to many other functional languages (and some languages with a strong functional subset, like Scala), is pattern matching.  In Haskell, a formal parameter can have the syntactic structure of a constructor for any type (and, in fact, such constructors can be nested).  In this case, the parameter of add is a constructor for a tuple containing two values, x and y, and has the parenthesized form (x, y).  This means that the function can only accept tuples of this form, and when it does, the first element will be called x and the second will be called y.  This form is deceptively similar to the usual mathematical notation, but keep in mind that this is not natural for Haskell and interferes with various Haskell idioms.  The norm in Haskell is to use curried functions; any other use requires careful justification.

Having gone through the preliminaries, here is the fixed-point function:

Scala

def fixedpoint(f: Double => Double, v: Double): Double = { val next = f(v) if (Math.abs(next - v) < epsilon) next else fixedpoint(f, next) }

Haskell

fixedpoint :: (Ord a, Fractional a) => (a -> a) -> a -> a fixedpoint f guess =   let next = f guess in       if abs(guess - next) < epsilon       then next       else fixedpoint f next

The let syntax binds one or more variables in the context of an expression (which follows the keyword in).  As in Scala, if in Haskell is an expression that returns one of two values depending on the condition.  The parenthesis on the argument to the abs function are required; without them, the expression would be parsed as (abs guess) - next.

The type of fixedpoint is (a -> a) -> a -> a, using only the required parentheses; this could equivalently be written as (a -> a) -> (a -> a), which makes it clearer that fixedpoint takes a function from a to a and returns another such function.  The type a is constrained to be ordered (because of the use of <), as well as fractional (because it is compared with epsilon, which is a Double).

In Haskell, of course, recursion is the norm.  It is not impossible to write this as a loop, but it is too cumbersome to even try.  Instead, I want to show a more abstract version of this function, in which the separate parts are given meaningful names; this is actually closer to the original Scheme example.

Haskell

fixedpoint :: (Ord a, Fractional a) => (a -> a) -> a -> a fixedpoint f guess =   let closeEnough v1 v2 = abs(v1 - v2) < epsilon       try guess =           let next = f guess in               if closeEnough guess next               then next               else try next   in try guess0

Here, the decision of whether the guess is close enough to the desired value is abstracted into the function closeEnough, and the recursion is encapsulated into the function try.  As usual, the internal functions have access to enclosing scopes, so they can refer to f and epsilon.

Lambda notation in Haskell uses the backslash as the ASCII character typographically closest to lambda.  A single arrow is used instead of Scala's double arrow to separate the body from the argument list.  Using this notation, here is the non-terminating version of sqrt:

Scala

def sqrt(x: Double) = fixedpoint(y => x / y, 1.0)

Haskell

sqrt :: Double -> Double sqrt x = fixedpoint (\y -> x / y) 1.0

The terminating version is of course very similar:

Scala

def sqrt(x: Double) =     fixedpoint(y => (y + x / y) / 2.0, 1.0)

Haskell

sqrt :: Double -> Double sqrt x = fixedpoint (\y -> (y + x / y) / 2.0) 1.0

The generalization of the average-damp procedure and its use should hold no surprises now:

Scala

def averageDamp(f: Double => Double) = (x: Double) => (x + f(x)) / 2.0 def sqrt(x: Double) = fixedpoint(averageDamp(y => x / y), 1.0)

Haskell

averageDamp :: Fractional a => (a -> a) -> a -> a averageDamp f x = (x + f x) / 2.0 sqrt :: Double -> Double sqrt x = fixedpoint (averageDamp (\y -> x / y)) 1.0

Haskell takes some getting used to for people used to imperative or object-oriented languages.  However, it you are ready to take the commitment to pure functional programming, Haskell would be the obvious choice.

Remember that we have only discussed functional abstraction up to this point; there is much more to functional programming (even in mainstream languages), and I will address that in future posts. #functionalprogramming #haskell

Functional Programming in Mainstream Languages, Part 6: Higher-Order Functions in Xtend

(Jump to Table of Contents)

I introduced the Xtend programming language in a previous post.  Xtend is similar to Java, and compiles to Java (not to bytecode), but is much more pleasant to use.  In particular, it supports functional programming in various ways, both in the language itself and in the libraries.  Some of these will have to wait for later posts in the series; for now, as in previous posts, I am only discussing higher-order functions.  Again, I will contrast Xtend with Java 8.

Here is the simple example of the curried addition function:

Java 8

IntFunction makeAdder = x -> y -> x + y; IntUnaryOperator increment = makeAdder.apply(1); int res = increment.applyAsInt(4);

Xtend

val makeAdder = [int x|[int y|x + y]] val increment = makeAdder.apply(1) val res = increment.apply(4)

The syntax for anonymous functions (lambdas) in Xtend is different from all those we saw before; instead of some kind of arrow symbol, it uses square brackets with a vertical bar separating the parameters from the body.  Type inferencing is applied (as in Scala) to infer the types of the expressions.  Unlike Scala, and like Java, Xtend still requires the method-call syntax for function calls.

The recursive fixed-point function looks like this:

Java 8

public double fixedpoint(DoubleUnaryOperator f, double v) { double next = f.applyAsDouble(v); if (Math.abs(next - v) < epsilon) return next; else return fixedpoint(f, next); }

Xtend

def double fixedpoint(Function1<Double, Double> f, double v) { val next = f.apply(v) if ((next - v).abs < epsilon) next else fixedpoint(f, next) }

This uses the Xtend interface for unary functions, Function1, with the Java wrapper type Double.  In principle, the compiler could have inferred the return type of this function (Scala can do it, see Part 5), but its type-inference mechanism doesn't handle recursion, so it is necessary to specify the type manually.  I hope this will be fixed in a future release.

In this example we can see a nice extension feature, one of those that gave Xtend its name.  Doubles in Java has no abs method; instead, you call the static method Math.abs with the number as a parameter.  This is awkward and places an unnecessary cognitive burden on programmers, who need to remember which methods each object has and which static methods are available for it.  (This is quite common in Java, which has many classes that offer services as static methods; Arrays and Collections are famous examples.)  In general, having different and mutually exclusive ways of expressing what is essentially the same concept is bad.  Xtend allows developers to define "extension methods," which are static methods that can be called like regular methods on the first argument.  In this example, for a double variable x the following are completely equivalent: Math.abs(x), and x.abs.  This equivalence (like many others) is defined in the standard Xtend libraries.

Because this recursive version of fixedpoint compiles in a straightforward manner to Java, tail-recursion optimization is not necesarily applied.  The imperative version is therefore preferred in this case as well:

Java 8

public double fixedpoint(DoubleUnaryOperator f, double v) { double prev = v; double next = v; do { prev = next; next = f.applyAsDouble(next); } while (Math.abs(next - prev) >= epsilon); return next; }

Xtend

def fixedpoint(Function1<Double, Double> f, double v) { var next = v var prev = v do { prev = next next = f.apply(next) } while ((next - prev).abs >= epsilon) next }

A seemingly slight difference between the recursive and imperative versions is the use of the keyword to define variables.  Unmodifiable variables in Xtend (which are translated into Java final variables) are introduced by the keyword val, whereas modifiable variables (non-final) are introduced by the keyword var.  In Xtend it is therefore just as easy to define final variables as non-final ones.  This is a great incentive for writing functional programs, which don't have modifiable variables.  When you write Xtend code, you should always use val rather than var, unless you convince yourself that there is good reason why the variable should be modifiable.  And you should be hard to convince on this point!

At this point you know to expect the non-terminating sqrt; here it is:

Java 8

public double sqrt(double x) { return fixedpoint(y -> x / y, 1.0); }

Xtend

def sqrt(double x) { fixedpoint([y|x / y], 1.0) }

The differences are minor: less type information is required in Xtend, and, like Scala, Xtend doesn't require the access-level designator (public) and the return keyword; however, the braces are still required.

By now you can surely write the terminating version yourselves:

Java 8

public double sqrt(double x) { return fixedpoint(y -> (y + x / y) / 2.0, 1.0); }

Xtend

def sqrt(double x) { fixedpoint([y|(y + x / y) / 2.0], 1.0) }

The general average-damp and the corresponding sqrt again hold no surprises:

Java 8

public DoubleUnaryOperator averageDamp(DoubleUnaryOperator f) { return x -> (x + f.applyAsDouble(x)) / 2.0; } public double sqrt(double x) { return fixedpoint(averageDamp(y -> x / y), 1.0); }

Xtend

def averageDamp(Function1<Double, Double> f) { [double x|(x + f.apply(x)) / 2.0] } def sqrt(double x) { fixedpoint(averageDamp[y|x / y], 1.0) }

As I said before, Xtend is a very pleasant alternative to Java, which has many similarities with Java but many points in which it improves on it significantly.  One of those is its support for functional programming (of which we have seen only one part, higher-order functions).  Java 8 has closed some (but not enough) of this distance, and made some choices that are different from Xtend's.  The most obvious is the lambda notation, but perhaps more important are the use of the functional interfaces, more limited type inference, and the inconsistent use of the method name (apply, applyAsDouble, test, etc.).  As we saw in Part 5, Scala is perhaps more pleasant that Xtend in some ways, but is places itself further away from Java (in many more ways than we have seen).

In summary, if you are now programming in Java and want a closely-related but better language, you should take a good look at Xtend.

#FunctionalProgramming #Xtend

Functional Programming in Mainstream Languages, Part 5: Higher-Order Functions in Scala

(Jump to Table of Contents)

Scala is a relatively new language; it belongs to the bigger-is-better school of programming languages, and includes many kinds of object-oriented features as well as a functional subset.  Scala captured a lot of interest in the academic community, and for several years it featured in many papers in the leading conferences on object-oriented programming.

Scala attempts (among other things) to combine object-oriented and functional programming in a graceful way.  In this post, I will show how higher-order functions are expressed in Scala, using the same examples as previous posts, and contrast it with the Java 8 implementation.

Scala compiles to Java bytecode, and is therefore compatible with Java code.  It extends the Java type system in ways that make it more consistent.  For example, all values in Scala are objects, so it doesn't have the artificial and annoying distinction between primitive types (int, double, ...) and classes (everything else, including Integer and Double).  Like Java, Scala is strongly typed, but contains extensive type-inference mechanisms so that programmers can avoid a lot of type specifications.

Here is the simple example of the curried addition function:

Java 8

IntFunction<IntUnaryOperator> makeAdder = x -> y -> x + y; IntUnaryOperator increment = makeAdder.apply(1); int res = increment.applyAsInt(4);

Scala

def makeAdder = (x: Int) => (y: Int) => x + y def increment = makeAdder(1) def res = increment(4)

Note that in this example type inference goes in the opposite direction in the two languages: Java infers parameter types from the declaration, whereas Scala infers the function's type from the parameter types and the expression in the body.  Scala infers the following type for the add function: Int => (Int => Int).  We could specify this type manually, but don't need to.

Clearly, Scala's notation for functional types is much nicer than Java's use of multiple interfaces; and the function application notation doesn't require an artificial method call.  In both aspects, Scala notation is similar to the usual mathematical notation.

Here is the recursive fixed-point function:

Java 8

public double fixedpoint(DoubleUnaryOperator f, double v) { double next = f.applyAsDouble(v); if (Math.abs(next - v) < epsilon) return next; else return fixedpoint(f, next); }

Scala

def fixedpoint(f: Double => Double, v: Double): Double = { val next = f(v) if (Math.abs(next - v) < epsilon) next else fixedpoint(f, next) }

These are quite similar, except for the notations for types and for function application, and the fact that Scala doesn't require explicit return statements.

Scala emphasizes recursion, and will therefore perform tail-recursion optimization whenever possible.  If you want to make sure that the function is indeed optimized in this way, you can add the annotation @tailrec to the function (or method).  This will cause the compiler to produce an error if the tail-recursion optimization can't be applied.  In this case, the compiler accepts this annotation, so that this version is just as efficient as the imperative one.  Because recursion is natural in Scala, this would be the preferred way of writing this method.  For comparison, here is the imperative version:

Java 8

public double fixedpoint(DoubleUnaryOperator f, double v) { double prev = v; double next = v; do { prev = next; next = f.applyAsDouble(next); } while (Math.abs(next - prev) >= epsilon); return next; }

Scala

def fixedpoint(f: Double => Double, v: Double) = { var next = v var prev = v do { prev = next next = f(next) } while (Math.abs(next - prev) >= epsilon) next }

This is not too bad; still, I recommend using recursion instead of assignments in all languages that fully support it (that is, guarantee the tail-recursion optimization), including Scala.

Now for the naive non-terminating version of sqrt that uses fixedpoint:

Java 8

public double sqrt(double x) { return fixedpoint(y -> x / y, 1.0); }

Scala

def sqrt(x: Double) = fixedpoint(y => x / y, 1.0)

The differences are small, and have to do with Java's verbosity more than anything else.  Gone are the access-level designator (public), the return type, the return keyword, and the braces.  The Scala version is more concise, and can easily be written in one line.  These are small savings, but they add up over a large program and reduce the noise-to-signal ratio.  Except for Haskell (forthcoming), Scala is the most concise (for this kind of code) of all the languages I survery in this series.

The terminating version of sqrt that uses average damping should now come as no surprise:

Java 8

public double sqrt(double x) { return fixedpoint(y -> (y + x / y) / 2.0, 1.0); }

Scala

def sqrt(x: Double) = fixedpoint(y => (y + x / y) / 2.0, 1.0)

Here is the general average-damp procedure and the version of sqrt that uses it:

Java 8

public DoubleUnaryOperator averageDamp(DoubleUnaryOperator f) { return x -> (x + f.applyAsDouble(x)) / 2.0; } public double sqrt(double x) { return fixedpoint(averageDamp(y -> x / y), 1.0); }

Scala

def averageDamp(f: Double => Double) = (x: Double) => (x + f(x)) / 2.0 def sqrt(x: Double) = fixedpoint(averageDamp(y => x / y), 1.0)

Again, the Scala formulation is concise and clear, while still being strongly typed.  By design, Scala is well-suited for expressing functional-programming abstractions, using type inference effectively in order to reduce the burden of specifying types.  Scala is too large for my taste, but functional programming is easy and natural in it.

#functionalprogramming #scala

Functional Programming in Mainstream Languages, Part 4: Higher-Order Functions in JavaScript

(Jump to Table of Contents)

JavaScript is the only universal language for client-side programming for web applications.  If you need to write anything that will run in the browser, JavaScript is currently your only option.  That is unfortunate, since JavaScript is an amalgam of some good parts and some truly horrible parts.  (See the book JavaScript: The Good Parts for more details.)

Among the good parts of JavaScript is its functional part, which is widely used to create callbacks; but it can also be used for functional-programming techniques in general.  For a fascinating but advanced presentation of the elegant way in which NetFlix uses functional programming in JavaScript to perform asynchronous processing, see the ACM webinar titled "August 2014: Async JavaScript at Netflix."

In this part of the series, I will show the examples of higher-order functions from Part 3 in JavaScript, and contrast it with the Java 8 implementation.  For the Scheme and Java 7 versions, see Part 3.  First, however, is the simple example from Part 2:

Java 8

IntFunction<IntUnaryOperator> makeAdder = x -> y -> x + y; IntUnaryOperator increment = makeAdder.apply(1); int res = increment.applyAsInt(4);

JavaScript

var makeAdder = function(x) {     return function(y) {         return x + y;     } } var increment = makeAdder(1); var res = increment(4);

As you can see, the JavaScript syntax for defining functions is more verbose but not unreasonable.  In contrast, function calls use the familiar mathematical notation without requiring a spurious method call.

Ecma International publishes the standards for the JavaScript language, under the name ECMAScript.  The draft ECMAScript 6 standard (code named Harmony) introduces "arrow functions"; these are very similar to regular JavaScript functions but use an alternative definition syntax (and improve the semantics in small but significant ways).  For comparison, here is the same code using this notation:

ECMAScript Harmony (still in draft status)

var makeAdder = x => y => x + y; var increment = makeAdder(1); var res = increment(4);

This is very similar to Java 8, except for the use of the => symbol instead of ->.  As in Java 8, this is the simplest syntax for defining functions; there are variants for more complex cases.  For example, if the function has more (or less) than one argument, the argument list must be placed in parentheses.  Unlike Java 8, of course, ECMAScript has no syntax to specify the types of the arguments or the returned value.  There are other differences as well; see the proposed draft for further details.

Here is the recursive fixed-point function:

Java 8

public double fixedpoint(DoubleUnaryOperator f, double v) {     double next = f.applyAsDouble(v);     if (Math.abs(next - v) < epsilon)         return next;     else         return fixedpoint(f, next); }

JavaScript

function fixedpoint(f, v) {     var next = f(v);     if (Math.abs(next - v) < epsilon)         return next     else         return fixedpoint(f, next); }

These are very similar, except for the lack of types in JavaScript.  Here is the imperative version of fixedpoint.  JavaScript, like Java, doesn't guarantee that tail-recursion optimization will always be performed, and this version is more natural for JavaScript.  For these reasons, I find this acceptable practice even when using functional-programming techniques in JavaScript, provided that the variables being modified aren't used in any other context.

Java 8

public double fixedpoint(DoubleUnaryOperator f, double v) {     double prev = v;     double next = v;     do {         prev = next;         next = f.applyAsDouble(next);     } while (Math.abs(next - prev) >= epsilon);     return next; }

JavaScript

function fixedpoint(f, v) {     var next = v;     var prev = v;     do {         prev = next;         next = f(next)     } while (Math.abs(next - prev) >= epsilon);     return next; }

Next is the naive non-terminating version of sqrt that uses fixedpoint:

Java 8

public double sqrt(double x) {     return fixedpoint(y -> x / y, 1.0); }

JavaScript

function sqrt(x) {     fixedpoint(function(y) {         return x / y;     }, 1); }

The boilerplate code is starting to get in the way here (although not as much as in Java 7, due to the lack of types).  Still, it's becoming difficult to recognize the syntactic role of the constant 1.  This annoyance should disappear with the release of ECMAScript Harmony.

The terminating version of sqrt that uses average damping implicitly looks like this:

Java 8

public double sqrt(double x) {     return fixedpoint(y -> (y + x / y) / 2.0, 1.0); }

JavaScript

function sqrt(x) {     fixedpoint(function(y) {         return (y + x / y) / 2;     }, 1); }

Finally, here is the average-damp operator and the implementation of sqrt that uses it explicitly:

Java 8

public DoubleUnaryOperator averageDamp(DoubleUnaryOperator f) {     return x -> (x + f.applyAsDouble(x)) / 2.0; } public double sqrt(double x) {     return fixedpoint(averageDamp(y -> x / y), 1.0); }

JavaScript

function averageDamp(f) {     return function(x) {         return (x + f(x)) / 2;     } } function sqrt(x) {     return fixedpoint(averageDamp(function(y) {         return x / y;     }), 1); }

In summary, higher-order functions are quite natural in JavaScript, with a syntax that is somewhat cumbersome but still manageable.  One of the reasons it is simpler than Java 7 is the lack of types, which is a result of the lack of static typing in JavaScript as a whole.  An interesting compromise is the language TypeScript, which supports gradual typing (see my review in a previous post) but compiles into JavaScript.  TypeScript uses the arrow-function notation proposed for ECMAScript, so it allows very concise function definitions that do contain types.  I will address TypeScript in a future post.

Coming up in this series: Scala, Xtend, and Haskell!

#functionalprogramming #javascript