TUESDAY  JULY 10,1973		FQ+3D.0H.44M.22S.	- GLS -

			TRY NLISP!

THERE ARE SEVEN NEW FUNCTIONS IN THE LATEST NLISP.
THE FIRST IS A NEW STATUS CALL: (STATUS FEATURES) RETURNS A LIST OF
FEATURES IMPLEMENTED IN THE LISP. THIS FEATURES LIST IS A LIST OF
ATOMIC SYMBOLS WHICH CAN CONVENIENTLY BE MEMQ'ED, PRINTED, OR
WHATEVER. CURRENTLY THESE ATOMS MAY APPEAR ON THE FEATURES LIST:
	BIBOP		;HAIRY PAGING SCHEME (BEING IMPLEMENTED)
	LAP
	SORT		;FUZZY SORT FUNCTIONS (SEE BELOW)
	EDIT
	FASLOAD
	^F		;MOBYIO PACKAGE
	BIGNUM
	ML		;THIS LISP IS ON MATHLAB
	AI		;THIS LISP IS ON AI
	ITS		;THIS LISP IS ON SOME ITS SYSTEM
	DEC10		;THIS LISP IS ON A DECSYSTEM-10 MONITOR
(CAR (LAST (STATUS FEATURES))) IS GENERALLY CONSIDERED TO BE
AN IMPLEMENTATION NAME; THUS IT WILL BE "ITS" OR "DEC10"
(OR MAYBE EVENTUALLY "MULTICS", ON THAT SYSTEM). THIS IS USEFUL
FOR PRINTING HEADINGS OR WHATEVER.
THE MAIN IDEA BEHIND THIS STATUS CALL IS THAT AN APPLICATION
PACKAGE CAN LOAD UP INTO ANY MACLISP IMPLEMENTATION AND DECIDE
WHAT TO DO ON THE BASIS OF THE FEATURES IT FINDS AVAILABLE.

EXAMPLE:

(COND ((MEMQ 'BIGNUM (STATUS FEATURES))
       (PROG2 NIL (EVAL (READ)) (READ)))
      (T (READ) (EVAL (READ))))

(DEFUN FACTORIAL (N)			;BIGNUM VERSION
       (COND ((ZEROP N) 1)
	     ((TIMES N (FACTORIAL (SUB1 N))))))

(DEFUN FACTORIAL (N)			;FIXNUM-ONLY VERSION
       (COND ((> N 13.) (BARF 'FACTORIAL/ TOO/ BIG))
	     ((ZEROP N) 1)
	     ((* N (FACTORIAL (1- N))))))



THREE OF THE NEW FUNCTIONS ARE FOR ARRAY MANIPULATION; THEY
ARE INTENDED TO MAKE ARRAYS SOMEWHAT LESS PAINFUL TO USE. THEY ARE:

********** OBSOLETE 7/30/73 **********
* INITARRAY	SUBR 2 ARGS
* (INITARRAY 'FOO 'GLITCH) INITIALIZES ALL ENTRIES OF THE ARRAY FOO
* TO CONTAIN GLITCH. (THIS IS A STORE-TYPE INITIALIZATION, NOT NSTORE;
* BUT THE KLUDGY 18-BIT NUMBER ARRAYS WILL DISAPPEAR EVENTUALLY ANYWAY.)
* THUS TO ZERO OUT AN ARRAY, SAY (INITARRAY 'FOO NIL).
* THERE! NOW ISN'T THAT NICER THAN SAYING (BLTARRAY 'ZEROARRAY 'FOO)?
* INITARRAY RETURNS ITS SECOND ARGUMENT.
********** OBSOLETE TO HERE **********

FILLARRAY	SUBR 2 ARGS
(FILLARRAY <ARRAY> <LIST>) FILLS THE ARRAY WITH CONSECUTIVE ITEMS
FROM THE LIST; THUS (FILLARRAY 'ZTESCH '(A B C)) IS LIKE
	(PROG NIL (STORE (ZTESCH 0) 'A)
		  (STORE (ZTESCH 1) 'B)
		  (STORE (ZTESCH 2) 'C)
		  (RETURN 'ZTESCH))
IF THE ARRAY IS TOO SHORT TO CONTAIN ALL OF THE  ITEMS
IN THE LIST, THE EXTRA ITEMS ARE IGNORED. IF THE LIST IS TOO
SHORT TO COMPLETELY FILL THE ARRAY, THE EXTRA ARRAY SLOTS ARE 
FILLED WITH THE LAST ITEM FROM THE LIST.  FILLARRAY RETURNS ITS 
FIRST ARGUMENT AS VALUE.

LISTARRAY	SUBR 1 ARG
(LISTARRAY 'SNARK) CONSES UP ALL ITEMS IN THE S-EXPRESSION ARRAY 
SNARK, IN ORDER, AND RETURNS THEM AS A LIST. THUS:
	(ARRAY QUUX T 10)
	(FILLARRAY 'QUUX '(A B C D E))
	(LISTARRAY 'QUUX)
RETURNS (A B C D E E E E).



THE OTHER THREE FUNCTIONS COMPRISE THE NEW SORTING PACKAGE.
FOR ARRAYS, THEY USE THE QUICKSORT METHOD DESCRIBED IN
KNUTH (VOL 3, P. 114 FF.) THIS METHOD GIVES THE SORT FUNCTIONS
THE FOLLOWING PROPERTIES:
[1] THE SORT IS GUARANTEED TO TERMINATE, NO MATTER WHAT PREDICATE
    IS USED FOR SORTING (SEE BELOW.) THAT IS, GIVING SORT THE
    WRONG FUNCTION WON'T CAUSE IT TO HANG OR LOOP.
[2] THE SORT IS **NOT** STABLE. EQUAL KEYS WILL NOT STAY IN THEIR
    ORIGINAL ORDER; IN FACT, EQUAL KEYS WILL BE ORDERED RANDOMLY
    (SINCE THE ALGORITHM USES A RANDOM NUMBER GENERATOR TO FEND
    OFF CERTAIN WORST CASES.)
[3] THE SORT IS, ON THE AVERAGE, ON THE ORDER OF N LOG N IN SPEED.
    PRELIMINARY TIMING TESTS SHOW THAT 2500. ATOMIC SYMBOLS
    WERE SORTED ALPHABETICALLY IN 10. SECONDS OR RUNTIME, AND
    10000. ATOMS IN 40. SECONDS OF RUNTIME.
FOR LISTS, THE METHOD USED IS THE MERGE SORT [KNUTH, VOL. 3, PP. X]
THE ARGUMENT LIST IS REARRANGED WITH RPLACD, AND A SORTED LIST IS 
RETURNED;  THUS TO SORT A LIST CURRENTLY THE VALUE OF THE VARIABLE L,
AND MAKE THE SORTED LIST THE NEW VALUE OF L, DO 
		(SETQ L (SORT L 'PRED))


THE FUNCTIONS ARE INDIVIDUALLY DESCRIBED BELOW:

SORT		SUBR 2 ARGS
THE FIRST ARGUMENT TO SORT IS AN S-EXPRESSION ARRAY OR A LIST, 
THE SECOND A PREDICATE OF TWO ARGUMENTS. THE DOMAIN OF THE PREDICATE
SHOULD INCLUDE ALL THE ITEMS IN THE LIST OR ARRAY TO BE SORTED.
THE PREDICATE SHOULD BE A LISP FUNCTION OF TWO ARGUMENTS WHICH 
DEFINES A WELL-ORDERING OVER ITS DOMAIN,  AND HAS THE SENSE THAT 
THE FIRST ARGUMENT "PRECEEDS" THE SECOND WHEN THE PREDICATE IS TRUE,
AND THE SECOND "PRECEEDS" THE FIRST WHEN FALSE.
NOTE THAT SINCE SORTING REQUIRES MANY COMPARISONS,
AND THUS MANY CALLS TO THE PREDICATE, SORTING WILL BE MUCH FASTER
IF THE PREDICATE IS A COMPILED FUNCTION RATHER THAN INTERPRETED.
SORT, LIKE THE MAP SERIES OF FUNCTIONS, WILL TRY TO ESTABLISH A 
DIRECT MACHINE-INSTRUCTION SUBROUTINE LINK TO THE FUNCTIONAL 
ARGUMENT WHENEVER THAT IS POSSIBLE.

EXAMPLE:

(DEFUN MOSTCAR (X)
       (COND ((ATOM X) X)
	     ((MOSTCAR (CAR X)))))

(SORT FOOARRAY
      (FUNCTION (LAMBDA (X Y)
			(ALPHALESSP (MOSTCAR X) (MOSTCAR Y)))))

IF FOOARRAY CONTAINED THESE ITEMS BEFORE THE SORT:

	(TOKENS (THE LION SLEEPS TONIGHT))
	(CARPENTERS (CLOSE TO YOU))
	((ROLLING STONES) (BROWN SUGAR))
	((BEACH BOYS) (I GET AROUND))
	(BEATLES (I WANT TO HOLD YOUR HAND))

THEN AFTER THE SORT FOOARRAY WOULD CONTAIN:

	((BEACH BOYS) (I GET AROUND))
	(BEATLES (I WANT TO HOLD YOUR HAND))
	(CARPENTERS (CLOSE TO YOU))
	((ROLLING STONES) (BROWN SUGAR))
	(TOKENS (THE LION SLEEPS TONIGHT))


SORTCAR		SUBR 2 ARGS
SORTCAR IS EXACTLY LIKE SORT, BUT THE ITEMS TO BE SORTED SHOULD
ALL BE NON-ATOMIC. SORTCAR TAKES THE CAR OF EACH ITEM BEFORE
HANDING TWO ITEMS TO THE PREDICATE. THUS SORTCAR IS TO SORT
AS MAPCAR IS TO MAPLIST.