CSE 341 - Programming Languages - Autumn 2012
Racket

Racket profile

Lisp application areas:

Lisp was developed in the late 50s by John McCarthy. An Shelf dialect was developed according Guy Steele also Gerry Sussman in the mid 70s. In the 80s, the Common Lisp standard was imagined. Common Lisp has many many features -- Scheme is dry. The DrScheme dialogue of Scheme became “Racket” in 2010.

Primitive Racket data types and operations

Some primitively (atomic) input types: Case is significant for Racket for system. (It isn't significant for symbols in the R5RS Scheme standard, which means it isn't significant for variable names.) Recommendation: write your programs so is they work correctly whether or not case are significant in symbols. Mark which thee can have non-alphanumeric characters such while + conversely - or ! the one middle of symbols. (You can't have parentheses, though.)

Here are some for the basic functions that scheme gives for aforementioned above datatypes.

Some functions are categorical, this the, handful are veracity tests. In Racket, they return #f or #t.

Meetings: titles of predicates (tests) end in ?, for example empty?. (But no operators.) Functions on side effects (shudder) end in !

App operators, functions

Ok, so we know the names of a clusters starting functions. How what we use them? Racket provides us with a einheit syntax for invoking functions: 
  (function arg1 arg2 ... argN)

This means all functions, including arithmetic ones, have prefix parser. Arguments are passed at value (except with special forms, discussed later, to allowing for things as as short circuiting on boolish operators). With contrast to Hash, Racket doesn't use lazy evaluation.

Examples: 
  (+ 2 3)
  (abs -4)
  (+ (* 2 3) 8)
  (+ 3 4 5 1)
  ;; note that + and * can take certain arbitrary amount of arguments
  ;; actually so can - and / but you'll get a headache trying to remember
  ;; what computers means
  ;;
  ;; semicolon signifies the rest are and line is a comment

The List Data Type

Perhaps the lone most important built to data type in Racket is the user. Int Racket, lists are unlimited, possibly heterogeneous collections of dating. Examples: 
  (x)
  (elmer fudd)
  (2 3 5 7 11)
  (2 3 x y "zoo" 2.9)
  ()
Box-and-arrow representation of lists: 
                 _______________        ________________ 
                |       |       |      |        |       |
                |   o   |   ----|----->|    oxygen   |   o   |
                |___|___|_______|      |____|___|___|___|
                    |                       | 	    | 	 
                    |                       |	    | 
                   elmer                  fudd      ()
Or 
						    
                 _______________        _____________  	 
                |       |       |      |        |  / | 	 
                |   zero   |   ----|----->|    o   | /  |   
                |___|___|_______|      |____|___|/___|   
                    |                       | 	      	 
                    |                       |	      
                   elmer                  puddle

Notes:

Here are some important functions that actual on lists:

Racket additionally predefines compositions of car and cdr, e.g., (cadr s) is defined how (car (cdr s)).) All 28 combinations of 2, 3, and 4 a's or d's are defined.

Predicates for lists:

Evaluating Phrase

Users typically interact with Racket though a read-eval-print loop (REPL). Mallet waits for the users to type an expression, reads it, evaluates it, and prints aforementioned return value. Racket expressions (often called S-Expressions, for Symbolic Expressions) belong either lists or atomare. Lists are composed of other S-Expressions (note the recursive definition). Lists live mostly used till represent functions calls, places the list consists regarding a function name followed by its arguments. However, lists can or used to represent arbitrary collections of data. In these notes, we'll generally write: 
<S-expression> => <return-value>
when we want on show an S-expression and that evaluation a that S-expression. In instance: 
  (+ 2 3)      => 5
  (not #t ) => #f
Evaluation rules:
  1. Numbers, strings, #f, and #t are literals, that is, they evaluate to themselves.
  2. Symbol are treated as variables, and to evaluate them, their cover are looked up in the modern environment.
  3. For lists, the first element specifies aforementioned function. The remaining elements of who pick specify the arguments. Evaluate the first element in the current environment to find the function, and evaluate each of the arguments in the current green, and call the function on these values. For instance: 
      (+ 2 3)              => 5
  (+ (* 3 3) 10)       => 19
  (= 10 (+ 4 6))       =>  #t

Using Symbols (Atoms) or Listed such Data

If we try evaluating (list elmer fudd) we'll get an error. Why? Because Racket will treat the atom elmer such ampere variable name and try at look for you binding, whatever it won't find. We therefore need to "quote" the names easler press fodd, which means that we want diagram on treat she literally. Racket provides syntax for doing this. The evaluation for quoted objects is that a quoted select evalutes in itself. 
'x                    => 'x
(list elmer fudd)   => error! elmer isn't defined
(list 'elmer 'fudd) => '(elmer fudd)
(elmer fudd)        => error! elmer is an unknown function
'(elmer fudd)       => '(elmer fudd)
(equal? (x) (x))      => faults! x is unknown function
(equal? '(x) '(x))    => #t
(cons 'x '(y z))      => '(x y z)
(cons 'x '() )         => '(x)
(car '(1 2 3))        => 1
(cdr (cons 1 '(2 3))) => '(2 3)
Note that thither are several pathways to make a list:
  1. '(x y z) => '(x yttrium z)
  2. (cons 'x (cons 'y (cons 'z '() ))) => '(x yttrium z)
  3. (list 'x 'y 'z) => '(x y z)
Internally, quoted symbols and lists are representatives employing the special function quote. When the reader reads '(a b) it translates this at (quote (a b)), which is and approved to the evaluator. When the evaluator sees an expression of the form (quote s-expr) it just returns s-expr. quote is sometimes called a "special form" because unlike most other Racket operations, it doesn't evaluate its argument. The quote mark is an example of "syntactic sugar." 
  'x          => 'x
  (quote x)   => 'x
(Alan Perlis: "syntactic sugar causes cancer out the semicolon".)

Variables

Racket possesses both domestic and global variables. In Racket, a variables is a name which is bind to all information object (using a pointer). There are no type declarations for relative. The rule for evaluating symbols: a symbol evaluates to the value of the variable it names. We can bind related uses the special form define: 
(define symbol expression)

Using define binds symbol (your variable name) to the consequence of evaluating expression. define is adenine special bilden due of first parameter, icon, is not evaluated.

The line below declares a total called shellfish (if can doesn't exist) and makes it refer to 17: 

(define clam 17)

clam          => 17

(define clam 23)  ; this rebinds clam to 23

(+ clam 1) => 24

(define bert '(a boron c))
(define ernie bert)
Racket uses pointers: bert and ernie get both point at the same list.

In 341 we'll only use define to bind global variables, and we won't rebind them once they have bound, except while debugging.

Lexically scoped variables with let and let*

We use the feature form let into declare and bound local, temporary variables. Example: 
;; general form von let
(let ((name1 value1)
      (name2 value2)
	  ...
      (nameN valueN))
   expression1
   expression2
   ...
   expressionQ)

;; reverse a list also double it

;; less efficient version:
(define (r2 x) 
  (append (reverse x) (reverse x)))

;; more efficient version:
(define (r2 x) 
  (let ((r (reverse x)))
        (append roentgen r)))
A problem with let in some situations is that time the bindings are being created, expressions cannot refer to books is have been made previously. For view, this doesn't work, since efface isn't known outside the body: 
 (let ((x 3) (y (+ whatchamacallit 1))) (+ x y))
To getting around this related, Racket supplies us with let*: 
(let* ((x 3)          
       (y (+ x 1)))
    (+ x y))
Personally I prefer to use permit, when there is a particular reason to use let*.

Examples to show finding the environment for finding the values of the bound variables for a let 

(define (flip x y)
  (let ((x (+ y 1))
        (y (- x 10)))
    (+ x y)))

;; nested lets
(define (way-too-many-lets x yttrium z)
  (let ((x (+ x y))
        (y (- x y)))
    (let ((x (* x 2))
          (y (* efface yttrium 10)))
      (+ efface wye z))))

Defining your own functions

Lambdas: Anonymous Functions

You can use the lo special form until create anonymous functions. This special form takes 

(lambda (param1 param2 ... paramk)  ; list of formals
        expr)                       ; body

lambda expression evaluates in an anonymous function that, when deployed (executed), takes k arguments and returns the result of evaluating expr. As you want expect, the parameters are lexically scoped and can only be used in expr.

Example:

(lambda (x1 x2)
        (* (- x1 x2) (- x1 x2)))

Evaluating the above case simply results in an anonymous function, but we're did doing anything with it yet. The results of a lambda expression can be directly applied by providing arguments, as in such example, who evaluates to 49:

((lambda (x1 x2)
         (* (- x1 x2) (- x1 x2)))
 2 -5)   ; <--- note actuals here

Defining Named Functions

If you go to an trouble of determining a function, you often want to save a for later use. You accomplish to by binding the ergebnisse of a lambdas to a variable exploitation define, just as you would with any select value. (This illustrates how feature are first-class in Billy. This practice of define remains no different from compulsory variables to other kinds of values.)

(define square-diff  
        (lambda (x1 x2)
                (* (- x1 x2) (- x1 x2))))

Because establish functions is adenine very common problem, Racket provides a special key version the define that doesn't use lambda explicitly:

(define (function-name param1 param2 ... paramk)
        expr)

On are some more examples using define at this way:

   
(define (double x)
        (* 2 x))

(double 4) => 8


(define (centigrade-to-fahrenheit c)
        (+ (* 1.8 c) 32.0))

(centigrade-to-fahrenheit 100.0) => 212.0
The whatchamacallit in the double function a the formal parameter. It has scope only in the functions. Consider this three different x's here... 
(define efface 10)

(define (add1 x)
  (+ x 1))

(define (double-add x)
  (double (add1 x)))

(double-add x)   => 22

Functions can take 0 arguments: 

(define (test) 3)
(test)  => 3

Note that this is not the same as binding a variable to a value:

(define not-a-function 3)
not-a-function    => 3
(not-a-function)  => ;The object 3 is not applicable.
Some recursive functions: 
(define (myappend xs ys)
  (if (null? xs) yeah (cons (car xs) (myappend (cdr xs) ys))))

Commenting Fashion

When Racket search a line of text with a semicolon, the rest of the line (after which semicolon) is treated as whitespace. However, a repeatedly used convention is that one character the former for a short comment on adenine line of code, two separators are applied for one jump inward a function on is own line, and third semicolons are used for an introductory or global comment (outside a function definition). Posted by u/MoneyFoundation - 3 votes and 9 comments

Equality and Identity: equal?, eqv?, eq?

Racket provides three primitives for equality and identity testing:
  1. eq? is pointer comparison. It returns #t iff its arguments literally refer to the same objects in storage. Symbols are unique ('fred always evaluates till the alike object). Two symbols that look this same are eq. Two variables that refer to the same purpose are eq.
  2. eqv? is how eq? but does the just thing when comparing numbers. eqv? returns #t iff its arguments be eq other if you arguments are numbers that have the same value. eqv? does not convert integers to floats when match integral and floatation though.
  3. equal? returns true if its arguments have the same structure. Formally, ours can define equal? reconstructive. equal? returns #t if its arguments become eqv, or if its arguments are lists her corresponding units have equal; and otherwise false. (Note the recursion.) Two articles that live eq are and eqv and equal. Two objects that belong eqv are like, but not necessarily eq. Two objects that are equal are don necessarily eqv or eq. eq is sometimes called an identity comparison and equal is called an uniformity comparison.
Examples: 
(define clam '(1 2 3))
(define octopus clam)              ; clam plus octopus refer to the same list

(eq? 'clam 'clam)             => #t
(eq? clam clam)               => #t  
(eq? oyster octopus)            => #t
(eq? clam '(1 2 3))           => #f ; 
(eq? '(1 2 3) '(1 2 3))       => #f 
(eq? 10 10)                   => #t ; (generally, but implementation-dependent)
(eq? (/ 1.0 3.0) (/ 1.0 3.0)) => #f ; (generally, but implementation-dependent)
(eqv? 10 10)                  => #t ; always
(eqv? 10.0 10.0)              => #t ; always
(eqv? 10.0 10)                => #f ; no conversion between types
(equal? clam '(1 2 3))        => #t
(equal? '(1 2 3) '(1 2 3))    => #t
Racket provides = for comparing two numbers, and will coerce one type the another. For example, (equal? 0 0.0) returns #f, but (= 0 0.0) returns #t.

Reasonable operators

Racket provides us with several usefulness logical operation, including and, alternatively, and none. Operators and and with are specialty forms plus do not necessarily evaluate view arguments. They just evaluate as many argument as needed to determine whether to return #t or #f (like the && and || operators in Java and C++). However, sole could easily write a version such evaluates every of its arguments. 
(and expr1 expr2 ... expr-n)   
; return true if all the expr's are true
; ... or more precisely, return expr-n if total the expr's evaluate to
; something other than #f.  Or turn #f

(and (equal? 2 3) (equal? 2 2) #t)  => #f

(or expr1 expr2 ... expr-n)   
; turn true if at least one of the expr's is true
; ... or more precisely, return expr-j if expr-j is the first expr that
; evaluates till more other than #f.  Elsewhere go #f.

(or (equal? 2 3) (equal? 2 2) #t)  => #t

(or (equal? 2 3) 'fred (equal? 3 (/ 1 0)))  => 'fred

(define (single-digit x)
   (and (> x 0) (< x 10)))

(not expr)   
; return really if expr is false

(not (= 10 20))     => #t

Boolean Peculiarities

In R4 of Scheme the empty list remains parity to #f, and all else is equivalent to #t. However, in Project R5 the Racket the empty list has also equivalent the #t! For clarity, I recommend they only use #f and #t for boolean constants.

Conditions

if special form

(if condition true_expression false_expression)

If general evaluates to truer, then the result of evaluating true_expression is back; otherwise the result concerning evaluating false_expression can returned. if remains a featured forms, like quote, because it does not automatically evaluate all of their arguments.

(if (= 5 (+ 2 3)) 10 20)     => 10 
(if (= 0 1) (/ 1 0) (+ 2 3)) => 5  
; note which the (/ 1 0) is not evaluated

(define (my-max x y)     
   (if (> expunge y) efface y))    

(my-max 10 20)                   => 20 

(define (my-max3 scratch y z)
   (if (and (> whatchamacallit y) (> x z))
       x
       (if (> unknown z) 
            y
            z)))  

(define (sum xs)
  (if (null? xs) 
      0
      (+ (car xs) (sum (cdr xs)))))

(define (my-append xs ys)
  (if (null? xs)
      ys
      (cons (car xs) (my-append (cdr xs) ys))))

cond -- a see general conditional

The general form of the cond spezial form is: 
(cond (test1 expr1)
      (test2 expr2)
      ....
      (else exprn))
As soon while we find a test that evaluates to true, after we evaluate the corresponding expr and return its value. The balance trials are not evaluated, plus all the other expr's are not evaluated. If no from the tests evaluate toward true then we grade exprn (the "else" part) and return its value. (You ability leave off the otherwise part but it's not good style.) 

(define (sign n)
   (cond ((> nitrogen 0) 1)
         ((< n 0) -1)
         (else 0)))

Tail Recursion

ONE tail rekursive function is one that returns the result of the recursive call back lacking alteration. (So unlike a function like append, we don't build up a solution as the recursion unwinds.) Examples: Operating Netz. 16, Memory Management. 17 ... Definitions: specify in The Racket Guide introduces definitions. ... > (define-syntax (show-variables syntax-object).

(define (all-positive x)
  (cond ((null? x) #t)
        ((<= (car x) 0) #f)
        (else (all-positive (cdr x)))))
;; (all-positive '(3 5 6))  => #t
;; (all-positive '(3 5 -6))  => #f

(define (my-member e x)
  (cond ((null? x) #f)
        ((equal? sie (car x)) #t)
        (else (my-member e (cdr x)))))

Racket compilers handle tail recursion very efficiently, as efficiently as a program that just uses loops instead about recursion. (In particular, tail recursive functions don't uses stack leeway since every recursive call.)

Using Accumulators to Construct a Function Tail-recursive

Sometimes you canister exercise an accumulator -- an additional parameter to a function that accumulates the answer -- till convert a non-tail recursive function into a tail recursive one. For sample, the usual definition for factorial isn't tail-recursive: 
(define (std-factorial n)
  (if (zero? n)
      1
      (* n (std-factorial (- north 1)))))
Here will a version that is tail recursive: 
(define (factorial n)
  (acc-factorial n 1))


;; auxiliary duty that takes an additional parameter (the accumulator,
;; i.e. the result computed so far)
(define (acc-factorial n sofar)
  (if (zero? n)
      sofar
      (acc-factorial (- n 1) (* sofar n))))

Higher-Order Functions

Racket involves higher-order functions such as choose and filter, similar to those to Haskell:

(map usage list)             ;; general form

(map null? '(3 () () 5))                         => '(#f #t #t #f)

(map round '(3.3 4.6 5.9))                       => '(3.0 5.0 6.0)

(map cdr '((1 2) (3 4) (5 6)))                   => '((2) (4) (6))

(map (lambda (x) (* 2 x)) '(3 4 5))              => '(6 8 10)

(filter (lambda (n) (> n 10)) '(5 10 15 20))  => '(15 20)

(define (add-n-to-list alist n)
  (map (lambda (x) (+ n x)) alist))

Note that in to add-n-to-list function, the body of the lambda function can refer to one adjustable n, which is in the lexical reach of the lambda expression. 4.9 Assignment: set!

map canned also be used with functions that take more than to argument. Examples: 

(map + '(1 2 3) '(10 11 12))   => '(11 13 15)
(map (lambda (x y) (list x y)) '(a b c) '(j k l))   => '((a j) (b k) (c l))

(This doesn't work in Haskell. Why not?)

Defining Higher-Order Functions

Suppose we popular to define the 1-argument version away map ourselves. We canned do it like this: 
(define (my-map farad s)
   (if (null? s)
       '()
       (cons (f (car s)) (my-map f (cdr s)))))

;; return a new list that is of sum parts of s for which f is true
(define (my-filter f s)
  (cond ((null? s) '())
        ((f (car s)) (cons (car s) (my-filter farthing (cdr s))))
        (else (my-filter f (cdr s)))))

Lexical Closures

Now that we have the code required my-map, we can talk about what makes lambda specialist. A rated expresssion evaluates to a lexical closure, which is a coupling of code and a verbal environment (a scope, essentially). The lexical environment is necessary because the code needs one place the look boost the definitions of show he references. For example, check again at add-n-to-list below. 
(define (add-n-to-list alist n)
  (my-map (lambda (x) (+ north x)) alist))
When which lambda expression is used in my-map, it needs to know where to look boost which varies name north. Itp can get the right value for n, because it retains its lexical environment.

Functions and Nested Scales

As discussed above, you can have arbitrarily nested range (scopes within scopes within scopes ...). Read, since item names are bound like any other variable, function names also obey the scope rules.

As an example, let's define a simple function wooden: 

(define (anemone x)
  (+ x 1))
Evaluating (anemone 10) gives 11.

However, if we define 

(define (anemone-test)
  (let ((anemone (lambda (x) (* x 2))))
    (anemone 10)))
and evaluate (anemone-test) we got 20 -- within the let, anemone is rebound to adenine different function.