Re: functional programming

"William James" <[e-mail]> writes:

> Pascal J. Bourguignon wrote:
>
>> So to make a list, first, the basic building block, the cons cell:
>> 
>> (class Cons
>>  (attr_accessor :car)
>>  (attr_accessor :cdr)
>>  (def initialize(car,cdr)
>>     (@car = car)
>>     (@cdr = cdr)
>>   end)
>> end)
>> 
>> 
>> Let's wrap this object into a functional abstraction layer:
>> 
>> (def cons(car,cdr)
>>  (Cons . new(car,cdr))
>> end)
>> 
>> (def car(x)
>>  (x . car)
>> end)
>> 
>> (def cdr(x)
>>  (x . cdr)
>> end)
>> 
>> (def null(x)
>>  (x . nil?)
>> end)
>> 
>> irb(main):040:0> (cons 1,2)
>> #<Cons:0x7fdfb53eb808 @cdr=2, @car=1>
>> irb(main):042:0> (car (cons 1,2))
>> 1
>> irb(main):043:0> (cdr (cons 1,2))
>> 2
>> irb(main):044:0> (null (cons 1,2))
>> false
>> irb(main):045:0> (null (car (cons 1,nil)))
>> false
>> irb(main):046:0> (null (cdr (cons 1,nil)))
>> true
>> 
>> 
>> 
>> Then you can build a list over these cons cells:
>> 
>> (def list(*args)
>>   (i = (args . length))
>>   (r = nil)
>>   (loop {
>>      (if (i == 0)
>>         (break)
>>       else
>>         (i = (i - 1))
>>         (r = (cons (args [ i ]),r))
>>      end)
>>   })
>>  r
>> end) 
>> 
>> irb(main):127:0> (list 1,2,3)
>> #<Cons:0x7fdfb53b81d8 @cdr=#<Cons:0x7fdfb53b8200
>> @cdr=#<Cons:0x7fdfb53b8228 @cdr=nil, @car=3>, @car=2>, @car=1>
>> 
>> 
>> Let's print them pretty:
>> 
>> (def printelements(cons)
>>   (if (Cons === cons)
>>       (if (Cons === (car cons))
>>          (printlist (car cons))
>>         else
>>          (print (car cons))
>>       end)
>>       (if (Cons === (cdr cons))
>>          (print " ")
>>          (printelements (cdr cons))
>>        elsif (not (null (cdr cons)))
>>          (print " . ")
>>          (print (cdr cons))
>>       end)
>>   else
>>      (print cons)
>>   end)
>> end)
>> 
>> (def printlist(cons)
>>  (print "(")
>>  (printelements cons)
>>  (print ")")
>>  cons
>> end)
>> 
>> (def terpri()
>>   (print "\n")
>> end)
>> 
>> 
>> irb(main):263:0> (begin
>>                    (terpri)
>>                    (printlist (list 1,2,3))
>>                    (terpri)
>>                  end)
>> 
>> (1 2 3)
>> nil
>> 
>> You can also add some higher level abstractions:
>> 
>> (def first(list)
>>   (car list)
>> end)
>> 
>> (def rest(list)
>>   (cdr list)
>> end)
>> 
>> (def endp(list)
>>   (if (Cons === list)
>>       nil
>>    elsif (null list)
>>       true
>>    else
>>       (error ("Expected a list instead of the atom " + (list . to_s)))
>>    end)
>> end)
>> 
>> 
>> 
>> Once you've got this list abstraction, you can build functions such
>> as reverse:
>> 
>> (def revappend(list,tail)
>>  (if (null list)
>>      tail
>>   else
>>      (revappend (cdr list),(cons (car list),tail))
>>   end)
>> end)
>> 
>> (def reverse(list)
>>  (revappend list,nil)
>> end)
>> 
>> 
>> 
>> irb(main):267:0> (begin
>>                    (printlist (reverse (list 1,2,3)))
>>                    (terpri)
>>                  end)
>> (3 2 1)
>> nil
>> 
>> 
>> 
>> Now we also need the function abstraction.  In ruby functions have to
>> be in modules, and always qualified by the module name.  This is not
>> pretty, so we will allow any method to be treated as a function, but 
>> we will ignore it's recipient object, always passing self.
>> 
>> # For methods, the first function argument is the recipient of the
>> # message:
>> 
>> (def method(designator,arity=(-1)) 
>>    # Important: the given arity must include the recipient object,
>> but not the recipient class:     # (method :==,2) .call(42,42)   vs.
>> 42.==(42)    (if (arity == -1)
>>       # This is the default, bugged behavior: 
>>       (Proc . new {| x , *args | (x . send(designator , *args))})
>>     elsif (arity == 0)
>>       (raise (Exception.exception("An instance method must have an
>> arity>=1, not 0.")))     else
>>       (arity = (arity - 1))
>>       (args = (((arity == 0)? "" : " , ") + (((1 .. arity) . map { |
>> i | ("a" + i.to_s) }) . join(" , "))))       (eval("(Proc . new { |
>> x" + args + " | " +             "( x . send( :" + (designator . to_s)
>> + args + " ))})"))     end)
>>  end)
>> 
>> 
>> # for functions, the recipient of the message is always 'self', all
>> # arguments are passed as arguments.
>> 
>> (def function(designator,arity=(-1)) 
>>   # Important: the given arity must include the recipient object, but
>> not the recipient class:    # (function "SOME_MODULE.someFunction",1)
>> .call(42)   vs. SOME_MODULE.someFunction(42)   # (function
>> :someFunction             ,2) .call(42)   vs. self.someFunction(42)
>> or someFunction(42)   (if (String === designator)      mod , met =
>> (designator . split("."))      (if (arity == -1)
>>         # This is the default, bugged behavior:
>>         (Proc . new {| *args | ((eval mod) . send((met . to_sym) ,
>> *args))})       else
>>         (args = (((1 .. arity) . map { | i | ("a" + i.to_s) }) .
>> join(" , ")))         (sep = " ")
>>         (if (0 < arity)
>>            (sep = " , ")
>>          end)
>>         (eval("(Proc . new { | " + args + " | " +
>>               "( " + mod  + " . send( :" + met + sep + args + "
>> ))})"))       end)
>>    else
>>      (if (arity == -1)
>>         # This is the default, bugged behavior:
>>         (Proc . new {| x , *args | (x . send(designator , *args))})
>>       elsif (arity == 0)
>>         (eval("(Proc . new {" +
>>               "(" + (designator . to_s) + " )})"))
>>       else
>>         (args = (((1 .. arity) . map { | i | ("a" + i.to_s) }) .
>> join(" , ")))         (eval("(Proc . new { | " + args + " | " +
>>               "(" + (designator . to_s) + " " + args + " )})"))
>>       end)
>>    end)
>> end)
>> 
>> 
>> (def funcall(fun,*args)
>>   (fun . call(*args))
>> end)
>> 
>> 
>> 
>> irb(main):370:0> (funcall (method :+,2),3,4)
>> (funcall (method :+,2),3,4)
>> 7
>> 
>> irb(main):478:0> (begin 
>>                    (terpri)
>>                    (printlist (funcall (function :reverse,1),(list
>> 1,2,3)))                    (terpri)
>>                  end)
>> 
>> (3 2 1)
>> nil
>
>
> You have certainly proved that everything is 10 times as hard
> as it should be when you use Commune Lisp!
>
> Ruby:
>
> [1,2,3].reverse
>     ==>[3, 2, 1]
>
> [1,2,3].send :reverse
>     ==>[3, 2, 1]
>
>
>
>> 
>> 
>> 
>> Now that you have first class functions, you can start to implement
>> higher level functions:
>> 
>> (def mapcar (fun,list)
>>  (if (endp list)
>>     nil
>>   else
>>    (cons (funcall fun,(first list)),(mapcar fun,(rest list)))
>>   end)
>> end)
>> 
>> 
>> irb(main):271:0> (begin
>>                    (printlist (mapcar (lambda {|x| (x + 1)}),(list
>> 1,2,3)))                    (terpri)
>>                  end)
>> 
>> (2 3 4)
>> nil
>> 
>
>
> Ruby:
>
> [1,2,3].map{|x| x + 1}
>     ==>[2, 3, 4]
>
>
> or:
>
> augment = proc{|x| x + 1}
>     ==>#<Proc:0x0282c2cc@(irb):11>
> [1,2,3].map &augment
>     ==>[2, 3, 4]
>
>> 
>> 
>> So at least, now you can find the smallest element of a list:
>> 
>> This function implements an accumulator pattern: we pass the partial
>> result along with the parameters.  We process the list item by item
>> and when its finished we return the result we've accumulated so far:
>> 
>> (def smallestElement(list,minimum)
>>  (if (endp list)
>>      minimum
>>   elsif (minimum < (first list))
>>      (smallestElement (rest list),minimum)
>>   else
>>      (smallestElement (rest list),(first list))
>>   end)
>> end)
>> 
>> (def smallest(list)
>>  (smallestElement (rest list),(first list))
>> end)
>> 
>> 
>> 
>> irb(main):422:0> 
>> (begin 
>>    (terpri)
>>    (printlist (mapcar (function :smallest,1),(list (list 1),
>>                                                    (list 1,1,1,1),
>>                                                    (list 1,2,3,4),
>>                                                    (list 4,3,2,1),
>>                                                    (list
>> 1,2,3,4,3,2,1),
>> (list 4,3,2,1,2,3,4))))    (terpri)
>> end)
>> 
>> (1 1 1 1 1 1)
>> nil
>
>
> Ruby:

No, you're wrong.  All the above code IS RUBY!

> [[1],[1,1,1,1],[1,2,3,4],[4,3,2,1],[1,2,3,4,3,2,1],[4,3,2,1,2,3,4]].
> map{|a| a.min}
>     ==>[1, 1, 1, 1, 1, 1]
>
> Yes, COBOL Lisp is an ancient, cumbersome, and clunky language.
> Ruby is to it as a transistor is to a vacuum tube.

Wrong, the above code wasn't Lisp, it was Matzacred Lisp, aka Ruby.

Ruby is to a vacuum tube what debris of glass and tungsten filaments
are.

-- 
__Pascal Bourguignon__