Checkout our contents page for back issues of 'the works' and 'The Lisp Reader'.
Comments to web@harlequin.com
Inside this issue:
Welcome to the second issue of The Works newsletter. We are excited to bring you news from Harlequin, with customer stories, columns and competitions.
In this issue you will find the latest column from our own industry expert Peter Norvig. Try to solve the two programming brainteasers and you may win a copy of his acclaimed book on artificial intelligence.
Don't worry if you don't manage to solve the brainteasers, you still have a chance to win either a copy of Peter Norvig's book or Dylan Programming: An Object-Oriented and Dynamic Language by Neal Feinberg, Sonya E. Keene, Robert O. Matthews, and P. Tucker Withington when you complete our on-line survey.
Learn how the foundations of 21st century space exploration are being developed today with Harlequin's Lisp technology in "LispWorks Helps to Probe the Secrets of the Galaxy".
There's also information on what Harlequin will be demonstrating at the upcoming AAAI-96 and Object World West conferences and where to find us.
Armadas of tiny unmanned spacecraft fan out from Earth in precisely controlled formations to study Earth, the Moon and Sun, traverse the farthest reaches of our solar system, and beyond. No, this is not a lost episode of "Star Trek The Next Generation," but rather a carefully laid plan for space exploration in the 21st century. And, the key to ensuring the accurate control of these unmanned micro-spacecrafts is Harlequin's LispWorks®
The United States National Aeronautics and Space Administration (NASA) is working toward a 21st century plan, the New Millenium Program (NMP), which includes affordable, frequently-launched missions to carry out very specific scientific inquiries. The Jet Propulsion Laboratory (JPL) in Pasadena CA, mandated to manage the NMP, is currently developing the technological underpinnings that will enable these aggressive space programs.
Early NMP spacecraft are expected to weigh about 45 lbs. The goal is to eventually develop microspacecraft that will weigh as little as 2 lbs, a "spacecraft on a chip" that is essentially a package of dime-sized micro-instrumentation wrapped in a "gossamer" architecture.
Extremely high levels of autonomy will allow for extraordinary navigational precision. Harlequin's LispWorks was the technology selected to build the Remote Agent software that will allow these incredible spacecraft to operate autonomously without guidance from the ground.
Two crucial components of the Remote Agent being built with LispWorks are the "Mode Identification and Recovery system" (MIR) and the "Smart Executive." MIR is a model-based diagnosis engine that monitors information coming from the spacecraft's sensors. When it receives an indication that something has gone wrong through an anomalous reading from the sensors, the software tries to determine what has happened and solve the problem if one exists.
The Smart Executive is based on a system called ESL, a set of very sophisticated control constructs, implemented on top of LispWorks, that correspond to the kinds of concepts that humans use when giving one another instructions. Both systems are critical to the success of the planned space missions.
According to Erann Gat, a member of the Technical Staff, "We feel that the right way to program is to build computational abstractions and Lisp is the best language for doing this because of its meta-linguistic features. In particular, the fact that there is a very close correspondence between the surface syntax and parse tree makes it possible to design the very sophisticated macros required to build the Remote Agent."
It was decided to build the application in Lisp, but JPL needed a compiler for the RAD 6000 running Wind River Systems' VxWorks&174; OS. "Harlequin became the obvious choice for us," said Abdullah Aljabri, DS1 Autonomy/Flight Software Project Element Manager.
"Harlequin's experience and expertise in porting applications was critical to completing this part of the project in such a short period of time. Their responsiveness and technical savvy has been outstanding."
The Remote Agent system is being developed by JPL in conjunction with the Ames Research Center and is scheduled to debut on the first New Millenium test mission in June of 1998.
Q. Can I trace generic-functions and methods?
A. You can trace a generic-function in exactly the same way as any other function. Tracing of methods is also possible but differs between the two lisps.
In LispWorks use the TRACE macro:
(TRACE ((METHOD . ) &REST; OPTIONS))
where spec ::= [qualifier]* (specializer*)
Eg: (TRACE ((METHOD FOO :AFTER (CONS)) :BREAK T))
In Lucid Common Lisp use the function TRACE-METHOD:
(TRACE-METHOD &OPTIONAL; OPTIONS)
Eg: (TRACE-METHOD '(FOO :AFTER (CONS)) '(:BREAK T))
Q. What is a "MOP" and what would I do with one?
A. MOP stands for Meta-Object Protocol. This provides the classes and generic functions that drive the (ANSI) standardized interface to CLOS, controlling everything from instance creation to slot look-up and method dispatch, all from the inside.
Knowledge of the MOP allows you to completely redesign your object system, if thatÕs your fancy...
But a much more common use is probably introspection, as the internals of standardized :meta-classes" (such as STANDARD-CLASS and STANDARD-GENERIC-FUNCTION) are opened up by a range of obvious accessors, for example: CLASS-NAME, GENERIC-FUNCTION-METHODS, METHOD-GENERIC-FUNCTION and METHOD-FUNCTION, to name but a few.
One warning though: the CLOS MOP has not been finalized and an official version has never been published. The closest approximation is AMOP* and this is very close to the MOPs of both our lisps, though not identical to either in all its details. If you're not sure about an apparent difference, please feel free to contact Harlequin support.
*For general insight into MOPs see "The Art of the Metaobject Protocol" (or "AMOP" for short) by Kiczales, Rivieres and Bobrow (MIT Press, 1991).
Q. When do I need to validate a superclass?
A. Every time you define a new class, its superclass(es) will be validated by the MOP, by the call:
(VALIDATE-SUPERCLASS CLASS SUPERCLASS) which must return T. The primary method on this generic-function will take care of almost every situation for you, and the only circumstance you need to be aware of is when a class and superclass are themselves instances of different classes (i.e. they have different metaclasses). In this case you should add a method to VALIDATE-SUPERCLASS.
If there are any questions you would like answered in our Dear Obbie column, please submit them to us by e-mail at dear-obbie@harlequin.com
Committed to bringing only the best software to market, Harlequin will even use alchemy in its quest to develop applications that meet the needs of the development community.
After many months of hard work, and in preparation for the upcoming 5.0 release, Harlequin is proud to announce that they have managed to turn Lucid to Liquid . . .
Harlequin has announced the renaming of the popular Lucid Common Lisp(TM) development environment to Liquid Common Lisp.(TM) Since the acquisition of Lucid Common Lisp from Lucid, Inc. in 1994, Harlequin has continued the development and support of the product, working to preserve the essence of the Lucid development environment while adding new features.
With the renaming of Lucid Common Lisp, Harlequin brings the Liquid Common Lisp application fully into the Harlequin family of dynamic object-oriented systems, preparing the way for the upcoming release of an exciting redesign of the product later this year.
Dylan(TM) Programming: An Object-Oriented and Dynamic Language by Neal Feinberg, Sonya E. Keene, Robert O. Matthews, and P. Tucker Withington.
Harlequin is proud to have some of the world's best software engineers, but did you know that many of us are also very well-published, especially in the areas of object- oriented and dynamic languages?
The latest addition to the publications authored by Harlequinites is Dylan Programming: An Object-Oriented and Dynamic Language by Neal Feinberg, Sonya E. Keene, Robert O. Matthews, and P. Tucker Withington.
Dylan is a language that makes your programming time both productive and enjoyable by combining the best qualities of object-oriented, procedural, dynamic, and static languages, while avoiding many of the drawbacks.
The goal of the book is to introduce programmers to those features of Dylan that allow for 1) rapid development as well as 2) the deploy-ment of applications and components on a wide range of machines and operating systems.
Dylan Programming is available in bookstores everywhere, as well as at many trade shows. Copies may also be purchased directly from the publisher, Addison Wesley Longman, at 1-800-238-9682.
Fill out Harlequin's on-line survey at: http://www.harlequin.com/full/products/sp/ooquest.html for a chance to win a copy of the book.
And don't forget to stop by booth #925 at Object World West for a preview of Harlequin's implementation of the Dylan(TM) programming environment and native compiler currently under development.
Fill out a copy of our on-line survey and you'll be entered in a drawing to win a copy of either Peter Norvig's Artificial Intelligence: A Modern Approach, or Dylan Programming: An Object-Oriented and Dynamic Language by Neal Feinberg, Sonya E. Keene, Robert O. Matthews, and P. Tucker Withington (all members of the Harlequin engineering team!).
We have developed this survey to get your opinion on a host of technology-related subjects. The results will help us to gauge the interests and needs of the development community we serve, and bring you the software that best meets your needs.
Of course, you'll agree that the prospect of winning a book is also a good incentive!
Stop me if you've heard this story about the great mathematician Srinisava Ramanujan before.
"...I remember once going to see him when he was lying ill at Putney. I had ridden in taxi cab number 1729 and remarked that the number seemed to me rather a dull one, and that I hoped it was not an unfavorable omen. 'No,' he replied, 'it is a very interesting number; it is the smallest number expressible as the sum of two cubes in two different ways.' "
- G. H. Hardy, Ramanujan,
London: Cambridge University Press, 1940.
So now you know that Ramanujan was great at math trivia, but what does that have to do with the dreaded job interview? Well, when a friend of mine went to an interview at Microsoft, they asked him to write a solution to the following programming question on the blackboard: Given an integer n, print a list of all the Ramanujan numbers (sum of two cubes in two different ways) up to n.
My friend told Microsoft that such games were a waste of his time. But assuming you don't have that kind of chutzpah, what program would you write, and how would you justify it? You can assume n won't exceed a billion, and that you have a machine with 32Mb of RAM. You shouldn't need more than about a dozen lines of code.
Another friend was asked a harder question at an interview: Given a string of any length n, efficiently find the longest substring that is a palindrome.
For example, given "hello world," the longest palindrome substring is "ll". It's easy to come up with a solution that is n O(n3) in the worst case and O(n2) in the average case; the trick is to come up with a faster algorithm. If you can do it in less than fifteen minutes, give me a call - maybe we have a job for you.
Last issue's puzzle asked for a proper implementation of LET-STATIC that binds static variables (that is, variables that are initialized once when the function containing them is created, and maintain their values between calls to the function). We gave two test cases in the last issue; here is a third:
(defun test3 (x) (let-static ((calls 0) (best x)) ...))
You can imagine that CALLS counts the number of calls to the function, for profiling purposes, and BEST accumlates the best value of X seen so far. When defining macros it is usually best to first imagine what you want your code to expand into. Here is a possible expansion for TEST3:
(let ((calls *uninitialized*)
(best *uninitialized*))
(defun test3 (x)
(psetq calls (if (eq calls *uninitialized*)
0 calls)
best (if (eq best *uninitailized*)
x best))
...))
Note that the lexical variables CALLS and BEST are bound outside the definition of TEST3, while they are given their initial value inside; this is the main purpose of LET-STATIC.
The trick is to notice that this means we need a new definition of DEFUN, in addition to a definition for LET-STATIC. (Other solutions dealing with special variables rather than lexical, or with gensymed variable names are subject to problems. For example, Common Lisp leaves unspecified exactly when a macro will be expanded, so any approach that relies on having macros in interpreted code being expanded exactly once will not be portable.) Here is the definition of LET-STATIC and the new definition of DEFUN:
(defmacro let-static (bindings &rest; body)
`(progn (psetq ,@(mapcan #'static-initializer
bindings))
,@body))
(defmacro new:defun (name parameters &rest; body)
`(let ,(extract-static-vars body)
(defun ,name ,parameters ,@body)))
Here are the auxiliary routines to support the above:
(defconstant *uninitialized* ÒUnInitializedÓ)
(defun binding-var (binding)
(if (atom binding) binding (first binding)))
(defun binding-val (binding)
(if (atom binding) nil (second binding)))
(defun static-initializer (b)
(list (binding-var b)
`(if (eq ,(binding-var b) *uninitialized*)
,(binding-val b) ,(binding-var b))))
(defun extract-static-vars (body)
(cond ((atom body) nil)
((eq (first body) 'let-static)
(nconc (mapcar #'binding-var (second body))
(extract-static-vars (nthcdr 2 body))))
(t (nconc (extract-static-vars (car body))
(extract-static-vars (cdr body))))))
To be complete, we'll also need new definitions for all the other macros that create functions: DEFMETHOD, FLET, LABELS, FUNCTION, and the #' read macro. These can follow the model of NEW:DEFUN. To make using them more transparent, we can define NEW as a package that uses the Common Lisp User package, and shadows DEFUN and the other relevant symbols:
(defpackage :new (:use :cl-user) (:export :defun :defmethod :flet :labels :function :lambda) (:shadow :defun :defmethod :flet :labels :function :lambda))
What's the moral of this puzzle? There are several: (1) Lexical variables in Common Lisp provide a powerful mechanism, even more powerful than static variables in other languages. (2) It is sometimes convenient to separate the scope of a variable from its initialization. LET-STATIC does just that. (3) While it is not portable in Common Lisp to change the definition of a built-in symbol like DEFUN, it is possible to use a new package and shadow the definition. (4) It is debatable whether the convenience of LET-STATIC is worth the mechanism required to implement it. Different programmers have different tastes.
There were several partial solutions to last issue's puzzle, but nobody submitted a complete solution, so we'll roll the prize over and offer two prizes this time, one for the best solution to the Ramanujan puzzle, and one for the Palindrome puzzle. And, oh yeah, the friend that interviewed at Microsoft now works at JavaSoft!
The works continues . . .
(C) The Harlequin Group Limited. LispWorks is a registered trademark and KnowledgeWorks, Transducer, DataWorks/LS, WebMaker and Liquid Common Lisp are trademarks of The Harlequin Group Limited. All other brand and product names are trademarks of their respective owners and are used herein in an editorial fashion.
Copyright © 1995-1997 The Harlequin Group Limited. All rights reserved. Last update August 01 1997