Functional Programming, Type Systems, and LISP

This post is a personal summary after reading Multiparadigm Programming (by Yoo In-dong).

Type Inference, Function Types, and Generics

Using TypeScript, you can write safe code without explicit type declarations through type inference, and implement complex functional patterns using higher-order functions and generics.

Type Inference

TypeScript's type inference is a feature that allows the TypeScript compiler to automatically infer the types of variables, functions, expressions, etc., without explicit type declarations.

let a = 10; // Infers the type of a as number from the value 10
let message = "Hello TypeScript!" // Infers as string type

const selected = true; // Since const cannot be reassigned, the type is inferred as true
let checked = true; // Since it's declared with let and can be reassigned, it's inferred as boolean


function add(a: number, b: number) {
  return a + b; // Return type is not explicitly specified, but inferred as number from a and b
}


// Object literal property types can also be inferred
let user = {
  name: "Marty",
  age: 30
}

user.name; // string
user.age; // number


// Function argument types can also be inferred
let strs = ['a', 'b', 'c'];
strs.forEach(str => console.log(str.toUpperCase()));

Type Inference through Generics

When using generic functions in TypeScript, a single function can support various types, resulting in a highly polymorphic function. The actual type of a generic is determined by the type of the argument passed at the time of function call.

function identity<T>(arg: T): T {
  return arg;
}

const a = identity("hi");

const e = identity(new User());

This works the same way not only for basic types like strings but also for objects like User.

Function Types and Generics

TypeScript provides various features to support functional programming, such as higher-order functions, function types, and generics. You can explicitly define function types to clearly express input and output types, and use generics to create widely applicable general-purpose functions. Higher-order functions can infer the parameter types of the functions they receive and flexibly infer types in conjunction with other arguments.

Various Ways to Define Function Types

The most basic method is to specify types for the function's parameters and return value.

function add(a: number, b: number): number {
  return a + b;
}

You can also define various signatures with the same function name using function overloading.

function double(a: number): number;
function double(a: string): string;
function double(a: number | string): number | string {
  if (typeof a === 'number') {
    return a * 2;
  } else {
    return a + a;
  }
}

/* WRONG */
declare function fn(x: unknown): unknown;
declare function fn(x: HTMLElement): number;
declare function fn(x: HTMLDivElement): string;
var myElem: HTMLDivElement;
var x = fn(myElem); // x: unknown, wat?

/* OK */
declare function fn(x: HTMLDivElement): string;
declare function fn(x: HTMLElement): number;
declare function fn(x: unknown): unknown;
var myElem: HTMLDivElement;
var x = fn(myElem); // x: string, :)

You can also create function types to reuse in multiple places.

type Add = (a: number, b: number) => number;
const add: Add = (a, b) => a + b;

The constant function below returns a function that always returns the value received as an argument. This function captures a specific value and returns that value each time it's called.

function constant<T>(a: T): () => T {
  return () => a;
}

const getFive = constant(5);
const ten = getFive() + getFive();

Thanks to generics, it can handle values of any type, and thanks to type inference, it works correctly without explicit type declarations.

Functional Type Systems in Multiparadigm Languages

Functional Higher-Order Functions and Type Systems

The functional higher-order functions we implement using the iterator pattern are centered around iterable data structures, so we can call them iterable helper functions. Now, let's learn about functional type systems in multiparadigm languages while applying type systems to these iterable helper functions.

reduce and Types

The reduce function takes a function and an initial value, iterates through elements while executing the function to calculate an accumulated value, and finally returns the accumulated value.

function reduce<A, Acc>(f: (acc: Acc, a: A) => Acc, acc: Acc, iterable: Iterable<A>): Acc {
  for (const a of iterable) {
    acc = f(acc, a)
  }
  return acc;
}

reduce Function Overload

The built-in Array.prototype.reduce function in JavaScript allows omitting the initial value. Let's support the same specification in our reduce function.

• When there's an initial value, it takes three arguments.
• When the initial value is omitted, it only takes f and iterable. The first element of the iterable becomes the initial value.
• If there's no initial value and an empty array is passed, an error is thrown because the type is not correct.

For this, we need to use function overloading. Function overloading defines multiple signatures but provides only one implementation.

function baseReduce<A, Acc>(
  f: (acc: Acc, a: A) => Acc, acc: Acc, iterator: Iterator<A>
): Acc {
  while (true) {
    const { done, value } = iterator.next();
    if (done) break;
    acc = f(acc, value);
  }
  return acc;
}

// (1)
function reduce<A, Acc>(
  f: (acc: Acc, a: A) => Acc, acc: Acc, iterable: Iterable<A>
): Acc;
// (2)
function reduce<A, Acc>(
  f: (a: A, b: A) => Acc, iterable: Iterable<A>
): Acc;
function reduce<A, Acc>(
  f: (a: Acc | A, b: A) => Acc, 
  accOrIterable: Acc | Iterable<A>, 
  iterable?: Iterable<A>
): Acc {
  if (iterable === undefined) { // (3)
    const iterator = (accOrIterable as Iterable<A>)[Symbol.iterator]();
    const { done, value: acc } = iterator.next();
    if (done) throw new TypeError("'reduce' of empty iterable with no initial value");
    return baseReduce(f, acc, iterator) as Acc;
  } else { // (4)
    return baseReduce(f, accOrIterable as Acc, iterable[Symbol.iterator]());
  }
}

The function signature parts (1, 2) and implementation parts (3, 4) can be explained as follows:

1. Takes a function f that receives an accumulated value and initial value, an initial value acc (Acc), and an iterable (Iterable<A>) as arguments. Returns a value of type Acc.
2. Takes a function f that receives two values and an iterable (Iterable<A>) as arguments. Uses the first element of the iterable as the initial value to calculate the accumulated value and returns a value of type Acc.
3. If the last argument iterable is missing, the second argument accOrIterable becomes the iterable.
4. If all three arguments are received, the second argument accOrIterable is the initial value.

Multiparadigm Languages and Metaprogramming - From LISP

The examples in this section examine the process of creating flexible and highly extensible abstractions by combining various language features such as generics, first-class functions, classes, and iterable protocols. Through this, let's gain an experience as if extending the language itself by implementing code expressiveness enhancement and runtime feature modification that might be obtained from metaprogramming.

Pipe Operator

Code like the following is not very readable because you have to read it from the bottom right to the top left.

forEach(printNumber,
  map(n => n * 10,
    filter(n => n % 2 === 1,
      naturals(5))));

LISP has excellent strengths in terms of lazy evaluation and metaprogramming, so developers can create their own pipe functions to solve this problem.

Also, some languages already support the Pipe Operator to alleviate readability issues.

naturals(5)
  |> filter(n => n % 2 === 1, %)
  |> map(n => n * 10, %)
  |> forEach(printNumber, %)

Combining Classes, Higher-Order Functions, Iterators, and Type Systems

Let's directly solve the readability problem by appropriately combining object-oriented paradigm classes, iterables, functional functions, and type systems.

Extending Iterable with a Generic Class

Let's create a class that extends Iterable. We define it as a generic class by writing FxIterable<A> and have it internally have an iterable property.

class FxIterable<A> {
  constructor(private iterable: Iterable<A>) {}
}

Now let's add various higher-order functions as methods to this generic class.

Adding a map Method to FxIterable<A>

function* map<A, B>(f: (a: A) => B, iterable: Iterable<A>): IterableIterator<B> {
  for (const a of iterable) {
    yield f(a);
  }
}

class FxIterable<A> {
  constructor(private iterable: Iterable<A>) {}

  map<B>(f: (a: A) => B): FxIterable<B> {
    return new FxIterable(map(a => f(a), this.iterable));
  }
}

const mapped = new FxIterable(['a', 'b']) 
  .map(a => a.toUpperCase())             
  .map(b => b + b);

The map method creates an iterable iterator by applying map(f) to this.iterable, then creates and returns an FxIterable<B>. Instances of the FxIterable class can execute map consecutively in a chaining manner.

You can make it more concise by adding a helper function as follows:

function fx<A>(iterable: Iterable<A>): FxIterable<A> {
  return new FxIterable(iterable);
}

const mapped2 = fx(['a', 'b'])
  .map(a => a.toUpperCase())
  .map(b => b + b);

Creating a reduce Method

As implemented earlier, reduce should support two calling methods through method overloading. Method overloading in TypeScript is handled in the same way as function overloading.

class FxIterable<A> {
  constructor(private iterable: Iterable<A>) {}

  // ... 

  reduce<Acc>(f: (acc: Acc, a: A) => Acc, acc: Acc): Acc;
  reduce<Acc>(f: (a: A, b: A) => Acc): Acc;
  reduce<Acc>(f: (a: Acc | A, b: A) => Acc, acc?: Acc): Acc {
    return acc === undefined
      ? reduce(f, this.iterable) // (3)
      : reduce(f, acc, this.iterable); // (4)
  }
}

Learning from LISP (Clojure) - Code is Data, Data is Code

LISP is famous for its long history and unique syntax. The biggest feature of LISP is the concept that 'code is data and data is code'. This allows the syntax of programming languages to be expressed and manipulated as data structures.

In this section, let's learn about the basic concepts of LISP, macros, metaprogramming, etc., using Clojure, a LISP family language, as an example.

Clojure

Clojure is a functional programming language developed by Rich Hickey in 2007 and belongs to the LISP family. It runs on the JVM and can easily call Java libraries along with LISP language characteristics. It supports functional programming, immutability, concurrency, etc. Clojure also treats code and data the same way.

S-Expressions

LISP's S-expressions refer to list-form syntax expressions.

(+ 1 2) ;; Code that adds 1 and 2, and simultaneously data in list form

• First element: Operator (function) +
• Remaining elements: Operands 1 and 2

In LISP family languages, function calls are made in list structures, with the first element being the function and the remaining elements being arguments.

When map Executes in Clojure

(map #(+ % 10) [1 2 3 4])

This code works as follows:

• First element: Function map
• Second element: Anonymous function
  • A function that adds 10 to the current element
• Third element: Vector
  • In Clojure, [] means a vector, () means a list

#(+ % 10) is expanded by the reader macro into an anonymous function of the form (fn [x] (+ x 10)). Since function definitions in Clojure are also expressed as lists, the function definition syntax itself can be treated as 'code and data structure'.

Extracting the First Two Values

The following code is an example of extracting the first two values from the result of map using let and destructuring.

v(let [[first second] (map #(+ % 10) [1 2 3 4])]
  (println first second))
;; 11 12

map is lazily evaluated, so elements are only calculated when actually needed.

In LISP family languages, code is expressed in list form, and lists are just simple data structures until they are evaluated. Only when the evaluation process begins is the list interpreted and executed as actual function calls or logic. For example, the anonymous function (fn [x] (+ x 10)) is also a 'code' that has not yet been evaluated and a 'value' composed in list form.

This way of treating code and data in the same form and evaluating them progressively when needed is one of the characteristics and strengths of LISP family languages.

Creating User-Made Code and Classes as Lists in Multiparadigm Languages

Let's extend the FxIterable class to have the same time complexity and expressiveness as code made with Clojure.

The answer is simple: make FxIterable a value that follows the iteration protocol.

class FxIterable<A> {
  constructor(private iterable: Iterable<A>) {}
  
  [Symbol.iterator]() {
    return this.iterable[Symbol.iterator]();
  }
  
  // ...
}

const [first, second] = fx([1, 2, 3, 4]).map(a => a + 10);
console.log(first, second); // 11 12

This way, the operation of adding 10 is executed only twice to extract two values.

LISP's Extensibility - Macros and Metaprogramming

In LISP family languages, macros are not simple text substitutions but can be considered functions that take code in list form as input and return code in list form.

Let's take the famous example of the unless macro:

(defmacro unless [test body]
  `(if (not ~test) ~body nil))

Looking at the unless definition, test and body are 'code-form arguments' passed to the macro. In function calls, arguments are evaluated first and then passed to the function, but in macros, arguments are given in their 'original code form' without being evaluated.

This means that the unless macro receives test and body like function arguments but treats them as code structures themselves without executing their values.

Macros play a role in reconstructing code fragments to emit new code at compile time. This allows developers to easily extend, which is one of the powerful metaprogramming abilities of LISP family languages.

Language Extension Implemented through Collaboration of Code, Objects, and Functions

We went through a process of securing a high level of abstraction and flexibility, as if extending the language, through close collaboration of imperative syntax destructuring assignment, object-oriented design pattern method chaining pattern, and functional higher-order functions mediated by the iteration protocol.

const [first, second] = fx([1, 2, 3, 4, 5, 6])
  .map(a => a + 10)
  .reject(isOdd);

In addition, concepts and features such as imperative code generators, object-oriented pattern iterators, first-class functions, classes, generics, and type inference interact with each other, containing many values and possibilities.

Also, this code is not an implementation that solves a specific domain or problem but shows a general-purpose aspect that can be used anywhere.

In conclusion, this code is implemented in a multiparadigm way and is simultaneously a general-purpose code that can interact with all features supported by multiparadigm languages.

Conclusion

I had never deeply thought about the fact that various features provided by languages are complexly intertwined with multiple programming paradigms and patterns. Through examples centered on the iterable protocol, I clearly understood how object-oriented, functional, and imperative paradigms work harmoniously.

Now, when encountering new technologies, I think I'll ask deeper questions beyond "how to use it," such as "what paradigm is it based on" and "how does it interact with other patterns."