Playing around with some Java 8 features ...

LispLikeLang.java

package java8.lisp;

import java.util.Collections;
import java.util.List;
import java.util.Optional;
import java.util.Stack;
import java.util.function.Function;

public class LispLikeLang {
    interface LExpression {
        LExpression eval(Stack<LPair> env);

        default LExpression lookup(LVar v, Stack<LPair> env) {
            Optional<LPair> r = env.stream()
                    .filter(p -> p.e1.equals(v)).findFirst(); // yuk, very inefficient!
            if (r.isPresent())
                return r.get().e2;
            else
                throw new RuntimeException("No var found: " + v.toString());
        }
    }

    static class LInteger implements LExpression {
        private Integer num;
        public LInteger(Integer num) {
            this.num = num;
        }
        Integer getNum() {
            return num;
        }
        @Override
        public LExpression eval(Stack<LPair> env) {
            return this;
        }

        @Override
        public String toString() {
            return getNum().toString();
        }
    }

    static class LNil implements LExpression {
        private List<LExpression> empty;
        public LNil() {
            this.empty = Collections.emptyList();
        }

        @Override
        public LExpression eval(Stack<LPair> env) {
            return this;
        }

        @Override
        public String toString() {
            return "nil";
        }
    }

    static class LVar implements LExpression {
        private String var;
        public LVar(String var) {
            this.var = var;
        }

        String getVar() {
            return var;
        }

        @Override
        public LExpression eval(Stack<LPair> env) {
            return lookup(this, env);
        }

        @Override
        public String toString() {
            return getVar();
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            LVar lVar = (LVar) o;

            if (var != null ? !var.equals(lVar.var) : lVar.var != null) return false;

            return true;
        }
    }

    static class LPair implements LExpression {
        private final LExpression e1;
        private final LExpression e2;
        public LPair(LExpression e1, LExpression e2) {
            this.e1 = e1;
            this.e2 = e2;
        }

        public LExpression getFirst() {
            return e1;
        }

        public LExpression getSecond() {
            return e2;
        }

        @Override
        public LExpression eval(Stack<LPair> env) {
            return new LPair(e1.eval(env), e2.eval(env));
        }

        @Override
        public String toString() {
            return new StringBuilder("(")
                    .append(e1.toString())
                    .append(" . ")
                    .append(e2.toString())
                    .append(")").toString();
        }
    }

    static class LLet implements LExpression {
        private String var;
        private LExpression e;
        private LExpression body;
        public LLet(String var, LExpression e, LExpression body) {
            this.var = var;
            this.e = e;
            this.body = body;
        }

        @Override
        public LExpression eval(Stack<LPair> env) {
            env.push(new LPair(new LVar(var), e.eval(env)));
            return body.eval(env);
        }

        @Override
        public String toString() {
            return new StringBuilder("(let (")
                    .append(var)
                    .append(" ")
                    .append(e.toString())
                    .append(") ")
                    .append(body.toString())
                    .append(")").toString();
        }
    }

    static class LAdd implements LExpression {
        private final LExpression e1;
        private final LExpression e2;
        public LAdd(LExpression e1, LExpression e2) {
            this.e1 = e1;
            this.e2 = e2;
        }

        @Override
        public LExpression eval(Stack<LPair> env) {
            LExpression n1 = e1.eval(env);
            LExpression n2 = e2.eval(env);
            if (n1 instanceof LInteger && n2 instanceof LInteger)
                return new LInteger(((LInteger) n1).getNum() + ((LInteger) n2).getNum());
            throw new IllegalArgumentException("Addition applied to non-number");
        }

        @Override
        public String toString() {
            return new StringBuilder("(+ ")
                    .append(e1.toString())
                    .append(" ")
                    .append(e2.toString())
                    .append(")").toString();
        }
    }

    static class LFirst implements LExpression {
        private LExpression e;
        public LFirst(LExpression e) {
            this.e = e;
        }

        @Override
        public LExpression eval(Stack<LPair> env) {
            LExpression pr = e.eval(env);
            if (pr instanceof LPair)
                return ((LPair)pr).getFirst();
            else
                throw new IllegalArgumentException("Expected a pair");
        }

        @Override
        public String toString() {
            return new StringBuilder("(fst ")
                    .append(e.toString())
                    .append(")").toString();
        }
    }

    static class LSecond implements LExpression {
        private LExpression e;
        public LSecond(LExpression e) {
            this.e = e;
        }

        @Override
        public LExpression eval(Stack<LPair> env) {
            LExpression pr = e.eval(env);
            if (pr instanceof LPair)
                return ((LPair)pr).getSecond();
            else
                throw new IllegalArgumentException("Expected a pair");
        }

        @Override
        public String toString() {
            return new StringBuilder("(snd ")
                    .append(e.toString())
                    .append(")").toString();
        }
    }

    public static void main(String... args) {
        System.out.println(
                new LPair(new LInteger(1),
                    new LPair(
                        new LAdd(new LInteger(3), new LInteger(4)),
                        new LNil())));
        System.out.print("==> ");
        System.out.println(
                new LPair(new LInteger(1),
                        new LPair(
                                new LAdd(new LInteger(3), new LInteger(4)),
                                new LNil())).eval(new Stack<>()));

        System.out.println(new LLet("a", new LInteger(3),
                            new LAdd(new LInteger(4), new LVar("a"))));
        System.out.print("==> ");
        System.out.println(
            new LLet("a", new LInteger(3),
                new LAdd(new LInteger(4), new LVar("a"))).eval(new Stack<>()));

        System.out.println(
            new LLet("p", new LPair(new LInteger(4), new LInteger(5)),
                new LPair(new LFirst(new LVar("p")), new LVar("p"))));
        System.out.print("==> ");
        System.out.println(
                new LLet("p", new LPair(new LInteger(4), new LInteger(5)),
                        new LPair(new LFirst(new LVar("p")), new LVar("p"))).eval(new Stack<>()));

        System.out.println(
                new LLet("x", new LInteger(4),
                    new LLet("y", new LInteger(10),
                        new LAdd(new LVar("x"), new LVar("y")))));
        System.out.print("==> ");
        System.out.println(
                new LLet("x", new LInteger(4),
                    new LLet("y", new LInteger(10),
                        new LAdd(new LVar("x"), new LVar("y")))).eval(new Stack<>()));

        System.out.println("Now for some lambda expressions...");

        LExpression le1 = new LAdd(new LVar("x"), new LInteger(3))::eval;
        Stack env1 = new Stack();
        env1.push(new LPair(new LVar("x"), new LInteger(7)));
        System.out.println("var (x = 3) added to a constant 7 = " + le1.eval(env1));

        Function<Integer,LExpression> mkDouble = n ->
                new LLet("x", new LInteger(n),
                        new LAdd(new LVar("x"), new LVar("x")))::eval;
        System.out.println("Double of 2 = " + mkDouble.apply(2).eval(new Stack<>()));
    }
}