Pure functional programming languages have dramatically improved lately. Around 2010 functional programming became popular, and Haskell was the most elite language. It was pure and would give you programming super powers. But it was mainly for PhDs. Meanwhile mainstream OOP languages like C++, C#, Java and Typescript stole a lot of functional features and became object oriented functional hybrid languages. This made these languages better, but interest in pure functional programming declined.
Recently Haskell has become simpler, stable, with polished IDEs. Two new pure functional languages Lean 4 and Unison-lang deliver new unique abilities, and a high level of maturity.
Is Pure FP Still Competitive?
Haskell, Lean 4 and Unison are all open source, cross platform and have good IDE support. They are stable and work well with LLMs. They all seem production quality.
A pure functional language has been a Utopian dream
It finally happened. This is a miracle! But the bar for success is much higher today. So I have looked for niches where pure functional languages are better than hybrid languages and here is what I found.
Current Programming Landscape
What is important in computer science today and what are the pain points?
Languages are converging on the same features set
Vibe coding with LLMs is common
Software is complex and has many layers
Cloud computing does not match well with programming languages
The core value of pure functional programming is that you are programming with the power of mathematics, in smaller languages that are easier to reason about. The main issue is that the real world changes. Modelling these changes in pure FP involves keeping track of some history, this can be extra work.
Haskell
Haskell has been a laboratory for developing new ideas in functional programming. This gave it a bad reputation for being too complex, too many language pragmas and dependency hell.
Now Haskell is battle tested on a global scale with a big ecosystem and many libraries. It is the only lazy language, this gives it strong declarative features. IMHO this is Haskell's niche
Haskell finally accesses fields in records using dot as most other languages, and has a modern debugger.
The main compiler is GHC, Glasgow Haskell Compiler. It is amazing and built with 100s of man years of work by the smartest people. This has also made it heavy weight. My Haskell install took 6 GB. Now there is also MicroHs tiny, light weight Haskell compiler that creates small portable programs, it is self hosted and compiles itself in 10 seconds.
Interaction with the world is handled with monads. But monads do not compose well. You can use monad transformers, but that is heavy handed. There is a new algebraic effect library BlueFin that is simple and composable.
Lean 4
Lean 4 is a theorem prover and proof assistant but also dependently typed functional language, close to Haskell. Mathematicians have now started to use Lean 4 to check and develop proofs.
Lean 4 is also used by large language models for reasoning. This is probably the reason that it is well founded by Microsoft.
Formal verification was too expensive for all but the most critical application, but this is much cheaper in Lean 4. There are problems that lend themselves well to mathematical description. E.g. schema development.
I like that the ST monad is represented as mutable variables inside Lean functions. Lean 4 translates to C code, unfortunately not code meant for humans but as an assembly language. Still this is making Lean very portable.
Unison-lang
Unison-lang is truly different from anything I have programmed in. It takes composability to a new level. It does not store programs as text files but as a big hash table. Every function has a hash to executable code. You are programming with fragments, including big fragments. Mind blowing to program without a project and git.
MapReduce for big data was part of the reason that functional programming gained popularity. Unison can run distributed MapReduce natively. Unison Cloud is a new offering, where Unison is the only language you need for cloud computing. BYOC, bring your own cloud.
Cloud programming is the most complex programming environment I have worked in. The cloud is not well integrated with CS concepts and languages. So much glue code, configurations, deployment scripts and new features are added all the time. With a good team you can get everything packed into Terraform and CI/CD pipelines, but that is expensive to maintain, and when somebody adds infrastructure in a web portal that clashes with the Terraform code.
AWS and Azure have their own idiosyncratic way to do cloud computing, it is not easy to break into this for Unison. A big issue in the cloud is permissions, AWS and Azure do that in quite different ways, and I am not sure how well Unison can abstract over that. Still Unison has great ideas for better language integration with cloud computing.
Metric for Comparison
First I wrote a few command line tools, they were all easy in all the languages. Then I ported a small fluid dynamics simulation program from C++20 to Haskell, Lean 4, Unison and TypeScript. The complexity of code was similar in all languages, except for C++ that was a little harder.
Language Niches
Pure functional programming will not give you super powers. Sorry 😑
But today they are simple to learn, ergonomic, stable and vibe code friendly. I found these niches where they are better than hybrid languages:
Haskell: Declarative programming, battle tested with big ecosystem
Haskell tooling has improved, but getting an IDE-like setup is still tricky. It took me some trial and error finding a good Haskell environment. I tried 5 modern libraries implementing IDE functionality for Haskell:
Intero
haskell-ide-engine (HIE )
haskell-language-server
Spacemacs Haskell Layer
SpaceVim Haskell Layer
Intero
I had good experience combining Intero and Haskero VS Code plugin. It is not great but I got it to work with syntax highlighting, code completion and goto definitions.
Intero is based on a fork of the GHC compiler and a downside is that Intero is no longer maintained, but it works up till GHC 8.6 the second last version of the GHC compiler.
Intero Installation
Install Stack
Install Intero using Stack
Install the Haskero VS Code plugin
Create a project that is using GHC 8.6
Open VS Code in the project
Creating New Project
stack install intero export PATH=$PATH:~/.local/bin/ stack new myproject --resolver lts-14.27 cd myproject code .
haskell-ide-engine (HIE)
haskell-ide-engine is currently the most advanced IDE project for Haskell. It is using the LSP, the language server protocol that was started on VS Code. HIE should work with editors supporting LSP.
HIE with VS Code
Here is a post about getting HIE working with VS Code on the Mac. It kept crashing on me but recently it has been more stable. Adding a hie.yaml file sometimes helps.
HIE with Neovim
HIE works with Neovim without too much work. Here is what I did:
Install HIE
git clone https://github.com/haskell/haskell-ide-engine --recursive cd haskell-ide-engine stack ./install.hs hie-8.6.5
Install Neovim with LSP Support
I used Neovim 0.5 beta with builtin LSP, language server protocol.
You can also do: brew install neovim
and install vim-lsp coc.
Configure Neovim to Work with HIE
Add the following to your config file:
~/.config/nvim/init.vim
Neovim is more complicated than I like an editor to be. However with LSP integration Vim and Neovim are providing power that justifies a small learning curve.
Programming Haskell in Neovim brings me back to computing in the 1980s, before we had GUI there were still very powerful development environments running in very little memory.
haskell-language-server
The long awaited haskell-language-server is starting to work. I got it to work for a simple GCH 8.6 and GHC 8,8 project. It looks good and is full featured when it works.
Install haskell-language-server
export PATH=$PATH:~/.local/bin git clone https://github.com/haskell/haskell-language-server --recurse-submodules cd haskell-language-server stack ./install.hs help stack ./install.hs hls stack ./install.hs data stack ./install.hs hls-8.6.5
VS Code setting
Integration with VS Code still seems immature.
Problems with Stack and manually edited cabal file
I am using Stack as my build tool, but I also had a manually edited cabal file. When I deleted my cabal file and generated it from package.yaml it worked better.
Spacemacs Haskell Layer
It had a good experience using the Spacemacs Haskell layer.
Install a newer Emacs and install Spacemacs. Press the following four keys to get to the config file: "space" f e d
You should add haskell to the list of layers. Here is my layers list:
There are a few Haskell packages that need to be installed. You can try this:
export PATH=$PATH:~/.local/bin/ stack new myproject --resolver lts-14.27 cd myproject stack install apply-refact hlint hasktags hoogle
git clone git@github.com:jaspervdj/stylish-haskell.git cd stylish-haskell stack install
Doing the install under a project will make it reuse the resolver for that project.
When I did my install, stylish-haskell had an version conflict problem, so I had to do a git clone of stylish-haskell and installed from there instead.
SpaceVim Haskell Layer
It took a little work to get SpaceVim installed on Windows. First I installed Neovim with Scoop:
scoop install neovim
SpaceVim is a configuration for Vim and Neovim. The main idea in SpaceVim is that you hit the space bar and it will show you what options you have.
The Haskell Layer worked quite well and looked good. I used the new Windows Terminal with split screen and a stack build loop in the other pane.
Configure Neovim / SpaceVim
Installing Spacevim Haskell Layer was very easy. Just add these 2 lines to ~/.SpaceVim/init.toml:
[[layers]] name = "lang#haskell"
OS for testing
Libraries should generally be cross platform. This is what I tested on.
OS X and Windows 10
Intero and SpaceVim Haskell layer.
OS X
haskell-ide-engine and Spacemacs Haskell layer.
But they should probably also work on Linux, WSL etc.
Conclusion
Haskell already has an intimidating learning curve. With immature tooling Haskell is a language for language researchers and diehard hackers.
Haskell tooling has gotten much better, but I am spoiled and I prefer to work in an IDE-like environment.
Haskell does not have a first class IDE like IntelliJ for Java, but all libraries provide a pleasant development environment. They are not super stable, and I find myself going back and forth between them depending on the project.
Haskell is now ready for casual users to explore a pure functional language and see if they find mathematical enlightenment.
In 2012 Haskell and Hadoop were the hottest technologies. They had a lot of hype and I loved them. Both were based on functional programming and built on towering abstractions.
Elite functional programmers used Haskell. Serious tech startups had to use big data, meaning Hadoop. Three years later I had learned Haskell and Hadoop and my top advice to startups was:
Don't use Haskell or Hadoop!
They won't you give you a competitive advantage they will just slow you down.
That was my personal experience. For years after that I avoided jobs involving Hadoop, but for the last couple of years I have mainly been working in Hadoop with
Spark. It's now solid and very productive.
I found the productivity increase quite remarkable. Some of it is a textbook example of technology life-cycle, but a some of it comes down to understanding the power and limitation of functional programming.
Modern Programming Paradigms
There are three main modern programming paradigms:
Object oriented
Functional
Declarative
Object oriented programming gives you fine-grained control. Functional programming uses transformations with less control. In declarative programming you just write queries and you have little control. The higher the abstraction the less control.
Essential Hadoop
The breakthrough that Hadoop / MapReduce made was that by using functional programming transformation you could distribute a computation over thousands of computers in a fault tolerant way. This was a monumental achievement, but what made Hadoop the dominant data platform it is today was that it later combined functional with the declarative programming available in Spark SQL, HIVE or PIG.
Combined functional and declarative programming was once the holy grail in computing, but nobody knew how to do it. Today it is ubiquitous and it is free, until you get the bill from your cloud provider.
Essential Haskell
I expected Haskell to be a mathematical version of Python. It was not. If you are trying to do object oriented programming in Haskell it will cause you a lot of pain. Unlike doing OOP in hybrid languages like F#, OCaml or Scala.
The power of Haskell is that it limits you to a small set of basic operations that compose. This allows you to build a big machine out of simple parts. The lazy evaluation makes it natural to work on infinite streams of data. The powerful type system makes it possible to connect small pieces of code in many different dimensions. My metaphor is:
Haskell is an extra dimensional Lego set
Haskell started as a playground for language researchers experimenting. I wanted to play with all these shiny theoretical toys. That was a big time sink and a part of the reason it took me a long time to learn.
Common Problems
One reason I gave up on both Haskell and Hadoop was that it was hard to get things done. Both were beautiful abstractions built on a tower of unstable software libraries. Everything was evolving quickly. This made it hard to keep the libraries underneath on compatible version. Every time your Hadoop distribution was updated your code would break.
In Haskell this problem was called Cabal Hell after the build system Cabal. There were simple solutions. Haskell now has stable versions of libraries that work with each other. It has a modern build system called Stack. Now tooling in both Haskell and Hadoop is quite good.
The Aftermath
I spent more time and effort learning Haskell and Hadoop than any other technologies. With that much effort I expected them to give me superpowers. Instead they slowed me down. This caused a backlash. I felt naive for jumping on the Haskell and Hadoop bandwagon and wasting so much time.
Now 8 years later the dust has settled and part of my problem was that I was an early adapter of immature technologies. Haskell and Hadoop are now mature but inherently complex technologies. They draw their power from giving up fine control. Instead they let you build machines that you can pipe data through.
Big data in the case of Hadoop. Infinite data in the case of Haskell.
Hadoop is highly successful, and is now a cornerstone of data engineering. Even though it is currently standing in the shadow of Spark that was built to run on top of Hadoop infrastructure.
Haskell is a practical programming language well suited for constructive mathematics and category theory, but it is not a better version of Scala. It is pretty successful at number 19 on RedMonk programming language ranking and is used in industry.
This post is a brief status of the state of typed functional languages in late 2019.
Typed
functional languages like Clean, Haskell and OCaml were developed within
academia in the 1990s. Around 2010, languages like F# and Scala were
gaining some acceptance in industry. Today there are many great typed functional languages, several used in industry. I will give a brief side by side introduction to the following languages:
F#
F*
Haskell
OCaml
Rust
Scala
TypeStript
Concepts from typed functional languages have also spread into object oriented languages like C++, C# and Java. The distinction between OOP and typed functional is fluid, so that list might seem a little arbitrary.
These languages are best of breed so the point of this article is not to compare them by merits, but to explore what language to use for what purpose. Follow up post covers F# vs Scala.
F# (F Sharp)
F# is a mature, open source, cross-platform, functional-first programming language.
Core: Strict, strong, inferred, hybrid
Popularity: Some use in industry and backed by Microsoft
Complexity: Easy to learn, but part of a big ecosystem
Maturity: It is 14 years old and part of the .NET, so quite mature
Tooling: Very good
Cross platform: with Mono and .NET Core and JavaScript
IDE: Visual Studio, VS Code
Strengths
Simple, open source, cross platform with good integration with the whole .NET universe.
Well suited for backend programming, Azure, web-serving and finance.
Type providers give easy typed access to a lot of different data sources.
Issues
IDE, GUI programming and LINQ is not as well developed as for C#.
F* (F Star)
F* is a general-purpose functional programming language with effects aimed at program verification.
Maturity: Several researchers are working on it, but it is not used a lot
Tooling: Not super polished, but build on top of good tooling in OCaml and F#
Cross platform: OCaml, F#, C, WASM and ASM
IDE: Support for Emacs
Strengths
F*
has implemented a lot of powerful and interesting ideas that you can
try and actually use. It is a very well developed dependently typed
language.
Good for validating highly sensitive security programs, encryption protocols.
Issues
There is little adaptation and it has not stood the test of time yet.
Haskell
Haskell is an advanced purely-functional programming language.
Core: Lazy, pure, effect tracking using effect monads
Popularity: Prestigious research language with some industry adoption. Number 19 on Red Monk June 2019 list
Complexity: Very complex language
Maturity: It has been around for 30 years, used in industry, used for research
Tooling: New build tool Stack is quite nice
Cross platform: Runs on OS X, Linux and Windows
IDE: Several decent plugins for: VSCode, emacs, Spacemacs, SpaceVim and IntelliJ
Strengths
Very influential research language, test bed for a lot of language research and development.
It has been optimized for years and has some use in industry.
Type classes are built into the language so you can reuse code very broadly.
Aesthetically pleasing if you love math or category theory.
Issues
It is a very complex language and tracking effect in non pure computations is quite hard.
It has some use in industry, but is still very much a research language.
OCaml
OCaml is a strictly evaluated functional language with some imperative features.
Core: Strict, strong, inferred, hybrid
Popularity: Used as teaching language and by a few big companies
Complexity: It is a simple language to learn
Maturity: It has been around for 20 years and is used in industry so quite mature
Tooling: Recently it got a good build tool and package manager
Cross platform: Runs on a lot of different operating system, hardware
IDE: Language server with good integration with Eclipse, VS Code, Emacs and Vim
Strengths
Great REBL, very fast compiler, makes it suited for tooling. Facebook using it for web tooling.
Popular in theorem provers.
Issues
Concurrency is not great.
Rust
TM Mozilla
Rust is a multi-paradigm system programming language focused on safety, especially safe concurrency.
Core: Inferred, linear type, nominal, static, strict, strong, build around concurrency
Popularity: Quite popular and raising. No 21 on Red Monk June 2019 list
Complexity: Somewhat complex language
Maturity: Pretty new language, but used in Firefox and by AWS Firecracker
Tooling: Excellent build tool and package manager
Cross platform: Work on many different OSs
IDE: Good VS Code support
Strengths
Rust
is a combination of ideas from OCaml, Haskell, C++, linear types and
low level imperative control. It is very fast and well suited for system programming
and secure programming. There is no garbage collector and no runtime, this makes Rust great for writing libraries and WebAssembly. Rust has started to make inroads in cloud infrastructure.
Issues
Getting rid of the garbage collector makes the language harder to understand and program in.
It is a pretty new language, still developing, and there are fewer libraries.
Scala
Scala combines object-oriented and functional programming in one concise, high-level language.
Core: Strict and lazy, nominal and structural, hybrid, implicits for IoC
Popularity: Very popular. No 13 on Red Monk June 2019 list. Spark is written in Scala
Complexity: It is a quite complex language, but it is easy to get started with
Maturity: Very stable. Run on JVM, well integrated with JVM ecosystem
Tooling: Great build tool and package managers
Cross platform: JVM and JS. Also early work on native / LLVM version
IDE: IntelliJ, VS Code, Eclipse
Strengths
Back-end programming, data engineering, web serving.
It
is a great all around language. A lot of work has gone into creating
language constructs that makes Scala work well with Java libraries. In
Scala 2.0 this was not the case.
Spark is a cornerstone in data engineering.
Issues
There is quite a lot of complexity: Implicits, macros, type classes / ad hoc polymorphism is possible but it takes some work.
Not super easy to set up a small project.
GUI programming support is not that great.
TypeStript
TypeScript brings you optional static type-checking along with the latest ECMAScript features.
Core: Gradually typed, structural, many new sophisticated type constructs, data language
Popularity: Very popular. No 10 on Red Monk June 2019 list
Complexity: Pretty complex
Maturity: A lot of money has gone into JavaScript, it is improving but it still feels wonky
Tooling: NPM. There are a lot of tools in the Nodes ecosystem, too many
Cross platform: Runs in every browser and on Node.js
IDE: Amazing support in VS Code
Strengths
Typescript makes big JavaScript codebases a lot more robust.
It is really easy to process semi structured data in json.
Starting to see some use of TS in machine learning e.g. with TensorFlow.js.
Issues
The
JavaScript modules seem simple like in Python or Java, but there are
many different module systems and it is pretty complicated. There are a
lot of NPM packages but it still feels less mature. Getting setup with a
small project with unit tests is more work than it should be.
Concurrency: Async await dramatically simplified call back style of programming, but still not great.
Golden Age Programming Languages
For many years I was puzzled about why language evolution
seems to favor bloated and hacky development, while ignoring more principled computer science ideas. Twenty years ago I got very
excited to read about these new functional languages with strong
types. Unfortunately they were only popular in academia.
We are finally living in the golden age of programming languages. It just took some time. Development is moving quickly now and not slowing down.
Apologies in advance for omissions, outdated information and other mistakes.
You can divide functional programming languages into 2 groups: Static and dynamic.
Dynamic functional languages: Clojure, Common Lisp, Racket and Scheme. They have few types often only known at run time.
Statically typed functional languages: F#, ML, Haskell, Idris and Scala. They have advanced types that are known at compile time.
Functional programming languages have similarities but are very different from one another. Some are quite hard to learn. What should you pick?
Slogans
Here are two extreme positions in functional programming reduced to slogans:
Lisp: Everything is Data
Lisp has a great story: Everything is data.
Lisp is homoiconic. There is one datatype: The S-expression in Lisp or an EDN in Clojure. This encodes:
Records
List
Map
Stream
Programs
Everything is unified and first class. This makes Lisp very elastic and adaptable to handle open ended problems like AI. It also leaves a lot of room for mistakes when dealing with complex data structures since everything sticks to everything.
Haskell: Everything is a Computation
Computation sounds like an equally strong unifying foundation. This is a strong counter argument to Lisp.
Haskell turns the world into mathematics by giving strong guarantees and the ability to reason about programs. It is fast, elegant and remarkably safe.
Most of the world is messy so programming in Haskell is both an art and a science.
A Type System is a Must For Production Code
In my experience:
A complex production server application demands a static type system for stability
The type system is doing at least half of my work when I work alone and prevents total anarchy when working in teams.
History of Static and Dynamic Type System
Like many other programmers, I have gone back and forth between preferring static and dynamic languages several times.
C++ and Java
I started using and loving the sophisticated statically typed object oriented languages: C++ and Java.
Why would anybody want to program in Basic?
Perl, Python and Ruby
At some point I had to make a small script for text processing. I realized that dynamically typed languages Perl, Python and Ruby are much simpler and faster to work with.
They borrow a lot of ideas form functional languages and saves you a lot of boiler plate. Programming became fun again.
I never wanted to go back.
F#, Scala and Haskell
Then came the raise of F#, Scala and Haskell.
I thought that you got the best of both worlds:
There are few visible types due to type inference
They look like dynamic language
Still you get strong safety from the invisible type system
They are fast
My stability concern for production application ruled out dynamic languages. The future belongs to F#, Scala and Haskell.
Living with Static Types
For the last 4 years I
have been happy programming in Scala. It really improved my productivity.
I mainly deal with stable data types. Each data structure get immutable case class and they flow beautifully and it even works well in a concurrent system.
I am a little concerned about the amount of black magic going on at the type level in Scala and Haskell.
Web, Scripting and Data Exploration
Some fields continue to be dominated by dynamic languages:
Data exploration
Data science
Scripting
Web front end work in JavaScript, PHP and Ruby
I do data mining in Scala and can quickly add a new data source with unit tests to a stable functional reactive ingestion pipeline, but during a hackaton I had to explore a lot of different data sources and my normal startup time was too slow for the deadline.
Dynamic languages have an edge for small systems.
Problems Using Scala for NLP
Idiomatic Scala has been great for NLP.
I had to extract all the hidden and visible
information on a html page and had to parse the DOM tree for
everything: elements, attributes, code and json data.
The DOM tree is
similar to an S-expression.
The best idiomatic Scala
representation I could find was Play JSON. The DOM tree and Play JSON
are not that similar and processing json in dynamic languages is more
natural than in strongly typed languages.
Dynamic languages have an edge for some complex systems.
Lisp Revisited
I used Lisp in school. It was the cool AI language and my first functional
language. I loved it, it blew my mind but I had a very shallow
understanding.
Impressions from revisiting Lisp after using statically typed functional languages:
Lisp is small and elegant
Easy learning curve
Great at traversing dynamic data
Well suited for exploration
A lot of the principles of statically typed functional programming translate directly
I still think in Scala like types making my Clojure code better organized
Macros feel natural unlike in C++ and Scala
Lisp is really fluid combining in so many crazy ways
You lose a lot of safety
Going from Haskell to Clojure left me with the feeling I had
when moving from C++ to Python. You get a lot of value for less
effort.
Raise of the Gradual Type Systems
There has been slow movement towards gradual types. Here are a few place where they have popped up:
Ambrose Bonnaire-Sergeant on gradual typing in Clojure
The type systems in Typed Clojure and Typed Racket are pretty different than in Scala and Haskell. Generally weaker, but Typed Clojure and Typed Racket have union types that are only now investigated in Scala's experimental new type system Dotty.
These advances in gradual types make it possible to harden Lisp code to improve stability.
Data or Calculation
I was puzzled by the Lisp and Haskell slogans:
Everything is data
Everything is a calculation
It was a paradox. Which is a better foundation for computer science?
I could not easily dismiss either. For now I have accepted that we are stuck with both.
For a long time I suffered from the misunderstanding that F#, Scala
and Haskell are like dynamic languages, with the addition of speed and
safety. But they are fundamentally different.
Functional programming has moved from academia to industry in the last few years. It is theoretical with a steep learning curve. I have worked with strongly typed functional programming for 4 years. I took the normal progression, first Scala then Haskell and ended with category theory.
What practical results does functional programming give me?
I typically do data mining, NLP and back end programming. How does functional programming help me with NLP, AI and math?
Scala
Scala is a complex language that can take quite some time to learn. For a couple of years I was unsure if it really improved my productivity compared to Java or Python.
After 2 years my productivity in Scala went up. I find that Scala is an excellent choice for creating data mining pipelines because it is:
Before Scala I did NLP in Python. I used NLTK the Natural Language Toolkit for 3 years.
NLTK vs. ScalaNLP
NLTK
Easy to learn and very flexible
Gives you a lot of functionality out of the box
Very adaptable, handles a lot of different structured file formats
What I did not like about NLTK was:
It had a very inefficient representation of a text features as a Dictionary
The file format readers were not producing exactly matching structures and this did not get caught by the type system
You have to jump between Python, NumPy and C or Fortran for low level work
ScalaNLP
ScalaNLP merged different Scala numeric and NLP libraries. It is a very active parent project of Breeze and Eric.
ScalaNLP Breeze
Breeze is a full featured, fast numeric library that uses the type system to great effect.
Linear algebra
Probability Distribution
Regression algorithms
You can drop down to the bottom level without having to program in C or Fortran
ScalaNLP Eric
Eric is the natural language processing part of ScalaNLP. It has become a competitive NLP library with many algorithms for several human languages:
Reader for text corpora
Tokenizer
Sentence splitter
Part-of-speech tagger
Named entity recognition
Statistical parser
Video lecture by David Hall the Eric lead
Machine Learning in Scala
The most active open source Scala machine learning library is MLib which is part of the Spark project.
Spark now has data frames like R and Pandas.
It is easy to set up machine learning pipelines, do cross validation and optimization of hyper parameters.
I did text classification and set it up in Spark MLib in only 100 lines of code. The result had satisfactory accuracy.
AI Search Problem in Scala vs. in Lisp
I loved Lisp when I learned it at the university. You could do all these cool Artificial Intelligence tree search problems. For many years I suffered from Lisp envy.
Tree search works a little differently in Scala, let me illustrate by 2 examples.
Example 1: Simple Tree Search for Bird Flu
You have an input HTML page and parsed into a DOM tree. Look for the word bird and flu in a paragraph that is not part of the advertisement section.
I can visualize what a search tree for this would look like.
Example2: Realistic Bird Flu Medication Search
The problems I deal with at work are often more complex:
Given a list of medical websites, search for HTML pages with bird flu and doctor recommendations for medications to take. Then do a secondary web search to see if the doctors are credible.
Parts of Algorithm for Example 2
This is a composite search problem:
Search HTML pages for the words bird and flu close to each other in DOM structure
Search individual match to ensure this is not in advertisement section
Search for Dr names
Find what Dr name candidates could be matched up with the section about bird flu
Web search for Dr to determine popularity and credentials
Visualizing this as a tree search is hard for me.
Lazy Streams to the Rescue
Implementing solutions to the Example 2 bird flu medication problem takes:
Feature extractors
Machine learning on top of that
Correlation of a disease and a doctor
This lends itself well to using Scala's lazy streams. Scala makes it easy to use the lazy streams and the type system gives a lot of support, especially when plugging together various streams.
Outline of Lazy Streams Algorithm for Example 2
Stream of all web pages
Stream of tokenized trees
Steam of potential text matches e.g. avian influenza, H5N1
Filter Stream 3 if it is an advertisement part of the DOM tree, (no Dr Mom)
Stream of potential Dr text matches from Stream 2
Stream of good Dr names. Detected with machine learning
Merge Stream 3 and Stream 6 to get bird flu and doctor name combination
Web search stream for the doctor names from Stream 7 for ranking of result
AI Search Problem in Lisp
Tree search is Lisp's natural domain. Lisp could certainly handle Example 2 the more complex bird flu medication search. Even using a similar lazy stream algorithm.
Additionally, Lisp has the ability to do very advanced meta programming:
Rules that create other rules or work on multiple levels. Things I do not know how to do in Scala.
Lisp gives you a lot of power to handle open ended problems and it is great for knowledge representation. When you try to do the same in Scala you end up either writing Lisp or Prolog style code or using RDF or graph databases.
Some Scala Technical Details
Here are a few observations on working with Scala.
Scala's Low Rent Monads
Monads are a general way to compose functionality. They are a very important organizing principle in Scala. Except is not really monads it is just syntactic sugar.
You give us a map and a flatMap function and we don't ask any questions.
Due to the organization of the standard library and subtyping you can even combine an Option and a List, which should strictly not be possible. Still this give you a lot of power.
I do use Scala monads with no shame.
Akka and Concurrency
Scala's monads make it convenient to work with two concurrency constructs: Futures and Promises.
Akka is a library implementing an Erlang style actor model in Scala.
I have used Akka for years and it is a good framework to organize a lot of concurrent computation that requires communication.
The
type system does not help you with the creation of parent actors so you
are not sure that they exist. This makes it hard to write unit tests
for actors.
Akka is good but the whole Erlang actor idea is rather low level.
Scalaz and Cake Patterns
Scalaz is a very impressive library that implements big parts of Haskell’s standard library in Scala.
Scalaz’s monad typeclass is invariant, which fixes the violations allowed in the standard library.
Cake Patterns allows for recursive modules, which make dependency injection easier. This is used in the Scala compiler.
Both of these libraries got me into trouble as a beginner Scala programmer. I would not recommend them for beginners.
How do you determine if you should use this heavy artillery?
Once you feel that you are spending a lot of time repeating code due to insufficient abstraction you can consider it. Otherwise:
Keep It Simple.
Dependent Types and Category Theory in Scala
There are many new theoretical developments in Scala:
Dotty - a new compiler built on DOT a new type-theoretic foundation of Scala
Cats library - a simplified version of Scalaz implementing concepts from category theory
Shapeless library for dependent types. I am using this in my production code since Shapeless is used in Slick and Parboiled2
Haskell
Haskell is a research language from 1990. In 2008 its popularity started to rise. You can now find real jobs working in Haskell. Most publicized is that Facebook wrote their spam filter in Haskell.
Why is Haskell so Hard to Learn?
It took me around 2 years to learn to program in Haskell, which is exceptionally long. I have spoken to other people at Haskell meetups who have told me the same.
Mathematical Precision
Python effectively uses the Pareto principle: 20% of the features will give give you 80% of the functionality; Python has very few structures in the core language and reuses them.
Haskell uses many more constructs. E.g. exception handling can be done in many different ways each with small advantages. You can chose the optimal exception monad transformer that has least dependencies for your problem.
Cabal Hell and Stack
Haskell is a fast developing language with a very deep stack of interdependent libraries.
When I started programming in it, it was hard to set up even a simple project since you could not get the libraries to compile with versions that were compatible with each other.
The build system is called cabal, and this phenomenon is called Cabal Hell.
If you have been reading mailing list there are a lot of references to Cabal Hell.
The Haskell consulting company FPComplete first released Stackage a curated list of libraries that works together. In 2015 they went further and released Stack which is a system that installs different versions of Haskell to work with Stackage versions.
This has really made Haskell development easier.
Dependently Typed Constructs in Haskell
Dependently typed languages are the next step after Haskell. In
normal languages the type system and the objects of the language are
different systems. In dependently typed languages the objects and the
types inhabits the same space. This gives more safety and greater
flexibility but also makes it harder to program in.
The type checker has to be replaced with a theorem-prover.
You have to prove that the program is correct, and the proofs are part of the program and first order constructs.
Haskell has a lot of activities towards emulating dependently typed languages.
The next version of the Haskell compiler GHC 8 is making a big push for more uniform handling of types and kinds.
Practical Haskell
Haskell is a pioneering language and still introducing new ideas. It has clearly shown that it is production ready by being able to handle Facebook's spam filter.
Aesthetically I prefer terse programming and like to use Haskell for non work related programming.
There is a great Haskell community in New York City. Haskell feels like a subculture where Scala has now become the establishment. That said I do not feel Haskell envy when I program in Scala on a daily basis.
Learning Haskell is a little like running a marathon. You get in good mental shape.
Category Theory
Category theory is often called Abstract Nonsense both by practitioners and detractors.
It is a very abstract field of mathematics and its utility is pretty controversial.
It abstracts internal properties of objects away and instead looks at relations between objects.
Categories require very little structure and so there are categories everywhere. Many mathematical objects can be turned into categories in many different ways. This high level of abstraction makes it hard to learn.
There is a category Hask of Haskell types and functions.
Steve Awodey lecture series on category theory
Vector Spaces Described With a Few String Diagrams
To give a glimpse of the power of category theory: In this video lecture John Baez shows how you can express the axioms of finite dimensional vector spaces with a few string diagrams.
Video lecture by John Baez
With 2 more simple operations you can extend it to control theory.
Quest For a Solid Foundation of Mathematics
At the university I embarked on a long quest for a solid scientific foundation. Fist I studied chemistry and physics. Quantum physics drove me to studying mathematics for more clarity. For higher clarity and a solid foundation I studied mathematical logic.
I did not find clarity in mathematical logic. Instead I found:
Some random badly motivated axioms and inference rules
The Dirty Secret About the Foundation of Mathematics
My next stop was the normal foundation for modern mathematics: ZFC, Zermelo–Fraenkel set theory with the axiom of choice.
This was even less intuitive than logic. There were more non intuitive axioms. This was like learning computer science from a reference of x86 assembly: A big random mess. There were also an uncertain connection between the axioms of logic and the axioms set theory.
ZFC and first order logic makes 2 strong assumptions:
Law of Excluded Middle
Axiom of Choice
Law of Excluded Middle is saying that every mathematical sentence is either true or false. This is a very strong assumption that was not motivated at all. And it certainly does not extend to other sentences.
Constructive Mathematics / Intuitionistic Logic
There was actually a debate about what should be a foundation for mathematics at the beginning of the 20th century.
A competing foundation of mathematics was Brouwer's constructive mathematics. In order to prove something about a mathematical object you need to be able to construct it and via the Curry-Howard correspondence this is equivalent to writing a program constructing a particular type.
This was barely mentioned at the university. I had one professor who once briefly said that there was this other thing called intuitionistic logic, but it was so much harder to prove things in it, why should we bother.
Recently constructive mathematics have had a revival with Homotopy Type Theory. HoTT is based on category theory, type theory, homotopy theory and intuitionistic logic.
This holds a lot of promise and is another reason why category theory is practical for me.
Robert Harper's lectures on type theory end with an introduction to HoTT
Future of Intelligent Software
There are roughly 2 main approaches to artificial intelligence
Top down or symbolic techniques e.g. logic or Lisp
Bottom up or machine learning techniques e.g. neural networks
The symbolic approach was favored for a long time but did not deliver on its promise. Now machine learning is everywhere and has created many advances in modern software.
To
me it seems obvious that more intelligent software needs both. But
combining them has been an elusive goal since they are very different by
nature.
Databases created a revolution in data management. They reduce data
retrieval to simplified first order logic, you just write a logic
expression for what you want.
Dependently typed language is the level of abstraction where programs and logic merge.
I think that intelligent software of the future will be a combination of dependently typed languages and machine learning.
A promising approach is: Discovery of Bayesian network models from data. This finds causality in a form that can be combined with logic reasoning.
Conclusion
I invested a lot of time in statically typed functional languages and was not sure how much this would help me in my daily work. It helped a lot, especially with reuse and stability.
Scala has made it substantially easier to create production quality software.
MLib and ScalaNLP are 2 popular open source projects. They show me that Scala is a good environment for NLP and machine learning.
I am only starting to see an outline of category theory, dependently typed languages and HoTT. It looks like computer science and mathematics are not mainly done, but we still have some big changes ahead of us.
I just saw David Nolen give a talk at a LispNYC Meetup called:
LISP is Too Powerful
It was a provocative and humorous talk. David showed all the powerful features of LISP and said that the reason why LISP is not more used is that it is too powerful. Everybody laughed but it made me think. LISP was decades ahead of other languages, why did it not become a mainstream language?
David Nolen is a contributor to Clojure and ClojureScript.
He is the creator of Core Logic a port of miniKanren. Core Logic is a Prolog-like system for doing logic programming.
When I went to university my two favorite languages were LISP and Prolog. There was a big debate whether LISP or Prolog would win dominance. LISP and Prolog were miles ahead of everything else back then. To my surprise they were both surpassed by imperative and object oriented languages, like: Visual Basic, C, C++ and Java.
What happened? What went wrong for LISP?
Prolog
Prolog is a declarative or logic language created in 1972.
It works a little like SQL: You give it some facts and ask a question, and, without specifying how, prolog will find the results for you. It can express a lot of things that you cannot express in SQL.
A relational database that can run SQL is a complicated program, but Prolog is very simple and works using 2 simple principles:
Unification
Backtracking
The Japanese Fifth Generation Program was built in Prolog. That was a big deal and scared many people in the West in the 1980s.
LISP
LISP was created by John McCarthy in 1958, only one year after Fortran, the first computer language. It introduced so many brilliant ideas:
Minimal syntax, you program in abstract syntax trees
It took other languages decades to catch up, partly by borrowing ideas from LISP.
Causes for LISP Losing Ground
I discussed this with friends. Their views varied, but here are some of the explanations that came up:
Better marketing budget for other languages
Start of the AI winter
DARPA stopped funding LISP projects in the 1990s
LISP was too big and too complicated and Scheme was too small
Too many factions in the LISP world
LISP programmers are too elitist
LISP on early computers was too slow
An evolutionary accident
Lowest common denominator wins
LISP vs. Haskell
I felt it was a horrible loss that the great ideas of LISP and Prolog were lost. Recently I realized:
Haskell programs use many of the same functional programming techniques as LISP programs. If you ignore the parenthesis they are similar.
On top of the program Haskell has a very powerful type system. That is based on unification of types and backtracking, so Haskell's type system is basically Prolog.
You can argue that Haskell is the illegitimate child of LISP and Prolog.
Similarity between Haskell and LISP
Haskell and LISP both have minimal syntax compared to C++, C# and Java.
LISP is more minimal, you work directly in AST.
In Haskell you write small snippets of simple code that Haskell will combine.
In the book The Selfish Gene, evolutionary biologist Richard Dawkins makes an argument that genes are much more fundamental than humans. Humans have a short lifespan while genes live for 10,000s of years. Humans are vessels for powerful genes to propagate themselves, and combine with other powerful genes.
If you apply his ideas to computer science, languages, like humans, have a relatively short lifespan; ideas, on the other hand, live on and combine freely. LISP introduced more great ideas than any other language.
Open source software has sped up evolution in computer languages. Now languages can inherit from other languages at a much faster rate. A new language comes along and people start porting libraries.
John McCarthy's legacy is not LISP but: Garbage collection, functional programming, homoiconicity, REPL and programming in AST.
The Sudden Rise of Clojure
A few years back I had finally written LISP off as dead. Then out of nowhere Rich Hickey single-handedly wrote Clojure.
Features of Clojure
Run on the JVM
Run under JavaScript
Used in industry
Strong thriving community
Immutable data structures
Lock free concurrency
Clojure proves that it does not take a Google, Microsoft or Oracle to create a language. It just takes a good programmer with a good idea.
Typed LISP
I have done a lot of work in both strongly typed and dynamic languages.
Dynamic languages give you speed of development and are better suited for loosely structured data.
After working with Scala and Haskell I realized that you can have a less obtrusive type system. This gives stability for large applications.
There is no reason why you cannot combine strong types or optional types with LISP, in fact, there are already LISP dialects out there that do this. Let me briefly mention a few typed LISPs that I find interesting:
Typed Racket and Typed Clojure do not have as powerful types systems as Haskell. None of these languages have the momentum of Haskell, but Clojure showed us how fast a language can grow.
LISP can learn a lesson from all the languages that borrowed ideas from LISP.
Functional programming is on the upswing, but should you bet your career on it, or is it a short-lived technology fad?
I have long wanted to use functional programming professionally and for the last year I have. Mainly Scala, written in Haskell style, plus some real Haskell programming.
Here is my impression of Scala and Haskell compared to my benchmark language, Python.
Scala
Scala is a functional object oriented hybrid language running on the JVM. It was created by Martin Odersky in 2003. Scala took Java / JVM and organized it nicely according to a few orthogonal principles.
Working in Scala has been a pleasure, there is a lot to like:
You have easy access to the giant world of Java libraries
A monad gives you simple ways of composing different operations. First it seems like an odd principle. Understanding monad took me several months.
In UNIX and OS X you can create complex programs by piping simple commands together. A monad generalizes this a lot.
Once you understand the monad you will see monads pop up in so many places. The monad is an amazingly powerful construct.
The last place I found monads unexpectedly showed up was in asynchronous programming, e.g. used in AJAX.
You send an external request and you do not block but you have a callback for when the result comes back. This is efficient but messy to program especially if you have a chain of requests to process and you have to have a lot of callbacks floating around. You can do this type of calculations using a future / promise, and luckily a future is a monad so you string a long list of operations after each other in a very simple way.
Scalaz
Scalaz is a Scala library that replicates a lot of Haskell constructs, at the cost of being similarly hard to understand.
You can work with monads in Scala without using Scalaz since the "for-statement" in Scala is syntactic sugar for monadic "for-comprehension".
I have programmed Java in a functional style both professionally and for my open source project. It is possible but it is rather verbose and clunky. Scala is much more powerful, simpler and cleaner than both Java approaches, and Scalaz is a big step up from Scala.
When I started programming in Scala I read a really funny blog post called Truth about Scala that describes how a
team starts to use Scala and first they are excited, but it quickly descends into a death spiral of complexity. I was concerned with this and tried
to keep my code as simple as possible and avoid Scalaz for a long
time. I would advise others to become very comfortable with Scala before starting to work with Scalaz.
Haskell
Haskell is a strongly typed, lazy, pure functional programming language. It is an academic research language created by a committee in 1987.
One reason that I got into Haskell was in order to understand monads and applicative functors, they are important constructs in Haskell and category theory.
There is a steep learning curve for Haskell. Maybe it is more like a hump you have to get over. Just getting to basic proficiency is hard. It took me around one year of low intensity studying, but one day it just made sense.
A colleague told me that when he needed a function he would write out its signature and put it into Hoogle and often it would take him to the function that he needed. First time I tried it, and it actually took me to a function that solved a bigger part of the problem than what I was looking for.
When I searched Hoogle for this function signature:
(a -> Bool) -> [a] -> [Int]
I got these results in EclipseFP:
Eclipse Plugin EclipseFP
EclipseFP with Hoogle
The Haskell Eclipse plugin is quite good:
Syntax highlighting
Cabal integration
Hoogle integration
Code completion
Debugger
GHCi integration with automatic reload
Python
Python is a high-level language built on ideas from functional, imperative and object oriented programming. It was created by Guido van Rossum in 1989.
For many years Python was my favorite language. It is a language for kids and also for scientists and a lot of people
in between.
Python is probably the easiest language to learn
It took me a day to learn well enough to use
Very
minimal language
Very terse code
Excellent wrapper language
Many implementations: CPython, Jython (JVM), IronPython (CLR), PyPy
Good bindings to numerical packages: NumPy, SciPy
Used in
computer vision since OpenCV
choosing Python to be its scripting language
Used in natural language processing due to the NLTK
If a kid can understand a technology it is well designed. My daughter is turning 5 and I am thinking about what language I should introduce her to first.
Python
My first inclination was to teach her Python since it is the simplest, but it needs to give immediate visual feedback. Python's lack of a good GUI is a problem.
Haskell
I have also been tempted to show her some Haskell to teach her good habits in a pure and minimal language. But if I tell her that:
"A monad is just a monoid in the
category of endofunctors"
she will walk away or scream.
Scala
Kojo is a LOGO like graphical turtle programming environment written in
Scala. Scala's type inference makes it simpler for kids who will not have a good concept of types.
My daughter plays with Kojo and she likes it. She
comes and asks me if we can do the turtle?
Kojo notice green drawing turtle in the middle
So unexpectedly, Scala, the biggest language, was the most kid friendly language. Based on a very small sample size.
Category Theory
Haskell is using plenty of concepts from category
theory. E.g. the monad. In my quest to understand it I started to study category theory.
Category theory has been called: "Abstract nonsense", both by its practitioners and critics. And for very good reasons. It can suck you into a black hole of abstraction.
Category Theory Introductions
You do not need to understand category theory to program in Haskell or Scalaz, but if it helps you here are a few introduction videos.
Dominic Verity presents a gentle introduction to Category Theory:
Error792's category theory class, currently there are 5 parts
Math and Programming
I have often said that there is no connection between math and programming. The only math you need to program is counting, and occasionally, addition. I felt:
Programmers are the grease monkeys of today
We move some data around and throw it on webpages
After working in Scala and Haskell I have changed my tune:
When you program in Scala you feel like an engineer
When you program in Haskell you feel like a mathematician
Adapting Haskell and Scalaz for a Team
Using Haskell and Scalaz takes a special mindset and a lot of dedication. I have been very lucky to work at a place that has attracted physicists, mathematicians and theoretical CS people.
If a big part of your team does not have these qualities you risk wasting time and chasing developers away.
On the other hand if your team is using Haskell or Scalaz you will attract this brand of developers.
Conclusion
I had high expectations when I started using functional programming full time, but I have been disappointed by new technology many times before. Functional programming met my high expectations. It has been challenging and very enjoyable.
I was a C++ programmer for 8 years, and considered C++ the one true way for high speed, high level programming.
Recently I looked at a code sample written in C++ and it hurts my eyes: Filled with boilerplate and state.
Functional programming is addictive and will make you spoiled
Functional programming is here to stay. It has been an important part of C# since v3.0. It is finally getting added to Java in Java 8 coming out soon. The classic functional languages LISP or ML are the basis of: Clojure and F# that have thriving communities and are used in industry. The time has come to invest some time in understanding functional programming.
Python
I enjoy Scala and Haskell more than Python, but Python seem to be the language that I always go back to. It is a power tool that adds very little weight to your programmer's toolbox. You get high return on investment with Python, while with Scala and especially Haskell you have to invest a lot and for a long time before you break even.
Scala
Scala is now popular enough that you can get a job doing it. Moving from Java or C# to Scala is pretty easy. Since you can start programming
Scala like Java. Scala is a big and complex language with a big
ecosystem and it takes months to get a deeper understanding. Scala is substantially more powerful than Java 7, but Java 8 has supposedly
taken a lot of ideas from Scala.
Haskell
Haskell is definitely the road less traveled, but it is a road, not a trail. It is an academic research language created in 1987. Recently it has started to break into the mainstream. There are a few jobs in Haskell. Gaining basic proficiency in Haskell is quite hard, but afterwards other languages look a little clunky. Writing Haskell feels like doing math.
Scala vs. Haskell
Scala is a safer bet for most programmers, since it is better adapted to more tasks, and you can approximate Haskell pretty well with Scalaz. Scala has a very advanced type system to handle its
object oriented features.
Haskell appeals to functional
language purists, mathematicians and category theorists. Esthetically I prefer Haskell. It is terser and the type inference is better.
In most cases external factors would dictate whether Scala or Haskell would be a better fit for your project.
