perm filename EXER[206,LSP] blob sn#240348
filedate 1976-10-16 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00002 PAGES
C REC PAGE DESCRIPTION
C00002 00002 1. Write down an S-expression A with the property that eval(A,NIL)=A.
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.