Re: FP using CL

On 2021-05-01 11:00, Duke Normandin wrote:
> 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.

The good news is that pretty much "nobody" does that. Common Lisp is a
multi-paradigm language.

A useful program has effects, like input and output.

In Common Lisp, effects are worked into a program without any functional
ceremony using regular imperative programming.

> 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.

In just about any imperative program, you can find sub-calculations
which can be worked in a functional style.

For instance, if you take two character strings and catenate them
together to produce a new string, without changing the original objects,
that's functional. You may have done that in already in imperative
programming. Inquiring about some property of an object without changing
its state is also functional.

In some Lisp programs, or program modules, that sort of calculation is
emphasized a great deal.

If you've done any Unix shell scripting, a lot of it is functional,
except for the part that we clobber a file at the end of the pipe:

    sed 's/a/b/' < this | grep that | sort > that

The evaluation of an arithmetic formula is functional. Where it becomes
imperative is when we stick the result into a variable or array or
whatever.

> I can learn the CL/Scheme/et al syntax, but it's the "Thinking in FP"
> that's killing me. :)

The following is not everything there is to "thinking in FP", but a big
part.

What is a computation? It's a transformation from some input to an
output according to some well-defined calculation steps.  A complex
transformation is made of simpler transformations.

Under FP, we break down the calculation into a sequence of data
transformations, much like what the mathematical description of the
process would be. We represent these transformations as functions, and
then chain them together.

Also, it is useful to keep in mind that the binding of a new variable
isn't mutation/assignment; it is also functional. The obvious example is
that functions have named parameters, and when they are called, those
parameters bind to argument values, and become newly instantiated
variables. If that weren't functional, functional programming would not
be possible (or would all have to be "point free": more on that point
later).

We can bind variables using *let* (which was originally a syntactic
sugar for lambda). Thus something like this is quite functional:

    (let ((x '(1 2 3))
          (y '(4 5 6)))
      (append x y))

which produces (1 2 3 4 5 6).

This principle helps in the writing of pure functions, because it allows
us to give meaningful names to subexpressions, and also to refer to
repeated terms by convenient names.

In contrast, the following is not functional, since we are mutating
variables:

    (let (x y z)
      (setq x '(1 2 3))
      (setq y '(4 5 6))
      (setq z (append x y)))

However, that brings me to a point: local variables (at least ones which
are not captured by an escaping closure) do not live past their
enclosing scope.

We can define a function that provides a calculation as a pure
transformation of its inputs. Yet, inside that function we can mutate
storage locations in order to implement that calculation.

You will find that Lisp functions in the wild often take such liberties.

One of the main engineering motivations behind using functional
programming is that mutations cause bugs that are hard to track down.
However local mutations which are confined to a small scope are easy to
reason about, and even formally verify.

If the specification of a function is functional, and by tests of its
external behavior, it appears functional (doesn't mutate anything that
the caller could possibly care about), then the function is in fact
function and can be used in functional programs.

This fact helps you: you can start using functional approaches in your
code without beating yourself up to make the internals of every function
being meticulously functional, and avoiding iteration in favor of
recursion and all that jazz.

It's a lot more important to specify (if possible) a functional API or
building block than for internals to be pure.

Here is a pure function for reversing a list, which
is internally impure:

    (defun reverse-list (input)
      (let (stack) ;; uninitialized lexicals are nil in CL!
        (dolist (i input stack)
           (push i stack))))

This walks the input list, pushing every element onto the local stack.
When dolist is finished the stack expression in (i input stack)
specifies the return value. I.e. loop i over the input, and when done,
return stack.

These pushes are imperative. The (push i stack) form has the same
meaning as (setq stack (cons i stack)): using the functional expression
(cons i stack) create a stack which has one more item than the previous
stack.  Then using setq, store the new stack into the stack variable.

The dolist macro itself may or may not be functional.  ANSI Common Lisp
says:

   It is implementation-dependent whether dolist establishes
   a new binding of var on each iteration or whether it
   establishes a binding for var once at the beginning and
   then assigns it on any subsequent iterations.

We have to assume that whenever we use dolist, it is just stepping the
same variable; i.e. that it is quite likely an imperative construct.

Anyway, when the function has terminated and produced a value, the
caller cannot tell that there existed a stack variable and a variable
called i which was stepped over a list. Those variables are gone. All it
knows is that the list which it passed into reverse-list has not been
modified, and that now also has a new list which is the reverse of that
list.

I mentioned "point-free" and promised to have more on it later. This is
something you may come across when you read about functional
programming. Point-free style means achieving a transformation without
mentioning any intermediate variables, including function arguments.
"Point" comes from a terminology which refers to the arguments of a
function as points. E.g. a binary function is "two point" and so on.

I gave a shell pipeline example earlier; and that happens to be point
free at least throughout the interior of the pipeline. The pipeline
connects a file called "this" to an output file called "that" and those
are named points. The pipeline itself is point-free: each pipeline stage
implicitly takes input from the previous stage.

Nested function invocations are point-free in the sense that variables
are not mentioned: For instance

    (* 2 (cos (sin x)))

is point free, except for the mention of *x*.

The shell pipeline style represents an alternative version of point-free
application, which is generally called "concatinative". The names of the
operations are written side by side and are understood to be implicitly
chained together.

Some functional languages emphasize concatinative point-free
programming. In Lisp, it can be simulated with macros.

(There are concatinative languages that are not strictly functional,
like Forth, which uses a stack for passing and returning values rather
than named parameters. The stack can be misused, causing underflows, or
stray values.)

Concatinative point-free code can make a functional program look
"scary". Expressions in the program just look like sentences of strange
words.

Also, unlike Lisp, some functional languages feature implicit partial
evaluation. A function call might be written like f x y, which is
ambiguous: it can be regarded as f being applied to arguments x y,
or as (f x) y: f partially applied to x to yield a function of one 
parameter,
which is then applied to y. These languages are statically typed,
therefore an expression like map f 3 s might be resolved as follows.
map is a two-point function which requires a function as its
first argument. Suppose f is a two-point function which takes two
integers and returns an integer. The only way a correct argument can
be formed for map is if f 3 is treated as a partial application.
That denotes an integer -> integer function, and s becomes the second
argument to map: the sequence to map over.  When reading this kind
of code, you have to be aware of the types and arities of the functions,
and possibly at the same time of unfamiliar infix operators that have
unfamiliar associativity and precedence.

In Lisp, partial application is simulated using explicit lambdas, for
which syntactic sugar can be developed using macros.

Thus you will not come across Lisp code that is concatinative or that
uses partial evaluation, except if it's doing that by means of macros,
which announce themselves by their explicit calls.



_______________________________________________
clisp-list mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/clisp-list