JL Programming Language

JL is a small, embeddable LISP-like language. The intended use is configuration files where it is desirable to support complex configurations (JWM, for example). Although use in configuration files is the primary goal, JL is a full-featured language in its own right that can be used to write useful programs.

JL is purely-functional, lexically scoped, and dynamically typed. Like other LISP languages, JL uses s-expressions. For example, the following expression calls the "list" function, passing it three arguments:

(list 1 2 3)

There are four value types in JL:

Numbers are floating point values. For example, 1 or 2.718281828. Strings are sequences of characters, which are specified using quote characters. Special characters are specified using escape sequences starting with "\", much like in C, Java, and other languages. For example, "This is a string\n" would represent a string with a trailing new-line character. Lists are sequences (singly-linked) of other values, which can be of any type. The distinguished value, nil, represents the empty list. Finally, lambdas are anonymous functions, which can take zero or more arguments and return a result.

Because there is no boolean type, by convention, nil and 0 represent false and any other value represents true. For functions that return a boolean value, 1 is returned to indicate true and nil is returned to indicate false.

See the JL function reference for a list of built-in JL functions and the API reference for information on embedding JL in another program.

Getting Started

JL is distributed in source form. The JL source code is hosted on GitHub. After downloading JL, simply run "make" to build the library and interpreter. Note that it may be necessary to modify the Makefile to work on some platforms.

A REPL (read-evaluate-print loop) comes with JL to allow one to experiment with JL from the command line. After building JL, the interpreter will be called jli. Running jli without arguments starts the REPL. From there you can enter JL expressions and see their output. jli is also capable of running programs in a file by supplying the file name on the command line.

Quicksort Example

To demonstrate JL, an implementation of the Quicksort algorithm is presented below. Quicksort is a simple sorting algorithm that works by first selecting a pivot of the list to be sorted. The algorithm then sorts the items less than the pivot as well as the elements greater than the pivot using the same algorithm on the two smaller sublists. Finally, the results are combined. This "divide-and-conquer" technique allows us to sort a list of n elements in O(n lg n) time on average. Note that for simplicity we use the first element of the list for the pivot, though this is not recommended in general.

The first function we'll define is a function to filter a list of elements. This higher-order function will be used to select the elements greater than and less than the pivot in our algorithm. Note that many languages, especially functional languages, have such a function predefined. JL does not currently predefine such a function, though its implementation is fairly trivial:

; Function to return a sublist of lst that contains only
; those items for which f returns true.
 (define filter (lambda (f lst)
  (if lst
    (if (f (head lst))
      (cons (head lst) (filter f (rest lst)))
      (filter f (rest lst)))
    nil)))

Note that a semicolon starts a comment that runs to the end of the line. The first line of code uses define to insert a binding called filter into the current scope. The second parameter to define is a call to the lambda function, which creates an anonymous function. By using define and lambda in this fashion, we are able to define new functions that may be used recursively.

The filter function above works by first checking if there is anything in lst, returning the empty list (nil) if the list is empty. Next it checks if the head of the list should be inserted into the result: (f (head lst)). If so, the head is prepended, using cons, to the list created by filtering the rest of the list. Otherwise, the result of filtering the rest of the list is returned.

The next function we need is a function to combine two lists. We will use this function after sorting the two sublists to construct the sorted result.

; Combine two lists.
 (define combine (lambda (as bs)
  (if as
    (cons (head as) (combine (rest as) bs))
    bs)))

The combine function above simply prepends the first item of the as list to the result of calling itself on the rest of the as list and the bs list. When the as list is exhausted, it simply returns the bs list. The running time of this function is, therefore, the length of the as list.

Finally, we have the qsort function which does the actual work:

; Sort a list using the Quicksort algorithm.
 (define qsort (lambda (lst)
  (if lst
    (begin
      (define pivot (head lst))
      (define less (filter (lambda (a) (< a pivot)) (rest lst)))
      (define greater (filter (lambda (a) (>= a pivot)) (rest lst)))
      (combine (qsort less) (cons pivot (qsort greater))))
    nil)))

This function first checks if lst is empty, returning nil if it is. Assuming lst is not empty, the function starts a new scope using begin. Note that begin allows one to insert multiple expressions as a single argument to another function. In this case, we use begin as the second argument to if. Within the new scope, we define pivot to be the first item of the list. We then use the filter function to select the items of the list smaller than pivot using our filter function (note the use of an anonymous function passed to filter). Next we use the filter function again to select items that are greater or equal to the pivot in the rest of the list. Finally, we sort the sublists and combine them for the result.

Those familiar with other LISP dialects might notice that JL does not use let. Instead, define is used to insert bindings into the current scope. As soon as the scope goes out of context, the bindings are removed. We can even over-write bindings by using define with the same name, which will only last until the end of the scope. Note that define does not change the value of anything; it only inserts bindings (mappings from name to value). Therefore, code using define in this manner is completely functional despite its imperative appearance.

With this function, we can sort lists of numbers or strings. For example:

(print (sort (list 7 3 2 6 9 1 8 4 5)) "\n")

Note that print is a function provided by the jli interpreter, which comes with JL.

This is one of the example programs comes with JL (examples/sort.jl). To run the example, specify this file as the first argument jli.