Home
Calendar
Homework
Lectures
Syllabus
Resources
People

History

one of the first functional languages - developed 1958
now a family of dialects, Clojure, CommonLisp, newLISP, Scheme, Interlisp, etc.
based on lists, lambda calculus
one of first to support first-class continuations
minimialist philosophy, clean design
Lisp is interpreted (compiled dialects are also available)

Why study Lisp?

different from C, Pascal
has a minimal syntax
based on functions rather than statements
dynamically typed
automatic storage management
dynamically scoped

Notation Used in Notes

Will substitute something for bar

(foo bar)

May substitute more than one thing following foo

(foo bar ...)

Using newLISP

newLISP shell runs the interpreter (REPL - Read, eval, print loop).

Compute the sum of 4 and 5

     > (+ 4 5)
     9

To exit

     (exit)

Lexical Matters

Identifiers

start with a character that cannot begin a number, then any of the following
```
+ - . * / < = > ! ? : $ % _ ~ ^
```
case-sensitive (among Lisp dialects, it is more common to be case insensitive)
; this is a comment

newLISP names and bindings

Create binding in current environment:

  (define name expression)

Simple example:

(define foobar 42)

Expression could be complicated:

(define foobar (+ 40 2))

Note that in general you should *not* redefine a name.

Name dereferencing/evaluation

Give name to dereference (get binding)

> (define foobar 42)
42
> foobar
42
> barfoo ; undefined name is nil, not an error
nil

Names are dynamically typed (type is determined when bound)

> (define foobar 42)
42
> (define foobar "hello there")
"hello there"

Literals

Examples

     42 -99 1.23 4.56e2

Strings

     "hello there!"
     "I said \"hello there\" to you"
     "A backslash is the \\ character"

Booleans

     true
     false
     nil ; false

Function Calls

An expression of the form:

(operator operand ...)

Examples

> (+ 4 5)
9
> (+ (+ 4 5) 9)
18

Parentheses in C

parentheses control precedence
```
  5 * (4 + 6)
```
some infix notation
```
     4 + 6
```
some prefix notation
```
     add(4, 6)
```

Prefix Notation and Parentheses in newLISP

prefix notation only
parentheses delimit expression
```
      (* 5 (+ 4 6))
```

If expressions

general form

(if test true-expression false-expression)

alternate form (false branch returns #f)
```
(if test consequent)
```

examples

    > (if (> 5 4) 42 99)
    42
    > (if (< 5 4) 42 99)
    99
    > (if (> 5 0) 33)
    33

Case expressions

General form

    (case key 
      ((case-values ...) expression) 
        ...
      (else expression)
    )

Examples

    > (define x 6)
    > (case x
        ((2 3 5 7)   (+ x 3))
        ((1 4 6 8 9) (+ x 100)))
    106
    > (case (+ x 2)
        ((3 5 7) 42)
        ((1 4 6) 99)
        (else    33))
    33

Sequencing

General form

(begin expression ...)

Example of a begin expression:

   > (define x 0)
   > (begin (println x) (+ x 1))
   0 ; printed value
   1 ; result of last expression in (begin ...)

Iteration

newLISP for expression is similar to a C for loop.

(for (name init limit  step)
  body-expression ...)

Example

  > (for (i 1 10 2)
              (println i) 
            )
  1 
  3 
  5 
  7 
  9

equivalent C code

  for (i = 1; i <= 10; i += 2)
      printf ("%d\n ", i);

Defining a function

General form of function call

(operator operand ...)

Function definition

(define (variable formal ...) expression ...)

Note, no types for args.

Example

     > (define (add1 arg) (+ arg 1))
     > (add1 4)
     5

Zero argument function

     > (define (foo) (+ 42 99))
     > (foo)
     141

Binary function

     > (define (bar arg1 arg2) (+ arg1 arg2))
     > (bar 42 99)
     141

newLISP is dynamically-scoped and dynamically typed.

     > (define x 1)
     1
     > x
     1
     > (define (foo) (+ x 2))
     (lambda () (+ x 2))
     > (foo)
     3
     > (define x 4)
     4
     > (foo)
     6

Quoting and Symbols

Quote suspends evaluation. Can quote lists.

     > (define a 42)
     > a
     42
     > (quote (1 2 2))
     (1 2 2)
     > '(1 2 2)
     (1 2 2)

A quoted name is called a symbol.

An Aside on Literals

     > (+ 4 5)
     9

Literals are self-evaluating so we don't have to do this:

     > (+ '4 '5)
     9

Flexible conditionals

Conditional expression general form is:

(cond clause1 clause2 ...)

where each clause is of the form:

(test expression ...)

tests evaluated in order till one is true
if true then expression is executed
default is else
```
(else expression ...)
```

An example

     > (cond ((> 3 2) 'greater)
             ((< 3 2) 'less))
     greater
     > (cond ((> 3 3) 'greater)
             ((< 3 3) 'less)
             (else    'equal))
     equal

Binding constructs, let

The general form of let is:

(let ((variable init)
      ...)
  body-expression ...)

init expressions are evaluated in some unspecified order
each variable bound to appropriate value
body-expressions are evaluated
bindings in let hide bindings in outer environments

Example of let

     > (define x 42)
     > (let ((x 99)
             (y 101))
         (+ x y))
     200
     > x
     42

Consider the following sequence of evaluations:

     > (define x 42)
     > (define (addx y) (+ x y))
     > (addx 99)
     141

If we change that value of x then we change how addx behaves:

     > (define x 1)
     > (addx 99)
     100

But a x in a nested environment it has no effect on addx

     > (define x 1)
     > (let ((x 99))
	     (addx 99))
     100
     > x
     1

Anonymous functions and lambda expressions

Mechanism for anonymous functions

General form of a lambda expression

(lambda (formal ...) expression ...)

An example

     > (define (add2 x) (+ x 2))
     > (add2 42)
     44
     > ((lambda (x) (+ x 2)) 42)
     44

Anonymous functions as operands

Anonymous functions can be used as operands to other functions.

     > (define (double proc arg) (* (proc arg) 2))
     > (define (add1 x) (+ x 1))
     > (double add1 4)
     10
     > (double (lambda (x) (+ x 1)) 4)
     10

lambda compared to define

definition of the form:

(define (variable formals) body)

is equivalent to a definition of the form:

(define variable (lambda (formals) body))

Higher-order functions

A higher-order function is a function that takes a function as a parameter, or constructs a function as its result.

   ; the map function applies a function to each value in a list
   (define (map f L) 
      (if (null? L) '()
          (cons (f (first L)) (map f (rest L)))
      )
   )

One might use it as follows.

   (define (square x) (* x x))
   (map square '(1 2 3 4))
   ; returns (1 4 9 16)

A higher-order function might also construct a function.

   (define (make-double f) 
      (lambda (x) (f x x)
   )
   ((make-double *) 3)
   ; returns 9
   ((make-double (make-double *)) 3)
   ; returns 81

Currying is a functional programming technique that takes advantage of the idea that functions with multiple parameters can be viewed as a higher-order function of a single parameter.

   (define (curry-two-parameters f)
      ; Create a function that takes a single parameter
      (lambda (x) 
      ; Create a function that takes a single parameter
         (lambda (y) (f x y))
      )
   )
   ; creates a function 

   (((curry-two-parameters +) 3 ) 4)
   ; returns 7

Lists

Lists are an important data structure used by Scheme programs.

General form (note, if evaluated this list will have 1 as the function call)

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

can have literals of any type

     ("cp2050" "is" "fun")

can mix literals of any type

     ("foo" 4 5.3)

can contain other lists

     (42 ("is" "the" "answer") 5.3)

Nesting of lists can be taken to arbitrary levels

Standard list stuff

The empty list.

()

Return a list containing the objects as its elements. None of the objects will be evaluated.

'(obj ...)

Return true if obj is the empty list, otherwise return false.

(null? obj)

Return the first element of list. It is an error to try to get the first element of the empty list.

(first list) or (car list)

Return list with its first element removed. It is an error to try to get the rest of the empty list.

(rest list) or (cdr list)

Return a list with obj as its first element and list as the rest of the elements.

(cons obj list)

Return a list having the objects as its elements.

(list obj ...)

Return the number of elements in list.

(length list)

Return a list consisting of all of the elements of the first list, followed by all the elements of the second list, and so on.

(append list ...)

Return a list consisting of the elements of list in the opposite order.

(reverse list)

Return the first sublist of list whose first element is obj. The elements are compared using eqv?

(memv obj list)

map applies proc element-wise to the elements of the lists and returns a list of the results, in order from left to right. That is, map first takes the first element of each list and passes those values to proc. Then it takes the second element of each list and passes those values to proc. And so on, until all the elements of the lists have been used. The results of each of the calls to proc are joined together in a list in the order obtained and returned by the map call. The lists must be lists, and proc must be a procedure taking as many arguments as there are lists. If more than one list is given, they must be the same length.

(map proc list ...)

Booleans

(not obj)

Returns #t if obj is false, otherwise #t.

(and test ...)

The test expressions are evaluated from left to right. If one of them evaluates to false, then false is returned and no further expressions are evaluated. If all the expressions evaluate to true, the value of the last expression is returned.

(or test ...)

The test expressions are evaluated from left to right. If one of them evaluates to true, then the value of that expression is returned and no further expressions are evaluated. If all the expressions evaluate to false, then false is returned.

Numbers

Returns true if all of its arguments are equal numerically, otherwise returns false.

(= num ...)

Returns true if each argument is less than the argument following it, otherwise returns false. Analogously, there are procedures >, <= and >=.

(< num ...)

Return the maximum of the argument numbers. Analogously, there is a procedure min.

(max num ...)

Return the sum of the argument numbers. Analogously, there are procedures -, * and /.

(+ num ...)

Return the absolute value of num.

(abs num)

Return the value of num1 raised to the num2 power.

(expt num1 num2)

Strings

Return the number of characters in string.

(string-length string)

Return true if string1 and string2 contain the same characters, otherwise return false.

(string=? string1 string2)

Return true if string1 is alphabetically less than string2, otherwise return false. Analogously, there are procedures string>?, string<=? and string>=?.

(string<? string1 string2)

Start and end are integers indicating character positions in the string numbered from the left starting at 0. Returns the substring of string starting at character number start and finishing at the character before character number end.

(substring string start end)

Return a string consisting of all the argument strings concatenated together.

(string-append string ...)

Miscellaneous

Read a representation of a Scheme object from the user and return that object.

(read)

Write a representation of obj to the terminal.

(print obj)

Write a newline to the terminal.

(println)

Errors

Sometimes the cause of the error will be obvious from the message:

     > (-)
     ERR: -: Value expected in function - : nil

Tracing

Can trace functions

     > (trace foo)
     #<unspecified>
     > (foo)
     #FUNTION FOO CALLED
     #RETURN FROM FOO

Copyright © 2019 by Curtis Dyreson. All rights reserved.