A Practical Introduction to Pyth, Part 1

Today, I executed the following piece of Python code:

assign('Q',eval(input()))
@memoized
def subsets(b):
 return neg([times(Plen(b),assign("J",reduce2(lambda b, Z:times(b,Z),end(Pchr(b))))),Psum(Pmap(lambda d:times(head(d),div(J,end(d))),b))])
@memoized
def gte(G,H):
 return ((subsets(Pmap(lambda d:gte(tail(G),minus(assign_at(d,assign("K",H),neg(1)),neg(Pnot(d)))),Plen(H))) if G else [0,1]) if (head(H) and Psum(tail(H))) else [T,T])
imp_print(reduce2(lambda b, Z:chop(b,Z),gte(head(Q),Psum(tail(Q)))))

This corresponds to the following Pyth code:

L_,*lbJ*FeCbsm*hd/JedbM?&hHstH?GymgtG-XdKH_1_!dlH,01,TTcFghQstQ

Pyth is a programming language which I created, and is deisgned for writing short programs. This program is a solution to the following challenge: http://codegolf.stackexchange.com/questions/53688/probability-to-clear-the-board-or-win

The challenge involves simulating a fairly simple game, and reporting the exact probability of victory. You can read about it at the link.

I'll be explaining exactly how the above Pyth code works, over the coming days.

Part 1: Prefix notation

Let's focus in on the following segment of the code:

*FeCb

The first thing to know about Pyth is that it uses Prefix Notation, also known as Polish Notation. This means 2 things:

1. A function comes before its arguments.
2. Function take a fixed number of arguments, known as their arity.

Because of the prefix notation, it makes the most sense to look at a piece of Pyth code from end to start.

Let's start with b. b is a variable, which functions are being called on. At this point in the code, b is a list of 2 element lists. Each sublist is representing a rational number, and this code is calculating the product of their denominators, or in other words the product of the second elements of each list. Let's suppose the following is the value of b:

[[3, 4], [10, 10], [0, 5]]

Next in the order from right to left is C. C takes one argument, and has a variety of uses, depending on the type of its argument. Since its argument, b, is a list, C performs a matrix transpose operation, making the first element of every list into a single list, then the second, and the third, and so on. Thus, in the example, Cb is the following:

[[3, 10, 0], [4, 10, 5]]

Next to the left is e. e also takes one argument, and its operation also depends on its argument. In fact, most functions in Pyth have different properties based on their arguments' types. e when called on a list returns the last element, making e the end function. Thus, eCb is:

[4, 10, 5]

Now comes something a bit unusual. This first two characters in the code snippet, *F, must be thought of as a unit. * is an arity two function which, as you might expect, multiplies its arguments together. F has a variety of uses, but when it appears immediately after an arity two function is the fold operator. It effectively "folds" the function just prior to it in between the consequtive elements of the sequence following it. You can learn more about folds at Wikipedia.

The result is equivalent to doing the following in an ordinary programming language:

4 * 10 * 5

Giving a result of 200, which is the product of the denominators, as desired.

Those 5 characters of Pyth code were compiled into the Python:

reduce2(lambda b, Z:times(b,Z),end(Pchr(b))

Well, we're 5 characters in, only 56 to go. More to come next time.