Extensions - Lambda functions


The com.singularsys.extensions.lambda package adds anonymous functions and higher order functions.

Defining a function

The default syntax for an anonymous function is x => x^2, this is a function which squares its argument. The functions can be evaluated using the apply higher order function which takes a lambda function as its first argument and a value for the second arguments. apply(x=>x^2,5). Functions with multiple arguments can be defined like [x,y] => x^y and evaluated using apply([x,y]=>x^y,5,2).

Functions can be assigned to variables Square = x => x^2 and these can be evaluated using apply(Square,5).

Higher order functions

Various higher order functions are available:

Range operator

Sequences can be easily built using the [1 .. 10] notation, equivalent to the sequence [1,2,3,4,5,6,7,8,9,10] This is implemented using the RangeOperator and Range function.

Combining functions

Multiple lambda functions can be used together which can produce complex functions. Variables defined in the outer function can be used in the inner function. So a lambda function to sum a sequence can be defines as Sum = seq => fold([x,y]=>x+y,seq) and applied using apply(Sum,[1..10]).

Simple recipes

Sum a sequence:
Sum = seq => fold([x,y]=>x+y,seq)
Sum of squares:
fold([x,y]=>x+y,map(x=>x^2,[1,2,3,4,5]))
Sum of squares (using the Sum higher order function defined above)
apply(Sum,map(x=>x^2,[1..5]))
Product a sequence:
Prod = seq => fold([x,y]=>x*y,seq)
Factorial as product of a list
Fact = n => n<=1 ? 1 : apply(Prod,[1..n])
Recursive factorial
Fact = x => x<=1 ? 1 : x*apply(Fact,x-1)
Logical or of a sequence
Or = seq => fold([x,y]=>x||y,seq)
Test if a sequence contains a value
Contains = [seq,n] => apply(Or, map(x=>x==n,seq))
Minimum value of a sequence
Min = seq => fold([x,y]=>x<y?x:y,seq)
Maximum value of a sequence
Max = seq => fold([x,y]=>x>y?x:y,seq)
Length of a sequence
Count = seq => apply(Sum,map(x=>1,seq))
Last element of a sequence
Last = seq => fold([x,y]=>y,seq)
Sequence of n copies of p
Rep = [n,p] => map(x=>p,[1..n])
Concatenate two sequences
Concat=[a,b]=>apply([a,b,la,lb]=>map(i=>i<=la?a[i]:b[i-la],[1..la+lb]), a,b,apply(Count,a),apply(Count,b))
Fibonacci numbers
map(n=>n[1],iterate([1,0],n=>[n[1]+n[2],n[1]],n=>n[1]<100))

More complex recipes

Reverse a sequence 

Rev = seq => apply([seq,k]=> 
   map( i => seq[k-i+1], [1..k]),seq,fold([x,y]=>x+y,map(x=>1,seq)));
or if a count function is available 
Rev = seq => apply([seq,k]=> map( i => seq[k-i+1], [1..k]),seq,count(seq))

Calculating primes 

candidates = [2..100];
// Removes multiples of a number from a sequence 
RmMul = [w,seq] => filter(x=>                 
  !apply(Contains,map(y=>y*w,[2..apply(Last,candidates)/w]),x),seq);
// Produce a sequence who's first element is [primes] 
// and subsequent elements are primes[1], primes[2]
// So the sequence [[2,3,4,5,...],2,3,4,5,...]
seq2 = map(i=> i==0 ? candidates : candidates[i], 
            [0..sqrt(apply(Last,candidates))]);
// Repeatedly apply the RmMul operation to the current list of primes
primes = fold([seq,n]=>apply(RmMul,n,seq),seq2);

Or if a for loop is available using the Structure package. 

Contains = [seq,k] => fold([a,b]=>a||b,map(x=> x==k,seq));
Muls = [k,maxv]=>map(x=>k*x,[2..maxv/k]);
tmp=[2..100];
for(i=1;tmp[i]*tmp[i]<last;++i) { \\
    tmp=apply([seq,mu]=>filter(x=>   \\
        !apply(Contains,mu,x),seq),tmp,apply(Muls,tmp[i],last)); \\
    println(tmp); \\
}

Calculating e using 1 + 1/1! + 1/2! + ... 

E = apply(Sum,map(x=>1/apply(Fact,x),[0..20]));

More efficient version using recursion, eliminating need for repeated calls for factorial. Runs in O(n) rather than O(n^2) time. 

E = u => u[3]+1/(u[2]*u[1]) == u[3] ? u :
            apply(E,[u[1]+1,u[2]*u[1],u[3]+1/(u[2]*u[1])]);
apply(v=>v[3],apply(E,[1,1,1]))

Combining Symbolic operations with Lambda functions

Symbolic operations like differentiation can be combined with lambda function. Here the ExtractEqn function can be useful. This extracts the equation from a symbolic variable. Here we add a symbolic assignment operator := and the eqn() function, using 

DJep djep = new DJep(optab,cp, lp);
((OperatorTable2) djep.getOperatorTable()).addOperator(
    new Operator(":=",new XAssign(),Operator.BINARY+Operator.RIGHT),
	    djep.getOperatorTable().getAssign());
djep.getFunctionTable().addFunction("eqn", new ExtractEqn());

Once setup we can define a Newton function which takes a starting value, number of iterations and lambda functions for the function and its derivative. The function then applies the iteration \(x_{n+1} = x_{n} - f(x)/f'(x)\). Below we use Newton's method to solve \(x^m + x^n=1\). 

x=1; m=2; n=3;          // define parameters
f_exp := x^m + x^n - 1; // symbolic expressions
df_exp := diff(f_exp,x); // calculate derivative
f_lam = x => eqn(f_exp);  // lambda expressions
df_lam = x=> eqn(df_exp);
Newton = [x,n,f,df] => fold(
            [x,y] => x - apply(f,x) / apply(df,x), 
            map(i=>x,[1..n]) );
res=apply(Newton,1,5,f_lam,df_lam);
res^m+res^n;           // test result

With str being the string with the above equations the expression could be preprocessed and evaluated using 

Node parsed;
djep.initMultiParse(str);
while((parsed = djep.continueParsing())!=null) {
	djep.println(parsed);
	Node pre=djep.preprocess(parsed);
	Object res = djep.evaluate(pre);
	System.out.println(res);
}

Configuration

Configuring Jep to use Lambda functions has several steps: adding operators, configuring the parser, adding the ListProcessor to Jep and adding the higher order functions.

To setup first the operators for range, and lambda functions should be added. The ternary cond ? x : y is also useful to add. 

OperatorTable2 optab = new StandardOperatorTable2();
		
Operator rangeOp = new RangeOperator("..", "[", "]", new Range(), 
                         Operator.BINARY+Operator.NOT_IN_PARSER);
optab.insertOperator(OperatorTable2.SpecialOperators.RANGE, 
                         rangeOp, optab.getAssign());
		
TernaryOperator ternOp = new TernaryOperator("cond", "?", ":", 
		new TernaryConditional(), 
		Operator.TERNARY+Operator.NARY+Operator.LEFT);
optab.insertOperator(ternOp,optab.getAssign());
		
Operator lambdaOp = new Operator("=>", new LambdaFunGenerator(), Operator.BINARY);
optab.insertOperator(lambdaOp, optab.getAssign());
The lambdaOperator should be added with a precedence just less than the assignment operator and greater than all other operators.

To use the range operator a modified configurable parser must be use. This adds a new symbol (.. by default) to the parser and adds a new ListOrRangeGrammarMatcher. The .. notation could be confuse with the dots in numbers or the . operator used for dot products. A NumberTokenMatcher with a custom pattern ensures correct parsing. 

ConfigurableParser cp = new ConfigurableParser();
cp.addHashComments();
cp.addSlashComments();
cp.addSingleQuoteStrings();
cp.addDoubleQuoteStrings();
cp.addWhiteSpace();
cp.addTokenMatcher(  // enhanced regexp ensuring 1..2 is not parsed as 1. .2
        new NumberTokenMatcher("((\\d+\\.\\d+)|(\\d+\\.(?!\\.))|(\\.\\d+)|(\\d+))(?:[eE][+-]?\\d+)?")); 

// Adds .. to list of symbols. 
// The symbol token matcher must appear before the operator token matcher.
cp.addSymbols("(",")","[","]",",",".."); 
cp.setImplicitMultiplicationSymbols("(","["); 
cp.addOperatorTokenMatcher();

cp.addIdentifiers();
cp.addSemiColonTerminator();
cp.addWhiteSpaceCommentFilter();
cp.addBracketMatcher("(",")");
cp.addFunctionMatcher("(",")",",");

// Don't use the standard list matcher, use the ListOrRangeGrammarMatcher instead
//cp.addListMatcher("[","]",","); 
cp.addGrammarMatcher(
    new ListOrRangeGrammarMatcher(
        cp.getSymbolToken("["),
        cp.getSymbolToken("]"),
        cp.getSymbolToken(","),
        cp.getSymbolToken(".."),
        rangeOp));
cp.addArrayAccessMatcher("[","]");

The Jep instance needs to created using the operator table, the parser and a ListProcessor which handles the reading and creation of lists. 

Jep jep = new Jep(optab,cp, new StandardListProcessor());

Finally the higher order functions are added. 

jep.getFunctionTable().addFunction("map",new Map());
jep.getFunctionTable().addFunction("fold",new Fold());
jep.getFunctionTable().addFunction("filter",new Filter());
jep.getFunctionTable().addFunction("sort",new Sort());
jep.getFunctionTable().addFunction("apply",new Apply());
jep.getFunctionTable().addFunction("merge",new Merge());
jep.getFunctionTable().addFunction("iterate",new Iterate());
jep.getFunctionTable().addFunction("define",new Define());
jep.reinitializeComponents();

You could then generate Fibonacci numbers using 

Node n = jep.parse("map(n=>n[1],"+
         "iterate([1,0],n=>[n[1]+n[2],n[1]],n=>n[1]<100))");
Object res = jep.evaluate(n);
assertEquals("[1.0, 1.0, 2.0, 3.0, 5.0, 8.0, 13.0, 21.0, 34.0, 55.0, 89.0]",
         res.toString());
top