Slashdot Mirror
Common Lisp: Inside Sabre
bugbear writes "I just got permission from the author (Carl de Marcken of ITA Software) to publish this
email, which describes the inner workings of
Sabre, the flight search software that the airlines and travel agencies use. It
is a case study in cheap Linux/Intel, NT/Intel and Hpux boxes replacing mainframes, and also the use of lisp and other languages in a server-based app. Update: 01/16 13:45 GMT by H :RawDigits writes "Common Lisp: Inside Sabre - correction. The Lisp engine is used by Orbitz, and not Sabre. Sabre still maintains mainframe systems for their booking. I should know, I am sitting in the Orbitz NOC right now ;)"
This is the first use of lisp that I've seen that used it in an environment where performance was the main goal. This seems like what I've always been told any "reasonable person" would use C for. Is it common that lisp is used in mission-critical high volume computing? Or was the point in using lisp the fare-searching algorithm? My lisp knowledge is limited to one semester of scheme, so I'm pretty ignorant.
I did some research a few months ago on Lisp since I am not very familiar with it and I discovered that Yahoo stores uses Lisp.
It would seem to me that if it can power 14,000 e-commerce sites for the largest web network that it must be pretty scalable.
Lisp, due to its recursive nature is often used in AI because it can perform operations with lower overhead.
--Jon
"Of course, with things like STL and Java, I think programmers of other languages are also becoming pretty ignorant."
I once worked on a project where we used LISP to processes elements of Radar data. Our reason for choosing LISP was two fold, firstly we were doing List transformation, mapping and comparison. Secondly and most importantly though....
we knew that when it worked, that was it and we didn't want people buggering with it if they didn't understand it. LISP makes sure that the people writing it are going to have a better grasp on computing that the average C/C++/Java person.
Of course the comment at the top of "If you come here thinking you've found a bug, you are wrong, look elsewhere. If you are 100% certain then remember this.... everyone relies on this, if you bugger it up thats a lot of angry people" also probably helped. But using LISP enabled us to write a small piece of very tight code that made understanding the task simple.
You can also write the most evil code in the world in LISP, variables that become functions... occasionaly, excellent stuff >:-)
An Eye for an Eye will make the whole world blind - Gandhi
The system has a state, which you don't feed entirely into your top-level query, rather, you examine the state, and sometimes change it, from wherever in the program flow you need the data.
The characteristic that really gives you benefits in Lisp is the way you can have Lisp write itself, creating little programming languages which fit each problem. They don't have the visual appeal of a specialized language written with full freedom to define the syntax, but their form still reflects the programmer's understanding of the problem, rather than the details of the solution.
People shouldn't talk about Lisp as "functional" versus "imperative" languages like C++, they should talk about Lisp as "flexible" as opposed to the inflexibility of C, which forces the programmer to do tedious, repetitive work.
Everything about Lisp facilitates this flexibility, from its simple, regular syntax to its implicit type handling.
Turing said: "This process of constructing instruction tables [i.e., programming] should be very fascinating. There need be no real danger of it ever becoming a drudge, for any processes that are quite mechanical may be turned over to the machine itself." And Lisp is certainly well-made for this method of avoiding drudgery.
The real beauty of it comes when you have to optimize your code: rather than fiddling with the part that defines the problem, you change the bit that transforms it from a problem definition to a solution. This ability to seperate leaves you free to optimize one problem area however you wish, without having to go around and fix the code in a thousand other places your modification breaks.
Getting back on topic, Lisp certainly allows functional programming, but sit down with Common Lisp and try to translate a C program into it line by line; you'll have very little trouble: it contains all the imperative stuff you need. For that matter, you can program C in a very functional style, using the trinary ?: operator and recursion, if you like. In either language, though, sticking to functional style as strictly as possible will hurt your performance.
Just as the standard teaching examples of C, full of gets(), sprintf(), and the like, are terrible for C code stability, the standard teaching examples of Lisp, which emphasize its functional nature, are terrible for code efficiency.
Some tasks are naturally functional, some are inherently imperative, and any large project (even most small projects!) will include both. A good language for large projects provides support for both, as it is foolish to fight the nature of the problem.
In this case they are getting the best of both worlds by using GC where appropriate, and then using special knowledge about the application to optimise away the overhead.
Paul.
You are lost in a twisty maze of little standards, all different.
Located here.
The description of the inner workings of SABRE impresses the hell out of me. However, I've used sabre a lot for getting iternational flights in the past, and I can only recall _one_ occasion when I've not been able to find better/cheaper fares by messing with the search process - kidding the system on that I was going on a single hop flight on each leg that I knew was sensible, for example.
However it usually does do a reasonable job, the savings I can get by extra typing are minimal. My biggest gripe against such systems is that they havent got a clue about what it is travellers actually want to do. I hardly ever want to travel 'from LHR to CDG' (ie specific airports). I'm usually able to get to any airport with in 50 miles using public transport. So in the UK I would usually like to be able to propose Glasgow and Edinburgh as alternates, or Manchester and Leeds/Bradford, etc. But what I really want is not these simple choices but... I'll tell you where I am, and where I want to get to, now tell me about through fares on buses trains and planes from here to there.
Given the description they give of the problem it sounds way too hard. But....
They describe what they're doing as basically enumeration of the graph of all routes between destinations. Once again, this does not mimic what a traveller will do when figuring out how to get from place to place. We construct routes using waypoints - going from one regional aiport to another usually involves connections via hub airports; travelling by train from eg Auchtermuchty to Reading means going via Edinburgh and London. By thinking this way we reduce the number of routes under consideration to a manageable size. (this is also how game ai works. I would include a link to an article on this at http://www.gamasutra.com/ but all their articles are now members only)
Hell I'm sure they know what they're doing - sound like smart guys...
Most people who have tried developing these kinds of systems seem to move away from them over time and end up developing a single-language solution--it's simpler to maintain and debug in the long run.
As Paul Graham said at Beating The Averages, anyone who wants to run a business can say whatever they want in publicity, but they have to tell you their technology in their job ads.
Just to point out that this is another case of the mainframe big iron being more cost effective. Take 200 boxes, add networking, admin cost, and the mainframe looks pretty cheap.
Also, ignoring whether Lisp may or may not be better suited for this problem, the algorithms described can be implemented in many languages with. Indeed, many program use all those tricks.
See http://www.cs.rice.edu/CS/PLT/packages/mzcom/index .html for a way to embed scheme in your Windows apps...support the rebellion! Write VB apps that do all the processing in Scheme! It will improve your sanity, promise.
Since the day I joined Franz Inc. as the new Webmaster, I have been writing more code than at any previous point in my career. I have become immersed in Lisp programming, specifically AllegroCL, which I found to be a stimulating challenge to learn. I discovered that writing Lisp is sheer joy to anyone who has ever been frustrated out of programming by the tedium of obligatory declaration of data types, allocation and de-allocation of memory and the like, or simply by the time they take to learn. To finalize my education in AllegroCL, I was tasked with replacing the Franz webserver with AllegroServe. Though I am not a slow student, I made many mistakes and found that the simplified testing of code via the AllegroCL debugger and the ability to modify a program while it is running were indispensable tools both in my education and software troubleshooting. Making use of these features, I have found that adding new code to a program is remarkably easy to do, even when that new code requires making significant structural changes. In the end, I'm always left with a program which runs as quickly as any others I use and exhibits enhanced stability and security features while maintaining a reasonable memory footprint.
Among my first tasks at Franz was familiarizing myself with Allegro Common Lisp. My interest in Lisp's long, rich and diverse history was one of the chief reasons I applied for the job, so I was happy to oblige. I've always found the history of computing to be of great interest, and Lisp has been there throughout most of the last 50 years (of currently-used languages, only Fortran predates its nativity), so I find its endurance of especial interest. Lisp has undergone a process of evolution during its lifetime spawning several dialects, one of which is Common Lisp; AllegroCL is an implementation of Common Lisp.
The aspects which I find most satisfying in AllegroCL include automatic memory management and dynamic typing of data. Both of these features eliminate a tremendous amount of tedium from coding and allow me to get more work done in less time. I was never a serious programmer before I was introduced to Lisp, but now I've found a passion which outweighs my penchant for computer gaming. In the past, I would frequently spend much of my free time mastering the newest reason to own a 3d-accelerated video card, but recently I've found that I have more to show afterwards if I write code for fun, as evidenced by the chatroom software I wrote as an educational exercise which can be seen in production on my server at home, here (running on AllegroServe). It took a little longer to write the chat software than it usually takes me to master a new game, but at a total of 16 hours, it was less than half the time that most games take to complete. I began working more and producing a tremendously increased level of output, all without the slightest increase in my stress level.
After spending a couple of months with Franz, familiarizing myself with my responsibilities as Webmaster while learning Allegro Common Lisp, I was tasked with converting the Franz website from Apache webserver to an AllegroServe-based solution, which entailed writing a webserver which used AllegroServe at its core and provided all of the features which I found in Apache, while adding a few site-specific features. AllegroServe's chief developer, John Foderaro, and I were able to complete this task in time for the recent release of AllegroCL 6.1. The speed of development under AllegroCL was due in no small part to the ACL debugger of which I made prodigious use early-on. The ability to inspect running code and make modifications at the point of failure not only made it a simple matter to identify and fix bugs, but it was also an invaluable educational tool. Initially, I wrote bad code - lots of bad code - but every mistake I made was immediately obviated and resolved through liberal application of this handy tool. The ability to directly interact with data in a running program provided education that extended beyond the scope of any single programming language, my ability to visualize software structure and the flow of data was greatly enhanced.
After a few weeks of use, I began to realize that I wasn't having more than one bug in my code every few days - needless to say, I was elated. Until this point, I was working on relatively simple aspects of the webserver, such as the Franz menu generation, customer survey, and trial download sections. This accelerated rate of learning gave me enough positive feedback that I felt comfortable taking on more ambitious segments of the project. After I progressed through the header, menu, and footer-wrapping code which provides the interface to my earlier menu generator's output on Franz' "lhtml" pages, I came to the logging facility. By far, writing the code to manage the log handling was the most challenging aspect of the webserver's design so far. It was at this point that John and I came to realize that we would need to significantly enhance the virtual-host capabilities of AllegroServe to provide such services as separate access and error log streams for each individual virtual host. Despite the challenge, John managed to implement these changes in less time than it took me to write the code to handle formatting the logfiles in a manner compatible with Apache's output, which Franz especially required to enable the continued use of certain website log analysis tools. The two of us had completely changed the manner in which AllegroServe handled logging in a mere two days. John also eventually added excellent support for running standard CGI programs which would have their own log streams, and I made use of the added functionality to support a "cgiroot" which allows the Apache-like feature of being able to specify a path in which cgi programs will reside while sending any cgi log output to the vhost error log. I would encourage any current Apache users who wish to try-out AllegroServe to make use of this feature when configuring a server, it makes CGI installation and use a snap. After I'd written the bulk of my contribution to our system, I hit upon another necessary feature, the ability to include in-tree access control files akin to ".htaccess" files under Apache. This was a significantly more complex challenge than the logging and virtual host modifications John and I had previously added, due to the depth of the AllegroServe feature-set we would have to make available for modification within these files, and the associated security concerns. This obstacle took a fair amount of time to surmount, John made significant changes throughout AllegroServe, and we went through a great deal of testing to ensure that no security risks had been created. In the end, we were satisfied that we had made a very worthwhile addition to the webserver.
I continued writing interface and configuration code and enlisted John's expert help whenever I would find a feature AllegroServe lacked, and we concluded the conversion with a version of the Franz webserver that has only required minor modifications since. When I had ironed-out any remaining bugs, of which there were fortunately very few, John assisted me in profiling our code to assess its speed bottlenecks. After heavily load-testing the server, we discovered that the slowest part of the code was that used to check the timestamps on files for the purposes of updating our cache. This was greatly satisfying because the speed of this code was so fast that we could not consider this to be a problem. We also discovered that there was an excessive memory waste within a few seemingly clean segments of code, we were using a dynamically-sized string creation function which relies upon the multiple different data types for the sake of convenience. We converted this to make use of a large fixed-size array which would contain the string, even if it grew as long as it possibly could, and halved the server's memory usage. Bandwidth load testing showed that we had an extremely fast server - we were able to utilize around 850-900KB/sec. across a 10 megabit network when running the system on an Intel Celeron 533. Additionally, thanks to our prior memory-usage enhancement which came-up during profiling, we were only using a total of 30MB of RAM for the webserver, cache and all.
I am very satisfied to have had a hand in such a successful project, especially successful considering that I was a rank novice programmer when I began work on it. The speed with which I learned to program in AllegroCL was an entirely new phenomenon to me, one which has enriched my computer usage and allowed me to express my ideas for software in code, something I never had the capability of doing in the past due to my unwillingness to suffer through the tedium programming had historically presented me with. When I found myself attaining a satisfactory level of programming ability, I was struck by the ease of writing clean and modular code on the first attempt. Augmenting that ability, the ease of adding and restructuring AllegroCL code to a running or non-running program, especially with the aid of the ACL debugger, greatly decreased both my development time and my frustration while further enhancing my level of programming skill. I have learned a great deal about Lisp, AllegroCL, and programming in general over the course of this project, and without it I would not have had the chance to make such a satisfying acquaintance with Allegro Common Lisp, which has become my programming language of choice.
Those who do not know the past are doomed to reimplement it, poorly.
Uh... Scheme isn't a toy. It doesn't have the super-expansive libraries of Common Lisp, but it's used in real world applications all the time. Hell, a month or so back, Transmeta posted to comp.lang.lisp, looking for someone to continue working on some huge Scheme app that they used for design.
Working toward a usable PDA environment in the spirit of Newton OS: Dynapad
Yahoo shopping, was mainly written in Lisp too, as this article by one of the original authors of Viaweb (which is now Yahoo Shopping) details.
Other guy: So, what's your system coded in?
Travel guy: Well, there's a little C for API glue, but about 99% of it is in (LISP, Tcl, etc).
The reactions are lots of fun, from confusion to disbelief to horror.