N00b notes on CHICKEN scheme

README.md

The following is a collection of notes generated while learning CHICKEN Scheme.

Syntax

Function definition using defun:

(define (my-name arg1 arg2)
  (body...))

Functions that return true (#t) or false (#f) are called predicates:

(zero? 0) ; #t

Some predicates are eq?, equal?, zero? and number?.

To control the flow of evaluation, conditionals, use cond.

(cond
  (predicate body)  ; clause 1
  (predicate body)) ; clause 2

cond evaluates the predicate of the first clause, if it's truthy (everything but #f is considered true), it evaluates body and ignores other clauses. Otherwise, it moves onto the second clause and repeats. It's good to always catch the last statement with #t.

Factorial, could be written as follows:

(cond ((zero? n) 1)
      (#t (* n (fact (- n 1))))))

cond returns the value of the evaluated block. A shortcut is using else

(cond ((zero? n) 1)
      (else (* n (fact (- n 1))))))

Yet another way is using if

;(if condition consequent alternative)
(if #t 1 2) ; => 1

Loops and recursion

A program that ‘‘does not do anything’’after calling itself is called a tail recursive program. Fact2 is a tail-recursive program, while the original fact program is not, because it applies * to the value returned by the recursive call:

(* n (fact (- n 1)))
; ^^^--- this is done after the return of fact

Wrapping a tail-recursive function is common.

(define (fact n)
  (fact2 n 1))

There's a shortcut for that:

(define (fact n)
  (letrec
    ((fact2
      (lambda (n r)
        (cond ((zero? n) r)
              (#t (fact2 (- n 1) (* n r)))))))
    (fact2 n 1)))

Manual Reduction

Lambda calculus, is basically, a process of substitution. Just reduce the values until you get a result: Eg:

(fact 3)
-> (cond ((zero? 3) 1) (#t (* 3 (fact (- 3 1)))))
-> (* 3 (fact (- 3 1)))
-> (* 3 (fact 2))
-> (* 3 (* 2 (fact 1)))
-> (* 3 (* 2 (* 1 (fact 0))))
-> (* 3 (* 2 (* 1 1)))
-> (* 3 (* 2 1))
-> (* 3 2)
=> 6

At some point the reduction normally reachesa point where the expression cannot be reduced any further. Such an expression is said to be in its normal form.