tag:blogger.com,1999:blog-55360174332651893182024-02-19T19:20:33.310+02:00The Dusty Deck<big><b>Thoughts about software development and related issues.
</b></big><br>
<big>The views expressed here are my own and do not necessarily reflect those<br>of my employer, IBM.</big>Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.comBlogger43125tag:blogger.com,1999:blog-5536017433265189318.post-51807855777224882172022-12-25T15:07:00.009+02:002022-12-26T16:19:34.881+02:00Metaprogramming in Python 2: An Interning Decorator<p style="text-align: left;"></p><p style="text-align: left;"><span style="font-family: georgia;"><b></b></span></p><div class="separator" style="clear: both; text-align: center;"><span style="font-family: georgia;"><b><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjdNlGBY0XC_cnWO9XHYdq0ffKPT7z36CgT5IDyvrDfTBSxGs6jLx5re1yn5TbV7Qz3lj-mitjM-q9Izcc6BOO-hX_9SkgROH34F3Q07A57giybS4RXg3b2KlPvg2nXkxXKv9sJMVTRwEBJYoFyJ13i0gU9Eh58X-VySrUOLFXG-uUKvyXU5Z9Xii3PxQ/s6000/Singled-out.Original.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="4500" data-original-width="6000" height="480" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjdNlGBY0XC_cnWO9XHYdq0ffKPT7z36CgT5IDyvrDfTBSxGs6jLx5re1yn5TbV7Qz3lj-mitjM-q9Izcc6BOO-hX_9SkgROH34F3Q07A57giybS4RXg3b2KlPvg2nXkxXKv9sJMVTRwEBJYoFyJ13i0gU9Eh58X-VySrUOLFXG-uUKvyXU5Z9Xii3PxQ/w640-h480/Singled-out.Original.jpg" width="640" /></a></b></span></div><span style="font-family: georgia;"><b><br />Note:</b> the code related to this post can be found in the <a href="https://github.com/IBM/IBM-Metaprogramming-for-Python" target="_blank">github IBM-Metaprogramming-for-Python repo</a>, <span style="font-family: inherit;">in </span><a href="https://github.com/IBM/IBM-Metaprogramming-for-Python/blob/main/metautils/intern.py" target="_blank"><span style="font-family: courier;">intern.py</span></a>, available under the <a href="https://github.com/IBM/IBM-Metaprogramming-for-Python/blob/main/LICENSE" target="_blank">Apache 2.0 license</a>. <br /></span><p></p><h1 style="text-align: left;">Contents</h1><p style="text-align: left;"><a href="https://the-dusty-deck.blogspot.com/2022/12/metaprogramming-in-python-1-introduction.html" target="_blank">Part 1: Introduction </a></p>Part 2: An Interning Decorator<span style="font-family: georgia;"> <br /></span><h1 style="text-align: left;"><span style="font-family: georgia;">Interning</span></h1><p style="text-align: left;"><span style="font-family: georgia;">Interning is a mechanism for ensuring that any two equal objects of the same class are actually identical (that is, the same object). This can save memory, by preventing the proliferation of many objects that are equal to each other. It can also speed up computation by using pointer comparison (which takes small and constant time) instead of object equality, which can be arbitrarily complex. And, in case object creation requires expensive computation, this can be avoided whenever an equal object to the one being requested already exists.<br /></span></p><p style="text-align: left;"><span style="font-family: georgia;">Sometimes it is necessary to ensure that a change to the state of an object is seen by every part of the program that has access to that object or any other object that is equal to it. Interning achieves this goal by ensuring that there is only one such object, so that a change to it is automatically seen everywhere in the program.<br /></span></p><p style="text-align: left;"><span style="font-family: georgia;">Interning has a cost of its own; this includes storage for a table that keeps track of existing objects, as well as a small overhead on the creation of objects, which must look at the table before creating new objects.<br /></span></p><p style="text-align: left;"><span style="font-family: georgia;">Interning is used for strings in many programming languages; for example, the Java compiler interns all literal strings (those that appear in double quotes in the source files); Java, Python, and many other languages provide an <span style="font-family: courier;">intern()</span> method for strings, for use at the programmer's discretion.</span></p><p style="text-align: left;"><span style="font-family: georgia;">Interning is useful for many other types of objects besides strings. If it is only used to save memory, it need not be perfectly accurate; as long as it drastically reduces the number of new objects created, it serves its purpose. However, in order to allow the replacement of equality comparisons by object identity, it must ensure that there will never be two distinct but equal objects.</span></p><p style="text-align: left;"><span style="font-family: georgia;">Interning can be implemented using a static method that creates objects instead of using the constructor. However, this is cumbersome and unsafe, since users can still call the constructor to generate new objects, bypassing the interning mechanisms. (In Java this can be prevented by making the constructor private, but Python doesn't have a corresponding mechanism.)</span></p><p style="text-align: left;"><span style="font-family: georgia;">A better way is to change the behavior of the constructor so that it doesn't always create a new object. In some languages, including C++ and Java, this is impossible, since a constructor is guaranteed to return a fresh object. However, languages such as Python do provide mechanisms to change the behavior of constructors (and other parts of the language) in a very flexible way, using metaprogramming (see <a href="https://the-dusty-deck.blogspot.com/2022/12/metaprogramming-in-python-1-introduction.html" target="_blank">Part 1</a>)<i>.</i></span></p><p style="text-align: left;"><span style="font-family: georgia;">To implement a general interning mechanism in Python, we will create an <span style="font-family: courier;">@intern</span> decorator for classes whose elements should be interned. This decorator will add or modify the class's <span style="font-family: courier;">__new__()</span> </span><span style="font-family: georgia;">method to use an interning table, </span><span style="font-family: georgia;">and the <span style="font-family: courier;">__init__()</span> method to ensure that object initialization is done exactly once per object.<i> </i></span><br /></p><h1 style="text-align: left;">Applying Interning to a Class</h1><h3 style="text-align: left;">Default Interning<br /></h3><p>The simplest way to apply interning to a class is just to decorate it with <span style="font-family: georgia;"><span style="font-family: courier;">@intern</span></span>, as in the following example:</p><p></p><p><span style="font-family: courier;"><span style="color: #2b00fe;">@intern</span><br />class Foo:<br /> def __init__(self,<br /> s1: str,<br /> i1: int,<br /> t1: tuple,<br /> set1: frozenset,<br /> kt1: tuple = ()):<br /> self.s1 = s1<br /> self.i1 = i1<br /> self.t1 = t1<br /> self.set1 = set1<br /> self.kt1 = kt1</span><br /></p><p>(All the examples shown here are taken from the <a href="https://github.com/IBM/metatools/blob/main/test/test_intern.py" target="_blank">test file</a>.)<br /></p><p>This class has five fields, which are initialized from corresponding parameters of the constructor. If you create two instances of this class with equal (but not necessarily identical) parameters, you will get the same identical instance in both cases, as shown by the first test case:</p><p><span style="font-family: courier;">obj1 = Foo('test1', 1, ((1, 2), (3, 4)), frozenset((10, 11)))<br />obj2 = Foo('test1', 1, ((1, 2), (3, 4)), frozenset((11, 10)))<br />self.assertIs(obj1, obj2)</span> </p><p>Note that the tuple and sets are distinct objects, yet the values of <span style="font-family: courier;">obj1</span> and <span style="font-family: courier;">obj2</span> are the same object (in other words, <span style="font-family: courier;">obj1 is obj2</span> would evaluate to <span style="font-family: courier;">True</span>).</p><p>This implementation of the <span style="font-family: courier;">@intern</span> decorator indexes objects based on the arguments to the constructor rather than the object's actual fields (which are not available unless the object is actually created, defeating the purpose of the exercise). This is based on the assumption that equal constructor arguments create equal objects; an assumption that often but not always true. But don't worry! This behavior can be customized, as we will see shortly.<br /></p><p>Another caveat of the default implementation is that supplying the default value of a keyword argument in the constructor call looks different than a call that omits that keyword argument. Therefore, the next object, <span style="font-family: courier;">obj3</span>, is <i>not</i> the same as the previous two:</p><p><span style="font-family: courier;">obj3 = Foo('test1', 1, ((1, 2), (3, 4)), frozenset((11, 10)), kt1=())<br />self.assertIs<span style="color: #2b00fe;">Not</span>(obj1, obj3)</span></p><p>Similarly, providing a keyword argument positionally, without using the keyword, is different from anything else we have seen above:</p><p><span style="font-family: courier;">obj4 = Foo('test1', 1, ((1, 2), (3, 4)), frozenset((11, 10)), ())<br />self.assertIsNot(obj1, obj4)<br />self.assertIsNot(obj3, obj4)</span></p><h3 style="text-align: left;">Using a Key Function <br /></h3><p>These issues can be solved by a very general mechanism built into the <span style="font-family: courier;">intern</span> decorator: user-provided key functions. These are functions that accept the same parameters as the class constructor, and return an object that can be used to index class objects in the internal table. A simple and common example is the following:</p><p><span style="font-family: courier;">def key_func(s1: str, i1: int, t1: tuple, set1: frozenset, kt1: tuple = ()):<br /> return s1, i1, t1, set1, kt1<br /><br /><br />@intern(key=key_func)<br />class Bar:<br /> def __init__(self, s1: str, i1: int, t1: tuple, set1: frozenset, kt1: tuple = ()):<br /> self.s1 = s1<br /> self.i1 = i1<br /> self.t1 = t1<br /> self.set1 = set1<br /> self.kt1 = kt1<br /></span>This class is defined with the <span style="font-family: courier;">@intern</span> decorator, but in this case it is given a <span style="font-family: courier;">key</span> parameter, which is the function <span style="font-family: courier;">key_func</span>. This function simply returns a tuple of all the constructor parameters, but it puts the value of the keyword parameter into the same tuple, regardless of how it was specified in the construtor call (positionally, by keyword, or omitted). The <span style="font-family: courier;">Bar</span> constructor calls corresponding to the four examples shown above for <span style="font-family: courier;">Foo</span> therefore all return the same object:</p><p><span style="font-family: courier;">obj1 = Bar('test1', 1, ((1, 2), (3, 4)), frozenset((10, 11)))<br />obj2 = Bar('test1', 1, ((1, 2), (3, 4)), frozenset((11, 10)))<br />self.assertIs(obj1, obj2)<br />obj3 = Bar('test1', 1, ((1, 2), (3, 4)), frozenset((11, 10)), kt1=())<br />self.assertIs(obj1, obj3)<br />obj4 = Bar('test1', 1, ((1, 2), (3, 4)), frozenset((11, 10)), ())<br />self.assertIs(obj1, obj4)</span><br /></p><h3 style="text-align: left;">Mutable Constructor Arguments</h3><p>Python refuses to use objects that are not hashable as keys of tables (such as instances of <span style="font-family: courier;">dict</span>). In particular, mutable objects (those whose state can change during runtime) should not be hashable, otherwise they will be lost if used as table keys when their values (and therefore also their hash values) change.<br /></p><p>This means that any mutable (or, in general, non hashable) argument to the constructor of a class that uses interning must not be used as a key. For example, the following test succeeds because the creation of the object raises an exception:<br /></p><p><span style="font-family: courier;">@intern<br />class Qux:<br /> def __init__(self, s1: str, i1: int, l1: list, set1: set, kt1: tuple = ()):<br /> self.s1 = s1<br /> self.i1 = i1<br /> self.l1 = l1<br /> self.set1 = set1<br /> self.kt1 = kt1<br /></span></p><p><span style="font-family: courier;">try:<br /> Qux('test1', 1, [(1, 2), (3, 4)], {10, 11})<br />except TypeError:<br /> pass<br />else:<br /> self.fail("Expected TypeError: unhashable type: 'list'")</span><br /></p><p>The class <span style="font-family: courier;">Qux</span> is different from <span style="font-family: courier;">Foo</span> only in the type of the third constructor parameter, which is a list instead of a tuple. (Unless you activate runtime type checking, you will not see a difference between the behaviors of <span style="font-family: courier;">Foo</span> and <span style="font-family: courier;">Qux</span>.) Since the default behavior of <span style="font-family: courier;">@intern</span> is to use the constructor arguments to compose the key, Python will raise a <span style="font-family: courier;">TypeError</span> when a mutable list and a mutable set are used as the key to a table.</p><p>Key functions can be used to solve this issue as well. The key function needs to construct a hashable key; for example, it can replace lists by tuples, sets by frozen sets (elements of <span style="font-family: courier;">frozenset</span>), and tables by tuples of key-value pairs (each of which is itself a tuple). This is done in the following example:</p><p><span style="font-family: courier;">def key_func_for_list(s1: str, i1: int, l1: list, set1: set, kt1: tuple = ()):<br /> return s1, i1, tuple(l1), frozenset(set1), kt1 <br /></span></p><p><span style="font-family: courier;">@intern(key=key_func_for_list)<br />class Quux:<br /> def __init__(self, s1: str, i1: int, l1: list, set1: set, kt1: tuple = ()):<br /> self.s1 = s1<br /> self.i1 = i1<br /> self.l1 = l1<br /> self.set1 = set1<br /> self.kt1 = kt1<br /></span></p><p><span style="font-family: courier;">obj1 = Quux('test1', 1, [(1, 2), (3, 4)], {10, 11})<br />obj2 = Quux('test1', 1, [(1, 2), (3, 4)], {11, 10})<br />self.assertIs(obj1, obj2)<br />obj3 = Quux('test1', 1, [(1, 2), (3, 4)], {11, 10}, kt1=())<br />self.assertIs(obj1, obj3)<br />obj4 = Quux('test1', 1, [(1, 2), (3, 4)], {11, 10}, ())<br />self.assertIs(obj1, obj4)</span><br /></p><p>This now works as expected, with all four constructor calls returning the same object.</p><p>In general, of course, you need to take care of deep data structures that have unhashable elements; for example, a tree that is represented as lists nested within other lists must be converted to another form, such as tuples nested in tuples.</p><h3 style="text-align: left;">Indexing by Object Identity</h3><p>Sometimes you want to intern your objects based on the identity of the constructor arguments rather than by equality. This is also easy to do using a key function, as in the following example:</p><p><span style="font-family: courier;">def key_by_id(s1: str, i1: int, l1: list, set1: set, kt1: tuple = ()):<br /> return tuple(map(id, (s1, i1, l1, set1, kt1)))<br /><br />@intern(key=key_by_id)<br />@dataclass<br />class Xyzzy:<br /> s1: str<br /> i1: int<br /> l1: list<br /> set1: set<br /> kt1: tuple = ()</span></p><p><span style="font-family: courier;">list1 = [(1, 2), (3, 4)]<br />set1 = {10, 11}<br />obj1 = Xyzzy('test1', 1, list1, set1)<br />obj2 = Xyzzy('test1', 1, list1, set1, kt1=())<br />self.assertIs(obj1, obj2)<br />obj3 = Xyzzy('test1', 1, [(1, 2), (3, 4)], set1, kt1=())<br />self.assertIsNot(obj1, obj3) </span><br /></p><p>In this case, the key consists of the "identities" of the constructor parameters, as given by the built-in Python function <span style="font-family: courier;">id</span> (in CPython these are memory addresses).<br /></p><p>Both <span style="font-family: courier;">obj1</span> and <span style="font-family: courier;">obj2</span> are constructed with identical parameters, and are therefore the same object. (Note that the string and int arguments are identical because of the interning behavior of Python for these data types; this behavior is undocumented and may differ between implementations of versions of Python.)</p><p>However, <span style="font-family: courier;">obj3</span> is given a different list, and is therefore not identical to the previous object.</p><p>This example also demonstrates that <span style="font-family: courier;">@intern</span> can be applied on data classes (decorated with <span style="font-family: courier;">@dataclass</span>). However, in such cases you must ensure that the <span style="font-family: courier;">@intern</span> decorator comes before <span style="font-family: courier;">@dataclass</span> (which means that it is applied after it), since <span style="font-family: courier;">@dataclass</span> will not create an <span style="font-family: courier;">__init__()</span> method if one has been created by <span style="font-family: courier;">@intern</span>, and <span style="font-family: courier;">@intern</span> must have access to the <span style="font-family: courier;">__init__()</span> method generated by <span style="font-family: courier;">@dataclass</span>.<br /></p><h4 style="text-align: left;">Caveat<br /></h4>Suppose you use object identities as keys, as in the <span style="font-family: courier;">Xyzzy</span> example, but the generated object does not keep a pointer to the argument, as in the following example:<p><span style="font-family: courier;">@intern(key=key_by_id)<br />class Gritch:<br /> def __init__(self, s1: str, i1: int, l1: list, set1: set, kt1: tuple = ()):<br /> self.s1 = s1<br /> self.i1 = i1<br /> self.l1 = <span style="color: #2b00fe;">tuple(l1)</span><br /> self.set1 = <span style="color: #2b00fe;">tuple(set1)</span><br /> self.kt1 = kt1</span> <br /></p><p>The following test case passes on my current Python installation (CPython 3.11.1 for x64):</p><p><span style="font-family: courier;">obj1 = Gritch('test1', 1, [(1, 2), (3, 4)], {10, 11})<br />obj2 = Gritch('test1', 1, [(10, 20), (30, 40)], {100, 110})<br />self.assertIs(obj1, obj2)</span><br /></p><p>How is this possible? The values of <span style="font-family: courier;">obj1</span> and <span style="font-family: courier;">obj2</span> should be different, and so they can never be represented by the same object!</p><p>The reason for this is that the first list can be garbage-collected immediately after <span style="font-family: courier;">obj1</span> is created, since there are no longer any references to it. The second list (used to initialize <span style="font-family: courier;">obj2</span>) can in principle be allocated at the same address as the first one, and the same holds for the set argument. The Python garbage collector (in my installation, at least) takes advantage of this fact, and reuses the memory without even waiting for a full garbage-collection cycle. The keys used for interning both objects therefore contain the same ids for the list and set, and the constructor returns <span style="font-family: courier;">obj1</span>, which is indexed under this key.</p><p>This can never happen if you object keeps a reference to the arguments used in the key, since they can't be garbage collected as long as the object exists in the table, and so this object will never be confused for any other.</p><h1 style="text-align: left;">Singleton <br /></h1><p>The same approach can be used to create singleton classes, where the first call to the constructor creates the singleton object, and further calls return the same object.</p><p>In fact, if the constructor has no parameters (except for <span style="font-family: courier;">self</span>, of course), the <span style="font-family: courier;">@intern</span> decorator will create a singleton. However, a direct implementation of the singleton pattern may be very slightly more efficient.<br /></p><h1 style="text-align: left;">Implementing Interning</h1><p style="text-align: left;"><span style="font-family: georgia;">Note: the implementation described below can be found in </span><span style="font-family: georgia;">the <a href="https://github.com/IBM/IBM-Metaprogramming-for-Python" target="_blank">github IBM-Metaprogramming-for-Python repo</a>, </span><span style="font-family: georgia;">in <a href="https://github.com/IBM/IBM-Metaprogramming-for-Python/blob/main/metautils/intern.py" target="_blank"><span style="font-family: courier;">intern.py</span></a>.</span></p><p style="text-align: left;"><span style="font-family: georgia;">The <span style="font-family: courier;">@intern</span> decorator is actually an instance of the class <span style="font-family: courier;">Intern</span>, defined as follows:</span></p><p style="text-align: left;"><span style="font-family: courier;"><span>intern = Intern()</span></span></p><p style="text-align: left;"><span style="font-family: georgia;">This enables users to create independent interning objects, with possibly different behaviors (in this implementation, default key functions). The </span><span style="font-family: georgia;"><span style="font-family: courier;">Intern</span></span><span style="font-family: georgia;"> class constructor accepts an optional <span style="font-family: courier;">default_key</span> parameter; if provided, it should be a function that takes a class object as a parameter and returns the appropriate key function. (Of course, it may ignore the class parameter and return the same key function for all classes decorated with this instance.)</span></p><p style="text-align: left;"><span style="font-family: georgia;">Let's call an instance of the <span style="font-family: courier;">Intern</span> class an <i>interner</i>. In order to be used as a decorator, an interner needs to be callable; the main interning functionality is therefore implemented inside the <span style="font-family: courier;">__call__()</span> method, whose header is:</span></p><p style="text-align: left;"><span style="font-family: courier;"><span>def __call__(self,<br /> cls: Optional[type] = None, *,<br /> key: Callable = None,<br /> reset_method: Optional[str] = 'reset_intern_memory'):</span></span><span style="font-family: georgia;"> <br /></span></p><p style="text-align: left;"><span style="font-family: georgia;">The first (positional) parameter <span style="font-family: courier;">cls</span> is the decorated class. The keyword parameters can be provided as </span><span style="font-family: georgia;">arguments to the decorator; for example, we used </span><span style="font-family: courier;">@intern(key=key_by_id)</span><span style="font-family: georgia;"> as a decorator for <span style="font-family: courier;">Xyzzy</span> and <span style="font-family: courier;">Gritch</span>. The <span style="font-family: courier;">key</span> parameter is an optional key function, as explained above. The <span style="font-family: courier;">reset_method</span> parameter is an optional name for a method that can be used to reset the interning table, or <span style="font-family: courier;">None</span> to prevent the creation of such a method.<br /></span></p><p style="text-align: left;"><span style="font-family: georgia;">The decorator returns the same class it received, suitably modified.<br /></span></p><p style="text-align: left;">The following lines allow the decorator to be used with or without arguments:</p><p style="text-align: left;"><span style="font-family: courier;">if cls is None:<br /> return partial(self, key=key, reset_method=reset_method)</span><br /></p><p style="text-align: left;">In brief, if no class argument is provided, the call expects to receive the keyword arguments, and returns another decorator function that encapsulates those arguments and can be called on the class.</p><p style="text-align: left;">The next lines choose a key function, giving precedence to the one given as a decorator parameter over the <span style="font-family: courier;">default_key</span> of the interner:</p><p style="text-align: left;"><span style="font-family: courier;">if key is None and self.default_key is not None:<br /> key = self.default_key(cls)</span><br /></p><p style="text-align: left;"><span style="font-family: georgia;">The table used by the interner is created by the expression</span></p><p style="text-align: left;"><span style="font-family: courier;">memory = WeakValueDictionary()</span><br /></p><p style="text-align: left;"><span style="font-family: georgia;">A </span><span style="font-family: courier;">WeakValueDictionary</span> is a data structure similar to a <span style="font-family: courier;">dict</span>, except that it doesn't prevent the garbage collector to collect its values (provided, of course, they have no other [strong] references). This is done in order to avoid memory leaks due to stale objects being held only by the interner.</p><p style="text-align: left;">The next order of business, and perhaps the most significant, is the creation (or modification) of the decorated class's <span style="font-family: courier;">__new__()</span> method. This is where the table is searched for an existing object, which will be returned if it is found without creating a new object. If no existing object is found under the key, a new object will be generated, put into the table, and returned.</p><p style="text-align: left;">The code has two possible versions of this method, depending on whether or not the class already has a <span style="font-family: courier;">__new__()</span> method. If it does, it will be called to create the new object if necessary.</p><p style="text-align: left;">If the class has no <span style="font-family: courier;">__new__()</span> method of its own (that is, it uses <span style="font-family: courier;">object.__new__</span>), the code calls <span style="font-family: courier;">object.__new__()</span>. That method does not accept any additional arguments beyond the class itself, unlike custom <span style="font-family: courier;">__new__()</span> methods that can be given the constructor arguments. The definition of the new <span style="font-family: courier;">__new__()</span> method in this case is:</p><p style="text-align: left;"><span style="font-family: courier;">def __new__(cls, *args, **kwargs):<br /> element_key = (args, tuple(sorted(kwargs.items()))) if key is None else key(*args, **kwargs)<br /> try:<br /> result = memory[element_key]<br /> setattr(result, '*already_initialized*', True)<br /> return result<br /> except KeyError:<br /> result = object.__new__(cls)<br /> memory[element_key] = result<br /> return result</span> <br /></p><p style="text-align: left;">The <span style="font-family: courier;">try</span> block attempts to retrieve a previously-created object from the table; if successful, this object will be returned. (We will discuss the strangely-named <span style="font-family: courier;">*already_initialized*</span> attribute a little later.)</p><p style="text-align: left;">If the key doesn't exist in the table, a <span style="font-family: courier;">KeyError</span> exception will be raised. In this case, we will call <span style="font-family: courier;">object.__new__()</span> to create a new (uninitialized) object, put it in the table, and return it.<br /></p><p style="text-align: left;">If the class has a custom <span style="font-family: courier;">__new__()</span> method, the definition of the new <span style="font-family: courier;">__new__()</span> method is only slightly different, as marked in color below; <span style="font-family: courier;">old_new</span> is the value of <span style="font-family: courier;">getattr(cls, '__new__')</span>: <br /></p><p></p><p><span style="font-family: courier;">def __new__(cls, *args, **kwargs):<br /> element_key = ((args, tuple(sorted(kwargs.items())))<br /> if key is None<br /> else key(*args, **kwargs))<br /> try:<br /> result = memory[element_key]<br /> setattr(result, '*already_initialized*', True)<br /> return result<br /> except KeyError:<br /> result = <span style="color: #2b00fe;">old_new(cls, *args, **kwargs)</span><br /> memory[element_key] = result<br /> return result</span><br /></p><p style="text-align: left;"></p><p>In either case, the new method is installed on the class using the call <span style="font-family: courier;">setattr(cls, '__new__', __new__)</span>.</p><p>According to Python's data model, the object returned by a <span style="font-family: courier;">__new__()</span> method should be initialized by invoking on it the <span style="font-family: courier;">__init__()</span> method, with the provided constructor arguments. However, this rule is not followed if the <span style="font-family: courier;">__new__()</span> method returns an object whose type is different from the class whose constructor was called. Recall that the <span style="font-family: courier;">__new__()</span> method is allowed to return a value of any type; it would not make sense to initialize an object or a different class with the arguments appropriate to the original class.</p><p>This rule implies that if <span style="font-family: courier;">__new__()</span> does return an object of the same class, it will be initialized. In our case, this will be wrong, because <span style="font-family: courier;">__new__()</span> will return an already-initialized object from its table. The state of this object may already have been modified, and initializing it again would incorrectly overwrite these changes. We therefore need to prevent a second initialization. This is the purpose of the <span style="font-family: courier;">*already_initialized*</span> attribute; we set this to indicate that the object shouldn't be initialized again. We use a name that is not a legal identifier in order to prevent accidental collisions with users who may choose a similar, but legal, name for a class attribute.</p><p>The way to prevent re-initialization is to create or modify the class's <span style="font-family: courier;">__init__()</span> method so it skips initialization if <span style="font-family: courier;">*already_initialized*</span> is true for the object. Again there are two cases, depending on whether or not the class already has an <span style="font-family: courier;">__init__()</span> method:</p><p><span style="font-family: courier;">init = getattr(cls, '__init__', None)<br />if init is None:<br /> def __init__(self, *args, **kwargs):<br /> if not (hasattr(self, '*already_initialized*')<br /> and getattr(self, '*already_initialized*')):<br /> <span style="color: #2b00fe;">super().__init__(self, *args, **kwargs)</span><br />else:<br /> @wraps(init)<br /> def __init__(self, *args, **kwargs):<br /></span><span style="font-family: courier;"> if not (hasattr(self, '*already_initialized*')<br /> and getattr(self, '*already_initialized*')):<br /> </span><span style="font-family: courier;"> <span style="color: #2b00fe;">init(self, *args, **kwargs)</span><br /><br />setattr(cls, '__init__', __init__)</span> <br /></p><p>Finally a reset method is created if requested, and the original (but modified) class is returned:</p><p><span style="font-family: courier;">if reset_method:<br /> def reset_intern_method():<br /> nonlocal memory<br /> memory = WeakValueDictionary()<br /><br /> setattr(cls, reset_method, reset_intern_method)<br /><br />return cls</span><br /></p><p><br /></p>Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com0tag:blogger.com,1999:blog-5536017433265189318.post-40420369496615826572022-12-25T15:06:00.002+02:002022-12-26T16:16:11.746+02:00Metaprogramming in Python 1: Introduction<h1 style="text-align: left;"><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjx5To_4V5T7TNT2JhQYH_AOfbVVWQKNQnzc5Qj3Dh5rDM4odtvwOklfwn51CbjJY2DwzeezcNql9lyTvMpChintDMvCu5BwyLVxiK104qDFiDPrWeKLNghwuDAAjmaO1VdJDcqsXOGXNJCbn-W7XQ_GgkF2JS__JtAUMNZjqmQe68q7m2nV2bLRvmfJw/s5700/code-brain.Original.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="3800" data-original-width="5700" height="426" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjx5To_4V5T7TNT2JhQYH_AOfbVVWQKNQnzc5Qj3Dh5rDM4odtvwOklfwn51CbjJY2DwzeezcNql9lyTvMpChintDMvCu5BwyLVxiK104qDFiDPrWeKLNghwuDAAjmaO1VdJDcqsXOGXNJCbn-W7XQ_GgkF2JS__JtAUMNZjqmQe68q7m2nV2bLRvmfJw/w640-h426/code-brain.Original.jpg" width="640" /></a></div></h1><h1 style="text-align: left;">Contents</h1><p style="text-align: left;">Part 1: Introduction </p><p style="text-align: left;"><a href="https://the-dusty-deck.blogspot.com/2022/12/metaprogramming-in-python-2-interning.html" target="_blank">Part 2: An Interning Decorator</a><br /></p><p style="text-align: left;">See also the discussion of <a href="https://the-dusty-deck.blogspot.com/2022/01/whats-wrong-with-pythons-super.html" target="_blank">how to do <span style="font-family: courier;">super()</span> in Python correctly</a>; the <a href="https://github.com/yishaif/parseltongue/blob/main/extensions/super/precursor.py" target="_blank">implementation</a> uses inspection to find the correct super method to apply.<br /></p><h1 style="text-align: left;">Series Introduction</h1><p>Metaprogramming is (among other things) a way of programming general techniques that operate by transforming a target program in various ways. Python has many features that are implemented using metaprogramming, including static and class methods, abstract classes and methods, data classes, properties, and context managers.</p><p>Python also exposes metaprogramming facilities that enable Python developers to create their own features. These include an elaborate data model that has many hooks for modifying the standard behavior of the language, and decorators, which are a handy shorthand mechanism for applying new features to user code.</p><p>In this series of posts I will present several new and useful features and show how they can be implemented using Python's metaprogramming facilities.</p><h1 style="text-align: left;">A Little History</h1><p>Metaprogramming, in the sense of programs operating on other programs, includes assemblers, compilers, linkers, and loaders, and therefore harks back to the early days of computing. Metaprogramming in the more restricted sense used in this series, of language facilities that enable modifying the default behavior of the language itself, also has its roots in one of the earliest high-level language, <a href="https://en.wikipedia.org/wiki/Lisp_(programming_language)" target="_blank">Lisp</a>. Unlike other early languages, which focused on scientific or business processing, Lisp was all about symbolic processing, and was one of the major languages used for Artificial Intelligence research for several decades.<br /></p><p>Because of its focus on symbolic processing, a list is the basic data structure of Lisp (hence the name of the language, a contraction of <i>list processing</i>). A Lisp program is also a list (with other lists nested inside it), so that writing Lisp interpreters and manipulating Lisp programs in Lisp is easy and natural. The creators and many of the users of Lisp were also interested in language design, and created many features and language dialects by modifying the Lisp interpreter, and using metaprogramming. These came together in the early 1980s to create a specification for <a href="https://en.wikipedia.org/wiki/Common_Lisp" target="_blank">Common Lisp</a>, an attempt to collect the best features of previous dialects into a single language. The Common Lisp Object System (CLOS) exposed its implementation through the CLOS <a href="https://users.cs.duke.edu/~vahdat/ps/mop.pdf" target="_blank">Meta-Object Protocol</a>, which enabled extensive customizations of the behavior of the basic language mechanisms.</p><p>Lisp, and Common Lisp in particular, had a strong influence on many newer languages, including Python, which follows the tradition of providing powerful metaprogramming capabilities. This series will demonstrate how these can be used to add useful features to the language in a way that is very easy to use.<br /></p><h1 style="text-align: left;"><span style="font-family: georgia;">Metaprogramming</span></h1><p style="text-align: left;"><span style="font-family: georgia;">There are many definitions of metaprogramming; very generally, it refers to programs that operate on other programs (<a href="https://cs.lmu.edu/~ray/notes/metaprogramming/" target="_blank">https://cs.lmu.edu/~ray/notes/metaprogramming/</a>).
In the context of this series, it refers to a set of mechanisms for changing the
standard behavior of a programming language in flexible ways. The
major mechanisms we will use are:</span></p><ul style="text-align: left;"><li><span style="font-family: georgia;">d</span><span style="font-family: georgia;">ynamically and
programmatically adding or modifying class methods;</span></li><li><span style="font-family: georgia;">m</span><span style="font-family: georgia;">odifying the behavior of class constructors
so that they don't necessarily create objects of the class, or even any new objects</span><span style="font-family: georgia;">;<br /></span></li><li><span style="font-family: georgia;">modifying
classes, </span><span style="font-family: georgia;">methods, </span><span style="font-family: georgia;">or </span><span style="font-family: georgia;">functions </span><span style="font-family: georgia;">using decorators; and</span></li><li><span style="font-family: georgia;">inspecting classes, methods, and functions to find relevant properties at runtime.<br /></span></li></ul><h3 style="text-align: left;"><span style="font-family: georgia;">Adding or Modifying Class Methods</span></h3><p style="text-align: left;"><span style="font-family: georgia;">Adding or modifying class methods can be done as for any class attribute, using</span> <a href="https://docs.python.org/3/library/functions.html#setattr" target="_blank"><span style="font-family: courier;">setattr()</span></a> <span style="font-family: georgia;">and</span> <a href="https://docs.python.org/3/library/functions.html#getattr" target="_blank"><span style="font-family: courier;">getattr()</span></a>.<span style="font-family: georgia;"> These methods are similar to the use of dot notation to access a class attribute (as in </span><span style="font-family: courier;">"abc".capitalize()</span>).<span style="font-family: georgia;">
Unlike dot notation, you can use them to get and set attributes whose
names are not fixed in the source code. We will use these to create or
modify the behavior of classes according to the feature we are implementing.<br /></span></p><h3 style="text-align: left;"><span style="font-family: georgia;">Modifying Class Constructors <br /></span></h3><p style="text-align: left;"><span style="font-family: georgia;">Many
of Python's metaprogramming facilities operate through "magic" methods,
whose names have double underscores at the beginning and end (and are
therefore called "dunder methods"). Most of these are part of Python's <a href="https://docs.python.org/3/reference/datamodel.html" target="_blank">data model</a>.<br /></span></p><p style="text-align: left;"><span style="font-family: georgia;">Changing the behavior of class constructors is done in Python through the magic method</span> <a href="https://docs.python.org/3/reference/datamodel.html#object.__new__" target="_blank"><span style="font-family: courier;">__new__()</span></a>.<span style="font-family: georgia;">
This is a static method that is automatically invoked during the
processing of a constructor call. By default, it creates a new object,
which is then initialized by the<span style="font-family: courier;"> __init__()</span> method. However, you can
override this method to return any object of any class, including
previously-created objects. </span></p><h3 style="text-align: left;"><span style="font-family: georgia;">Decorators <br /></span></h3><p><span style="font-family: georgia;">Decorators
are a very powerful Python mechanism that can apply arbitrary code to a
class, method, or function object and modify or replace it to customize
its behavior. One of the best known decorators in Python is <span style="font-family: courier;">@staticmethod</span>, which turns a method defined inside a class into a static method (one that does not take the <span style="font-family: courier;">self</span>
object as a parameter). A decorator is a function that takes the
decorated class, method, or function, and returns another one to replace
the original. Syntactically, it is written as the name of the decorator preceded by an at-sign (</span><span style="font-family: georgia;"><span style="font-family: courier;">@</span></span><span style="font-family: georgia;">); the decorator is placed before the class, method, or function definition it modifies.</span></p><p><span style="font-family: georgia;">The meaning of a decorator written this way is to replace the defined element by whatever the decorator function returns when given the result of the original definition. For example, the effect of the definition</span></p><p><span style="font-family: courier;"><span>@dataclass<br />class Foo:<br /> f1: int<br /> f2: str</span></span></p><p><span style="font-family: georgia;">will be first to create the class </span><span style="font-family: courier;"><span>Foo</span></span><span style="font-family: georgia;">, which has two <i>class-level</i> fields, </span><span style="font-family: courier;"><span>f1</span></span><span style="font-family: georgia;"> and </span><span style="font-family: courier;"><span>f2</span></span><span style="font-family: georgia;">. Without the decorator, these fields belong to the class rather than to specific instances, and are therefore shared between all instances. However, the decorator corresponds to the following statement:</span></p><p><span style="font-family: courier;"><span>Foo = dataclass(Foo)</span></span></p><p><span style="font-family: georgia;">The </span><span style="font-family: courier;"><span>dataclass</span></span><span style="font-family: georgia;"> function examines the class object it receives (the one that has two class-level fields), and modifies it by (among other things) creating a method <span style="font-family: courier;">__init__(f1: int, f2: str)</span>; this new method create two <i>instance-level</i> fields in every object of the class.</span></p><p><span style="font-family: georgia;">The </span><span style="font-family: courier;"><span>dataclass</span></span><span style="font-family: georgia;"> </span><span style="font-family: georgia;"> decorator can take various arguments that change the way it works on the given class, making it very flexible. For more details, see <a href="https://docs.python.org/3/library/dataclasses.html" target="_blank">the documentation</a>.<br /></span></p><h3 style="text-align: left;">Inspection</h3><p style="text-align: left;">Inspection (also called introspection) is the ability of a program to investigate properties of itself. This can include its global data (variables, classes, functions), the methods of a class, the arguments of a function or method, and much more. This is useful for metaprogramming because the behavior being implemented may depend on these properties of the parts of the program it modifies.</p><p style="text-align: left;">As one example, modifying the behavior of object initialization, as done by the <span style="font-family: courier;">__init__()</span> method, depends on whether or not a class defines this method. Finding such a method definition in the class, as described above, is a simple case of inspection.</p><p style="text-align: left;">For a more complex example, see the series of posts on <a href="https://the-dusty-deck.blogspot.com/2022/01/whats-wrong-with-pythons-super.html" target="_blank">how to do <span style="font-family: courier;">super()</span> in Python correctly</a> and the corresponding <a href="https://github.com/yishaif/parseltongue/blob/main/extensions/super/precursor.py" target="_blank">implementation</a>. </p><h3 style="text-align: left;">Putting Things Together</h3><p>When adding a feature to the language, you will often have to create new classes, methods, or functions, or modify existing ones. Your code will often need to override some of the magic dunder methods. You will then probably deliver this functionality in the form of a decorator, like <span style="font-family: courier;"><span>dataclass</span></span><span style="font-family: georgia;"> </span><span style="font-family: georgia;"> </span>. Subsequent posts will illustrate how this is done.<br /></p>Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com0tag:blogger.com,1999:blog-5536017433265189318.post-67214439876684351802022-03-14T12:54:00.000+02:002022-03-14T12:54:29.975+02:00Implementing precursor in Python<p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/a/AVvXsEiJeO3E98duZVgLFbYEk8RnL0KqYV2H5GeOE4WBysjhhU9IIeapnEhe8wxT0eL2JcnpA0kXdTtYdq_vnS17FTOkJJvL0alSbQewEHkk1cynuWdGUnkTvJV6gU3jqsbaZyKAapxYVHJWBrcsuKnS7khEq3AvPVs_AjBnJ0yG4jRQAQu5pVsRjFVP4h0w0Q=s4640" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="2610" data-original-width="4640" height="275" src="https://blogger.googleusercontent.com/img/a/AVvXsEiJeO3E98duZVgLFbYEk8RnL0KqYV2H5GeOE4WBysjhhU9IIeapnEhe8wxT0eL2JcnpA0kXdTtYdq_vnS17FTOkJJvL0alSbQewEHkk1cynuWdGUnkTvJV6gU3jqsbaZyKAapxYVHJWBrcsuKnS7khEq3AvPVs_AjBnJ0yG4jRQAQu5pVsRjFVP4h0w0Q=w489-h275" width="489" /> </a></div><div class="separator" style="clear: both; text-align: center;"> </div><span style="font-family: georgia;">In <a href="https://the-dusty-deck.blogspot.com/2022/01/whats-wrong-with-pythons-super.html">Part 1</a> of this series I explained why the Python interpretation of</span> <span style="font-family: courier;">super()</span><span style="font-family: georgia;"> is flawed and how it limits the user of <span style="font-family: courier;">super()</span> to carefully controlled situations. In <a href="https://the-dusty-deck.blogspot.com/2022/01/the-principles-of-deferring-to.html">Part 2</a>, I discussed the theoretical principles behind <span style="font-family: courier;">super()</span>, and how it can be implemented in Python based on these principles.</span><p></p><p><span style="font-family: georgia;">The <a href="https://github.com/yishaif/parseltongue/tree/main/extensions/super" target="_blank">sample implementation</a> uses inspection to find out the required information about the caller of the <span style="font-family: courier;">precursor()</span>, <span style="font-family: courier;">precursor_of()</span>, and <span style="font-family: courier;">static_super()</span> functions. This is inefficient, but is easily implemented using available Python features. A better implementation, like that of the existing <span style="font-family: courier;">super()</span>, would be done in the Python compiler.</span></p><p><span style="font-family: georgia;"> 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 </span><span style="font-family: georgia;"><span style="font-family: courier;">super()</span>.</span></p><p><span style="font-family: georgia;">We start with the best version (the one that best fits the theoretical principles), which is the precursor, in <a href="https://github.com/yishaif/parseltongue/blob/main/extensions/super/precursor.py">https://github.com/yishaif/parseltongue/blob/main/extensions/super/precursor.py</a>.</span></p><p><span style="font-family: georgia;">Assuming that the <span style="font-family: courier;">precursor</span> 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 </span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">precursor</span></span> 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.</span></p><p><span style="font-family: georgia;">This is done by the function <span style="font-family: courier;">find_static_caller</span>. It first inspects the calling frame, which it gets as an argument. (This is computed in the function </span><span style="font-family: georgia;"><span style="font-family: georgia;"></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">precursor</span></span></span>, using the expression </span><span style="font-family: georgia;"><span style="font-family: courier;"><span class="pl-s1"><span class="pl-token" data-hydro-click-hmac="ab3d940e9996af2f5ba605fe1ac8103d55d7cd2c65fc57abb1b9d509a5d018ed" data-hydro-click="{"event_type":"code_navigation.click_on_symbol","payload":{"action":"click_on_symbol","repository_id":448604849,"ref":"main","language":"Python","backend":"ALEPH_PRECISE","code_nav_context":"BLOB_VIEW","retry_backend":"","originating_url":"https://github.com/yishaif/parseltongue/find-definition?q=inspect&blob_path=extensions%2Fsuper%2Fprecursor.py&ref=main&language=Python&row=29&col=20&code_nav_context=BLOB_VIEW","user_id":null}}">inspect</span></span>.<span class="pl-en"><span class="pl-token" data-hydro-click-hmac="098b90096188ba724beeddefeab4e92d83528eb62fb8bbd27dcd2637a7f4d152" data-hydro-click="{"event_type":"code_navigation.click_on_symbol","payload":{"action":"click_on_symbol","repository_id":448604849,"ref":"main","language":"Python","backend":"ALEPH_PRECISE","code_nav_context":"BLOB_VIEW","retry_backend":"","originating_url":"https://github.com/yishaif/parseltongue/find-definition?q=getouterframes&blob_path=extensions%2Fsuper%2Fprecursor.py&ref=main&language=Python&row=29&col=28&code_nav_context=BLOB_VIEW","user_id":null}}">getouterframes</span></span>(<span class="pl-s1"><span class="pl-token" data-hydro-click-hmac="1567f6cc918284a3de13d06b825f60b95299d9eca313b3f80ff85a616c4da942" data-hydro-click="{"event_type":"code_navigation.click_on_symbol","payload":{"action":"click_on_symbol","repository_id":448604849,"ref":"main","language":"Python","backend":"ALEPH_PRECISE","code_nav_context":"BLOB_VIEW","retry_backend":"","originating_url":"https://github.com/yishaif/parseltongue/find-definition?q=inspect&blob_path=extensions%2Fsuper%2Fprecursor.py&ref=main&language=Python&row=29&col=43&code_nav_context=BLOB_VIEW","user_id":null}}">inspect</span></span>.<span class="pl-en">currentframe</span>())[<span class="pl-c1">1</span>]</span>.) 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 <span style="font-family: courier;">self</span>). The most tricky part is finding the particular method implementation that called </span><span style="font-family: georgia;"><span style="font-family: georgia;"></span><span style="font-family: georgia;"><span style="font-family: georgia;"></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">precursor</span></span></span></span>. 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.</span></p><p><span style="font-family: georgia;">The </span><span style="font-family: georgia;"><span style="font-family: georgia;"></span><span style="font-family: georgia;"><span style="font-family: georgia;"></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">precursor</span></span></span></span> 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.</span></p><p><span style="font-family: georgia;">If there are multiple base classes, </span><span style="font-family: georgia;"><span style="font-family: georgia;"></span><span style="font-family: georgia;"><span style="font-family: georgia;"></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">precursor_of</span></span></span></span> must be called instead of </span><span style="font-family: georgia;"><span style="font-family: georgia;"></span><span style="font-family: georgia;"><span style="font-family: georgia;"></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">precursor</span></span></span></span>, to provide an explicit superclass whose implementation is to be called. The details are similar to that of </span><span style="font-family: georgia;"><span style="font-family: georgia;"></span><span style="font-family: georgia;"><span style="font-family: georgia;"></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">precursor</span></span></span></span>, except that </span><span style="font-family: georgia;"><span style="font-family: georgia;"></span><span style="font-family: georgia;"><span style="font-family: georgia;"></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">precursor_of</span></span></span></span> 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.</span></p><p><span style="font-family: georgia;">As I said in <a href="https://the-dusty-deck.blogspot.com/2022/01/the-principles-of-deferring-to.html">Part 2</a> 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 <span style="font-family: courier;">static_super</span> in <a href="https://github.com/yishaif/parseltongue/blob/main/extensions/super/static_super.py">https://github.com/yishaif/parseltongue/blob/main/extensions/super/static_super.py</a>.</span></p><p><span style="font-family: georgia;">This implementation is similar to that of</span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;"></span></span></span></span></span></span> <span style="font-family: georgia;"></span><span style="font-family: georgia;"><span style="font-family: georgia;"></span><span style="font-family: georgia;"><span style="font-family: georgia;"></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">precursor</span></span></span></span></span>. <span style="font-size: small;"> <span style="font-family: georgia;">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 <span style="font-family: courier;"><span class="pl-v">SuperCaller</span></span> 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 <span style="font-family: courier;"><span class="pl-en">__getattr__</span></span> 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 <span style="font-family: courier;"><span class="pl-en">getattr</span>(<span class="pl-s1">self</span>.<span class="pl-s1">cls</span>, <span class="pl-s1">method</span>)</span>), 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 <span style="font-family: courier;">functools.partial</span>).<br /></span></span><br /></p>Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com0tag:blogger.com,1999:blog-5536017433265189318.post-20759749385974171012022-01-20T12:36:00.001+02:002022-03-14T12:53:28.071+02:00The Principles of Deferring to a Superclass, or How to Do super() Right<p><span style="font-family: georgia;"></span></p><div style="text-align: center;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><a href="https://blogger.googleusercontent.com/img/a/AVvXsEh4e_XFNFlwSiEZkpWCUjnd3Rtm4hEYOqirWln1qM54eWItX2buttOZuIWeipGguUgtMi2Obatx3_CHaXxi5JgiEG01Ebza3dZ7R1G5oaVNoLnTIipRUSSjnk8YHdrguJm9qecz8Gbuapz8ZPfF04AlbeEo3m_AfMjVhDOPzzQdkGYUJnbAnkavtpcnxg=s4640" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="2610" data-original-width="4640" height="310" src="https://blogger.googleusercontent.com/img/a/AVvXsEh4e_XFNFlwSiEZkpWCUjnd3Rtm4hEYOqirWln1qM54eWItX2buttOZuIWeipGguUgtMi2Obatx3_CHaXxi5JgiEG01Ebza3dZ7R1G5oaVNoLnTIipRUSSjnk8YHdrguJm9qecz8Gbuapz8ZPfF04AlbeEo3m_AfMjVhDOPzzQdkGYUJnbAnkavtpcnxg=w551-h310" width="551" /></a></span></span></span> </span></div><p></p><p><span style="font-family: georgia;">In a <a href="https://the-dusty-deck.blogspot.com/2022/01/whats-wrong-with-pythons-super.html" target="_blank">previous post</a> I showed how Python's implementation of <span style="font-family: courier;">super()</span> is unpredictable and therefore impossible to use reliably. What are the theoretical principles on which a correct implementation should be built?</span></p><p><span style="font-family: georgia;">I have written before on <a href="https://the-dusty-deck.blogspot.com/search/label/Design%20by%20contract" target="_blank">Design by Contract</a>, a practical methodology for correct object-oriented design. In a nutshell, it requires every class to have a <i>class invariant,</i> which specifies the acceptable states of objects of that class. For example, a container class must ensure that its size as reported (or stored in a class field) is always non-negative. The invariant must be maintained at all times, except when inside the implementation of a class method. In the absence of concurrent executions of methods on the same object, it is sufficient to guarantee that the constructor establishes the invariant, and that every method maintains it. In addition, each method has a <i>precondition,</i> which specifies the legal configurations (object state and argument values) in which it is possible to call the method, and a <i>postcondition,</i> which specifies the state in which the method must leave the object, as a function of its previous state and the argument values. The precondition is the responsibility of the caller; for example, it is illegal to call <span style="font-family: courier;">pop()</span> on a stack when its </span><br /><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">empty()</span> method returns true. The postcondition, the responsibility of the method implementation; for example, after pushing an element to the stack, it must be the top element of the stack, and all other elements must stay the same.</span></span></p><p><span style="font-family: georgia;"><span style="font-family: georgia;">From the point of view of the programmer who calls any operation on an object, the relevant contract is that of the static type of the object, since the dynamic type can't be known when writing the code; however, it must be a subtype of the static type. The Design by Contract methodology follows <a href="https://en.wikipedia.org/wiki/Liskov_substitution_principle" target="_blank">Liskov's Substitution Principle</a>, which implies that a subclass must obey the contracts of all its superclasses. Therefore, relying on the static type is always correct.</span></span></p><p><span style="font-family: georgia;"><span style="font-family: georgia;">However, in the Python implementation of <span style="font-family: courier;">super()</span>, this isn't true. As we saw in the <a href="https://the-dusty-deck.blogspot.com/2022/01/whats-wrong-with-pythons-super.html" target="_blank">previous post</a></span></span><span style="font-family: georgia;"><span style="font-family: georgia;">, a super call can invoke an implementation from a class that is not a superclass of the static type of the receiver object. In the last example shown there, the call <span style="font-family: courier;">super(ContainerMixin, self).__init__(**properties)</span> in the class <span style="font-family: courier;">Document</span> could invoke a method of an unrelated class (<span style="font-family: courier;">SomeMixin</span>). Under such behaviors, it is impossible to know what is the contract of the called method, and therefore impossible to write correct code. The only way to enable developers to write correct and reliable code is to restrict super calls to static superclasses; that is, superclasses of the class in which the super call appears, regardless of the dynamic type of the receiver object.</span></span></p><p><span style="font-family: georgia;"><span style="font-family: georgia;">In addition, the super mechanism in Python (and most other object-oriented languages, including Java and C++) allows <i>diagonal calls,</i> in which one method can call a different method on the super object. This is rarely done in practice, and should be disallowed in principle, since it bypasses the contract of the called method. The implementation of a method can use implementations provided by superclasses for the same method, and will need to be mindful of their contracts; but if it needs a service from another method of the same object, it should call the implementation provided for that object, which is the only one that is responsible for the correct contract. (Remember that the dynamic type of the object, which determines its contract, is not known when writing the code.)<br /></span></span></p><p><span style="font-family: georgia;"><span style="font-family: georgia;"><a href="https://en.wikipedia.org/wiki/Bertrand_Meyer" target="_blank">Bertrand Meyer</a>, the author of the Design by Contract methodology, embodied this methodology in the programming language #<a href="https://en.wikipedia.org/wiki/Eiffel_(programming_language)" target="_blank">Eiffel</a>. In Eiffel, the super construct is called <i>Precursor, </i>and calls the implementation of the method in which it appears in the immediate (static) superclass, if there is exactly one such. Otherwise, Precursor needs to be decorated with the name of one of the static superclasses, whose implementation is to be invoked. This adheres to the principles above: it is based on static relationships between classes, and so the relevant contract is always known; and it prohibits diagonal calls.</span></span></p><p><span style="font-family: georgia;"><span style="font-family: georgia;">This behavior can be implemented in Python, although a more efficient implementation will have to be done inside the compiler. Before we show the implementation, let's look at a particularly difficult example. This is taken from Meyer's book, </span></span><br /><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><a href="http://www.amazon.com/gp/product/0136291554/ref=as_li_tl?ie=UTF8&camp=1789&creative=9325&creativeASIN=0136291554&linkCode=as2&tag=thdude04-20&linkId=EVKD6KLM4U62RXQB" target="_blank"><i>Object-Oriented Software Construction</i></a></span></span></span></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"> (2nd edition),</span></span></span></span> and is based on an earlier example from Stroustrup's book <a href="https://amzn.to/3H2nKfP" target="_blank"><i>The C++ Programming Language</i></a>.</span></span></span></span></p><p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;">In this example, we have a <span style="font-family: courier;">Window</span> class, describing a window or widget in a graphical user interface. One of the important methods of this class is <span style="font-family: courier;">draw()</span>, which draws the contents of the window on the screen. Some windows have borders, and some have menus. These are described by subclasses <span style="font-family: courier;">WindowWithBorder</span> and <span style="font-family: courier;">WindowWithMenu</span>, respectively. The implementation of the <span style="font-family: courier;">draw()</span> method in each of these subclasses first needs to draw the window, using the method in the parent <span style="font-family: courier;">Window</span> class, and then add the border or menu. The implementation of these classes could look like this, translated into Python syntax:</span></span></span></span></p><p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"></span></span></span></p><blockquote><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">class Window:<br /> def draw(self):<br /> print('Window.draw()')<br /><br /><br />class WindowWithBorder(Window):<br /> def draw_border(self):<br /> print('WindowWithBorder.draw_border()')<br /><br /> def draw(self):<br /> print('WindowWithBorder.draw()')<br /> precursor()<br /> self.draw_border()<br /><br /><br />class WindowWithMenu(Window):<br /> def draw_menu(self):<br /> print('WindowWithMenu.draw_menu()')<br /><br /> def draw(self):<br /> print('WindowWithMenu.draw()')<br /> precursor()<br /> self.draw_menu()</span><br /></span></span></span></span></blockquote><p></p><p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;">Running the following test will print the output shown:</span></span></span></span></p><p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"></span></span></span></span></p><blockquote><p><span style="font-family: courier;">wb = WindowWithBorder()<br />wb.draw()<br /></span><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">print('***')<br /></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>wm = WindowWithMenu()<br />wm.draw()</span><br /></p></blockquote><p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;">Output: <br /></span></span></span></span></p><p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"></span></span></span></p><blockquote><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">WindowWithBorder.draw()<br />Window.draw()<br />WindowWithBorder.draw_border()<br />***<br />WindowWithMenu.draw()<br />Window.draw()<br />WindowWithMenu.draw_menu()</span><br /></span></span></span></span></blockquote><p></p><p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;">This demonstrates that the correct methods are called, in the correct order. <br /></span></span></span></span></p><p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;">But what about windows that have both borders and menus? These would be described by a class <span style="font-family: courier;">WindowWithBorderAndMenu</span>, which should inherit from both </span></span></span></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">WindowWithBorder</span> and <span style="font-family: courier;">WindowWithMenu</span></span></span></span></span>. Unfortunately, its </span></span></span></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">draw()</span> method must not call the implementations in its immediate superclasses, since that will call <span style="font-family: courier;">Window.draw()</span> twice; this is likely to undo the effects of the call from the previous superclass, and may well cause other issues. Instead, the implementation of <span style="font-family: courier;">draw()</span> in this class should call the <span style="font-family: courier;">Window</span> implementation, followed by <span style="font-family: courier;">draw_border()</span> and <span style="font-family: courier;">draw_menu()</span>.</span></span></span></span></span></span></span></span></p><p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"></span></span></span></span></span></span></span></p><blockquote><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">class WindowWithBorderAndMenu(WindowWithBorder,<br /> WindowWithMenu):<br /> def draw(self):<br /> print('WindowWithBorderAndMenu.draw()')<br /><span style="color: #2b00fe;"> precursor_of(Window)()</span><br /> self.draw_border()<br /> self.draw_menu()</span><br /></span></span></span></span></blockquote><p></p><p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;">The blue line shows how to call the implementation in a superclass, using a different function <span style="font-family: courier;">precursor_of</span>, which takes the appropriate class object as a parameter and returns the method implementation from that class.</span></span></span></span></span></span></span></span></p><p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"></span></span></span></span></span></span></span></span></p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;">Eiffel prohibits calling a method implementation that is not in one of the immediate superclasses, based on the consideration that jumping over an implementation is likely to miss important parts of the implementation. However, in this case this is justified, and it is possible to do this in Eiffel by inheriting yet again from <span style="font-family: courier;">Window</span>, this time directly. My implementation of precursor in Python does allow such jumps, although this can be changed.</span></span></span><p></p><p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;">The following test of </span></span></span></span></span></span></span></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">WindowWithBorderAndMenu</span></span></span></span></span></span></span></span></span> will give the output shown:</span></span></span></span></span></span></span></span></p><p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"></span></span></span></span></span></span></span></p><blockquote><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">wbm = WindowWithBorderAndMenu()<br />wbm.draw()</span><br /></span></span></span></span></blockquote><p></p><p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;">Output:</span></span></span></span></span></span></span></span></p><p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"></span></span></span></span></span></span></span></p><blockquote><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">WindowWithBorderAndMenu.draw()<br />Window.draw()<br />WindowWithBorder.draw_border()<br />WindowWithMenu.draw_menu()</span><br /></span></span></span></span></blockquote><p></p><p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;">How does this magic happen? The short answer is "with some reflection." Getting more technical, we use Python's <span style="font-family: courier;">inspect</span> module to find the frame that called the <span style="font-family: courier;">precursor()</span> function. From that frame we can extract the name of the method, as well as the target of the call (that is, the receiver object), and the <span style="font-family: courier;">__bases__</span> field of its class gives the list of superclasses. T</span></span></span></span></span></span></span></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;">he <span style="font-family: courier;">precursor()</span> function will only work if there is a single superclass, in which case it will call the implementation of the called method from that superclass (or whatever that superclass defers to).</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></p><p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;">The <span style="font-family: courier;">precursor_of()</span> function is similar, but instead of searching for a unique superclass it accepts the superclass as an argument. It then returns an internal function that will invoke the correct method implementation when it is called. (This is why there is another set of parentheses in the call marked in blue in the code above; this is where you would provide any arguments to the super method.)</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></p><p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;">You can find the full implementation in my github repo <a href="https://github.com/yishaif/parseltongue" target="_blank">yishaif/parseltongue</a>, in the <a href="https://github.com/yishaif/parseltongue/tree/main/extensions/super" target="_blank">extensions/super</a> directory; tests are in <a href="https://github.com/yishaif/parseltongue/tree/main/extensions/test" target="_blank">extensions/tests</a>.<br /></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></p><p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;">Of course, using reflection for every super call is not advisable. This implementation is just an example of how this could work; an efficient implementation would have to be part of the Python compiler.</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></p><p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;">But what if you perversely want a static super implementation that can still perform diagonal calls? I don't want to encourage you to do such a thing, but it can certainly be done. Here is the windowing example using this style. I am using the functions <span style="font-family: courier;">static_super()</span> and </span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">static_super_of()</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>instead of </span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">super()</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>, so as not to interfere with Python's builtin function. The first is for the case in which the class has a single immediate superclass, and the second is for multiple inheritance, and takes a parameter that specified the class whose implementation is to be invoked. The changes from the previous example are in blue.<br /></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></p><p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">class Window:<br /> def draw(self):<br /> print('Window.draw()')<br /><br /><br />class WindowWithBorder(Window):<br /> def draw_border(self):<br /> print('WindowWithBorder.draw_border()')<br /><br /> def draw(self):<br /> print('WindowWithBorder.draw()')<br /> <span style="color: #2b00fe;">static_super().draw()</span><br /> self.draw_border()<br /><br /><br />class WindowWithMenu(Window):<br /> def draw_menu(self):<br /> print('WindowWithMenu.draw_menu()')<br /><br /> def draw(self):<br /> print('WindowWithMenu.draw()')<br /> <span style="color: #2b00fe;">static_super().draw()</span><br /> self.draw_menu()<br /><br /><br />class WindowWithBorderAndMenu(WindowWithBorder, WindowWithMenu):<br /> def draw(self):<br /> print('WindowWithBorderAndMenu.draw()')<br /> <span style="color: #2b00fe;">static_super_of(Window).draw()</span><br /> self.draw_border()<br /> self.draw_menu()</span><br />Here are the tests, with the output:</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></p><p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;"></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></p><blockquote><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">wb = WindowWithBorder()<br />wb.draw()<br /></span><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">print('***')<br /></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>wm = WindowWithMenu()<br />wm.draw()<br /></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">print('***')<br /></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">wbm = WindowWithBorderAndMenu()<br />wbm.draw()</span></span></span></span></span></span></span></span></blockquote><span style="font-family: courier;"></span> <p></p><p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;">Output:</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><br /></p><blockquote><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">WindowWithBorder.draw()<br />Window.draw()<br />WindowWithBorder.draw_border()<br /></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">***<br /></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>WindowWithMenu.draw()<br />Window.draw()<br />WindowWithMenu.draw_menu()<br />***<br /></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">WindowWithBorderAndMenu.draw()<br />Window.draw()<br />WindowWithBorder.draw_border()<br />WindowWithMenu.draw_menu()</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></blockquote><p><span style="font-family: georgia;">As you can see, the results are exactly the same. However, this form enables diagonal calls, since the <span style="font-family: courier;">static_super()</span> object can invoke any method defined in the chosen superclass.</span></p><p><span style="font-family: georgia;">The code for </span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">static_super()</span></span> can be found in the <a href="https://github.com/yishaif/parseltongue/tree/main/extensions/super" target="_blank">same github repo</a>. I will go into the details of the implementation in the <a href="https://the-dusty-deck.blogspot.com/2022/03/implementing-precursor-in-python.html">next post</a>.</span><br /></p><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;"></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><p></p>Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com0tag:blogger.com,1999:blog-5536017433265189318.post-23061605823177080952022-01-09T18:49:00.002+02:002022-03-14T12:54:16.158+02:00What's Wrong with Python's super()?<h1 style="text-align: left;"><span style="font-size: small;"><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/a/AVvXsEgDbWSZB6GQkGMfuu1PRJGZK2r5vPLVdjRcE8QYkkUY17bwJ1F8oirov4c_bRqdjkvHUE7I7E4dS_3UD95ISnJZZPb7SCY9DWDD2TdTBhvY9zRc4ct15P2fSR0DGxKcIyfqxOB1X10i_yiIbJ0xz-LTEQ_qUMNNRfztmhilWPFkqnqT3_o6awPkpEvb8g=s3249" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="2072" data-original-width="3249" height="350" src="https://blogger.googleusercontent.com/img/a/AVvXsEgDbWSZB6GQkGMfuu1PRJGZK2r5vPLVdjRcE8QYkkUY17bwJ1F8oirov4c_bRqdjkvHUE7I7E4dS_3UD95ISnJZZPb7SCY9DWDD2TdTBhvY9zRc4ct15P2fSR0DGxKcIyfqxOB1X10i_yiIbJ0xz-LTEQ_qUMNNRfztmhilWPFkqnqT3_o6awPkpEvb8g=w549-h350" width="549" /></a></div><span style="font-family: georgia;"></span></span></h1><div style="text-align: left;"><p style="text-align: left;"><span style="font-size: small;"><span style="font-family: georgia;">This is Part 1: the problem.</span></span></p><p style="text-align: left;"><span style="font-size: small;"><span style="font-family: georgia;">Jump to <a href="https://the-dusty-deck.blogspot.com/2022/01/the-principles-of-deferring-to.html">Part 2: the solution</a>.</span></span></p><p style="text-align: left;"><span style="font-size: small;"><span style="font-family: georgia;">Jump to <a href="https://the-dusty-deck.blogspot.com/2022/03/implementing-precursor-in-python.html">Part 3: the implementation</a>.<br /></span></span></p><p style="text-align: left;"><span style="font-size: small;"><span style="font-family: georgia;"> </span></span></p><p style="text-align: left;"><span style="font-size: small;"><span style="font-family: georgia;">#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 <i>dynamic binding,</i> 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 <span style="font-family: courier;">super</span> in many languages, including Java and #Python.</span></span></p><p style="text-align: left;"><span style="font-size: small;"><span style="font-family: georgia;">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.<br /></span></span></p><p style="text-align: left;"><span style="font-size: small;"><span style="font-family: georgia;">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 <span style="font-family: courier;">DocumentElement</span>. Classes such as <span style="font-family: courier;">Document</span>, <span style="font-family: courier;">Heading</span>, <span style="font-family: courier;">Paragraph</span>, and <span style="font-family: courier;">List</span> would inherit from </span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">DocumentElement</span></span>.</span></span></p><p style="text-align: left;"><span style="font-size: small;"><span style="font-family: georgia;">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 <a href="https://en.wikipedia.org/wiki/Mixin" target="_blank">mixin</a> classes to selectively make document elements containers or property owners; these could be classes such as:</span></span></p><blockquote><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"></span></span><span style="font-family: courier;">class ContainerMixin:<br /> def __init__(self):<br /> self.contents = []<br /><br /> def add_contents(self, *contents):<br /> self.contents.extend(contents)<br /><br /><br />class PropertyMixin:<br /> def __init__(self):<br /> self.properties = {}<br /><br /> def add_properties(self, **properties):<br /> self.properties.update(properties)</span><br /><span style="font-family: georgia;"><span style="font-family: courier;"></span></span></span></blockquote><p><span style="font-size: small;"><span style="font-family: georgia;">If a document is supposed to have both contents and properties, the class would be declared like this:</span></span></p><blockquote><p><span style="font-family: courier; font-size: small;">class Document(DocumentElement,<br /> ContainerMixin,<br /> PropertyMixin):<br /> def __init__(self):<br /> super().__init__()<br /><br /></span></p></blockquote><p><span style="font-size: small;"><span style="font-family: georgia;">Since neither </span><span style="font-family: georgia;"><span style="font-family: courier;">ContainerMixin</span> nor </span><span style="font-family: georgia;"><span style="font-family: courier;">PropertyMixin</span> have any superclasses other than the default <span style="font-family: courier;">object</span>, you would think that they don't need to call </span><span style="font-family: georgia;"><span style="font-family: courier;">super().__init__()</span>, right? Wrong! The </span><span style="font-family: georgia;"><span style="font-family: courier;">super().__init__()<span style="font-family: georgia;"> </span></span>call in </span><span style="font-family: georgia;"><span style="font-family: courier;">Document</span> calls the <span style="font-family: courier;">__init__</span> method of </span><span style="font-family: georgia;"><span style="font-family: courier;">ContainerMixin</span>, but </span><span style="font-family: georgia;"><span style="font-family: georgia;">the <span style="font-family: courier;">__init__</span> method of <span style="font-family: courier;">Property</span></span><span style="font-family: georgia;"><span style="font-family: courier;">Mixin</span> will not be called, and its <span style="font-family: courier;">properties</span> field will not be initialized. This <i>will</i> happen if </span></span><br /><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;">the <span style="font-family: courier;">__init__</span> method of </span><span style="font-family: georgia;"><span style="font-family: courier;">ContainerMixin</span> calls </span></span></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">super().__init__()</span>; that call will invoke </span></span></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;">the <span style="font-family: courier;">__init__</span> method of <span style="font-family: courier;">Property</span></span><span style="font-family: georgia;"><span style="font-family: courier;">Mixin<span style="font-family: georgia;">, even though </span></span></span></span></span></span></span></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">Property</span></span><span style="font-family: georgia;"><span style="font-family: courier;">Mixin<span style="font-family: georgia;"> </span></span></span></span></span></span></span></span>is not a superclass of </span></span></span></span></span></span></span></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"></span><span style="font-family: georgia;"><span style="font-family: courier;">ContainerMixin</span> </span></span></span>, 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.</span></span></span></span></span></span></span></span></span></p><p><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;">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 <a href="https://www.python.org/download/releases/2.3/mro/" target="_blank">Method Resolution Order</a>, 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 <span style="font-family: courier;">Document</span>, 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 </span></span></span></span></span></span></span></span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-family: courier;">super().__init__()</span> (or any other method), unless you know your class will never be subclassed.<br /></span></span></span></span></span></span></span></span></span></p><p><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;">Unfortunately, this won't work in general. Suppose, for example, that the <span style="font-family: courier;">__init__</span> methods of the mixin classes take arguments:</span></span></span></span></span></span></span> <br /></span></span></p><span style="font-size: small;"><span style="font-family: georgia;"><blockquote><span style="font-family: courier;">class ContainerMixin:</span><span style="font-family: georgia;"><span style="font-family: courier;"></span></span><span style="font-family: georgia;"><span style="font-family: courier;"><br /> def __init__(self, *contents):<br /> self.contents = contents</span><br /><br /><span style="font-family: courier;">class PropertyMixin:<br /> def __init__(</span></span><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-family: courier;">self, </span></span>**properties):<br /> self.properties = </span></span><span style="font-family: georgia;"><span style="font-family: courier;">properties</span></span><br /></blockquote></span></span><p><span style="font-size: small;"><span style="font-family: georgia;">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?</span></span></p><p><span style="font-size: small;"><span style="font-family: georgia;">There is a workaround, but it doesn't work all cases. The trick is to use the 2-argument form of <span style="font-family: courier;">super()</span>. The first argument is one of the receiver object's superclasses, and the second is the object itself. When using this form of </span><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;">super()</span></span>, the implementation that will be invoked for the method call will be the one from the class that <i>follows the given superclass</i> on the MRO list. The code will look like this:</span></span></p><p></p><blockquote><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;">class Document(DocumentElement,<br /> ContainerMixin,<br /> PropertyMixin):<br /> def __init__(self, *contents, **properties):<br /> super().__init__(*contents)<br /> super(ContainerMixin, self).__init__(**properties)</span><br /></span></span></blockquote><p></p><p><span style="font-size: small;"><span style="font-family: georgia;">The first </span></span><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;">super()</span></span></span> call, without arguments, will call the first <span style="font-family: courier;">__init__</span> method of the first superclass on the MRO (that is, one that follows the <span style="font-family: courier;">Document</span> class itself) that provides such a method. If you execute the command <span style="font-family: courier;">print(Document.__mro__)</span>, you will see the following output:</span></span></p><p><span style="font-size: small;"></span></p><blockquote><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;">(<class '__main__.Document'>,<br /> <class '__main__.DocumentElement'>,<br /> <class '__main__.ContainerMixin'>,<br /> <class '__main__.PropertyMixin'>,<br /> <class 'object'>)</span><br /></span></span></blockquote><p></p><p><span style="font-size: small;"><span style="font-family: georgia;">The first superclass is </span></span><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;">DocumentElement</span></span></span>, which has no </span></span><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;">__init__</span> method. The following one is </span></span></span></span><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;">ContainerMixin</span></span></span>, which does, and therefore this is the implementation invoked, with the </span></span></span></span><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;">arguments from</span></span></span></span> <span style="font-family: courier;">contents</span>.</span></span></span></span><br /><span style="font-size: small;"><span style="font-family: georgia;"></span></span></p><p><span style="font-size: small;"><span style="font-family: georgia;">The second <span style="font-family: courier;">super</span> call has </span></span><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;">ContainerMixin</span></span></span> as its first argument. The implementation invoked is therefore searched on the MRO starting with the <i>following</i> class, </span></span><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;">PropertyMixin<span style="font-family: georgia;">, and this indeed accepts the <span style="font-family: courier;">properties</span> argument.</span></span></span></span></p><p><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;">This behavior means that the first <span style="font-family: courier;">super</span> call could also have been written as:</span></span></span></span><br /><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"> super(DocumentElement, self).__init__(*contents)</span></span></span></span></span></p><p><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;">The reason that Python searches the MRO from the class <i>after </i>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, <span style="font-family: courier;">super</span> 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:</span></span></span></span></span></span></p><blockquote><p><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;">super(Document, self).__init__(*contents)</span></span></span></span></span></span></span></span></span></span></span></p></blockquote><p><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;">Note that this assumes that the </span></span></span></span></span></span><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;">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 </span></span></span></span></span></span></span></span></span></span></span></span><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;">DocumentElement</span></span></span></span></span> and </span></span></span></span></span></span></span></span></span></span></span></span><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;">ContainerMixin</span></span></span> on it. For example, if <span style="font-family: courier;">SomeMixin</span> has an <span style="font-family: courier;">__init__</span> method that doesn't call super, the following class definition will not call </span></span></span></span></span></span></span></span></span></span></span></span><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;">PropertyMixin.</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-family: courier;">__init__()</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>:</span></span></span></span></span></span></span></span></span></span></span></span></p><p><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"></span></span></span></span></span></span></span></span></span></span></span></p><blockquote><span style="font-size: small;"><span style="font-family: courier;"><span style="font-size: small;"><span style="font-size: small;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-family: courier;">class MyDocument(Document, SomeMixin, PropertyMixin):<br /> pass</span><br /></span></span></span></span></span></span></blockquote><p></p><p><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;">This definition has the effect of putting </span></span></span></span></span></span></span></span></span></span></span></span><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: courier;"><span style="font-size: small;"><span style="font-size: small;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-family: courier;">SomeMixin</span></span></span></span></span></span></span> before </span></span></span></span></span></span></span></span></span></span></span></span><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: courier;"><span style="font-size: small;"><span style="font-size: small;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-family: courier;">PropertyMixin</span></span></span></span></span></span></span> in the MRO of </span></span></span></span></span></span></span></span></span></span></span></span><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: courier;"><span style="font-size: small;"><span style="font-size: small;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-family: courier;">MyDocument</span></span></span></span></span></span></span>, so that the call </span></span></span></span></span></span></span></span></span></span></span></span><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;">super(ContainerMixin, self).__init__(**properties)</span></span></span> in </span></span></span></span></span></span></span></span></span></span></span></span><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;">Document</span></span></span> actually calls the </span></span></span></span></span></span></span></span></span></span></span></span><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;">__init__</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span> method of </span></span></span></span></span></span></span></span></span></span></span></span><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: courier;"><span style="font-size: small;"><span style="font-size: small;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-family: courier;">SomeMixin</span></span></span></span></span></span></span>, not that of </span></span></span></span></span></span></span></span></span></span></span></span><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: courier;"><span style="font-size: small;"><span style="font-size: small;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-family: courier;">PropertyMixin</span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span>.<br /></span></span></span></span></span></span></span></span></span></span></span></span></p><p><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;">This may seem strange: why put </span></span></span></span></span></span></span></span></span></span></span></span><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-family: courier;">PropertyMixin</span></span></span></span></span></span></span></span></span></span></span></span></span> in the superclass list at all, given that </span></span></span></span></span></span></span></span></span></span></span></span><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-family: courier;">Document</span></span></span></span></span></span></span></span></span></span></span></span></span> already inherits from it? But sometimes this is necessary in order to give precedence to methods of one class over another.</span></span></span></span></span></span></span></span></span></span></span></span></p><p><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;">This behavior is unpredictable, and therefore dangerous, from the point of view of the developer who writes the <span style="font-family: courier;">super()</span> 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.<br /></span></span></span></span></span></span></span></span></span></span></span></span></p><p><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;">All the examples above used the <span style="font-family: courier;">__init__</span> method, but, of course, the same issues apply to any method of the class.<br /></span></span></span></span></span></span></span></span></span></span></span></span></p><p><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;">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 <span style="font-family: courier;">super()</span> 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 <span style="font-family: courier;">(*args, **kwargs)</span>, and passing all arguments to all super methods. Each of these has its own issues, and in any case severely limit the design if <span style="font-family: courier;">super()</span> is to be supported.<br /></span></span></span></span></span></span></span></span></span></span></span></span></p><p><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;">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 <span style="font-family: courier;">super</span> feature.</span></span></span></span></span></span></span></span></span></span></span></span></p><p><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"><span style="font-family: georgia;">What is a sound theoretical basis? I have mentioned <a href="https://the-dusty-deck.blogspot.com/2011/02/design-by-contract.html">Design by Contract</a> in several previous posts, and it also explains how super calls need to be treated. More on this in <a href="https://the-dusty-deck.blogspot.com/2022/01/the-principles-of-deferring-to.html">the next post</a>!<br /></span></span></span></span></span></span></span></span></span></span></span></span></p><p><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: georgia;"><span style="font-family: courier;"></span></span></span></span></p><span style="font-size: small;"><span style="font-family: georgia;"><span style="font-family: courier;"></span></span></span><p></p></div>Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com1tag:blogger.com,1999:blog-5536017433265189318.post-230754253606491822021-12-02T16:26:00.001+02:002021-12-16T15:53:18.926+02:00The Kyng of the Gods<div><p><span style="font-family: georgia;"></span></p><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEif6Bt0S98K-HmpbqGuFIj5cgcDAS6uI-zqLn1Ar71KIsZUsAJS4rzDqszfJgRnLkc_ekkp6rLkaXYJvHAmTA8uUtioXji_HkgtQc39aERHZqQ6h-VcgJ6TG8LeLmXlViFGSQR4fyKq3sOb/s640/radowan-nakif-rehan-cYyqhdbJ9TI-unsplash.jpg" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="479" data-original-width="640" height="383" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEif6Bt0S98K-HmpbqGuFIj5cgcDAS6uI-zqLn1Ar71KIsZUsAJS4rzDqszfJgRnLkc_ekkp6rLkaXYJvHAmTA8uUtioXji_HkgtQc39aERHZqQ6h-VcgJ6TG8LeLmXlViFGSQR4fyKq3sOb/w511-h383/radowan-nakif-rehan-cYyqhdbJ9TI-unsplash.jpg" width="511" /></a></div><p></p><p><span style="font-family: georgia;">I have recently watched several data scientists use #Jupyter #notebooks, and I felt young again!</span></p><p><span style="font-family: georgia;">Notebooks are basically a command-line interface (CLI) on steroids. They make it easy to re-run commands, possibly after changing them, using a modern graphical user interface in a browser. Experimentation is very easy, since you can modify cells and try out various ideas, while keeping the computation state. Unlike textual interfaces, they can show graphical output directly in the same browser window. And you can also add documentation, including graphics, to create a nicely-formatted document that can be used as a live demonstration or explanation.</span></p><p><span style="font-family: georgia;">Like any other CLI, you are free to re-do any action in any order. This freedom comes with the usual cost: you can get confused about the state of your computation. In such cases, you can run the notebook from the start in order to get a consistent state. However, if you are using a notebook in order to investigate the results of a lengthy computation, you will be reluctant to do that, and will have to be more selective about what you re-run.</span></p><p><span style="font-family: georgia;">Occasionally (well, frequently, in my experience) you will want to debug the behavior of your code. Jupyter notebooks do not support a debugger, so you will have to resort to sprinkling print statements in the code, and analyze the output. This is what I used to do when programming in Fortran using punched cards in the 1970s; and removing the print statements was as easy as removing a few cards from the deck!<br /></span></p><p><span style="font-family: georgia;">These days, however, developers are used to having IDEs with interactive debuggers that support stopping at any statement, inspecting the state of the execution stack, and even making modifications before continuing. After enjoying such tools, it is difficult for people like me to revert to debugging with print statements.</span></p><p><span style="font-family: georgia;">IDEs have a lot of other features; notebooks have syntax highlighting, but they don't have:</span></p><ul style="text-align: left;"><li><span style="font-family: georgia;">Context-sensitive completion. Immediately during typing, or on request, the #IDE will provide a list of possible completions for the partial text already written. These depend on the syntactic context, as well as on type information. For example, after typing <span style="font-family: courier;">x.f</span>, the suggestions will include all methods and fields whose names start with "<span style="font-family: courier;">f</span>" and belong to the class of <span style="font-family: courier;">x</span>. The determination of the class of <span style="font-family: courier;">x</span> requires type analysis. This isn't easy even for strongly-typed languages, such as #Java, because the text of the program is incomplete and doesn't even compile. For dynamic languages such as #Python, this is even more difficult. This difficulty applies not only to automated tools, but also to people, which is why this feature is particularly helpful.<br /></span></li><li><span style="font-family: georgia;">Interactive error indications. The IDE will flag parts of the text as likely to contain errors of various kinds. These include syntax errors; references to undefined variables or methods; type errors (again particularly difficult</span><span style="font-family: georgia;"><span style="font-family: georgia;">, and particularly helpful,</span> for dynamic languages); and shadowing of global variables or variables of enclosing contexts.</span></li><li><span style="font-family: georgia;">Intelligent search. This includes "jump to definition" for variables, methods, and types; list all uses of a variable, method, or type (using type analysis to distinguish different elements with the same name); find overridden or overriding methods; and search by element kind with word completion (for example, a search for a class using the partial name <span style="font-family: courier;">DoI</span> will find a class named <span style="font-family: courier;">DomainInformation</span>.</span></li><li><span style="font-family: georgia;">Automatic correction suggestions ("auto-fix"). For many types of errors, the IDE can suggest one or more ways to fix them; these will be done automatically based on the user's choice. <br /></span></li><li><span style="font-family: georgia;">Syntactic transformations. These are things like adding placeholders for abstract methods that need to be implemented in a subclass; commenting or uncommenting a section of code; surrounding an expression with various kinds of parentheses or quotes; and many others.</span></li><li><span style="font-family: georgia;">Refactoring. These are behavior-preserving transformations that can have global effects, and can be difficult to do manually. Examples are renaming a variable, method, or class; extracting an expression into a variable for reuse; extracting a section of code to a separate function or method; inlining a variable or method; moving global elements between modules; and moving methods up or down the inheritance hierarchy.</span></li></ul></div><p><span style="font-family: georgia;">All of these capabilities require deep analysis of the code, including type, data-flow, and control-flow analyses. These are made difficult by more permissive language features (especially dynamic types), and are not always completely accurate. Still, they offer a great boost to productivity, and I have come to rely on all of them, to the extent that I try to minimize my typing and let the IDE do as much of the work as possible. I'm very conscious of error or warning indications; I always try the auto-fix capability, and in many cases find an automatic solution. Refactoring is especially useful; in fact, the availability of refactoring in Eclipse many years ago was the ultimate factor in my moving to IDEs from my beloved Emacs editor for code development.</span></p><p><span style="font-family: georgia;">I recently heard a talk by a self-titled "Chief Data Scientist</span><span style="font-family: georgia;"><span style="font-family: georgia;">,</span>" who only uses Jupyter notebooks for code. When asked whether he misses the capabilities of IDEs, his reply was that anyone who needs those for data science is working at a too-low level. Presumably he limits himself to using existing tools for data exploration, with a minimum of actual programming.<br /></span></p><p><span style="font-family: georgia;">This is a valid position, but my response would be that data scientists who don't need the capabilities I listed above are working at a too-high level, either avoiding serious programming, or depriving themselves of productivity-boosting tools that developers have come to take for granted in the past few decades. I personally suffer when I have to watch them struggling to manually do things that can easily be automated.</span></p><p><span style="font-family: georgia;">While notebooks have many advantages, they are still in essence command-line tools. It is time that advanced IDE features be added to notebooks, to create a really state-of-the-art environment not only for data scientists but for developers as well. I have seen (but not tested) plugins for a number of popular IDEs to support notebooks, but the browser-based Jupyter notebooks still seem to be the tool of choice for data scientists.</span></p><p><span style="font-family: georgia;"><img alt="" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAn0AAAAICAYAAACMA0mWAAAASklEQVR4nO3YwQkAMAgEQWtJU+m/Eq0iBLwZ2L/Pw2oAANar3wcAAPCe0QcAEKD6npYkSdLufPoAAAIYfQAAAYw+AIAARh8AQIABwiCM1SVv3IIAAAAASUVORK5CYII=" /> <br /></span></p><p><span style="font-family: georgia;"><b>Addendum: </b>Thanks to Lev Greenberg for showing me the notebook capabilities of Microsoft's free IDE, <a href="https://code.visualstudio.com/docs/datascience/jupyter-notebooks" target="_blank">Visual Studio Code</a>. They satisfy a lot of the requirements mentioned above, making VSCode a much better environment for code development in notebooks than the web-based Jupyter Notebooks.<br /></span></p>Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com3tag:blogger.com,1999:blog-5536017433265189318.post-8627732649393350542016-06-07T18:47:00.001+03:002016-06-07T18:47:05.371+03:00Robopsychology, Part 1: What Goes on in the Mind of a Cognitive System?<span style="font-family: inherit;">
</span><span style="font-family: inherit;">Dr Susan Calvin in Asimov’s <i>I, Robot</i> is a
robopsychologist. <span style="mso-spacerun: yes;"> </span>As Asimov explains in
the preface, this means a psychologist of robots, and is not to be
misunderstood as a robot who is also a psychologist.<span style="mso-spacerun: yes;"> </span>Robopsychology should perhaps be a
sub-discipline of Cognitive Psychology, but the latter term is firmly
entrenched as relating exclusively to human psychology.<o:p></o:p></span><br />
<span style="font-family: inherit;">
</span><span style="font-family: inherit;"></span><br />
<span style="font-family: inherit;">With increasing interest in Artificial Intelligence and
cognitive systems, it may be time to lay the foundations for
robopsychology.<span style="mso-spacerun: yes;"> </span>What can we learn from
human psychology about cognitive systems?</span><br />
<div class="MsoNormal" style="margin: 0cm 0cm 8pt;">
<span style="font-family: inherit;"></span><br />
<span style="font-family: inherit;">I believe that a useful analogy can be based on the work of
Nobel-laureate Daniel Kahneman and his late colleague Amos Tversky, as
described in Kahneman’s wonderful book, <i>Thinking, Fast and Slow.</i><span style="mso-spacerun: yes;"> </span>They describe two modes of thought, called
“System 1” (“fast thinking”) and “System 2”<span style="mso-spacerun: yes;">
</span>(“slow thinking”).<span style="mso-spacerun: yes;"> </span>System 1 is automatic,
instinctive, fast, parallel, and emotional; it enables jumping to conclusions quickly.<span style="mso-spacerun: yes;"> </span>In contrast, System 2 is deliberative,
conscious, slow, and logical; it involves careful and explicit reasoning.<span style="mso-spacerun: yes;"> </span>System 1 is optimized for common cases, and
therefore has biases that result in wrong conclusions in unusual situations.<span style="mso-spacerun: yes;"> </span>The book explores these biases by presenting
a series of problems, and asking the reader to respond immediately.<span style="mso-spacerun: yes;"> </span>In most cases, your responses will be wrong;
I know mine were.<span style="mso-spacerun: yes;"> </span>This is due to the
fact that these problems were carefully chosen to expose the various biases of
System 1 thinking.<span style="mso-spacerun: yes;"> </span>In contrast, System 2
thinking is more accurate, but requires considerably more effort.<span style="mso-spacerun: yes;"> </span>It is therefore impossible to use it for
every task, or we would be able to perform very little.<span style="mso-spacerun: yes;"> </span>Just imagine having to compute mathematically
the trajectories of all cars you see before being able to cross the street.<o:p></o:p></span></div>
<span style="font-family: inherit;">
</span><span style="font-family: inherit;">Cognition requires both types of thinking.<span style="mso-spacerun: yes;"> </span>For example, you would use fast thinking to
zero in on a small number of candidate solutions, then use slow thinking to
evaluate these solutions carefully, in order to consciously overcome System 1
biases.<span style="mso-spacerun: yes;"> </span>To complete the cycle, you can
use slow thinking to direct a new burst of fast thinking, leading to a new
evaluation step.<o:p></o:p></span><br />
<span style="font-family: inherit;">
</span><br />
<div class="MsoNormal" style="margin: 0cm 0cm 8pt;">
<span style="font-family: inherit;">The early days of AI were mostly concerned with the mechanization
of slow thinking, and resulted in knowledge-based systems (or “expert
systems”), planning systems such as <a href="https://en.wikipedia.org/wiki/STRIPS" target="_blank">STRIPS</a></span><span style="font-family: inherit;">,
and machine learning based on models (for example, explanation-based learning).<span style="mso-spacerun: yes;"> </span>Much of this work was based on the Knowledge
Representation Hypothesis, which states that:</span></div>
<div class="MsoQuote" style="margin: 10pt 43.1pt 8pt;">
<span style="color: #404040;"><span style="font-family: inherit;">Any mechanically embodied intelligent process will be
comprised of structural ingredients that (a) we as external observers naturally
take to represent a propositional account of the knowledge that the overall
process exhibits, and (b) independent of such external semantic attribution,
play a formal but causal and essential role in engendering the behavior that
manifests that knowledge.<o:p></o:p></span></span></div>
<span style="font-family: inherit;">
</span><span style="font-family: inherit;">According to this hypothesis, in order for us to assign
intelligence to a computer system, we need to be able to see how it represents
its knowledge explicitly, and how it uses that knowledge to perform tasks that
we would consider to be intelligent.<span style="mso-spacerun: yes;"> </span>It
isn’t sufficient for the task to require intelligence, since machines can use
other means (such as computation speed or access to large sources of data) to
perform the task without an explicit representation of knowledge.<o:p></o:p></span><br />
<span style="font-family: inherit;">
</span><br />
<div class="MsoNormal" style="margin: 0cm 0cm 8pt;">
<span style="font-family: inherit;">Knowledge-based technology, originally developed for AI, is
widely used today in various industries, such as insurance and finance, and
there are several successful commercial and open-source rule systems available
for building such applications.<span style="mso-spacerun: yes;"> </span>For most
AI tasks, unfortunately, knowledge-based systems did not scale well, and were
not very successful commercially.</span><br />
<br />
<span style="font-family: inherit;">This led to a backlash in AI research (sometimes called the
“AI winter”), the abandonment of the Knowledge Representation Hypothesis, and the
rise of statistical methods in AI.<span style="mso-spacerun: yes;"> </span>These
methods, including various forms of neural networks used to support large-scale
machine learning, were very successful in many applications such as the
deciphering handwriting and speech understanding, which had been very difficult
to automate previously.<span style="mso-spacerun: yes;"> </span>These methods
scale well with increasing computational power, and can solve larger and more
difficult problems as more resources become available.</span><br />
<br />
<span style="font-family: inherit;">This manifest success of System 1 methods in AI has
profoundly changed the field, its methods and goals.<span style="mso-spacerun: yes;"> </span>Instead of focusing on understanding, it is
now concerned with classification and information retrieval.<span style="mso-spacerun: yes;"> </span>These systems learn, but cannot in general
externalize what they learn, since it is encoded in a large set of numeric
weights in a neural network or similarly opaque representation.</span><br />
<br />
<span style="font-family: inherit;">The domain-specific focus of knowledge-based systems was
driven by the need to create domain knowledge manually, but the goal was to
create universal mechanisms for representing the knowledge, so that different
sources could eventually be used together in a single system.<span style="mso-spacerun: yes;"> </span>In contrast, statistical methods are now
being tuned for each problem separately.<span style="mso-spacerun: yes;">
</span>They can work together to the extent that they can be combined through
their end results, but they don’t share a common representation.<span style="mso-spacerun: yes;"> </span>For example, in this paradigm it is
impossible to combine one system that solves geometry problems with another
that solves algebraic problems to obtain a system that can solve problems that
require both geometrical and algebraic reasoning.<span style="mso-spacerun: yes;"> </span>Thus, each of these systems is an island; it
can perhaps be pushed further in a single direction, but is unlikely to work
with other systems to solve more complex problems (except by combining results
rather than mechanisms).</span><br />
<br />
<span style="font-family: inherit;">Pat Langley’s paper “The Cognitive Systems Paradigm” <i>(Advances
in Cognitive Systems 1, 2012)</i> analyzes this shift in the field of AI and
cognitive systems, and proposes six features that distinguish research on
fundamental issues of machine intelligence from more recent approaches, which
he characterizes as producing “impressive but narrow idiot savants.”<span style="mso-spacerun: yes;"> </span>I recommend this paper for anyone interested
in the original goals of AI and in getting it back on track.</span></div>
Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com1tag:blogger.com,1999:blog-5536017433265189318.post-69849378364249987882015-07-17T17:47:00.003+03:002015-10-21T13:10:59.126+03:00Programming by ThinkingIn my second post (<a href="http://the-dusty-deck.blogspot.co.il/2010/12/programmers-as-children.html" target="_blank">Programmers as Children)</a> I complained about the fact that programmers work with their fingers instead of using their brains. This is gradually getting worse instead of better, with growing academic research concentrating on the use of examples from the internet, search tools to find such examples for specific questions, and so on. Of course, there are many websites containing advice for various programming domains, and the examples they provide are often quite useful. However, copying these into your own code without understanding what they do, and what are the wider implications (for example, on performance and security), is a recipe for disaster.<br />
<br />
The <a href="http://cacm.acm.org/magazines/2015/4" target="_blank">April 2015 issue of <em>Communications of the ACM</em></a> contains several articles that should be required reading for every software developer. The first is Leslie Lamport's viewpoint article, "<a href="http://cacm.acm.org/magazines/2015/4/184705-who-builds-a-house-without-drawing-blueprints" target="_blank">Who Builds a House without Drawing Blueprints</a>." No engineering discipline proceeds to build anything without first analyzing the requirements, making initial designs and analyzing them from various points of view (such as cost, safety, standards, and legal implications) -- in other words, thinking deeply about the problem and possible solutions. But in the (arguably misnamed) discipline of software engineering, starting with coding is all too often the norm, and is even praised as a methodology. (I am not implying that any of the agile methodologies advocates that; quite the contrary! However, agile methods are often misunderstood as "don't think before you code.")<br />
<br />
Lamport argues that thinking is necessary before coding, and that writing specifications is an excellent way to focus your thinking. The specifications need not always be formal, although Lamport makes a good case for using formal specifications, and using tools to check them. Specifically, TLA+ is a formal specification language created and used by Lamport himself in various projects.<br />
<br />
You may be inclined to dismiss this as only academic, and, unfortunately, this is the too-prevalent view. However, you may learn otherwise if you read another article in the same issue, "<a href="http://cacm.acm.org/magazines/2015/4/184701-how-amazon-web-services-uses-formal-methods" target="_blank">How Amazon Web Services Uses Formal Methods</a>." This article describes how TLA+ was used in several critical Amazon projects, and discovered bugs that the authors admit they could not have found otherwise. In some cases, Amazon engineers used TLA+ successfully on their projects after two weeks of self-learning.<br />
<br />
Of course, getting the specifications right does not mean that the code will be correct as well. Tool support for verifying the code against its specification would be very helpful, and this is an area of active research. However, <em>not</em> getting the specifications right is almost a guarantee that the code will have bugs. This is particularly true for large concurrent systems, which are a source of extremely subtle bugs that programmers have great difficulties understanding and predicting.<br />
<br />
And while you have the April issue in your hands, I recommend you also read the article "<a href="http://cacm.acm.org/magazines/2015/4/184691-security-challenges-for-medical-devices" target="_blank">Security Challenges for Medical Devices</a>." It discusses safety, security, and privacy issues with various kinds of medical devices. Even hospital information systems have such issues, but they are most critical with implanted devices such as pacemakers. Modern implantable devices communicate wirelessly to provide information they collect, and sometimes they can even be programmed wirelessly. This creates health hazards from mistakes but also deliberate attacks. Even devices that only provide information are dangerous if this information is modified anywhere along the way from the device to the physician (including in IT systems that store or transmit this information), since this could lead to the wrong treatment being applied.<br />
<br />
Security cannot be added as an afterthought; it must be designed-in from the beginning. While not all systems have the same security implications as medical devices, the whole chain is as strong as the weakest link, which implies that security is crucial to more systems than would be immediately obvious. This helps drive home Lamport's point. Think before you code!<br />
<br />
<span style="font-size: x-small;">#formalmethods #specifications</span>Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com1tag:blogger.com,1999:blog-5536017433265189318.post-75456720185504033262015-01-11T18:06:00.000+02:002015-01-12T18:46:24.195+02:00Functional Programming in Mainstream Languages, Part 7: Higher-Order Functions in Haskell<blockquote class="tr_bq">
(Jump to <a href="http://the-dusty-deck.blogspot.com/2014/09/functional-programming-in-mainstream.html#toc">Table of Contents</a>)</blockquote>
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.<br />
<br />
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.<br />
<br />
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 <em>tuples</em>, as I will show below. But first, here is the curried version:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Scala
</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">def makeAdder = (x: Int) => (y: Int) => x + y
def increment = makeAdder(1)
def res = increment(4)
</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Haksell
</td></tr>
<tr><td style="font-family: monospace; white-space: pre;"><span style="color: blue;">makeAdder :: (Num a) => a -> a -> a
</span>makeAdder x y = x + y
<span style="color: blue;">increment :: (Num a) => a -> a
</span>increment = makeAdder 1
<span style="color: blue;">res :: Integer
</span>res = increment 4
</td></tr>
</tbody></table>
<br />
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 <span style="font-family: "Courier New", Courier, monospace;">makeAdder</span>, but it isn't necessary in this case.<br />
<br />
The <span style="font-family: "Courier New", Courier, monospace;">makeAdder</span> function in Haskell, unlike all the other examples we saw before, is exactly equivalent to the function <span style="font-family: "Courier New", Courier, monospace;">+</span>; both are curried and take one argument. Thus, the above code is equivalent to the following:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Haksell </td></tr>
<tr><td style="font-family: monospace; white-space: pre;"><span style="color: blue;">increment :: (Num a) => a -> a</span>
increment = (+) 1
<span style="color: blue;">res :: Integer</span>
res = increment 4</td></tr>
</tbody></table>
<br />
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.)<br />
<br />
Looking at the types, from the simplest (the last) to the most complicated (the first), we see that the type of res is simply <span style="font-family: "Courier New", Courier, monospace;">Integer</span>. However, if we give increment an argument of a different type, the result will be the corresponding type:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Haksell </td></tr>
<tr><td style="font-family: monospace; white-space: pre;"><span style="color: blue;">real :: Double</span>
real = increment 0.5</td></tr>
</tbody></table>
<br />
This is possible since the type of the <span style="font-family: "Courier New", Courier, monospace;">increment</span> function is parameterized. Before the double arrow (<span style="font-family: "Courier New", Courier, monospace;">=></span>) is a type constraint; we'll look at that in a minute. The type of <span style="font-family: Courier New;">increment</span> is <span style="font-family: "Courier New", Courier, monospace;">a -> a</span>, where <span style="font-family: "Courier New", Courier, monospace;">a</span> is a type parameter. This means that the function takes one argument of type <span style="font-family: "Courier New", Courier, monospace;">a</span>, and returns a result of the same type. However, the function applies the <span style="font-family: "Courier New", Courier, monospace;">+</span> operator to its argument (indirectly through <span style="font-family: "Courier New", Courier, monospace;">makeAdder</span>), and therefore the type <span style="font-family: "Courier New", Courier, monospace;">a</span> must be appropriate as an argument to <span style="font-family: "Courier New", Courier, monospace;">+</span>. This is the purpose of the type constraint <span style="font-family: "Courier New", Courier, monospace;">(Num a)</span>; it restricts <span style="font-family: "Courier New", Courier, monospace;">a</span> to be a <em>numeric type</em>, which (among other operations) supports <span style="font-family: "Courier New", Courier, monospace;">+</span>.<br />
<br />
Both <span style="font-family: "Courier New", Courier, monospace;">Integer</span> and <span style="font-family: "Courier New", Courier, monospace;">Double</span> are numeric types, so the type of <span style="font-family: "Courier New", Courier, monospace;">increment</span> includes both <span style="font-family: "Courier New", Courier, monospace;">Integer -> Integer</span> and <span style="font-family: "Courier New", Courier, monospace;">Double -> Double</span>. 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.<br />
<br />
The type of <span style="font-family: Courier New;">makeAdder</span> is more of the same: <span style="color: blue;"><span style="color: black; font-family: "Courier New", Courier, monospace;">a -> a -> a</span></span><span style="color: black;">
is the type of a function that takes a single argument of type <span style="font-family: Courier New;">a</span>, and returns a function of type <span style="font-family: Courier New;">a -> a</span>, that is, a function (like <span style="font-family: "Courier New", Courier, monospace;">increment</span>) that takes a single argument of type <span style="font-family: Courier New;">a</span> and returns a result of the same type. Again, this has the constraint that <span style="font-family: "Courier New", Courier, monospace;">a</span> must be a numeric type.</span><br />
<br />
As is usual in type theory, the <span style="font-family: "Courier New", Courier, monospace;">-></span> type constructor is right-associative, so that the type <span style="font-family: Courier New;">a -> a -> a</span> is the same as <span style="font-family: Courier New;">a -> (a -> a)</span>. 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.<br />
<br />
In contrast, function application binds to the left; for example, <span style="font-family: "Courier New", Courier, monospace;">makeAdder 1 4</span> is the same as <span style="font-family: Courier New;">(makeAdder 1) 4</span>, which is the same computation as our <span style="font-family: "Courier New", Courier, monospace;">increment 4</span> 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.<br />
<br />
If you really want the uncurried version of <span style="font-family: "Courier New", Courier, monospace;">makeAdder</span>, 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: <span style="font-family: "Courier New", Courier, monospace;">(1, 4)</span>. Here is the uncurried version, which can simply be called <span style="font-family: "Courier New", Courier, monospace;">add</span>:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Haksell </td></tr>
<tr><td style="font-family: monospace; white-space: pre;"><span style="color: blue;">add :: (Num a) => (a, a) -> a</span>
<span style="color: black;">add (x, y) = x + y</span></td></tr>
</tbody></table>
<br />
As you can see, the type now represents a function that takes a tuple containing two elements of type <span style="font-family: "Courier New", Courier, monospace;">a</span>, and returns a result of type <span style="font-family: "Courier New", Courier, monospace;">a</span>. A very useful feature of Haskell, common to many other functional languages (and some languages with a strong functional subset, like Scala), is <em>pattern matching</em>. 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 <span style="font-family: "Courier New", Courier, monospace;">add</span> is a constructor for a tuple containing two values, <span style="font-family: "Courier New", Courier, monospace;">x</span> and <span style="font-family: "Courier New", Courier, monospace;">y</span>, and has the parenthesized form <span style="font-family: "Courier New", Courier, monospace;">(x, y)</span>. This means that the function can only accept tuples of this form, and when it does, the first element will be called <span style="font-family: "Courier New", Courier, monospace;">x</span> and the second will be called <span style="font-family: "Courier New", Courier, monospace;">y</span>. 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.<br />
<br />
Having gone through the preliminaries, here is the fixed-point function:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Scala</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">def fixedpoint(f: Double => Double, v: Double): Double = {
val next = f(v)
if (Math.abs(next - v) < epsilon)
next
else
fixedpoint(f, next)
}
</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Haskell</td></tr>
<tr><td style="font-family: monospace; white-space: pre;"><span style="color: blue;">fixedpoint :: (Ord a, Fractional a) => (a -> a) -> a -> a</span>
fixedpoint f guess =
let next = f guess in
if abs(guess - next) < epsilon
then next
else fixedpoint f next</td></tr>
</tbody></table>
<br />
The <span style="font-family: "Courier New", Courier, monospace;">let</span> syntax binds one or more variables in the context of an expression (which follows the keyword <span style="font-family: "Courier New", Courier, monospace;">in</span>). As in Scala, <span style="font-family: "Courier New", Courier, monospace;">if</span> in Haskell is an expression that returns one of two values depending on the condition. The parenthesis on the argument to the <span style="font-family: "Courier New", Courier, monospace;">abs</span> function are required; without them, the expression would be parsed as <span style="font-family: "Courier New", Courier, monospace;">(abs guess) - next</span>.<br />
<br />
The type of <span style="font-family: "Courier New", Courier, monospace;">fixedpoint</span> is <span style="font-family: "Courier New", Courier, monospace;">(a -> a) -> a -> a</span>, using only the required parentheses; this could equivalently be written as <span style="font-family: Courier New;">(a -> a) -> (a -> a)</span>, which makes it clearer that <span style="font-family: "Courier New", Courier, monospace;">fixedpoint</span> takes a function from <span style="font-family: "Courier New", Courier, monospace;">a</span> to <span style="font-family: "Courier New", Courier, monospace;">a</span> and returns another such function. The type <span style="font-family: "Courier New", Courier, monospace;">a</span> is constrained to be ordered (because of the use of <span style="font-family: "Courier New", Courier, monospace;"><</span>), as well as fractional (because it is compared with <span style="font-family: "Courier New", Courier, monospace;">epsilon</span>, which is a <span style="font-family: "Courier New", Courier, monospace;">Double</span>).<br />
<br />
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.<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Haskell</td></tr>
<tr><td style="font-family: monospace; white-space: pre;"><span style="color: blue;">fixedpoint :: (Ord a, Fractional a) => (a -> a) -> a -> a</span>
fixedpoint f guess =
<span style="color: black;"> let closeEnough v1 v2 = abs(v1 - v2) < epsilon</span>
<span style="color: black;"> try guess =</span>
<span style="color: black;"> let next = f guess in</span>
<span style="color: black;"> if closeEnough guess next</span>
<span style="color: black;"> then next</span>
<span style="color: black;"> else try next</span>
<span style="color: black;"> in try guess0</span></td></tr>
</tbody></table>
<br />
Here, the decision of whether the guess is close enough to the desired value is abstracted into the function <span style="font-family: "Courier New", Courier, monospace;">closeEnough</span>, and the recursion is encapsulated into the function <span style="font-family: "Courier New", Courier, monospace;">try</span>. As usual, the internal functions have access to enclosing scopes, so they can refer to <span style="font-family: "Courier New", Courier, monospace;">f</span> and <span style="font-family: "Courier New", Courier, monospace;">epsilon</span>.<br />
<br />
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 <span style="font-family: "Courier New", Courier, monospace;">sqrt</span>:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Scala</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">def sqrt(x: Double) =
fixedpoint(y => x / y, 1.0)
</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Haskell</td></tr>
<tr><td style="font-family: monospace; white-space: pre;"><span style="color: blue;">sqrt :: Double -> Double
</span><span style="color: black;">sqrt x = fixedpoint (\y -> x / y) 1.0
</span></td></tr>
</tbody></table>
<br />
The terminating version is of course very similar:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Scala</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">def sqrt(x: Double) =
fixedpoint(y => (y + x / y) / 2.0, 1.0)</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Haskell</td></tr>
<tr><td style="font-family: monospace; white-space: pre;"><span style="color: blue;">sqrt :: Double -> Double</span>
<span style="color: black;">sqrt x = fixedpoint (\y -> (y + x / y) / 2.0) 1.0</span></td></tr>
</tbody></table>
<br />
The generalization of the average-damp procedure and its use should hold no surprises now:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Scala</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">def averageDamp(f: Double => Double) =
(x: Double) => (x + f(x)) / 2.0
def sqrt(x: Double) =
fixedpoint(averageDamp(y => x / y), 1.0)</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Haskell</td></tr>
<tr><td style="font-family: monospace; white-space: pre;"><span style="color: blue;">averageDamp :: Fractional a => (a -> a) -> a -> a
</span>averageDamp f x = (x + f x) / 2.0<br />
<span style="color: blue;">sqrt :: Double -> Double
</span>sqrt x = fixedpoint (averageDamp (\y -> x / y)) 1.0</td></tr>
</tbody></table>
<br />
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.<br />
<br />
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.
<span style="font-size: x-small;">#functionalprogramming #haskell</span>Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com0tag:blogger.com,1999:blog-5536017433265189318.post-84033316784095073062014-12-09T22:35:00.000+02:002015-01-12T18:45:57.586+02:00Functional Programming in Mainstream Languages, Part 6: Higher-Order Functions in Xtend<blockquote class="tr_bq">
(Jump to <a href="http://the-dusty-deck.blogspot.com/2014/09/functional-programming-in-mainstream.html#toc">Table of Contents</a>)</blockquote>
I introduced the Xtend programming language in a <a href="http://the-dusty-deck.blogspot.co.il/2014/06/xtend-gentle-and-functional-java.html" target="_blank">previous post</a>. 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.<br />
<br />
Here is the simple example of the curried addition function:<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">IntFunction<intunaryoperator> makeAdder = x -> y -> x + y;
IntUnaryOperator increment = makeAdder.apply(1);
int res = increment.applyAsInt(4);</intunaryoperator></td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Xtend</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">val makeAdder = [int x|[int y|x + y]]
val increment = makeAdder.apply(1)
val res = increment.apply(4)
</td></tr>
</tbody></table>
<br />
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.<br />
<br />
The recursive fixed-point function looks like this:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">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);
}</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Xtend</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">def double fixedpoint(Function1<Double, Double> f, double v) {
val next = f.apply(v)
if ((next - v).abs < epsilon)
next
else
fixedpoint(f, next)
}
</td></tr>
</tbody></table>
<br />
This uses the Xtend interface for unary functions, <span style="font-family: "Courier New", Courier, monospace;">Function1</span>, with the Java wrapper type <span style="font-family: "Courier New", Courier, monospace;">Double</span>. In principle, the compiler could have inferred the return type of this function (Scala can do it, see <a href="http://the-dusty-deck.blogspot.com/2014/12/functional-programming-in-mainstream.html" target="_blank">Part 5</a>), 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.<br />
<br />
In this example we can see a nice extension feature, one of those that gave Xtend its name. Doubles in Java has no <span style="font-family: "Courier New", Courier, monospace;">abs</span> method; instead, you call the static method <span style="font-family: "Courier New", Courier, monospace;">Math.abs</span> 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; <span style="font-family: "Courier New", Courier, monospace;">Arrays</span> and <span style="font-family: "Courier New", Courier, monospace;">Collections</span> 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 <span style="font-family: "Courier New", Courier, monospace;">x</span> the following are completely equivalent: <span style="font-family: "Courier New", Courier, monospace;">Math.abs(x)</span>, and <span style="font-family: "Courier New", Courier, monospace;">x.abs</span>. This equivalence (like many others) is defined in the standard Xtend libraries.<br />
<br />
Because this recursive version of <span style="font-family: "Courier New", Courier, monospace;">fixedpoint</span> 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:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">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;
}</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Xtend</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">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
}
</td></tr>
</tbody></table>
<br />
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 <span style="font-family: "Courier New", Courier, monospace;">val</span>, whereas modifiable variables (non-final) are introduced by the keyword <span style="font-family: "Courier New", Courier, monospace;">var</span>. 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 <span style="font-family: "Courier New", Courier, monospace;">val</span> rather than <span style="font-family: "Courier New", Courier, monospace;">var</span>, 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!<br />
<br />
At this point you know to expect the non-terminating <span style="font-family: "Courier New", Courier, monospace;">sqrt</span>; here it is:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">public double sqrt(double x) {
return fixedpoint(y -> x / y, 1.0);
}</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Xtend</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">def sqrt(double x) {
fixedpoint([y|x / y], 1.0)
}
</td></tr>
</tbody></table>
<br />
The differences are minor: less type information is required in Xtend, and, like Scala, Xtend doesn't require the access-level designator (<span style="font-family: "Courier New", Courier, monospace;">public</span>) and the <span style="font-family: "Courier New", Courier, monospace;">return</span> keyword; however, the braces are still required.<br />
<br />
By now you can surely write the terminating version yourselves:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">public double sqrt(double x) {
return fixedpoint(y -> (y + x / y) / 2.0, 1.0);
}</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Xtend</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">def sqrt(double x) {
fixedpoint([y|(y + x / y) / 2.0], 1.0)
}
</td></tr>
</tbody></table>
<br />
The general average-damp and the corresponding <span style="font-family: "Courier New", Courier, monospace;">sqrt</span> again hold no surprises:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">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);
}</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Xtend</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">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)
}
</td></tr>
</tbody></table>
<br />
As I said <a href="http://the-dusty-deck.blogspot.co.il/2014/06/xtend-gentle-and-functional-java.html" target="_blank">before</a>, 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 (<span style="font-family: "Courier New", Courier, monospace;">apply</span>, <span style="font-family: "Courier New", Courier, monospace;">applyAsDouble</span>, <span style="font-family: "Courier New", Courier, monospace;">test</span>, etc.). As we saw in <a href="http://the-dusty-deck.blogspot.co.il/2014/12/functional-programming-in-mainstream.html" target="_blank">Part 5</a>, 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).<br />
<br />
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.<br />
<br />
<span style="font-size: x-small;">#FunctionalProgramming #Xtend</span>Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com0tag:blogger.com,1999:blog-5536017433265189318.post-82180063494352497592014-12-07T18:36:00.000+02:002015-01-12T18:45:45.584+02:00Functional Programming in Mainstream Languages, Part 5: Higher-Order Functions in Scala<blockquote class="tr_bq">
(Jump to <a href="http://the-dusty-deck.blogspot.com/2014/09/functional-programming-in-mainstream.html#toc">Table of Contents</a>)</blockquote>
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.<br />
<br />
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.<br />
<br />
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.<br />
<br />
Here is the simple example of the curried addition function:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8
</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">IntFunction<IntUnaryOperator> makeAdder = x -> y -> x + y;
IntUnaryOperator increment = makeAdder.apply(1);
int res = increment.applyAsInt(4);</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Scala
</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">def makeAdder = (x: Int) => (y: Int) => x + y
def increment = makeAdder(1)
def res = increment(4)
</td></tr>
</tbody></table>
<br />
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 <span style="font-family: "Courier New", Courier, monospace;">add</span> function: <span style="font-size: small;"><span style="font-family: "Courier New", Courier, monospace;">Int => (Int => Int)</span>. We could specify this type manually, but don't need to.</span><br />
<br />
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.<br />
<br />
Here is the recursive fixed-point function:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">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);
}</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Scala</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">def fixedpoint(f: Double => Double, v: Double): Double = {
val next = f(v)
if (Math.abs(next - v) < epsilon)
next
else
fixedpoint(f, next)
}
</td></tr>
</tbody></table>
<br />
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.<br />
<br />
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 <span style="font-family: "Courier New", Courier, monospace;">@tailrec</span> 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:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8
</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">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;
}</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Scala</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">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
}
</td></tr>
</tbody></table>
<br />
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.<br />
<br />
Now for the naive non-terminating version of <span style="font-family: "Courier New", Courier, monospace;">sqrt</span> that uses
<span style="font-family: "Courier New", Courier, monospace;">fixedpoint</span>:<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">public double sqrt(double x) {
return fixedpoint(y -> x / y, 1.0);
}</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Scala</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">def sqrt(x: Double) =
fixedpoint(y => x / y, 1.0)
</td></tr>
</tbody></table>
<br />
The differences are small, and have to do with Java's verbosity more than anything else. Gone are the access-level designator (<span style="font-family: "Courier New", Courier, monospace;">public</span>), the return type, the <span style="font-family: "Courier New", Courier, monospace;">return</span> 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.<br />
<br />
The terminating version of sqrt that uses average damping should now come as no surprise:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">public double sqrt(double x) {
return fixedpoint(y -> (y + x / y) / 2.0, 1.0);
}</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Scala</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">def sqrt(x: Double) =
fixedpoint(y => (y + x / y) / 2.0, 1.0)
</td></tr>
</tbody></table>
<br />
Here is the general average-damp procedure and the version of <span style="font-family: "Courier New", Courier, monospace;">sqrt</span> that uses it:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">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);
}</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Scala</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">def averageDamp(f: Double => Double) =
(x: Double) => (x + f(x)) / 2.0
def sqrt(x: Double) =
fixedpoint(averageDamp(y => x / y), 1.0)
</td></tr>
</tbody></table>
<br />
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.<br />
<br />
<span style="font-size: xx-small;">#functionalprogramming #scala</span>Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com0tag:blogger.com,1999:blog-5536017433265189318.post-63423284936581415072014-11-28T13:07:00.000+02:002015-01-12T18:45:31.231+02:00Functional Programming in Mainstream Languages, Part 4: Higher-Order Functions in JavaScript<blockquote class="tr_bq">
(Jump to <a href="http://the-dusty-deck.blogspot.com/2014/09/functional-programming-in-mainstream.html#toc">Table of Contents</a>)</blockquote>
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 <a href="http://www.amazon.com/gp/product/0596517742/ref=as_li_tl?ie=UTF8&camp=1789&creative=9325&creativeASIN=0596517742&linkCode=as2&tag=thdude04-20&linkId=VCTKPMVJI6Z2SSBB">JavaScript: The Good Parts</a><img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=thdude04-20&l=as2&o=1&a=0596517742" height="1" style="border: none !important; margin: 0px !important;" width="1" /> for more details.)<br />
<br />
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 <a href="http://learning.acm.org/webinar/" target="_blank">ACM webinar</a> titled "August 2014: Async JavaScript at Netflix."<br />
<br />
In this part of the series, I will show the examples of higher-order functions from <a href="http://the-dusty-deck.blogspot.com/2014/11/functional-programming-in-mainstream_27.html" target="_blank">Part 3</a> in JavaScript, and contrast it with the Java 8 implementation. For the Scheme and Java 7 versions, see <a href="http://the-dusty-deck.blogspot.com/2014/11/functional-programming-in-mainstream_27.html" target="_blank">Part 3</a>. First, however, is the simple example from <a href="http://the-dusty-deck.blogspot.com/2014/11/functional-programming-in-mainstream.html" target="_blank">Part 2</a>:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8 </td></tr>
<tr><td style="font-family: monospace; white-space: pre;">IntFunction<IntUnaryOperator> makeAdder = x -> y -> x + y;
IntUnaryOperator increment = makeAdder.apply(1);
int res = increment.applyAsInt(4);</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">JavaScript</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">var makeAdder = function(x) {
return function(y) {
return x + y;
}
}
var increment = makeAdder(1);
var res = increment(4);</td></tr>
</tbody></table>
<br />
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.<br />
<br />
<a href="http://www.ecmascript.org/" target="_blank">Ecma International</a> 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:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">ECMAScript Harmony (still in draft status)</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">var makeAdder = x => y => x + y;
var increment = makeAdder(1);
var res = increment(4);</td></tr>
</tbody></table>
<br />
This is very similar to Java 8, except for the use of the <span style="font-family: "Courier New", Courier, monospace;">=></span> symbol instead of <span style="font-family: "Courier New", Courier, monospace;">-></span>. 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 <a href="http://people.mozilla.org/~jorendorff/es6-draft.html" target="_blank">the proposed draft</a> for further details.<br />
<br />
Here is the recursive fixed-point function:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">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);
}</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">JavaScript</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">function fixedpoint(f, v) {
var next = f(v);
if (Math.abs(next - v) < epsilon)
return next
else
return fixedpoint(f, next);
}</td></tr>
</tbody></table>
<br />
These are very similar, except for the lack of types in JavaScript. Here is the imperative version of <span style="font-family: "Courier New", Courier, monospace;">fixedpoint</span>. 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.<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">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;
}</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">JavaScript</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">function fixedpoint(f, v) {
var next = v;
var prev = v;
do {
prev = next;
next = f(next)
} while (Math.abs(next - prev) >= epsilon);
return next;
}</td></tr>
</tbody></table>
<br />
Next is the naive non-terminating version of <span style="font-family: "Courier New", Courier, monospace;">sqrt</span> that uses <span style="font-family: "Courier New", Courier, monospace;">fixedpoint</span>:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">public double sqrt(double x) {
return fixedpoint(y -> x / y, 1.0);
}</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">JavaScript</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">function sqrt(x) {
fixedpoint(function(y) {
return x / y;
}, 1);
}</td></tr>
</tbody></table>
<br />
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.<br />
<br />
The terminating version of sqrt that uses average damping implicitly looks like this:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">public double sqrt(double x) {
return fixedpoint(y -> (y + x / y) / 2.0, 1.0);
}</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">JavaScript</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">function sqrt(x) {
fixedpoint(function(y) {
return (y + x / y) / 2;
}, 1);
}</td></tr>
</tbody></table>
<br />
Finally, here is the average-damp operator and the implementation of <span style="font-family: "Courier New", Courier, monospace;">sqrt</span> that uses it explicitly:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">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);
}</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">JavaScript</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">function averageDamp(f) {
return function(x) {
return (x + f(x)) / 2;
}
}
function sqrt(x) {
return fixedpoint(averageDamp(function(y) {
return x / y;
}), 1);
}</td></tr>
</tbody></table>
<br />
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 <a href="http://www.typescriptlang.org/" target="_blank">TypeScript</a>, which supports gradual typing (see <a href="http://the-dusty-deck.blogspot.com/2014/08/review-how-programming-languages-will.html" target="_blank">my review in a previous post</a>) 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.<br />
<br />
Coming up in this series: Scala, Xtend, and Haskell!<br />
<br />
<span style="font-size: x-small;">#functionalprogramming #javascript</span>Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com1tag:blogger.com,1999:blog-5536017433265189318.post-48178369653525456802014-11-27T21:49:00.001+02:002015-01-12T18:44:52.964+02:00Functional Programming in Mainstream Languages, Part 3: Higher-Order Functions in Java 7 and 8<blockquote class="tr_bq">
(Jump to <a href="http://the-dusty-deck.blogspot.com/2014/09/functional-programming-in-mainstream.html#toc">Table of Contents</a>)</blockquote>
Having seen (in the <a href="http://the-dusty-deck.blogspot.com/2014/11/functional-programming-in-mainstream.html" target="_blank">part 2 of this series</a>) the basic syntax for expressing functions in Java 8, we will now explore some functional-programming techniques and compare how they are expressed in Scheme, Java 7, and Java 8. The examples are adapted from the book <a href="http://www.amazon.com/gp/product/0262510871/ref=as_li_tl?ie=UTF8&camp=1789&creative=9325&creativeASIN=0262510871&linkCode=as2&tag=thdude04-20&linkId=NANXAQG57OETLKYF">Structure and Interpretation of Computer Programs (2nd Edition)</a><img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=thdude04-20&l=as2&o=1&a=0262510871" height="1" style="border: currentColor !important; margin: 0px !important;" width="1" />
by Abelson and Sussman.<br />
<br />
The following function attempts to compute an approximation to a <em>fixed point</em> of a given function <em>f</em>; that is, a value <em>x</em> such that <em>x</em> = <em>f</em>(<em>x</em>). The computation starts from an initial guess <em>c</em>, and repeatedly applies the function <em>f</em> to it, to get the series <em>f</em>(<em>c</em>), <em>f</em>(<em>f</em>(<em>c</em>)), <em>f</em>(<em>f</em>(<em>f</em>(<em>c</em>))), .... If this process converges, the result is close to a fixed point, since convergence means that applying <em>f</em> one more time returns (almost) the same value. However, the process may not converge at all, either because <em>f</em> has no fixed points at all, or because the process oscillates without finding a fixed point.<br />
<br />
Here are the implementations of this function in the three languages:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Scheme</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">(define (fixed-point f first-guess)
(define (try guess)
(let ((next (f guess)))
(if (< (abs (- guess next)) epsilon)
next
(try next))))
(try first-guess))</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 7</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">public double fixedpoint(UFunc<Double, Double> f, double v) {
double next = f.apply(v);
if (Math.abs(next - v) < epsilon)
return next;
else
return fixedpoint1(f, next);
}</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">public double fixedpoint(DoubleUnaryOperator f, double v) {
double next = f.applyAsDouble(v);
if (Math.abs(next - v) < epsilon)
return next;
else
return fixedpoint1(f, next);
}</td></tr>
</tbody></table>
<br />
Functional implementations usually use recursion instead of loops; the Scheme implementation defines an internal recursive function <span style="font-family: "Courier New", Courier, monospace;">try</span>, which computes the next value in the series and checks whether it is already close enough to the previous one to consider the series to have converged. If so, it returns the last value in the series; if not, it continues recursively to try the next value.<br />
<br />
The two Java implementations are quite similar, except for the types. For the Java 7 implementation, I created the following interface to represent unary functions from a domain <span style="font-family: "Courier New", Courier, monospace;">D</span> to a range <span style="font-family: "Courier New", Courier, monospace;">R</span>:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 7
</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">public interface UFunc<D, R> {
R apply(D arg1);
}</td></tr>
</tbody></table>
<br />
As I explained in the <a href="http://the-dusty-deck.blogspot.co.il/2014/11/functional-programming-in-mainstream.html" target="_blank">previous post</a>, Java 8 supplies a large set of interfaces to describe functions; <span style="font-family: "Courier New", Courier, monospace;">DoubleUnaryOperator</span> is the type of functions that take a double and return a double.<br />
<br />
There is a fundmemtal difference between functional languages (including Scheme) and most other languages, including Java. In the former, tail-recursive calls are converted by the compiler into jumps that don't add a frame to the execution stack. This means that such calls behave like loops in terms of their memory consumption. (For more details see <a href="http://www.amazon.com/gp/product/0262510871/ref=as_li_tl?ie=UTF8&camp=1789&creative=9325&creativeASIN=0262510871&linkCode=as2&tag=thdude04-20&linkId=NANXAQG57OETLKYF">Abelson and Sussman</a><img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=thdude04-20&l=as2&o=1&a=0262510871" height="1" style="border: currentColor !important; margin: 0px !important;" width="0" />.) However, the latter languages don't guarantee this property. As a result, the Java implementations above may use stack space proportional to the number of applications of the function required for convergence.<br />
<br />
A more natural style for implementing these methods in Java is imperative rather than functional:
<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 7</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">public double fixedpoint(UFunc<Double, Double> f, double v) {
double prev = v;
double next = v;
do {
prev = next;
next = f.apply(next);
} while (Math.abs(next - prev) >= epsilon);
return next;
}</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">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;
}</td></tr>
</tbody></table>
<br />
While functional-programming purists frown at this style, which modifies the values of the variables <span style="font-family: "Courier New", Courier, monospace;">prev</span> and <span style="font-family: "Courier New", Courier, monospace;">next</span>, this style is more natural for Java, and uses constant space on the stack. For those reasons, I find it acceptable when using functional techniques in Java, provided that the changes are confined to local variables (rather than fields), and, in particular, locals that aren't referenced in any other method (such as those in inner classes) or function.<br />
<br />
We can now try to use the fixedpoint function to compute square roots, using the fact that <em>y</em> is a square root of <em>x</em> if <em>y</em> = <em>x/y</em>; in other words, if <em>y</em> is a fixed point of the function λ<em>y</em>.<em>x</em>/<em>y</em>:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Scheme</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">(define (sqrt x)
(fixed-point (lambda (y) (/ x y)) 1.0))</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 7</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">public double sqrt(final double x) {
return fixedpoint(new UFunc<Double, Double>() {
@Override
public Double apply(Double y) {
return x / y;
}
}, 1.0);
}</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">public double sqrt(double x) {
return fixedpoint(y -> x / y, 1.0);
}
</td></tr>
</tbody></table>
<br />
Here we need to create an anonymous function ("lambda"), and here the difference between Java 7 and Java 8 becomes very clear. In Java 7 we need to create the function as an anonymous inner class, with all the necessary boilerplate code, which obscures the essentials of what we are trying to do. (For example, it is quite difficult to figure out that <span style="font-family: "Courier New", Courier, monospace;">1.0</span> is the second parameter to the <span style="font-family: "Courier New", Courier, monospace;">fixedpoint</span> method.) In contrast, in Java 8 we can just use the new lambda notation, and the meaning is immediately clear.<br />
<br />
In both versions of Java, it is only possible to refer in inner methods to variables defined in enclosing constants if these variables are final; that is, if they can't be modified. In Java 8 the variables doesn't need to be declared final, but it needs to be "effectively final," which means that it is never changed. (It is as though the compiler added the final modifier itself; this is similar to the type inference done by the Java 8 compiler.)<br />
<br />
The reason for this restriction is that local variables have a lifetime (sometimes called "extent") that coincides with the lifetime of the method in which they are defined. In other words, when the method returns, these variables are no longer accessible. This is done so that the variables can be allocated on the stack rather than on the heap, avoiding the need for garbage-collecting them. However, an object containing an inner method that refers to these variables may be used after the method that generated the object has already returned. If (and only if) the variables are final is it possible to copy their values to the new object so that references to their values are still valid. This is a poor-man's version of a <em>closure</em>, which is an object containing a function pointer together with all accessible variables in outer scopes. As we will see in a later post, Scheme (like other dialects of Lisp) supports full closures, which also allow changing bound variables.<br />
<br />
Unfortunately, the method above doesn't work in any language. The problem is that the computational process oscillates between two values and doesn't converge (try it for <em>x</em>=2). One value is too high, and the other is too low. However, if we take their average, the process converges; the following implementations all compute the square root:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Scheme
</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">(define (sqrt x)
(fixed-point (lambda (y) (/ (+ y (/ x y)) 2.0) 1.0))</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 7</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">public double sqrt(final double x) {
return fixedpoint(new UFunc<Double, Double>() {
@Override
public Double apply(Double y) {
return (y + x / y) / 2.0;
}
}, 1.0);
}</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">public double sqrt(double x) {
return fixedpoint(y -> (y + x / y) / 2.0, 1.0);
}</td></tr>
</tbody></table>
<br />
It turns out that this is a general technique, called <em>average damping</em>. It takes any function <em>f </em>and returns the function λ<em>x</em>.(<em>x</em>+<em>f</em>(<em>x</em>))/2; this function has exactly the same fixed points as <em>f</em>. In certain cases, however, the computational process of the fixed-point function converges with the new function when it diverges on the original function. This technique is easily specified as a program:<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Scheme
</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">(define (sqrt x)(define (average-damp f)
(lambda (x) (average x (f x))))
</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 7</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">public UFunc<Double, Double> averageDamp(final UFunc<Double, Double> f) {
return new UFunc<Double, Double>() {
@Override
public Double apply(Double x) {
return (x + f.apply(x)) / 2.0;
}
};
}</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">public DoubleUnaryOperator averageDamp(DoubleUnaryOperator f) {
return x -> (x + f.applyAsDouble(x)) / 2.0;
}</td></tr>
</tbody></table>
Again, the Java 7 version is obscured by the boilerplate code (not to mention the annoying repetitions of the template type). Here is the definition of <span style="font-family: "Courier New", Courier, monospace;">sqrt</span> that uses average damping (this time I will spare you the agony of the Java 7 version):<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Scheme</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">(define (sqrt x)
(fixed-point (average-damp (lambda (y) (/ x y))) 1.0))</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">public double sqrt(double x) {
return fixedpoint(averageDamp(y -> x / y), 1.0);
}</td></tr>
</tbody></table>
<br />
Computationally, this is exactly the same as the previous version, except that we use the original function λ<em>y</em>.<em>x</em>/<em>y</em> after applying the average damp operator to it.<br />
<br />
In summary, it is possible to use functional abstraction in Java 7, but it is very painful. The one case where it is widely used (although not usually thought of as such) is the case of callback functions, which are encapsulated as methods in one-method classes. Java 8 makes higher-order functions much easier to use, even though the cumbersome type system is still annoying and gets in the way.<br />
<br />
In subsequent posts we will see how to express the same ideas in other languages.<br />
<br />
<span style="font-size: x-small;">#functionalprogramming #java</span>Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com0tag:blogger.com,1999:blog-5536017433265189318.post-2120426040261110562014-11-27T11:13:00.001+02:002015-01-12T18:44:26.151+02:00Functional Programming in Mainstream Languages, Part 2: Introduction to Higher-Order Functions in Java 8<blockquote class="tr_bq">
(Jump to <a href="http://the-dusty-deck.blogspot.com/2014/09/functional-programming-in-mainstream.html#toc">Table of Contents</a>)</blockquote>
If immutability is the primary principle of functional programming, higher-order functions are its most important technique. Higher-order functions, also called <em>lambas,</em> are now part of many mainstream languages. In particular, they have been added to Java 8. In this post I will show how higher-order functions can be expressed in Java 8.<br />
<br />
I can't explain the details of the theory and techniques here; I highly recommend the wonderful book <a href="http://www.amazon.com/gp/product/0262510871/ref=as_li_tl?ie=UTF8&camp=1789&creative=9325&creativeASIN=0262510871&linkCode=as2&tag=thdude04-20&linkId=NANXAQG57OETLKYF">Structure and Interpretation of Computer Programs (2nd Edition)</a><img alt="" border="0" src="http://ir-na.amazon-adsystem.com/e/ir?t=thdude04-20&l=as2&o=1&a=0262510871" height="1" style="border: currentColor !important; margin: 0px !important;" width="1" />
by Abelson and Sussman. Most of the examples in this series of posts are taken from that book.<br />
<br />
In functional programming, functions are <em>first-class objects.</em> This means that functions can be passed as parameters to other functions, they can be returned from functions, they can be stored in data structures; in other words, anything you can do with any other object in the language, such as numbers or strings, you can do with functions.<br />
<br />
Some languages fake it: for example, in C you can pass around function pointers, but not function objects. The major difference is that function objects contain not only the code the function executes, but also its <em>environment</em>, meaning all bound variables known to the function. This is particularly important (and powerful) when functions are nested inside other functions (or methods, or any other binding scope).<br />
<br />
The inventors of <a href="http://en.wikipedia.org/wiki/Lisp_(programming_language)" target="_blank">LISP</a> struggled with the correct semantics of first-class functions; they called this the "<a href="http://en.wikipedia.org/wiki/Funarg_problem" target="_blank">funarg problem</a>." It turns out that the power of functional programming requires <em>lexical scope,</em> which means that variable names must be resolved with respect to the nesting of functions in the code, rather than to the structure of the calling stack at runtime. And in order for that to work correctly, it is impossible to allocate function parameters and other local variables on the program stack if those may be referred to in an internal function that is returned from the call. This complicates the compiler, but is invisible to programmers using the language.<br />
<br />
As a simple example, consider a function <span style="font-family: "Courier New", Courier, monospace;">make-adder</span> that accepts a single number, and returns a function that adds that number to its own argument. For example, if <span style="font-family: Courier New;">make-adder</span> is called with the value 1, it will return a function that can be called <span style="font-family: "Courier New", Courier, monospace;">increment</span>, since it adds one to whatever argument it is given. Here is how to write this function in Scheme and in Java 8.<br />
<br />
<table><tbody>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Scheme
</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">(define make-adder (lambda (x) (lambda (y) (+ x y)))
(define increment (make-adder 1))
(increment 4)
</td></tr>
<tr><td style="background-color: gold; color: darkblue; font-size: larger; font-weight: bold; padding: 0px;">Java 8
</td></tr>
<tr><td style="font-family: monospace; white-space: pre;">IntFunction<IntUnaryOperator> makeAdder = x -> y -> x + y;
IntUnaryOperator increment = makeAdder.apply(1);
int res = increment.applyAsInt(4);</td></tr>
</tbody></table>
<br />
The result of the last expression (in either language) is 5.<br />
<br />
The syntax is quite different, but the effect is the same. Let's look at the functions first. The Scheme syntax is a direct translation of the syntax used in the <a href="http://en.wikipedia.org/wiki/Lambda_calculus" target="_blank">Lambda Calculus</a>, which was invented by the great logician <a href="http://en.wikipedia.org/wiki/Lambda_calculus" target="_blank">Alonzo Church</a>, and which forms the theoretical basis for functional programming (in addition to its major importance in the theory of computer science). In the lambda calculus, the <span style="font-family: "Courier New", Courier, monospace;">make-adder</span> function would be written like this: λ<em>x</em>.λ<em>y</em>.<em>x</em>+<em>y</em>.<br />
<br />
This syntax describes a function of one argument whose name is <em>x</em>; this is indicated by the notation "λ<em>x</em>.". What follows the dot is the value of the function for a given value of <em>x</em>; in this case, this is another function, whose argument is called <em>y</em>. The value returned by this function is the sum of <em>x</em> and <em>y</em>.<br />
<br />
In Scheme, a function is denoted by the syntax <span style="font-family: "Courier New", Courier, monospace;">(lambda (v1 v2 ...) body)</span>, where <span style="font-family: "Courier New", Courier, monospace;">v1</span> <span style="font-family: "Courier New", Courier, monospace;">v2</span> ... are the parameter names, and <span style="font-family: "Courier New", Courier, monospace;">body</span> is an expression representing the value that the function returns.<br />
<br />
In Java 8, function syntax has the names of the parameters before the arrow (<span style="font-family: "Courier New", Courier, monospace;">-></span>), and the body follows the arrow. It is possible to specify more than one argument, in which case the arguments need to be put in a parenthesized list. It is also possible to specify the types of the arguments, but fortunately the designers of Java have finally realized what a burden repetitive types are on programs, and Java 7 introduced type inference into the compiler in order to eliminated some (but not enough) of this repetition. Java 8 extends this mechanism also to lambdas. In this case, the compiler can infer the types of the arguments from the type declared for the function <span style="font-family: "Courier New", Courier, monospace;">makeAdder</span>. This type needs some explanation.<br />
<br />
Java 8 has a new set of interfaces to describe various types of functions. For example, <span style="font-family: "Courier New", Courier, monospace;">Function<T,R></span><span style="font-family: inherit;"> is the type of functions that take an argument of type <span style="font-family: "Courier New", Courier, monospace;">T</span> and return a result of type <span style="font-family: "Courier New", Courier, monospace;">R</span>. However, there is a whole set of interfaces that cater for primitive types, in order to avoid boxing and unboxing. (This primary mistake in the design of Java has been giving programmers grief since Java 1, and is unlikely to go away.) So <span style="font-family: "Courier New", Courier, monospace;">Int</span><span style="font-family: Courier New;">Function<R></span><span style="font-family: inherit;"> denotes functions that take an <span style="font-family: "Courier New", Courier, monospace;">int</span> and return a value of type <span style="font-family: "Courier New", Courier, monospace;">R</span>.</span></span><br />
<br />
What is the return type of <span style="font-family: "Courier New", Courier, monospace;">makeAdder</span>? It is a function that takes an <span style="font-family: "Courier New", Courier, monospace;">int</span> and returns an <span style="font-family: "Courier New", Courier, monospace;">int</span>; such functions are described by the interface <span style="font-family: "Courier New", Courier, monospace;">IntUnaryOperator</span>. The corresponding interface for functions that take an object of type <span style="font-family: "Courier New", Courier, monospace;">T</span> and return an object of the same type is <span style="font-family: "Courier New", Courier, monospace;">UnaryOperator<T></span>.<br />
<br />
As I will discuss in a later post, typed functional languages such as ML and Haskell have a rich set of functional types and a concise yet very expressive type notation. The type of <span style="font-family: "Courier New", Courier, monospace;">makeAdder</span> would be specified in such languages simply as <span style="font-family: "Courier New", Courier, monospace;">int -> int -> int</span>, a notation that is similar to the way functions are defined. This one indicates a function that receives an <span style="font-family: Courier New;">int</span>, and returns a function of type <span style="font-family: Courier New;">int -> int</span>, that is, a function that takes an <span style="font-family: Courier New;">int</span> and returns an <span style="font-family: "Courier New", Courier, monospace;">int</span>. Such notations would make the burden of type specifications in Java much easier.<br />
<br />
<span style="font-size: x-small;">#functionalprogramming #java8</span>Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com0tag:blogger.com,1999:blog-5536017433265189318.post-33497495606523172022014-09-21T14:11:00.000+03:002015-01-12T18:42:32.753+02:00Functional Programming in Mainstream Languages, Part 1: What and Why<blockquote class="tr_bq">
(Jump to <a href="http://the-dusty-deck.blogspot.com/2014/09/functional-programming-in-mainstream.html#toc">Table of Contents</a>)</blockquote>
John Backus worked for IBM from 1950 until 1991 and was the principal developer of FORTRAN, one of the first high-level programming languages. He is immortalized in the acronym BNF, which stands for "Backus-Naur Form" (or sometimes "Backus Normal Form"). In 1977 he received the ACM Turing Award (the "Nobel prize of Computer Science"); his award lecture was titled "<a href="http://dl.acm.org/citation.cfm?id=359579" target="_blank">Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs</a>." This was in a way a reaction to FORTRAN, and describes the vision of functional programming.<br />
<br />
The "von Neumann style" is a model of computation that is very close to the way computers actually work. Its main component is the memory, which is composed of individually-addressable cells. Each memory cell can be read and modified by the computer executing a program, which is also stored in memory. This model was very useful for building early computers, and was naturally taken as the basis for the first high-level languages. The closer the model of the language is to the hardware model, the easier it is to compile programs to machine instructions that the hardware can execute directly.<br />
<br />
Backus, however, made the point that the language model can be more abstract than the hardware model. While this puts a greater strain on compiler writers, it can free (or "liberate") programmers from a lot of the drudgery that is involved in programming directly to the hardware model.<br />
<br />
The most basic principle of functional programming is the absence of any side effects. This means that functional programming language do not have the concept of variables as places (representing memory cells) that can be changed. Values in functional programs are <em>immutable;</em> that is, they can't change. This concept extends to data structures as well; for example, lists, maps, and "objects" in functional languages can't be modified, in total or in part. And it also extends to interactions of the program with the outside world.<br />
<br />
This may seem like an impossible restriction; how can you describe a computation without changing values? In fact, it is quite easy and natural, but it does take some getting used to, especially if you are used to programming in imperative languages. These include most mainstream languages, in which variables and mutable data structures are the norm.<br />
<br />
The major benefit of functional programming is its very simple computational model, which is very close to mathematical thinking. Because values in a functional program can't change, functional programs enjoy the property of <em>referential transparency</em>. This means that if an expression has some value, it will always have the same value. (This is not true in imperative languages; just think of a parameterless function that returns pseudo-random numbers.) This means that you can use the well-known substitution principle from mathematics: if <em>a</em>=<em>b</em> then you can replace <em>a</em> by <em>b</em> everywhere it appears. This is not true in imperative languages, since even if <em>a</em>=<em>b</em> now, they may be different after any change that may affect one or both of the expressions. The computational model of imperative languages therefore must incorporate the notion of time; every assertion may be true at one time and false in another. This results in a much more complicated model.<br />
<br />
Most programmers don't bother thinking about the computational model underlying their programming language, but it is crucial for writing, understanding, and reasoning about programs. A simple model makes all these simpler. Programming in a language that has a complex model is like walking around with a heavy weight on your back; you don't notice you're carrying it until it is suddenly gone.<br />
<br />
Another important property of functional programs, which is becoming increasingly important, is that it is much easier to parallelize them. Imperative programs suffer from problems such as race conditions and non-atomic updates, which are a result of side effects. By eliminating side effects, functional programs get rid of these undesirable consequences as well. One commercially-successful functional language that makes great use of this fact is <a href="http://en.wikipedia.org/wiki/Erlang_(programming_language)" target="_blank">Erlang</a>.<br />
<br />
The functional paradigm is Turing-complete; that is, it can express any computation that any conceivable machine can perform. However, creating functional analogues of mutable data structures is complicated (although this work can mostly be relegated to library writers). It is therefore unrealistic to expect most programmers to abandon mainstream languages in favor of functional languages.<br />
<br />
Since functional programming is predicated on the lack of side effects, it seems to be inherently contradictory to imperative programming. However, in the last decade or two, there is a growing movement to incorporate functional programming techniques into scripting and object-oriented languages, including JavaScript, Ruby, Scala, and, more recently, Java 8. There is also much academic work on the integration of the functional and object-oriented paradigms; so much so, that one of the predictions of Murphy-Hill and Grossman in their paper "<a href="http://homes.cs.washington.edu/~djg/papers/fose14.pdf" target="_blank">How Programming Languages Will Co-evolve with Software Engineering: A Bright Decade Ahead</a>" (Future of Software Engineering, 2014) is the blurring between these paradigms (see <a href="http://the-dusty-deck.blogspot.com/2014/08/review-how-programming-languages-will.html" target="_blank">my review of that paper</a>).<br />
<br />
How can these conflicting paradigms be reconciled? The point is that even if you want to use side effects (including assignment and mutation of data structures), you don't have to go the whole hog and use them everywhere. By making some of your data structures immutable, you will reap some of the benefits of functional programming. Bertrand Meyer, one of the gurus of object-oriented programming, includes the Command-Query Separation principle in the chapter on designing class interfaces in his landmark book, <a href="http://www.amazon.com/gp/product/0136291554/ref=as_li_tl?ie=UTF8&camp=1789&creative=9325&creativeASIN=0136291554&linkCode=as2&tag=thdude04-20&linkId=EVKD6KLM4U62RXQB">Object-Oriented Software Construction (2nd Edition)</a>. This principle requires methods to be either <em>queries</em>, which return information but don't mutate objects, or <em>commands</em>, which mutate objects but don't return any results, but not both. This separation results in some measure of referential transparency, because it tends to reduce the number of mutations.<br />
<br />
In addition to immutability, the most important aspects of functional programming that are also relevant to imperative languages are high-order functions and streams. In following posts I will show examples of functional programming techniques, both in (fully or mostly) functional languages, as well as in mainstream languages including Java 8.<br />
<br />
<a href="https://www.blogger.com/null" id="toc"></a>
This series of posts has the following parts:<br />
<br />
<strong>Introduction</strong><br />
<a href="http://the-dusty-deck.blogspot.com/2014/09/functional-programming-in-mainstream.html">Part 1: What and Why</a><br />
<br />
<strong>Higher-order functions</strong><br />
<a href="http://the-dusty-deck.blogspot.com/2014/11/functional-programming-in-mainstream.html">Part 2: Java 8 (Introduction)</a><br />
<a href="http://the-dusty-deck.blogspot.com/2014/11/functional-programming-in-mainstream_27.html">Part 3: Java 7 and Java 8</a><br />
<a href="http://the-dusty-deck.blogspot.com/2014/11/functional-programming-in-mainstream_28.html">Part 4: JavaScript</a><br />
<a href="http://the-dusty-deck.blogspot.com/2014/12/functional-programming-in-mainstream.html">Part 5: Scala</a><br />
<a href="http://the-dusty-deck.blogspot.com/2014/12/functional-programming-in-mainstream_9.html">Part 6: Xtend</a><br />
<a href="http://the-dusty-deck.blogspot.com/2015/01/functional-programming-in-mainstream.html">Part 7: Haskell</a><br />
<br />
<span style="font-size: x-small;">#functionalprogramming</span>Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com0tag:blogger.com,1999:blog-5536017433265189318.post-35595221620270706852014-08-17T16:05:00.000+03:002014-08-17T16:05:36.999+03:00Review: How Programming Languages Will Co-evolve with Software EngineeringUntil recently, programming languages have been developed with little consideration for programming environments and tools, with the notable exception of Smalltalk, which was co-developed with an elaborate environment from the start. Murphy-Hill and Grossman note in their paper "<a href="http://homes.cs.washington.edu/~djg/papers/fose14.pdf" target="_blank">How Programming Languages Will Co-evolve with Software Engineering: A Bright Decade Ahead</a>" (Future of Software Engineering, 2014) that this situation is changing, and provide seven predictions on the convergence of programming languages and software engineering (or, more precisely, programming environments and tools) in the next decade.<br />
<br />
They predict that future programming languages will be designed with integrated development environments (IDEs) and social networks in mind. One example they give for the former is the addition of dot notation to F#, allowing a syntax such as x.Length in addition to the functional length(x). (Note, though, that in F# these have different meanings.) The authors claim that the primary benefit of this notation is the ability of the IDE to provide code-completion for method (or function) names when typing "x."; this facility doesn't (yet) exist for the functional notation. I have my doubts about this being the major reason for the inclusion of members in F#, but it could certainly be a reason for introducing dot notation as syntactic sugar for function calls in new languages.<br />
<br />
Another prediction is that source code will no longer be limited to a single sequence of characters, instead being replaced by multiple simultaneous views. Multiple views are already available through the use of various tools; what I would call refactor-and-undo is probably the most widely used method, but there are various tools specifically targeted at showing multiple views of a program. These multiple views can be stored together as the official representation of the program, instead of being generated from a single "ground truth" consisting of ASCII (or unicode) strings.<br />
<br />
Murphy-Hill and Grossman expect that future language design will be influenced by controlled experiments on how programmers use language features and to what extent. With the widespread availability of open-source projects, it is possible to study this rigorously, and select language features based on what really works "in the wild." This is already happening to some extent with existing languages, such as C#. I would advocate some care when using this method, since we know that some programming features take a long time to achieve adoption; a case in point is functional-programming techniques (see the last prediction below). We should be careful not to eliminate good ideas just because they don't receive a wide following in the short term.<br />
<br />
Turning to other technologies, the next prediction is that formal verification will become a reality for developers, rather than being limited to a small group of highly experienced researchers. This will require the development of proof assistants that are stronger and more usable than those available today. Obviously, there is a lot of work to be done before the use of formal verification becomes widespread, but advances in this area provide some support for the authors' optimism.<br />
<br />
Gradual typing is a technique that allows developers to write programs with little or no type information. As the programs mature, types can be added in order to raise the level of confidence in the correctness of the program by making more properties statically checkable. Murphy-Hill and Grossman predict that gradual typing will become more widespread in new programming languages, and will expand to include properties that can be expressed as types but aren't available in popular contemporary languages.<br />
<br />
Existing programming languages are being used in new domains, such as parallel and distributed programming and big data, even though these languages aren't particularly suited to these domains. The success of Erlang is an example of how well a language built from the ground up to support distributed computation can do when applied appropriately. Murphy-Hill and Grossman predict that newer languages will focus more on new paradigms at the expense of traditional single-user (and often still single-threaded) applications.<br />
<br />
This is related to the final prediction, which is that functional-progrmming concepts will become more widespread, and the distinction between functional and imperative (or object-oriented) programming will be more and more blurred. This trend is already happening, with the introduction of function objects ("lambdas") into popular languages such as C++, Java, C#, and Ruby, and with mixed languages such as Scala. First-class function objects are one primary feature of functional programming; the other is the use of immutable data, which is particularly important in distributed applications.<br />
<br />
There is a recent (and not so recent) body of work that points in the direction of each of these predictions. Unfortunately, there are many influences on the design of programming languages, and various features of currently-popular languages were not really designed but added without serious consideration. I am therefore not quite as optimistic as the authors; however, the points they make are insightful and the paper is well-worth reading. Be sure to put a link to the paper in your 2024 calendar, in order to see which of the predictions will be realized by then! Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com0tag:blogger.com,1999:blog-5536017433265189318.post-33810150246651569142014-06-05T18:13:00.002+03:002014-06-08T14:31:01.316+03:00Xtend, the Gentle and Functional JavaI didn't want to learn yet another programming language. But I had to.<br />
<br />
I needed to create an Eclipse editor for a domain-specific language, and I needed to customize content-assist and completion. A friend recommended <a href="http://www.eclipse.org/Xtext/" target="_blank">Xtext</a> as a quick way to get an Eclipse editor with all the goodies up and running. And it was quite easy to start with; I had to translate my ANTLR grammar into Xtext, which wasn't too painful, and within a day or so I had a working editor for my DSL.<br />
<br />
The next step was to add custom content-assist to the editor. This turned out to be relatively easy as well, except that the file Xtext generated for me was in this new language, <a href="http://www.eclipse.org/xtend/" target="_blank">Xtend</a>. So I had to learn the language. Unlike quite a few other people I know, I first read the manual. I admit I did this reluctantly, but as I kept reading I got more and more excited.<br />
<br />
I've been using Java for many years, both in teaching and in developing applications. It is certainly nicer than C++, and the refactoring support in Eclipse is wonderful, but there were other languages I used in the past that I enjoyed much more than Java. Common Lisp, especially on the Lisp Machine, was a great language with a great environment. Scheme was a special pleasure, being a very compact yet extremely powerful language. In contrast, Java is very limiting and extremely verbose!<br />
<br />
<div class="MsoNormal">
First, the substance. I am a great fan of functional programming; it is a limiting yet at the same time liberating paradigm. You don't get to make any assignments or other state changes; in return, the computation model is very simple and similar to standard mathematics. Functional languages enjoy <i>referential transparency</i>, which means that the same expression in the same environment will always yield the same value. In contrast, when side effects are possible, it is possible to call the same function or method multiple times and get different results each time, since something in the environment may have changed. While object-oriented programming seems to be all about changing state, it is still possible to use functional-programming techniques to minimize state changes to those places where they are really useful. Item 15 of Joshua Bloch's excellent book <a href="http://www.amazon.com/gp/product/0321356683/ref=as_li_tl?ie=UTF8&camp=1789&creative=9325&creativeASIN=0321356683&linkCode=as2&tag=thdude04-20&linkId=ZG5765C5GHBKNPLO" target="_blank">Effective Java (2nd Edition)</a> is "Minimize mutabililty." And Bertand Meyer, designer of the Eiffel programming language,
expounds in his classic text <a href="http://www.amazon.com/gp/product/0136291554/ref=as_li_tl?ie=UTF8&camp=1789&creative=9325&creativeASIN=0136291554&linkCode=as2&tag=thdude04-20&linkId=G7AYF6UJY6LIIASI" target="_blank">Object-Oriented Software Construction (2nd Edition)</a> on his Command-Query Separation Principle.<span style="mso-spacerun: yes;"> </span>This
principle advocates minimizing state changes, and using functional programming
techniques inside object-oriented programs as much as possible.<span style="mso-spacerun: yes;"> </span>The Scala language is a more recent attempt
to reconcile the functional and object-oriented programming styles. Java allows a functional programming style, but makes it unnecessarily difficult. (A ray of hope, though: Java 8 is going to have lambda notation!)<br />
<br />
And then, there is the form. Java is obnoxiously verbose, especially in its requirements for types everywhere. I'm not necessarily objecting to strong typing here, but even with strong typing there are many type inferences that the compiler can make. For example, the fact that I have to write something like this is infuriating:<br />
<br />
HashMap<String, List<String, Integer>> map = new HashMap<String, List<String, Integer>>();<br />
<br />
One way of thinking about Xtend is as a simpler syntax for Java. The Xtend compiler does extensive type inference, and most type specifications are optional. But Xtend is much more than that. It provides many conveniences, and is particularly well-geared to the use of functional techniques. Functions ("lambda expressions") are an essential part of the language, and are a pleasure to use and read. They simplify a lot of the boilerplate code needed in Java for callbacks of various kinds. In addition, Xtend libraries supply many utilities in the functional style, and these look like an integral part of the language due to Xtend's extension capabilities, which allow external libraries to add methods that can be called as though they existed in the original Java classes. Another great convenience is a much enhanced switch statements, which, among other things, can switch on types without requiring type casts.<br />
<br />
At the same time, Xtend compiles directly into (readable) Java, not even into bytecode. So it is 100% compatible with Java, and can be used in any combination with Java classes. For example, Xtend classes can inherit from Java classes as well as the other way round. Xtend is well-integrated with Eclipse, and offers most of the conveniences of Java development, including debugging the Xtext sources. The major lack is in refactoring, although Rename, for example, is available using the Alt-Shift-R shortcut.<br />
<br />
If you are stuck with Java but want a nicer syntax, I recommend that you take a good long look at Xtend. You can start with the 50-second video on the <a href="http://www.eclipse.org/xtend/" target="_blank">Xtend website</a>, then read the manual; surprisingly, it is quite readable!<br />
<br />
<span style="font-size: x-small;">#Xtend #FunctionalProgramming #Java</span></div>
Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com0tag:blogger.com,1999:blog-5536017433265189318.post-66235645463266567142014-03-10T15:09:00.000+02:002014-03-10T15:09:15.247+02:00Review: Mars Code<!--[if gte mso 9]><xml>
<w:WordDocument>
<w:View>Normal</w:View>
<w:Zoom>0</w:Zoom>
<w:TrackMoves/>
<w:TrackFormatting/>
<w:PunctuationKerning/>
<w:ValidateAgainstSchemas/>
<w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid>
<w:IgnoreMixedContent>false</w:IgnoreMixedContent>
<w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText>
<w:DoNotPromoteQF/>
<w:LidThemeOther>EN-US</w:LidThemeOther>
<w:LidThemeAsian>X-NONE</w:LidThemeAsian>
<w:LidThemeComplexScript>HE</w:LidThemeComplexScript>
<w:Compatibility>
<w:BreakWrappedTables/>
<w:SnapToGridInCell/>
<w:WrapTextWithPunct/>
<w:UseAsianBreakRules/>
<w:DontGrowAutofit/>
<w:SplitPgBreakAndParaMark/>
<w:DontVertAlignCellWithSp/>
<w:DontBreakConstrainedForcedTables/>
<w:DontVertAlignInTxbx/>
<w:Word11KerningPairs/>
<w:CachedColBalance/>
</w:Compatibility>
<w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel>
<m:mathPr>
<m:mathFont m:val="Cambria Math"/>
<m:brkBin m:val="before"/>
<m:brkBinSub m:val="--"/>
<m:smallFrac m:val="off"/>
<m:dispDef/>
<m:lMargin m:val="0"/>
<m:rMargin m:val="0"/>
<m:defJc m:val="centerGroup"/>
<m:wrapIndent m:val="1440"/>
<m:intLim m:val="subSup"/>
<m:naryLim m:val="undOvr"/>
</m:mathPr></w:WordDocument>
</xml><![endif]--><br />
<!--[if gte mso 9]><xml>
<w:LatentStyles DefLockedState="false" DefUnhideWhenUsed="true"
DefSemiHidden="true" DefQFormat="false" DefPriority="99"
LatentStyleCount="267">
<w:LsdException Locked="false" Priority="0" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Normal"/>
<w:LsdException Locked="false" Priority="9" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="heading 1"/>
<w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 2"/>
<w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 3"/>
<w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 4"/>
<w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 5"/>
<w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 6"/>
<w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 7"/>
<w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 8"/>
<w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 9"/>
<w:LsdException Locked="false" Priority="39" Name="toc 1"/>
<w:LsdException Locked="false" Priority="39" Name="toc 2"/>
<w:LsdException Locked="false" Priority="39" Name="toc 3"/>
<w:LsdException Locked="false" Priority="39" Name="toc 4"/>
<w:LsdException Locked="false" Priority="39" Name="toc 5"/>
<w:LsdException Locked="false" Priority="39" Name="toc 6"/>
<w:LsdException Locked="false" Priority="39" Name="toc 7"/>
<w:LsdException Locked="false" Priority="39" Name="toc 8"/>
<w:LsdException Locked="false" Priority="39" Name="toc 9"/>
<w:LsdException Locked="false" Priority="35" QFormat="true" Name="caption"/>
<w:LsdException Locked="false" Priority="10" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Title"/>
<w:LsdException Locked="false" Priority="1" Name="Default Paragraph Font"/>
<w:LsdException Locked="false" Priority="11" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Subtitle"/>
<w:LsdException Locked="false" Priority="22" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Strong"/>
<w:LsdException Locked="false" Priority="20" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Emphasis"/>
<w:LsdException Locked="false" Priority="59" SemiHidden="false"
UnhideWhenUsed="false" Name="Table Grid"/>
<w:LsdException Locked="false" UnhideWhenUsed="false" Name="Placeholder Text"/>
<w:LsdException Locked="false" Priority="1" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="No Spacing"/>
<w:LsdException Locked="false" Priority="60" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Shading"/>
<w:LsdException Locked="false" Priority="61" SemiHidden="false"
UnhideWhenUsed="false" Name="Light List"/>
<w:LsdException Locked="false" Priority="62" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Grid"/>
<w:LsdException Locked="false" Priority="63" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 1"/>
<w:LsdException Locked="false" Priority="64" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 2"/>
<w:LsdException Locked="false" Priority="65" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 1"/>
<w:LsdException Locked="false" Priority="66" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 2"/>
<w:LsdException Locked="false" Priority="67" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 1"/>
<w:LsdException Locked="false" Priority="68" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 2"/>
<w:LsdException Locked="false" Priority="69" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 3"/>
<w:LsdException Locked="false" Priority="70" SemiHidden="false"
UnhideWhenUsed="false" Name="Dark List"/>
<w:LsdException Locked="false" Priority="71" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Shading"/>
<w:LsdException Locked="false" Priority="72" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful List"/>
<w:LsdException Locked="false" Priority="73" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Grid"/>
<w:LsdException Locked="false" Priority="60" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Shading Accent 1"/>
<w:LsdException Locked="false" Priority="61" SemiHidden="false"
UnhideWhenUsed="false" Name="Light List Accent 1"/>
<w:LsdException Locked="false" Priority="62" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Grid Accent 1"/>
<w:LsdException Locked="false" Priority="63" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 1"/>
<w:LsdException Locked="false" Priority="64" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 1"/>
<w:LsdException Locked="false" Priority="65" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 1 Accent 1"/>
<w:LsdException Locked="false" UnhideWhenUsed="false" Name="Revision"/>
<w:LsdException Locked="false" Priority="34" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="List Paragraph"/>
<w:LsdException Locked="false" Priority="29" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Quote"/>
<w:LsdException Locked="false" Priority="30" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Intense Quote"/>
<w:LsdException Locked="false" Priority="66" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 2 Accent 1"/>
<w:LsdException Locked="false" Priority="67" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 1"/>
<w:LsdException Locked="false" Priority="68" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 1"/>
<w:LsdException Locked="false" Priority="69" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 1"/>
<w:LsdException Locked="false" Priority="70" SemiHidden="false"
UnhideWhenUsed="false" Name="Dark List Accent 1"/>
<w:LsdException Locked="false" Priority="71" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Shading Accent 1"/>
<w:LsdException Locked="false" Priority="72" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful List Accent 1"/>
<w:LsdException Locked="false" Priority="73" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Grid Accent 1"/>
<w:LsdException Locked="false" Priority="60" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Shading Accent 2"/>
<w:LsdException Locked="false" Priority="61" SemiHidden="false"
UnhideWhenUsed="false" Name="Light List Accent 2"/>
<w:LsdException Locked="false" Priority="62" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Grid Accent 2"/>
<w:LsdException Locked="false" Priority="63" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 2"/>
<w:LsdException Locked="false" Priority="64" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 2"/>
<w:LsdException Locked="false" Priority="65" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 1 Accent 2"/>
<w:LsdException Locked="false" Priority="66" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 2 Accent 2"/>
<w:LsdException Locked="false" Priority="67" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 2"/>
<w:LsdException Locked="false" Priority="68" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 2"/>
<w:LsdException Locked="false" Priority="69" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 2"/>
<w:LsdException Locked="false" Priority="70" SemiHidden="false"
UnhideWhenUsed="false" Name="Dark List Accent 2"/>
<w:LsdException Locked="false" Priority="71" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Shading Accent 2"/>
<w:LsdException Locked="false" Priority="72" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful List Accent 2"/>
<w:LsdException Locked="false" Priority="73" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Grid Accent 2"/>
<w:LsdException Locked="false" Priority="60" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Shading Accent 3"/>
<w:LsdException Locked="false" Priority="61" SemiHidden="false"
UnhideWhenUsed="false" Name="Light List Accent 3"/>
<w:LsdException Locked="false" Priority="62" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Grid Accent 3"/>
<w:LsdException Locked="false" Priority="63" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 3"/>
<w:LsdException Locked="false" Priority="64" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 3"/>
<w:LsdException Locked="false" Priority="65" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 1 Accent 3"/>
<w:LsdException Locked="false" Priority="66" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 2 Accent 3"/>
<w:LsdException Locked="false" Priority="67" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 3"/>
<w:LsdException Locked="false" Priority="68" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 3"/>
<w:LsdException Locked="false" Priority="69" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 3"/>
<w:LsdException Locked="false" Priority="70" SemiHidden="false"
UnhideWhenUsed="false" Name="Dark List Accent 3"/>
<w:LsdException Locked="false" Priority="71" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Shading Accent 3"/>
<w:LsdException Locked="false" Priority="72" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful List Accent 3"/>
<w:LsdException Locked="false" Priority="73" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Grid Accent 3"/>
<w:LsdException Locked="false" Priority="60" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Shading Accent 4"/>
<w:LsdException Locked="false" Priority="61" SemiHidden="false"
UnhideWhenUsed="false" Name="Light List Accent 4"/>
<w:LsdException Locked="false" Priority="62" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Grid Accent 4"/>
<w:LsdException Locked="false" Priority="63" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 4"/>
<w:LsdException Locked="false" Priority="64" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 4"/>
<w:LsdException Locked="false" Priority="65" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 1 Accent 4"/>
<w:LsdException Locked="false" Priority="66" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 2 Accent 4"/>
<w:LsdException Locked="false" Priority="67" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 4"/>
<w:LsdException Locked="false" Priority="68" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 4"/>
<w:LsdException Locked="false" Priority="69" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 4"/>
<w:LsdException Locked="false" Priority="70" SemiHidden="false"
UnhideWhenUsed="false" Name="Dark List Accent 4"/>
<w:LsdException Locked="false" Priority="71" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Shading Accent 4"/>
<w:LsdException Locked="false" Priority="72" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful List Accent 4"/>
<w:LsdException Locked="false" Priority="73" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Grid Accent 4"/>
<w:LsdException Locked="false" Priority="60" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Shading Accent 5"/>
<w:LsdException Locked="false" Priority="61" SemiHidden="false"
UnhideWhenUsed="false" Name="Light List Accent 5"/>
<w:LsdException Locked="false" Priority="62" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Grid Accent 5"/>
<w:LsdException Locked="false" Priority="63" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 5"/>
<w:LsdException Locked="false" Priority="64" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 5"/>
<w:LsdException Locked="false" Priority="65" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 1 Accent 5"/>
<w:LsdException Locked="false" Priority="66" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 2 Accent 5"/>
<w:LsdException Locked="false" Priority="67" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 5"/>
<w:LsdException Locked="false" Priority="68" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 5"/>
<w:LsdException Locked="false" Priority="69" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 5"/>
<w:LsdException Locked="false" Priority="70" SemiHidden="false"
UnhideWhenUsed="false" Name="Dark List Accent 5"/>
<w:LsdException Locked="false" Priority="71" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Shading Accent 5"/>
<w:LsdException Locked="false" Priority="72" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful List Accent 5"/>
<w:LsdException Locked="false" Priority="73" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Grid Accent 5"/>
<w:LsdException Locked="false" Priority="60" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Shading Accent 6"/>
<w:LsdException Locked="false" Priority="61" SemiHidden="false"
UnhideWhenUsed="false" Name="Light List Accent 6"/>
<w:LsdException Locked="false" Priority="62" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Grid Accent 6"/>
<w:LsdException Locked="false" Priority="63" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 6"/>
<w:LsdException Locked="false" Priority="64" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 6"/>
<w:LsdException Locked="false" Priority="65" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 1 Accent 6"/>
<w:LsdException Locked="false" Priority="66" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 2 Accent 6"/>
<w:LsdException Locked="false" Priority="67" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 6"/>
<w:LsdException Locked="false" Priority="68" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 6"/>
<w:LsdException Locked="false" Priority="69" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 6"/>
<w:LsdException Locked="false" Priority="70" SemiHidden="false"
UnhideWhenUsed="false" Name="Dark List Accent 6"/>
<w:LsdException Locked="false" Priority="71" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Shading Accent 6"/>
<w:LsdException Locked="false" Priority="72" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful List Accent 6"/>
<w:LsdException Locked="false" Priority="73" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Grid Accent 6"/>
<w:LsdException Locked="false" Priority="19" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Subtle Emphasis"/>
<w:LsdException Locked="false" Priority="21" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Intense Emphasis"/>
<w:LsdException Locked="false" Priority="31" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Subtle Reference"/>
<w:LsdException Locked="false" Priority="32" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Intense Reference"/>
<w:LsdException Locked="false" Priority="33" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Book Title"/>
<w:LsdException Locked="false" Priority="37" Name="Bibliography"/>
<w:LsdException Locked="false" Priority="39" QFormat="true" Name="TOC Heading"/>
</w:LatentStyles>
</xml><![endif]--><!--[if gte mso 10]>
<style>
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:"Table Normal";
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-priority:99;
mso-style-qformat:yes;
mso-style-parent:"";
mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
mso-para-margin:0cm;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:11.0pt;
font-family:"Calibri","sans-serif";
mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:"Times New Roman";
mso-fareast-theme-font:minor-fareast;
mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:Arial;
mso-bidi-theme-font:minor-bidi;}
</style>
<![endif]-->
<br />
<div class="MsoNormal">
Despite a few spectacular failures (such as the <a href="http://mars.jpl.nasa.gov/msp98/orbiter/" target="_blank">Mars Climate Orbiter</a> and <a href="http://mars.jpl.nasa.gov/msp98/lander/" target="_blank">Mars Polar Lander</a>), NASA is one of the top
organizations worldwide in Systems and Software Engineering.<span style="mso-spacerun: yes;"> </span>The Mars rover <a href="http://marsrover.nasa.gov/home/index.html" target="_blank">Opportunity</a> has recently
celebrated ten years of operation on Mars, and the newer <a href="http://www.nasa.gov/mission_pages/msl/" target="_blank">Curiosity</a> has been
operating since August 2012, after a <a href="http://www.jpl.nasa.gov/video/index.php?id=1103" target="_blank">landing maneuver</a> of unprecedented
complexity.<span style="mso-spacerun: yes;"> </span>This is quite a feat,
considering the fact that the nearest repair technician is over 30 million
miles away, and communications delay is about 15 minutes on average.<span style="mso-spacerun: yes;"> </span>How do they do it?</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
The paper <i>Mars Code</i> by Gerard J. Holzmann (<a href="http://cacm.acm.org/magazines/2014/2/171689-mars-code/fulltext" target="_blank">Communications of the ACM, Feb. 2014</a>) gives a rare glimpse into the process used in programming the Mars
rovers.<span style="mso-spacerun: yes;"> </span>It focuses on three methods used
to reduce the risk of failure.<span style="mso-spacerun: yes;"> </span>An
important feature of all three methods is the use of automation.<span style="mso-spacerun: yes;"> </span>The first consists of a set of risk-related
coding rules, based on actual risks observed in previous missions.<span style="mso-spacerun: yes;"> </span>For example, one rule requires the code to
pass compilation and static analyzer checks without any warnings.<span style="mso-spacerun: yes;"> </span>Another requires the code to have a minimum
assertion density of 2%.<span style="mso-spacerun: yes;"> </span>The assertions
are enabled not only for testing, but also during the mission, when violations
place the rover into a safe mode, during which failures can be diagnosed and
fixed.<span style="mso-spacerun: yes;"> </span>All the rules are checked
automatically when the code is compiled.<span style="mso-spacerun: yes;"> </span></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
The second method consists of tool-based code review.<span style="mso-spacerun: yes;"> </span>Four different static-analysis tools are
used, with an automated system to manage the interaction between developers and
reviewers in response to tool warnings.<span style="mso-spacerun: yes;">
</span>In over 80% of the cases, developers agreed with the warnings and fixed
the code without reviewer intervention.<span style="mso-spacerun: yes;">
</span>An interesting observation Holzmann makes is that there was surprisingly
little overlap between the between the warnings issued by the four tools. Apparently, each tool has its own areas of strength, and they are different enough that it is useful to use them all.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
The third and strongest method is the use of a model
checking tool for race conditions, one of the most difficult types of bugs to
discover.<span style="mso-spacerun: yes;"> </span>This cannot be done for the
whole code base, but was used extensively in the Curiosity mission to verify
critical multithreaded algorithms.<span style="mso-spacerun: yes;"> </span>In
some cases, the tool works directly from the C source code.<span style="mso-spacerun: yes;"> </span>For larger subsystems, input models had to be
prepared manually in the language of the model checker; this can reduce the
input size by over one order of magnitude.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
The challenges faced by NASA are obviously unique, and are
very different from those involved in cloud-based mobile applications, to take
a popular example.<span style="mso-spacerun: yes;"> </span>There are many papers
and books describing methodologies for developing such systems.<span style="mso-spacerun: yes;"> </span>However, developing safety-critical systems
for cars and aircraft, medical devices, and power grids, or financial systems
that must be resilient to faults and deliberate attacks, requires reliability
levels similar to those of NASA.<span style="mso-spacerun: yes;"> </span>For
developers of such systems, papers such as Holzmann’s should be required
reading.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
A related article you may want to read is <a href="http://www.fastcompany.com/28121/they-write-right-stuff" target="_blank">They Write the Right Stuff</a>, by Charles Fishman. This article, from 1996, describes the culture of the group that wrote the software for the space shuttle, and how their development process led to the very high quality of their product. For example, whenever a mistake was found in the code, it was traced to the corresponding problem in the process that allowed the mistake to be written and pass reviews and testing. Then, the team investigated what other bugs could have been caused by the same process failure. In this way, a bug in the control of the shuttle's robotic manipulator arm was traced back to a certain type of problem. When investigating other effects of the same problem, a much more serious bug was found in the control of the high-gain antenna. The bug was fixed before it had a chance to manifest itself.</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
It takes a lot of discipline and investment to work this way, but the result is a much better, more reliable product. Sometimes it isn't all that important; other times, it's the difference between life and death.</div>
Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com0tag:blogger.com,1999:blog-5536017433265189318.post-44444076560540958972012-06-24T13:41:00.000+03:002012-06-24T13:41:02.810+03:00Design by Contract and RefactoringI am a great believer both in refactoring and in design by contract. How do these two work together?<br />
<br />
First, contracts are a great help when refactoring. The first thing you need to know when you refactor a piece of code is what it is supposed to do. This tells you what you can and can't do with it, and, no less important, what would be useful to do with it. If it's an arbitrary set of statements, say part of an existing method you are trying to extract into a new method, there's little to help beyond reading the code and trying to figure out what it does and how it fits with the rest of the code. (Even then, there are tools that try to deduce a contract for an arbitrary piece of code; more on that in a later post). But if it's a method, you should have more help.<br />
<br />
If you have a good suite of unit tests, you can try to look at the tests of that method to figure out what it's supposed to do. But it's much easier if you have a contract attached to the method; the contract should give you a lot of the information you need. For example, suppose you want to move one or more methods and fields from one class to another (perhaps you are using Pull Up Method, Push Down Method, or just Move Method). In that case, you should check the contracts of moved methods to see how they fit in their new class. Are the invariants of the new class maintained by the moved methods? Are the contracts of the methods still valid, taking inheritance into account? Nasty bugs can result if the answers are negative.<br />
<br />
On the other hand, refactoring may require corresponding changes in existing contracts, as well as the creation of brand-new contracts. In other words, contracts need to be refactored together with the associated code. This is an added burden, which may well be an obstacle to the use of the design-by-contract methodology; not only do I have to invest effort in creating the contracts in the first place, I also have to refactor them later. Why should I bother?<br />
<br />
There are several answers to this complaint. First, consider the alternatives. You may be flying blind, trusting only on your undocumented understanding of the code. In that case, good luck to you; you'll need it. If you follow an agile methodology, such as Extreme Programming, you should have an extensive suite of unit tests to help you refactor. Unit tests are very vulnerable to change in the code, since they are attached to small units of code. This means that any shift in responsibilities is likely to invalidate some tests, which will then have to be refactored or completely rewritten. So there's always the need to refactor associated artifacts when you refactor the code.<br />
<br />
Having contracts can significantly reduce the amount of detail in unit tests, and even the total number of unit tests. This is due to the fact that a major part of the responsibility usually given to unit tests is now taken by the contract. All that the tests need to do is exercise the system, but correctness checking (or a large part of it) is now done by checking the contracts. So now you can have higher-level tests that exercise the system, instead of unit tests for each class and method. For example, suppose you are implementing a cryptographic algorithm such as RSA. A test that creates a random key, then encrypts a random data buffer, decrypts it, and checks that the result is the original data, is guaranteed to exercise almost all of your cryptographic code. Moreover, this test can be used on many different implementations. In contrast, the internals of the implementation can vary widely, since there are many ways to implement the large-number arithmetic operations required for RSA, and their efficiency will be different under different circumstances. By having an application-level test augmented with contracts, the burden of refactoring tests is reduced to almost nil.<br />
<br />
This still leaves the requirement of refactoring contracts, and the question of how much refactoring tools can help. In order to understand that, it is necessary to examine the relationships between code refactorings and contracts. On the simplest level, contracts are treated just like code. For example, when renaming a method, all references to it in the code must be appropriately modified; so must all references in assertions. Similarly, a method may be eliminated when it is not used anywhere, including in assertions. Contract-aware tools should find these kinds of relationships easy to perform automatically. Of the refactorings listed in Fowler's <a href="http://www.amazon.com/gp/product/0201485672/ref=as_li_qf_sp_asin_tl?ie=UTF8&tag=thdude04-20&linkCode=as2&camp=1789&creative=9325&creativeASIN=0201485672">Refactoring</a><img alt="" border="0" height="1" src="http://www.assoc-amazon.com/e/ir?t=thdude04-20&l=as2&o=1&a=0201485672" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; margin: 0px;" width="1" /> book, 32% do not interact with contracts except possibly in this way. These are mostly syntactic refactorings such as Remove Parameter or Rename Method, or those that eliminate classes or methods, such as Inline Class and Inline Method.<br />
<br />
Some contracts affect the applicability of certain refactorings. As mentioned above, a method should only be moved if it won't violate the invariant of its new class. (Of course, it might be possible to modify that invariant to accomodate the moved method; this can be done in a separate step, before moving the method.) 13% of Fowler's refactorings have this nature.<br />
<br />
Some refactorings require the creation of new or modified contracts. The most extreme case is Extract Method, which creates a new method out of arbitrary code. Discovering the contract for arbitrary code is impossible in general, although some tools can discover partial contracts. Another example is Create Superclass, which can create contracts for new methods based on existing contracts in subclasses. 59% of Folwer's refactorings fall into this category (which includes 4% that are also included in the previous one).<br />
<br />
Finally, some new refactorings can be defined to deal specifically with contracts; these include Pull Up Contract, Push Down Contract, Create Abstract Precondition, and Simplify Assertion.<br />
<br />
In a future post I will discuss automation of contract-related refactorings and how refactoring tools can take some of the burden of the contracts.<br />
<br />
<br />Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com0tag:blogger.com,1999:blog-5536017433265189318.post-11548630705958612912012-02-19T12:13:00.001+02:002012-02-19T12:13:57.760+02:00RefactoringChange is a way of life in software development. Requirements change because clients gain a better understanding of their needs (possibly due to experience with an existing version of the software), to take advantage of new business opportunities, or for external reasons such as new legislation that requires new types of auditing, or change in standards. The environment may change in various ways; for example, moving from a private data center to a public cloud, operating systems may become obsolete, or mission-specific hardware may need to be upgraded. Change is the greatest challenge to the software development process, and development methodologies employ various tactics to accommodate it. The classic "waterfall" methodology tries to eliminate it, by spending a lot of time in the beginning of the project trying to get the requirements just right. Unfortunately, even if this is extraordinarily successful, by the time the other steps in the process are done, the requirements are practically guaranteed to be out of date.<br />
<br />
Agile methodologoies take the other extreme. Significantly, the classic introduction to Extreme Programming (nicknamed XP) by Kent Beck is called <a href="http://www.amazon.com/gp/product/0321278658/ref=as_li_tf_tl?ie=UTF8&tag=thdude04-20&linkCode=as2&camp=1789&creative=9325&creativeASIN=0321278658">Extreme Programming Explained: Embrace Change</a>. These methodologies accept that change is inevitable, and gear every activity to support it. This can only work if it is possible to modify existing software to fit changing requirements, and this is only possible if the software is always well-designed. Unfortunately, software tends to change away from a good design, because each change is usually done without much regard for the overall design. As changes accumulate, it becomes harder and harder to make further changes, and the likelihood of introducing errors grows in an exponential manner. Therefore, one of the basic tenets of agile methods is that developers must take the time to restore a clean design to their software every once in a while. This activity may seem to be unproductive, since it doesn't result in any modifications to the external behavior of the software. However, it enables further modifications, and is therefore essential.<br />
<br />
The activity of changing the internal structure of the software in order to restore it to a well-designed form without affecting external behavior is called refactoring. First introduced by Bill Opdyke in his 1992 PhD thesis, and popularized in the famous book <a href="http://www.amazon.com/gp/product/0201485672/ref=as_li_tf_tl?ie=UTF8&tag=thdude04-20&linkCode=as2&camp=1789&creative=9325&creativeASIN=0201485672">Refactoring: Improving the Design of Existing Code</a>, refactoring is an approach to software development as well as a set of "refactorings," each of which is a detailed list of instructions on how to perform structure-modifying but behavior-preserving changes in code in a reliable way. Reliability is achieved by performing unit tests after each small change, in an attempt to guarantee that behavior is still preserved. If some of the tests fail, it is easy to identify the reason, since it is rooted in the last small modification performed.<br />
<br />
Of course, in order for this to work, it is necessary to have an extensive suite of unit tests, which will guarantee (with high probability) that any change that doesn't preserve functionality will be discovered immediately. This is easier said than done. A good set of unit tests may be considerably larger than the production code itself, and requires significant effort to create and maintain. Most agilists consider this to be a necessary evil; I once heard a developer say he enjoys writing these tests, and even Kent Beck, the high priest of XP, expressed his surprise at that.<br />
<br />
Still, developing without a good suite of tests is like driving blindfolded; you can't see where you're going and you're afraid to make any change at all. In fact, Michael Feathers, in his book <a href="http://www.amazon.com/gp/product/0131177052/ref=as_li_tf_tl?ie=UTF8&tag=thdude04-20&linkCode=as2&camp=1789&creative=9325&creativeASIN=0131177052">Working Effectively with Legacy Code</a>, defines a legacy system to be one for which you don't have a good suite of unit tests. And refactoring is a very effective and satisfying way to program. I recall several experiences in which I started making some change in my code, which led to further changes, leading to a period of several days when I couldn't even compile my code, let alone run it. This is a terrible feeling; you <em>know</em> you have problems in your code, but you have no way of testing it to find out what they are. At the end of this process, when I got back to a running system, it indeed had problems, and it took a long time to find them all and fix them. By restructuring the work into a series of refactorings, it would have been possible to test much more often, and thus find problems and fix them much earlier.<br />
<br />
As I said, there can be no agile methodologies without refactoring. However, refactoring is a useful activity regardless of which methodology you use (including no methodology at all). It does come at a cost; you must have an extensive test suite, and refactoring itself takes time and effort. I consider this cost to be well spent, since it saves much more effort down the line, when the inevitable requirement changes appear. Hard as it is to convince programmers to invest in their future (see <a href="http://the-dusty-deck.blogspot.com/2010/12/programmers-as-children.html">Programmers as Children</a>), this is one of the important places to try.<br />
<br />
As in other cases, tools are a great help in following the methodology, and therefore also in convincing programmers to use it. Furthermore, good tools take away some of the burden of checking the correctness of the transformation. Good refactoring support exists (mostly for Java) in Eclipse and other modern IDEs, and I urge every developer to make the maximum use of these. When I modify my code, I make every effort to use the automated refactoring capabilities provided by the IDE, as well as the related source transformations and quick fixes. I do this even when this forces me to make the changes in a certain way or order, just to take advantage of the automation (and related reliability) in the IDE<br />
<br />
Unfortunately, all modern IDEs have bugs in their refactoring support, chiefly due to insufficient analysis. For example, they might create variable bindings that shadow existing bindings incorrectly. So you must be careful when using these tools, and be aware of their limitations. In spite of these limitations, I find them extremely useful. One of the current research interests of our group is automating more powerful refactorings and making them more reliable; more about that in a later post.Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com0tag:blogger.com,1999:blog-5536017433265189318.post-74897163773373794382011-11-14T14:44:00.001+02:002011-11-14T15:55:48.130+02:00Runtime Checking of ContractsAs <a href="http://the-dusty-deck.blogspot.com/2011/02/design-by-contract.html">I said before</a>, the most important use of contracts is methodological; by paying attention to contracts, you will be able to avoid many errors you won't have to fix later. Still, if you go to the trouble of writing contracts, you would like to get additional benefits. One of the most obvious is runtime checking of contracts, which gives warning about contract violations as they occur, helping catch errors close to their sources. Without contracts, a bug can corrupt a data structure or its contents, planting a time bomb that can explode much later. At that point, it is difficult to discover who made the erroneous change even with a debugger, since the offending method is no longer on the stack and can't be examined, and many other traces of the buggy action may also have disappeared.<br />
<br />
In order to get these kinds of warnings, the contract must be written in some formal language; typically it is some extension of boolean-valued expressions in the programming language. Extensions are necessary in order to refer to "old" values; that is, allowing the postcondition to refer to values of variables or expressions on entry to the method. Rich assertion languages also add ways of expressing universal and existential quantifiers; often, you want to express some property of all the contents of some array or other data structure, or to assert that there is some element with a given property. However, it is easy to add such capabilities to languages that don't offer them simply by writing appropriate methods to check any required condition.<br />
<br />
Runtime contract checking is complicated by several factors. First is the relationship between contracts on methods in inheritance hierarchies. As I explained in <a href="http://the-dusty-deck.blogspot.com/2011/04/correct-use-of-inheritance.html">The Correct Use of Inheritance</a>, inheriting methods may only weaken preconditions and strengthen postconditions. There are two approaches to enforcing this constraint. The one used by Eiffel uses syntactic enforcement, in which you can never write assertions violating this rule. In Eiffel, overriding methods use "ensure then" instead of "ensure" for postconditions, with the meaning that any assertion following "ensure then" is conjoined with any assertions from superclasses. For example, suppose you have a postcondition "ensure contains(x)" on the method Container.put(x); this ensures that after adding x to the container, it is indeed in it. A list is a kind of container, and there you want to add the postcondition "ensure then count = old count + 1", which means that the number of elements in the list has increased by one after adding an element. (This is not the case for sets, which are also containers.) The full postcondition of List.put(x) is now "contains(x) and then count = old count + 1". (The "and then" operator is a short-circuit operator, like && in the C family.) Similarly, preconditions in overriding methods use "require else" rather than "require", and add the new assertions by disjunction ("or else" in Eiffel, || in the C family.) While this approach prevents any violations of the inheritance rules, it means that you don't see the full contract in the class itself, and there could be hidden assertions you aren't aware of. This calls for tools that can display the full contract (see <a href="http://the-dusty-deck.blogspot.com/2011/09/viewing-contracts.html">Viewing Contracts</a>).<br />
<br />
The other approach is to require developers to maintain the correct relationships themselves, by copying assertions as necessary. In this case, you see the full contract in each class, but need to verify for yourself that the inheritance rules hold in each case.<br />
<br />
A runtime assertion-checking tool needs to be aware of the inherited contracts in either approach. In the first one, it must be aware of the full contract in order to check it properly. This is less of an issue for postconditions, because these can be checked independently. But it is crucial for preconditions, since the fact that a precondition written with a certain overriding method is false is not an error if the precondition of the method in some superclass is satisfied. In the second approach, assertions can be checked for each class independently, but you also want to add checks that warn in case the inheritance rules are violated.<br />
<br />
Another complicating factor is the need to keep "old" values, as in the example shown above: "count = old count + 1". An assertion-checking tool needs to keep the value of count on entry to the method in order to make sure that the value on exit is exactly one more. The computation of the old value could cause an exception; for example, the Stack.put(x) method may have a postcondition "count > 1 implies item(2) = old item(1)", which means that if after insertion the stack has at least two elements, then the element that used to be on top of the stack ("old item(1)") is now second ("item(2)"). As the tool evaluates the expression item(1) on entry to the method, an exception will occur if the stack is empty. This, however, is not an error in the program or in the assertions! What the tool must do is keep a record of the exception, and only raise it if the old value is ever referenced. This will never happen in this example, because if the stack was initially empty, it will have exactly one element following the put operation, the antecedent "count > 1" of the postcondition will be false, and the consequent that calls for the old value, "item(2) = old item(1)", will never be evaluated.<br />
<br />
Yet another challenge is preventing infinite recursion in assertion checking. For example, if the Stack class has an invariant capacity() >= 0, and this invariant is checked upon entry to the capacity method, an infinite recursion will result. Eiffel takes a conservative view, and turns off all assertion checking while it checks any assertion. The rationale for this is that methods used in assertions should be verified separately, before being used to specify the behavior of other parts of the program. It is possible to check more assertions without getting into an infinite recursion, and various tools have different strategies for dealing with this issue.<br />
<div dir="ltr">
<br /></div>
<div dir="ltr">
Our own assertion-checking tool for Java is called Jose, and uses aspect-oriented programming to handle the issues mentioned above. More on Jose in a later post!</div>Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com0tag:blogger.com,1999:blog-5536017433265189318.post-33046653800987845582011-09-13T20:39:00.000+03:002011-09-13T20:39:32.269+03:00Viewing ContractsThere are many ways to view a contract. As you edit your class, you naturally see the contract for each method in the header of the method, since it is part of the text. (In Eiffel, it is part of the syntax of the language; in design-by-contract tools for Java, the contract is typically expressed in the Javadoc comments of classes and methods.) But what do you do when you want to see the full contract of the method, including inherited parts? And when you are about to call some method of another class, how do you know what is the full contact for that method?<br />
<br />
The contract can have private parts, which are not meaningful to clients. As I mentioned previously, preconditions must be fully understandable to clients, since otherwise they can't be expected to comply with them. However, postconditions and invariants may refer to private parts of the implementation. For example, suppose your Queue class uses a circular buffer, called items, to implement the (bounded) queue. The implementation invariant should specify that items != null. This is an important property of the class to its implementer and anyone creating an inheriting class, but it shouldn't be exposed to clients who aren't supposed to know about implementation details. Similarly, the method that adds an element to the queue may have a postcondition specifying that the write-pointer has advanced by 1 modulo the buffer size. Again, this is useful information to the implementer, but should be hidden from clients.<br />
<br />
The distinction between private and public access levels, in code or in contracts, is usually not clear cut. For example, Java provides four different access levels; C++ has three, but allows "friends" to access private and protected members; and Eiffel has a selective export mechanism where a class can specify which other classes have access to each of its features. This means that the same class can present different interfaces to other classes, depending on their access levels. As always, interfaces include the methods visible to the particular client, as well as the contract. Different parts of the postconditions and invariants of the contract would be visible to different clients.<br />
<br />
The Eiffel development environment can show contracts in different ways, based on whether to show private assertions or not, and whether to show assertions from a single class or show all inherited assertions as well. However, the views can't be customized by client. I don't know of any other development environment that can show more than one view of a contract. Ideally, the environment would be able to show contracts from a supplier's perspective as well as from the perspective of any client. For example, if I'm editing class A, and place the cursor on a call to a method f of class B, I should be able to see (in a tooltip or in a separate view) the full contract of B.f from the point of view of class A. Such a view is not difficult to create, although it might require some tedious work. I consider such a view essential to any development environment that takes design-by-contract seriously.<br />
<br />
Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com0tag:blogger.com,1999:blog-5536017433265189318.post-21855371784256177682011-08-05T13:27:00.001+03:002011-08-05T13:27:00.646+03:00Why Don't YOU Use Design by Contract?I spent quite some time explaining why I think design by contract is such a useful methodology, and why every programmer (and especially those using object-oriented programming) should use it. So why isn't it more widely used?<br />
<br />
One obvious reason is the lack of education about design by contract. You can find many university-level courses on object-oriented programming that hardly mention design by contract, or not at all. Naturally, people who don't know about it aren't going to use it. But the problem is deeper; I know that many of my own students don't use design by contract regularly. It may be that I wasn't able to convince them that it is really useful, but I know I'm not alone in this situation. I believe that for any methodology to be practically useful, it must be supported by tools that make its application not only painless but also rewarding. And tools for design by contract are not yet at a level that promotes wide use. Also, since programmers need instant gratification (see <a href="http://the-dusty-deck.blogspot.com/2010/12/programmers-as-children.html">Programmers as Children</a>), they need tools that will help them immediately, not only in some unforseeable (yet inevitable) future where the bugs they are writing now will come back to bite them.<br />
<br />
I firmly believe that design by contract is useful even without any tools. But consider the amount of work required to use it. First, you have to write contracts for your methods. As I said before, these don't have to be complete, but they do have to capture those parts of the contract that are likely to cause the most trouble. Often, these are not deep properties of the computation. On the contrary, these are things like whether an argument to a method is allowed to be null, whether a string or an array may have zero length, whether a number has to be positive, and so on. This is not difficult to write, but write it you must. Then, you need to look at this contract whenever you call a method, and consider whether your call is correct. (Of course, if you don't bother, you will find your mistakes the hard way.)<br />
<br />
But the most painful part of almost all methodologies arises when something needs to change. Whether your requirements have changed, or whether you are just refactoring your code, you will need to change some contracts, and create new ones. Then you will have to check whether all existing calls obey the new contract (or find out the hard way, as is the normal custom).<br />
<br />
There are many opportunities for automated tools to help, at different levels . To begin with, you will want syntax checking of your contracts. This includes checking whether all preconditions can be evaluated by every caller; this is a must, since you can't require callers to obey conditions they can't evaluate. You may also want your IDE to provide syntax highlighting for contracts in a similar way to what it does with code. A "contract view" that shows just the contracts for a class would be nice, especially if it could show various views of the contracts. Such views can include the client view (where internal parts of the contracts are hidden), and the provider view (where everything is shown). The views would be customizable, for example, by showing only direct class members or all members (including inherited ones).<br />
<br />
At a more semantic level, you want your contracts to be checked while you run the program. This has great value in catching errors close to their sources. However, instrumenting a program to check contracts is not trivial. Beyond the difficulties of instrumenting any program, the semantics of the contract require some tricky handling. One example is the ability to reference in postconditions the value of expressions on entry to the method, which requires tools to compute this value and keep it intact until the end of the call.<br />
<br />
More generally, you may want a tool to help you verify the correctness of your implementation based on the contracts you write. Software verification is still an open problem, but it is a very active area of research. Part of this research is focused on verification of contracts.<br />
<br />
Turning now to the question of change, tools that help manage contracts when the code changes are a must. Such tools can modify existing contracts as well as create (draft) contracts for new code. This is by no means easy. Analyzing an arbitrary piece of code to extract contracts from it is an open (and very difficult) problem, although some progress has been made on it. The problem is easier if some information about the intent of the change is available. This can happen in refactoring; when you invoke a refactoring such as Extract Superclass, the tool has an indication of your intent, and can use this information together with existing contracts for the class (or classes) you are generalizing in order to create the contract for the new superclass.<br />
<br />
Needless to say, the Eiffel programming environment has the best tools for design by contract, although much more is needed. In future posts, I will describe some of the work my students and I have done on creating tools for design by contract in Java.Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com0tag:blogger.com,1999:blog-5536017433265189318.post-90796405299442058902011-06-12T18:52:00.005+03:002011-06-19T18:03:57.902+03:00Watch Your Step!(Note: if you are familiar with SQL injection vulnerabilities, you may want to skip to the end of this post, which mentions some new research that could eliminate such errors before they are made.)<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://imgs.xkcd.com/comics/exploits_of_a_mom.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="196" src="http://imgs.xkcd.com/comics/exploits_of_a_mom.png" t8="true" width="640" /></a></div><br />
This classic comic from <a href="http://xkcd.com/327/">xkcd</a> demonstrates one of the most common and dangerous type of security vulnerabilities in web applications, called <em>SQL injection</em>. This is a way in which an attacker can cause the application to execute unintended and unanticipated (by the application operator) actions on the database. In this example, the action is to remove the database table called "Students," thus removing all student information.<br />
<br />
The application server executes some code in response to receiving information submitted from a web form. I will show the example in Java, but similar code is written in other languages, including PHP, Perl, and .NET. The application sends a query to the database; in this example, it tries to get student information. The query is typically coded in SQL, and may have a form similar to this:<br />
<br />
<blockquote><span style="font-family: "Courier New", Courier, monospace;">SELECT * FROM Students WHERE NAME = '<em><span style="font-family: Times, "Times New Roman", serif;">name</span></em>'</span></blockquote>The name itself, shown above in italics, is of course different for each student; the value of this field is taken from the web form. The code that generates this query in Java looks like this:<br />
<blockquote><span style="font-family: "Courier New", Courier, monospace;">String query = "SELECT * FROM Students WHERE NAME = '" <span style="color: black;">+ request.getParameter("name") + "'";</span></span></blockquote>This builds the query string from three parts: two constant strings, and the call request.getParameter("name"), which returns the "name" field of the web form. Unfortunately, if you substitute little Bobby Tables' name into this computation, you will end up with the following SQL statement:<br />
<blockquote><span style="font-family: "Courier New", Courier, monospace;">SELECT * FROM Students WHERE NAME = '<span style="color: red;">Robert';</span></span><br />
<span style="font-family: "Courier New", Courier, monospace;"><span style="color: red;">DROP TABLE Students;</span></span><span style="font-family: "Courier New", Courier, monospace;"><br />
</span><span style="color: red;">--</span>'</blockquote><div></div>(Bobby's full name is shown in red; note that the final single quote comes from the second constant string in the original computation.) When this string is sent to the database for execution, it will be interpreted as three different commands, shown above on three separate lines. The first will indeed return the information about Bobby, but the second will remove the Students table. The third consists only of the three characters --' ; the first two dashes indicate that this is a comment and the rest of the line (the trailing quote) is to be ignored.<br />
<br />
This is not funny! All too many web applications are written in this way, and are therefore vulnerable to SQL injection attacks. In <a href="https://www.owasp.org/index.php/Top_10_2010-A1">OWASP's list of top 10 vulnerabilities</a>, injection vulnerabilities appear as the first item, tagged as being common, easy to exploit, and having severe impact.<br />
<br />
How can such problems be avoided? Obviously, any user-supplied information, including the contents of web forms, must be validated or sanitized. Validation means blocking any potentially-dangerous input (such as anything that includes quotes), while sanitation means modifying such inputs to a non-harmful form. This is easy enough to do; any reasonable web-development framework will supply appropriate validation and sanitization functions. However, the developer must remember to call these functions on each and every user input; any omission creates a security vulnerability, and a systematic attacker will discover it eventually.<br />
<br />
An alternative solution is to use <em>prepared statements</em> to communicate with the database. Java, like other server-side programming languages, offers more than one interface to the database. A prepared statement uses a fixed SQL statement, which includes question marks instead of actual parameter values. Bobby's example would look like this:<br />
<blockquote><span style="font-family: "Courier New", Courier, monospace;">SELECT * FROM Students WHERE NAME = ?</span></blockquote>When a prepared statement is used to invoke a database operation, all parameters identified by question marks are given their actual values by invoking type-specific methods (such as setString or setInt) on the prepared statement object. These take care of sanitization internally, so that the developer doesn't need to worry about it. A prepared statement object can therefore be used multiple times with the same SQL query but with different arguments. Another advantage of prepared statements it that the query string they receive must obey SQL syntax rules (with the addition of the question marks), and this can be checked when the prepared statement is initialized with the query, and the query can also be optimized once instead of having to be optimized for each call.<br />
<br />
However, there is a serious problem in the approach taken by all these languages that require the construction of SQL queries as strings. This gives too much freedom to the developer, allowing the creation of security and other errors that will not be discovered until the application is actually run. Certainly, if you use a statically-typed language like Java, you should also be able to express the syntax of your database queries in a way that can be checked for correctness at compile time rather than at runtime. This calls for a syntactic extension of the programming language, which will support SQL statements with parameter indicators such as the question marks of prepared statements. This will have the advantage of catching syntactic erros at compile time, as well as the possibility of adding sanitation automatically, as is done for prepared statements.<br />
<br />
Current web-development languages make it difficult for developers to do the right thing, necessitating special tools for discovering security vulnerabilities and fixing them. Why not provide the ability to prevent them in the first place?<br />
<br />
This is actually possible. In their paper "<span style="font-family: t1-gul-regular;"><span style="font-family: t1-gul-regular;">Simple and safe SQL queries with C++ templates</span></span>" (<span style="font-family: t1-gul-regular;"><span style="font-family: t1-gul-regular;">Science of Computer Programming 75 (2010)</span></span>), Joseph Gil and Keren Lenz describe a system that uses C++ template metaprobramming techniques to represent relational algebra expressions inside the C++ language. (Relational algebra is an alternative to SQL with a more mathematical syntax.) The compiler can check the expressions written this way for syntactic correctness, and when the SQL query is actually built for sending to the database, all string inputs are sanitized so that they can't modify the syntax and create injection attacks. Bobby's example can be written in this system this way:<br />
<blockquote><span style="font-family: "Courier New", Courier, monospace;">(Students / (NAME == name)).asSQL()</span></blockquote>The parenthesized expression is the relational-algebra form of the query, and the asSQL() method converts it to a string that can be sent to the database. This syntax uses C++ operator overloading, and is therefore inapplicable to Java and similar languages. It is possible to extend these with similar capabilities using more cumbersome syntax, but the right thing to do would be to make SQL (better yet, relational algebra) an integral part of the language. Anyone who has ambitions to develop the next server-side programming language should be aware of this research!Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com0tag:blogger.com,1999:blog-5536017433265189318.post-45635963741198731432011-05-30T12:50:00.000+03:002011-06-11T21:15:17.133+03:00The Weakest LinkThe May 2011 issue of <em>Communications of the ACM</em> contains an article called <a href="http://cacm.acm.org/magazines/2011/5/107701-weapons-of-mass-assignment/fulltext">Weapons of Mass Assignment</a> by Patrick McKenzie. The article describes McKenzie's security analysis of the pre-release source code of Diaspora, an attempt to build a "privacy-aware Facebook alternative". The <a href="https://joindiaspora.com/">Diaspora home page</a> makes the following claim: "Inherently private, Diaspora doesn’t make you wade through pages of settings and options just to keep your profile secure." Unfortunately, McKenzie was "struck by numerous severe security errors", which were "serious enough to jeopardize the goals of the project."<br />
<br />
The first kind of errors McKenzie reports are a result of confusion between authentication and authorization. Authentication means that the system has identified the user using some secure mechanism, so that nobody else can impersonate that user. Authorization, on the other hand, refers to the set of operations that a user can legally perform. Naturally, authorization is meaningless without authentication, since you can't refer to the operations a user is permitted to perform without authenticating that user. But authentication isn't enough; once you know who the user is, you should allow him to perform only operations he is authorized to perform.<br />
<br />
In the code release that McKenzie examined (the "pre-alpha developer review"), an authenticated user could delete photos based on their IDs. If you knew the ID of somebody else's photo, you could delete it, and discovering photo IDs was easy. Here is an example of a URL (from another source) that contains IDs: <a href="http://ark.intel.com/Product.aspx?id=52215&processor=i7-2600S&spec-codes=SR00E">http://ark.intel.com/Product.aspx?<strong>id=52215&processor=i7-2600S&spec-codes=SR00E</strong></a>. The part that follows the question mark (shown here in bold) contains a list of parameters and values, which the server-side script accesses to figure out what to do. When you see such URLs, you can often figure out what the IDs refer to, and you can replace IDs in them to create various effetcs. In Diaspora, for example, you could delete one of your own photos to see what that request URL was like, and then replace the photo ID to delete somebody else's photo.<br />
<br />
Diaspora uses Ruby on Rails, and suffers from the security vulnerabilities of that platform. In particular, McKenzie points to the Rails feature of "mass update", which is a convenient but dangerous programming tool. It takes a list of keys and associated values and calls the related accessor method for each key. This allows an attacker to add keys that the developer didn't intend to be modified, thus creating serious security vulnerabilities such as allowing one user to take over another's account. If mass update is used on values received from an HTML form (which is often the case), all an attacker needs to do is modify the form to send malicious key-value pairs. Because the form is presented on the attacker's machine, this is an easy task.<br />
<br />
McKenzie details several other vulnerabilities, which allow attackers to discover or replace another user's encryption key, thus allowing them to decipher all that user's previous and future communications with the server. This is quite serious in an application whose first priority was security and privacy. A chain is only as strong as its weakest link, and this applies first and foremost to security, where an attacker will deliberately go after the weakest link. The fact that Rails has mass update enabled by default should make you suspicious of any application built on Rails, since it requires positive action by security-conscious developers to disable mass update. The more issues developers need to be careful of, the greater the chance that they will miss some, creating security vulnerabilities. This makes me question whether Rails is a good tool for developing secure web applications (see <a href="http://the-dusty-deck.blogspot.com/2010/12/right-tool-for-job.html">The Right Tool for the Job</a>). This is unfortunate in tool whose main purpose is to make web development easy.<br />
<br />
It remains to be seen whether Diaspora will finally be secure. McKenzie ends his article on a positive note: "This is not a reason to despair, though: every error fixed or avoided through improved code, improved practices, and security reviews offers incremental safety to the users of software and increases its utility." I am less optimistic: an application that boasts its security needs to designed for security from the first, not debugged and reviewed to decrease its vulnerabilities after the fact.Yishai Feldmanhttp://www.blogger.com/profile/10970435788360319331noreply@blogger.com0