Pigeon Core - Functions

lambda

Lambda is the 11th letter of the Greek alphabet. It is also the abstraction operator from the lambda calculus that was developed by Alonzo Church in the 1930s. And it is also the Pigeon function for creating new functions. The special form:

(lambda (args) code ...)

creates a new function which, when called, will evaluate the supplied code expressions from left to right, returning the result of the final expression. For instance:

(lambda (a b) (add: a b))

is a function which returns the result of adding its two arguments.

Lambda expressions create anonymous functions. Sometimes this is what you want, for instance if you are immediately going to pass the new function as a parameter to some other function, but you will often want to provide a name by assigning the result of the lambda to a variable:

// store a function into the variable 'hello'
(def (hello
  (lambda (name)
    (print 'hello, ')
    (print name)
    (print ': pleased to meet you!\n'))))

// now call it
(hello 'shawn')

Lambda Closures

Pigeon is a lexically scoped language, which means that lambda functions can refer to variables from outside the lambda itself, but that were visible at the point when the function was created. Such variables will be kept alive as long as any function needs them, even after the scope in which the variable was originally defined has exited. The new function has 'closed over' the variable, ie. has become a closure.

Example:

// function that creates other functions
(def (counter
  (lambda ()
    (def (count 0))
    (lambda ()
      (set count (add: count 1))
      (print count)))))

// create two counter functions
(def (a (counter)))
(def (b (counter)))

// call the counters
(a) (a) (a)
(b) (b)
(a)

// output: 123124

Closures can be initially confusing, but are well worth spending the time to get your head around. They give elegant expression to many powerful concepts, and there is much zen to be had here.

Lambda Parameter Lists

Immediately after the lambda symbol comes a list describing the function parameters. An empty list means there are no parameters, otherwise this list can contain any combination of:

symbol. A regular function parameter.
(symbol value). An optional parameter. If not provided by the caller, the default value will be used instead. Default values are evaluated when the lambda is created, in the context of the enclosing scope.
(symbol *). A 'rest' parameter. If the caller provides too many parameters, the leftovers are grouped into a list and stored here. There can only be one rest parameter, and it must come after all the regular parameters.
(symbol **). A 'keys' parameter. If the caller provides unknown keyword parameters, the leftovers are grouped into a hash and stored here. There can only be one keys parameter, and it must come after all the regular and optional parameters.
(. label). Not strictly a parameter at all. This labels the function, creating a new execution frame alias.

For example:

(lambda () ...)
(lambda (a b c) ...)
(lambda (shape (color red) (size 10)) ...)
(lambda ((. scopename) a b (rest *) (keys **)) ...)

Lambda Calls

When calling a function, parameters can be passed by position or by name. For instance, given the function:

(def (f (lambda (a b (c *) (d nil)) ...)))

these calls are all equivalent:

(f 23 42)
(f a: 23 b: 42)
(f b: 42 a: 23)
(f 23 b: 42)
(f b: 42 23)

If a call mixes positional and named parameters, the location of the named parameters is unimportant.

For functions that accept rest lists, parameters coming before the rest location can be passed by name or position, but parameters coming after the rest list can only be passed by name. For instance with the example given above:

(f 1 2 3 4 5)

will bind a to 1, b to 2, and c to the list [3 4 5]. The d parameter is only accessible by name.

If you have a list holding positional parameters, or a hash holding keyword parameters, you can unpack these into the argument list:

(f (* args) (** keywords))

The result is exactly as if the contents of the list or hash had been manually expanded out at this point in the argument list.

It is an error to omit parameters that lack default values, or to provide too many positional parameters for functions without a rest list, or to provide unknown named parameters for functions without a keys hash, or to provide both positional and named values for the same parameter.

Note that the :param shortcut syntax for optional boolean parameters is not part of Core Pigeon: that is implemented by the higher level parser.

Lambda Recursion

Pigeon supports tail recursive function calls. This means that if the very last thing a function does is to return the value of calling some other function, the new function can reuse the current execution frame. This is not just a performance optimisation: it also means that deeply recursive algorithms can run without fear of running out of stack space. For instance, state machines can be cleanly expressed as a set of mutually recursive functions, one per state, which simply call each other when they want to change state.

Because the def statement makes itself visible to nested lambda expressions, singly recursive functions can be written directly:

(def (factorial
  (lambda (n)
    (if (equal: n 1)
      1
      (mul: n (factorial (sub: n 1)))))))

But mutually recursive sets of functions need to be predefined:

(def a b)

(set a (lambda () (print 'a') (b)))
(set b (lambda () (print 'b') (a)))

(a)