FLASJS Implementation Blog

DOM Access

Since this is JavaScript, can we really do anything without DOM access? Probably not. So this time, I'm going to try and render a trivial, hello-world like page functionally.

To do this, I'm going to introduce a new library, DOM, which has one main type with a single constructor Element which represents a DOM Element with attributes and nested elements. I'm also going to limit myself (for now) to nested elements which are text-ish (JavaScript strings and numbers) or else other Elements.

In a standard notation, this would be something like:

data DOM.Element = Element (String tag) ([(String, String)] attrs) ([Node] contents)
type DOM.Node = DOM.Element | String

There do need to be some caveats, because not all strings are legal tags (you could argue that only the set of HTML4 or HTML5 tags are actually legal), neither are all attribute names.

The code consists of a prelude that gets the right ducks lined up, and then the main code consists of building a structure like this:

e1 = DOM.Element "div" [("id", "k16")] ["hello world", DOM.Element "div" [] []]

(it just takes a little more space written as closure evaluations).

We then fully evaluate that object and call the (under the covers?) method on DOM.Element to convert this functional structure into a genuine DOM Element in the browser. We then add it "by hand" to the body element.

Second Example: Primes

Another classic in functional programming is the Sieve of Eratosothenes. This is a method for finding prime numbers by starting off assuming that every number could be prime and going through them one by one saying that the "first" number is prime and that all subsequent numbers can only be prime if they do not have it as a divisor.

More formally, we can write:

primes = sieve [2..]
sieve (p:l) = p:sieve (filter (notp p) l)
notp p n = n % p != 0

Obviously, this is going to produce an infinite list (since there is an infinite number of primes). To avoid generating an infinite number, the test will simply "take" the first few:

take 7 primes

This requires defining a "standard library" to provide functions such as filter and take. These are fairly boring, except for the use of a curried function as an argument to filter. I chose to implement the curried function as a JavaScript function, albeit one that is nested within another function. The FLEval.curry method takes the "actual function" to call (in this case notp), the defined arity of the function (which can only really be inferred during type checking, but as a human I'm filling that role and saying it's 2), and then whatever arguments are already on hand (in this case the prime number to check against). Filter then just calls this "function" on the remaining argument (the prospective element of the list) and expects to get a boolean back: if true, the element is added to the "result list"; if false, it is discarded.

As before, I think the JavaScript basically speaks for itself, with a similar translation. For example, the main function for primes is defined as follows:

primes =
  construct 3 closures:
    c1 = CLOSURE(List.intsFrom, 2);
    c2 = CLOSURE(sieve, c1)
  and return c2

First Commit: Fib

There are classic problems in functional programming and it seems to me that the right place to start is to try and implement some of those.

One of my favorites is the fibonacci sequence because it has two interesting properties: it is very, very easy to write in the obvious way; and that implementation is seriously flawed.

So the objective for "Lesson 1" is to get a lazy version of of this code running:

fib 0 = 1
fib 1 = 2
fib n = fib (n-1) + fib (n-2)

Obviously, we're not going to write a compiler (just yet) for that; we're just going to try and get it manually working. So, what does that look like?

Well, without descending into JavaScript just yet, this is really equivalent to something like the following:

fib n =
  EVALUATE n
  IS n AN INTEGER?
    yes =>
      Is it 0?  yes => return 1
      Is it 1?  yes => return 1
      Otherwise, construct five closures:
        c1 = CLOSURE(-, n, 1);
	c2 = CLOSURE(fib, c1);
        c3 = CLOSURE(-, n, 2);
	c4 = CLOSURE(fib, c3);
	c5 = CLOSURE(+, c2, c4);
      and return c5
    no =>
      return an error object

In this context, the statement EVALUATE n means to iterate until you have an actual value: any time the expression has a head which is a "closure" or other intermediate form, it needs to be evaluated by calling the function in the first part with the remaining arguments. Note that BECAUSE this is lazy evaluation, it is up to the function being called to decide if and when any arguments will be evaluated.

I claim almost all the rest of the logic can be determined by a perusal of testfib.js. I'm sure this can be run in a browser, but I've been testing this using iojs on the command line.

Most of the plumbing at this point is just manipulating things, for example, defining the plus function to do the add operation as a function. FLError and FLClosure are just types to support errors and closures.

The head method is responsible for doing "head" evaluation of a closure. Obviously, if it has already been head evaluated then it just returns the value; otherwise it attempts to evaluate it. To handle "tail recursion" a loop is used to allow any method to return a closure which will again be evaluated (so as to avoid infinite depth of recursion).