[clisp-list] Fwd: FP using CL

[Pascal B. <pj...@in...>]

-------- Message transféré --------
Subject: Re: [clisp-list] FP using CL
To: Duke Normandin <duk...@gm...>
References: <202...@gm...>
From: Pascal Bourguignon <pj...@in...>
Message-ID: <917...@in...>
Date: Sun, 2 May 2021 02:03:18 +0200
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0) 
Gecko/20100101 Thunderbird/78.10.0
MIME-Version: 1.0
In-Reply-To: <202...@gm...>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: fr
Content-Transfer-Encoding: 8bit

Le 01/05/2021 à 20:00, Duke Normandin a écrit :
> Noob here!
> 
> All of my previous non-pro, hobbyist hacking experience has been imperative.
> I want to give FP a shot using CL.
> Problem: I don't seem to grok how to start the process of creating a CL program using **just** functions.
> 
> I mean, I can flowchart an imperative-styled program w/o too much difficulty.
> Need to grok how to do same in FP-style with CL.
> 
> I can learn the CL/Scheme/et al syntax, but it's the "Thinking in FP" that's killing me. :)
> 
> Any leads to relevant online resource(s)? TIA ...

I would advise to start with Bachus's fundational paper.

https://dl.acm.org/doi/pdf/10.1145/359576.359579
https://www.youtube.com/watch?v=FxcT4vK01-w
https://www.youtube.com/watch?v=OxuPZXXiwKk


Now, you don't have to use *just* functions, but indeed the idea is to 
build functions from other functions using function operators (such as 
the function composition operator for example), instead of definiting 
the functions detailing each operation element by element.

A function takes elements from a source set, and return elements in an 
image set.  The usual programming will give an expression of the image 
element "in function of" the element of the source set.


Let's define an affine function a:

a : ℤ → ℤ
     x ↦ 2x+1

or in lisp:

     (defun a (x)
       (+ (* 2 x) 1))


But if we define the function 2* (or double):

2* : ℤ → ℤ
      x ↦ 2x

and the function 1+ (or successor):

1+ : ℤ → ℤ
      x ↦ x+1

Then instead of defining a giving an expression element by element:

a : ℤ → ℤ
     x ↦ 2x+1

we can write a functional expression:

a = 1+ ∘ 2*

Using the composition operation between two functions f∘g(x) = f(g(x))

So:  a(x) = 1+ ∘ 2* (x) = 1+(2*(x)) = 1+(2*x) = 1+2*x = 2*x+1

Note that Common Lisp already has a function 1+ (and 1- for x-1).
We only need to define double and compose:

     (defun compose (f g) (lambda (x) (funcall f (funcall g x))))

     (defun times (n) (lambda (x) (* x n)))

     (defmacro define (fname fexpression)
        `(progn
           (declaim (ftype (function (t) t) ,fname))
           (setf (symbol-function ',fname) ,fexpression)))

     (define double (times 2))
     (define a (compose (function 1+) (function double)))

     (mapcar (function a) (iota 10))
     --> (1 3 5 7 9 11 13 15 17 19)

Note how I used mapcar, and not a procedural dotimes, so I get the
results for all the elements of the input set (iota 10) at once,
instead of computing and getting the result element by element:

     (dotimes (i 10)
       (print (a i)))

     1
     3
     5
     7
     9
     11
     13
     15
     17
     19

Now the question is to collect a library of functional operators that
will help us writing such functional expressions easily and
expressively.  And not all functions in the CL library are conductive
to easy building functional expressions from them.  So we may also
have to rewrite some library functions.


So here is another example; we could write:

     (defun minus (n) (lambda (x) (- x n)))
     (defun partial (f x)
       (lambda (y) (funcall f x y)))

     (mapcar
      (compose (partial (function reduce) (function +))
               (lambda (x)
                 (mapcar (lambda (f) (funcall f x))
                         (list (function identity)
                               (compose (minus 10) (function a))))))
      (iota 10))
     --> (-9 -6 -3 0 3 6 9 12 15 18)

     (list (function identity)
           (compose (minus 10) (function a)))

     --> (#<Compiled-function identity #x30000012D5FF>
         #<ccl:compiled-lexical-closure (:internal compose) #x30200275E99F>)

builds a list of 2 functions, identity = x ↦ x
and a-10 = x ↦ (2*x)+1-10 = 2*x-9


           (lambda (x)
             (mapcar (lambda (f) (funcall f x))
                     (list (function identity)
                           (compose (minus 10) (function a)))))


is a function that takes an argument and applies it to each function
of the list, returning a list of results:

          ((lambda (x)
             (mapcar (lambda (f) (funcall f x))
                     (list (function identity)
                           (compose (minus 10) (function a)))))
           5)
         --> (5 1)

partial is a function that takes a function and an argument, and
returns a function that takes a second argument and call the first
function with the two arguments.  It's a partial application of the
function.

So:  (funcall (partial f x) y)  == (funcall f x y)

Therefore:     (partial (function reduce) (function +))
returns a function that sums a list of numbers:

     (funcall (partial (function reduce) (function +)) (list 1 2 3 100))
     --> 106

So we can use it to compose it with the previous lambda which returns
a list of 2 numbers:

     (funcall (compose (partial (function reduce) (function +))
                       (lambda (x)
                         (mapcar (lambda (f) (funcall f x))
                                 (list (function identity)
                                       (compose (minus 10) (function a))))))
              5)
     --> 6

and use the composition in a map of the set of integers from 0 to 9:

     (mapcar
      (compose (partial (function reduce) (function +))
               (lambda (x)
                 (mapcar (lambda (f) (funcall f x))
                         (list (function identity)
                               (compose (minus 10) (function a))))))
      (iota 10))
     --> (-9 -6 -3 0 3 6 9 12 15 18)


-- 
__Pascal Bourguignon__

-- 
__Pascal Bourguignon__