Scheme

Scheme

-   Scheme is a dialect of Lisp.

-   It uses a lot of parentheses.

https://scheme.cs61a.org

61A Scheme

Why another language?

: The goal of this class is not to teach Python, but rather to teach a variety of programming techniques and core concepts.

How does learning another language help us?

- To see some key components across many programming languages.

- To see what paradigms certain languages prioritize.

- To learn how interpreters are implemented!

Scheme Expressions

: Scheme programs consist entirely of two types of expressions

1. Atomic expressions

2. Combinations

Scheme values

Atoms : primitive values that cannot be broken up into smaller parts

Procedures : function objects, either built-in or user-defined

Lists : a sequence of zero or more values

Combinations

- All non-primitive expressions in Scheme have the following syntax:

- A combination is either a call expression or a special form expression.

- The operator of a call expression evaluates to a procedure.

- The operator of a special form expression is a special form.

Call expressions

: A call expression applies a procedure to some arguments.

How to evaluate call expressions:

Step 1. Evaluate the operator to get a procedure.

Step 2. Evaluate all operands left to right to get the arguments.

Step 3. Apply the procedure to the arguments.

Special form expressions

- Special forms have special behaviors that allow us to write complex programs.

How to evaluate special form expressions:

-   Each special form has its own rules!

-   Some operands may not be evaluated.

Special Forms

Assigning values to names

The define special form assigns a value to a name : 

( define < name > < expr > )

How to evaluate:

Step 1. Evaluate the given expression.

Step 2. Bind the resulting value to the given name in the current frame.

Step 3. Return the name as a symbol.

Defining functions with names

The second version of define is a shorthand for creating a function with a name :

( define ( < name > < param1 > < param2 > … ) < body > )

How to evaluate:

Step 1. Create a lambda procedure with the given parameters and body.

Step 2. Bind it to the given name in the current frame.

Step 3. Return the function name as a symbol.

Creating functions

The lambda special form returns a lambda procedure :

( lambda ( < param1 > < param2 > … ) < body > )

How to evaluate:

Step 1. Create a lambda procedure with the given parameters and body.

Step 2. Return the lambda procedure.

Control flow

The if special form allows us to evaluate an expression based on a condition :

( if < predicate > < if-true > < if-false > )

How to evaluate:

Step 1. Evaluate the <predicate>.

Step 2. If <predicate> evaluates to anything but #f, evaluate <if-true> and return the value. Otherwise, evaluate <if-false> if provided and return the value.

 

Pairs and Lists _ Scheme data structures

-   The pair is the basic compound value in Scheme

-   Lists in Scheme are created using pairs; they’re linked lists

Pairs

- Pairs are created using the cons expression in Scheme

- car selects the first element in a pair

- cdr selects the second element in a pair

- The second element of a pair must be another pair, or nil

:

- The only type of sequence in Scheme is the linked list

  : We can create these with pairs using multiple cons expressions

- nil represents the empty list

 

Scheme

-   We are learning Scheme to compare conventions across different languages, study what paradigms certain languages emphasize, and, later, learn how languages are interpreted!

-   Scheme programs consist only of expressions, all of which can be categorized into either atomic expressions or combinations.

-   Combinations are either call expressions or special form expressions, and they differ in the value of the operator.

-   Scheme call expressions are evaluated just like they are in Python, but each special form has its own rules of evaluation.

-   The special forms we learned today are define, lambda, if, and cond.

-   Writing procedures in Scheme will require recursion; there is no special form for iteration!