2. Syntax

1. Simple Example

To run a simple Scheme program in Ubuntu, you can use an interpreter like Gambit, MIT Scheme, or Racket. Here’s how you can do it using MIT Scheme:

1.1 Install MIT Scheme

Open a terminal and run the following command to install MIT Scheme:

sudo apt-get update
sudo apt-get install mit-scheme

1.2 Write a Scheme Program

Create a new file with a .scm extension (e.g., hello.scm). You can use any text editor, such as nano, vim, or gedit:

nano hello.scm

Write a simple Scheme program in the file:

(display "Hello, World!")
(newline)

Save and exit the editor.

1.3 Run the Scheme Program

You can run the program using the MIT Scheme interpreter:

mit-scheme --load hello.scm

This will execute the hello.scm file and display “Hello, World!” in the terminal.

1.4 Running in Interactive Mode

Alternatively, you can start the MIT Scheme interpreter in interactive mode by typing:

mit-scheme

Once in the interactive mode, you can type and run Scheme code directly:

(display "Hello, World!")
(newline)

To exit the interpreter, type:

(exit)

This setup should allow you to run simple Scheme programs on Ubuntu using MIT Scheme.

2. Control Structures

Scheme, like other Lisp dialects, has a few core control structures for managing the flow of a program. Here are the most common ones:

2.1 Conditional Expressions

if

• The if expression is the basic conditional construct.
• Syntax: (if condition then-expression else-expression)

(define x 10)
(if (> x 5)
    (display "x is greater than 5")
    (display "x is not greater than 5"))

cond

• The cond expression is used for multiple conditions, similar to a series of if-else statements.
• Syntax:

  (cond
    (condition1 expression1)
    (condition2 expression2)
    ...
    (else default-expression))

(define x 3)
(cond
  ((= x 1) (display "x is one"))
  ((= x 2) (display "x is two"))
  ((= x 3) (display "x is three"))
  (else (display "x is something else")))

2.2 Iteration

do

• The do expression is used for looping, with an initialization part, a termination condition, and a body that is executed repeatedly.
• Syntax:

  (do ((var init step) ...)
      (exit-condition result-expression)
    body ...)

(do ((i 0 (+ i 1)))
    ((>= i 5) (display "Done"))
  (display i)
  (newline))

• This loop starts with i at 0 and increments it by 1 each time. The loop exits when i is 5 or greater.

let (used with recursion for iteration)

• Scheme often uses recursion for iteration, sometimes in combination with let for local variable binding.
• Syntax for named let (useful for creating loops):

  (let loop ((var1 init1) (var2 init2) ...)
    (if condition
        result
        (loop new-var1 new-var2 ...)))

(let loop ((i 0))
  (if (< i 5)
      (begin
        (display i)
        (newline)
        (loop (+ i 1)))))

• This example mimics a for loop, incrementing i from 0 to 4.

2.3 Logical Operators

• and: Evaluates expressions from left to right and returns the first #f (false) value, or the last value if all are true.

  (if (and (> 3 2) (< 5 10))
      (display "True")
      (display "False"))

• or: Evaluates expressions from left to right and returns the first non-#f (true) value, or #f if all are false.

  (if (or (> 3 5) (< 5 10))
      (display "True")
      (display "False"))

2.4 Sequencing

begin

• The begin expression is used to sequence multiple expressions, where the expressions are evaluated in order and the value of the last expression is returned.
• Syntax:

(begin
  expr1
  expr2
  ...
  exprN)

(begin
  (display "Hello, ")
  (display "World!")
  (newline))

These control structures are the building blocks for flow control in Scheme programs.

3. Data Structures

In Scheme, data structures are often built using the language’s fundamental constructs like lists, pairs (cons cells), vectors, strings, and records. Here’s an overview of common data structures in Scheme:

3.1 Pairs and Lists

Pairs

• Scheme uses pairs (or cons cells) as a basic building block. A pair consists of two elements.
• cons creates a pair.
• car and cdr access the first and second elements of a pair, respectively.

(define p (cons 1 2))  ; p is a pair containing 1 and 2
(car p)  ; returns 1
(cdr p)  ; returns 2

Lists

• A list is a sequence of elements, typically implemented as a chain of pairs.
• '() is the empty list.
• list creates a list of elements.

(define lst (list 1 2 3 4))  ; lst is a list containing 1, 2, 3, 4
(car lst)  ; returns 1
(cdr lst)  ; returns (2 3 4)

• Nested Lists: Lists can contain other lists.

(define nested-list (list 1 (list 2 3) 4))
; nested-list is (1 (2 3) 4)

Difference between list and pairs

In Scheme, both pairs and lists are fundamental data structures, but they serve different purposes and have distinct properties.

Pairs

• Definition: A pair is a basic data structure consisting of two elements, often called car and cdr. It’s created using the cons procedure.
• Syntax: (cons x y) creates a pair where x is the car and y is the cdr.
• Usage: Pairs are used to build more complex structures, including lists and trees. They are flexible and can hold any type of data.

Lists

• Definition: A list is a special case of pairs where the cdr of each pair is itself a list, ending in an empty list (). This recursive structure makes lists easy to process.
• Syntax: Lists are usually written using parentheses, e.g., (a b c d).
• Usage: Lists are used for ordered collections of items and are a common way to handle sequences of elements in Scheme.

Why Two?

• Flexibility: Pairs offer a low-level building block that can be used to create various data structures beyond lists, like pairs, trees, and more. Lists provide a higher-level abstraction for ordered sequences.
• Efficiency: Working directly with pairs can be more efficient for certain operations or data structures, while lists offer convenient syntax and operations for working with sequences of elements.
• Abstraction: Lists abstract away the details of the underlying pairs, making it easier to work with sequences of data in a more readable and structured way.

In essence, pairs provide the foundational building blocks, while lists offer a more specialized and user-friendly way to work with ordered collections.

3.2 Vectors

• Vectors are fixed-size, mutable arrays that allow constant-time access to elements.
• vector creates a vector.
• vector-ref accesses an element by index.
• vector-set! modifies an element.

(define vec (vector 1 2 3 4))  ; vec is a vector containing 1, 2, 3, 4
(vector-ref vec 0)  ; returns 1
(vector-set! vec 0 10)  ; sets the first element to 10

3.3 Strings

• Strings are sequences of characters.
• string creates a string.
• string-ref accesses a character by index.
• string-set! modifies a character.

(define str "Hello, World!")  ; str is a string
(string-ref str 0)  ; returns #\H

3.4 Records

• Records are structured data types with named fields.
• Scheme doesn’t have a standard built-in record type, but many implementations provide a way to define records (like define-record-type in Racket or SRFI-9).

(define-record-type person
  (make-person name age)
  person?
  (name person-name)
  (age person-age))

(define p (make-person "Alice" 30))
(person-name p)  ; returns "Alice"
(person-age p)  ; returns 30

3.5 Association Lists (Alists)

• An association list is a simple key-value store implemented as a list of pairs.
• assoc finds a key in an alist.

(define alist '((a . 1) (b . 2) (c . 3)))
(assoc 'b alist)  ; returns (b . 2)

3.6 Hash Table

• Hash tables are available in many Scheme implementations and provide efficient key-value storage.

Example using Racket:

(define ht (make-hash))
(hash-set! ht 'key1 "value1")
(hash-ref ht 'key1)  ; returns "value1"

3.7 Queues and Stacks

• Queues and stacks can be implemented using lists, pairs, or vectors.

Stack (LIFO)

(define stack '())
(define (push stack elem) (cons elem stack))
(define (pop stack) (cdr stack))

Queue (FIFO)

(define queue '())
(define (enqueue queue elem) (append queue (list elem)))
(define (dequeue queue) (cdr queue))

IMPORTANT

• Pairs and Lists: Basic building blocks for many other data structures.
• Vectors: Mutable arrays with constant-time access.
• Strings: Sequences of characters.
• Records: Structured data types with named fields.
• Association Lists: Simple key-value pairs stored in lists.
• Hash Tables: Efficient key-value stores (available in some Scheme implementations).
• Queues and Stacks: Easily implemented using lists or pairs.

These data structures cover most of the typical needs in Scheme programming, allowing for a wide range of algorithms and applications.

4. Functions

In Scheme, functions are first-class citizens, and defining a function is straightforward. Here’s a basic overview of how to write a function in Scheme:

4.1 Defining a Function

To define a function, you use the define keyword, followed by the function name, a list of parameters, and the function body.

Syntax:

(define (function-name parameter1 parameter2 ...)
  body-expressions)

4.2 Example 1: Simple Function

Here’s a simple function that adds two numbers:

(define (add a b)
  (+ a b))

• define: This keyword defines a new function.
• add: This is the name of the function.
• a, b: These are parameters for the function.
• (+ a b): This is the body of the function, which returns the sum of a and b.

Usage:

(add 3 4)  ; returns 7

4.3 Example 2: Recursive Function

Here’s a function that calculates the factorial of a number recursively:

(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))

• factorial: This function calculates the factorial of n.
• if: Checks if n is 0; if true, returns 1 (base case). Otherwise, it multiplies n by the factorial of n-1.

Usage:

(factorial 5)  ; returns 120

4.4 Example 3: Higher-Order Function

Functions in Scheme can take other functions as arguments or return functions. Here’s an example of a higher-order function that takes a function and applies it twice:

(define (apply-twice f x)
  (f (f x)))

• apply-twice: Takes a function f and an argument x, and applies f to x twice.

Usage:

(define (square x) (* x x))
(apply-twice square 2)  ; returns 16

4.5 Lambda Expressions

You can also define anonymous functions (lambda expressions) without naming them:

(define (add-square x y)
  ((lambda (a b) (+ (* a a) (* b b))) x y))

Here, the lambda function takes two arguments and returns the sum of their squares.

Usage:

(add-square 3 4)  ; returns 25

IMPORTANT

• define: Used to create named functions.
• lambda: Used to create anonymous functions.
• Function Body: Contains expressions that are evaluated when the function is called.
• Higher-Order Functions: Functions that take or return other functions.

These are the basic steps to define and use functions in Scheme.