Scheme

Main features

“Scheme … a lot of parentheses.”

Scheme dialect (which is in turn a language in the Lisp family) can be used in a functional style (but not purely functional)
Dynamically typed: the type of a value is determined at runtime, rather than at compile-time. In dynamic typing, you don’t have to specify the type of a variable when you declare it, and the type of the value stored in the variable can change dynamically during the execution of the program. (for example C++ is statically typed).
Functions are first class objects; in this example I can pass any binary function to the function like any other object:

(define (fold binop n e)
  (if (<= n e)
      e
      (binop (fold binop (- n 1) e) n)))

Scheme is lexical scoped like most programming languages (C, C++, and Java): the scope of a variable is determined by its location in the source code, more properly a variable always refers to its top-level environment. For example, if a variable is defined within a function, it will only be visible within that function and will not be accessible outside of it. This makes it easier to understand and manage the scope of variables in a program, because you can determine their visibility simply by looking at the source code. On the other hand, in dynamic scoping, the scope of a variable is determined by the order of function calls rather than its position in the source code.
Homoiconicity: it means that there is no distinction between code and data and that for example statements, like expressions, are nestable.: (+ 42 (if (< 1 0) 23 0)). The if statement is nested inside the + expression and is treated as just another expression with a value.

Variables

Booleans: #t, #f
Numbers: 42, 1.23e+33, 23/169, 12+4i
Characters: #a, #Z
Symbols: a-symbol, another-symbol?, indeed!
Vectors: #(1 2 3 4)
Strings: "this is a string"
Pair: (x . y) where the car is x and the cdr is y .
Lists: '(1 2 3) or (quote (1 2 3)) or even '(+ 1 2)'

Lambda Expressions

You can use the lambda special form to create anonymous functions. Any lambda expression can be evaluated in any moment using ().

(lambda (<parameters>) <body> )
 
; here an example where I use "immediately" the lambda
 
> (display ((lambda (x y) (- x y))  2 3))
-1

Pairs and lists

A pair is an immutable data structure that holds two values.

cdr of a list always returns a list while in a pair it returns a single value.
car first element of a list
cdr rest of a list
cons function can be used to create a new cons cell by specifying its car and cdr values as arguments.

; Creating cons cells using the cons function
(cons 1 2) ; => '(1 . 2)
(cons 1 '(1 2)) ; => '(1 1 2)
(cons '(1) '(2)) ; => '((1) . (2))
(cons '(1) 'a ) ; => '((1) . a)

The names cons, car, and cdr are historical conventions from the original Lisp interpreter of 1958.

Lists are unbounded, possibly heterogeneous collections (Racket lists can contain items of different types) of data.

list function can be used to create a new list by specifying its elements as arguments. Each argument will become an element in the resulting list (even if it is already a list itself).
length length of a list
append works as expected between two lists

; Creating lists using the list function
(list 1 2 3) ; => '(1 2 3)
(list '(1) '(2)) ; => '((1) (2))
(list 1) ;=> '(1)
 
> (append '(1 2) '(2 1))
'(1 2 2 1)
 
> (append '(1 2) '(1))
'(1 2 1)
 
> (append '(1 2) 1)
'(1 2 . 1)

Vectors

Vectors are more convenient and efficient than lists for some applications. Whereas accessing an arbitrary element in a list requires a linear traversal of the list up to the selected element, arbitrary vector elements are accessed in constant time. The length of a vector is the number of elements it contains. Vectors are indexed by exact nonnegative integers, and the index of the first element of any vector is 0. The highest valid index for a given vector is one less than its length.

As with lists, the elements of a vector can be of any type, and a single vector can hold more than one type of object.

A vector is written as a sequence of objects separated by whitespace, preceded by the prefix #( and followed by ). For example, a vector consisting of the elements a, b, and c would be written #(a b c).

It’s possible to use (vector-length vect_name) (vector-ref vect i)

(make-vector 5 1) ’#(1 1 1 1 1) (make-vector 5 ‘(1,2,3)) ’#((1 ,2 ,3) (1 ,2 ,3) (1 ,2 ,3) (1 ,2 ,3) (1 ,2 ,3))

Predicates

Predicates are procedures that returns boolean.

null? often used in loops to check if we are at the end of a list: (if (null? rest ) ;is rest = ()?
eq? tests if two objects (all objects except numbers) are the same
eqv? like eq? but also checks numbers
pair? is the predicate function.
equal? is #t iff its arguments are equal as ordered trees:

- > (equal? '(1 2 3) '(1 2 3)) 
#t
> (equal? '(1 2 3) '(1 2 4)) 
#f

Quote and Eval

Note that in the last example (quote ) is equivalent to ' . In Scheme data and code are basically the same thing. The “inverse” of (quote ) is (eval ). The eval procedure is used to evaluate a Scheme expression at runtime. It takes an expression as its argument and returns the result of evaluating that expression. For example:

(define x 5)
(eval '(+ x 3)) ; returns 8

Apply

Both eval and apply are involved in evaluating expressions in Scheme:

eval is used when you want to evaluate an individual expression dynamically at runtime.
apply is used when you want to apply a function or procedure to multiple arguments provided as elements in a list.

apply takes at least two arguments, the first of them being a procedure and the last a list. It will call the procedure with the following arguments, including those inside the list.

(apply + 1 -2 3 '(20 20))
; => 42

This is the same as (+ 1 -2 3 20 20) apply has that name because it allows you to “apply” a procedure to several arguments.

(define arguments '(10 50 100))
(apply + arguments)

Let

Let is not assignment, is creating a new variable. Let is used to bind variables. We say the variables are bound to the values by the let.

(let ( (<var> <expr>) (<var> <expr>) ... )
  <let body> 
)
 
//examples 
 
(let ((x 3) (y 2)) ;It's parallel 
  (+ x y)) ; 5 
)
 
(let* ((x 3) (y 2))  ; let* it's sequential
  (+ x y)) ; 5 
)

Variables created by let are local. To create top-level bindings there is define:

(define x 12)  
(define y #(1 2 3))

Begin

We can perform a block of procedural code using (begin ...):

(begin
	(op_1 ...)
	(op_2 ...)
	...
	(op_n ...)
)

Defining Functions

If you go to the trouble of defining a function, you often want to save it for later use. You accomplish this by binding the result of a lambda to a variable using define, just as you would with any other value.

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

Bang Procedures

In general, procedures with side effects have a trailing bang (!) character. For example set! is used for assignment.

(begin 
	(define x 23) 
	(set! x 42) 
	x)

is equals to 42.

Variable number of arguments

Variable argument functions can accept zero or more additional arguments
The additional arguments are captured as a list, which can be accessed and manipulated within the body of the procedure.
The rest parameter acts as a placeholder for all extra arguments provided during function invocation.
You can use various list manipulation functions like car, cdr, and others to work with the rest parameter and process its elements.

(define (my arg1 arg2 . args)
  (begin
    (display arg1) (newline)
    (display arg2) (newline)
    (display (car args)) (newline)
    (display (cdr args))
  )
)

(my 1 2 3 45 54 42)

Output:

Example

To define a function f with a variable number of arguments, such that when called like (f x1 x2 .. xn), it returns: (xn (xn-1 ( .. (x1 (xn xn-1 .. x1))..)), the function f can be defined using only fold operations for loops.

(define (f . L)
  (foldl 
    (lambda (x y)
      (list x y))
    (foldl cons '() L)
    L))

Macros

A macro is simply a text substitution of the body of the macro over the macro name. Scheme has a very powerful Turing-complete macro system (note that Scheme is cool because you can define recursive macros).

You don’t evaluate macros, you expand them.

Macros are of course expanded at compile-time and they are defined in this way:

(define-syntax <rule_name> 
  (syntax-rules () ;variant of the rule name
  ((_ <first_parameter_here> <second_param> ...)
  <body_pattern_match>
  )))

In functions parameters are passed by values while in macros the parameters are passed by name.

(define-syntax while
(syntax-rules () ; no other needed keywords
((_ condition body ...)    ; pattern 1  
(let loop () ; expansion of P
	(when condition
		(begin
		body ...
		(loop)))	
))))

Note that _ is just a shorthand notation and ... is a way to say that you can have multiple elements as body. An other example:

(define-syntax block-then
  (syntax-rules (where then <-)
    ((_ ((e1 ...) ...)
       then
       ((e2 ...) ...)
       where (v <- a b) ...)
     (begin 
       (let ((v a) ...)
         e1 ...))
       (let ((v b) ...)
         e2 ...)))))

Here’s an example usage of the block-then construct:

(block-then 
  ((displayln (+ x y))
   (displayln (* x y))
   (displayln (* z z)))
  then
  ((displayln (+ x y))
   (displayln (* z x)))
  where 
    (x <- 12 3)
    (y <- 8 7)
    (z <- 3 2))

This will output:

Hygiene of macros

A macro could be expanded into a piece of code that contains a label that has the same name of a variable used by the user somewhere else. This would lead to a name clash. But in Scheme this is not possible since Scheme macros are hygienic: this means that symbols used in their definitions are actually replaced with special symbols not used anywhere else in the program.

Loops

Generally loops can be achieve using let:

(let (( x 0))
	(let label () 
	(when (< x 10)
		(display x)
		(newline )
		(set! x (+ 1 x ))
(label)))) ; go-to label

(label) is used to jump back at the start of the iteration body. But also remember that a loops can always be expressed as recursive functions:

(let label (( x 0))
	(when ( < x 10)
		(display x)
		(newline)
(label (+ x 1)))) ; x++

Recursion

Recursion is a favored technique in functional programming. The most important concept of recursion is tail recursion. A tail recursive function is one that returns the result of the recursive call back without alteration.

(define (fold op n e)
  (fold-helper op n e n))
 
(define (fold-helper op n e acc)
  (if (<= n e)
      acc
      (fold-helper op (- n 1) e (op acc (- n 1)))))
 
>(display (fold + 10 1))
> 55
>(+ 10 9 8 7 6 5 4 3 2 1)

The difference between a tail recursive function and a not tail recursive one is that at each time the operation is done before the recursion call: in this way “there are just calls of functions on the stack and not pending operations”.

This is NOT tail recursive, since after the recursion it performs an multiplication:

(define (std-factorial n)
  (if (zero? n)
      1
      (* n (std-factorial (- n 1)))))

To turn this into a tail recursion function it’s necessary an accumulator. This is a typical pattern: use an helper function with an additional parameter which accumulates the answer (the accumulator) to convert a non-tail recursive function into a tail recursive one.

(define (factorial n)
  (acc-factorial n 1))
 
;; auxiliary function 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))))

Mapping and Folding

Some classical higher order functions are: map, foldl, foldr, filter:

((map (lambda (x) (+ 1 x)) ’(0 1 2)) ; => 
(1 2 3)
 
(foldl cons ’() ’(1 2 3)) ; => (3 2 1)
 
(foldr cons ’() ’(1 2 3)) ; => (1 2 3)
 
(filter (lambda (x) (> x 0)) ’(10 -11 0)) ; 
=> (10)

Implementation of folds:

(define (fold-left f i L) ;foldl is tail recursive
  (if (null? L)
      i
      (fold-left f (f (car L) i) (cdr L))))
 
(define (fold-right f i L) ;foldr is not tail recursive
  (if (null? L)
      i
      (f (car L) (fold-right f i (cdr L)) )))

Continuations

A continuation is a special kind of function that’s like a snapshot of the current state of a running program. Continuations let you jump back to an earlier point in the computation, circumventing the control flow of the program.

When you invoke a continuation, it sends you back to the point in the program where the bookmarked expression was evaluated.
The continuation takes one argument, which replaces the value of the bookmarked expression. Evaluation resumes from there.
The fun part is when you treat the continuation as an object like others and for example, save it in a variable: the variable contains “a fixed point” in the control flow of the program.
Continuations are also used as “glorified GOTO” since they permit to escape from cycles or bodies of procedures.
call/cc is the keyword for continuations and it always takes a lambda function as argument.

(+ 23 (call/cc (lambda (k) (+ 10 9)))) ;Risultato: 42
 
(+ 11 (call/cc (lambda (k) (+ 23 (k 31))))) ;Risultato: 42 poichè si esce subito da call/cc appena a k è stato assegnato un valore

This is a function which print until it finds a negative number, in this case the continuation is used as GOTO:

(define (print_until_neg l)
  (call/cc (lambda (exit) (for-each (lambda (x)
                (if (< x 0)
                    (exit)
                    (begin (display x) (newline))))l))))
 
>  (prova '(1 2 -3 4))
1
2

Example of an alternative implementation of call/cc, called store-cc: the continuation is called only once and it is implicit. To run the continuation, we can use the associated construct run-cc (which may take parameters).

(define *stored-cc* '())
(define-syntax store-cc
  (syntax-rules ()
    ((_ e ...)
     (call/cc (lambda (k)
                (set! *stored-cc* (cons k *stored-cc*))
                e ...)))))
(define (run-cc . v)
  (let ((k (car *stored-cc*)))
    (set! *stored-cc* (cdr *stored-cc*))
    `(apply k ,v))))

Closures

The interesting thing to do with call/cc and continuations is using it to have closures. A closure is basically (explained in “spaghettata mode”) a function with an environment, and we can write it using the ability of continuations to capture the state of its environment. Closures are a fundamental concept in functional programming and are used for a variety of purposes, including creating function factories (functions that return functions), iterators and generators. Let’s see a “generator” of Fibonacci sequence:

(define fibo-stack #f)
 
(define (fibonacci-gen)
  (let ((last-fib 0) (fib 1) (x #f))
    (call/cc (lambda (fibo)
               (set! fibo-stack fibo))) ;assignment
    (set! x  (+ last-fib fib))
    (set! last-fib fib)
    (set! fib x)
    x))

call/cc allows us to “save the stack” by capturing the current continuation and storing it in fibo-stack. This captured continuation can then be invoked later, allowing us to jump back to the saved state.

> (fibonacci-gen)
1
> (fibo-stack)
2
> (fibo-stack)
3
> (fibo-stack)
5
> (fibo-stack)
8
> (fibo-stack)
13
> (fibo-stack)
21

At the line of 'assignment comment I’m “saving” the computation exactly before the assignment of last-fib and fib . Every time that I call my continuation variable fibo-stack I obtain the next Fibonacci number (note that when I call fibo-stack I jump back inside the function and I perform the set! operations and, at the end, I’m giving back the variable x which contains the Fibonacci number).

In Scheme, the “closure as classes” approach refers to a programming technique where closures are used to simulate object-oriented programming and create class-like structures.

In traditional object-oriented programming languages, classes define objects with properties (attributes) and behaviors (methods). Objects of the same class share the same structure and behavior defined by their class. In Scheme, which is a functional programming language, there are no built-in constructs for defining classes or objects.

However, using closures in Scheme allows you to emulate some aspects of object-oriented programming. Closures are functions that capture variables from their surrounding environment. By combining closures with data structures like lists or records, you can create objects with associated state and behavior.

(define (test-closures)
  (define (greet)
    (display "Hello"))
  
  (define (farewell)
    (display "Goodbye"))
 
  (lambda (message)
    ((case message
       ((greet) greet)
       ((farewell) farewell)))))
 
(load "ex.rkt")
((test-closures) 'greet )
((test-closures) 'farewell )
 
(define t (test-closures))
(t 'greet)
(t 'farewell)

Explanation:

The test-closures function defines two inner functions, greet and farewell, which are used to display different messages.
It returns a lambda function that takes a message as an argument.
Inside the lambda function, there is a case statement that matches the given message with either 'greet or 'farewell.
If it matches 'greet, it calls the greet function. If it matches 'farewell, it calls the farewell function.
The code then loads this file using (load "ex.rkt").
It demonstrates how to call these functions by directly invoking them with (test-closures) followed by either 'greet or 'farewell.
Alternatively, you can assign (test-closures) to a variable t, and then call t with either 'greet or 'farewell.

Structs

New types can be defined with struct similar to C, but with some differences. Related procedures such as the constructor and a predicate to check the type of the new object are automatically created:

(struct node
  (left right))
 
> (define a (node 1 2))

typeof: (<struct>? <instance>) to understand if a particular instance <instance> is of type <struct_name>
getter: (<struct>-<field> <instance>)

Structs can inherit:

(struct node node-base ;inheritance
  (left right))

setter: (set-<struct>-<field>! <instance> <value>) to set a value for a mutable field.

(struct leaf 
  ((value #:mutable)) ) ;making a mutable field 
 
> (define a (leaf 23))
 
> (display a)
#<leaf>
 
> (leaf-value a)
23
 
> (set-leaf-value! a 42) ;SETTER 
> (leaf-value a)
42

Setup to code

Install Linux package Racket
Omit the lang declaration in the source file
Launch from CLI Racket
Use (load <file>)

> racket
Welcome to Racket 7.6.
> (load "hello.rkt")
'hello-world
> (hello)
'hello-world

blog.martino.im

Explorer

00.Scheme