Presumptions Presumptions Presumptions

@danielbodart

http://dan.bodar.com/

The Story

What follows are some of the presumptions I challenged while writing 11 open source tools:

pre·sump·tion:

  1. An act or instance of taking something to be true or adopting a particular attitude toward something, esp. at the start of a chain of argument or action
  2. An idea that is taken to be true, and often used as the basis for other ideas, although it is not known for certain

Java is ugly and verbose

Which language?

reduce lcm (range 1 21)Clojure
reduce(lcm, range(1, 20))Java
foldl1 lcm [1..20]Haskell
range(1,20).reduce(lcm)Java
1 to 20 reduce lcmScala
range(1, 999).
    filter(or(sequence(3, 5).map(asWhere(mod, is(zero)))).
    reduce(sum);Project Euler 1
List<Number> factor(Segment<Number> ps, Number n) {
    Number p = ps.head();
    if (greaterThan(squared(p), n)) return list(n);
    if (isZero(remainder(n, p))) return cons(p, factor(ps, quotient(n, p)));
    return factor(ps.tail(), n);
}Prime Factors
Sequence<Number> primes() {
    return computation(2, computation(3, nextPrime));
}

Number nextPrime(Number number) {
    return iterate(add(2), number).filter(prime)).second();
}

boolean prime(Number candidate) {
    return primes().takeWhile(where(squared, lessThanOrEqualTo(candidate))).
        forAll(where(remainder(candidate), is(not(zero))));
}Primes*

Java does not have ...

sequence('λ','Σ').forAll(isJavaIdentifier));Crazy Symbols
@tailrec
public static int gcdInt(int x, int y) {
    if (y == 0) return x;
    return gcdInt(y, x % y);
}Tail Call Optimisation (JCompilo)
sequence("car", "bob").
    map(λ(s, s.toUpperCase()));Lambdas (Enumerable)
Function2<Number,Number,Number> Σ = λ(n,m, n + m);
Function1<Number,Function1<Number, Number>> curried = Σ;
Currying
Function1<Number, Number> inc = Σ.apply(1);Partial Application
some(5).
    applicate(some(3).
    applicate(some(Σ));Applicative Functors
class Car {
    enum constructors { factory;
        Car car() { return new Car(); }
    }
}Companion Objects
<T extends Runnable & Closeable> void go(T t){
    try {
        t.run();
    } finally {
        t.close();
    }
}Multiple Bounds
primes().map(inc).
    drop(10000).head();Laziness + Infinite Sequences

JVM (Bytecode) does not support ...

abstract overloaded()I;
abstract overloaded()Ljava/lang/String;Overloading by Return Type
public RecursiveZipper top();
    Code:
    Stack=1, Locals=1, Args_size=1
    0:	aload_0
    1:	invokevirtual	#57;
    4:	ifeq	9
    7:	aload_0
    8:	areturn
    9:	aload_0
    10:	invokevirtual	#59;
    13:	astore_0  // re-assign 'this'
    14:	goto	0Re-assigning 'this'

'LINQ' requires Expression Trees

records.get(people).
    filter(where(firstName, startsWith("d"))).
    sortBy(age).
    map(firstName);Java (LazyRecords)

Query Projections:

select firstName from people
    where firstName like 'd%'
    order by age ascSQL
+type:people +firstName:d*Lucene
POST https://sdb.amazonaws.com/ HTTP/1.1
Content-Type: application/x-www-form-urlencoded
Action=Select
SelectExpression=select firstName from people where firstName like 'd%'
    order by age asc
...  SimpleDB
//people[starts-with(firstName, 'd')]/firstNameXml/XPath*

Persistent Data Structures are complex

Lines of Code
GetPutRemoveBalance
HashMap11202426
TreeMap344845125
ConcurrentSkipListMap346767??
AVLTree (TotallyLazy)551124
 
public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key); // type (and possibly null) check

        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    else {
        if (key == null)
            throw new NullPointerException();
        Comparable<? super K> k = (Comparable<? super K>) key;
    do {
        parent = t;
        cmp = k.compareTo(t.key);
        if (cmp < 0)
            t = t.left;
        else if (cmp > 0)
            t = t.right;
        else
            return t.setValue(value);
        } while (t != null);
    }
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}
TreeMap (JDK 1.7)
public Self put(K key, V value) {
    int difference = difference(key);
    if (difference == 0) return create(key, value, left, right, comparator);
    if (difference < 0) return create(this.key, this.value, left.put(key, value), right, comparator);
    return create(this.key, this.value, left, right.put(key, value), comparator);
}
                        AVLTree (TotallyLazy)

Recursion ≡ StackOverflow

Given a O(log n) binary tree and stack depth size of 1024.

How many elements would be needed to blow the stack?

1×1032 or 100,000,000,000,000,000,000,000,000,000,000

Persistent Data Structures are slow

GET
101001k10k100k1M
HashMap100100100100100100
TreeMap100110130150180190
ConcurrentSkipListMap130140150180210260
AVLTree (TotallyLazy)100110120130150160
PUT
101001k10k100k1M
HashMap606060606070
TreeMap7080100130180200
ConcurrentSkipListMap100110170180200260
AVLTree (TotallyLazy)120170250430550620
REMOVE
101001k10k100k1M
HashMap100110110120130140
TreeMap110130140150170190
ConcurrentSkipListMap160190290340400450
AVLTree (TotallyLazy)160200340470540630

Presumptions Presumptions Presumptions

@danielbodart

http://dan.bodar.com/