CS374: Programming Language Principles - Functional Programming with Scheme

Activity Goals

The goals of this activity are:
  1. To explore the functional programming paradigm using Scheme

Supplemental Reading

Feel free to visit these resources for supplemental background reading material.

The Activity

Directions

Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity, and compare with your group to prepare for our whole-class discussion. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.

Model 1: Declarative Languages - Functional Programming with Scheme

?
1
2
3
4
5
6
7
8
9
(define L (list 'a 'b 'c))
(car L)
(cdr L)
 
(define x (+ 3 2))
(+ x 5)
 
(define add +)
(add 3 2)

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(define square
  (lambda(n)
    (* n n)
  )
)
 
(define pow
  (lambda(n k)
    (if (= k 0)
      1
      (* n (pow n (- k 1)))
    )
  )
)
       
(square (pow 5 3))

?
1
2
3
4
5
6
7
8
9
10
(define sumlist
  (lambda(L)
    (if (null? (cdr L))
      (car L)
      (+ (car L) (sumlist (cdr L)))
    )   
  ) 
)
 
(sumlist (list 1 2 3))

?
1
2
3
4
5
6
7
8
9
10
11
12
13
(define largest
  (lambda(L)
    (if (null? (cdr L))
      (car L)
      (if (>= (car L) (largest (cdr L)))
        (car L)
        (largest (cdr L))
      )
    ) 
  )
)
 
(largest (list 1 2 4 3))

Questions

  1. What is a statement in Scheme?
  2. What shared variables exist in this program?
  3. What are some potential advantages of Functional Programming as a paradigm?
  4. How might you improve upon the implementation of the largest function?

Model 2: The Scheme Programming Language

?
1
2
3
4
5
(define y
  (lambda(m x b)
    (+ (* x m) b)))
     
(y 5 6 7)

?
1
2
3
4
5
6
7
8
9
10
11
(define v0 3)
(define t 5)
(define a 9.80665)
 
(define square
  (lambda(n)
    (* n n)))
     
(+ (* v0 t) (* 0.5 (* a (* t t))))
 
(+ (* v0 t) (* 0.5 (* a (square t))))

?
1
2
3
4
5
6
7
8
(define czr
  (lambda(l)
    (if (null? (cdr l))
      (car l)
      (czr (cdr l))
    )
  )
)

?
1
2
3
4
5
6
7
8
9
10
(define plusminus
  (lambda(a b)
    (
      (lambda (x y) (list (+ x y) (- x y)))
      a b
    )
  )
)
 
(plusminus 6 2)

?
1
2
3
4
5
6
(define L1 '(1 2 3))
(define L2 '(4 5 6))
(define L3 (map - L1 L2))
(apply + L3)
((lambda (x) (* x x)) 5)
(map (lambda (x) (* x x)) '(1 2 3 4 5))

?
1
2
3
4
5
6
7
8
9
10
11
12
(define (make-counter)
  (let ((count 0)) ; This is the environment the closure captures
    (lambda ()     ; The lambda function forms the closure
      (set! count (+ count 1)) ; Modifies the captured variable 'count'
      count)))
 
(define counter1 (make-counter))
(define counter2 (make-counter))
 
(counter1) ; Returns 1
(counter1) ; Returns 2
(counter2) ; Returns 1

Questions

  1. How are function parameters handled in Scheme? Are they passed by value or by reference?
  2. What is a function in Scheme? How is it represented?
  3. What does czr do in your own words?
  4. Write a function to count the number of items in a list using a recursive call and a base case, using czr as a guide to traversing a list.
  5. Diagram the binding of the values in the call to plusminus to the anonymous lambda function.
  6. What is the result of the map/apply sequence? What would happen if map were applied to only a single list?
  7. In your own words, define tail recursion. Do you see instances of tail recursion in these examples? Draw a call stack for one of these examples.
  8. Compare and constrast closures and objects.
  9. Using the pair? directive, which returns #t if the parameter is a nonempty list, add a check to one of these list recursion examples to ensure that null is returned if an empty list is passed.
  10. Write a function that accepts a list and an operator as parameters, such as addition. Apply that operator to the whole list recursively; for example, if the operator is the addition operator, return the sum of the list. If it is the multiplication operator, return the product of all items in the list.

Model 3: Functional Programming in Modern Languages

?
1
2
3
4
5
6
7
8
# Define the sumlist function using a lambda and recursion
sumlist = lambda L: L[0] if len(L) == 1 else L[0] + sumlist(L[1:])
 
# Test the function with a list
result = sumlist([1, 2, 3])
 
# Print the result
print(result)

Questions

  1. What does this code do? How does it do it?
  2. What are the advantages of programming this way?

Model 4: Functional Programming in Modern Languages

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from concurrent.futures import ThreadPoolExecutor, as_completed
from functools import reduce
import operator
 
# A pure function that does not depend on or modify shared state
def factorial(n):
    return reduce(operator.mul, range(1, n + 1), 1)
 
# Another pure function that computes the sum of a list of numbers
def sum_of_factorials(numbers):
    return sum(map(factorial, numbers))
 
def main():
    # List of numbers to compute the factorial of
    numbers = [5, 7, 10, 12, 15]
 
    # Using ThreadPoolExecutor for concurrent execution
    with ThreadPoolExecutor(max_workers=4) as executor:
        # Submit tasks to the thread pool
        futures = {executor.submit(factorial, n): n for n in numbers}
 
        results = {}
        for future in as_completed(futures):
            n = futures[future]
            try:
                result = future.result()
                results[n] = result
            except Exception as exc:
                print(f"Factorial of {n} generated an exception: {exc}")
 
    # Compute the sum of all factorials
    total_sum = sum_of_factorials(numbers)
 
    print("Factorials:", results)
    print("Sum of factorials:", total_sum)
 
if __name__ == "__main__":
    main()

Questions

  1. Time the following program for various numbers of threads and values for numbers. What do you notice?

Installing Scheme

You can git clone https://github.com/BillJr99/scheme-interpreter.git which will give you a scheme.py that you can run via python scheme.py <your scheme file, or do one of the following:

  • Cygwin (Windows): Install guile from the Cygwin installer
  • Ubuntu (Linux): sudo apt install mit-scheme
  • Mac: brew install mit-scheme, provided that you have installed homebrew

Submission

I encourage you to submit your answers to the questions (and ask your own questions!) using the Class Activity Questions discussion board. You may also respond to questions or comments made by others, or ask follow-up questions there. Answer any reflective prompt questions in the Reflective Journal section of your OneNote Classroom personal section. You can find the link to the class notebook on the syllabus.