jugad2 - Vasudev Ram on software innovation: programming

Follow me on: LinkedIn * Twitter

Are you a blogger with some traffic? Get Convertkit:

Get fast web hosting with A2Hosting.com

Share |

Porting a prime checker from Q to Python (with improvements)

By Vasudev Ram

Q => Py

Hi readers,

I was checking out the Q programming language.

It's an interesting language, a descendant of APL, that supports array and functional programming styles. Some information about Q from its Wikipedia page:

Paradigm: Array, functional
Designed by: Arthur Whitney
Developer: Kx Systems
First appeared: 2003
Typing discipline: Dynamic, strong
Influenced by: A+, APL, Scheme, K

Q is a proprietary array processing language developed by Arthur Whitney and commercialized by Kx Systems. The language serves as the query language for kdb+, a disk based and in-memory, column-based database. kdb+ is based upon K, a terse variant of APL. Q is a thin wrapper around K, providing a more readable, English-like interface.

I had tried out Q a bit recently, using one of the tutorials.

Then, while reading the Q Wikipedia page again, I saw this paragraph:

[
When x is an integer greater than 2, the following function will return 1 if it is a prime, otherwise 0:

{min x mod 2_til x}
The function is evaluated from right to left:

"til x" enumerate the positive integers less than x.
"2_" drops the first two elements of the enumeration (0 and 1).
"x mod" performs modulo division between the original integer and each value in the truncated list.
"min" find the minimum value of the list of modulo result.
]

It's basically an algorithm in Q to find whether a given number x (> 2) is prime or not [1]. The algorithm returns 1 if x is a prime, else 0. Notice how concise it is. That conciseness is a property of the APL family of languages, such as APL, J and Q. In fact Q is slightly less concise than some of the others, I've read, because it puts a thin English-like wrapper on the hard-core APL symbolic syntax. But all of them are still very concise.

So I thought of implementing that algorithm in Python, just for fun. I first wrote a naive version, more or less a port of the Q version. Then I rewrote that first version in a more functional way. Then I realized that there are other opportunities for improving the code [2], and implemented a few of them.

So I combined the few different versions of the is_prime_* functions (where * = 1, 2, 3, etc.) that I had written, in a single program, with a driver function to exercise all of them. The code is in file is_prime.py, shown further below. There are comments in the program that explain the logic and improvements or differences of the various is_prime function versions.

[1] Prime_number

[2] There are obviously many other ways of checking if numbers are prime, and many of them are faster than these approaches; see [3]. These are not among the most efficient ways, or even close; I was just experimenting with different ways of rewriting and refactoring the code, after the initial port from Q to Python. Even the original Q version in the Wikipedia page was not meant to be a fast version, since it does not use any of the improvements I mention below, let alone using any special Q-specific algorithm or language feature, or advanced general prime-finding algorithms.

[3] Primality test

There might still be some scope for further changes or improvements, some of which I may do in a future post. A few such improvements are:

1. Don't divide x by all values up to x - 1. Instead, only check up to the square root of x. This is a standard improvement often taught to programming beginners; in fact, it is mentioned in the Wikipedia articles about primes.

2. Terminate early when the first remainder equal to 0 is found. This avoids unnecessarily computing all the other remainders. I did that in is_prime_3().

3. Don't check for divisibility by any even number > 2 (call it b), because if any such b divides x evenly, then so will 2, and we would have checked earlier if 2 divides x evenly.

4. Create a function for the output statements, most of which are common across the different is_prime versions, and call that function instead from those places.

5. Use a generator to lazily yield divisors, and when any divisor gives a zero remainder, exit early, since it means the number is not prime. Done in is_prime_4().

Other ways of doing it may include use of some other functional programming features of Python such as filter(), itertools.takewhile/dropwhile, etc. (The itertools module has many functions and is very interesting, but that is a subject for a different post.)

I also observed some interesting behavior when running the program with large ranges of inputs for prime number checking. Will analyze that a bit and write about my opinions on that in a future post.

Here is the code for is_prime.py:

# File: isprime.py
# A port of a primality checking algorithm from the Q language to Python, 
# plus a few improvements / variations, using Python features.
# Ref: https://en.wikipedia.org/wiki/Q_(programming_language_from_Kx_Systems)
# Search for the word "prime" in that page to see the Q code.

# Author: Vasudev Ram
# Copyright 2018 Vasudev Ram
# Web site: https://vasudevram.github.io
# Blog: https://jugad2.blogspot.com
# Product store: https://gumroad.com/vasudevram

from __future__ import print_function
from debug1 import debug1

import sys

# Naive, mostly procedural port from the Q version.
def is_prime_1(x):
    # Guard against invalid argument.
    assert x > 2, "in is_prime_1: x > 2 failed"
    # The range of integers from 0 to x - 1
    til_x = range(x)
    # The range without the first 2 items, 0 and 1.
    divs = til_x[2:]
    # The remainders after dividing x by each integer in divs.
    mods = map(lambda d: x % d, divs)
    # x is prime if the minimum-valued remainder equals 1.
    return min(mods) == 1

# Shorter, more functional version, with nested calls 
# to min, map and range.
def is_prime_2(x):
    assert x > 2, "in is_prime_2: x > 2 failed"
    # Eliminate slicing used in is_prime_1, just do range(2, x).
    return min(map(lambda d: x % d, range(2, x))) == 1

# Early-terminating version, when 1st remainder equal to 0 found, 
# using a list for the range of divisors.
def is_prime_3(x):
    assert x > 2, "in is_prime_3: x > 2 failed"
    divs = range(2, x)
    # Check if x is divisible by any integer in divs; if so, 
    # x is not prime, so terminate early.
    debug1("in is_prime_3, x", x)
    for div in divs:
        debug1("  in loop, div", div)
        if x % div == 0:
            return False
    # If we reach here, x was not divisible by any integer in 
    # 2 to x - 1, so x is prime.
    return True

# Generator function to yield the divisors one at a time, to 
# avoid creating the whole list of divisors up front.
def gen_range(start, x):
    assert start > 0, "in gen_range, start > 0 failed"
    assert x > start, "in gen_range, x > start failed"
    i = start
    while i < x:
        yield i
        i += 1

# Early-terminating version, when 1st remainder equal to 0 found, 
# using a generator for the range of divisors.
def is_prime_4(x):
    assert x > 2, "in is_prime_4, x > 2 failed"
    divs = gen_range(2, x)
    debug1("in is_prime_4, x", x)
    for div in divs:
        debug1("  in loop, div", div)
        if x % div == 0:
            return False
    return True

def check_primes(low, high):
    assert low <= high, "in check_primes, low <= high failed"

    """
    print("\nWith a for loop:")
    for x in range(low, high + 1):
        print(x, "is" if is_prime_1(x) else "is not", "prime,", end=" ")
    print()
    """

    print("\nWith nested function calls:")
    output = [ str(x) + (" prime" if is_prime_2(x) else " not prime") \
        for x in range(low, high + 1) ]
    print(", ".join(output))

    print("\nWith a list of divisors and early termination:")
    output = [ str(x) + (" prime" if is_prime_3(x) else " not prime") \
        for x in range(low, high + 1) ]
    print(", ".join(output))

    print("\nWith a generator of divisors and early termination:")
    output = [ str(x) + (" prime" if is_prime_4(x) else " not prime") \
        for x in range(low, high + 1) ]
    print(", ".join(output))

def main():
    try:
        low = int(sys.argv[1])
        high = int(sys.argv[2])
        if low <= 2:
            print("Error: Low value must be > 2.")
            sys.exit(1)
        if high < low:
            print("Error: High value must be >= low value.")
            sys.exit(1)
        print("Checking primality of integers between {} and {}".format(low, high))
        check_primes(low, high)
        sys.exit(0)
    except ValueError as ve:
        print("Caught ValueError: {}".format(str(ve)))
    except IndexError as ie:
        print("Caught IndexError: {}".format(str(ie)))
    sys.exit(1)

if __name__ == '__main__':
    main()

And here are some runs of the output, below, both for normal and error cases. Note that I used my debug1() debugging utility function in a few places, to show what divisors are being used, in a few places. This helps show that the early termination logic works. To turn off debugging output, simply use the -O option, like this example:

python -O is_prime.py other_args

This improved version of the debug1 function (get it here), unlike the earlier version that was shown in this blog post:

A simple Python debugging function

, does not require the user to set any environment variables like VR_DEBUG, since it uses Python's built-in __debug__ variable instead. So to enable debugging, nothing extra needs to be done, since that variable is set to True by default. To disable debugging, all we have to do is pass the -O option on the python command line.

Here is the prime program's output:

Try this one later (if you're trying out the program), since it takes 
longer to run. You may observe some interesting behavior:

$ python -O is_prime.py 3 10000 | less

where less is the Unix 'less' command, a text pager. Any command-line text pager 
that can read standard input (from a pipe) will work.

Try some of these below (both normal and error cases) before the one above:

Some error-handling cases:

$ python -O is_prime.py 0 0
Error: Low value must be > 2.

$ python -O is_prime.py 2 0
Error: Low value must be > 2.

$ python -O is_prime.py 3 0
Error: High value must be >= low value.

$ python -O is_prime.py 4 2
Error: High value must be >= low value.

Some normal cases:

$ python -O is_prime.py 3 3
Checking primality of integers between 3 and 3

With nested function calls:
3 prime

With a list of divisors and early termination:
3 prime

With a generator of divisors and early termination:
3 prime

To show that the early termination logic works, run the program without 
the -O option. 
Here is one such run. Due to more debugging output, I've only checked 
two numbers, 4 and 5. But you can try with any number of values if you 
page the output, or redirect it to a file.

$ python is_prime.py 4 5
Checking primality of integers between 4 and 5

With nested function calls:
4 not prime, 5 prime

With a list of divisors and early termination:
in is_prime_3, x: 4
  in loop, div: 2
in is_prime_3, x: 5
  in loop, div: 2
  in loop, div: 3
  in loop, div: 4
4 not prime, 5 prime

With a generator of divisors and early termination:
in is_prime_4, x: 4
  in loop, div: 2
in is_prime_4, x: 5
  in loop, div: 2
  in loop, div: 3
  in loop, div: 4
4 not prime, 5 prime

You can see from the above run that for 4, the checking stops early, 
at the first divisor (2), in fact, because it evenly divides 4.
But for 5, all divisors from 2 to 4 are checked, because 5 has 
no prime factors (except itself and 1).

And here is a run checking for primes between 3 and 30:

$ python -O is_prime.py 3 30
Checking primality of integers between 3 and 30

With nested function calls:
3 prime, 4 not prime, 5 prime, 6 not prime, 7 prime, 8 not prime, 9 not prime, 
10 not prime, 11 prime, 12 not prime, 13 prime, 14 not prime, 15 not prime, 
16 not prime, 17 prime, 18 not prime, 19 prime, 20 not prime, 21 not prime, 
22 not prime, 23 prime, 24 not prime, 25 not prime, 26 not prime, 27 not prime, 
28 not prime, 29 prime, 30 not prime

With a list of divisors and early termination:
3 prime, 4 not prime, 5 prime, 6 not prime, 7 prime, 8 not prime, 9 not prime, 
10 not prime, 11 prime, 12 not prime, 13 prime, 14 not prime, 15 not prime, 
16 not prime, 17 prime, 18 not prime, 19 prime, 20 not prime, 21 not prime, 
22 not prime, 23 prime, 24 not prime, 25 not prime, 26 not prime, 27 not prime, 
28 not prime, 29 prime, 30 not prime

With a generator of divisors and early termination:
3 prime, 4 not prime, 5 prime, 6 not prime, 7 prime, 8 not prime, 9 not prime, 
10 not prime, 11 prime, 12 not prime, 13 prime, 14 not prime, 15 not prime, 
16 not prime, 17 prime, 18 not prime, 19 prime, 20 not prime, 21 not prime, 
22 not prime, 23 prime, 24 not prime, 25 not prime, 26 not prime, 27 not prime, 
28 not prime, 29 prime, 30 not prime

You can see that all three functions (is_prime_2 to 4) give the same results. 
(I commented out the call to the naive function version, is_prime_1, after 
a few runs (not shown), so none of these outputs shows its results, but they 
are the same as the others, except for minor formatting differences, due to 
the slightly different output statements used.

I also timed the program for finding primes up to 1000 and 10,000 
(using my own simple command timing program written in Python - not shown).

Command: python -O is_prime.py 3 1000
Time taken: 2.79 seconds
Return code: 0

Command: python -O is_prime.py 3 10000
Time taken: 66.28 seconds
Return code: 0

Related links:

Q (programming_language from Kx_Systems

Kx Systems

Kdb+

Column-oriented DBMS

In-memory database

If you want to try out Q, Kx Systems a free version available for download for non-commercial use, here: Q downloads

Enjoy.

- Vasudev Ram - Online Python training and consulting

Get updates (via Gumroad) on my forthcoming apps and content.

Jump to posts: Python * DLang * xtopdf

Follow me on: LinkedIn * Twitter

Are you a blogger with some traffic? Get Convertkit:

- Vasudev Ram - Python, Unix and database training and consulting

Share |

Tuesday, May 2, 2017

Interesting tech links of the week

By Vasudev Ram

Talk Python to Me podcast: Episode #107: Python concurrency with Curio - David Beazley

Excerpt:

[ You've heard me go on and on about how Python 3.5's async and await features changed the game for asynchronous programming in Python, but what exactly does that mean? How does that look in the APIs? How does it work internally? Today I'm here with David Beazley (@dabeaz) who's been deeply exploring this space with his project Curio. And that's what this episode of Talk Python To Me is all about. It's episode 107 recorded April 14th 2017. ]

Programming as a Way of Thinking (scientificamerican.com)
HN thread about it

Why Use Postgres? (craigkerstiens.com)

There is no pass by reference in Go (cheney.net)

Building a QNX 7 Desktop (membarrier.wordpress.com)

Ask HN: What do you do while your code compiles?

Write Fast Apps Using Async Python 3.6 and Redis (paxos.com)

Understand Go pointers (cheney.net)

Software Developers after 40, 50 and 60 Who're Still Coding (belitsoft.com)

Ask HN: How did you acquire your first 100 users?

Ask HN: How did you grow from 100 to 1,000 users?

Six programming paradigms that will change how you think about coding

The Joy of Concatenative Languages Part 1

Get updates (via Gumroad) on my forthcoming apps and content.

Jump to posts: Python * DLang * xtopdf

Follow me on: LinkedIn * Twitter

Are you a blogger with some traffic? Get Convertkit:

Share |

Thursday, April 27, 2017

Using nested conditional expressions to classify characters

By Vasudev Ram

While writing some Python code, I happened to use a conditional expression, a Python language feature.

Conditional expressions are expressions (not statements) that have if/else clauses inside them, and they evaluate to either one of two values (in the basic case), depending on the value of a boolean condition. For example:

for n in range(4):
    print n, 'is odd' if n % 2 == 1 else 'is even'
0 is even
1 is odd
2 is even
3 is odd

Here, the conditional expression is this part of the print statement above:

'is odd' if n % 2 == 1 else 'is even'

This expression evaluates to 'is odd' if the condition after the if is True, and evaluates to 'is even' otherwise. So it evaluates to a string in either case, and that string gets printed (after the value of n).

Excerpt from the section about conditional expressions in the Python Language Reference:

[
conditional_expression ::= or_test ["if" or_test "else" expression]
expression ::= conditional_expression | lambda_expr

Conditional expressions (sometimes called a “ternary operator”) have the lowest priority of all Python operations.

The expression x if C else y first evaluates the condition, C (not x); if C is true, x is evaluated and its value is returned; otherwise, y is evaluated and its value is returned.
]

You can see that the definition of conditional_expression is recursive, since it is partly defined in terms of itself (via the definition of expression).

This implies that you can have recursive or nested conditional expressions.

Also, since the syntax of the Python return statement is:

return [ expression_list ]

(where expression_list means one or more expressions, separated by commas, it follows that we can use a nested conditional expression in a return statement (because a nested conditional expresssion is an expression).

Here is a small program to demonstrate that:

'''
File: return_with_nested_cond_exprs.py 
Purpose: Demonstrate nested conditional expressions used in a return statement, 
to classify letters in a string as lowercase, uppercase or neither.
Also demonstrates doing the same task without a function and a return, 
using a lambda and map instead.
Author: Vasudev Ram
Copyright 2017 Vasudev Ram
Web site: https://vasudevram.github.io
Blog: https://jugad2.blogspot.com
'''

from __future__ import print_function
from string import lowercase, uppercase

# Use return with nested conditional expressions inside a function, 
# to classify characters in a string as lowercase, uppercase or neither:
def classify_char(ch):
    return ch + ': ' + ('lowercase' if ch in lowercase else \
    'uppercase' if ch in uppercase else 'neither')

print("Classify using a function:")
for ch in 'AaBbCc12+-':
    print(classify_char(ch))

print()

# Do it using map and lambda instead of def and for:
print("Classify using map and lambda:")

print('\n'.join(map(lambda ch: ch + ': ' + ('lowercase' if ch in lowercase else 
'uppercase' if ch in uppercase else 'neither'), 'AaBbCc12+-')))

Running it with:

$ python return_with_nested_cond_exprs.py

gives this output:

Classify using a function:
A: uppercase
a: lowercase
B: uppercase
b: lowercase
C: uppercase
c: lowercase
1: neither
2: neither
+: neither
-: neither

Classify using map and lambda:
A: uppercase
a: lowercase
B: uppercase
b: lowercase
C: uppercase
c: lowercase
1: neither
2: neither
+: neither
-: neither

As you can see from the code and the output, I also used that same nested conditional expression in a lambda function, along with map, to do the same task in a more functional style
.

- Vasudev Ram - Online Python training and consulting

Get updates (via Gumroad) on my forthcoming apps and content.

Jump to posts: Python * DLang * xtopdf

Follow me on: LinkedIn * Twitter

Are you a blogger with some traffic? Get Convertkit:

Share |

Friday, April 21, 2017

Python callbacks using classes and methods

By Vasudev Ram

Hi readers,

I had written this post a few days ago:

Implementing and using callbacks in Python

In it, I had shown how to create simple callbacks using just plain Python functions, and said I would write a bit more about callbacks in my next post.

This is that next post. It discusses how to create callbacks in Python using classes and methods.

Here is an example program, callback_demo2.py, that shows how to do that:

'''
File: callback_demo2.py
To demonstrate implementation and use of callbacks in Python, 
using classes with methods as the callbacks.
Author: Vasudev Ram
Copyright 2017 Vasudev Ram
Web site: https://vasudevram.github.io
Blog: https://jugad2.blogspot.com
Product store: https://gumroad.com/vasudevram
'''

from __future__ import print_function
import sys
from time import sleep

class FileReporter(object):

    def __init__(self, filename):
        self._filename = filename
        try:
            self._fil = open(self._filename, "w")
        except IOError as ioe:
            sys.stderr.write("While opening {}, caught IOError: {}\n".format(
                self._filename, repr(ioe)))
            sys.exit(1)

    def report(self, message):
        self._fil.write(message)

class ScreenReporter(object):

    def __init__(self, dest):
        self._dest = dest

    def report(self, message):
        self._dest.write(message)

def square(i):
    return i * i

def cube(i):
    return i * i * i

def processor(process, times, report_interval, reporter):
    result = 0
    for i in range(1, times + 1):
        result += process(i)
        sleep(0.1)
        if i % report_interval == 0:
            # This is the call to the callback method 
            # that was passed to this function.
            reporter.report("Items processed: {}. Running result: {}.\n".format(i, result))

file_reporter = FileReporter("processor_report.txt")
processor(square, 20, 5, file_reporter)

stdout_reporter = ScreenReporter(sys.stdout)
processor(square, 20, 5, stdout_reporter)

stderr_reporter = ScreenReporter(sys.stderr)
processor(square, 20, 5, stderr_reporter)

I ran it with:

$ python callback_demo2.py >out 2>err

The above command creates 3 files, processor_report.txt, out and err.
Running fc /l on those 3 files, pairwise, shows that all three have the same content, but the output has gone to 3 different destinations (a specified file, standard output, and standard error output, based on which callback was passed to the processor function, in the 3 calls to it.

These two lines from the program:

file_reporter = FileReporter("processor_report.txt")
processor(square, 20, 5, file_reporter)

send output to the file processor_report.txt.

These two lines:

stdout_reporter = ScreenReporter(sys.stdout)
processor(square, 20, 5, stdout_reporter)

send output to the standard output (stdout), which is redirected to the file out.

These two lines:

stderr_reporter = ScreenReporter(sys.stderr)
processor(square, 20, 5, stderr_reporter)

send output to the standard error output (stderr), which is redirected to the file err.

The difference between this program (callback_demo2.py) and the one in the previous post (callback_demo.py), is that in this one, I pass an instance of some class to the processor function, as its last argument. This argument is the callback. And this time, rather than treating it as a function, processor treats it as an object, and invokes the report method on it, giving us much the same output as before (I just made minor cosmetic changes in the output). This same thing is done in all the 3 calls to processor. The difference is that different types of objects are passed each time, for the callback argument.

[ An interesting side note here is that in some other languages, for example, Java, at least in earlier Java versions (I'm not sure about recent ones), we cannot just pass different types of objects for the same callback parameter, unless they are all derived from some common base class (via inheritance). (Can it be done using Java interfaces? Need to check - been a while.) While that is also possible in Python, it is not necessary, as we see here, due to Python's more dynamic nature. Just passing any object that implements a report method is enough, as the program shows. The FileReporter and ScreenReporter classes do not (need to) descend from some common base class (other than object, but that is just the syntax for new-style classes; the object class not provide the report method). Python's smooth polymorphism, a.k.a. duck typing, takes care of it. ]

The first time, a FileReporter object is passed, so the output goes to a text file.

The second and third times, a ScreenReporter object is passed, initializing the _dest field to stdout and stderr respectively, so the output goes to those two destinations respectively. And the command line redirects those outputs to the files out and err.

Although I didn't say so in the previous post, the first argument to processor (square), is also a callback, since it, in turn, is called from processor, via the process parameter. So I can pass some other argument in place of it, like the cube function defined in the program, to get different computations done and hence different results.

Keen on creating and selling products online? Check out the free Product Creation Masterclass. It runs for about 4 weeks from 24 April 2017 (that's 3 days from now), with lots of emails, videos and expert interviews, all geared toward helping you create and sell your first product online. Check it out: The Product Creation Masterclass.

- Vasudev Ram - Online Python training and consulting

Get updates (via Gumroad) on my forthcoming apps and content.

Jump to posts: Python * DLang * xtopdf

Follow me on: LinkedIn * Twitter

Are you a blogger with some traffic? Get Convertkit:

- Vasudev Ram - Online Python training and consulting

Share |

Tuesday, April 18, 2017

Implementing and using callbacks in Python

By Vasudev Ram

Callbacks (or callback functions, as they are also called) are a useful and somewhat powerful programming technique. I first learned about the technique (in C) during a course on X-Windows , XLib and Motif, that I attended years ago.

Wikipedia article about callbacks.

( Also see this :)

In this post I'll show a simple way of implementing callbacks in Python. Due to Python's dynamic nature, it is quite easy to implement callbacks in it, more so than in some other languages, like C++ or Java. (But it's not difficult in those languages either.)

The program callback_demo.py (below) shows a simple way to implement and use callbacks, using just plain functions, i.e. no classes or anything more sophisticated are needed:

# File: callback_demo.py
# To demonstrate implementation and use of callbacks in Python, 
# using just plain functions.
# Author: Vasudev Ram
# Copyright 2017 Vasudev Ram
# Web site: https://vasudevram.github.io
# Blog: https://jugad2.blogspot.com
# Product store: https://gumroad.com/vasudevram

from __future__ import print_function
from time import sleep

def callback_a(i, result):
    print("Items processed: {}. Running result: {}.".format(i, result))

def square(i):
    return i * i

def processor(process, times, report_interval, callback):
    print("Entered processor(): times = {}, report_interval = {}, callback = {}".format(
    times, report_interval, callback.func_name))
    # Can also use callback.__name__ instead of callback.func_name in line above.
    result = 0
    print("Processing data ...")
    for i in range(1, times + 1):
        result += process(i)
        sleep(1)
        if i % report_interval == 0:
            # This is the call to the callback function 
            # that was passed to this function.
            callback(i, result)

processor(square, 20, 5, callback_a)

And here is the output when I run it:

$ python callback_demo.py
Entered processor(): times = 20, report_interval = 5, callback = callback_a
Processing data ...
Items processed: 5. Running result: 55.
Items processed: 10. Running result: 385.
Items processed: 15. Running result: 1240.
Items processed: 20. Running result: 2870.
$

The function callback_a (the last argument to the call to processor), gets substituted for the function parameter callback in the processor function definition. So callback_a gets called, and it reports the progress of the work being done. If we passed a different callback function instead of callback_a, we could get different behavior, e.g. progress report in a different format, or to a different destination, or something else, without changing the actual processor function. So this is a way of creating functions with low coupling, or putting it in other terms, creating functions (like processor) that have high cohesion.

Read up about coupling and cohesion.

Note that in the program, callback_demo.py, I've shown two ways of getting the name of a function, one being callback.func_name and the other being callback.__name__ (the latter in a comment). Both ways work. Also see this code snippet, which shows that if you define a function foo, it's func_name attribute is 'foo'; if you then assign foo to bar, bar's func_name attribute is still 'foo', not 'bar':

>>> def foo(): pass
...
>>> foo.__name__
'foo'
>>> bar = foo
>>>
>>> bar.__name__
'foo'
>>>
>>> foo.func_name
'foo'
>>> bar.func_name
'foo'

I'll talk a bit more about callbacks in my next post.

Enjoy.

Do you have the yen to create products? Check out the Product Creation Masterclass. (Not yen as in cash - the class is free.) It runs for about 4 weeks from 24 April 2017, with lots of emails and videos and interviews, all geared toward helping you create and sell your first product online. Check it out: The Product Creation Masterclass.

Get updates (via Gumroad) on my forthcoming apps and content.

Jump to posts: Python * DLang * xtopdf

Follow me on: LinkedIn * Twitter

Are you a blogger with some traffic? Get Convertkit:

Share |

Wednesday, April 12, 2017

Interesting programming links of the week

By Vasudev Ram

I've been seeing a good number of interesting posts about programming topics lately, on various forums, particularly HN, so I thought of sharing them here (both for my readers and for myself to look up again later). Here are some selected posts or threads that I think are interesting to programmers:

Electron is flash for the desktop (2016) (josephg.com)

Web Development in Go (inburke.com)

Ask HN: Will Rust ever become a mainstream systems programming language?

Computer Programming Using GNU Smalltalk (2009) (canol.info)

Ask HN: What would you use to make cross-platform desktop application?

The reference D compiler is now open source (dlang.org)

The Power of Prolog (metalevel.at)

I also commented on some of the threads.

Enjoy.

- Vasudev Ram - Online Python training and consulting

Get updates (via Gumroad) on my forthcoming apps and content.

Jump to posts: Python * DLang * xtopdf

Follow me on: LinkedIn * Twitter

Are you a blogger with some traffic? Get Convertkit:

Share |

Sunday, March 12, 2017

Find the number of bits needed to store an integer, and its binary representation (Python)

By Vasudev Ram

Hi readers,

I wrote this post yesterday:

Analyse this Python code snippet

I was initially going to give the solution (to the question asked in that post) today, but then realized that I posted it at the weekend. So, to give a bit of time for anyone to attempt it, including some of my programming students, I decided to post the solution early next week.

But in the meantime, inspired some Q&A in a class I taught, I had the idea of creating this simple program to find the the number of bits needed to represent integers of various sizes (0 to 256, specifically, though the code can easily be modified to do it for any size of int). Note that this is the calculation of the minimum number of bits needed to represent some integers per se, not necessarily the number of bits that Python or any other language actually uses to store those same integers, which can be more than the minimum. This is because, at least in the case of Python, being a dynamic language, most data types have more capabilities than just being data - e.g. ints in Python are objects, so they incur some overhead for being objects (instances of classes, such as having a dictionary of attributes, and so on). The other reason is that data objects in dynamic languages often take up extra pre-allocated space, to store some metadata or to allow for future expansion in the size of the value being stored - e.g. that may or not apply in the case of ints, but it can in the case of lists.

(See this earlier post by me: Exploring sizes of data types in Python for more on this topic.)

Note: the level of this post is targeted towards relative beginners to programming, who might not be too familiar with computer representation of numbers, or even towards somewhat experienced programmers, who are not familiar with that topic either (I've come across some). Believe it or not, I've come across people (ex-colleagues in some cases, as well as others, and developers as well as system administrators) who did not know that a compiled binary for one processor will usually not run on another type of processor [1], even though they may be running the same OS (such as Unix), because their (processor) instructions sets are different. (What's an instruction set? - some of them might ask.) This is like expecting a person who only knows language A to understand something spoken in language B - impossible, at least without some source of help, be it another person or a dictionary.

Having some knowledge in these areas (i.e. system internals or under-the-hood stuff, even at a basic level) is quite useful to have, and almost needed, for many real-life situations, ranging from things like choosing an appropriate data representation for your data, finding and fixing bugs quicker, system integration, data reading / writing / transformation / conversion, to bigger-picture issues like system performance and portability.

[1] Though there are exceptions to that these days, such as fat binaries.

Anyway, end of rant :)

I chose 256 as the upper limit because it is the size (+1) of the highest unsigned integer that can be stored in a single byte, and because values in the range 0 to 255 or 256 are very commonly used in low-level code, such as bit manipulation, assembly or machine language, C, some kinds of data processing (e.g. of many binary file formats), and so on. Of course values of word size (2 bytes / 16 bits) or double-word (4 bytes / 32 bits) are also often used in those areas, but the program can be modified to handle them too.

If you want to get a preview (and a clue) about what is coming up, check this snippet and its output first:

>>> for item in (0, 1, 2, 4, 8, 16):
...     print item.bit_length()
...
0
1
2
3
4
5

Hint: Notice that those are all powers of 2 in the tuple above, and correlate that fact with the output values.

Here is the program to find the number of bits needed to store an integer, and its binary representation (Python):

# int_bit_length_and_binary_repr.py
# Purpose: For integers from 0 to 256, print the number of 
# bits needed to represent them, and their values in binary.
# Author: Vasudev Ram
# Website: https://vasudevram.github.io
# Product store on Gumroad: https://gumroad.com/vasudevram
# Blog: https://jugad2.blogspot.com
# Twitter: @vasudevram

for an_int in range(0, 256 + 1):
    print an_int, "takes", an_int.bit_length(), "bits to represent,",
    print "and equals", bin(an_int), "in binary"

Before showing the output (because it is long, since I've shown all 257 rows of it:

If you found this post informative, you may also be interested in this earlier one on a related topic:

Converting numeric strings to integers with handrolled code

(I didn't remember to say it in that earlier post, but the image at the top of it is of a roti being rolled out with a rolling pin:)

And here is the output when I run the program:

$ python int_bit_length_and_binary_repr.py
0 takes 0 bits to represent, and equals 0b0 in binary
1 takes 1 bits to represent, and equals 0b1 in binary
2 takes 2 bits to represent, and equals 0b10 in binary
3 takes 2 bits to represent, and equals 0b11 in binary
4 takes 3 bits to represent, and equals 0b100 in binary
5 takes 3 bits to represent, and equals 0b101 in binary
6 takes 3 bits to represent, and equals 0b110 in binary
7 takes 3 bits to represent, and equals 0b111 in binary
8 takes 4 bits to represent, and equals 0b1000 in binary
9 takes 4 bits to represent, and equals 0b1001 in binary
10 takes 4 bits to represent, and equals 0b1010 in binary
11 takes 4 bits to represent, and equals 0b1011 in binary
12 takes 4 bits to represent, and equals 0b1100 in binary
13 takes 4 bits to represent, and equals 0b1101 in binary
14 takes 4 bits to represent, and equals 0b1110 in binary
15 takes 4 bits to represent, and equals 0b1111 in binary
16 takes 5 bits to represent, and equals 0b10000 in binary
17 takes 5 bits to represent, and equals 0b10001 in binary
18 takes 5 bits to represent, and equals 0b10010 in binary
19 takes 5 bits to represent, and equals 0b10011 in binary
20 takes 5 bits to represent, and equals 0b10100 in binary
21 takes 5 bits to represent, and equals 0b10101 in binary
22 takes 5 bits to represent, and equals 0b10110 in binary
23 takes 5 bits to represent, and equals 0b10111 in binary
24 takes 5 bits to represent, and equals 0b11000 in binary
25 takes 5 bits to represent, and equals 0b11001 in binary
26 takes 5 bits to represent, and equals 0b11010 in binary
27 takes 5 bits to represent, and equals 0b11011 in binary
28 takes 5 bits to represent, and equals 0b11100 in binary
29 takes 5 bits to represent, and equals 0b11101 in binary
30 takes 5 bits to represent, and equals 0b11110 in binary
31 takes 5 bits to represent, and equals 0b11111 in binary
32 takes 6 bits to represent, and equals 0b100000 in binary
33 takes 6 bits to represent, and equals 0b100001 in binary
34 takes 6 bits to represent, and equals 0b100010 in binary
35 takes 6 bits to represent, and equals 0b100011 in binary
36 takes 6 bits to represent, and equals 0b100100 in binary
37 takes 6 bits to represent, and equals 0b100101 in binary
38 takes 6 bits to represent, and equals 0b100110 in binary
39 takes 6 bits to represent, and equals 0b100111 in binary
40 takes 6 bits to represent, and equals 0b101000 in binary
41 takes 6 bits to represent, and equals 0b101001 in binary
42 takes 6 bits to represent, and equals 0b101010 in binary
43 takes 6 bits to represent, and equals 0b101011 in binary
44 takes 6 bits to represent, and equals 0b101100 in binary
45 takes 6 bits to represent, and equals 0b101101 in binary
46 takes 6 bits to represent, and equals 0b101110 in binary
47 takes 6 bits to represent, and equals 0b101111 in binary
48 takes 6 bits to represent, and equals 0b110000 in binary
49 takes 6 bits to represent, and equals 0b110001 in binary
50 takes 6 bits to represent, and equals 0b110010 in binary
51 takes 6 bits to represent, and equals 0b110011 in binary
52 takes 6 bits to represent, and equals 0b110100 in binary
53 takes 6 bits to represent, and equals 0b110101 in binary
54 takes 6 bits to represent, and equals 0b110110 in binary
55 takes 6 bits to represent, and equals 0b110111 in binary
56 takes 6 bits to represent, and equals 0b111000 in binary
57 takes 6 bits to represent, and equals 0b111001 in binary
58 takes 6 bits to represent, and equals 0b111010 in binary
59 takes 6 bits to represent, and equals 0b111011 in binary
60 takes 6 bits to represent, and equals 0b111100 in binary
61 takes 6 bits to represent, and equals 0b111101 in binary
62 takes 6 bits to represent, and equals 0b111110 in binary
63 takes 6 bits to represent, and equals 0b111111 in binary
64 takes 7 bits to represent, and equals 0b1000000 in binary
65 takes 7 bits to represent, and equals 0b1000001 in binary
66 takes 7 bits to represent, and equals 0b1000010 in binary
67 takes 7 bits to represent, and equals 0b1000011 in binary
68 takes 7 bits to represent, and equals 0b1000100 in binary
69 takes 7 bits to represent, and equals 0b1000101 in binary
70 takes 7 bits to represent, and equals 0b1000110 in binary
71 takes 7 bits to represent, and equals 0b1000111 in binary
72 takes 7 bits to represent, and equals 0b1001000 in binary
73 takes 7 bits to represent, and equals 0b1001001 in binary
74 takes 7 bits to represent, and equals 0b1001010 in binary
75 takes 7 bits to represent, and equals 0b1001011 in binary
76 takes 7 bits to represent, and equals 0b1001100 in binary
77 takes 7 bits to represent, and equals 0b1001101 in binary
78 takes 7 bits to represent, and equals 0b1001110 in binary
79 takes 7 bits to represent, and equals 0b1001111 in binary
80 takes 7 bits to represent, and equals 0b1010000 in binary
81 takes 7 bits to represent, and equals 0b1010001 in binary
82 takes 7 bits to represent, and equals 0b1010010 in binary
83 takes 7 bits to represent, and equals 0b1010011 in binary
84 takes 7 bits to represent, and equals 0b1010100 in binary
85 takes 7 bits to represent, and equals 0b1010101 in binary
86 takes 7 bits to represent, and equals 0b1010110 in binary
87 takes 7 bits to represent, and equals 0b1010111 in binary
88 takes 7 bits to represent, and equals 0b1011000 in binary
89 takes 7 bits to represent, and equals 0b1011001 in binary
90 takes 7 bits to represent, and equals 0b1011010 in binary
91 takes 7 bits to represent, and equals 0b1011011 in binary
92 takes 7 bits to represent, and equals 0b1011100 in binary
93 takes 7 bits to represent, and equals 0b1011101 in binary
94 takes 7 bits to represent, and equals 0b1011110 in binary
95 takes 7 bits to represent, and equals 0b1011111 in binary
96 takes 7 bits to represent, and equals 0b1100000 in binary
97 takes 7 bits to represent, and equals 0b1100001 in binary
98 takes 7 bits to represent, and equals 0b1100010 in binary
99 takes 7 bits to represent, and equals 0b1100011 in binary
100 takes 7 bits to represent, and equals 0b1100100 in binary
101 takes 7 bits to represent, and equals 0b1100101 in binary
102 takes 7 bits to represent, and equals 0b1100110 in binary
103 takes 7 bits to represent, and equals 0b1100111 in binary
104 takes 7 bits to represent, and equals 0b1101000 in binary
105 takes 7 bits to represent, and equals 0b1101001 in binary
106 takes 7 bits to represent, and equals 0b1101010 in binary
107 takes 7 bits to represent, and equals 0b1101011 in binary
108 takes 7 bits to represent, and equals 0b1101100 in binary
109 takes 7 bits to represent, and equals 0b1101101 in binary
110 takes 7 bits to represent, and equals 0b1101110 in binary
111 takes 7 bits to represent, and equals 0b1101111 in binary
112 takes 7 bits to represent, and equals 0b1110000 in binary
113 takes 7 bits to represent, and equals 0b1110001 in binary
114 takes 7 bits to represent, and equals 0b1110010 in binary
115 takes 7 bits to represent, and equals 0b1110011 in binary
116 takes 7 bits to represent, and equals 0b1110100 in binary
117 takes 7 bits to represent, and equals 0b1110101 in binary
118 takes 7 bits to represent, and equals 0b1110110 in binary
119 takes 7 bits to represent, and equals 0b1110111 in binary
120 takes 7 bits to represent, and equals 0b1111000 in binary
121 takes 7 bits to represent, and equals 0b1111001 in binary
122 takes 7 bits to represent, and equals 0b1111010 in binary
123 takes 7 bits to represent, and equals 0b1111011 in binary
124 takes 7 bits to represent, and equals 0b1111100 in binary
125 takes 7 bits to represent, and equals 0b1111101 in binary
126 takes 7 bits to represent, and equals 0b1111110 in binary
127 takes 7 bits to represent, and equals 0b1111111 in binary
128 takes 8 bits to represent, and equals 0b10000000 in binary
129 takes 8 bits to represent, and equals 0b10000001 in binary
130 takes 8 bits to represent, and equals 0b10000010 in binary
131 takes 8 bits to represent, and equals 0b10000011 in binary
132 takes 8 bits to represent, and equals 0b10000100 in binary
133 takes 8 bits to represent, and equals 0b10000101 in binary
134 takes 8 bits to represent, and equals 0b10000110 in binary
135 takes 8 bits to represent, and equals 0b10000111 in binary
136 takes 8 bits to represent, and equals 0b10001000 in binary
137 takes 8 bits to represent, and equals 0b10001001 in binary
138 takes 8 bits to represent, and equals 0b10001010 in binary
139 takes 8 bits to represent, and equals 0b10001011 in binary
140 takes 8 bits to represent, and equals 0b10001100 in binary
141 takes 8 bits to represent, and equals 0b10001101 in binary
142 takes 8 bits to represent, and equals 0b10001110 in binary
143 takes 8 bits to represent, and equals 0b10001111 in binary
144 takes 8 bits to represent, and equals 0b10010000 in binary
145 takes 8 bits to represent, and equals 0b10010001 in binary
146 takes 8 bits to represent, and equals 0b10010010 in binary
147 takes 8 bits to represent, and equals 0b10010011 in binary
148 takes 8 bits to represent, and equals 0b10010100 in binary
149 takes 8 bits to represent, and equals 0b10010101 in binary
150 takes 8 bits to represent, and equals 0b10010110 in binary
151 takes 8 bits to represent, and equals 0b10010111 in binary
152 takes 8 bits to represent, and equals 0b10011000 in binary
153 takes 8 bits to represent, and equals 0b10011001 in binary
154 takes 8 bits to represent, and equals 0b10011010 in binary
155 takes 8 bits to represent, and equals 0b10011011 in binary
156 takes 8 bits to represent, and equals 0b10011100 in binary
157 takes 8 bits to represent, and equals 0b10011101 in binary
158 takes 8 bits to represent, and equals 0b10011110 in binary
159 takes 8 bits to represent, and equals 0b10011111 in binary
160 takes 8 bits to represent, and equals 0b10100000 in binary
161 takes 8 bits to represent, and equals 0b10100001 in binary
162 takes 8 bits to represent, and equals 0b10100010 in binary
163 takes 8 bits to represent, and equals 0b10100011 in binary
164 takes 8 bits to represent, and equals 0b10100100 in binary
165 takes 8 bits to represent, and equals 0b10100101 in binary
166 takes 8 bits to represent, and equals 0b10100110 in binary
167 takes 8 bits to represent, and equals 0b10100111 in binary
168 takes 8 bits to represent, and equals 0b10101000 in binary
169 takes 8 bits to represent, and equals 0b10101001 in binary
170 takes 8 bits to represent, and equals 0b10101010 in binary
171 takes 8 bits to represent, and equals 0b10101011 in binary
172 takes 8 bits to represent, and equals 0b10101100 in binary
173 takes 8 bits to represent, and equals 0b10101101 in binary
174 takes 8 bits to represent, and equals 0b10101110 in binary
175 takes 8 bits to represent, and equals 0b10101111 in binary
176 takes 8 bits to represent, and equals 0b10110000 in binary
177 takes 8 bits to represent, and equals 0b10110001 in binary
178 takes 8 bits to represent, and equals 0b10110010 in binary
179 takes 8 bits to represent, and equals 0b10110011 in binary
180 takes 8 bits to represent, and equals 0b10110100 in binary
181 takes 8 bits to represent, and equals 0b10110101 in binary
182 takes 8 bits to represent, and equals 0b10110110 in binary
183 takes 8 bits to represent, and equals 0b10110111 in binary
184 takes 8 bits to represent, and equals 0b10111000 in binary
185 takes 8 bits to represent, and equals 0b10111001 in binary
186 takes 8 bits to represent, and equals 0b10111010 in binary
187 takes 8 bits to represent, and equals 0b10111011 in binary
188 takes 8 bits to represent, and equals 0b10111100 in binary
189 takes 8 bits to represent, and equals 0b10111101 in binary
190 takes 8 bits to represent, and equals 0b10111110 in binary
191 takes 8 bits to represent, and equals 0b10111111 in binary
192 takes 8 bits to represent, and equals 0b11000000 in binary
193 takes 8 bits to represent, and equals 0b11000001 in binary
194 takes 8 bits to represent, and equals 0b11000010 in binary
195 takes 8 bits to represent, and equals 0b11000011 in binary
196 takes 8 bits to represent, and equals 0b11000100 in binary
197 takes 8 bits to represent, and equals 0b11000101 in binary
198 takes 8 bits to represent, and equals 0b11000110 in binary
199 takes 8 bits to represent, and equals 0b11000111 in binary
200 takes 8 bits to represent, and equals 0b11001000 in binary
201 takes 8 bits to represent, and equals 0b11001001 in binary
202 takes 8 bits to represent, and equals 0b11001010 in binary
203 takes 8 bits to represent, and equals 0b11001011 in binary
204 takes 8 bits to represent, and equals 0b11001100 in binary
205 takes 8 bits to represent, and equals 0b11001101 in binary
206 takes 8 bits to represent, and equals 0b11001110 in binary
207 takes 8 bits to represent, and equals 0b11001111 in binary
208 takes 8 bits to represent, and equals 0b11010000 in binary
209 takes 8 bits to represent, and equals 0b11010001 in binary
210 takes 8 bits to represent, and equals 0b11010010 in binary
211 takes 8 bits to represent, and equals 0b11010011 in binary
212 takes 8 bits to represent, and equals 0b11010100 in binary
213 takes 8 bits to represent, and equals 0b11010101 in binary
214 takes 8 bits to represent, and equals 0b11010110 in binary
215 takes 8 bits to represent, and equals 0b11010111 in binary
216 takes 8 bits to represent, and equals 0b11011000 in binary
217 takes 8 bits to represent, and equals 0b11011001 in binary
218 takes 8 bits to represent, and equals 0b11011010 in binary
219 takes 8 bits to represent, and equals 0b11011011 in binary
220 takes 8 bits to represent, and equals 0b11011100 in binary
221 takes 8 bits to represent, and equals 0b11011101 in binary
222 takes 8 bits to represent, and equals 0b11011110 in binary
223 takes 8 bits to represent, and equals 0b11011111 in binary
224 takes 8 bits to represent, and equals 0b11100000 in binary
225 takes 8 bits to represent, and equals 0b11100001 in binary
226 takes 8 bits to represent, and equals 0b11100010 in binary
227 takes 8 bits to represent, and equals 0b11100011 in binary
228 takes 8 bits to represent, and equals 0b11100100 in binary
229 takes 8 bits to represent, and equals 0b11100101 in binary
230 takes 8 bits to represent, and equals 0b11100110 in binary
231 takes 8 bits to represent, and equals 0b11100111 in binary
232 takes 8 bits to represent, and equals 0b11101000 in binary
233 takes 8 bits to represent, and equals 0b11101001 in binary
234 takes 8 bits to represent, and equals 0b11101010 in binary
235 takes 8 bits to represent, and equals 0b11101011 in binary
236 takes 8 bits to represent, and equals 0b11101100 in binary
237 takes 8 bits to represent, and equals 0b11101101 in binary
238 takes 8 bits to represent, and equals 0b11101110 in binary
239 takes 8 bits to represent, and equals 0b11101111 in binary
240 takes 8 bits to represent, and equals 0b11110000 in binary
241 takes 8 bits to represent, and equals 0b11110001 in binary
242 takes 8 bits to represent, and equals 0b11110010 in binary
243 takes 8 bits to represent, and equals 0b11110011 in binary
244 takes 8 bits to represent, and equals 0b11110100 in binary
245 takes 8 bits to represent, and equals 0b11110101 in binary
246 takes 8 bits to represent, and equals 0b11110110 in binary
247 takes 8 bits to represent, and equals 0b11110111 in binary
248 takes 8 bits to represent, and equals 0b11111000 in binary
249 takes 8 bits to represent, and equals 0b11111001 in binary
250 takes 8 bits to represent, and equals 0b11111010 in binary
251 takes 8 bits to represent, and equals 0b11111011 in binary
252 takes 8 bits to represent, and equals 0b11111100 in binary
253 takes 8 bits to represent, and equals 0b11111101 in binary
254 takes 8 bits to represent, and equals 0b11111110 in binary
255 takes 8 bits to represent, and equals 0b11111111 in binary
256 takes 9 bits to represent, and equals 0b100000000 in binary

If you look carefully at the values in the output, you can notice some interesting bit patterns, e.g.:

1. Look at the bit patterns for the values of (2 ** n) - 1, i.e. values one less than each power of 2.
2. The same for the values halfway between any two adjacent powers of 2.

Notice any patterns or regularities?

The number columns in the output should really be right-justified, and the repeated (and hence redundant) text in between numbers in the rows should be replaced by a header line at the top, but this time, I've leaving this as an elementary exercise for the reader :)

Enjoy.

- Vasudev Ram - Online Python training and consulting

Get updates (via Gumroad) on my forthcoming apps and content.

Jump to posts: Python * DLang * xtopdf

Follow me on: LinkedIn * Twitter

Are you a blogger with some traffic? Get Convertkit: