When I was learning Scheme), I was told that Scheme is a expressive language, because it can implement higher order function, closure, and even OOP.

Now I am learning javascript, and I find that JS is can be even more expressive than scheme. First, you can write C-style code in JS, which is difficult, or impossible in scheme. Moreover, JS has scheme’s functional programming behavior, and it can also implement higher order function, closure, and even OOP.

Let’s implement a Scheme’s classic example: print all permutation of a set of numbers

We start from simulating Pair and List in scheme, then implement operations on list, and finally implement “perm” operation. All implementations are following the way they implemented in scheme style (use recursions instead of loops).

An impressive example of scheme is it’s higher order function, which takes functions as arguments, or return functions. Higher order function is a more general function, and an good example is memoization.

Memoization is one implementation of Dynamic Programming: it keeps DP formula’s recursive style in code, which is easy to understand, while avoid repeated calculations by memorize all result for each states.

All memoizations have similar format:

Although all memoization code looks similar, we need to rewrite all code from scratch every time in languages like C. However, if we can use higher order function, memoization can be generalized into a template, where we only need to pass recursive formula and base case into it, and the higher order function handle the rest automatically.

The higher order memoization can be implemented in lines of code in js. base argument is a function that returns answer inly on base case parameters, while return undefined otherwise. _dp_ is function that implement dp formula using recursive calls.

Some interesting examples:

DP functions can also call each other:

Javascript is also able to do “currying”. Currying is how Haskell handle functions: “+” is a function takes 2 arguments, return the sum; “1+” is a function takes 1 arguments x, return x+1. That is to say, if you pass function with partial arguments in Haskell, you will get a function taking the rest arguments, and return the result with complete arguments.