perm filename EXER[206,LSP] blob sn#240348 filedate 1976-10-16 generic text, type C, neo UTF8
C00001 00001
C00002 00002	1.  Write down  an S-expression  A with the  property that  eval(A,NIL)=A.
C00006 ENDMK
1.  Write down  an S-expression  A with the  property that  eval(A,NIL)=A.
(Hint: use the function SUBST)

    2.  A real number  generator is a function  f which maps the  integers
into the set of decimal digits 0,1...9, the idea being that f(n)= the  nth
digit after the decimal  point of the real  number "generated" by f.   The
values of  the  function on  non-positive  integers determine  the  digits
before the decimal point in the obvious way.  We restrict our attention to
functions f with the property that only  a finite number of its values  on
non-positive integers are non-zero (no "infinite" numbers allowed!).   For
example the real number generator(λx.if x≤-2 then 0 else 3) generates  the
real number  33.3333....   =  33  1/3.   (Only  positive  numbers  can  be
represented using this  scheme; extension  of the scheme  to the  negative
numbers would be trivial)  You are to write  an addition routine for  real
number generators.  This will  be a functional  PLUS which,given two  real
number generators f and g, returns a real number generator PLUS(f,g) which
generates the sum of the real numbers generated by f and g.  In fact  this
task as stated  is impossible,since  no functional  PLUS which  represents
addition of real numbers can have the property that its output is always a
total function when its inputs are total.  (Why?)  Thus we must relax  our
conditions:  whenever PLUS(f,g) terminates on input n, the value  returned
must be the  nth digit of  the sum of  the numbers generated  by f and  g.
(Note  that  the  function  which  is  undefined  everywhere  meets  these
conditions; however you can  certainly do better than  that.  At the  very
least PLUS should return a total  function when its arguments have only  a
finite number  of non-zero  digits.)   If you  enjoyed writing  plus,  try
writing more pieces of an arithmetic package for real number generators.

    3.  (Hard)  Write  a lisp  expression  f such  that  apply(f,x)=x!  (x
factorial), observing the following restriction:  f must be an  expression
in pure LISP (no PROGs) which does not use the LABEL construct.