Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to understand the functional programming code for converting IP string to an integer?

In a python discusion, I saw a function to convert IP string into an integer in functional progamming way. Here is the Link .

The function is implemented in a single line.

def ipnumber(ip):
    return reduce(lambda sum, chunk: sum <<8 | chunk, map(int, ip.split(".")))

However, I have few ideas of funcional programming. Could anybody explain the function in detail? I've some knowledge of "map" and "reduce". But I don't konw what "|" and "chunk" mean here.

Thanks.

like image 793
zfz Avatar asked Oct 31 '12 10:10

zfz


2 Answers

sum and chunk are arguments to the lambda function passed to reduce. | is the binary or operator.

The thing works like this:

  • ip.split(".") returns a list of strings, each corresponding to a piece of the dotted string ("192.168.0.1" => ["192", "168", "0", "1"];

  • map applies its first operand to each element of its second operand (["192", "168", "0", "1"] => [192, 168, 0, 1]);

  • reduce takes the first two arguments from the list and applies the lambda to them; then it does this again with the result of the lambda and the next element of the list; and so on.

  • the labmda function (an anonymous function defined on the spot) does this: takes the first argument, shifts it by eight bits and ORs to it the new chunk; thus, what happens is that the result is computed like:

    (((192<<8 | 168) << 8 | 0)<<8 | 1) = 192<<24 | 168<<16 | 0<<8 | 1
    

    which is exactly what the "dotted form" represents (it's just a shorthand to indicate a 32 bit unsigned integer, which is what an IP is in IPv4 - you could say it's a bit like expressing it in base 256)

like image 165
Matteo Italia Avatar answered Oct 20 '22 04:10

Matteo Italia


| is a bitwise, logical or:

>>> 0 | 1
1
>>> 1 | 1
1

Reduce calls the lambda with the current running total and the next (integer) value of the output of the map() function. So, it is doing the following in a loop:

sum = 0
for chunk in map(int, ip.split(".")):
    sum = (sum << 8) | chunk

where map(int, ip.split(".")) turned the IP address into a sequence of integers; 1.2.3.4 becomes [1, 2, 3, 4].

The << is a bitwise left shift, by 8 bits in this case:

>>> 1 << 8
256

So, for each integer part of an ip address, it shifts the value to the left by 8 positions, and adds the bits of the next part of the address to that number.

This makes perfect sense, since an IP address is nothing but a 32-bit number, and the string notation divides that number up into 4 chunks of 8 bits, and 'prints' the integer value of each of those 8 bits with a . character in between.

It helps to print each stage as a binary number:

>>> map(int, '1.2.3.4'.split('.'))
[1, 2, 3, 4]
>>> bin(1)
'0b1'
>>> bin(2)
'0b10'
>>> bin(3)
'0b11'
>>> bin(4)
'0b100'
>>> bin(1 << 8)
'0b100000000'
>>> bin(1 << 8 | 2)
'0b100000010'
>>> bin((1 << 8 | 2) << 8)
'0b10000001000000000'
>>> bin((1 << 8 | 2) << 8 | 3)
'0b10000001000000011'
>>> bin(((1 << 8 | 2) << 8 | 3) << 8)
'0b1000000100000001100000000'
>>> bin(((1 << 8 | 2) << 8 | 3) << 8 | 4)
'0b1000000100000001100000100'
like image 40
Martijn Pieters Avatar answered Oct 20 '22 03:10

Martijn Pieters