Scheme

From CS 61A Wiki
Jump to: navigation, search

Scheme is a functional programming language, and the target language for the interpreter built in the final project of CS61A. Please add your descriptions and simple examples of the basic forms of Scheme here.

Syntax

Below are various syntax examples of how to use scheme. For more information on scheme and functional programming see John DeNero's Functional Programming. [1] You can play around with an online scheme interpreter here.

Define

Scheme syntax for defining expressions and statements are as follows:


(define (function/variable name and arguments go here) (return statement if it's a function))


So, for example, if you wanted to define a simple square function, that would take in some value x and return it's square it would look something like this:

>>> (define (square x) (* x x))

The first statement after Define is read as the name of the function or variable and the arguments of the function, then the return value. To give a function multiple arguments, simply declare all the arguments inside a parenthetical like so:

>>> (define (multiply x y) (* x y))
>>> (multiply 3 2)
>>> 6


Conditional Statements

Conditional statements such as cond, and, or, and if are used much the same as in python with the exception of the cond statement.

if statements

(if (condition) (true value) (false value))

The if statement is a conditional that contains three statements. It first evaluates its condition, and from there returns either the true or the false value based on its evaluation.

>>> (if #t (* 3 2) (- 1 2))
>>> 6
>>> (if #f (* 3 2) (- 1 2))
>>> -1

and statements

(and (condition) ... (tail value))

The and statement evaluates its arguments one by one until either:

  • It evaluates a false expression, in which case it'll return false.
  • It evaluates all of its condition as true, in which case it'll return it's tail value.
  • If no arguments are given, it'll return true.
  • If only one expression is given it'll consider it the tail value and return the tail value.

Examples:

>>> (and #t #f 1/0)  ;this will never reach 1/0
>>> #f
>>> (and #t #t 100) ;will return the tail value no matter how many expressions if they're all true.
>>> 100
>>> (and #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t 100) ;see?
>>> 100
>>> (and) ;no conditions returns true.
>>> #t
>>> (and '(1/0)) ;only one expression = tail value
>>> (1/0) ;nothing broke. Yet. Just don't ever use this. It's not even in the right syntax. 
>> (and #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #t #f '(<--scumbag false))
>>> #f

or statements

(or (condition) ... (more conditions))

The or statement takes in only expressions to use as conditions. If any one of these statements return true, then the entire expression returns true. This means that the expression will always try to evaluate all of its arguments.

(or #f #f #f #f #f #f #f #f #f #f #f #f 1/0)


cond statements

The cond statement


Dot Notation

In Scheme, pairs will often be expressed using dot notation. The two values in a dotted pair are separated by a dot.

 
> (equal? (cons 1 2) '(1 . 2))
#t
> (equal? '(1 2 3 4) '(1 . (2 . (3 . (4 . ())))))
#t

In the following example, the first expression is false because '(1 2) represents a list in which the first value is 1 and the second value is another list with first value 1 and second value null. '(1 . 2) simply represents the pair in which the first value is 1 and the second value is 2.

> (equal? '(1 2) '(1 . 2))
#f
> (equal? '(1 2) (cons 1 (cons 2 ())))
#t
> (equal? '(1 . 2) (cons 1 2))
#t

lambda statements

Lambda functions work just like they do in Python. By defining a lambda function and assigning it to a variable, you are then able to call that function by applying that variable.

STk> (define x (lambda (y) (* y y)))
x
STk> (x 4)
16

They can also be used as a type of operator. Just like we would use addition or multiplication. Lambda allow for more flexibility, however.

STk> (+ 4 4)
8
((lambda (a b) (+ a b)) 4 4) ;These two lines do the same thing
8

cons statements

The cons statement allows users to join together values to form lists. There are a few distinct cases in which the cons statement produces different results.

1. "Cons-ing" two single values produces what is known as a "badly formed list". A pair, separated by a dot.

STk> (cons 4 5)
(4 . 5)

Continuing to "cons" on single values continues the "badly formed list".

STk> (define x (cons 4 5))
x
STk> x
(4 . 5)
STk> (cons x 6)
((4 . 5) . 6)
STk> (define y (cons x 6))
y
STk> y
((4 . 5) . 6)
STk> (cons y 7)
(((4 . 5) . 6) . 7)

2. A correctly formed list, using cons requires a special format. Any time a dot is followed by a left parentheses in Scheme, it collapses to create a list. For instance.

STk> (cons 5 nil)
(5)

What would have ordinarily been (5 . ()) now turns into (5). Here's a better example of how to create a list using cons.

(cons 1
        (cons 2
              (cons 3
                    (cons 4 nil))))
(1 2 3 4)

Cons is ultimately useful in recursive processes that require one element to be added at a time. Each recursive step can be completed by using cons to link one element to a growing list.

car/cdr statements

The car statement allows the user to draw the first element from a list. The cdr statement provides the "rest" of the list, returning a list that includes every element except the first one. These two statements can be used to traverse any list and obtain their elements for processing.

STk> (car (list 1 2 3))
1
 
STk> (cdr (list 1 2 3))
(2 3)
 
STk> (define lst (list (list 1 2 3) 4 5)) ;( ( 1 2 3) 4 5 )
lst 
STk> (car lst )
(1 2 3)
STk> (car (car lst ))
1
STk> (cdr (car lst ))
(2 3)
STk> (car (cdr (car lst )))
2

car and cdr are invaluable tools to navigating and creating scheme algorithms.

References

  1. http://composingprograms.appspot.com/pages/32-functional-programming.html