1. Scheme Introduction

1. Background

1.1 Comparing Functional Programming Languages (FPLs) to Other Languages

Functional Programming Languages (FPLs): FPLs like Haskell and Scheme emphasize functions as first-class citizens, immutability, and referential transparency. Functions are pure, meaning they don’t have side effects and their output is solely determined by their input.
Imperative Languages: Languages like C and Java focus on changing state through statements and commands. They often rely on mutable data and have side effects. The focus is on the sequence of operations to achieve a result.
Object-Oriented Languages: Languages like Python and Java incorporate encapsulation, inheritance, and polymorphism. They blend functional and imperative styles, allowing mutable state and side effects, but also support functions and methods.

1.2 Referential Transparency:

Referential transparency means that an expression can be replaced with its value without changing the program’s behavior. This is a key property of pure functions in FPLs.

Example: In a function f(x) = x + 2, you can replace f(3) with 5 because f(3) always evaluates to 5 given x is 3.

1.3 Side Effects:

A side effect is any change in state or observable interaction with the outside world that occurs during the execution of a function. This includes modifying a global variable, writing to a file, or printing to the console.

In FPLs: Traditional FPLs avoid side effects by using pure functions. However, some FPLs allow controlled side effects, for example, in Haskell, through the IO monad.

1.4 Functions as Values in FPLs

Yes, functions can be treated as values in FPLs. They can be passed as arguments to other functions, returned as results, and assigned to variables.

1.5 Suitability of FPLs for Concurrent Systems

FPLs are often suitable for concurrent systems due to their emphasis on immutability and stateless functions. These characteristics help avoid issues related to shared mutable state and make it easier to reason about concurrent execution.

Example: Languages like Erlang and Elixir (based on the Erlang VM) use functional paradigms to manage concurrency and are designed to handle many concurrent processes efficiently.

1.6 Tail Recursion Optimization (TRO)

Tail recursion optimization is a technique where the compiler or interpreter optimizes tail-recursive functions to avoid growing the call stack. In a tail-recursive function, the recursive call is the last operation in the function.

Example: The tail-recursive version of a factorial function avoids stack overflow issues by reusing the current function’s stack frame.

1.7 Lambda Functions

Lambda functions are anonymous functions that are defined inline without a name. They are often used for short-lived, simple operations.

Example in Python: lambda x: x + 1 is a lambda function that adds 1 to its argument.

1.8 Closure

A closure is a function that captures the lexical environment in which it was defined, allowing it to access variables from that scope even after the outer function has finished executing.

Example in JavaScript:

function outer() {
  let x = 10;
  return function inner() {
    console.log(x);
  };
}
let closure = outer();
closure(); // Logs 10

1.9 Comparing Scheme and Elixir

Scheme: A minimalist, functional Lisp dialect that emphasizes recursion and symbolic computation. It’s known for its simplicity and powerful macro system.
Elixir: A functional language designed for concurrent, distributed systems. It runs on the Erlang VM and focuses on fault tolerance and scalability. Elixir has immutable data structures and a message-passing concurrency model.

Lisp and Scheme

Lisp (short for “LISt Processing”) is a family of programming languages that has a long history in computer science, dating back to its creation by John McCarthy in 1958. Lisp is known for its simple and powerful syntax, where code and data share the same structure (both are represented as lists). This feature, called “homoiconicity,” allows Lisp programs to easily manipulate code as data, making it a popular choice for symbolic computation, AI research, and academic exploration.

Scheme is a dialect of Lisp, created in the 1970s by Guy L. Steele and Gerald Jay Sussman. Scheme was designed to be a simpler, more elegant, and minimalistic version of Lisp, emphasizing a small core of powerful features and a clean, consistent design. It introduced several key ideas to the Lisp family, such as first-class continuations and lexical scoping, which influenced many later programming languages.

1.10 Orthogonality in Scheme

Scheme is considered orthogonal because its features are independent and can be combined in a modular way. For example, functions and conditionals can be combined without restrictions.

Example: You can use functions and conditionals together:
```
(define (max a b)
  (if (> a b) a b))
```

1.11 List Structures in Elixir and Scheme

Both languages use lists as fundamental data structures.

Scheme:
```
(define my-list (list 1 2 3))
```
Elixir:
```
my_list = [1, 2, 3]
```

1.12 Scheme’s `car` and `cdr` Functions

car: Returns the first element of a list.
```
(car (list 1 2 3)) ; Returns 1
```
cdr: Returns the rest of the list after removing the first element.
```
(cdr (list 1 2 3)) ; Returns (2 3)
```

1.13 Tail-Recursive Factorial Function in Scheme

To transform the given factorial function into a tail-recursive version:

(define (fact x)
  (define (fact-tail x acc)
    (if (= x 0)
        acc
        (fact-tail (- x 1) (* x acc))))
  (fact-tail x 1))

Here, fact-tail is the tail-recursive helper function, and acc accumulates the result.

2. What is an S-expression?

An S-expression (symbolic expression) is a notation used in Lisp and its dialects to represent both code and data. It is a way to write nested lists using a simple parenthesis-based syntax. S-expressions are used to encode structured data and code in a uniform format.

Basic Structure:
- Atoms: Basic elements that are indivisible, such as numbers, symbols (e.g., x, foo), or strings.
- Lists: Ordered sequences of S-expressions enclosed in parentheses. For example, (+ 1 2) is a list where + is the operator and 1 and 2 are operands.
Example:
- (+ 1 2) is a list with the operator + and two operands 1 and 2.
- (define (square x) (* x x)) is a list representing a function definition.

2.1 Visually Representing S-expressions

A visual representation of S-expressions often uses a tree structure where:

Nodes: Represent individual elements or sub-expressions.
Edges: Represent the hierarchical relationship between elements.

Example Visualization:

For the S-expression (+ 1 2), the tree representation is:

    +
   / \
  1   2

For a more complex S-expression like (define (square x) (* x x)), the tree representation is:

DEFINE
   /  \
SQUARE  (* x x)
   / \       / \
  x   (* x x)
        / \
       x   x

2.2 Evaluating S-expressions

The evaluation of an S-expression in Lisp involves the following steps:

1. Check for Atom or List:

If the S-expression is an atom, it is either a constant value or a variable. Constants evaluate to themselves, and variables are looked up in the environment.
If the S-expression is a list, further evaluation is required.

2. Evaluate the Function Call:

Function Name: The first element of the list is typically the function to be called. This element is evaluated to determine the actual function.
Arguments: The remaining elements of the list are the arguments to the function. Each argument is evaluated in the current environment.

3. Apply the Function:

After evaluating the function name and arguments, the function is applied to the arguments. The result of the function application is the result of the S-expression.

Example Evaluation:

Evaluate (+ 1 2):

1. Identify: + is a function, 1 and 2 are arguments. 2. Evaluate:

+ is the function that performs addition.
1 evaluates to 1.
2 evaluates to 2. 3. Apply: Perform the addition: 1 + 2 = 3.

Another Example:

Evaluate (define (square x) (* x x)):

1. Identify: define is a special form for defining functions. 2. Evaluate:

square is the function name.
x is the parameter.
(* x x) is the body of the function. 3. Apply: In Lisp, this will define a function square that takes one argument x and returns (* x x).

Thus, the evaluation process involves interpreting the list structure, applying functions, and using the results to compute the final value.