functional-programming# What is the most minimal functional programming language?

What is the most minimal functional programming language?

Solution

It depends on what you mean by minimal.

To start with, the ancestor of functional languages is, first and foremost, **mathematical logic**. The computational use of certain logics came after the fact. In a sense, many mathematical systems (the cores of which are usually quite minimal) could be called functional languages. But I doubt that's what you're after!

Best known is Alonzo Church's lambda calculus, of which there are variants and descendants:

The simplest form is what's called the

**untyped lambda calculus**; this contains nothing but lambda abstractions, with no restrictions on their use. The creation of data structures using only anonymous functions is done with what's called**Church encoding**and represents data by fundamental operations on it; the number 5 becomes "repeat something 5 times", and so on.Lisp-family languages are little more than untyped lambda calculus, augmented with atomic values, cons cells, and a handful of other things. I'd suspect Scheme is the most minimalist here, as if memory serves me it was created first as a teaching language.

The original purpose of the lambda calculus, that of describing logical proofs, failed when the untyped form was shown to be inconsistent, which is a polite term for "lets you prove that false is true". (

*Historical trivia: the paper proving this, which was a significant thing at the time, did so by writing a logical proof that, in computational terms, went into an infinite loop.*) Anyway, the use as a logic was recovered by introducing**typed lambda calculus**. These tend not to be directly useful as programming languages, however, particularly since being logically sound makes the language not Turing-complete.However, similarly to how Lisps derive from untyped lambda calculus, a typed lambda calculus extended with built-in recursion, algebraic data types, and a few other things gets you the extended ML-family of languages. These tend to be pretty minimal at heart, with syntactic constructs having straightforward translations to lambda terms in many cases. Besides the obvious ML dialects, this also includes Haskell and a few other languages. I'm not aware of any especially minimalist typed functional languages, however; such a language would likely suffer from poor usability far worse than a minimalist untyped language.

So as far as lambda calculus variants go, the pure untyped lambda calculus with no extra features is Turing-complete and about as minimal as you can get!

However, arguably more minimal is to eliminate the concept of "variables" entirely--in fact, this was originally done to simplify meta-mathematical proofs about logical systems, if memory serves me--and use only higher-order functions called **combinators**. Here we have:

Combinatory logic itself, as originally invented by Moses Schönfinkel and developed extensively by Haskell Curry. Each combinator is defined by a simple substitution rule, for instance

`Sxyz = xz(yz)`

. The lowercase letters are used like variables in this definition, but keep in mind that combinatory logic itself doesn't use variables, or assign names to anything at all. Combinatory logic is minimal, to be sure, but not too friendly as a programming language. Best-known is the**SK**combinator base. S is defined as in the example above; K is`Kxy = x`

. Those two combinators alone suffice to make it Turing-complete! This is almost frighteningly minimal.Unlambda is a language based on SK combinators, extending it with a few extra combinators with special properties. Less minimal, but lets you write "Hello World".

Even two combinators is more than you need, though. Various one-combinator bases exist; perhaps the best known is the

**iota Combinator**, defined as`ιx = xSK`

, which is used in a minimalist language also called IotaAlso of some note is Lazy K, which is distinguished from Unlambda by not introducing additional combinators, having no side effects, and using lazy evaluation. Basically, it's the Haskell of the combinator-based-esoteric-language world. It supports both the SK base, as well as the iota combinator.

Which of those strikes you as most "minimal" is probably a matter of taste.

- How to implement db capability approach with pure functions in F#?
- Find a pair of integers from an array that sums up to a given number in Java 8 using functionals
- How to join array of optional integers to string?
- Which functions in Array.prototype are pure function in Javascript
- Is this property of a functor stronger than a monad?
- How do I make a minimal working example for the a DBus server?
- unfamiliar syntax in Haskell / Clash function type signature
- How to debug with PureScript?
- Generic Map function in Golang
- Learning functional/Clojure programming - practical exercises?
- Python functional method of checking that all elements in a list are equal
- What is the proper way of wrapping an Int (not a general type) in another type if type safety is the only motive?
- javascript fold reduce functional programming
- Typescript types for a pipe() function
- Can you explain closures (as they relate to Python)?
- Zipping streams using JDK8 with lambda (java.util.stream.Streams.zip)
- Unable to understand the strange "where" syntax in Haskell / Clash
- Codensity and ContT
- Python fluent filter, map, etc
- functional programming in python - using map(), filter(), and sum() together - java .stream() equivalent?
- Haskell foldr1 lambda function which adds tuple values
- How can I get the nested keys of a map in clojure?
- How do I use System.Console.ANSI to wrap a String in escape sequences for getting it colored in the terminal?
- Flux.switchIfEmpty - what if it doesn't switch when first Flux is completed?
- Does Raku has a data type for encoding side effects as pure values?
- Does Rust has a data type for encoding side effects as pure values?
- Getting the underlying type of slice passed as type argument to a type parameter in the receiver of a method
- Why is immutability so important (or needed) in JavaScript?
- fp-ts - how to reverse curried function order
- Can I have a monitor in XMobar that keeps state form one invocation to the next?