Konkatenative Programmierung mit Lambda-Ausdrücken (Java)

confunc.java

/* Konkatenative Programmierung mit Lambda-Ausdrücken (Java)
   Dominikus Herzberg, @denkspuren, 2018-03-09

   Ich liebe das konkatenative Programmierparadigma -- das ist ein Grund,
   warum Consize entstanden ist (https://github.com/denkspuren/consize).
   Hier ist die konkatenative Berechnung der Fakultät nachgebaut unter
   Verwendung von Lambda-Ausdrücken. Ich verwende einen Stapel, der
   von Funktion zu Funktion weitergereicht wird. Damit es funktional
   "sauber" zugeht, simuliere ich Immutabilität mithilfe von clone().

   Die Datei führe ich mit der JShell aus. Man kann die Warnungen des
   Compilers ignorieren; das Typsystem von Java ist für so einen
   flexiblen, dynamischen Umgang mit Datentypen nicht geeignet.

   Implementiert ist die Berechnung der Fakultät

   * mithilfe des Y-Kombinators (der den X-Kombinator nutzt), was
     ich mächtig cool finde
   * über eine rekursive Verwendung einer Variablen, was zu meiner
     Überraschung nicht funktioniert und Fehler produziert; die JShell
     scheint interne Referenzen auf frühere Variablendeklarationen zu
     nutzen
   * über eine statische, rekursive Methode, was tadellos funktioniert

   Die definierten Funktionen leiten sich allesamt aus der Dokumentation
   zu Consize ab:
   https://github.com/denkspuren/consize/blob/master/doc/Consize.pdf

   Einen Reducer gibt es außerdem, der hilft, eine Folge von Funktionen zu
   evaluieren. Allerdings ist der Reducer nicht parallelisierbar, da man
   die Funktionsfolge nicht an beliebigen Stellen aufbrechen kann.
*/

Function<Object,Function<Stack,Stack>> konst =
    c -> s -> { Stack<Object> r = (Stack)s.clone();
                r.push(c);
                return r; };

Function<Stack,Stack> self(Object o) { return konst.apply(o); }

Function<Stack,Stack> dup = s -> self(s.peek()).apply(s);
Function<Stack,Stack> drop = s -> { Stack<Object> r = (Stack)s.clone(); r.pop(); return r; }
Function<Stack,Stack> rot = s -> { Stack<Object> r = (Stack)s.clone();
                                   Object z = r.pop();
                                   Object y = r.pop();
                                   Object x = r.pop();
                                   r.push(y); r.push(z); r.push(x);
                                   return r; }
Function<Stack,Stack> swap = dup.andThen(rot).andThen(rot).andThen(drop);

Function<Stack,Stack> add = s -> self((Integer)s.pop() + (Integer)s.pop()).apply(s);
Function<Stack,Stack> neg = s -> self(-(Integer)s.peek()).apply(drop.apply(s));
Function<Stack,Stack> sub = neg.andThen(add);
Function<Stack,Stack> mul = s -> self((Integer)s.pop() * (Integer)s.pop()).apply(s);
Function<Stack,Stack> apply = s -> (Stack)((Function)s.peek()).apply(drop.apply(s));

Function<Stack,Stack> TRUE = drop;
Function<Stack,Stack> FALSE = swap.andThen(drop);

Function<Stack,Stack> isEqual = s -> {
    Stack<Object> r = (Stack)s.clone();
    Object y = r.pop();
    Object x = r.pop();
    r.push(x.equals(y) ? TRUE : FALSE);
    return r;
}

Function<Stack,Stack> choose = rot.andThen(apply);
Function<Stack,Stack> IF = choose.andThen(apply);
Function<Stack,Stack> dec = self(1).andThen(sub);
Function<Stack,Stack> inc = self(1).andThen(add);
Function<Stack,Stack> X = dup.andThen(apply);
Function<Stack,Stack> tor = rot.andThen(rot);
Function<Stack,Stack> swapd = swap.andThen(rot).andThen(rot);
Function<Stack,Stack> nip = swap.andThen(drop);
Function<Stack,Stack> dupd = swap.andThen(dup).andThen(rot);
Function<Stack,Stack> over = swap.andThen(dup).andThen(tor);
Function<Stack,Stack> twodup = over.andThen(over);
Function<Stack,Stack> wrap = s -> self(self(s.peek())).apply(drop.apply(s));

Function<Stack,Stack> compose = s -> {
    Stack<Object> r = (Stack)s.clone();
    Function f2 = (Function)r.pop();
    Function f1 = (Function)r.pop();
    r.push(f1.andThen(f2));
    return r;
}

Function<Stack,Stack> dip = swap.andThen(wrap).andThen(compose).andThen(apply);
Function<Stack,Stack> twodip = swap.andThen(self(dip)).andThen(dip);
Function<Stack,Stack> keep = self(dup).andThen(dip).andThen(dip);
Function<Stack,Stack> twokeep = self(twodup).andThen(dip).andThen(twodip);

/*
: Y ( val quot -- res )
[ [ [ call ] 2keep -rot dupd equal? ] dip
swap [ drop nip ] [ swapd X ] if ] X ;
*/

Function<Stack,Stack> Y = self(self(self(apply).andThen(twokeep).andThen(tor).andThen(dupd).andThen(isEqual)).andThen(dip).andThen(swap).andThen(self(drop.andThen(nip))).andThen(self(swapd.andThen(X))).andThen(IF)).andThen(X);

Function<Stack,Stack> id = s -> s;
Function<Stack,Stack> when = self(id).andThen(IF);

// 4 1 [ swap dup 0 equal? [ drop 1 ] when [ * ] keep 1 - swap ] Y nip

Function<Stack,Stack> body = swap.andThen(dup).andThen(self(0)).andThen(isEqual).
                             andThen(self(drop.andThen(self(1)))).andThen(when).
                             andThen(self(mul)).andThen(keep).andThen(dec).andThen(swap);
Function<Stack,Stack> fact = self(1).andThen(self(body)).andThen(Y).andThen(nip);

/* ****************************************************************
   Das Ziel ist erreicht: Fakultätsberechnung mit dem Y-Kombinator!
   ****************************************************************

jshell> fact.apply(self(4).apply(new Stack()))
$1367 ==> [24]

jshell> fact.apply(self(10).apply(new Stack()))
$1368 ==> [3628800]

*/


// : factorial ( n -- n! ) dup 0 equals? [ drop 1 ] [ dup dec factorial * ] if ;
Function<Stack,Stack> factorial = id;
factorial = dup.andThen(self(0)).andThen(isEqual).
                                  andThen(self(drop.andThen(self(1)))).
                                  andThen(self(dup.andThen(dec).andThen(factorial).andThen(mul))).
                                  andThen(IF);
factorial = dup.andThen(self(0)).andThen(isEqual).
                                  andThen(self(drop.andThen(self(1)))).
                                  andThen(self(dup.andThen(dec).andThen(factorial).andThen(mul))).
                                  andThen(IF);
factorial = dup.andThen(self(0)).andThen(isEqual).
                                  andThen(self(drop.andThen(self(1)))).
                                  andThen(self(dup.andThen(dec).andThen(factorial).andThen(mul))).
                                  andThen(IF);

/* **************************************************
   Rekursiv verwendete Variablen funktionieren nicht!
   **************************************************

Mit jeder weiteren Zuweisung der `factorial`-Variablen erreicht man teilweise
korrekte Werte für große Zahlen, kleinere wiederum brechen. Die JShell scheint
interne Verweise auf vorhergehende Variablen-Referenzen zu pflegen, anders
weiß ich mir das nicht zu erklären. Sowas kann einem schwer zu findende Bugs
bescheren!

jshell> factorial.apply(self(4).apply(new Stack()))
$1370 ==> [24]

jshell> factorial.apply(self(3).apply(new Stack())) // FEHLER!
$1371 ==> [0]

*/

class Calc {
    static Stack factn(Stack s) {
        return dup.andThen(self(0)).andThen(isEqual).
                 andThen(self(drop.andThen(self(1)))).
                 andThen(self(dup.andThen(dec).andThen(Calc::factn).andThen(mul))).
               andThen(IF).apply(s);
    }
}


/* ************************************************
   Rekursion per Namensbezug mit statischer Methode
   ************************************************

jshell> Calc.factn(self(4).apply(new Stack()))
$1372 ==> [24]

jshell> Calc.factn(self(5).apply(new Stack()))
$1373 ==> [120]
*/

// IGITT, ein SEITENEFFEKT
// Function<Stack,Stack> println = s -> { System.out.println(s.peek()); return s; };

BinaryOperator<Stack> concat = (s1, s2) -> { Stack s = (Stack)s1.clone(); s.addAll(s2); return s; };

/* Auch so kann man eine Liste von Funktionen auswerten lassen.
   Die Idee erst einmal gezeigt an einem Strom von Integern.

jshell> List.<Integer>of(1,2,3,4,5).stream().reduce("", (x,y) -> x + y, (x,y) -> x + y)
$115 ==> "12345"

jshell> List.of(self(2),dup,add,fact).stream().reduce(new Stack(), (s,f) -> f.apply(s), (s1, s2) -> concat.apply(s1,s2))
$1377 ==> [24]

*/

coole Sache!
NB: in strict Sprachen kann man mit dem Z-Combinator die Rekursion umgehen, siehe z.B. https://github.com/Dierk/HtmlJs/blob/748b5983fd7df031f6c2b0a27d3189ecbf3faeae/church/churchTest.js#L183

"S" + "H",
I though it was just a mistery; not at all. It's just very interesting... gonna learn it profundly this coming s'mester.
@Consize Me ;-)
@ssbf in Lambda-Expr

Danke für den Hinweis, Dierk! Als Notiz an mich ein paar Links:

• https://en.wikipedia.org/wiki/Fixed-point_combinator#Strict_fixed_point_combinator
• http://blog.errstr.com/2012/01/23/church-encoding-recursion/
• https://github.com/adlawson/js-zcombinator