Functions (draft)

Functional Programming in Pip

Although Pip is an imperative language, it also borrows some ideas from functional programming. Functions in Pip are first-class objects; they can be assigned to variables, used in expressions, and placed in lists. Pip has a set of operators that apply functions in various ways; often, such a functional approach to a problem is more concise than the equivalent imperative approach.

Defining and Calling Functions

A function can be defined by enclosing any number of statements in curly braces. For example, {Fi,5Pi"abc"} is a function that prints the numbers 0 through 4 and returns the string "abc" every time it is called. Functions in Pip are anonymous, although they can be assigned to a variable if need be.

A function that ends with an expression returns that expression. If it does not end with an expression (for instance, if the last statement in the function is a loop or an if statement), the function returns nil.

Inside a function, the local variables a through g are set as follows:

• a through e are set to the first through fifth arguments of the function.
• f is set to the function itself.
• g is set to a list of all the function's arguments. Use arGs as a mnemonic.

All functions in Pip are variadic: they can take any number of arguments, including zero. To find out how many arguments were passed, use #g to get the length of the argument list. If fewer than five arguments are provided, the variables in a through e that don't correspond to an argument are set to nil.

All variables other than a through g (global variables and special variables) work exactly the same inside functions as outside them.

To call a function, enclose it and its arguments in parentheses, separating them with semicolons as needed:

({a*5+b}11;-13)

The function {a*5+b} multiplies its first argument by 5 and adds its second argument to the product. With arguments 11 and -13, it returns a result of 42. Because the function call is the final expression in the program, this value is autoprinted. (TIO)

Note: Because functions are variadic, you can pass as many arguments as you like to this function. However, since the function only uses a and b, any arguments after the first two are simply ignored. (TIO)

The function-call syntax (func args) is borrowed from Lisp. While it may be less intuitive at first for programmers of C-like languages, it removes potential ambiguities from parsing. Since separators are not required between consecutive expressions in Pip, an expression like f(x) could represent the value f followed by the value x. (fx), on the other hand, cannot represent anything but a function call.

Recursion

Because the local variable f is set to the current function, calling f inside a function results in recursion. For example, here's a function that computes the factorial of its argument:

{a?a*(fa-1)1}

(TIO)

In practice, recursion is rarely useful. The current implementation of Pip is not optimized for recursion, to put it lightly: there is no tail-call optimization, and it takes less than 200 recursive calls in Pip to exceed Python's maximum recursion depth. (TIO) More importantly, recursion is not very golfy! The somewhat lengthy function-call syntax and the need to distinguish between base and recursive cases usually means another approach will be shorter.

The main program is a function too

You may have noticed some similarities between functions and the main program (setting the values of local variables, returning the last expression). That's because the main program is also a function. When a Pip program is run, the command-line arguments are treated as the arguments of the main function, and whatever the function returns is printed.

Fun fact: This is why a program that doesn't end in an expression doesn't produce any output (except whatever may have been explicitly printed earlier). The main function returns nil, which does get printed--but as you'll recall, printing nil outputs nothing and suppresses the trailing newline.

Since the main program is a function, we can call it recursively. Here's the factorial function from above, as a full program this time:

a?a*(fa-1)1

(TIO)

But to drive home the point about recursion not being the shortest way to do things, here's an iterative solution:

Fi\,ao*:io

This is one byte shorter, taking advantage of the preinitialized variable o == 1. (TIO)

So main-program recursion is not a strategy you'll employ often. But it's still a nice trick to keep in the back of your toolbox.

Lambda Expressions

So far, we've seen how to define a function using curly braces.

Problem #1: This syntax is not very golfy. If we want to define a function that adds 42 to its argument, we end up spending 33% of our six bytes on curly braces: {a+42}. A shorter syntax would be better.

Problem #2: Suppose we want to write a function that adds together its argument and the first argument of the main program. In the main program, we can access the first command-line argument as a. But inside a function, a is the function argument: the function's local variable "shadows" the outer value of a. The only way to access the program's argument from inside a function is to first assign it to a global variable. That costs bytes.

Enter lambda expressions:

_+42

The function _+42 is exactly equivalent to {a+42}, but two bytes shorter. (TIO)

_+a

The function _+a adds its argument to the program's first command-line argument. a still has its top-level value because it's not inside curly braces. (TIO)

Lambdas: the simple explanation

To write a lambda expression, proceed as if you were writing a single-expression function, but use _ for the first argument (in place of a) and B for the second argument (in place of b). Then simply leave off the curly braces. Local variables evaluate to whatever value they have in the surrounding scope.

Not all operators can be used in a lambda expression, but many can. Here's a function that checks whether the maximum element of a list is greater than the length of the list:

MX_>#_

(TIO)

The precedence table has a column that indicates whether each operator can be used in a lambda expression. In general, the only ones that can't are 1) operators that typically take functions as arguments and 2) very low-precedence operators like logic, assignment, and output operators.

Lambdas: behind the scenes

Lambda expressions are actually just ordinary expressions that happen to involve functions. Remember, functions are first-class objects in Pip. The _ used in lambda expressions is a global variable like all the others, initialized to the identity function {a}. Similarly, B is a global variable initialized to {b}.

When Pip evaluates an operator that can be used in lambda expressions, it checks whether one or both of the operands is a function. If so, the result of the operation is another function. So when you write _+42, you're actually adding 42 to the identity function; the result is a function that adds 42 to its argument. There's nothing special about _; you'd get the same result if you wrote {a}+42. You could even write f+42 and get a function that adds 42 to the result of a recursive call (though that can have unexpected results).

Applying a unary operator to a function results in a function that applies that operator to the original function's return expression:

-_ == -{a} == {-a}

Applying a binary operator to a function and a value results in a function that applies that operator to the original function's return expression and that value:

_+42 == {a}+42 == {a+42}
'x.B == 'x.{b} == {'x.b}
{a+1}/2 == {(a+1)/2}

Notice, in the last example, how this construction is not the same as just "moving the operator" inside the curly braces: The function's original expression retains highest precedence. (TIO)

Applying an operator to two functions results in a function that applies that operator to the original functions' return expressions:

_+B == {a}+{b} == {a+b}

It should be clear now why some operators can't be used in lambda expressions. If I write _:5, I'm assigning the value 5 to the variable _, the same as if I wrote f:5 or x:5. If I write P_, I'm printing the function {a}. So to use non-lambda-compatible operators in a function, you'll still need the curly-brace form. Similarly, if you need loops or if statements, you'll have to use curly braces.

Operators for Functional Programming

I mentioned above that some operators take functions as their arguments. These operators--map, filter, and a few others--are the main reason to use functions in Pip. Using a map operator with a lambda expression and a list-formatting flag is usually shorter than the equivalent for loop. For example, if we want to print each character in an input string followed by its character code:

FxaPx.s.Ax
_.s.A_Ma

The second program needs the -l or -n flag to give the same newline-separated output as the first, but it is two bytes shorter. (TIO 1; TIO 2)

Map

The map operator M takes a function and an iterable (List, Range, or Scalar). It applies the function to each item in the iterable and returns a List of the results.

Note: All the examples below use the -p flag to make the list structure clear; often, you will want to use a different list-formatting flag, depending on the required output format of the challenge.

Let's try mapping a function to different inputs. We'll use the function _WR':, which concatenates a colon to the front and end of its input.

_WR':M["Hello""beautiful""world"]

Each element of the list is wrapped in colons. (TIO)

_WR':M5,15

Each number in the range is wrapped in colons. (TIO)

_WR':M"abcd"

Each character in the string is wrapped in colons. (TIO)

The result of M is always a List, no matter what type of iterable we start with.

The M operator is right-associative, which means we can map one function, then another, then another by writing <func3>M<func2>M<func1>M<iterable>:

_*_MRV_Mg

The above code parses as _*_M(RV_Mg): it reverses every number in the command-line args and then multiplies each reversed number by itself. (TIO)

Filter

The filter operator FI takes a function and an iterable. It applies the function to each item in the iterable, but instead of returning the results, it returns a List of the original items for which the function returned a truthy value.

For example, we can use filter to create a list of all positive integers less than 1000 that are palindromes (equal to themselves when read backwards):

_=RV_FI1,m

The range of numbers 1 to 999 (1,m) is filtered on the function _=RV_, which tests whether its argument equals itself reversed. (TIO)

Or we can filter a string a to keep only the characters with codepoints greater than its first character:

_GT@aFIa

For each character (_), the function tests whether it is greater than (GT) the first character of a (@a). (GT does string comparison, whereas > does numeric comparison.) (TIO)

As with map, the result is always a List.

FI is also right-associative, which means you can chain several maps and filters together. For instance, suppose we want to write a program that finds the middle character of each command-line argument. Strings with even lengths don't have a middle character, so we want to discard them.

_@(#_//2)M#_%2FIg

The program filters g on #_%2, keeping the strings with odd lengths (since n mod 2 is truthy if n is odd and falsey if n is even). To the remaining list, it then maps _@(#_//2): index into each item (_@) at the index that is the length of the item divided by 2 (#_//2). (TIO)

Sort by key function

While FI selects items based on the return value of a function, the sort-keyed operator SK sorts an iterable based on the return value of a function. For example, we can sort a list of strings by length:

#_SKg

(TIO)

Again, the result is always a List.

Caveat: SK uses a numeric sort, so you'll want to use a function that returns numbers rather than strings.

Other mapping operators

Besides M, there are several other operators that perform some kind of map, all of which are two-letter operators that start with M. We'll just cover a few here:

The double-map operator MM ("map-map") maps at the second level: it applies a function to the items of the items of an iterable, returning a List of Lists of results. Let's revisit an earlier example:

_WR':MM["Hello""beautiful""world"]

Now, instead of each string being wrapped in colons, each character in each string is wrapped in colons. (TIO)

The map-unpack operator MU applies a function to the items of an iterable, but it unpacks each item (which must be an iterable itself) into separate arguments before passing it to the function. Suppose we have a list of Cartesian coordinate pairs (x, y), and we want to calculate each point's distance from the origin √(x² + y²). If we use M, our function will receive each pair as a single argument, a, and we'll have to do some indexing to get the values out:

{RT(a@0**2+a@1**2)}M[[1 0][-4 3][5 12]]

(TIO)

Using MU, each pair is unpacked as two separate arguments, a and b, which we can use directly:

{RT(a**2+b**2)}MU[[1 0][-4 3][5 12]]

(TIO)

I've written this example as a curly-brace function to make it easier to see what the arguments are. We can also write it as a lambda expression; remember that _ stands for the first argument and B for the second:

RT(_**2+B**2)MU[[1 0][-4 3][5 12]]

(TIO)

The map-pairs operator MP applies a function to each pair of adjacent items in an iterable, passing the two items as arguments a and b. For example, a triangular number is half the product of two consecutive integers. To calculate the first nine triangular numbers, we can apply MP to a Range:

(_*B)/2MP,t

The function calculates (0*1)/2, (1*2)/2, (2*3)/2, and so on. (TIO)

Sometimes you don't want your map results in a List. The map-sum and map-join operators, MS and MJ give a couple of other options: sum of results and results joined into a string, respectively. For example, to sum the ASCII codes of the characters in a string:

A_MS"Pip"

(TIO)

---

More on functional programming in Pip coming up!