Does anyone know why functional programming languages are so much favored by research teams over other types of PL ?
Every time i hear someone doing PL research, it's always on some kind of functional programming language such as Haskell or ML.
There is, however, a lot of research about implementation going on using other languages as well. Most GC research, for example, is done using JVM and Java programs. For this particular paper, it would be really hard to choose a different platform, though, because GHC is one of the rare industrial runtimes that offer lightweight threads.
OO/subtyping is NOT orthogonal to functional, nor is it inherently at odds with formal reasoning. OCaml has both imperative and functional objects; Haskell, Mercury, and Coq (a formal logic language) all support typeclasses, which subsume most of OO and provide subtyping.
Additionally, strong typing has little to do with formal reasoning as well (see: Lisp/Scheme/the lambda calculus). What makes functional languages amenable to formal methods is that they are functional and therefore referentially transparent. Mathematical proofs carry no implicit concept of "state"; hence if you are trying to prove anything about code in, say, C, you need to augment the code with explicit state and remove all non-local effects. (See: the Why language, which attempts to bridge this gap.)
Algebraic/generalized-algebraic type constructors used by most functional languages don't hurt either, as they allow programs to construct complex terms without relying on lower-level stateful abstractions such as memory allocation.
Actually, you just need to augment your model with notions of state, which is standard in operational semantics. It can just be harder to prove things in a complex model, so theorists prefer simplification when possible.
OO subtyping is hard to reason about formally in formal systems designed for FP...news at 11! I jest.
The reason FP does so well academically is that no one knows how to rigorously evaluate something that isn't theoretical (since FP is close to math anyways) or performance-based (most other PL work).
The Haskell crowd is also very creative so they do a lot of cool stuff. However, many of their ideas are transferrable to other languages without the FP ideology.
The OO people have something to offer also, but we've been kind of muted lately.
Well. Even systems like L2 (which are not functional) find subtyping difficult. It becomes difficult in the presence of overloading and overriding.
But the main problem with subtyping, nominative or structural, is how it messes up Hindley-Damas-Milner style type inference. But that shouldn't be surprising that an FP theory for type inference wouldn't work well for OOP.
BTW, Java has lightweight threads, too: https://github.com/puniverse/quasar (I'm the main author)
As far as I see you still use the same, standard JVM threads everyone uses, combined with a thread pool.
What am I missing?
Looking into the actual source code didn't reveal anything “special” either, so I'll just call bullshit on these claims.
Feel free to prove me wrong.
That's like asking why algebra is preferred among mathematicians over randomly pushing operators and parentheses around hoping that it will work this time.
FPL research: Ok, we have this cool way to describe our computation. But how can we efficiently map this to the HW? In essence build a nice language and find an implementation.
Imperative PL research: Ok, we have this HW, how can we build an expressive PL on top of it? In essence build an implementation (the HW) and find a language.
The two language schools you describe seem to be asking whether it is time (whether we have enough capacity) to simply float a new more mathematical world view on top of it all, or whether we should continue to play toward the strengths of the commodity hardware stack.
I personally think that something like Go works for my mind, and the hardware. (I will go make coffee now, rather than "define coffee" and wait for it to appear ;-)
Logic ~ Type theory ~ Functional programming
There's still active research in Fortran i.e. for super computers etc., check out the SIGPLAN Fortran Forum [1]. OOPSLA/SPLASH has lots of non-functional language research [2].
Also check out PLDI, arguably one of the most prestigious PL conferences. Scala, Dart, and LLVM feature in their tutorials section [3].
[1] http://dl.acm.org/citation.cfm?id=J286 [2] http://splashcon.org/2012/program/oopsla-research-papers [3] http://pldi2013.ucombinator.org/tutorials.html
<body><center><table border=0 cellpadding=0 cellspacing=0 width="85%" bgcolor=#f6f6ef>
Most really low level code generation and parsing research etc. will apply across the board or at least cover a wide range of type of languages (e.g. register allocation, instruction selection).
But consider type theory - a language like Haskell providers a lot wider scope for research in that area than e.g. C. Or garbage collection - admittedly that's more widely applicable, but many FP languages throw an extra factor into the mix with immutable variables. Etc.
But there's certainly other PL research as well. E.g. all the work that's gone into Javascript compilers in the last few years. Trace trees came out of work done on a JVM for example.
One thing I'm surprised no one has mentioned is that they found a race condition in epoll that's existed since version 2.4 of the linux kernel.
The state is not event-based in nature but does exist.
Functional programming languages have mechanisms that make this process pure, simple, and efficient and you get the benefits of never mutating an existing value (which is important when several different functions may hold a reference to it, among other reasons).
See also: The Haskell state monad or lenses. Theses are pure mechanisms that Haskell provides to update state without mutating any data.
Edit: In the event that you do need shared mutable state, the Haskell STM (Shared Transactional Memory) monad is your answer.
I would hope one wouldn't need to resort to STM for a compiler, especially since retry is fairly undefined! Still nothing about iterative computation however, I wonder how the ST monad would deal with a Y combinator?
compile :: Source -> Core
optimizer :: Core -> Core
nativeCode :: Core -> AssemblyAlso, how does one encode iterative computation, like a data-flow analysis, in Haskell? And symbol tables? Is it sufficient that the symbol table is encapsulated within compile even if it involves dictionary read/writes? I'm genuinely curious.
type SymbolTable = Map String Symbol
Here's the iterative code:
https://github.com/Peaker/lamdu/blob/master/Lamdu/Data/Expre...
If you need to internally carry state, you just use a State monad to thread around the state purely.