A Lisp interpreter in ABAP
I have long thought about writing a Lisp interpreter in ABAP, after coming across an article by Peter Norvig entitled “(How to Write a (Lisp) Interpreter (in Python))“. In that article, he shows how to construct a Lisp interpreter in what amounts to only a few lines of Python. Anthony Hay is someone, also inspired by Norvig’s article, who did the same thing in C++ with his article entitled “Lisp interpreter in 90 lines of C++“. (In the article he does point out that the 90 lines are for the core of the interpreter, not the built-in functions).
Well, taking the lead of their work, especially getting some insight from Hay, I have built a Lisp interpreter in ABAP now, though obviously it was never going to be in just 90 lines. In fact, doing most things in 90 lines of ABAP or less is somewhat of a Zumutung.
Before looking at the result though, let me give you a little background on Lisp.
(UPDATE! The interpreter is now able to call ABAP function modules. The whole solution is not very stable yet as I have done little to no negative testing. Please have a look on the wiki of the github project: https://github.com/mydoghasworms/abap-lisp/wiki. Here I have documented the latest functions and a getting started guide; there is also a section on ABAP integration).
Lisp: An executive summary
Lisp, which is an acronym for “LISt Processing”, is one of the oldest high-level computer languages, dating back to 1958, with only Fortran being older. You could say that Lisp is the oldest surviving computer language, as (I think) no-one uses Fortran anymore, except perhaps hobbyists. Correction: I have just read up a bit on Fortran and it seems there are still people using it for scientific applications. My apologies, Fortran lovers <3
In spite of being a product of the late 50s, Lisp implemented some way-ahead-of-its-time concepts, some which have started to appear in mainstream languages like Java only recently (the introduction of closures, for example), and some which have yet to make their appearance*(1).
Lisp, which is often regarded as a functional language (though not limited to that) is incredibly powerful and, due to its association with Artificial Intelligence, has been used widely by academia. However, it has found a very loyal following among a large contingency of IT specialists. Today it exists primarily in two dialects: Common Lisp and Scheme.
With the resurgence of interest in functional programming (consider also the recent SCN article on Functional Programming in ABAP), Lisp is getting a lot more attention these days, and this is a good thing.
Here is an example of List code:
(defun double (x) (* x 2))
This defines a function called “double”, which takes one argument, x, which it multiplies by two. (I have to warn you upfront though, that this is Common Lisp, and the Scheme syntax for defining a function, which we will use, is slightly different – read on).
Lisp code consists of parenthesized lists. A function call is constructed of a list in which the first element is the name of the function, and the elements following that are its arguments. In the example above, “defun” is the name of a function that creates a function, the first parameter is the name of the function, the second is a list of the arguments the function will receive, and the last is the body that will be evaluated when the function is called.
To call our function, we would write the following:
which, if it were evaluated, would give us 14. It may seem weird at first, especially when putting mathematical operators at the beginning of an expression, like (* 3 7), but it does become easier as you carry on.
An interesting aspect of Lisp is that code and data are represented in the same way. (Lists are just data after, all). This makes Lisp what is called a “homoiconic” language, and has some interesting implications, namely that if your code can emit data, it can potentially also emit other code, and this is in fact something that people do with Lisp: they write programs that construct other programs*(2).
There are numerous reasons to learn Lisp, and Eric S. Raymond, a well-known open source pundit, makes the following alluring statement:
LISP is worth learning for a different reason — the profound enlightenment experience you will have when you finally get it. That experience will make you a better programmer for the rest of your days, even if you never actually use LISP itself a lot.
A Lisp interpreter in ABAP
Now I will show you the Lisp interpreter I have built in ABAP. It’s not exactly a piece of art, more the result of some late-night slogging away at the keyboard, lots of testing and troubleshooting and prayer. It’s not coding poetry, but it’s functional (if you can excuse the terrible pun), and I think it’s pretty cool.
Although Norvig’s (and therefore Hay’s) interpreters clearly lean toward the Scheme persuasion, I at some point diverged and started using the book “Common Lisp: A Gentle Introduction to Symbolic Computation” as a reference for my implementation, primarily because I changed at one point from representing lists as internal tables of cells to using linked lists (cons cells). This is because, even though there are some performance gains to using tables, e.g. determining the size of a list, I ended up copying parts of tables everywhere, and this leads to greater memory consumption. The result is that I have adopted the Common Lisp approach to some things (e.g. false is represented by nil).
Apart from the pure fun in doing this, the great thing about implementing your own Lisp is that you are not bound to any particular standard. For example, for historical reasons, there are some weird names for functions dealing with lists, such as CAR (which retrieves the first element of a list) and CDR, which returns the remainder of the list, both important constructs. If I wanted, I could rename them HEAD and TAIL (and maybe I will).*(3)
The great thing about creating a Lisp interpreter for ABAP is that now you have an interactive means to write code on your ABAP application server, which opens up all sorts of possibilities. Imagine coding business rules in Lisp, for example.
Trying it out
To try out the interpreter, you will have to download the source from the following GitHub repo and install it on your system: mydoghasworms/abap-lisp · GitHub. By my own convention, the source files starting with ‘ZUSR’ must go into a type ‘1’ (report) program, and the ‘ZLIB’ programs into a type ‘I’ (Include) program*(4). At minimum you will need ZLIB_LISP, which contains the interpreter, and ZUSR_LISP_REPL, which is just a simple REPL (Read-Eval-Print Loop) front-end to the interpreter which consists of s single input and output field. (Sorry, no fancy multi-line inputs and script parsing at this point; hopefully in the future).
When you run ZLIB_LISP_REPL, you will get the following:
Now type in a number in the INPUT field and press Enter. The REPL responds with the number, because that is an expression on its own and a number will just evaluate to itself.
That’s not very impressive. Now enter something different, like ‘a’:
The interpreter responds correctly by telling us that the symbol ‘a’ is not defined. Let’s define it with some value:
(define a 22)
The REPL will respond with the defined symbol, which is ‘a’. If you enter ‘a’ now, it will respond with 22.
Now let’s define a function called ‘abs’ to calculate the absolute value of a number. (I told you earlier that the syntax is somewhat different in Scheme. I wasn’t lying):
(define abs (lambda (n) ((if (> n 0) + -) n)))
The built-in function ‘lambda’ creates a function which we can call, and by using that as input to the value portion of the built-in ‘define’ function, we assign a name to it that we can reference later. The body of the function makes use of a few built-in functions, namely ‘if’, ‘>’ (greater than), ‘+’ (add) and ‘-‘ (minus).
Let us try and execute the new function:
If everything went well, the interpreter should respond with 22.
We could have written the ‘abs’ function as follows and produced the same result:
(define abs (lambda (n) (if (< n 0) (– n) n)))
The first way, however, demonstrates an interesting feature: In the first definition of the ‘abs’ function, the invocation of ‘if’ evaluates to a function, which is either ‘+’ or ‘-‘, that is then subsequently applied to the input, n. This technique of determining the function to call based on some criteria within an expression is a powerful construct, and not something you would necessarily be used to from imperative or object-oriented programming. Needless to say, a transition to Lisp (and functional programming for that matter) involves a big mind-shift.
Let’s carry on: here is an example of a recursive function to calculate a factorial:
(define fact (lambda (n) (if (<= n 1) 1 (* n (fact (– n 1))))))
Run it with a few numbers and see what happens. If you run it with 2000, for example, you will probably notice a significant delay. With an input of 3000, you will cause a CX_SY_ARITHMETIC_OVERFLOW exception. (At least I assume that the ABAP kernel manages the same data types consistently across platforms).*(5)
Lastly, let’s play around with lists a little. Create a list and assign it to a symbol with the following:
(define mylist (list 1 2 3 4) )
You can check the result by evaluating the symbol ‘mylist’. Now, to get the first element of the list:
and to get the remainder (i.e. the rest of the list starting after the first element:
To try out some more examples and see some code showing the interpreter in action, look at the ZUSR_LISP_TESTS program.
A short reference
The following is a short reference of the built-in functions available in the interpreter. Some are available as symbols which map to native procedures which, like the functions you define, can be passed around in expressions. The other list are just symbols that are directly evaluated by the interpreter and by contrast, can not be passed around in expressions*(6).
These are the functions you can use in the current interpreter:
|+, -, *, /||1-n||Yes||Basic arithmetic functions|
|append||2||Yes||Takes an element and a list, appends the element to the list|
|list||1-n||Yes||Makes a list out of all given arguments|
|length||1||Yes||Length of the given list|
|car||1||Yes||Returns the first item in a list, or nil given an empty list (or nil)|
|cdr||1||Yes||Returns the tail of a list, which will be a list, or nil, given an empty list (or nil)|
|cons||2||Yes||Constructs a new list, making the first element the head and the second input (usually a list) the tail (like prepending, almost)|
|nil?, null?||1||Yes||Tests if the input is nil or not (null? is an alias added for compatibility with Scheme-based tests)|
|>, >=, <, <=||1-n||Yes||Comparison operators|
|equal?||2||Yes||Tests if the given arguments are equal (either by symbol or number) or, in the case of a list, whether it is the same list.|
|quote||1||No||Returns the argument verbatim, without evaluating it|
|if||2-3||No||Evaluates the first argument. If true, the second argument is evaluated. If not, a third argument is evaluated, otherwise nil (false) is returned|
|define||2||No||Assigns a value (second argument) to a symbol (first argument)|
|lambda||2||No||Defines an anonymous function; first input is a list of formal parameters; second is the body to be evaluated|
|begin||0-n||No||Evaluates all arguments as expressions in turn; a nice way to string a lot of expressions together to be executed|
*meaning you can use it as an argument or return-value. I’m not sure what the correct term is
There are also two other built-in values: nil and true. Anything that is not nil can be considered true. nil is essentially the same as an empty list, and this is more of a Common Lisp thing. Scheme also has a true keyword.
Where to from here? (Caution: Rough edges!)
While there is a certain thrill in creating a Fibonacci function and watching it execute, knowing that the code is being parsed, built into an abstract syntax tree and evaluated in ABAP, you quickly grow tired of it. What would make an interpreter like this really useful, is if you can interact with the rest of the system, by accessing the database or particularly consuming classes and function modules. It should be fairly straightforward to extend the list of built-in types in the interpreter and provide a set of built-in functions to achieve this.
At the moment, the interpreter lacks the notion of a string type, as well as other syntactic shortcuts (like prepending a symbol or list with a single quote, which is the shortcut for quoting something without the need to use QUOTE). That is definitely on the list. (Sorry, another bad pun).
There are other aspects to consider, such as the performance. Many applications in functional programming involve making use of recursive functions, and for this reason, many implement what is called “Tail Call Optimization”, which eliminates the need for a growing stack*(7). Inherently, this implementation makes use of the stack in ABAP, so perhaps another approach would be to realize the evaluation of functions using other ABAP constructs.
Also, I have not done a lot of negative testing, especially on the parsing side, so don’t be surprised if you come across problems. For now I assume all input is valid. (Feel free to raise an issue on the GitHub repo though. It would warm my heart to know that someone is actually playing with this).
Lisp makes an interesting topic of study, and there are many wonderful resources on the internet. I haven’t delved so much into all the technical aspects, so I am not going to try and recommend any books I have not read myself. Instead, because I love sensationalism, I have spent a lot of time reading blogs by people who rave about Lisp. One of the best reads I can recommend is an article by Paul Graham entitled “Revenge of the Nerds“.
While on the subject of futuristic, ahead-of-their-time languages, I could not finish this article without pointing you to REBOL, a language developed by Carl Sassenrath, one of the brains behind Amiga in the 90s. It’s not Lisp, but it embodies some of its spirit. You can almost think of it as “Lisp without the parentheses” (though I’m sure that hardly does it justice; it is probably the best thought-out language on the planet). It does a fantastic job of looking like an ordinary procedural language, but with the power of Lisp. REBOL is not developed so much anymore, but it’s spiritual successor, the Red Language is what you need to keep your eye on. If robots ever take over the world, the AI would be written in Red.
(1) See the link to the Paul Graham article somewhere in this post, where these features are listed.
(2) You have probably done this too before in ABAP if you have used the GENERATE SUBROUTINE POOL statement to generate code on the fly, which is a technique that was used more frequently in the past before the availability of more dynamic statements in ABAP. I can assure you though, that it is very rudimentary compared to what Lisp has to offer.
(3) The explanation is that on the hardware on which Lisp was initially implemented, CAR stood for “Contents of the Address portion of the Register” and CAR stood for “Contents of the Decrement portion of the Register”, i.e. references to assembly instructions.
(4) In hindsight, ZBIN would be more applicable to executable programs; it’s more Unix-like
(5) It should be noted that the interpreter makes use of the types provided by ABAP, so there is no support for big numbers like in other languages. But in 40 years of SAP, I don’t think anyone has complained of not being able to count a gazillion dollars.
(6) I just followed the lead of Norvig and Hay on this. In some cases it is obvious that if the function is independent of context, it is easy to use as a procedure. This may warrant a little closer inspection though.
(7) though admittedly ABAP seems to have no problem with sky-high stacks, probably because an application server is normally configured with a lot of memory.