Asp Forum - PG's On Lisp - generators of recursive functions

Malice

1/15/2016 3:43:00 PM

I am reading PG's On Lisp, and I am currently reading about functions that return recursive functions. For example, see Figure 5.5 on page 69 available here: http://ep.yimg.com/ty/cdn/paulgraham/...

Sorry for no source code, but I don't know whether I would violate any copyright laws. I want to stay on safe side.

Anyway; After a bit of thinking and plying with the functions, I understand both how they work, and I can use them to generate some of the functions I need; however, I often don't think of the functions the way that the e.g. #'lrec promotes - I think about what function needs to do, and then I try to figure out how to do it(often I have an algorithm in my head before I start writing). While I see clearly that you can save some code, I would argue that these constructs are less readable.

First of all, they require you to know their structure. Therefore, there's no gain in readability. Actually, I would say that it works the other way - I find #'lrec/#'ttrav definitions less readable, as I have to stop and think about what they would do. While the same applies for defining functions, the general shape and layout of program allows me to see through the whole algorithm and understand it, where in #'lrec/#'ttrav I only get a function and need to figure out myself what it does, since I can't inspect the code.. However, this might be the case just because I've never used lrec/ttrav.

Secondly - I've never heard of them until now. While this does not prove anything, this might suggest that these types of functions are not popular, and hence they could yield the same difficulties for other first timers as for me.

I am just not sure that I see that these functions are worth using. I am curious whether the functions like this are useful or (relatively) popular (in some areas)? Or is it more like proof of concept?

5 Answers

Madhu

1/19/2016 5:36:00 AM

* Malice <ed14529e-1eb3-44fb-9d2f-36497336aac5@googlegroups.com> :
Wrote on Fri, 15 Jan 2016 07:42:33 -0800 (PST):

| Anyway; After a bit of thinking and plying with the functions, I
| understand both how they work, and I can use them to generate some of
| the functions I need; however, I often don't think of the functions
| the way that the e.g. #'lrec promotes - I think about what function
| needs to do, and then I try to figure out how to do it(often I have an
| algorithm in my head before I start writing). While I see clearly that
| you can save some code, I would argue that these constructs are less
| readable.
|
| First of all, they require you to know their structure. Therefore,
| there's no gain in readability. Actually, I would say that it works
| the other way - I find #'lrec/#'ttrav definitions less readable, as I
| have to stop and think about what they would do. While the same
| applies for defining functions, the general shape and layout of
| program allows me to see through the whole algorithm and understand
| it, where in #'lrec/#'ttrav I only get a function and need to figure
| out myself what it does, since I can't inspect the code. However, this
| might be the case just because I've never used lrec/ttrav.
|
| Secondly - I've never heard of them until now. While this does not
| prove anything, this might suggest that these types of functions are
| not popular, and hence they could yield the same difficulties for
| other first timers as for me.
|
| I am just not sure that I see that these functions are worth using. I
| am curious whether the functions like this are useful or (relatively)
| popular (in some areas)? Or is it more like proof of concept?

Welcome to the emporer's new clothes. These bogus unreadable constructs
are immensely useful in perpetrating the goals of the empire of the
antichrist, and targetted at the creating "PG blub" demographic of
consumers, while pandering to their suspect sensibilities through a
self-blinding solipsistic narrative, eventually aimed to cause lasting
damage the programming landscape in the name of "LISP" when they receive
their payoffs. Sadly you can find these have are now defiling GNU elisp
too. ---Madhu

Paul Rubin

1/19/2016 6:22:00 AM

Malice <gwmaniak@gmail.com> writes:
> I am just not sure that I see that these functions are worth using. I
> am curious whether the functions like this are useful or (relatively)
> popular (in some areas)? Or is it more like proof of concept?

I've never seen that done in Lisp, especially in that non-tail-recursive
way. But if I understand what PG is getting at, lrec is what in
functional programming would be called a fold, and it's useful. The
Lisp "reduce" function is closely related.

The Scheme version is described here:

http://srfi.schemers.org/srfi-1/srfi-1...

Malice

1/19/2016 3:25:00 PM

> I've never seen that done in Lisp, especially in that non-tail-recursive
> way. But if I understand what PG is getting at, lrec is what in
> functional programming would be called a fold, and it's useful. The
> Lisp "reduce" function is closely related.

I know of reduce, first time I have seen fold. Thanks for the link.

However, fold is a bit different - consider this code snippet:

(fold cons '() '(1 2 3 4 5) ; -> (5 4 3 2 1)

This shows us that fold is indeed a function which applies the first argument(which is a function0 in some way to last argument(the list).

Now consider the #'lrec alternative in Common Lisp:

(lrec (lambda (x f) (append (funcall f) (mklist x))) nil)
(funcall * '(1 2 3 4 5)); -> (5 4 3 2 1)

We had to split it up into two steps. We could use #'lrec to build something that would work *kind of* like fold:

(defun almost-fold (fun base lst)
(funcall (lrec (lambda (x f) (funcall fun (funcall f) x)) base) lst))

Now let's test it:

(almost-fold (lambda (x y) (append x (mklist y))) nil '(1 2 3)) ;->(3 2 1)
(almost-fold #'+ 0 '(1 2 3 4)) ;->10

However, it lacks much functionality that fold offers, and it is actually harder to make it useful. We could, however, make something like fold with ease:

(defun almost-fold-2 (kons knil lis)
(if (null lis)
knil
(almost-fold-2 kons (funcall kons (car lis) knil) (cdr lis))))

Let's test it:
(almost-fold #'cons nil '(1 2 3));-> (3 2 1)
(almost-fold #'+ 0 '(1 2 3));->6

I actually think that this is much simpler. I can read the code, and since it's an easy pattern, I can actually see through it, whereas in #'lrec I have an additional thing that I need to process - the new lambda, which has a (funcall f) thing, which might be confusing.

As for fold: please note that you can achieve the same with #'reduce:

(reduce #'+ '(1 2 3));->6
(reduce #'+ '(1 2 3) :initial-value 5);->11 | equal to (fold + 5 '(1 2 3))
(reduce (lambda (x y) (append (mklist y) x)) '(1 2 3) :initial-value nil);->(3 2 1)

Since we already have a wealth of operators that allow us to perform such actions, and common use cases of #'lrec aren't convincing me, I'd say that this function isn't very useful.

William James

1/20/2016 3:30:00 AM

Paul Rubin wrote:

> Malice <gwmaniak@gmail.com> writes:
> > I am just not sure that I see that these functions are worth using. I
> > am curious whether the functions like this are useful or (relatively)
> > popular (in some areas)? Or is it more like proof of concept?
>
> I've never seen that done in Lisp, especially in that non-tail-recursive
> way. But if I understand what PG is getting at, lrec is what in
> functional programming would be called a fold, and it's useful. The
> Lisp "reduce" function is closely related.

Using "lrec", length of a list would be:

(funcall (lrec (lambda (x f) (1+ (funcall f))) 0) '(2 3 4 5))
===> 4

and sum of list items would be:

(funcall (lrec (lambda (x f) (+ x (funcall f))) 0) '(2 3 4 5))
===> 14

It seems simpler to use reduce:

;; Sum of items.
CL-USER(30): (reduce (lambda (sum x) (+ sum x)) '(2 3 4 5) :initial-value 0)
14
CL-USER(31): (reduce (lambda (sum x) (+ sum x)) '() :initial-value 0)
0

In MatzLisp (Ruby):

[2,3,4].reduce(0){|len,_| len+1}
===> 3

[2,3,4].reduce(0){|sum,x| sum+x}
===>9
[].reduce(0){|sum,x| sum+x}
===>0

William James

1/20/2016 5:13:00 AM

Madhu wrote:

> These bogus unreadable constructs
> are immensely useful in perpetrating the goals of the empire of the
> antichrist

See? Worship of CL (COBOL-Like) and LOOP is a religion.

--
In Stockholm ... 20 Muslim men ... cornered one of the [11-year-old] girls in a
grotto in the bathhouse and gang-raped her. The police refused to press any
charges. www.liveleak.com/view?i=807_1369627137

comp.lang.lisp

PG's On Lisp - generators of recursive functions

Malice

Madhu

Paul Rubin

Malice

William James

William James

x Login to ForumsZone