Power-Programmierung/CD1.mdf/lisp/interpre/apteryx/tutor2.lsp

Lisp/Scheme | 1993-12-09 | 18KB | 462 lines

; Copyright 1993 Apteryx Lisp Ltd

; The following is a file of some expressions/programs. Remember to
; use F4 (Lisp:Eval) to see what the expressions evaluate to.


; Here is a program that adds up the numbers from 1 to 10. It works because
; + is a function that takes any number of arguments, and adds them all up.

(+ 1 2 3 4 5 6 7 8 9 10)

; Here is another program that does the same calculation.

(let ( (i 1) (total 0))
  (while (<= i 10)
    (setq total (+ total i))
    (setq i (+ i 1)) )
  total)

; Roughly, it does the following - it makes a variable called "i" and gives
; it the value 1, and makes a variable total and gives it the value 0. The
; general idea is that the variable "i" is going to take on each value from
; 1 to 10 in turn and each of those values will get added to the value of
; the variable "total", so that the final value of "total" will be the sum
; of the numbers from 1 to 10.

; The variables i and total are created by the "let" statement.
; You can think of a variable as a place where you can put one item of
; data, which is accessed via the name of the variable. The first
; argument of the let is a list of variable definitions, i.e.
;    ( (i 1) (total 0) ). Each variable definition is a list of two
; elements. The first is the name of the variable, the second is an
; expression that is evaluated to give the initial value of the variable.
; For example the variable i takes on the initial value 1.
; The variables can be referred to in the expressions that follow the
; variable definitions and make up the rest of the let statement.
; They cannot be referred to outside the let statement. This normally
; means that they effectively cease to exist once evaluation of the let
; statement has completed.

; The variables can be referred to in two ways. If they are evaluated as
; an expression, the return value is their current value. We can use setq
; (or setf) to change their value. setq takes two arguments - the name of
; the variable (which is not evaluated) and an expression for the new
; value (which is evaluated). Here's an example-

(let ( (a 2) (b 3))
  (setq a (+ b 1))
  (setq b (+ a 1))
  (* a b) )

; What happens ?
; First, a gets set to 2 and b gets set to 3.
; In the first setq, the expression (+ b 1) evaluates to 4 (= 3 + 1),
; and this becomes the new value of a.
; In the second setq, the expression (+ a 1) evaluates to 5 (= 4 + 1),
; and this becomes the new value of b.
; Then the last expression evaluates to 4 * 5 = 20, which then becomes the
; result returned from the whole let expression.


; Here's the second expression again.

(let ( (i 1) (total 0))
  (while (<= i 10)
    (setq total (+ total i))
    (setq i (+ i 1)) )
  total)

; We note that the let contains two expressions after the variable
; definitions - the first is a list starting with while, the second is
; just the expression total. Whatever value the variable total has after
; the while expression has been evaluated will be the return value of the
; whole let expression.

; while is a special form which evaluates a series of expressions
; repeatedly, until something tells it to stop. The thing that tells
; it to stop is the first argument. This is a test expression that is
; evaluated before the start of each repetition. If it evaluates to nil
; (i.e. false) then the while finishes, otherwise the remaining arguments
; to the while are evaluated as expressions in order. Then the test
; expression is evaluated again and so on, until the test expression
; evaluates to false.

; What happens if the test expression never evaluates to nil ? Then the
; while expression will never finish evaluating. This sort of thing is
; called an infinite loop. It is inevitable that sometimes you will
; evaluate an expression that takes either forever or a very long time
; to evaluate, so you'll want to know how you can abort such an evaluation
; prematurely. The key for this is the F12 key (there is no menu choice
; because the menus cannot operate while an expression is being
; evaluated).

(while t (print "This program will go on forever until you hit F12"))

; Try evaluating the above program. The test expression is t (meaning true)
; which always evaluates to t (i.e. not nil), so the while expression
; never stops. The print expression prints its argument to the LispOutput
; window, and because its in the while statement, the string gets
; printed over and over again.
; When you hit F12, you get a dialog box which you OK, and then a stack
; dump appears in the LispOutput window. The stack dump shows what was
; happening at the time the F12 key was hit (there may be a slight
; delay between when the F12 key is hit and when the evaluation stops).

; Now that you known how to stop an infinite loop, we can take another
; look at the while loop in our program.

(let ( (i 1) (total 0))
  (while (<= i 10)
    (setq total (+ total i))
    (setq i (+ i 1)) )
  total)

; You can see that the test expression is (<= i 10) which will return t
; if the value of the variable i is less than or equal to 10. This
; seems reasonable, because we want the values of the variable i to go
; from 1 to 10, and then stop.

; The statement (setq total (+ total i)) causes the value of (+ total i)
; to become the new value of the variable total, i.e. it effectively adds
; the value of i onto the value of total.
; The statement (setq i (+ i 1)) similiarly adds 1 onto the value of i.

; We can add some format statements to the while loop to let us follow the
; course of the expression's evaluation. (Don't worry too much how the
; formats work, just read the output to the LispOutput window.)

(let ( (i 1) (total 0))
  (while (<= i 10)
    (format t "Current total = ~A, current i = ~A~%" total i)
    (setq total (+ total i))
    (format t " New total = ~A~%" total)
    (setq i (+ i 1))
    (format t " New i = ~A~%" i) )
  total)

; The variable i that goes from 1 to 10 is sometimes called a counter
; variable. There exists a Lisp construct that is made especially for
; counting called dotimes.

; The following example prints out hello 5 times -

(dotimes (i 5)
  (princ "hello ") )

; The first argument (i 5) consists of the variable i which does the
; counting, and the expression 5 which is the number of times that the
; statements in the dotimes are to be evaluated.

; If we evaluate the following expression, we can see that the counter
; variable actually starts at 0 and its last value is 1 less than the
; number of times the dotimes loops around.

(dotimes (i 10)
  (print i) )

; With this in mind, we can use dotimes to write a program that adds the
; numbers from 1 to 10

(let ( (total 0) )
  (dotimes (i 10)
    (setq total (+ total i 1)) )
  total)

; The extra 1 in (+ total i 1) makes up for the fact that i goes from 0
; to 9.

; Numbers like 55=1+2+3+4+5+6+7+8+9+10 are sometimes called triangular
; numbers. The following program shows why -

(dotimes (i 10)
  (dotimes (j (+ i 1))
    (princ "#") )
  (terpri) )

; Note that the number of times the innermost dotimes goes around is
; equal to 1 + the current value of the counter for the outermost
; dotimes.

; We can see that the 55 hashes that appear in the LispOutput window
; form a triangle.

; We might like to write a function called triangle that given a number
; returns the sum of the natural numbers from 1 to that number.

; For example -

(triangle 10)

; would return the value 10.
; If you tried evaluating the above expression, you would have got an
; error, because there isn't any function called triangle.

; But we can define one using defun -

(defun triangle (n)
  (let ( (total 0) )
    (dotimes (i n)
      (setq total (+ total i 1)) )
    total) )

; The first argument to defun is the name of the new function.
; The second argument is a list of names for the arguments that the
;  new function will take (for triangle there's just one argument
; which we are calling n).
; The rest is a series of expressions which will be evaluated when the
; function is used (or "called"), the last of which will give the return
; value for the function.

; In this case the last expression is the only one, and looks very similiar
; to our program for adding the numbers from 1 to 10. The only difference
; is that we've put n where we previously had 10. When a function is called
; variables are created with the names specified for the arguments in the
; defun, whose values are the actual values of the arguments passed to the
; function. For example, evaluate the defun above, and then the following
; expression -

(triangle 10)

; What happened was that a variable was created whose name was n and whose
; value was 10, so that when the expression

; (let ( (total 0) )
;    (dotimes (i n)
;      (setq total (+ total i 1)) )
;    total)

was evaluated, it gave the required result.

; Here's another program for calculating triangular numbers, with an
; example to try -

(defun triangle2 (n)
  (if (= n 0)
    0
    (+ (triangle2 (- n 1)) n) ) )

(triangle2 10)

; It seems a bit strange, because the body to the function contains a
; call to the function being defined.

; What the definition says in English is -

; (triangle 0) = 0 and for any other number
; (triangle n) = (triangle n-1) + n

; e.g. (triangle 10) = (triangle 9) + 10.

; The definition seems quite reasonable, and Apteryx Lisp doesn't seem
; to have any trouble evaluating it. To see how it does it, we can
; put in a few format statements -

(defun triangle2 (n)
  (format t "Starting to calculate (triangle ~A)~%" n)
  (let ( (result (if (= n 0)
                   0
                   (+ (triangle2 (- n 1)) n) )) )
    (format t " (triangle ~A) = ~A~%" n result)
    result) )

(triangle2 10)

; In order to calculate (triangle 10) it has to calculate (triangle 9)
; which requires it to calculate (triangle 8) and so on.
; We can see that we need to have at least one special case where the
; function doesn't call itself - otherwise we'd get into another
; infinite loop.
; We can also see that at the moment it's calculating (triangle 0) it's
; in the middle of calculating (triangle 1) and (triangle 2) and so on
; right up to (triangle 10). How can the variable n (and result) take on
; eleven different values at once ? The answer is that there are actually
; eleven different variables called n, one for each call (or invocation)
; of triangle2. The value of each variable n has the value passed as an
; argument to the invocation of triangle2 that created it, and each
; variable n is only referred to by the invocation that created it,
; so no confusion results between different n's.

; This business of a function calling itself is called recursion.
; Using a looping construct like while or dotimes is called iteration.
; Recursion is less efficient than iteration if there is a straightforward
; iteration that will do the same job, but for many complex tasks
; recursion is the simplest and most natural technique to use.

; Note the use of "if" in the above program.

; Here are some examples using if -

(if (< 2 3) (+ 2 2) (+ 3 3))
(if (> 2 3) (+ 2 2) (+ 3 3))

; if takes two or three arguments. The first is a test expression, which
; is evaluated. The result of this evaluation is used to decide which of
; the remaining two arguments is to be evaluated. If the test expression
; evaluates to nil (which means false) then the third expression is
; evaluated (or if there is no third expression then the value nil is
; returned). If it evaluates to anything else (which means true), then
; the second expression is evaluated.


; Here's a simple example that uses recursion. Lisp always requires
; arithmetic operators like +, *, / and - to appear before their
; arguments, because they are the names of functions, and that is where
; function names have to be. Putting the operator first is called "prefix"
; notation.

; But we're more used to writing expressions with these operators in
; between their arguments. This is called infix notation. Let's write a
; lisp function that evaluates expressions containing infix operators.

(setq infix-operators '(+ * - /))

(defun eval-infix (expr)
  (eval (infix-to-prefix expr)) )

(defun infix-to-prefix (expr)
  (if (and
        (listp expr)
        (= (length expr) 3)
        (member (second expr) infix-operators) )
    (list (infix-to-prefix (second expr))
      (first expr) (infix-to-prefix (third expr)))
    expr) )

(infix-to-prefix '(2 + (3 * 4)))

(eval-infix '(2 + (3 * 4)))

; (Note the use of the quote ' to prevent evaluation of the arguments
;  in the examples.)

; The function that does all the work is infix-to-prefix.
; If its input expression is a three element list where the
; second member is a member of the list of infix operators,
; then the returned value is the list constructed by putting
; the operator first followed by the other two members of the
; input expression. The tricky thing is that these two members
; may themselves be expressions that have infix operators that
; need changing to prefix, so first we have to call the function
; infix-to-prefix on those members.

; Any other expression is returned as is. The above function doesn't
; work properly on expressions that mix prefix and infix operators,
; where the arguments to prefix operators need fixing.

; An improved solution uses mapcar to apply infix-to-prefix to the
; list of arguments of a function call.

(defun infix-to-prefix (expr)
  (if (consp expr)
    (if (and (= (length expr) 3)
          (member (second expr) infix-operators) )
      (list (second expr)
        (infix-to-prefix (first expr))
        (infix-to-prefix (third expr)) )
      (mapcar #'infix-to-prefix expr) )
    expr) )

(infix-to-prefix '(triangle (1 + ((7 - 4) * (triangle 2)))))

(eval-infix '(triangle (1 + ((7 - 4) * (triangle 2)))))

; Note the use of mapcar. mapcar takes two arguments - a function, and
; a list. The function is applied to each member of the list in turn,
; and the results are made up into a list which is then the return value
; of mapcar. Here's an example using our function triangle -

(mapcar #'triangle '(2 10 5))

; #' is used to convert the name triangle into the function that
; the name triangle refers to. Lisp maintains a distinction between
; names (normally called symbols) and the functions that names
; refer to.

; We can make un-named functions using #' and lambda (having to use
; two items of notation to achieve one thing seems a bit redundant,
; and is required partly for historical reasons).

; The syntax for lambda is similiar to that for defun, but the symbol
; lambda replaces both defun and the function name. When #' is applied
; on the front, then what is returned is the same as the function that
; would be created by the corresponding defun.

; For example -

(defun square (x) (* x x))

(mapcar #'square '(1 2 3 4 5))

; or using lambda to get the same effect -

(mapcar #'(lambda (x) (* x x)) '(1 2 3 4 5))

; The word lambda is the name of a greek letter which was used to
; represent definition of a function in the mathematical theory of
; lambda calculus.

; We can use Lisp to study lambda calculus, but first we need to
; learn about funcall. funcall is a function that applies a function to
; some arguments.

; Here's an example

(funcall #'+ 3 4)

; #'+ evaluates to the function named by +. funcall calls that function
; which the remaining arguments to funcall being the arguments to the
; function.

; Here's the normal way of defining and using a function in Lisp -

(defun cube (x) (* x x x))

(cube 10)

; Here's doing it by creating the actual function object and then
; assigning it as the value of a variable -

(setq cube #'(lambda (x) (* x x x)))

(funcall cube 10)

; We can use lambda to define functions that create new functions. For
; example, here's a function that given a number creates a function that
; adds that number to its input argument

(defun adder (x)
  #'(lambda (y) (+ x y)) )

(funcall (adder 3) 4)

; The "scope" of x in the definition of adder, i.e. where it can be
; referred to, includes the lambda expression, and the function value
; of the lambda expression is what is returned as the result of adder.

; When (adder 3) was executed, a binding occurred between the name x and
; a variable which was created and given the value 3. This binding is
; visible from within the lambda expression. It follows then that the
; variable x created when (adder 3) was executed must remain in existence
; even after adder has finished executing, so that the invocation of
; the result of (adder 3) with the argument 4 returns the right result.

; Here is a function which given two functions returns the function that
; is the composition of two functions, i.e. to apply the composition of
; functions f and g to an argument x, pass x to f and pass the output of
; f to g, returning the output from g as the final result.

(defun compose (f g)
  #'(lambda (x) (funcall g (funcall f x))) )

(defun plus5 (x) (+ x 5))

(defun times10 (x) (* x 10))

(setq h (compose #'times10 #'plus5))

(funcall h 3)

; i.e (3 * 10) + 5