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 ;)"
5. Every query that hits our site gets sent via tcpip to a Lisp process running on an dual 800mhz x86 Linux box with 2g of ram ($3000, vs about $1,000,000 for a similarly capable mainframe), and the process devotes between 5 and 15 seconds of CPU time to it. One of our customers will have 200 such boxes, each running 2 or 3 Lisp processes. We save on ram by putting multiple processes on one box, since the virtual memory system automatically shares our read-only memory-mapped files between processes.
:)
That is some crazy-fun processing power!
I wish I had 200 of those babies. My 3D Studio rendering would fly like nobodies business
You can't legislate goodness. Let each to his own destiny, by will of his freely made choices.
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.
Go forth ye google hunters! I'm going to bed.
I expected to see a report on how Sabre works... not a long diatribe - 'oooh, look at us - we do it faster!' - about the replacement software these guys have cooked up.
Well done on getting some free advertising.
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
"...complexes in Kansas City, Denver, Germany and Atlanta, and ...."
Is this the Germany I am thinking about? Cool!
"Of course, with things like STL and Java, I think programmers of other languages are also becoming pretty ignorant."
TWW
"Encyclopedia" is to "Wikipedia" what "Library" is to "Some people at a bus stop"
ROTFLMAO, that's too funny, offtopic as hell but way tooo funny.
Y'know, I bet if you went over this with your english teacher and cleaned up the grammar a bit
you could actually post this someplace else and people would take it seriously
; now there's a scary thought.
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
years ago I had a chat with some nice people in blue suits who wanted to know what I knew about an airline system in Kasnas City and what I knew about programming. Turns out that a friend of mine told the nice men in blue suits that I had taught him how to program. He was part of a group of "evil hacker" types and one of them had been running a multi channel BBS. The BBS had two lines and was running on a vic 20. Now the odd thing about this BBS is you could upload as much stuff as your 110 baud modem could choke on and weeks later it was still there. This was odd considering the best you could on a vic 20 was maybe 8 single sided floppys. It turns out that someone from this evil computer club had found out how to transfer stuff off to one of the backup mainframes and he was using that for storage and all the vic 20 was doing was multiplexing data streams and sending out ansi graphics. I still consider that one of the best all time hacks I've heard of.
The Cray T3E weighs in at up-to-3-TFLOPS; depending on number of processors. Of course, this machine costs over $10,000,000.
For something a little more practical and realistic, the extremely-fast yet value priced Compaq AlphaServer rings in at 47 GFLOPS.
Granted, FLOPS aren't a very good judge of speed for this application, but they are easy stats to find. If you really want a standardized test, take a look at the TPC-C stats for the fastest cluster machines in the world. These more accurately reflect the kind of performance stats you're looking for in relation to this article.
You can't legislate goodness. Let each to his own destiny, by will of his freely made choices.
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.
Sabre has been in existence for quite a long time. I have this April 1964 issue of Fortune that describes the system. The magazine also has other interesting articles like "Security Is Too Important to Be Left to Computers" and ""On Line" in "Real Time"".
Most likely, if you have all the PCs on with 2g ram, i would suspect that it is >= to the mainframe. But one nice thing is that you can sleep these when the load is lighter. Even though the web is 24/7, there is a noticable difference during day vs. night (MST). It would be easy to then scale up when you need these. BTW, I suspect that they now run p4's of even a lower powered risc chip.
It has performance as a key objective. With a good compiler on a decent machine (i.e. not x86) it has a fair chance to produce reasonable code. Java on the other hand...
is better for write-only code :-)
SABRE != Orbitz. The author's company ITA software writes software that the ORBITZ site uses to answer queries against the same flight/fare dataset that SABRE and the other CRSes use, provided by the airlines.
Think of the various systems, SABRE, etc. as just different systems that are using more or less the same amalgamation of airline-provided data.
SABRE, and the other CRSes themselves are still running the big iron mainframe stuff, not LISP or Linux, and will likely remain so for a long time.
There's 10 types of people in this world, those who understand binary and those who don't.
I just finished CS161 (Artificial Intelligence) at UCLA last quarter.... nice to see some applications for the stuff they teach us here, as most of it seems like garbage. -Berj
Located here.
I was also under the impression that Sabre make a lot of use of the Versant ODBMS. Pretty advanced stuff.
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.
The airline trip planning problem sounds very similar to constrained graph search problems in speech recognition (which are now routinely carried out in real time on graphs with millions of nodes). It would be interesting to see a more detailed statement of what the problem actually is.
If some of the terminology in this article gets too daunting, check out this online Dictionary of Algorithms, Data Structures, and Problems
evanchik.net
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.
Surely it's "Lithp"?
;-)
Yeah Yeah Yeah I know it's poor too
Was recruiting Lisp programmers from an Slashdot ad! :-)
Am I the only one who was busy solving those puzzles they posted? (I know some people like Kaz
solved it, and posted hints on usenet.)
Reguardless of the language, I found the post insightful and informative. All of the techniques and decisions described in the post can be applied to most projects. Sure, most websites don't need to support the massive number of searches like Sabre, but programmers can apply those principles. Keeping a balanced foot isn't easy and there's always politics added to the brew, but with perseverance, programming can be something that provides a great service and tremendous personal pride.
Well, not really. The lack of higher-order function will eventually force you to use imperativeness. Then, the missing 'const' keyword won't be there to help you mesure the spread of your imperativness. The two togheter makes it rather useless to attempt coding in fn-style in C.
With C++ however, I'll agree you can enjoy some of the befinits of fn-style. In fact, I posted a little piece about it.
This post was compiled with `% gec -O`. email me if you need the sources
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.
I'd like to see somone post a couple of brief examples of things that were well-suited to Lisp (and would be much more difficult in C) - anyone have anything handy?
Functional programming vs. imperative programming have nothing to do with efficiency. At least not run-time efficiency.
:) Java is just LISP with objects and fancier syntax...
For an example of an (very basic, and done by all LISP implementations, and even partly by some C compilers, e.g. gcc) optimization, see "tail recursion optimization" in your nearest LISP-implementation documentation.
As yoy state, some problems are "inherently" imperative, and some are functional, to their nature, but that has more to do with how easily their solution is formalised in either formalism, not how well that solution is then executed.
But I think one should not emphasis that property as much as that LISP does have a garbage collector, which C does not have. It does not _allow_ for you to have neither memory leaks, nor crashes due to multiple free()'s of the same location. And it doesn't have any sprintf() that can produce buffer overruns. But OK, then you could use Java
Also, as you state, lambdas and higher-order-functions are central to what's good about LISP.
--The knowledge that you are an idiot, is what distinguishes you from one.
http://ictg.canterbury.ac.nz:8000/sql-tutor/
Dont know if this link still works from everywhere.
Sabre runs on a highly specialized operating system (not really but that is the closest analogy) called TPF (Transaction Processing Facility). The majority of the system is written in macro based 370 Assembly. Just now, there has been some C development deployed comercially. Sabre handles sustained message arrival rates that are insane (on the order of 6000 messages per second)! In order to do that with 1970's technology, you have to write down to the metal!
An RPN calculator? Back when I used to play with Scheme in school (Scheme is the toy version of Lisp), I noticed that anything with a stack based logic was natural in Scheme. The C implementation was considerably less elegant in the end.
I read the internet for the articles.
The article is talking about front-end software that could do fare shopping. These guys aren't replacing the mainframes that run the airline industry - they're providing a nice interface to use the data managed by the mainframes.
/. just ran a nice ad for some folks who are trying to get some work building software for online travel sites.
Based on the line claiming that they work with 2Gb of static data this sounds like the original message referred to a prototype. The reservation systems measure their data in Tb, and it's very dynamic.
Looks like
(Note: The Sabre bomb-proof bunker isn't located in any of the cities listed. I know because I can look out the window and see the top of it. See this.)
You never really know how close to the edge you can go until you fall off.
Looking at your page, maybe you might want to try
out another level of functional (but very inflexible) computing
possible with C++.
It's a bit extreme and completely offtopic, but more efficient
than this (save for pre-calculating) I cannot imagine:
#include < iostream>
template < int N > int factorial() { return N * factorial < N-1 >(); }
template <>
int factorial< 1 >() { return 1; }
int main()
{
std::cout << factorial< 10 >() << std::endl;
}
ITA is currently hiring for a variety of positions.
Here is the link.
The Sabre system is maybe the more interesting case study - how engineers kept an ancient and likely antiquated system up and running in the face of massive industry/technological change.
You are right. The original title of this article was "Inside Orbitz", but within slashdot they edit the title and description you submit, and in the process all the references to Orbitz got changed to Sabre. They are different programs. Sorry if this has confused anyone.
--pg
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.
Not knowing too much about GC, could someone tell me whether it would be possible to implement a solution , using a dual processor computer, where one CPU does the work, while the other handles the garbage collection. Would it work and would this be one way of dealing with the performance issues?
Jumpstart the tartan drive.
Franz Inc. interviewed Jeremy Wertheimer, founder of ITA Software, about why he used Lisp to build their software. The story can be found here:_ mi ning/itastory.lhtml
http://www.franz.com/success/customer_apps/data
functions that have multivariable output
in C I have to do tricks
in LISP it is natural
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.
I think its great that Orbitz has such cool software. But there web site is abismal. I've spent more money than I had to on flights there. Well, no more...
Unfortunately, I still think that the ease of use award goes to -- Ugghhh -- Expedia. The expedia site is simple, clear, does not flood you with data. Itineraries are presented in simple concise ways that people can understand.
I got stuck with a night lay-over in Baltimore in an itinerary, in a flight from Boston to Saint Louis. Somehow, Orbitz thiught that it could present me with that, Well, I didn't see a night layover in the itinerary until I had printed it out... Expedia makes it easy to see that sort of problem with a flight up front.
All the software in the world cant fix a bad user experience.
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.
Hi,
I am working for ITA and like to comment on some issue brought up here:
1) As said, we talk Orbitz here, and not SABRE. Currently, Orbitz
uses our software for domestic US flights, not for international.
2) Our engine does not use a functional programming style, rather the
opposite. Still, we found that Lisp is a great advantage. While
each hacker here has own preferences why he/she likes Lisp, key
elements (I see) are:
2a) macros, especiallly macros that allow us to define new iteration
constructs. C programmers can thing of being able to write their own
for/while/if as seem appropriate for the task as hand. Especially
with-[whatever] constructs, but also nice tricks with
destructuring-bind.
2b) scope, working annonymous functions with static scope. Kind of
Java's inner classes but in 1/10 of the codelines.
2c) said destructuring-bind which frees your from a lot of boring and
error-prone tasks of tree parsing with a snap.
2d) compile-time computing, a key element to make our software fast
without cluttering it up by expensing manually written source code by
a factor of 100 or by inventing ad-hoc code generators which need to
be debugged after they broke your system for weeks. Macros that can
use the full language at compile time and macros that can "walk" their
argument when passed at compile-time to find interesting things to do
with them. Also see define-compiler-macro to get an idea what makes
Lisp code fast while maintaining elegance (use with care, though).
2e) safety. A language without optional overflow checking of integers
is a toy at best and dangerous at worst.
2f) debugging and testing with the read-eval-print-loop (REPL). Like
the gdb prompt for evaluating code, but you can use the native
language and you have the full language. Or better like a shell where
thing's aren't echoed in ASCII and need to be re-parsed, but you get
the real objects you can play with (send message as defined in your
system). The debuggers in Allegro and CMUCL are rather crappy, IMHO,
but the REPL and ultra-fast re-compilation and loading of single
functions (standard feature of every Lisp) -used for debugging print
statements- make more than up for that.
Keep in mind that everyone of our Lisp hackers can contribute a Lisp
of similar length, this is just what *I* like.
For the record, I like C++, but I couldn't absord all the application--specific knowledge I need while spending my day figuring out C++ specialities and keeping them swapped in. C++ is for full-time C++ coders only.
While it may be possible to create 5000 connecting flights between Boston & LA with a maximum of 3 hops in a 24 hour period, you'll have to include flights like:
LAX -> JFK
JFK -> SFO
SFO -> BOS
It shouldn't take a smart computer to rule those out. Also, the possibility of 5000 (going) x 5000 (returning) x 100000 (fares) is ludicrous. Plus, airlines use hubs airports, so there are only a limited number of logical flights.
And to top it all off, you don't have to consider every combination. You can start with a list of (arbitrary number) 50 likely flights for price, time, speed, etc. and try their connections. You just do a simple query, pull up the 5000, and before even eliminating illogical and conflicting ones, pull a few the top of the list.
Not really. The objects searched over (phonemes) come from a relatively unchanging set having relatively unchanging attributes (frequency, duration, level, etc.) and are mapped to a relatively unchanging set of objects (vocabulary doesn't change that fast). New service levels, attribute changes, and itineraries need to be taken into count in the airline booking issue.
In the end, it's the flexibility in adding new models and code to handle new models in a seamless manner that makes Lisp (and other dynamic languages - e.g., Smalltalk for finance, Erlang for multiprocessing phone switches) so appealing for this type of problem.
That is all.
Those who do not know the past are doomed to reimplement it, poorly.
oh men, we realy shouldn't make fun of poor C++'s limping after-thought compile-time computation facilities. Think of its fellings!
:'-)
But when you think the equivalent elisp code is:
(defun fact (n) (if (= n 1) 1 (* n (fact (- n 1)))))
((insert (number-to-string (eval-when-compile (fact 10)))))
I can't help to think : So many code generator could have been avoided if C++ had included something like eval-when-compile. So many it makes me weep.
This post was compiled with `% gec -O`. email me if you need the sources
I'd like to see somone post a couple of brief examples of things that were well-suited to Lisp (and would be much more difficult in C) - anyone have anything handy?
If you're interested is LISP, you should take a look at Paul Graham's excellent ANSI Common LISP, a wonderfully written introduction to LISP which is nonetheless a decent resource which can almost replace the much heftier Steele. If you're not sure you want to spend the cash, the first couple chapters are online.
In this very small, very chatty book for beginners with not too much code, Graham nonetheless manages to include examples such as a ray tracer (90 lines of code); a program to dynamically generate HTML pages (119 lines of code; this program (very much expanded, but without a single rewrite) now powers Yahoo! Stores); and a complete, seperate object-oriented language with multiple inheritence (89 lines; but a much more powerful OO language, CLOS, is already included with Common LISP). The last two in particular would be impossible to do as quickly or easily in C.
A much bigger LISP book I happen to have at the moment is Peter Norvig's Paradigms of Artificial Intelligence Programming : Case Studies in Common Lisp, which includes a whole lot of impressive and/or historically interesting examples, including ELIZA, STUDENT (solves algebraic word problems) MACSYMA (symbolic integration ala Mathematica), a Prolog interpreter and compiler, a Scheme interpreter, an optimizing LISP compiler, a natural language grammar parser, and a couple other things. I just finished (well, turned in...) a project which extended Norvig's code to play the game Othello, also from this book, to use trained neural nets (which unfortunately didn't train all that well). The coding part of this was made darn easy by the fact that Norvig's Othello function takes as inputs two functions which provide the move-selection strategies for black and white respectively--something that can't be done in a language without functional closures.
I certainly wouldn't want to do any of these in C; although all of them could be so done, it would only be at the cost of a good deal of length, functionality and elegence.
In general, LISP is great for anything involving GOFAI (good old fasioned AI, i.e. non-stochastic), anything that needs to generate hierarchically nested text (e.g. HTML, XML, or LISP programs), anything that needs to be written quickly (or LISP can be used as a rapid-prototyping language), any sort of interpreter, or for any time you wished you could modify the available programming languages to build one that really suits your problem. LISP is also great for extending existing programs, which is why almost every user-extensible application uses a dialect of LISP to do the job. (e.g. emacs, AutoCAD, etc. No, VB macros for Word don't count, although it is noteworthy that LISP is useful over such a wide range of programming tasks as to be a replacement for VB and C.)
What is LISP bad at? Well, its libraries can be rather weak and nonstandard (although ANSI Common LISP itself comes with a large array of useful functions); GUI stuff, multithreading, and networking all fit in this category and are often implementation specific. (Of course, this is nothing to do with the language itself but just with what tools are available.) Its use for really low level bit-twiddling stuff is somewhat awkward. Iteration in LISP suffers somewhat from being only a little bit more powerful than iteration in C; the upside is you can still combine it with all the other great stuff in LISP, but the downside is that the parenthisis-style syntax, which is so much better for writing macros and functional code, only clutters up iterative code.
And, certain of the most powerful features of LISP, like macros and closures-as-first-level-objects, take a bit of experience to wrap your mind around, as does the functional programming paradigm. (LISP does not in any way require functional programming; it's just that while there are other languages as good as LISP at iterative code and arguably as good as LISP at OO code, there is nothing as good for functional code.) This is usually taken to mean that LISP is only suitable for CS students and AI researchers, because ordinary programmers are too dumb to get this stuff. I'm just a CS student, and I haven't had much experience with how dumb ordinary programmers are or aren't, but intuitively I think this argument is bunk.
Personally I think these techniques are just new things to learn; subtle and powerful, sure, but so is simple recursion the first time you learn it and every programmer knows how to use that. Indeed, once you understand recursion well, functional programming and function closures are not very large conceptual leaps at all. Sometimes the mechanics of lambda closures can be slightly tricky, but no more so than referencing and dereferencing pointers in C, and with a lot greater payoff. Hell, the most complicated uses of functions as objects in LISP are a lot easier to get right IMO than even simple uses of templates in C++, and "templates" (i.e. generic funcions) come for free in LISP, due to runtime type checking. (Of course, this is why no one uses C++ templates, but whatever.)
Macros are difficult to write. But then again, they are incredibly powerful, and not "necessary" very often. And it's usually *extremely* easy to understand someone else's macro code, which is all a novice would have to do anyways.
Plus there are lots of features of LISP which make it incredibly easy for beginners. Debugging in LISP is ridiculously easy, at least for programs which don't use too many functional closures or complex objects. Instead of the C paradigm where you only have one big executable main(), LISP programs are made up of lots of little functions, all of which are callable (and thus extraordinarily easily debuggable) from the top-level evaluator. There's no write-save-compile-test-debug loop; it's all together, and all very fast. Immediate feedback means more willingness to take chances, try out things, and make mistakes.
Plus, because there's no main(), your programs are always extensible. If you want to, once you're done with a function it's trivial to make a larger function which calls the other function, takes it as an input, etc.
There is no need to manage memory, no need to futz around with pointers, and no way to cause a segfault until you start optimizing. Buffer overflows are impossible. You can start with a skeleton of a program, gradually add functionality, and only add optimizations at the end when you have tested your code; and you can test every new function or optimization, so you know exactly what goes wrong when something does.
And it's fast: once you put in proper optimizations, compiled LISP is nearly as fast as C. Of course this wasn't always the case, and it's not the case for LISP before you put in type declarations. And a compiled LISP file will probably be bigger than compiled C code, especially when you add the LISP top-level eval to it. On the other hand, C is usually not as fast or small as well optimized assembly code, but there is a good reason very few people program in that anymore: because programming in C makes your code less buggy and much faster to develop. Similarly, programming LISP will almost always make your code less buggy and much faster to develop than using C. Now that compiler technology and computer hardware have made those differences almost moot, it probably makes much more sense to use LISP than C.
Of course, the result of this change has not been to drive more people to LISP, but instead to drive LISP's features into other languages. Thus we have C++ with attempts at generic functions; Java with decent OO and automatic garbage collection; Python showing the usefullness of an interactive top-level. Nowadays Perl and Python are getting functional closures and the list datastructure, although their functions are not quite first-level objects and so not quite as powerful. Plus it will probably take another prefix-syntax language for macros to be copied properly.
Whether the world will realize that LISP already exists (and indeed has since the late 50's) or continue to reinvent it, I dunno. Probably the latter so long as LISP remains short of libraries that tie it down to modern computers. (Again, GUIs, multithreading, networking.) Still, it's probably worth learning LISP just so that when the same ideas come out in more "mainstream" languages years from now you'll already know and understand them.
The real reason why people haven't done this "simple" task is that it ISN'T as simple as it sounds and that "simple" solutions turn out to be woefully inadequate when confronted with "real-world" data and problems.
That is all.
That's just the point, actually. It is the job of the search process which does eliminate possible, yet very inefficient flights like that.
So they should have written the code in SQL Server 2000 with a COM+ TCP monitor -- Microsoft rules the TPC-C measure having overtaken the big guns there some time ago. Or should I say "STOMPED ON IBM AND ORACLE". Notice that Linux is not a player in TPC-C. Not on the radar screen..
Common Lisp contains the most advanced iteration constructs I've ever seen in any lanugage, including C, Perl, Python, and others. It's called extended loop, and it doesn't need lots of parens. It's not used by by Graham or Norvig, since Graham despises loop and OO and Norvig uses applicative style since that fits most AI problems extremely well.
Also, there's series, which gives you lazy-functional list operations which compile directly to an iterative form when they can be. This makes for very elegant-looking code while maintaining maximum performance. It's also extremely extendable, as you can define your own functions which operate on series objects and get compiled into the iterative form just like the functions that series comes with.
--
Rahul Jain
Here's one.
Read two numbers.
Add them together.
Print the result.
(No restriction on size other than assuming that you have enough memory)
I find the bit-twiddling abilities of Common Lisp to be pretty advanced compared to C.
Granted, this depends on what you mean by "bit-twiddling"--smashing memory based on a pointer given to you by the OS is going to be implementation-dependent.
However, for actually pulling bits out of data and re-arranging them, I find the Common Lisp routines to be great. You can assign/extract integer values to/from any consecutive block of bits, without having to compute the masks and shifts yourself. I've found this quite nice in creating code that converts to/from native IEEE floats from/to other floating-point formats.
you can write functions in C!
you can even do stuff like:
do(something(else(again(and(again()))));
but the reason you don't is because people realized that it isn't maintainable, any you'll probably lose count of the parentheses. Of course a LISP guru would probably complain about the semi colon. Before they get to excited about their own superiority and job security, they should realize most VB types will pick up LISP very quickly, thanks to their experience with *gasp* Excel.
You are abolutely right, it's easy.
Unfortunately you're just talking flights and not fares. [Hint: if you think you pay a price for a flight you board like you do in a Bus, you're wrong].
In the wake of 9-11, there will be a new need arising for similar software applications involving massive computations and selections of data in the realm of graph theory, etc.
Not for finding the cheapest of a set of flight segments, but instead for finding connections between people-to-people relationships in the search for hidden, secret connections between terrorists and their organisations. That's how the law enforcement investigative process works: you map out all the relationships that one person has with other people, then all the relationships those people have with others, etc, until you have a huge network of "connections" and related parties.
Software of the type used in SABRE/Orbitz/whatever for the traversal of these huge trees and graphs databases will one day be employed against the coming database that will be filled with data on every person in the nation and all their relationships (family, friends, co-workers, etc) to others.
ITA's software allows you to specify that you'll also accept airports within X miles of your source and destination cities (you can specify the distances separately). Check the link on their main page on the right side to try out their software.
The huge explosion of possibilities doesn't come from the possible routes (note that their software can search multiple airlines and do mixed-airline trips, too, so the number of hub cities is quite large) but from the number of different fares and restrictions on those fares, as the email from Carl explains.
--
Rahul Jain
Even though ITA doesn't use any mainframes, the original Lisp was developed on the IBM 370, IIRC. The names CAR and CDR came from the assembly language of the 370, since John McCarthy couldn't think of anything better to call them. Since then, he's come up with FIRST and REST, but they only make sense when you're assuming that the cons cell is a list, so CAR and CDR are still used (for raisins other than the hysterical).
--
Rahul Jain
I wasn't directly on the team, but I was in close contacts with developers (4 guys at best time, 2 at worst), so I'm pretty aware of what's involved. It's one hell of a task. It's not clear if ITA guys do a real-time verification of flights availability which adds extra 5-10 sec per flight (at least). But as a note it seems like a lots of hardware and code. Our code was written in C and was using one 4-way IBM H80 to do the algorithm and one E30 to communicate to the Sabre/Galileo/Worldspan. It was guaranteed to give at least answer withing 50 sec and it worked about 90-95% of the time... And there wasn't ever single mathematician on the team. Unfortunately project was closed month ago (damn big bosses - don't know cool thing when they see one).
----
... <eventn>)
... <eventn>)
... <actionn>)
I'd like to see somone post a couple of brief examples of things that were well-suited to Lisp (and would be much more difficult in C) - anyone have anything handy?
----
One of the things that Lisp/Scheme is good at is as a tool for creating so-called "little languages" - miniature programming languages that are specific to a single problem domain.
Consider, for example, a computer game that had a "modding" API, allowing players to create their own levels and missions. The API would need to provide, amongst other things, a mechanism by which events could be trapped and bound to actions.
A Lisp/Scheme programmer might decide to tackle this problem by defining a little language that understood the concepts of events and actions.
For example, the "language" could provide a set of primitive events like this:
(item-taken <item>)
(item-destroyed <item>)
(item-activated <item>)
(item-proximity <item>)
(and <event1> <event2>
(or <event1> <event2>
(not <event>)
Using these primitives, we could trap more complex events such as:
(and (item-taken documents)
(item-destroyed generator)
(or (item-activated homing-beacon)
(item-activated cable-car)))
There would also be a list of primitive actions:
(play-sound <clipname>)
(display <string>)
(restart-level)
(skip-to-next-level)
(do-nothing <seconds>)
(activate <object>)
(destroy <object>)
(then <action1> <action2>
Compound actions could be specified like so:
(then (display "The reactor is going critical!")
(do-nothing 10)
(play-sound whine)
(do-nothing 5)
(play-sound explosion)
(display "The reactor has been destroyed"))
Putting all this together, we could bind actions to events in the following way:
(define-event rocket-launch
(and (item-taken key-card)
(item-activated control-panel))
(then (play-sound rumble)
(pause 3)
(activate-object rocket)
(destroy-object hanger)))
All that remains is to create a compiler for this language that will translate these expressions into a lower-level form suitable for use in the game engine. E.g. the compiler could output C code suitable for inclusion in a DLL.
What is LISP bad at? Well, its libraries can be rather weak and nonstandard (although ANSI Common LISP itself comes with a large array of useful functions); GUI stuff, multithreading, and networking all fit in this category and are often implementation specific. (Of course, this is nothing to do with the language itself but just with what tools are available.) Its use for really low level bit-twiddling stuff is somewhat awkward. Iteration in LISP suffers somewhat from being only a little bit more powerful than iteration in C; the upside is you can still combine it with all the other great stuff in LISP, but the downside is that the parenthisis-style syntax, which is so much better for writing macros and functional code, only clutters up iterative code.
Multithreading is found in the commercial Common Lisp environments and in the CMUCL/x86 port. CLOCC maintains several libraries for cross-implementation usage of non-standard features such as networking. CLIM solves the GUI problem, the problem is that there was no free CLIM implementation for a long time due to legal issues. Finally, a free CLIM is being developed: McCLIM and I'm sure they can use help. As for iteration, perhaps your mind has been clouded by Paul Graham; who has an irrational fear of the LOOP macro. The LOOP macro, however, provides one of the most powerful iteration constructs I've seen; and it's not parenthesized like the DO macro is. Example:
(loop for x from 1 to 10 summing x do (format t "~&~A" x))
Prints out a list of numbers from 1 to 10 and the sum of them all at the end.
The equivalent DO:
(let ((sum 0))
(do ((x 1 (1+ x)))
((> x 10) sum)
(incf sum x)
(format t "~&~A" x)))
Also the LOOP macro provides yet more keywords for all sorts of handy features which aren't so easy to do with DO; collecting, appending, finally, initially, if/else, etc... Please read the section in the HyperSpec about LOOP, Section 6.1
I even once wrote a finite-state-machine entirely within a single LOOP macro that processed the Unix mbox format. It's quite nearly a language in itself (speaking of which, FORMAT is in a similar category, except for formatted output instead).
I would argue that CL is better at bit-twiddling than C is. Take a look at the CLHS Section 12.1.1.3.2 and the functions BYTE, LDB, and DPB. It's a different perspective than the C view, but more interesting since you can extract and replace any number of bits that you want. Also it's not dependent on 8 bits per byte.
Still, there are many areas where CL just doesn't have the sheer effort put into the libraries, likely due to the lack of manpower. Particularly in the Free-software category; Lisp has a tradition extending long before the current wave of Free-software and while many commercial vendors will provide good support and lots of libraries, the Free implementations often lack this. Many Lisp programmers use the commercial Lisps and have the features they want; if not they ask/pay the vendor to implement them. Another issue is that Common Lisp is not Unix-centric, unlike *ahem* most popular languages today. CL was designed to be workable in any environment, so the designers could not take shortcuts with things like pathnames, executable formats, system libraries, or other system-dependent issues. After all; Common Lisp was conceived in the era of the Lisp Machine. Unix was just another OS in the vast array. Finally, it is unfair to compare the Common Lisp standard against a single-implementation language such as Perl. Standards cost $$$$$ and require a great deal of effort and responsibility. If a Common Lisp implementation does not comply with the standard then it is at fault. But with Perl, whatever Larry Wall does goes. Even if it breaks all your code; too bad.
Some interesting sites with regard to libraries:
(Back to the OP's topic) Franz's Success Stories has plenty of examples of Lisp applications. Franz develops Allegro Common Lisp, a popular commercial CL.
Those who do not know the past are doomed to reimplement it, poorly.
The functional style is far more maintainable than the imperative style, for any intelligent person (being able to program in Perl, VB, etc does not make you intelligent). It's so maintainable that you can prove its correctness using formal logic. If that's not an argument for functional-style programming then I don't know what is.
If you still count parenthesis you are a fool, plain and simple. There are many editors out there which count parenthesis for you, amazingly enough, and some go beyond by providing navigation commands based on S-expressions and automatic indentation. If you're still in the stone age, I'm sorry for you; stop using your crappy line-editors and join the modern world.
And the semi-colon would indicate a comment, btw
The bit about Excel is interesting. Care to elaborate?
Those who do not know the past are doomed to reimplement it, poorly.
>you can write functions in C!
>you can even do stuff like:
>do(something(else(again(and(again()))));
Don't embarass yourself. Being functional isn't about calling lots of functions. It's about being able to create functional closures. To wit:
(lambda ()
(let ((foo 3))
(lambda ()
(set! foo (+ foo 1))
foo)))
Is a function which returns a function which increments and returns a counter value. Each time you call the outside function you get a new distinct counter and increment function.
Functional closures can be really handy. You even see poor man's closures in some C programs. Ever notice how many library callbacks in C have an extra void pointer argument?
Something like:
typedef void (*callback_t)(int, void *);
void do_something(some_data_struct *t, callback_t cb, void *opaque);
You call do_something which eventually calls the callback function a bunch of times with an int argument derived from elsewhere and the void *opaque passed into the do_something call. This way you can pass in whatever extra state your callback needs to do its processing.
In Lisp, you don't need to monkey around with all of this void * cruft. You can just create a function inside of a let which declares the variables you need to share in your callback. Most often the variables you want to share are already locals so you just write your callback function in place and get on with your life.
Excel doesn't teach you anything about this, nor does VB.
The vast majority of language preferences reduce to religion, and of those the vast majority are dilettantes who know a dozen languages or fewer.
In reality, LISP isn't slow, and it really never was, compared to the alternatives. About 20 years ago, some deluded souls converted some heavily numerical FORTRAN code to LISP and found out it ran about 20% faster on LISP. I call them deluded because they were under the false impression that any of the detractors of LISP would care. They don't.
People prefer languages primarily for cultural reasons. LISP fits certain cultures and doesn't fit others. You can say the same about FORTRAN, C++, Java, Visual Basic, or any other language you like. Pseudo-quantitative arguments come later as justifications to be used in arguments.
Beyond that, different languages are good for different things, but it's almost impossible to have a discussion about it. If we were to have such a discussion, I would say that LISP is a great choice for anything involving graph theory, which a reservation system obviously does.
Me, I'm in the middle of writing a game engine and editor that's built in C and C++, does the plotting in an embedded Scheme, uses a Postscript-like code for run-time, interfaced with the Scheme, and under OSX uses Objective C for the user interface layer. So, what do I know anyway?
> Tail-recursion is nice, but macros like LOOP
> with the extended syntax are quite powerful. I
> would say that Common Lisp is better at iteration than
> most other languages.
I totally agree. The LOOP macro isn't just a way to do for, while, and foreach like we find in most primitive languages- LOOP is an entire language in and of itself. Immensely powerful.
Working toward a usable PDA environment in the spirit of Newton OS: Dynapad
Actually, it is usually much harder. While it seems simple enough, the fact of the matter is when you are doing a deep recursive search through the schedule, it gets (almost) expotentially more complex. First of all, you are assuming some intelligent database structure. Allow me to assure you, there isn't one. ATPCO issues mulitple fare and schedule updates a day and they are simply too huge to get into any kind of elegant relational order before they become stale. Additionally, all World Class CRS' (Computer Reservation Systems) which descend from the original IBM/AA development (ACS?) must answer this question first: Do you fly there? All of the data structures within the system are modelled around this one question (which nobody asks anymore)! While we humans now take for granted that air travel between two points is possible (regardless of direct flights or hub and spoke systems), the computer cannot. So, it begins it's search with LAX->BOS. Then, it moves to ???->BOS. Then it moves to LAX->???. Then it goes to ???->???(1) and so on and so on. Once it has determined the available routes, it then applies fare rules and tariffs on each segment. Walla-Kazam! 50 seconds has passed. All of this to answer the questions which are being asked:
What is the way to get there? (Cheapest, fastest, least number of connections, etc.) The deal is if the WC-CRS (Again, World Class CRS) cannot provide consistency in it's results, then the government starts coming down on them big time. Also, now WC-CRS companies are content providers to the general public. This means they are held to much higher degrees of scrutiny by the average consumer.
Travel agents used to fill the gap between the limitations of the WC-CRS and the consumer's needs. The fact that they may know alternate candidate routes which do not routinely show up in searches is one area where they add value in the travel marketplace. However, as the systems surrounding the WC-CRS become more sophisticated, the agents are finding that the general public would rather reduce their cost by not paying the higher price for their involvement.
Sorry, I formatted the question which is being asked incorrectly. It should be:
What is the [Fill in the blank] way of getting there? This question is incredibly difficult to answer given the current system's architecture and data models.
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
A simple eval would have done nicely as well, but then again, strong typing is for weak minds.
Have a nice day.
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.
OK, the usual /. banter. Lot's of flames on languages, but nothing on-topic. Any of you guys have a good link to info on SABRE?
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.
I find the bit-twiddling abilities of Common Lisp to be pretty advanced compared to C.
Granted, this depends on what you mean by "bit-twiddling"--smashing memory based on a pointer given to you by the OS is going to be implementation-dependent.
However, for actually pulling bits out of data and re-arranging them, I find the Common Lisp routines to be great. You can assign/extract integer values to/from any consecutive block of bits, without having to compute the masks and shifts yourself. I've found this quite nice in creating code that converts to/from native IEEE floats from/to other floating-point formats.
Interesting comment. I should have said that it was my *impression* that LISP wasn't particularly suited for bit-twiddling; I haven't had much experience with that aspect of it myself. Glad (and not terribly surprised) to hear that it's better than I reported.
uhhh....Orbitz? As in the topic of the article?
More seriously, the people who wrote Orbitz didn't pick Lisp just to make a theoretical point. They picked Lisp because they did not want to face the daunting task of solving their problem in C/C++. You might not believe it, but they did---and they are the ones making big bucks from it.
Visit the sites of major Lisp vendors (Xanalys.com, allegro.com) and they have many examples, often involving heavy-duty logistics or information management. Basically, everyone who can solve their problem using C++ uses C++. Anyone who has problems that can't be solved using C++, uses Lisp, decides to live with their problem, or creates more of a problem by trying to create a C++ solution.
There are many capabilities of Lisp that let it solve daunting problems; the fact that macros can manipulate code using code written in Lisp is a big one.
The previous comments that Sabre is not moving off the mainframe is inherently false. The relase definitely says migrate, and that's not supplement.
Perfectly understandable in a way, Sabre is some honking old code and many of the apps programmers must be reaching the retirement/consultant stage of their career.
IBM is also moving to 64-bit machines and ran off it's competitors with the horrid firmware clean-room reengineering compatibility would require. IBM is celebrating victory in the 30-Year Mainframe War by increasing costs of the high-end mainframes for deep-pocket companies. I'm guessing Sabre got the bill for the next few mainframe years and decided to get out while the getting is good.
________________________________________ History Must Not Fall Into The Wrong Hands ___________________________________
Well - I think the single most important feature are macros. They are a quite powerfull resource because they can really transform code before it gets compiled. I can give you an example that is quite concrete: evaluation of polynomials.
I wrote a small macro that takes as its first arument a list of coeficients and as a second arument a number. The code that ends up being executed is the evaluation of the polynomial using the horner scheme. That is, instead of
1 + 3 x + x^2 + 7 x^3
the code executes
1 + x*(3 +x*(1 + x*7))
and the invocation is
(horner-eval (1 3 1 7) x)
The point is that all the coficients end up as immediates.
Another example is a transformation of notation. If the prefix notation pisses you off, you can write a macro that evaluates infix notation. So insted of writing
(+ (* a b c (- 5 (/ d 2))) 4)
you write
(infix (a * b * c * (5 - d / 2) + 4))
Now try to mess with the syntax in C.
Another thing that is quite interesting is the posibility to change running code. You stop (with contol-C) the simulation that has been running for a week and substitute the function darn-inner-loop (compiled, mind you) with the faster version you've been working on. Then you let it continue. I think hot-swappable code is a nice way to describe this.
Now do *that* in C.
Last but not least, I can write a program that writes the code for a function (for example, the evluation of N5(x), the 5th order b-spline at x), with all the constants that would usually depend on the parameter (order), as immediates, compile it, and return it as a value to be used in the rest of the program (the compiled & optimized function!).
Just some examples.
Cheers
rmstar
I must admit it was some time since I hacked CL, and that I am biased towards Scheme. Scheme does require a GC, aswell as certain constructs of the language to be tail-recursion-optimized.
:)
:)
Okay, LISP doesn't lack objects, but it does lack (automatic) function dispatching depending on the type of an object. But this could easily be hacked into it, if someone wanted to
I have read some about MOP, and am really impressed. That is probably one of LISPs biggest strengths - introspection. All aspects of a program, and the language, can be determined, and controlled, by the progrram itself.
I have read some of the CL HyperSpec. But as I said before, I'm blinded by Scheme after reading too much of r5rs and the SRFIs
--The knowledge that you are an idiot, is what distinguishes you from one.
Disclaimer: the closest thing I've done to any real functional programming is a weird mix of logical and imperative programming in Prolog, so I may have a warped idea of what functional programming is.
But... a curious observation.... this last semester I was encouraged for a "Teaching with Technology Class" to develop an application using Excel with a limited number of Visual Basic macros thrown in. As I spent time working with the system, it occured to me I was actually doing functional programming. Each cell was a function call, which could only be fed results of other cells/function calls.... (any comments on whether this is actually true?)
It turned out to be a bit confining; iteration was a bit painful, and I ended up with a big state table that I was proud to simply have come up with, messy as it was. But it was also interesting to see what you can/have to come up with when confined. In the end, the application worked.
Libertarianism is rich wolves and poor sheep playing gambler's ruin for dinner.
Isn't there also some stuff written in a Qix or something like that... ISTR it came from Qantas, hence the Q.
What does "LISP" stand for?
"Lost In Superfluous Parentheses"
If any bozo with a P3 COULD do it, they would have. Scheduling and fare rules are infinitely complicated beasts. The access methods used by Sabre and other CRSs may seem arcane, but they are VERY efficient. I work in this every day and the volume of data is overwhelming for many SQL based systems with wholesale changes happening every day. The Sabre CRS gets more requests per second than many systems get in a day. Other CRSs are in the same boat. They certainly aren't pretty (but hey, Perl wins no beauty contests either) but it gets the job done. To replace it, you need something better and faster to justify the costs, not just something that does the same thing on another platform. Travel agencies would have to own huge servers to host their own systems even if the software were free and it would be highly inefficient tranfer all the data to hundreds of travel agencies.
Okay, LISP doesn't lack objects, but it does lack (automatic) function dispatching depending on the type of an object. But this could easily be hacked into it, if someone wanted to :)
I'm not sure what you mean by this? What do you think having various methods for a generic function does if not dispatch based on the types of the arguments? Perhaps you ought to make section 7.6 one of the sections of the CLHS that you read. :-)
Proprietary data.
bozo and me can't get access to it, no matter how much we pay, on account of the airlines (and travel services) don't want me to know what possible prices are available. They're business depends on it. If everyone knew there were a dozen open seats in first class and 50 in coach on the flight I wanted to take from LA to Boston, they couldn't get away with their pricing scheme.