These libraries provide a nearly complete version of the lambda calculus with extensions. This document includes:
Caveat reader: This is not a precise, or, even correct, introduction of the Lambda calculus, as there are several accurate and in-depth descriptions available.
The lambda calculus (from Church, et al) allows one to define functions rigorously: a "parameter list" and a "return value" or result or computation or expression or whatever buzzword you like that means doing something that returns a value.
\ x . x + 1
0.
The term has the head which includes lambda and the "parameter list" and the dot, and the body which is the action that returns a value.
Lambda terms are expressions, not "statements", so no side effects occur, such as assignment or mutation. A lambda term is cseable.
\x . \y . x + y
This framework provides syntactic extensions to the Java language that allow for a very close imitation of the lambda calculus. A lambda term in Java is actually an anonymous inner class instance of functional.Function, which promotes these anonymous "functions" to first-class objects: they can be passed as parameters, assigned, etc.
To create a lambda term do the following in a .latte file: 3
import functional.*; // ... in a method final Function succ = \ x . x + 1; final Function mult = \ x . \ y . x * y;
Lambda terms can be used in any place that anonymous inner class instantiation occurs (see, e.g. functional.Fn for descriptions of methods (iterators) that use lambda terms:
// ... boolean myFlavor = Fn.any(\x . x = "chocolate", flavors);
The Five Arithmetic Operators | |
---|---|
* | |
/ | |
% | |
+ | N.B.: only arithmetic addition (but also including character to integer addition), string concatenation shall be handled by ++ (!!) 4 |
- | N.B.: A character minus a character returns an integer |
Boolean operators | |
= | not
assignment, think more of Prolog's unification on two
constants, as this token is converted into
equals/1 . |
!= | |
! | |
&& | |
|| | |
< | |
> | |
<= | |
>= | |
true | |
false | |
List Operations | |
All List Operations are not yet available. | |
obj : [elt] | conses obj onto the head of the list, return list is [obj, elt] (partially implemented) |
obj : list | System doesn't yet know that list is a valid list, so the parser fails here |
++ | concatenates two lists |
[elt] | List constructor of a single instance. |
[1, 2, elt] | List constructor returning a List instance containing 1, 2, and 3 if elt is 3 and the list is eager. |
"a string" | Strings are converted into a list of characters internally and returned as java.lang.String objects. |
Higher-Order Functions | |
---|---|
These functions are members of functional.Fn | |
map(fn/1, list) : List | Creates and returns a new List instance by applying fn to each element of list (list can be an Iterator or a List instance) |
fold(fn/2, seed, list) : Object | Returns an object that is the accumulation of successive applications of fn to the elements of list. The process is started by applying fn to seed and list.get(0) 5, 6 |
fold(fn/2, list) : Object | Same as above, but uses the first first element of list as the seed. |
unfold(test/1, f/1, g/1, seed) : LazyList | Creates a LazyList by recursively applying f to a value until the result is done. The value is computed by applying g to the previous value. The first input value is seed, the first element of the list is f(seed), the second input value is g(seed). |
unfold(f/1, g/1, seed) : LazyList | Same as above, but the LazyList produced is infinite, as there's no test to stop the process. |
filter(test/1, list) : List | Selects all the elements that are true for test and returns them as a List |
partition(test/1, list) : List | Returns a List of two lists: the first list is all the elements that pass test, the second list is all the other elements. |
any(test/1, list) : boolean | Returns true if any element of list passes test. |
every(test/1, list) : boolean | Returns true only if every element in list passes test. |
List Functions | |
toList(list) : LazyList | Converts (currently) int[], char[], Object[], String, List or Iterator instances to a LazyList instance. |
toIterator(list) : Iterator | Same deal -- converts an object (we hope some kind of collection) into an iterator. |
reverse(list) : LazyList | Returns (e.g.) [4, 3, 2, 1] from [1, 2, 3, 4] |
take(n, list) : LazyList | returns the first n elements of list. |
drop(n, list) : LazyList | Removes the first n elements from list and returns the remainder. |
String Functions | |
just because | |
commaSeparatedList(fn/1, list) : String | This method iterates over a list, returning it as a String. fn transforms an element into a String (optionally doing some modification). |
commaSeparatedList(list) : String | This method iterates over a list, returning it as a String. Each element is converted by calling its toString/0 method. |
indefiniteArticle(noun) : String | indefiniteArticle("owl") returns "an owl" |
capitalize(word) : String | Why doesn't java.lang.String have this method? |
isVowel(char) : boolean | |
fromList(list) : String | Folds a list of characters into one string |
noneOr(string) : String | Returns "(none)" or string if string is not null and not empty |
htmlLineBreaks(string) : String | Puts "<br>" where it encounters carriage returns in string |
classname(obj) : String | Returns just the class name of obj |
The following syntax extensions allow one to create
functions by manipulating other functions. Place these
constructs (they should be final, if possible) into a file
with .latte
extension. To compile latte files,
execute the following commands in order:
java lambda.parser < foo.latte > foo.java
javac foo.java
\' foo /\
bar; | This method implements a higher-order and (&&) operation. It takes two predicates (a predicate is a Function instance that returns a Boolean) and returns a new predicate that is the intersection of the two. |
\' foo \/
bar; | This method implements a higher-order or (||) operation. It takes two predicates and returns a new predicate that is the union of the two. |
\'
~foo; | This method takes a predicate (a Function that returns a Boolean) and creates a Function that returns the opposite result. |
\' foo
. bar; | This method creates a Function h, such that h = foo(bar(xs)). |
\'
foo(bar); | This method takes a Function and its first "argument" and returns a new Function that takes one less parameter ... the original Function has been curried, e.g.: g(y) = foo(x, y), g is foo curried with bar |
0 Actually, \ should be lambda, but I use the backslash as some text editors/IDEs do not support Unicode.
1 Read Functional Programming in Haskell for reasons.
2 Remember, the lambda calculus came before programming languages, so the issue of parameter-order ambiguity was a serious one then, which the lambda calculus helped to resolve.
3 Note in the above example that there are no type declarations. The compiler uses type inferencing to declare automagically types for you. The type inferencer currently works on boolean, character, string, and arithmetic (number) expressions (i.e. all supported operations in lambda4J).
4
++/1
in Java is an impure operation, and is
therefore disallowed in the lambda calculus.
++/2
in functional programming (which the
lambda calculus describes) stands for list
concatenation, which has no side effects.
5 So, (e.g.) summation is Fn.fold(plus, new Integer(0), list)
6 The fold occurs starting from the left of the list.