Thursday, October 22, 2015

Cryptic Reeborg

Like many people, one of the main reasons I like Python so much is that Python programs are usually very readable ... at least for people that can read and understand English.   This post is definitely not about making Python programs readable in the usual sense.

I like to think of Reeborg's World as a learning environment not only for beginners, but also as a fun and visual place to experiment with various Python features.  For example, is it possible to give a different and interesting introduction to Python's "magic" methods within Reeborg's World?  By this, I mean to replace the usual English names for methods by symbols.  Here's one such quick attempt that may find its way into my Python tutorial.

Reeborg likes to collect objects.  He can add (+) an object found in his world to his collection, or leave an object behind, by removing an object from his collection (-).

Reeborg's favourite objects are (smilie face) tokens: These can be represented in a program by ":-)"  [I would have like to be able to use the unicode character but it is not a valid Python identifier.]

Reeborg can move forward (>) a set number of steps (> n); he can turn perpendicular to his direction of motion (^)  either to his left (^ left) or to his right (^ right).  Reeborg can also "invert" his position and turn around (~reeborg).

Reeborg can detect if there is a wall (|) immediately in front of him (| front) or to his right (| right); he can also build a wall if needed (| build).

Reeborg can detect if he has reached a goal (>> goal) or if he has reached a point where there is a wall in front of him (>> wall) or where there is an object [for instance, a token: >> ":-)"].    Here I would have preferred to use the __matmul__ symbol @ [as in @ goal], but it is not (yet) supported by Brython.  When @ becomes supported, I may use >> as a "fast forward" indicator to vary the speed of the display update [thus >> 100  could be equivalent to think(100)].

Here's a quick implementation of the above, followed by two animated gifs illustrating the result in action.

RUR.world.__remove_default_robot()

build = "build"
front = "front"
right = "right"
left = "left"
token = ":-)"
wall = "wall"
goal = "goal"


class Cryptic(UsedRobot):
    
    def __add__(self, obj):
        if obj == token:
            self.take("token")
        else:
            self.take(obj)    
            
    def __sub__(self, obj):
        if obj == token:
            self.put("token")
        else:
            self.put(obj)
    
    def __gt__(self, n):
        for _ in range(n):
            self.move()
    
    def __or__(self, wall):
        if wall == front:
            return self.wall_in_front()
        elif wall == right:
            return self.wall_on_right()
        elif wall == build:
            self.build_wall()
        else:
            raise ReeborgError("Unknown wall action")
            
    def __rshift__(self, obj):
        while self.front_is_clear():
            self.move()
            
    def __xor__(self, direction):
        if direction == left:
            self.turn_left()
        elif direction == right:
            for _ in range(3):
                self.turn_left()
                
    def __rshift__(self, obj):
        if obj == token:
            return self.object_here()
        if obj == goal:
            return self.at_goal()
    def __invert__(self):
        self.turn_left()
        self.turn_left()

reeborg = Cryptic(1, 1)




 [Note that turn_right() and turn_around() shown as comments on the image below must be defined by the student since Reeborg only knows turn_left().]




Wednesday, October 14, 2015

from __experimental__ import something_new : running scripts from the command line.

EDIT: I just found out that the notation "from __experimental__ import" had already been suggested in a different context than the one I have been working on.   Perhaps I should use "__nonstandard__" instead of "__experimental__" to avoid any confusion.



In a post I wrote yesterday, I mentioned a way to run "experimental" code containing non-standard Python syntax (e.g. new keywords, not recognized by Python's interpreter) by using an "import hook" to convert the code into a proper Python syntax prior to executing it.   One caveat of the approach I used was that it only worked if the "experimental" code was imported.  This restriction is also present in the MacroPy project (which is something I stumbled upon and is definitely a much more substantial project than the little toy I created.)

Today, I have a new version that can effectively be run from the command line.  (I believe that the approach I use could also work for the MacroPy project).  This is version 4 found in this github repository.

I will start with a concrete example taken from the repository (file test.py); the code below contains keywords and constructs that are definitely not valid in Python.


'''This is not a valid Python module as it contains two
   non-standard keywords:  repeat and function.  However,
   by using a custom importer, and the presence of the special
   import line below, these non-standard keywords will be converted
   into valid Python syntax prior to execution.
'''
from __experimental__ import repeat_keyword, function_keyword  # magic! :-)


def normal_syntax():
    '''Creates the list [4, 4, 4] by using the normal Python syntax,
       with a for loop and a lambda-defined function.
    '''
    res = []
    g = lambda x: x**2
    for _ in range(3):
        res.append(g(2))
    return res


def experimental_syntax():
    '''Creates the list [4, 4, 4] by using an experimental syntax
       with the keywords "repeat" and "function", otherwise
       using the same algorithm as the function called "normal_syntax".
    '''
    res = []
    g = function x: x**2
    repeat 3:
        res.append(g(2))
    return res


if __name__ == '__main__':
    if normal_syntax() == experimental_syntax():
        print("Success")
    else:
        print("Failure")

If you try to run this program from the command line using "python test.py" at your command/shell prompt ... it will definitely fail.  However, using the code from the repository, you can run it via "python import_experimental.py test".  The code inside import_experimental.py, which has many more comments than I would normally write, is the following:

''' A custom Importer making use of the import hook capability

https://www.python.org/dev/peps/pep-0302/

Its purpose is to convert would-be Python module that use non-standard
syntax into a correct form prior to importing them.
'''

# imp is deprecated but I wasn't (yet) able to figure out how to use
# its replacement, importlib, to accomplish all that is needed here.
import imp
import re
import sys

MAIN = False
from_experimental = re.compile("(^from\s+__experimental__\s+import\s+)")


class ExperimentalImporter(object):
    '''According to PEP 302, an importer only requires two methods:
       find_module and load_module.
    '''

    def find_module(self, name, path=None):
        '''We don't need anything special here, so we just use the standard
           module finder which, if successful,
           returns a 3-element tuple (file, pathname, description).
           See https://docs.python.org/3/library/imp.html for details
        '''
        self.module_info = imp.find_module(name)
        return self

    def load_module(self, name):
        '''Load a module, given information returned by find_module().
        '''

        # According to PEP 302, the following is required
        # if reload() is to work properly
        if name in sys.modules:
            return sys.modules[name]

        path = self.module_info[1]  # see find_module docstring above
        module = None

        if path is not None:   # path=None is the case for some stdlib modules
            with open(path) as source_file:
                module = self.convert_experimental(name, source_file.read())

        if module is None:
            module = imp.load_module(name, *self.module_info)
        return module

    def convert_experimental(self, name, source):
        '''Used to convert the source code, and create a new module
           if one of the lines is of the form

               ^from __experimental__ import converter1 [, converter2, ...]

           (where ^ indicates the beginning of a line)
           otherwise returns None and lets the normal import take place.
           Note that this special code must be all on one physical line --
           no continuation allowed by using parentheses or the
           special \ end of line character.

           "converters" are modules which must contain a function

               transform_source_code(source)

           which returns a tranformed source.
        '''
        global MAIN
        lines = source.split('\n')

        for linenumber, line in enumerate(lines):
            if from_experimental.match(line):
                break
        else:
            return None  # normal importer will handle this

        # we started with: "from __experimental__ import converter1 [,...]"
        line = from_experimental.sub(' ', line)
        # we now have: "converter1 [,...]"
        line = line.split("#")[0]    # remove any end of line comments
        converters = line.replace(' ', '').split(',')
        # and now:  ["converter1", ...]

        # drop the "fake" import from the source code
        del lines[linenumber]
        source = '\n'.join(lines)

        for converter in converters:
            mod_name = __import__(converter)
            source = mod_name.transform_source_code(source)

        module = imp.new_module(name)
        # From PEP 302:  Note that the module object must be in sys.modules
        # before the loader executes the module code.
        # This is crucial because the module code may
        # (directly or indirectly) import itself;
        # adding it to sys.modules beforehand prevents unbounded
        # recursion in the worst case and multiple loading in the best.
        sys.modules[name] = module

        if MAIN:  # see below
            module.__name__ = "__main__"
            MAIN = False
        exec(source, module.__dict__)

        return module


sys.meta_path = [ExperimentalImporter()]

if __name__ == '__main__':
    if len(sys.argv) >= 1:
        # this program was started by
        # $ python import_experimental.py some_script
        # and we will want some_script.__name__ == "__main__"
        MAIN = True
        __import__(sys.argv[1])

One could easily write a shell script/bat file which would simplify execution to something like "my_python test"

It would be nice to remove the "imp" dependency and use the proper functions/methods from the importlib module, something which I have not been able to figure out (yet).  Anyone familiar with the importlib module is more than welcome to do it and tell me about it. ;-)

Also, writing more useful code converters than the two toy ones I created would likely be an interesting project.

from __experimental__ import something_new

Python programmers are used to the notation:

from __future__ import new_functionality

which allows to experiment with changes that are to become part of a future Python version.  These are hard-coded in the Python interpreter and cannot be created at will by an average Python programmer.   Wouldn't it be nice if there was a simple way to try out possible new syntax by an average Python programmer?   This blog post describes a way to do this, with  a link to working code.  The code is not very sophisticated: firstly, I am not a professional programmer and have no training in computer science; as a result, all I do is simple stuff.  Secondly, I wrote the bulk of the code in a single day (ending with this blog post); I am sure it could be greatly improved upon.

However, like I say to beginners on various forums: the important thing is to first make your program do what you want it to.

Before I discuss the details of the code, I am going to make a rather long digression to explain my original motivation and what I found along the way.

Something special about Pattis's Karel the Robot


Anyone that has read more than a few posts on this blog is likely familiar with my Python implementations of Karel the Robot:  a desktop version, named RUR-PLE, and a more modern and sophisticated web version, Reeborg's World.  In what follows, I will give examples using code that could be readily executed in Reeborg's World.  These are extremely simple ... but I give them to illustrate a very important point about what motivated me.

Reeborg is a faulty robot.  It can move forward and turn left (by 90 degrees) as follows:

move()
turn_left()

However, it cannot turn right directly.  Nonetheless, one can define a new function to make it turn right by doing three consecutive left turns:

def turn_right():
    turn_left()
    turn_left()
    turn_left()

Reeborg (like the original Karel) can make single decisions based on what it senses about its environment
if wall_in_front():
    turn_left()
else:
     move()
or it can make repeated decisions in a similar way:
while not wall_in_front():
    move()
Using simple commands and conditions, beginners can learn the basics of programming using such an environment.   Notice something important in the above code samples: no variables are used and there are no function arguments.

What if we wanted Reeborg to draw a square?   If I were to use Guido van Robot,  Python-like implementation, I would write the following
do 4:
    move
    turnleft

Once again, no variable nor any function arguments.    However, if I wanted to do the same thing in Reeborg's World, at least up until a few days ago days ago, I would have needed to write:

for var in range(4):
    move()
    turn_left()

So much for the idea of not having variables nor function arguments ....    I've always hated the "don't worry about it now" kind of statements made to students.  However, the alternative is to explain a rather complicated expression (for beginners at this stage, especially young children who have never seen algebra and the idea of a variable) ... Wouldn't it be nice if
one could write instead:

repeat 4:
    move()
    turn_left()

or, if one does not want to introduce a new keyword, write

for 4:
    move()
    turn_left()

and have Python recognize it as having the same meaning?...  So, I subscribed to the python-ideas list and made this suggestion.   The result was more or less what I was expected...  And, to be honest, I completely understand the reluctance to introduce such a change.  While I expected a lack of support for this suggestion, (and, to be honest, I wasn't myself convinced that it fitted entirely Python's design philosophy) I wasn't expecting the amount of heat it would generate ... However, a couple of people with experience teaching to young children were sympathetic, including Luciano Ramalho.  Terry Jan Reedy, who thought I was using IDLE, suggested that I just patch it and transform the code prior to execution. Since I was already transforming the code prior to execution to support line highlighting in Reeborg's World, it was rather trivial to add yet one more code transformation to support the "repeat" keyword as illustrated above.

So, I have a way to support a "repeat" keyword in Reeborg's World ... but it left me somewhat unsatisfied to have something like this not easily available elsewhere in the Python world.


Additional motivation


In one of his posts to python-ideas, Terry Jan Reddy mentioned a discussion on the idle-dev list about making idle friendlier to beginners. In one of his post, he mentioned the idea of having non-English keywords. This idea is not new. There already exists an unmaintained version with Chinese Keywords as well as a Lithuanian and Russion version. Maintaining a version based on a different language for keywords is surely not something simple ... nor I think it would be desirable. However, it might be possible to essentially achieve the same goal by using an approach I describe in the next section.

Even just adding new keywords can be quite difficult. For example, in this post, Eli Bendersky explains how one can add a new keyword to Python. "All" you ned to do is

  1. Modify the grammar to add the new keyword
  2. Modify the AST generation code; this requires a knowledge of C
  3. Compile the AST into bytecode
  4. Recompile the modified Python interpreter
Not exactly for the faint of heart...

A simpler way...


Using the unmodified standard Python interpreter, I have written some proof-of-concept code which works when importing modules that satisfy certain conditions. For example, if an imported module
contains as its first line
for __experimental__ import repeat_keyword

it will support constructs like

repeat 4:
    move()
    turn_left()

If instead, it has

from __experimental__ import function_keyword

then one will be able to write "function" instead of "lambda" (which has been identified as one of Python's warts by a few people including Raymond Hettinger.)
One can combine two transformations as follows:


from __experimental__ import repeat_keyword, function_keyword


def experimental_syntax():
    res = []
    g = function x: x**2
    repeat 3:
        res.append(g(2))
    return res


def normal_syntax():
    res = []
    g = lambda x: x**2
    for i in range(3):
        res.append(g(2))
    return res

and both functions will have exactly the same meaning.   One caveat: this works only when a module is imported.

How does it work?


Each code transformer, such as repeat_keyword.py and function_keyword.py, contains a function named "transform_source_code"; this function takes an existing source code as input and returns a modified version of that code.  These transformations can thus be chained easily, where the
output from one transformation is taken as the input from another.

The transformation happens when a module is imported using an import statement; this is an unfortunate limitation as one can not execute

python non_standard_module.py

from the command line and expect "non_standard_module.py" to be converted.

The magic occurs via an import hook.  The code I have written uses the deprecated imp module.  I have tried to figure out how to use the importlib module to accomplish the same thing ... but I failed. I would be greatful to anyone who could provide help with this.

Other potential uses

In addition to changing the syntax slightly to make it easier to (young) beginners, or to make it easier to understand to non-English speaker especially if they use a different character set, more experienced programmers might find this type of code transformation potentially useful.

When PEPs are written, they often contain small sample codes.  When I read PEPs which are under discussion, I often wish I could try out to write and modify such code samples to see how they work. While not all proposed code could be made to work using the approach I have described, it might be possible in many cases.  As an example, PEP 0465 -- A dedicated infix operator for matrix multiplication could almost certainly have been implemented as a proof-of-concept using the approach I used.  I suspect that the existence of the appropriate code converter would often enrich the discussions about proposed changes to Python, and allow for a better evaluation of different alternatives.

A suggestion to come?...

I'm not ready yet to bring another suggestion to the python-ideas list ... However ...

Python support the special "from __future__ import ..." construct to determine how it will interpret the rest of the code in that file.  I think it would be useful if a similar kind of statement "from __experimental import ..." would also benefit from the same kind of special treatment so that it
would work in all instances, and not only when a module is imported.   People could then share (and install via pip) special code importers and know that they would work in all situations, and not limited to special environments like Reeborg's World, or IDLE as suggested by T.J. Reddy and likely others.

However, a concrete suggestions along these lines will have to wait for another day...