神.java | Shen for Java

http://shenlanguage.org/

Shen is a portable functional programming language by Mark Tarver that offers

• pattern matching,
• λ calculus consistency,
• macros,
• optional lazy evaluation,
• static type checking,
• an integrated fully functional Prolog,
• and an inbuilt compiler-compiler.

See also: shen.clj

This Java Port

Shen.java is an invokedynamic based K Lambda compiler. I don't vouch for any of the implementation details regarding this - I'm learning as we go. All code lives in Shen.java. It passes the Shen test suite.

The main Shen JVM port is done by Joel Shellman and might be used for Babel, Mark's IDE project.

This port is loosely based on shen.clj, but has no dependency on Clojure. Started as an interpreter using MethodHandles as a primitive. It's about 2x faster than shen.clj.

This is pretty experimental, and this entire project acts as a playground for various JDK 8 and JVM language stuff. There's an IntelliJ project, which requires IDEA 12 and JDK 8 with Lambda support (b106, the JDK8 Developer Preview now has lambda support). It's based on this Maven project.

To run the REPL:

export JAVA_HOME=/path/to/jdk1.8.0/with/lambdas
./shen.java

Shen 2010, copyright (C) 2010 Mark Tarver
released under the Shen license
www.shenlanguage.org, version 13
running under Java, implementation: Java(TM) SE Runtime Environment (build 1.8.0-ea-b106)
port <unknown> ported by Håkan Råberg


(0-) (define super
       [Value Succ End] Action Combine Zero ->
         (if (End Value)
             Zero
             (Combine (Action Value)
                      (super [(Succ Value) Succ End]
                             Action Combine Zero))))
super

(1-) (define for
       Stream Action -> (super Stream Action do 0))
for

(2-) (define filter
       Stream Condition ->
         (super Stream
                (/. Val (if (Condition Val) [Val] []))
                append
                []))
filter

(3-) (for [0 (+ 1) (= 10)] print)
01234567890

(4-) (filter [0 (+ 1) (= 100)]
             (/. X (integer? (/ X 3))))
[0 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60... etc]

The Shen Test Suite

Now passes. It is run at the end of the build:

./build   # or ./tests if the jar already exists.

[... loads of output ...]
passed ... 146
failed ...0
pass rate ...100.0%

ok
0

run time: 9.882 secs

It's close to 2x faster than shen.clj.

The benchmarks can be run via:

./benchmarks

What works?

• The K Lambda parser.
• KL special forms.
• Partial application.
• Implicit recur.
• Simple Java inter-op (based on Clojure's syntax).
  • This is pretty broken after changes to the number system, plan to revisit this entire area properly, see the road map below.
• Dominik's tests from Shen to Clojure.
• The REPL.
• Pre-compilation of the .kl to .class files.
  • It speeds up start-up of the REPL by a factor of 2-3, but preferably I would like to avoid this step.
• The Shen test suite passes.
• Different bootstrap methods for invoke, apply and symbols. Evolving.
• SwitchPoints for symbols - used when redefining functions.
• Cons as persistent collection vs. cons pairs.
• Recompilation of fns based on Shen types or runtime values.
  • This is primarily to narrow types down to primitives, but not sure typing Object arguments matter - all calls are linked via indy anyway.
• long reused as double via doubleToLongBits and a tag, as guards on primitives seems to require boxing.
  • 63 bit precision. bit 0 is a tag that's either 0 for double or 1 for long.
  • This is highly experimental, arithmetic with tagged longs is faster than boxed Java, doubles on par.
  • There's some wonderful potential inlining issue making the first branch taken (long vs. double) faster, and potentially destroys performance of the other one.
  • I think there's some fundamental piece of InvokeDynamic and primitives I don't understand that led me down this road.
  • Would obviously prefer to use real doubles.

Road Map

This is bound to change as we go:

• Saner choice of target method. Currently this is done by a mix of instanceof guards and earlier also fallback to ClassCastException. It's really only used for built-ins.
• Proper arithmetic. Shen.java uses long and double, but currently there's probably a lot of boxing going on. Currently experimenting with long only, see the section above.
• Performance. My use of invokedynamic is pretty naive so far, so there's a lot of work to be done here.
• Revisit how call sites are built and cached, see above.
• Proper Java inter-op. Potentially using Dynalink.
• Reader macros/extension for edn to support embedded Clojure-like maps/sets.
• Persistent collections for the above.
• JSR-223 script engine
• Investigate Clojure(Script) -> K Lambda.

References

The Book of Shen Mark Tarver, 2012

LISP in Small Pieces Christian Queinnec, 1996 "The aim of this book is to cover, in widest possible scope, the semantics and implementations of interpreters and compilers for applicative languages."

Performance and Evaluation of Lisp Systems Richard P. Gabriel, 1985

Asm 4.0 Eric Bruneton, 2007-12 -"A Java bytecode engineering library"

JDK 8 with Lambda support

InvokeDynamic - You Ain't Seen Nothin Yet Charles Nutter, 2012

JSR292 Cookbook | video Rémi Forax, 2011

Scheme in one class John Rose, 2010 - Parts of this looks pretty similar actually! Slightly more advanced/complex, has Java interop but no lambdas. Haven't been updated from the older java.dyn package. "semi-compiled" to MHs, no ASM used.

Optimizing JavaScript and Dynamic Languages on the JVM Marcus Lagergren and Staffan Friberg, 2012

Nashorn Jim Laskey et al, 2012 "ECMAScript 5.1 that runs on top of JVM."

Dynalink Attila Szegedi, 2010-12 "Dynamic Linker Framework for Languages on the JVM"

Invokedynamic them all Rémi Forax, 2012

Golo, a lightweight dynamic language for the JVM Julien Ponge, 2013 - "Golo is a simple dynamic, weakly-typed language for the JVM. Built from day 1 with invokedynamic."

Runtime metaprogramming via java.lang.invoke.MethodHandle Miguel Garcia, 2012 - The idea of building the AST from MethodHandles without using ASM did occur to me, and looks like it could be possible. Not sure you can actually create a fn definition though (see above). Did a spike, doesn't seem easy/worth the hassle, may revisit.

Patterns and Performance of InvokeDynamic in JRuby Hiroshi Nakamura, 2012

InvokeDynamic: Your API for HotSpot Tony Arcieri, 2012

Invokedynamic and JRuby Ola Bini, 2011 - Last time I met Ola he said that he considered to go back to C for his next language VM.

Dynamate: A Framework for Method Dispatch using invokedynamic Kamil Erhard, 2012

A Lisp compiler for the JVM Anton Kindestam, 2012

License

http://shenlanguage.org/license.html

Shen, Copyright © 2010-2012 Mark Tarver

Shen.java, Copyright © 2012-2013 Håkan Råberg

---

YourKit is kindly supporting open source projects with its full-featured Java Profiler. YourKit, LLC is the creator of innovative and intelligent tools for profiling Java and .NET applications. Take a look at YourKit's leading software products: YourKit Java Profiler and YourKit .NET Profiler.