Thinking Functional

[nklein]

I can really see and feel the benefits of pure functional programming. I don't yet have my head around it enough to use it everywhere I want to though. Maybe I am off track early somewhere.

As a toy example, pretend I am implementing a chat server. Somewhere, there will be a list of who is currently logged in. Say, for sake of argument that this list should be kept in alphabetical order by nickname. When someone logs in, the function thing to do is create a new list with this person in it. Yet, I still have to (setf ...) something if I am going to have the list the next time I need it. {Technically, if I could count on optimized tail recursion, I could fake it... but...}.

The situation gets worse if someone can update their nickname in real time. Now, I need to construct a whole new user struct to hold the new name and a whole new list that includes this new struct and excludes the old one. The situation is worse if I am tracking attendance in chat rooms within the system or buddy lists or what-have-you.

The problem, I guess is where to draw the line. I have to mutate something or copy whole hierarchies on every change.

Help me think.

[findinglisp]

I can really see and feel the benefits of pure functional programming. I don't yet have my head around it enough to use it everywhere I want to though. Maybe I am off track early somewhere.

I think the first place you got off-track was with the words "pure functional programming." There is no programming that is pure functional. Pure functional programs don't do anything useful because they cannot interact with their environment to even print the result of the program. Languages like Haskell are more strictly functional and shuffle off the impure parts of the program to monads, but Haskell without monads is pretty boring.

As a toy example, pretend I am implementing a chat server. Somewhere, there will be a list of who is currently logged in. Say, for sake of argument that this list should be kept in alphabetical order by nickname. When someone logs in, the function thing to do is create a new list with this person in it. Yet, I still have to (setf ...) something if I am going to have the list the next time I need it. {Technically, if I could count on optimized tail recursion, I could fake it... but...}.

So, a couple things. A chat server is all about I/O. As such, it's about the most non-functional sort of program that you could imagine. That doesn't mean that you can't use functional programming to implement a lot of it, but don't wrap yourself around the axle trying to analyze a non-functional program with functional programming techniques. That said, you either do the setf or you use tail recursion. For instance, Erlang would use tail recursion here to "jump to the top of the loop" with a new copy of the lists. With Common Lisp, you're sort of stuck because it doesn't guarantee tail recursion. You basically have to do the setf at the very top level of the data structure.

The situation gets worse if someone can update their nickname in real time. Now, I need to construct a whole new user struct to hold the new name and a whole new list that includes this new struct and excludes the old one. The situation is worse if I am tracking attendance in chat rooms within the system or buddy lists or what-have-you.

The problem, I guess is where to draw the line. I have to mutate something or copy whole hierarchies on every change.

Help me think.

Yes, when you program functionally, you have to copy. There are Lisp functions that will manage that all for you, however (things like SUBSTITUTE or MAPCAR). The nice thing is that Lisp is not purely functional. If you find that you're running into huge efficiency problems, then pick and choose where to break out of the functional paradigm and apply some mutation for efficiency's sake. The choice is yours.

[donkey]

The nice thing is that Lisp is not purely functional. If you find that you're running into huge efficiency problems, then pick and choose where to break out of the functional paradigm and apply some mutation for efficiency's sake. The choice is yours.

As a quick personal note -- this is what I believe to be one of Lisp's most important strenghts. Some parts of a program are best expessed in a functional manner -- some are not, so the most efficient method is simply to use the right one when required.

[findinglisp]

The nice thing is that Lisp is not purely functional. If you find that you're running into huge efficiency problems, then pick and choose where to break out of the functional paradigm and apply some mutation for efficiency's sake. The choice is yours.

As a quick personal note -- this is what I believe to be one of Lisp's most important strenghts. Some parts of a program are best expessed in a functional manner -- some are not, so the most efficient method is simply to use the right one when required.

Yup, I agree wholeheartedly. Also, because you can create DSLs using macros, it's relatively easy to incorporate other programming styles, too. For instance, there are several Prolog-like inference engines that you can use to do logic programming. While I think it would be a PITA to write a whole program in pure Prolog, I can absolutely see the value of being able to express a part of a larger program in a logic paradigm. While you could write a Prolog-like library for another language to do something similar, the fact that Lisp so naturally incorporates the new paradigm as a peer rather than just an interpreter is quite remarkable.

[Ramarren]

I have to mutate something or copy whole hierarchies on every change.

Google for functional data structures. The most basic case is keeping everything in binary trees, then you need to copy only log(n) elements on every change. Essentially only the tree nodes directly above the modified elements have to be recreated to point to the new version of data structure.

There are some CL libraries for this... see: Funds or FSet .

[Sacha]

Somewhere, there will be a list of who is currently logged in. Say, for sake of argument that this list should be kept in alphabetical order by nickname.

For this, I canibalized (ported) the dataset structure from haskell. It is nothing more than a binary tree. So I would have code like this :

Code: Select all

(setf users (dataset-insert new-user users))


As this is a persistent datastructure, the old version still exists (neat for undo), and could be use in an other thread at the same time(say to write the state to a file or something).

The situation gets worse if someone can update their nickname in real time.

You would need some kind of a function or macro that will do the copying for you. here is the one i use :

Code: Select all

(defmacro with-update ((type-name instance) &body updates)
  (let ((rectype (find-class type-name)))
    (unless rectype
      (error "Class ~a was not found." type-name))
    (let ((instance-gensym (gensym "INSTANCE-")))
      (let ((struct-slots (structure:structure-class-slot-names rectype)))
        (loop for (name . nil) in updates
              unless (member name struct-slots)
              do (error (error "Slot ~a not a member of class ~a." name type-name)))
        `(let ((,instance-gensym ,instance))
           (,(find-symbol (concatenate 'string "MAKE-" (symbol-name type-name)) (symbol-package type-name))
            ,@(loop for slot in struct-slots
                    for assoc = (assoc slot updates)
                    if assoc collect (second assoc)
                    else collect `(,(slot-name type-name slot) ,instance-gensym))))))))


It is somewhat cumbersome to use and works under the assumtion that the make-record function doesn't require keyword arguments (it's all positional here). Also that's for lispworks only.
an example usage :

Code: Select all

(defun dataset-delete (value dataset)
  (let-rec-slots ((dataset dataset (compare-func key-func root-node)))
    (with-update (dataset dataset)
      (root-node (%delete value compare-func key-func root-node)))))


Then you have the problem of updating something deep in the your "object hierachy".
I was asking that question on the haskell mailing list a few months ago. And they were kind enough to introduce me to the concept of "lifting".

It works something like this (dataset-lift "Sacha" users (lambda (user) (with-update (user user) (password "bigsecret"))))
dataset-lift will find user "Sacha" then updates it's password (so it creates a new user) and then creates the log2 nodes up to the top and returns a new dataset, thus hiding the details of the operations.

or deeper : (lift 'users config (dataset-lift "Sacha" users (lambda (user) (with-update (user user) (name "Pedro")))))
lift does the same as dataset-lift for the simpler case of updating a slot in a record.

Hope this helps

Sacha

[nklein]

Thank you all for the information. I suppose I did have my head on straight, I just
wasn't seeing a way around the log_n rebuilds of a tree or without a top-level setf
somewhere (unless I use the Erlang-ish tail-recursion trick).