Copyright 1984 by Gary M. Rader					   May 15, 1984
ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ»
º		      Converting Infix to Prefix Notation		      º
º									      º
º				      by				      º
º									      º
º				 Gary M. Rader				      º
ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ


ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
³ Introduction			   ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ

	       Suppose we are designing	a spreadsheet or calculator in
	  which	the user can enter expressions like


		    (A3	+ A4 - 2 * A10)

	  or

		    (365 + (4777 - 1330) * 12)


	       Such  expressions  are  in  "infix"  form  because  the
	  operators are	positioned between their operands rather  than
	  positioned before ("prefix"), or after ("postfix") them.

ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
³ LISP uses Prefix Form		   ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ

	       LISP can	only  directly evaluate	expressions  in	prefix
	  form,	where the operator is positioned before	its  operands.
	  For example, instead of (10 +	20), LISP requires (+ 10  20).
	  In  order  for  LISP	programs  to evaluate expressions like
	  those	 above,	 the  expressions  must	 first be converted to
	  prefix notation so they look like


		    (- (+ A3 A4) (* 2 A10))

	  and

		    (+ 365 (* (- 4777 1330) 12))


	  respectively.



	       Notice  that  infix  notation  is  basically limited to
	  binary operators - operations	 which take two	operands  like
	  +, -,	 *, /,	MOD, >,	 =, <,	~ (boolean  "not"), & (boolean
	  "and"), and  | (boolean  "or").  Operations  requiring, say,
	  three	operands, like the present value function, cannot  use
	  infix	 notation.   Thus  it  appears	in  many  spreadsheets
	  looking something like


		    @PV(Payment, Interest Rate,	Term)


	  which	is  a form  of prefix  notation.  Life	would be  much
	  easier for both humans and computers if we all forgot	 about
	  infix	notation.  Unfortunately,  the use of  infix notation,
	  for the operators listed above, has become too deeply	rooted
	  in  our  culture  to	easily	change.	  We continue to use a
	  hybrid  of  infix  and  prefix  notation  in	much  of   our
	  mathematics.

ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
³ "InfixToPrefix"  Program         ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ

	       The program "IToP" (standing for "InfixToPrefix") takes
	  a single argument, in	infix form, and	converts it to	prefix
	  form.	 (IToP resides in  the program file accompanying  this
	  article.  It is written  in muLISP-83.)  This	output	prefix
	  form will be in the form of a	list.

	       For instance,


		    (IToP '(10 - 9 * 8))


	  returns the list


	       (DIFFERENCE 10 (TIMES 9 8))


	  as  its   result.   (DIFFERENCE   is	the   LISP  name   for
	  subtraction.	TIMES is the LISP name for multiplication.)

	       You will	notice that  a number of associated  functions
	  are also defined in that file.  The function "IToPHelp" is a
	  help function	 for IToP.   "GetOperands" is  a help function
	  for IToPHelp.	 The conversion	program	 is set	up so you  can
	  define  new  operators  without  fussing  with  any function
	  definitions.	Two  operator-defining functions  are defined,
	  one for infix	operators  ("DefInfixOp"), and one for  prefix
	  operators ("DefPrefixOp").

	       DefInfixOp has the form


		    (DefInfixOp	<symbol> <LISP function> <precedence>)

	  where


	       <symbol>	is the symbol for the operator

	       <LISP function> is the muLISP function associated with the
	       operator


	  and

	       <precedence> is the operator's precedence.



	       (Precedence is what makes "(1 * 2 + 3)" equal "((1 * 2)
	  + 3)" rather than "(1 * (2  + 3))".  In this case "+" has  a
	  higher precedence than "*".)

	       For  example,  to  define  binary  "+"  as  the  muLISP
	  function PLUS	with a precedence of 3,	type


		    (DefInfixOp	'+ 'PLUS 3)


	       DefPrefixOp has the form


	  (DefPrefixOp <symbol>	<LISP function>	<arity>	<minimum arity>)


	  where	the first two input  parameters	are as before and  the
	  last two deal	 with the number  of operands.	If  <arity> is
	  specified, then  the function	 is required  to have  exactly
	  that	many  operands.	  If  <arity>  is  not	specified, the
	  minimum number of operands allowable in the function must be
	  specified.  All  prefix operators  have a  precedence	of  1,
	  automatically.


	       To define unary "-", we type


		    (DefPrefixOp '- 'MINUS 1)


	       To define  the function	SUM, which  takes two  or more
	  operands and returns their sum, we type


		    (DefPrefixOp 'SUM 'PLUS NIL 2)


	       Note that the LISP function in these definitions	can be
	  a user-defined function.

	       Using  the  operator  definitions  in the corresponding
	  program file,	the following conversions occur	(the input  is
	  not indented,	the result is):


	       (10 - 9)

		   (DIFFERENCE 10 9)


	       (10 - - 9)

		   (DIFFERENCE 10 (MINUS 9))


	       (10 + 9 * 8 - - A > 3 / B)

		   (GREATERP (DIFFERENCE (PLUS 10 (TIMES 9 8)) (MINUS A))
		     (QUOTIENT 3 B))


	       (5 + (SUM A (3 *	(B MOD 2)) 365)	= (C * (747 + D)))

		   (EQUAL (PLUS	5 (PLUS	A (TIMES 3 (REMAINDER B	2)) 365))
		     (TIMES C (PLUS 747	D)))


	       Some  error  checking  is  performed  in	 the  program.
	  However,  it	 is  not   exhaustive.	 When	an  error   is
	  encountered,	 the   speaker	 beeps	 and   the  conversion
	  terminates.	This  action  can  be  altered by changing the
	  "(PRIN1  (ASCII  7))"  parts  of  all  "(THROW  'Error ...)"
	  statements to	the desired action.

	       Finally,	 the  following	  code	evaluates  any	 infix
	  expression "Exp."


		    (EVAL (IToP	Exp))

	  e.g.,

		    (EVAL (IToP	'(10 + 9)))

			 19


	  or

		    (SETQ Exp '(10 + 9 * 8 - - 7))
		    (EVAL (IToP	Exp))

			 89


	       In  conclusion,	IToP  is  a  muLISP-83	function which
	  converts  infix  arithmetic  expressions  into  prefix  form
	  suitable for evaluation by  muLISP's EVAL function.  Such  a
	  function  is	useful	 in  both  spreadsheet	 programs  and
	  calculator  programs	where  the  user enters	expressions or
	  formulas in infix notation.  New infix and prefix  operators
	  can be defined using DefInfixOp and DefPrefixOp.

ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
³ LISP News			   ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ

	       LISP/88	which  was  mentioned  in  last	 issue's  LISP
	  article seems	to work	relatively well.  At $49.95 it is  the
	  cheapest implementation of LISP available for	the IBM-PC.  I
	  recommend it for  those wanting to  learn LISP, but  not for
	  serious LISP software	development.

	       Several new LISPs are about.  The LISP Company has  TLC
	  LISP while Gold Hill Computers announced Golden Common  LISP
	  (GCLISP).  A review of muLISP, IQLISP, and TLC LISP  appears
	  in   the   April,   1984,   issue   of   PC	Tech  Journal.
	  Unfortunately,  muLISP-82  was  used,	 instead of muLISP-83,
	  making  the  review  fairly  worthless for determining which
	  LISP	is  most   suitable  for  a   particular  application.
	  However, it does give	 a good	indication of  the differences
	  between IQLISP and TLC LISP.

	       An excellent new	book  for learning LISP	is  available:
	  "LISP:  A  Gentle  Introduction  to Symbolic Computation" by
	  David	S. Touretzky, Harper & Row, 1984, $18.95.


   ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
   ³			LISPs Mentioned	in This	Article			    ³
   ÃÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´
   ³  Golden Common LISP (GCLISP)	 ³  IQLISP			    ³
   ³  $375				 ³  $175			    ³
   ³  Gold Hill	Computers		 ³  Integral Quality		    ³
   ³  163 Harvard St.			 ³  P.O. Box 31970		    ³
   ³  Cambridge, MA 02139		 ³  Seattle, WA	98103-0070	    ³
   ³  (617)492-2071			 ³  (206)527-2918		    ³
   ÃÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´
   ³  LISP/88				 ³  muLISP-83			    ³
   ³  $49.95				 ³  $250			    ³
   ³  Norell Data Systems		 ³  The	Soft Warehouse		    ³
   ³  3400 Wilshire Blvd.		 ³  P.O. Box 11174		    ³
   ³  P.O. Box 70127			 ³  Honolulu, Hawaii 96828-0174	    ³
   ³  Los Angeles, CA 90010		 ³  (808)734-5801		    ³
   ³  (213)257-2026			 ³				    ³
   ÃÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´
   ³  TLC LISP				 ³				    ³
   ³  Price Unavailable			 ³				    ³
   ³  The LISP Company			 ³				    ³
   ³  330 C Village Lane		 ³				    ³
   ³  Los Gatos, CA 95030		 ³				    ³
   ³  (408)354-3668			 ³				    ³
   ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÁÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ




		     ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
		     ³ File Name:  ÛÛ	lisp1.txt   ÛÛ	³
		     ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ