## Language

This page provides a summary of the programming language used in this course: Beginning Student Language in part 1, then progressing to Intermediate and Advanced) later in the course.

### Values

Numbers: | 1, 3.5, 1/2, #i1.4142135623730951, ... |

Strings: | "Marvolo", "Black", "carrot", ... |

Images: | , ,... |

Booleans: | true, false |

Compound data: | (make-person "Claude" "Monet"), ... |

Lists: | empty, (cons 2 (cons 1 empty)), (cons "x" (cons "y" (cons "z" empty))), ... |

NOTE: The primitive types are: ` Number, Integer, Natural `(Integers greater than or equal to 0)`, String, Image and Boolean 2htdp/image also provides a primitive Color type`

### Primitive Operations

`+, -, *, / ... string-append, string-length, substring ... circle, square, overlay, above, beside...not, =, <, >, string=?, string<?, cons, first, rest, empty?, cons?`

### Forming Expressions

Form | Example |
---|---|

<value> |
3 |

<name-of-defined-constant> |
WIDTH |

(<name-of-primitive-operation> <expression> ...) |
(+ 2 (* 3 6)) |

(<name-of-defined-function> <expression> ...) A function call should have the same number of operands as parameters. |
(yell "hello") |

(if <question> <true-answer> <false-answer>) <question> must be an expression that evaluates to a boolean. <true-answer> and <false-answer> must be expressions. |
(if (> (string-length x) 3)"long" "short") |

(cond [<question> <answer>] ...) Each <question> must be either else or an expression that evaluates to a boolean. Each <answer> must be an expression. |
(cond [(> x y) "more"][(< x y) "less"] [else "same"]) |

(and <question> ...) Each <question> must be an expression that evaluates to a boolean. |
(and (< 0 x) (>= x 10)) |

(or <question> ...) Each <question> must be an expression that evaluates to a boolean. |
(or (< x 0) (> x 10)) |

Intermediate Student Language(local [<definition>...] <expression>) Any function or constant defined within the local is valid within the entire body of the local expression, but not outside of the local expression. |
(local [(define DOT (circle 5 "solid" "red")) (define (add-dot img) (beside img DOT))] (add-dot (square 20 "solid" "blue"))) |

Intermediate Student Language(shared [(<variable-name> <expression>)...] <expression>) Shared is a special version of local that makes it possible to build circular structure. Any variable defined within the shared is valid within the entire body of the shared expression, but not outside of the shared expression. By convention the variable names that are used in circular references are given names of the form -1- -2- etc. But this is just a convention, any variable name can be used. |
(shared [(-1- (list -2-)) (-2- (list -1-))] -1-) |

### Forming Definitions

(define SIZE (* 3 6)) ;a constant definition, the value of SIZE is 18

(define (bulb c) ;defines a function named bulb, with parameter c (circle 30 "solid" c)) ;this is the body of the function

(define-struct wand (wood core length)) ;defines the functions below: ; constructor: make-wand ; selectors: wand-wood, wand-core, wand-length ; predicate: wand?

### Evaluation Rules

For a **constant reference**, such as `SIZE`:

- The constant reference evaluates to the defined value of the constant.

For a **call to a primitive** such as `(+ 2 (* 3 6))`:

- First reduce the operands to values: proceed left to right making sure all the operands are values, for any that are not, evaluate them.

These values are called the arguments to the primitive. - Apply the primitive to those arguments.

For a **call to a defined function** such as `(bulb (string-append "r" "ed"))`:

- First reduce the operands to values (as for a call to a primitive). These values are called the arguments to the function.
- Replace the function call expression with the body of the function in which every occurrence of the parameter(s) has been replaced by the corresponding argument(s).

For example:

(bulb (string-append "r" "ed")) (bulb "red") (circle 30 "solid" "red")

For an **if expression**:

- If the question is not a value, evaluate it and replace it with its value.
- If the question is
`true`, replace the entire if expression with the true answer expression. - If the question is
`false`, replace the entire if expression with the false answer expression - If the question is a value other than
`true`or`false`, signal an error

For example:

(if (> (+ 1 2) 3) (* 2 3) (* 3 4)) ;since (> (+ 1 2) 3) is an expression, not a value, ;evaluate it left to right (if (> 3 3) (* 2 3) (* 3 4)) (if false (* 2 3) (* 3 4)) ;replace entire if expression with the false answer expression (* 3 4) ;evaluate false answer expression 12

For a **cond expression**:

- If there are no question/answer pairs, signal an error.
- If the first question is not a value, evaluate it and replace it with its value. That is, replace the entire
`cond`with a new`cond`in which the first question has been replaced by its value. - If the first question is
`true`or`else`, replace the entire`cond`expression with the first answer. - If the first question is
`false`drop the first question/answer pair; that is, replace the`cond`with a new`cond`that does not have the first question/answer pair - Since the first question is a value other than
`else`,`true`or`false`, signal an error.

For example:

(cond [(> 3 3) "more"] [(< 3 3) "less"] [else "same"]) ;the first question is not a value, the expression ;(> 3 3) is evaluated and replaced with a value (cond [false "more"] [(< 3 3) "less"] [else "same"]) ;the first question is false, so the first ;question/answer pair is dropped (cond [(< 3 3) "less"] [else "same"]) ;the first question is not a value, so (< 3 3) ;is evaluated and replaced with its value (cond [false "less"] [else "same"]) ;the first question is false, so the first ;question/answer pair is dropped (cond [else "same"]) ;since the question is else, the entire cond expression ;is replaced by the answer "same"

For an **and expression**:

- If there are no expressions produce
`true`. - If the first expression is not a value, evaluate it and replace it with its value.
- If the first expression is
`false`produce`false` - If the first expression is
`true`replace the entire`and`expression with an`and`expression without the first expression. - If the first expression is a value other than
`true`or`false`, signal an error.

For example:

(and (< 0 3) (< 3 10)) ;since (< 0 3) is an expression, not a value, ;evaluate it (and true (< 3 10)) ;first expression is true, drop it from the and (and (< 3 10)) ;now evaluate (< 3 10) (and true) ;now drop true (and) ;an empty and produces true

For an **or expression**:

- If there are no expressions produce
`false`. - If the first expression is not a value, evaluate it and replace it with its value.
- If the first expression is
`true`produce`true` - If the first expression is
`false`replace the entire`or`expression with an`or`expression without the first expression. - If the first expression is a value other than
`true`or`false`, signal an error.

For example:

(or (< 14 0) (> 14 10)) ;since (< 14 0) is an expression, not a value, ;evaluate it (or false (> 14 10)) ;first expression is false, drop it from the and (or (> 14 10)) ;now evaluate (> 14 10) (or true) ;first expression is true so produce true true

*Intermediate Student Language*

For a **local expression**:

- For each locally defined function or constant, rename it and all references to it to a globally unique name, and
**in the same step**lift the local definition(s) to the top level with any existing global definitions, and**in the same step**replace the local expression with the body of the local in which all references to the defined functions and constants have been renamed.

For example:

(define b 1) (+ b (local [(define b 2)] (* b b)) b) ;b evaluates to its defined value, 1 (define b 1) (+ 1 (local [(define b 2)] (* b b)) b) ; since b is a locally-defined constant, ;it is renamed to a globally unique name b_0 ;the local definition of b_0 is lifted to ;the top level and the entire local expression ;is replaced by its body (define b 1) (define b_0 2) ;---this renamed define was lifted (+ 1 (* b_0 b_0) ;---entire local replaced by renamed body b) ;evaluation continues normally from this point

For a **shared expression**:

The evaluation of shared is truly one of the deep mysteries of the universe. There are two very different ways to describe the evaluation rules.

One cannot be described exactly in terms of BSL (or ISL), but informally goes as follows:

- Each of the variables is defined as a constant with a special unique dummy value.
- Then the expressions are evaluated.
- Then each of the constants has its value change to the corresponding value. This is the part we have no words for in BSL or ISL, it is called mutation.
- Finally each of those values is traversed and each time one of the dummy values appears it is replaced in-situ by the corresponding value. (A different form of mutation.)

This evaluation rule for shared is cumbersome but goes beyond what we know.

The other evaluation rule is truly profound, see The Why of Y for an explanation.

### Built-In Abstract Functions

ISL and ASL have the following built-in abstract functions.

;; Natural (Natural -> X) -> (listof X) ;; produces (list (f 0) ... (f (- n 1))) (define (build-list n f) ...) ;; (X -> boolean) (listof X) -> (listof X) ;; produce a list from all those items on lox for which p holds (define (filter p lox) ...) ;; (X -> Y) (listof X) -> (listof Y) ;; produce a list by applying f to each item on lox ;; that is, (map f (list x-1 ... x-n)) = (list (f x-1) ... (f x-n)) (define (map f lox) ...) ;; (X -> boolean) (listof X) -> boolean ;; produce true if p produces true for every element of lox (define (andmap p lox) ...) ;; (X -> boolean) (listof X) -> boolean ;; produce true if p produces true for some element of lox (define (ormap p lox) ...) ;; (X Y -> Y) Y (listof X) -> Y ;; (foldr f base (list x-1 ... x-n)) = (f x-1 ... (f x-n base)) (define (foldr f base lox) ...) ;; (X Y -> Y) Y (listof X) -> Y ;; (foldl f base (list x-1 ... x-n)) = (f x-n ... (f x-1 base)) (define (foldl f base lox) ...)