Rel4tion-Wiki/projects/lambda.mdwn

# Intro

I made releases of SGP and Sif, and soon I'll get Tosaf ready for its first
release. When that happens, the minimal C++ toolset needed for
[[Release 0|/roadmap]] will be ready for first use. The next step will involve
the semantic components, such as Dilosi and Saugus.

For a while I've been considering to write them, and the system in general, in
a functional language. Instead of C++ as I've been doing so far. Since the
semantic components don't have much serious code yet, I want to examine the
situation carefully make an educated decision. If I choose functional I'll use
whatever conventions that language uses for module loading, error handling and
so on.

In this page I'm going to document my findings, thoughts and ideas. Functional
languages, APIs, compilers and examples of existing software.

# Info

First, a list of functional programming languages I know.

- Common Lisp
- Emacs Lisp
- Scheme
- Racket
- ML (?)
- Haskell
- Mercury (?) - logical with functional support

Now let's start. What is functional programming?

- [[!wikipedia Functional_programming]]
- <https://he.wikipedia.org/wiki/תכנות_פונקציונלי>
- [[!wikipedia Functional_logic_programming]]

Languages:

- [[!wikipedia Common_Lisp]]
- [[!wikipedia Scheme_(programming_language) desc=Scheme]]
- [[!wikipedia Clojure]]
- [[!wikipedia Racket_(programming_language) desc=Racket]]
- [[!wikipedia Erlang_(programming_language) desc=Erlang]]
- [[!wikipedia OCaml]]
- [[!wikipedia Standard_ML]]
- [[!wikipedia Haskell_(programming_language) desc=Haskell]]
- [[!wikipedia F_Sharp_(programming_language) desc=F#]]

Functional style is also supported in or possible with:

- [[!wikipedia Perl]]
- [[!wikipedia PHP]] (especially/at least since 5.3)
- [[!wikipedia C_Sharp_(programming_language) desc=C#]] 3.0
- [[!wikipedia Java_programming desc=Java]] 8
- [[!wikipedia Scala_(programming_language) desc=Scala]]
- [[!wikipedia C++11]]
- [[!wikipedia C++]] meta-programming with templates

First thoughts:

- Haskell is the most recent result of a standard for functional programming
  research, so it may be a good option.
- Scheme is older, but compiled Scheme with all the needed libraries and access
  may work too.
- I remember using OCaml programs such as Unison and some simple graph editor,
  so check OCaml too (and standard ML).
- What are Clojure and Erlang and F#? Are they relevant?
- Do I need functional logic? What does Mercury's code look like?
- Go over these languages' pages and see what influenced them, what they
  influenced etc. as a way to find more interesting languages to examine
- What about efficiecy? In general and specifically for working with a database
  like my case. Maybe write the DB in C/C++ and then everything else in
  functional?

Findings:

- For working with large arrays, multi dimensional DBs, etc. it seems that the
  J language and NumPy may peform better than the other options. But this is too
  early to optimize and perhaps conceptually wrong - why should a different
  style be chosen just because of super-low-level hardware design details? Also
  remember it's a personal system/desktop database, not a terabyte-huge one.
  Another option is to implement the trees, caches, etc. in C/C++ and then
  access them from functional style code.
- [[!wikipedia Software_transactional_memory]] can help with the database access
  related part. A Haskell implementation exists.

About languages - from Wikipedia:

- Clojure: General-purpose programming language with an emphasis on functional
  programming. It runs on the Java Virtual Machine, Common Language Runtime, and
  JavaScript engines. Like other Lisps, Clojure treats code as data and has a
  macro system. Its focus on programming with immutable values and explicit
  progression-of-time constructs are intended to facilitate the development of
  more robust programs, particularly multithreaded ones.
- Elixir: Functional, concurrent, general-purpose programming language built
  atop the Erlang Virtual Machine (BEAM). Elixir builds on top of Erlang to
  provide distributed, fault-tolerant, soft real-time, non-stop applications but
  also extends it to support metaprogramming with macros and polymorphism via
  protocols.
- Erlang: General-purpose concurrent, garbage-collected programming language and
  runtime system. The sequential subset of Erlang is a functional language, with
  eager evaluation, single assignment, and dynamic typing. It was designed by
  Ericsson to support distributed, fault-tolerant, soft-real-time, non-stop
  applications. It supports hot swapping, so that code can be changed without
  stopping a system. While threads require external library support in most
  languages, Erlang provides language-level features for creating and managing
  processes with the aim of simplifying concurrent programming. Though all
  concurrency is explicit in Erlang, processes communicate using message passing
  instead of shared variables, which removes the need for explicit locks (a
  locking scheme is still used internally by the VM).
- F#: Strongly typed, multi-paradigm programming language that encompasses
  functional, imperative, and object-oriented programming techniques. F# is most
  often used as a cross-platform CLI language, but can also be used to generate
  JavaScript and GPU code.
- Haskell: Standardized, general-purpose purely functional programming language,
  with non-strict semantics and strong static typing.
- Julia: High-level dynamic programming language designed to address the
  requirements of high-performance numerical and scientific computing while also
  being effective for general purpose programming. Distinctive aspects of
  Julia's design include having a type system with parametric types in a fully
  dynamic programming language, and adopting multiple dispatch as its core
  programming paradigm. It allows for parallel and distributed computing, and
  direct calling of C and Fortran libraries without glue code. Julia is garbage
  collected by default and unlike other functional languages that use lazy
  evaluation Julia uses eager evaluation (with the package Lazy.jl providing
  "cornerstones of functional programming - lazily-evaluated lists and a large
  library of functions for working with them") and includes efficient libraries
  for floating point, linear algebra, random number generation, fast Fourier
  transforms, and regular expression matching.
- Mercury: Functional logic programming language geared towards real-world
  applications. It was initially developed at the University Of Melbourne
  Computer Science department under the supervision of Zoltan Somogyi. The first
  version was developed by Fergus Henderson, Thomas Conway and Zoltan Somogyi
  and was released on April 8, 1995. Mercury is a purely declarative logic
  language. It is related to both Prolog and Haskell. It features a strong,
  static, polymorphic type system, as well as a strong mode and determinism
  system.
- OCaml: ML-derived languages are best known for their static type systems and
  type-inferring compilers. OCaml unifies functional, imperative, and
  object-oriented programming under an ML-like type system. This means the
  program author is not required to be overly familiar with pure functional
  language paradigm in order to use OCaml. OCaml features: a static type system,
  type inference, parametric polymorphism, tail recursion, pattern matching,
  first class lexical closures, functors (parametric modules), exception
  handling, and incremental generational automatic garbage collection.
- Scala: Object-functional programming language for general software
  applications. Scala has full support for functional programming and a very
  strong static type system. This allows programs written in Scala to be very
  concise and thus smaller in size than other general purpose programming
  languages. Many of Scala's design decisions were inspired by criticism over
  the shortcomings of Java. Scala source code is intended to be compiled to Java
  bytecode, so that the resulting executable code runs on a Java virtual
  machine. Java libraries may be used directly in Scala code, and vice versa.
  Like Java, Scala is object-oriented, and uses a curly-brace syntax reminiscent
  of the C programming language. Unlike Java, Scala has many features of
  functional programming languages like Scheme, Standard ML and Haskell,
  including currying, type inference, immutability, lazy evaluation, and pattern
  matching. It also has an advanced type system supporting algebraic data types,
  covariance and contravariance, higher-order types, and anonymous types. Other
  features of Scala not present in Java include operator overloading, optional
  parameters, named parameters, raw strings, and no checked exceptions.
- Ruby: Dynamic, reflective, object-oriented, general-purpose programming
  language. According to its authors, Ruby was influenced by Perl, Smalltalk,
  Eiffel, Ada, and Lisp. It supports multiple programming paradigms, including
  functional, object-oriented, and imperative. It also has a dynamic type system
  and automatic memory management.
- Rust: General purpose, multi-paradigm, compiled programming language developed
  by Mozilla Research. It is designed to be a "safe, concurrent, practical
  language", supporting pure-functional, concurrent-actor,
  imperative-procedural, and object-oriented styles. The goal of Rust is to be a
  good language for the creation of large client and server programs that run
  over the Internet. This has led to a feature set with an emphasis on safety,
  control of memory layout and concurrency. Performance of safe code is expected
  to be slower than C++ if performance is the only consideration, but to be
  comparable to C++ code that manually takes precautions comparable to what the
  Rust language mandates.
- Scheme: Functional programming language and one of the two main dialects of
  the programming language Lisp. Unlike Common Lisp, the other main dialect,
  Scheme follows a minimalist design philosophy specifying a small standard core
  with powerful tools for language extension.

What sounds good, after reading:

- Haskell
- OCaml
- Scheme

Also, it looks like there are many languages I can use in place of C++. For
example Go. But first, let's understand the nature of the problem. How do
databases even work? What is Software Transactional Memory, and do databases use
it? *Can* they use it? How does my query model work exactly and how queries can
be efficiently executed? Before I can provide good answers, here are the tasks:

- Understand better how DBs work by reading (e.g. my DB course slides)
- Look at the source code of:
  + SQLite
  + 4store
  + Redland
  + Haystack (unlike the rest, this is semantic desktop per definition)
- Understand better my requirements and make progress with Smaoin and Naya

Before that I'd like to make a first release of [[/projects/Tosaf]].

# Learning Haskell

There are several good Haskell learning books on the web, but not all of them
are free culture works. Money is driving some people to use NC licenses. I
wonder if selling a book makes more profit than taking donations for a free
culture book. Anyway, the point is we want to support free culture! Three of
the common licenses for free culture works are:

- CC by (requires just attribution, somewhat like BSD/MIT for software)
- CC by-sa (also requires share-alike, somewhat like GPL for software)
- CC0 (which is basically public domain)

Here are resources I checked which are free culture work and you can learn
Haskell using them (or ask people to liberate their nonfree work):

- Haskell wikibook

I'm collecting useful links and other info while learning Haskell and making
first steps. See [[here|/people/fr33domlover/haskell]].