What is a Functional Programming Language?


Perspective is everything. If you talk to a developer who has been trained in the traditional way (Java, C#, JavaScript, Python, etc), they will say that a functional programming language is one where you can pass functions as parameters to other functions, and return functions. This is not wrong.

Then there is this general definition on Quora:

Functional programming is a paradigm which concentrates on computing results rather than on performing actions.  That is, when you call a function, the only significant effect that the function has is usually to compute a value and return it. Of course, behind the scenes the function is using CPU time, allocating and writing memory, but from the programmer’s point of view, the primary effect is the return value.  Objects in a functional programming language are often immutable (a.k.a. const or final); instead of changing an object, you allocate a new object which looks like the old one except for the change.  Compare this with an imperative programming language like Java, where progress is made by changing objects’ fields, inserting them into sets, etc.

In a pure functional language, like Haskell, most functions are guaranteed by the type system not to perform any other actions.  In an impure functional language, like ML, a function may have other side effects, such as querying a database or server, generating random numbers, reading or writing the disk, etc.

This definition is not wrong either – although I am not sure that dynamic typing makes a language impure. A pure function is one that, given the same input data, will always produce the same result.

We could read Wikipedia:

In computer science, functional programming is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state andmutable data. It is a declarative programming paradigm, which means programming is done with expressions[1] or declarations[2]instead of statements. In functional code, the output value of a function depends only on the arguments that are input to the function, so calling a function f twice with the same value for an argument x will produce the same result f(x) each time. Eliminating side effects, i.e. changes in state that do not depend on the function inputs, can make it much easier to understand and predict the behavior of a program, which is one of the key motivations for the development of functional programming.

Functional programming has its roots in lambda calculus, a formal system developed in the 1930s to investigate computability, the Entscheidungsproblem, function definition, function application, and recursion. Many functional programming languages can be viewed as elaborations on the lambda calculus.

Again, not wrong, but incomplete according to the purists (that word again) who consider strong typing a core aspect of the paradigm.

If we delve into lambda calculus, we see that Church’s original papers presented untyped (1936) and simply typed (1940) specifications. From my cursory scanning, I don’t think lambda calculus typing maps to strong typing in modern functional languages.

The biggest eye-opener for me (so far) was the concept of expressions instead of statements. I did not understand the implications until reading a paper by McCarthy on the origins of Lisp. I’ll take the reasoning off-line for now.

In Haskell a function has only one input and one output. This is conceptually elegant, but would be awkward without syntax help.

(ref add (lambda [first] (lambda [second] (+ first second)))

(ref result ((add 12) 7) ## is 19

In summary, in a functional programming language

  1. Function references can be passed to and returned from other function.
  2. Prefer expressions over statements.
  3. Support referential integrity (isolating state and I/O).

What can you add to this list?

When to Consider Reactive Streams


Was implementing reactive streams for Lispz worth the effort? Let’s see where we stand. Let’s consider the example from the last blog post.

(using [message]
  (cascade
    (=> (dom.click "my-message-address" document.body))
    (=> (message.map      @    "mouse"    (=> {x: @.clientX  y: @.clientY})))
    (=> (message.filter      @ "top-left" (=> (< @.x @.y))))
    (=> (message.throttle @ 2000))
    (=> (message.listen   @ (=> (console.log @.x @.y))))
  )
)

If we did not have message streams, the code would look something like:

(document.body.addEventListener "click" (lambda [event]
  (ref data (stateful { last-time: 0 }))
  (ref loc { x: event.clientX, y: event.clientY })
  (cond (< loc.x loc.y) (do
    (ref now (Date))
    (cond ((> data.last-time (+ now 2000)))
      (data.update! { last-time: now })
      (console.log loc.x loc.y)
    )
  ))
))

Well, I guess that answers that. Reactive streams are a lot more readable than in-line code. In addition you are not rewriting throttle every time you need it.

Perhaps I should have asked the question “When don’t we use Reactive Streams for asynchronous events“.

  1. When a promise will do – so any server request that does not need to send a message.
  2. When a stream will have more than one source, or wait on a promise. The current architecture doesn’t merge asynchronous events (yet).

Ok, that is a shorter list thank I expected. Can you think of others? It seems to me that streams work well for continuous discrete data flows from callbacks and events.

Message Based Reactive Programming


As I move more from working on Lispz as a language to using it as a support system for Empiric, I need to deal more with the asynchronous nature of the underlying (browser/JavaScript) architecture. Callbacks are efficient, but make for messy hard-to-follow code. Promises only help a little and are single-shot.

For the ATO we were looking at RxJS, reactive programming and by extension function reactive programming (frp). With care the approach creates clear declarative code. On the down side, RxJS in particular requires a big learning curve. Also after looking at a number of reactive libraries, I see that they have in common a messy, large and decidedly non-functional support tier.

Async/await is great for treating asynchronous sequences in a synchronous manner, but is only suitable for tightly coupled code. Also it is not universally available yet.

I want to do better for Lispz.

I had previously chosen messaging for decoupled communications between components. I was already using it in a reactive manner so that components can listen to user interactions. It was more of a pub/sub model producing code that was not as clear and declarative as I would like.

Time for some research. My first stop was The Reactive Manifesto. It states that reactive systems should be responsive, resilient, elastic and message driven. This confirmed my belief that extending my messaging paradigm to be more stream-like was the way to go. I also wanted to carefully consider and cater for responsiveness, resilience and elasticity once I fully understood the consequences.

At the core, message.send is used to send a single message to any listeners. Given that reactive programming is about data streams, we need need to send messages when ‘things’ happen in a stream. In the browser the most common stream comes from events in the DOM.

(ref @click (dom.click "my-message-address" document.body))
## is a specific case for
(ref @click (dom.message "click" "my-message-address" document.body))

The function returns the generated name of the queue. In this case it would be dom-click/my-message-address/.

The core of all reactive systems is to map the data in the streams – meaning to convert it to something more suitable to the task at hand. Here we take the events from the DOM and extract the mouse position.

(ref @mouse (message.map @click "mouse" (lambda [event]
  {x: event.clientX y: event.clientY}
)))

The next most important action is to filter the data to remove impurities. Here we only return results from the top left quadrant of the browser window.

(ref @top-left (message.filter @mouse "top-left" (lambda [pos]
  (< pos.x pos.y)
)))

All stream processors return the new message queue name created by adding the provided name to the source. Here @top-left is dom-click/my-message-address/mouse/top-left – very readable in a message trace.

Lastly we want to observe the result and actually do something.

(message.listen @top-left (=> (console.log @.x @.y)))

Naming queues as above provides clarity but is a bit verbose. Cascade can be used for a more concise result. In Lispz, => is an anonymous function with one parameter, @.

(cascade
  (=> (message.from.click "my-message-address" document.body))
  (=> (message.map     @  "mouse" (=> {x: @.clientX y: @.clientY})))
  (=> (message.filter  @  "top-left" (=> (< @.x @.y))))
  (=> (message.observe @  (=> (console.log @.x @.y))))
)

Map and filter are easy to implement on the base messaging code. The are clean functional code with as much referential integrity as a function that sends messages can claim.

Sometimes it is not possible to provide the processing needed without keeping some state in the stream. For those evil beings, the action function provides a stateful object unique to the stream.

...
  (=> (message.filter  @  (lambda [packet context]
    (ref moved-x (isnt packet.x context.last-x)
    (context.update { last-x: packet.x })
    moved-x
  )))
  (=> (message.observe @  (=> (console.log @.x @.y))))
)

In Conclusion

So, how does it meet the other criteria in the reactive manifesto?

Responsive

An application is responsive when an event is acted upon more quickly than the observer can measure. Many systems fire off lightweight threads whenever action is required. With Lispz messages the system will be responsive if the attached functions complete in an interval less than the next likely event. It is the responsibility of the called function to call (yield) or (delay) if the process is to take time. This is the essence of co-operative multi-tasking. I considered using yield as an integral part of map and filter, but it seems an unreasonable overhead when most translation and filters are fast.

resilience

Resilience is the ability of the application or component to keep operating even after failures have occurred. For Lispz messages, this is built-in as long as the provided functions exhibit referential integrity. Resilience is still possible if the action functions hold state, but more care must be taken. If any map or filter fails then the rest of the stream is not informed, but any subsequent events are processed as usual.

elasticity

Elasticity is responsiveness under load. Again this is the responsibility of the action writer. A stream that catches all mouse move events and writes the event object to the console is not elastic. If you move the mouse fast and far then it will take time for all the messages to write.

More Asynchronicity


Philosophy

There are three kinds of people in the world – those who can count and those who can’t. And there are two ways to treat asynchronous events at the language/platform level. Either stop the process while waiting for something…

(while (read) (print)) ## this won't work in a JavaScript engine

…or provide actions to do when an event happens…

(read (lambda (print))) ## Call an anonymous function when event fires.

For some reason the first approach is called synchronous. In practice it means you can’t do anything until the event you are waiting for occurs. Systems that work this way compensate by making it easy to create multiple threads – allowing code to appear to work in parallel. The developer does not have much control on when the processor switches from one thread to another. This means that data can appear to change like magic between two instructions on one thread because another thread has been active. Not only does this make referential integrity difficult, but it creates  a need for locks and semaphores and other mind-bending and program-slowing mechanisms. On the bright side, a program can use multiple cores without any instruction from the developer.

By contrast the second approach is called asynchronous. Your code has full use of the processor until it releases it. Any operation that must wait for an external resource will be inside code that only called when needed. This is easier to comprehend. We humans have been trained to think in a synchronous manner when solving problems or writing programs.

One more tale before getting back to lispz. Microsoft Windows prior to ’95 used what they called “cooperative multi-tasking”. This meant that the operating system never took the CPU away from a program without the program first giving permission. Hmmm, very similar to a JavaScript machine based on asynchronous methods, isn’t it? The complaint then is that badly behaved applications coud freeze the UI by not releasing the CPU often enough. Since JavaScript runs on the UI thread it can also freeze the UI in the same way. A well behaved program, on the other hand, is more efficient and far easier to write and debug.

Callbacks

Callbacks provide the simplest mechanism for asynchronous responses. Any function that wants to initiate something that will complete at an undetermined later time can take a reference to a function to call at that time (or thereabouts)

(delay 2000 (lambda (console.log "delay over")))

Many callbacks producer follow the node-js approach of providing error and response parameters.

(read my-url (lambda [err response]
  (cond err (throw "read failed"))
  (return response.text)
)

Benefits

  1. Very simple with minimal overheads
  2. Can be called many times
  3. Cause and effect are sequential in code

Disadvantages

  1. Empiric in nature
  2. Highly coupled
  3. Leads to hard-to-read code in more complex event sequences.
  4. Exceptions are lost if not processed within the callback
  5. Actions triggered before the callback is set are lost

Promises

ES-2015 has introduced native promises into JavaScript. As of November 2015 it is available on all mainstream browsers. Even if not, there are shims that work in an identical(ish) manner.

Functions return a promise object. This object can be passed around and whoever needs the data it will or does contain can ask for it with a callback function.

A function that creates a promise uses the ‘promise’ keyword instead of ‘lambda’. When the promise is fulfilled it will call (resolve-promise data). If it fails it calls (reject-promise err).

(ref read (promise [addr param1 param2]
  (http-get (+ addr "?&" param1 "&" param2) (lambda [err response]
    (cond err (reject-promise err) (else) (resolve-promise response))
  ))
))

In promise the function is run immediately. In many situations it is nice to have a promise that only runs when it is first needed. You may, for example, create a file object that may or may not ever ask a server for the contents.

(ref file {
  read: (promise.deferred [addr param1 param2]
    (http-get (+ addr "?&" param1 "&" param2) (lambda [err response]
      (cond err    (reject-promise err)
            (else) (resolve-promise response)
      )
    ))
  )
})
...
## This will trigger a server request...
(when file.read [response] (console.log response))

Because it is common to turn a callback into a promise, lispz provides a helper macro. The following provides identical functionality. One of the benefits of a language with real macros 🙂

(ref read (promise.callback [addr param1 param2]
  (http-get (+ addr "?&" param1 "&" param2) callback)
))

Now that we have a promise, we can use it just like a callback if we want:

(ref reading (read "http://blat.com/blah" 1 2))
(when reading [result] (process result))
(promise-failed reading (lambda [err] (console.log "ERROR: "+err)))

Even without further knowledge, promises clean up errors and exceptions. If you do not catch errors, exceptions thrown in the asynchronous function can be caught in the code containing the promise.

The power of promises starts to become clearer with the understanding that ‘when’ can return a promise.

(ref processed (when reading (lambda [result] (process result))))
(when processed (console.log "All done"))

So far this adds very little at the cost of a relatively large supporting library. If we start thinking functionally instead of sequentially, promises provides a way to clarify our code (a little).

# change branch we will be working with
(ref update-mode (github.update lispz-repo))
# Once in update mode we can retrieve lispz.js and ask for a list of other file in parallel
(ref lispz-js    (when update-mode [] (read-file "lispz.js")))
(ref listing     (when update-mode [] (github.list-dir lispz-repo "")))
# We can only sort files once we have a listing from the server
(ref groups      (when listing [files] (group files)))
# but then we can process the different groups in parallel (retrieving source as needed)
(ref modules     (when groups [files] (build-modules files.modules)))
(ref riots       (when groups [files] (build-riots files.riots)))

# Now to pull it all together into a single file
(ref  source     (stateful ["window.lispz_modules={}"]))
# promise.sequence forces the order.
(ref all-loaded  (promise.sequence
  (when modules  [sources] (source.concat sources) (promise.resolved)
  # lisp.js is added after modules and lisp-js are resolved
  (when lispz-js     (source.push! code) (promise.resolved)
  # riot tags are added after lisp.js and lisp-js is added and riots promise is resolved
  (when riots    [sources] (source.concat sources) (promise.resolved)
))
# Only write the result when the sequence above is complete
(when all-loaded [] (write-lispz))
# returns a promise that is complete once the results are written

If you think this is still too hard to read, then I agree with you. I will discuss message driven reactive programming in a later article.

In summary we have

  1. (promise [params...] ...) is a macro that generates a function that returns a promise
    1. (resolve-promise results...) sets results used in (when [results...] ... )macros
    2. (reject-promise err) sets results used in (catch-failure [err] ...) macros
  2. (promise.deferred [params...] ...) prepares a promise that won't start the actions until the first (when ...)
  3. (promise.callback [params...] ...) is a macro to creates promises from traditional callbacks
    1. callback is a function reference to use where callbacks would normally be defined
  4. (promise.resolved results) Will return a promise that will always provide the results supplied to when. Use it to turn a synchronous function into a promise to use in sequences.
  5. (when a-promise [results...] ...) is a macro that works like a lambda where the function body is executed with the results supplied once (and if) the promise is resolved. If a when statement returns a promise it can be used for chaining.
  6. (promise-failed a-promise [err] ...) is a macro that works like a lambda where the function body is executed if any of a set of chained promises uses **reject-promise to indicate an error.
  7. (promise.all promise-1 promise-2 [[promises]]) will return a promise that is fulfilled when all the promises specified are resolved or rejected. It will flatten arrays of promises.
  8. (promise.sequence promise-1 promise-2 [[promises]]) will return a promise that is fulfilled when all the promises specified are resolved or rejected. Unlike all, each promise is triggered when the preceding promise is resolved.

Benefits

  1. Separates cause and effect more clearly
  2. Results are available even it the promise is resolved before inspection
  3. You can pass around a promise just like the data it will contain
  4. Handles exceptions in a structured way

Disadvantages

  1. Still fairly highly coupled
  2. Only allows one action - not for repetitive events
  3. Developer view needs to change from sequential perspective
  4. Being selective about errors and exceptions is painful. Once a promise is resolved it cannot change. Any promises that rely on a rejected promise will themselves be rejected causing a cascade of failures. To be selective you need to wrap a promise catch in an outer promise and resolve the outer one if the error itself can be resolved. Don't forget to resolve the outer promise with the data from the inner one when there are no errors.
  5. Makes it harder to follow the sequence of events.

Events

Events follow the observer pattern. Lispz provides access to the light-weight version in Riot. If you use Riot for UI components, the custom tags are always observers. You don't need to use riot to make use of events. You can either create an observable or make any object in the system observable.

(using [riot]
  (ref observable-1 (riot.observable))
  (ref element (get-my-element))
  (riot.observable element)
)

Once that is out of the way, tell the observable what to do if it receives an event either once or every time.

(observable-1.on "event-name" (lambda [params...] what to do...))
(element.one "focus" (lambda [contents] (element.set contents)))

One observable can have many listeners for the same or different events. Use 'trigger' to wake an observable.

(observable-1.trigger "event-name" param1 param2)

Finally there needs to be a way to stop listening.

(observable-1.off "event-name" event-function-reference) ## stops one listener
(observable-1.off "event-name") ## stops all listeners to an event
(observable-1.off "\*")          ## stops all listeners to all events for observable

Benefits

  1. Decouples the code to whatever extent is necessary.
  2. Associates code and data (such as the DOM).
  3. Allows multiple invocations

Disadvantages

  1. Too convoluted to use as an easy replacement for callbacks
  2. One-way communication
  3. No way of knowing if event was processed as expected.

Messaging

Lispz includes a complete decoupled communications solution based on messaging. The base version is in-browser, but the API is designed to work across systems with Restful access or Web-sockets. The UI components use messaging to communicate between components that are not linked, so cannot make more direct connections.

Here a code editor will wait on messages to open a new 'file'. The message includes a name unique to each code editor. The dictionary at the end can include any number of named requests. Each associated function takes a packet whose content format is known by clients and services.

(using [message]
  (ref open (lambda [packet] ...)
  (message.dispatch (+ "code-editor/" opts.name) { open })

The client will send a command to open a new file for display. If the editor is called 'scratch':

(message.send "code-editor/scratch/open" {
  key:      "scratchpad.lispz"
  contents: "..."
})

As an aid when sending messages to a dispatcher, use the connect short-cut:

(ref scratch (message.call "code-editor/scratch"))
(ref open-scratch (scratch "open"))
...
((scratch "open") {key: "scratchpad.lispz" contents: ""})
# is the same as
(open-scratch {key: "scratchpad.lispz" contents: ""})

The following example changes the left padding on a DOM element if asked.

(message.observe "page-content-wrapper-padding" (lambda [px]
  (stateful.morph! tag.page-content-wrapper.style)
  (tag.page-content-wrapper.style.update! { paddingLeft: (+ px "px") })
))

Lispz uses exchanges defined as part of the address. The address can include details that will define different exchanges.

It is possible to remove listeners by name or regular expression

(message.clear "my-message")
(message.clear '/code-editor.*/')

 

What is Lispz?


https://github.com/paulmarrington/lispz

Executive Summary: Lispz supports functional programming for developing single-page-applications for the browser. It does this with modules, RIOT web components, Bootstrap visuals, message passing and numerous other features to make SPA development easier.

Lispz encourages a functional programming style and data immutability in lisp-like syntax for running in the browser. It compiles to JavaScript, so can easily make use of all the JavaScript libraries and packages.

Lisp (without the z) is a functional language with a long pedigree. Only FORTRAN is an older living language. Traditionally it did not address data immutability, although Clojure (a relatively recent arrival) does.

Lispz as part of the Lisp family encourages functional programming. With Lisp, functions are the main form of flow control. Lisp has very few syntax rules when compared to other languages. Not only does this make it easier to learn, but it also encourages problem decomposition into smaller functions.

Lispz supports data immutability at the program level. This means it allows the creation and update of local data within a function but makes it harder and more obvious to change data passed in or from a more global scope. This works well due to the single threading and co-operative multi-tasking nature of the JavaScript VM.

If the Lisp syntax scares you, just remember that change encourages learning. In practice due to the much simpler syntax, it provides a lot less scaffolding than JavaScript, while still making it abundantly clear when a function needs to be decomposed.

Lispz inherits real macros from Lisp. With macros that use the underlying language you can create new domain specific languages to meet any need.

Lispz uses the power of closures from JavaScript to capture variables that can change to the function currently running.

Lispz includes a simple module system to provide name-spacing and separation of concerns.

Lispz is for single-page applications – including

  • the generation of cache manifests for performant and off-line applications.
  • Riot for web components
  • Bootstrap for visual

A sample using riot with bootstrap:

<panel heading="Panel heading" footer="Panel footer"
  context=warning menu=test-menu owner="Test Panel 2">
  This is a panel with simple heading and footer
</panel>

src=/lispz/lispz.js#riot,bootstrap>
id=test_code type="text/lispz">
  (using [message]
    (message.send "test-menu" [[
      { title: "Item 1" topic:     "Test menu item 1" }
      { title: "Item 2" children:  [[{ title: "Item 2a" }]] }
    ]] (=>))
    (message.listen (+ tag.\_riot_id "Test menu item 1") (lambda [data]
      (console.log data)
    ))
  )

 

This example displays a bootstrap pane with header, footer and a menu. The menu can be changed dynamically by sending it a message. If item 1 is selected it sends a message that causes the data to be printed on the console.

Asynchronisity 1


I have been working with asynchronous code all my career – ever since I wrote a multi-processing kernel on top of DOS to support a phone system reporter.

My second most recent cycle was on node-js over the last 3 years. On the server the need for callbacks is 100-fold higher than in the browser. The problem is the same, but the need for nesting is much greater.

Don’t get me wrong, I like the JavaScript asynchronous model. It sends me back to 1993 and Windows “cooperative multi-tasking”. I like the fact that I have control – and have the responsibility not to hog the CPU and freeze the system. This is literal in the case of the browser where the JavaScript runs in the same process as the UI update. Mostly I love the fact that my data is my own. I know no other thread is going to diddle with it until I specifically call something asynchronous. Between that and closures and local variable, life is sweet (no, not a pun on sweet.js).

There is a term “callback hell” when callbacks are coded directly creating a horizontal pyramid of indentation.

action_one(params, function(results) {
    work...
    action_two(params, function(results) {
      work...
      action_three(params, function(results) {
          work...
          action_four(params, function(results) {
              work...
          })
      })
    })
})}

Just imagine how this would look with more code and more asynchronous functions. My first attempt was to use a library similar to async.js (https://github.com/fjakobs/async.js).

async.list([
    function(callback) {
        work...
        action_one(params, callback)
    },
    function(callback) {
        work...
        action_two(params, callback)
    },
    function(callback) {
        work...
        action_three(params, callback)
    },
    function(callback) {
        work...
        action_four(params, callback)
    }
]).call().end(work...)

Looks cleaner, doesn’t it? In practice, once code is added the sequential nature is lost and it is no easier to follow than raw callbacks.

So, let’s clean thing up the practical way – separating concerns (or in this case steps).

step_one = function(callback) {
    work...
    action_one(params, callback)
}

step_two = function(callback) {
    work...
    action_two(params, callback)
}

step_three = function(callback) {
    work...
    action_three(params, callback)
}

step_four = function() {
    work...
    action_four(params)
}

async.list([step_one, step_two, step_three, step_four]).call().end(...)

This made sense to me. Each step is an action that ends in an asynchronous call. By naming the steps well, the waterfall clearly documented the sequence.

Now wait, what is the benefit of waterfall. How would it look with raw callbacks.

step_one( step_two( step_three( step_four())))

It is just as clear without the overheads on an async library.

The particular async library I linked to also has many of the interfaces provided by frp and reactivex (http://reactivex.io/) and streams – map, reduce, filter, etc. I will talk about it next installment.

Why I am writing yet another language implementation


Why am I writing a language that compiles to JavaScript when I have over 250 to choose from (https://github.com/jashkenas/coffeescript/wiki/List-of-languages-that-compile-to-JS)? For the same reason as 250 plus other developers – I want something different to what is already out there.

  • Minimalist Syntax and Semantics: To quote Einstein: “Everything should be made as simple as possible, but not simpler.” For this I lean towards the Lisp family where Syntax is all but non-existent. My first thought here was Clojure and ClojureScript.
  • Ability to compile and work in the Browser: So it has to be able to compile to JavaScript on the browser. This lets out ClojureScript as it is compiled on the server.
  • Something to help me learn to understand functional programming: Again ClosureScript comes to mind.
  • A language to work with the examples and problems in SICP (Structure and Interpretation of Computer Programs). SICP was the course-ware book from MIT in the 80’s. It used Scheme – another Lisp dialect.
  • An extensible language to so I can learn about reactive/frp: Again Lisp macros are suitable for this. Sweet.js adds macro capability to JavaScript. Impressive, but it is not minimalist.

I spent quite a while looking through the choices on GitHub. The one that attracted me most was LiScript. At 100 lines it was easy for me to  follow. It provided a lisp-like syntax with macros. It provided direct access to the power of JavaScript. It as close, but not perfect. The macros were too primitive and the translations could be translated into a language feature. Besides, the best way to learn is to do…