Who's proud of cute lil Gavino?

[Gavino himself]

$ cat defs
(defun average (x y)
(/ (+ x y) 2.0))


[5]> (load "defs")
;; Loading file /home/xbbnkfd/lisp/defs ...
;; Loaded file /home/xbbnkfd/lisp/defs
#P"/home/xbbnkfd/lisp/defs"
[6]> (average 45 3)
24.0

[tar...@google.com]

And the next level:

(defun average (&rest values)
(assert values)
(/ (reduce #'+ values) (length values)))

[Robert L.]

On 9/26/2017, tar...@google.com wrote:

> And the next level:
>
> (defun average (&rest values)
> (assert values)
> (/ (reduce #'+ values) (length values)))

(define (average . numbers)
(/ (apply + numbers) (length numbers)))

--
Black Panther Quanell X ... blamed the 11-year-old girl for being raped by 28
black males. http://archive.org/details/DavidDuke_videos/ (Trayvon Martin)
What I would most desire would be the separation of the white and black
races. --- A. Lincoln, July 17, 1858

[Gavino himself]

`-__|__-' 8 8 8 8 8
| 8 o 8 8 o 8 8
------+------ ooooo 8oooooo ooo8ooo ooooo 8

Welcome to GNU CLISP 2.49+ (2010-07-17) <http://clisp.org/>

Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Copyright (c) Bruno Haible, Sam Steingold 1999-2000
Copyright (c) Sam Steingold, Bruno Haible 2001-2010

Type :h and hit Enter for context help.

[1]> (defun avg (&rest values)
(assert values)
(/ (reduce #+ values) (length values)))

*** - READ from #<INPUT CONCATENATED-STREAM #<IO TERMINAL-STREAM>>: an object
cannot start with #\)
The following restarts are available:
ABORT :R1 Abort main loop

[Gavino himself]

mommys iny boy? robert dont make me bust you up

also bring back some working code

[9]> (define (average . numbers)

(/ (apply + numbers) (length numbers)))

*** - EVAL: undefined function DEFINE

The following restarts are available:

USE-VALUE :R1 Input a value to be used instead of (FDEFINITION 'DEFINE).
RETRY :R2 Retry
STORE-VALUE :R3 Input a new value for (FDEFINITION 'DEFINE).
ABORT :R4 Abort main loop

[Jim Newton]

(defun average (numbers)
(if numbers
(apply #'/ (reduce (lambda (acc new &aux (old (car acc)) (count (cadr acc)))
(declare (type cons acc)
(type number new old)
(type unsigned-byte count))
(list (+ old new) (1+ count)))
numbers
:initial-value '(0 0)))
0))

This one has no problem if the list is longer than the maximum arglength,
and only iterates once through the list. It calls #'/ with exactly two arguments.

[Gavino himself]

Why is this so complex?
Just add the numbers with + and divide by the number of args.
Wtf
Are you spergs trying to be funny? Its not working. This is why you are poor.

[Pascal J. Bourguignon]

It's rather a bad implementation, bceause you are allocating twice the
number of cons cells. So even if you would have gained anything from
avoiding duplicate memory accesses to the list (gain only possible if
your list is gigantic, way beyond the size of the caches), you would
kill it with that allocation and the corresponding garbage collector
activity.

(defun average (numbers)
(loop
:for n :in numbers
:sum n :into sum
:count 1 :into count
:finally (return (if (zerop count)
nil ; there's no reason to return a specific number!
(/ sum count)))))

this will scan the list only once, but will not allocate any other
temporary memory than the variables sum and count. It should have a
much better cache and garbage collector behavior on gigantic lists.

--
__Pascal J. Bourguignon
http://www.informatimago.com

[tar...@google.com]

On Tuesday, October 10, 2017 at 8:48:30 AM UTC-7, informatimago wrote:
> Jim Newton <jimka...@gmail.com> writes:
>
> > (defun average (numbers)
> > (if numbers
> > (apply #'/ (reduce (lambda (acc new &aux (old (car acc)) (count (cadr acc)))
> > (declare (type cons acc)
> > (type number new old)
> > (type unsigned-byte count))
> > (list (+ old new) (1+ count)))
> > numbers
> > :initial-value '(0 0)))
> > 0))
> >
> > This one has no problem if the list is longer than the maximum arglength,
> > and only iterates once through the list. It calls #'/ with exactly two arguments.
>
> It's rather a bad implementation, bceause you are allocating twice the
> number of cons cells. So even if you would have gained anything from
> avoiding duplicate memory accesses to the list (gain only possible if
> your list is gigantic, way beyond the size of the caches), you would
> kill it with that allocation and the corresponding garbage collector
> activity.

[Loop snipped]

One could avoid the extra consing by using a free variable in the
lambda used in the REDUCE call:

(defun average (&rest numbers)
(if numbers
(let ((count 0))
(/ (reduce (lambda (acc new) (incf count) (+ acc new))
numbers :initial-value 0)
count))
0))

[tar...@google.com]

The issue is a subtle one of taking the average of a list of numbers that is
bigger than the implementation limit on the number of arguments passed to
a function. So with a large list, you may not be able to just apply the
function to the arguments.

The CL spec only guarantees that this value is at least 50. Most implementations have larger limits, though.*

See: http://www.lispworks.com/documentation/HyperSpec/Body/v_call_a.htm#call-arguments-limit

SBCL's is 4.6 x 10^18 in its 64-bit implementation.
CLisp 2.49 is 4096.
CCL 1.11 is 65536.

[Gavino himself]

shouldnt recursion be used?

[Kaz Kylheku]

On 2017-10-10, Gavino himself <jack...@gmail.com> wrote:
> [1]> (defun avg (&rest values)
> (assert values)
> (/ (reduce #+ values) (length values)))

----------

This is the "hash plus" syntax' you wanted #'+ ("hash quote") followed
by the + symbol.

Hash plus implements conditional reading.

Example: the following will read expr if the :CLISP or :SBCL keyword
symbols are in the *FEATURES* list.

#+(clisp sbcl) expr

If neither :CLISP nor :SBCL is in the *FEATURES* list, then the whole
thing effectively goes away. However, expr is still scanned and
has to be well-formed syntax.

What you have "#+ values)" which checks whether :VALUES in in
*FEATURES*. It almost certainly is not. Your expr is ) which is not
valid syntax; when CLISP's reader tries to skip over it it diagnoses
a dangling ) character.

[Gavino himself]

[6]> (defun average (&rest values)
(assert values)

(/ (reduce #'+ values) (length values)))

AVERAGE
[7]> (average 4 88 3)
95/3
[8]> (average 4 88 3.0)
31.666666
[9]> (average 4 99)
103/2
[10]> (average 4 99.0)
51.5


WOW IT WORKS
HOLY FUK
Lisp works
why isnt lisp used instead of all the shit like java and diet java?
oracle is cancer!!

[Robert Munyer]

"Gavino himself" wrote:

> shouldnt recursion be used?

As a learning exercise, yes. When not learning, usually you
wouldn't use recursion for something this simple. You'd use a
higher-level construct like LOOP or DO, and then you wouldn't
need to know or care about whether that construct was using
recursion internally.

You could implement this function with a 4-line DO loop,
without doing any mutation or heap allocation. The DO loop
could have one use of each of ENDP, FIRST, REST, +, 1+ and /.

--
-- Robert Munyer code below generates e-mail address

(format nil "~(~{~a~^ ~}~)" (reverse `(com dot munyer at ,(* 175811 53922))))

[Barry Margolin]

In article <orng2d$1rh5$1...@gioia.aioe.org>,

Robert Munyer <rob...@not-for-mail.invalid> wrote:

> "Gavino himself" wrote:
>
> > shouldnt recursion be used?
>
> As a learning exercise, yes. When not learning, usually you
> wouldn't use recursion for something this simple.

Indeed, in practice one rarely uses recursion for any of the problems
where recursion is used in pedagogy. E.g. the most common example of
simple recursion is factorial, which is more easily done with a loop.

In real programming, recursion is mainly only used for processing
hierarchical data structures. But at the point in a programming class
where recursion is likely to be taught, the students might not be ready
for this. So simpler examples are used, even though they're not
realistic.

--
Barry Margolin, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

[Kaz Kylheku]

On 2017-10-12, Barry Margolin <bar...@alum.mit.edu> wrote:
> In real programming, recursion is mainly only used for processing
> hierarchical data structures. But at the point in a programming class
> where recursion is likely to be taught, the students might not be ready
> for this. So simpler examples are used, even though they're not
> realistic.

Bingo.

Okay, class, today we are going to learn ... recursion.

Everyone, take out your AST representing the regular expression
that we parsed yesterday; today we are going to traverse it ...
recursively ... to to build an NFA graph. How exciting!

[Ben Bacarisse]

I did it using graphics. The students had a simple tool-kit for making
drawings and after learning (a) how to package operations into
functions, (b) how to parameterise these (i.e. some abstraction), we
looked at drawing functions that call themselves. Lots of fun.

--
Ben.

[Stefan Monnier]

> In real programming, recursion is mainly only used for processing
> hierarchical data structures.

That depends on the language, tho. In Haskell/ML it's very common to
use recursion to write the moral equivalent of a while loop (and the
compiler is expected to generate code which doesn't consume stack space
in those cases).


Stefan

[Pascal J. Bourguignon]

Kaz Kylheku <398-81...@kylheku.com> writes:

> On 2017-10-12, Barry Margolin <bar...@alum.mit.edu> wrote:
>> In real programming, recursion is mainly only used for processing
>> hierarchical data structures.

Well only if those structures are not too deep. Usually, you have to
"manage the stack" yourself when you work on graphs.

>> But at the point in a programming class
>> where recursion is likely to be taught, the students might not be ready
>> for this. So simpler examples are used, even though they're not
>> realistic.
>
> Bingo.
>
> Okay, class, today we are going to learn ... recursion.

And the first thing you learn after recursion, is how to remove it!

This should tell you something.

Well I guess, if your brains are not fried after learning recursion, so
you may notice the derecursivation lessons.

[Chris Vine]

Not to mention The Language Which Shall Not Be Named in comp.lang.lisp -
scheme (oops[1]).

Chris

[1] Don't tell him, Pike. (Sorry, you have to come from the UK and be
over 40 to understand this last reference.)

[Paul Rubin]

Chris Vine <chris@cvine--nospam--.freeserve.co.uk> writes:
> Not to mention The Language Which Shall Not Be Named in comp.lang.lisp -

There's also Erlang.

[Gavino himself]

Paul graham would use recursion a lot.....despite what others would say....From some stuff I seem to remember reading....

[Gavino himself]

I heard erlang is haky....is it nice?
zotonic and chicago boss web frmeworks looked interesting...not sure what to make of mnesia.....or if its all bsd license or what.

[tar...@google.com]

On Monday, October 16, 2017 at 1:48:00 PM UTC-7, Gavino himself wrote:
>
> Paul graham would use recursion a lot.....despite what others would say....
> From some stuff I seem to remember reading....

Recursion is not in itself a problem.
And certainly not on small problems.

There are potential inefficiencies in recursive calls and the possibility of
exhausting stack space (which is typically much smaller than heap space).

For certain classes of recursion called tail-recursion, a compiler can arrange
to eliminate the need to use additional stack, and effectively turn recursive
calls into loops. But to get this benefit, you must write a properly tail
recursive function. (Paul Graham certainly knows how to do this).

In addition, for CommonLisp, you must be using an implementation that supports
tail-recursion optimization. And in general, you must have the compiler
optimization settings for safety, speed and debugging set so that the compiler
will perform this optimization. There is no guarantee in the CL standard that
this will be done. (There is a requirement in Scheme). In practice, all of
the major CL implementations will perform the optimization for some settings
of the compiler directives.

But I would say at this stage of your language usage, it is not the most
important thing to be worried about.

[Bigos]

On 13/10/17 11:36, Chris Vine wrote:

> [1] Don't tell him, Pike. (Sorry, you have to come from the UK and be
> over 40 to understand this last reference.)
>

We want more of that. Counting certain Italians was my favourite.

[Barry Margolin]

In article <b1267431-2983-4fed...@googlegroups.com>,

tar...@google.com wrote:

> On Monday, October 16, 2017 at 1:48:00 PM UTC-7, Gavino himself wrote:
> >
> > Paul graham would use recursion a lot.....despite what others would say....
> > From some stuff I seem to remember reading....
>
> Recursion is not in itself a problem.
> And certainly not on small problems.
>
> There are potential inefficiencies in recursive calls and the possibility of
> exhausting stack space (which is typically much smaller than heap space).
>
> For certain classes of recursion called tail-recursion, a compiler can arrange
> to eliminate the need to use additional stack, and effectively turn recursive
> calls into loops. But to get this benefit, you must write a properly tail
> recursive function. (Paul Graham certainly knows how to do this).

However, for many algorithms the tail-recursive form is not the most
intuitive. E.g. factorial is one of the most common examples of
recursion, but the usual code is not tail-recursive. It's not too hard
to convert it to tail-recursive form, but doing the same with fibonacci
(probably the second most common recursion example -- the mathematical
definition is inherently recursive) is less trivial.

It's true that any iteration or recursion can be recast as tail
recursion, but the Y-combinator is not something most programmers are
actually familiar with (I've been programming for 40 years, and all I
know about it is its name).

[Gavino himself]

I guess the better question would be: why dont they just teach loop? and avoid recusion if loop is as good or better and less dangerous?

[Gavino himself]

ok explain the ref, its killing me
its not pike from star trek....

[Gavino himself]

I thought y-combinator was a startup incubator?

[Gavino himself]

On Tuesday, September 26, 2017 at 3:09:51 PM UTC-4, Gavino himself wrote:
> $ cat defs
> (defun average (x y)
> (/ (+ x y) 2.0))
>
>
> [5]> (load "defs")
> ;; Loading file /home/xbbnkfd/lisp/defs ...
> ;; Loaded file /home/xbbnkfd/lisp/defs
> #P"/home/xbbnkfd/lisp/defs"
> [6]> (average 45 3)
> 24.0

Moving into ch4 of gentle intro.
skipped advanced topics of ch3
did I stub my toe by doing that?
I just read about cond....cool....eveything seesm so blindingly easy in lisp while you are doing stuff in lisp.
The shell however in unix lets me move file around easily.....and gather data from os about whats going on...not sure how to do such in lisp.
Is werc.cat-v.org simplicity more powerful than real lisp web framework like lisp on lines which will probly take me a lot of time to learn ?

[Madhu]

* Barry Margolin <barmar-176ACA....@reader.eternal-september.org> :
Wrote on Tue, 17 Oct 2017 11:29:49 -0400:

> It's true that any iteration or recursion can be recast as tail
> recursion, but the Y-combinator is not something most programmers are
> actually familiar with (I've been programming for 40 years, and all I
> know about it is its name).

I think have are used nowadays days in obfuscating javascript.

1. There was a classic example posted on cll, as an answer to a homework
problem, which illustrated its use.

From: Paul Foley <myc...@actrix.gen.nz>
Subject: Re: which articles are sold?
Date: 02 Nov 2001 03:10:52 +1300
Message-ID: <m2n126k...@mycroft.actrix.gen.nz>

2. My own programming introduction to fixed point combinators was in C,
via the "Reflections on trusting trust" paper, which introduced a quine,
a program when compiled and run, printed its own source.

The fixed point combinator is a hof that computes the fixed point of
other higher order functions. The Y-combinator is the simplest fixed
point combinator of lambda calculus. In function notation
Y (f) = p, where p = f (p)
The fixed point of f is another function p such that f(p) = p.

For the single argument case in CL:

(defun Y (func)
((lambda (x) (funcall x x))
(lambda (y)
(funcall func
(lambda (arg)
(funcall (funcall y y) arg))))))

This helps obfuscate the factorial function in groundbreaking ways:

We can write a function whose fixed point is the factorial function,

(lambda (f)
(lambda (x)
(if (not (plusp x))
1
(* x (funcall f (1- x))))))

And we can use the Y combinator to compute the fixed point: Calling Y on
this above function gives us a factorial function

(Y (lambda (f)
(lambda (x)
(if (not (plusp x))
1
(* x (funcall f (1- x)))))))

I admit It doesn't look that great in lisp, to appreciate it you
probably need a language with lazy evaluation and supportive syntax.

[Gavino himself]

I don't understand what you wrote.
starting with

[tar...@google.com]

On Tuesday, October 17, 2017 at 12:01:19 PM UTC-7, Gavino himself wrote:
> > It's true that any iteration or recursion can be recast as tail
> > recursion, but the Y-combinator is not something most programmers are
> > actually familiar with (I've been programming for 40 years, and all I
> > know about it is its name).
>

> I thought y-combinator was a startup incubator?

It is. But it is named after the Y Combinator from lambda calculus.
https://en.wikipedia.org/wiki/Fixed-point_combinator

[tar...@google.com]

On Tuesday, October 17, 2017 at 8:29:55 AM UTC-7, Barry Margolin wrote:

> It's true that any iteration or recursion can be recast as tail
> recursion, but the Y-combinator is not something most programmers are
> actually familiar with (I've been programming for 40 years, and all I
> know about it is its name).

I'll have to disagree that any recursion can be recast as tail recursion.

<Dusting off my rusty memory of 35 year old theory classes>

The set of recursively computable functions is strictly greater than the set of
interatively computable functions. The most common example of a recursive
function that cannot be done iteratively is a tree-walk. This is inherently
a recursive algorithm and cannot be done in a loop without effectively
simulating the recursion by manually managing a stack.

Now, tail recursive and iterative functions are interchangeable.

[Gavino himself]

does this mean I should never use recursioun and should only use loop?

[Barry Margolin]

In article <735e54ae-4e05-47a0...@googlegroups.com>,

Indeed, converting some recursive algorithms to iterative will often
involve relocating some of the housekeeping data from the automatic
stack to heap data that's managed by the algorithm.

This can still be valuable because stack space is often much more
limited than heap space.

> Now, tail recursive and iterative functions are interchangeable.

Of course, Lambda: the Ultimate Goto.

[josep...@gmail.com]

On Tuesday, October 17, 2017 at 3:01:19 PM UTC-4, Gavino himself wrote:
> I thought y-combinator was a startup incubator?

The startup incubator, which was started by Paul Graham (of "On Lisp" and "ANSI Common Lisp" fame) is named for well-known function called the Y-Combinator or fixed-point combinator; it is a nod to Graham's long career using and promoting Lisp, especially Common Lisp. They were referring to the function rather than the organization.

A fixed point combinator is a function that can be used to determines the fixed points in the domain and co-domain of another function. The form of the fixed-point combinator in lambda calculus is called the Y-combinator, and was originally developed by logician Haskell Curry in the 1950s (I think, it may have been earlier).

A fixed point is a domain value which, when the function is applied to it, maps to the same value in the co-domain. Thus, is we apply fixed-point combinator Y to function f, then for all x, (Y f x) -> x.

For example, for the sine function, zero is a fixed point; sin 0 -> 0.

A related function is the Identity function is a special case of a fixed point function which maps to the input value x to itself for all x. Applying Y

https://en.wikipedia.org/wiki/Fixed_point_(mathematics)

https://en.wikipedia.org/wiki/Fixed-point_combinator#Fixed_point_combinators_in_lambda_calculus

While any programming language which allows higher-order functions (functions either take other functions as operand, or return a function as a result), the Y-combinator is primarily associated with the Lisp languages, and with pure-functional languages such as Haskell and ML.

It is of interest for a number of both theoretical and practical concerns, but it is notoriously hard to understand. While it usually seen as quite important among Lispers, even many experienced Lisp devs (such as Barry above) have had trouble with it, or have simply never felt the need for it.

The Y-combinator has a number of applications in compiler and interpreter optimization, database engine implementation, and symbolic algebra, and according to Wikipedia, is used in Google's PageRank system as well. Apparently it is used also in code obfuscation, if Madhu is correct; given that it allows one to identify invariants in the code in order to re-arrange them, this makes sense.

Since you seem to be unfamiliar with it, I should also explain code obfuscation. is a method used for automatically distorting source code without changing it's compiled result, so that the source can be distributed but cannot be readily reverse engineered. The potential value and/or ethics of this practice are left as an exercise for the reader.

https://en.wikipedia.org/wiki/Obfuscation_(software)

I hope this makes these topics a bit less confusing, but history says this is probably not going to be the case.

(OK, so that snipe was unfair; you really do seem to be making an effort to learn, for once. Also, please don't take the mention of obfuscation as a cue for a political rant; I am sick of the topic already, and want nothing to do with it right now, or ever, really. AFAIAC, politics itself is irrelevant, something that fulfills a biological drive but has nothing to do with practical concerns despite the innate delusion of all Homo sapiens to the contrary).

[josep...@gmail.com]

On Saturday, October 21, 2017 at 7:15:35 PM UTC-4, josep...@gmail.com wrote:
> A fixed point combinator is a function that can be used to determines the fixed points in the domain and co-domain of another function. The form of the fixed-point combinator in lambda calculus is called the Y-combinator, and was originally developed by logician Haskell Curry in the 1950s (I think, it may have been earlier).
>
> A fixed point is a domain value which, when the function is applied to it, maps to the same value in the co-domain. Thus, is we apply fixed-point combinator Y to function f, then for all x, (Y f x) -> x.

Gaah, what was I thinking when I wrote that? Sorry, let me fix this. If anyone spots any further mistakes - and there almost certainly will be some - please speak up about them.

A fixed point combinator is a function that can be used to determines *a* fixed point in the domain and co-domain of another function. One of the better known fixed-point combinators in untyped lambda calculus (of which there are several known) is the Y-combinator. If we apply the Y-combinator to a function f, then it returns a value x such that x is a fixed point of f.

So,

(Y f) -> x

(f x) -> x

Y itself is defined in λ-calculus as

Y = λf.(λx.f (x x))(λx.f (x x))

I don't know if I could properly explain this, but in it would become (using the Rosetta Code example http://rosettacode.org/wiki/Y_combinator):

(defun Y (f)

((lambda (x) (funcall x x))
(lambda (y)

(funcall f (lambda (&rest args)
(apply (funcall y y) args))))))

For comparison, using some other languages you seem interested in Scheme
,
(define Y
(lambda (h)
((lambda (x) (x x))
(lambda (g)
(h (lambda args (apply (g g) args)))))))

Forth,

\ Address of an xt.
variable 'xt
\ Make room for an xt.
: xt, ( -- ) here 'xt ! 1 cells allot ;
\ Store xt.
: !xt ( xt -- ) 'xt @ ! ;
\ Compile fetching the xt.
: @xt, ( -- ) 'xt @ postpone literal postpone @ ;
\ Compile the Y combinator.
: y, ( xt1 -- xt2 ) >r :noname @xt, r> compile, postpone ; ;
\ Make a new instance of the Y combinator.
: y ( xt1 -- xt2 ) xt, y, dup !xt ;


And if you are ready to say goodbye to what remains of your sanity by this point, there is an extended derivation in tcl at http://wiki.tcl.tk/4833.

Note that the lambda expansion of Y is not guaranteed to terminate for all f; in fact, it generally doesn't terminate for functions of arity 1 (that is, functions which take only one argument). Applying it to functions in two or more variables often does terminate, however, which is where Y becomes useful.

Part of the result of this is that if a calculus or programming language permits higher-order functions, but doesn't explicitly permit recursion (as is the case for untyped lambda calculus), then for functions for which it does terminate, applying a function f to the value of applying Y to f:

(f (Y f))

can be used to define an effective recursion of f - the application itself can be treated as a function f' of the same arity as f, which applies f repeatedly until it can not be expanded further. So, if you want a function that adds x and y, you could (assuming that IF, ZEROP, LIST, INCREMENT, and DECREMENT are already defined) have a function

(PARTIAL-ADD a b) -> (IF (ZEROP a)
b
(LIST (DEC a) (INC b)))

(Note that these are transformations in a quasi-lambda-calculus notation, not actual Lisp operations. Basically, here I am making an expansion, replacing (PARTIAL-ADD a b) with the expression on the right.)

If we then take

(PARTIAL-ADD (Y PARTIAL-ADD)) - > ADD

and apply that to , say, 2 and 2, we get

(ADD 2 2) ->
((PARTIAL-ADD (Y PARTIAL-ADD)) 2 2)

I was going to continue the expansion but decided that I wasn't quite ready to go that far down the rabbit hole right now. If you really want to go into it further, someone can go over it with you in more detail later.

[josep...@gmail.com]

You know what? I give up. I can already see how badly I am mangling it, and frankly the salient point - that the Y-combinator is a higher-order function - should be clear enough without actually trying to explain it. I have to admit that I don't really know it myself, and for your purposes right now, it's something of a tangent. Sorry about this.

I really need to get this down myself at some point, though. Perhaps someone can give a few pointers towards books or papers with suitable a suitable explanation, for both of us.

[Barry Margolin]

In article <6e1434e7-0aaa-4a53...@googlegroups.com>,

Doesn't this kind of confirm the point I was making when I first
mentioned it? The Y-combinator is an interesting bit of CS theory, but
it's likely to be too confusing for most programmers to deal with.

[Kaz Kylheku]

On 2017-10-22, Barry Margolin <bar...@alum.mit.edu> wrote:
> In article <6e1434e7-0aaa-4a53...@googlegroups.com>,
> josep...@gmail.com wrote:
>
>> You know what? I give up. I can already see how badly I am mangling it, and
>> frankly the salient point - that the Y-combinator is a higher-order function
>> - should be clear enough without actually trying to explain it. I have to
>> admit that I don't really know it myself, and for your purposes right now,
>> it's something of a tangent. Sorry about this.
>>
>> I really need to get this down myself at some point, though. Perhaps someone
>> can give a few pointers towards books or papers with suitable a suitable
>> explanation, for both of us.
>
> Doesn't this kind of confirm the point I was making when I first
> mentioned it? The Y-combinator is an interesting bit of CS theory, but
> it's likely to be too confusing for most programmers to deal with.

The Y-combinator is, why, basically the Klein Bottle of functions and
lexical scoping. So to speak. :)

[josep...@gmail.com]

On Sunday, October 22, 2017 at 12:14:15 AM UTC-4, Barry Margolin wrote:
> In article <6e1434e7-0aaa-4a53...@googlegroups.com>,

> jo-...@gmail.com wrote:
> > I have to admit that I don't really know it myself,

> Doesn't this kind of confirm the point I was making when I first
> mentioned it? The Y-combinator is an interesting bit of CS theory, but
> it's likely to be too confusing for most programmers to deal with.

Yeah, I would say it does. I was so focused on Gavino's question that I overlooked the wider context.

I am also wondering if their are alternatives that are more readily explained and understood; after all, as I understand it there are an infinite number of fixed-point combinators which have similar properties, and my impression is that most of them *don't* involve paradoxical definitions. My impression is that the Y-combinator itself is mainly important because it encapsulates a known inconsistency in lambda calculus, and has mainly been perpetuated in the classroom as something the teacher can use to blow students' minds rather than for its (admittedly significant) practical uses and theoretical significance.

Is this something of a Social Problem Of Lisp, and if so, is there some other fixed-point combinator (or other tool) we can use that has same applications, but doesn't cause MEGO? It wouldn't be the first time for something like that, after all; for example, I understand that there are several much simpler proofs of incompleteness developed following Goedel's work, which tend to be the ones applied by working mathematicians.

One could also compare the original FORTRAN and COBOL compilers of the 1950s, with the Algol compilers from just a few years later when things like context-free grammars started to be used in language design and simpler, more efficient parsing techniques started to be developed (and yes, much of that work came out the MIT AI lab, and was both done in Lisp, and applied to Lisp compilers, especially in the development of canonical parsing).

It even can be seen in the history of physics, where Newton's work represented a massive simplification of the work of Galileo and Kepler; and later with quantum theory, going from Heisenberg to Dirac to Schwinger and eventually to Feynman and Gell-Mann.

In other words, contrary to what most people would expect, the first solution is often more complicated and harder to grasp than later refinements. My question is, is this the case with Curry's Y-combinator as well?

[Kaz Kylheku]

On 2017-10-22, josep...@gmail.com <josep...@gmail.com> wrote:
> On Sunday, October 22, 2017 at 12:14:15 AM UTC-4, Barry Margolin wrote:
>> In article <6e1434e7-0aaa-4a53...@googlegroups.com>,
>> jo-...@gmail.com wrote:
>> > I have to admit that I don't really know it myself,
>
>> Doesn't this kind of confirm the point I was making when I first
>> mentioned it? The Y-combinator is an interesting bit of CS theory, but
>> it's likely to be too confusing for most programmers to deal with.
>
> Yeah, I would say it does. I was so focused on Gavino's question that
> I overlooked the wider context.
>
> I am also wondering if their are alternatives that are more readily
> explained and understood; after all, as I understand it there are an
> infinite number of fixed-point combinators which have similar

The Y combinator is basically a pointless stupidity. It doesn't create
"support" for recursion. It only overcomes the lack of a mechanism for
establishing the binding of a function name such that the name is
visible to the body; i.e. the self-referential name lookup part of
recursion, not any aspect of the call itself.

Building this self-referential name binding mechanism into a language is
trivial compared to all the other shit that has to work right so that
the Y combinator has any hope of working.

In Common Lisp, we have two lexical function binding mechanisms: LABELS
and FLET. Under FLET, a function's body doesn't see that function's own
binding, and so recursion isn't possible. If only FLET existed, the Y
combinator could be used to get the functionality of LABELS.

Why bother? Just implement LABELS at the kernel level.
It will likely be more efficient. It expresses a direct self-reference.

The Y combinator is inherently inefficient if the combinator and the
function fragment are separately compiled. The function fragment body
has no idea that the binding F points back to itself. This is arranged
at run-time when the function is fed into the combinator.

Pure dweebery, basically.

[Robert Munyer]

> While it usually
> seen as quite important among Lispers, even many experienced Lisp devs
> (such as Barry above) have had trouble with it, or have simply never
> felt the need for it.

Probably because he isn't old enough to have needed it.

One accomplishment of the Lisp 1.0 era (late '50s) was providing
practical, "friendlier" constructs that could be used to express
things that might otherwise be expressed with the Y combinator.

To appreciate the difference, try writing some interesting
programs in Lisp and then writing the same programs in Unlambda.

I suspect that the Y combinator probably had great practical
value, for people who were interested in functional programming
_before_ the late '50s. From the '60s onward, not so much.

--
-- Robert Munyer code below generates e-mail address

(format nil "~(~{~a~^ ~}~)" (reverse `(com dot munyer at ,(* 175811 53922))))

[Barry Margolin]

In article <201710221...@kylheku.com>,

Kaz Kylheku <217-67...@kylheku.com> wrote:

> On 2017-10-22, josep...@gmail.com <josep...@gmail.com> wrote:
> > On Sunday, October 22, 2017 at 12:14:15 AM UTC-4, Barry Margolin wrote:
> >> In article <6e1434e7-0aaa-4a53...@googlegroups.com>,
> >> jo-...@gmail.com wrote:
> >> > I have to admit that I don't really know it myself,
> >
> >> Doesn't this kind of confirm the point I was making when I first
> >> mentioned it? The Y-combinator is an interesting bit of CS theory, but
> >> it's likely to be too confusing for most programmers to deal with.
> >
> > Yeah, I would say it does. I was so focused on Gavino's question that
> > I overlooked the wider context.
> >
> > I am also wondering if their are alternatives that are more readily
> > explained and understood; after all, as I understand it there are an
> > infinite number of fixed-point combinators which have similar
>
> The Y combinator is basically a pointless stupidity. It doesn't create
> "support" for recursion. It only overcomes the lack of a mechanism for
> establishing the binding of a function name such that the name is
> visible to the body; i.e. the self-referential name lookup part of
> recursion, not any aspect of the call itself.

I.e. it answers the question "How do I make an anonymous, recursive
function?"

Javascript actually has this built in, as the "named function
expression". When you use this syntax, the scope of the name is just the
body of the function. Although most of the times I've seen this syntax
used on Stack Overflow, there hasn't been any recursion; I think it's
being used either to have the name show up in the debugger (not
unreasonable) or simply because the poster doesn't know what they're
doing (most likely).

[Kaz Kylheku]

On 2017-10-23, Barry Margolin <bar...@alum.mit.edu> wrote:
> In article <201710221...@kylheku.com>,
> Kaz Kylheku <217-67...@kylheku.com> wrote:
>
>> On 2017-10-22, josep...@gmail.com <josep...@gmail.com> wrote:
>> > On Sunday, October 22, 2017 at 12:14:15 AM UTC-4, Barry Margolin wrote:
>> >> In article <6e1434e7-0aaa-4a53...@googlegroups.com>,
>> >> jo-...@gmail.com wrote:
>> >> > I have to admit that I don't really know it myself,
>> >
>> >> Doesn't this kind of confirm the point I was making when I first
>> >> mentioned it? The Y-combinator is an interesting bit of CS theory, but
>> >> it's likely to be too confusing for most programmers to deal with.
>> >
>> > Yeah, I would say it does. I was so focused on Gavino's question that
>> > I overlooked the wider context.
>> >
>> > I am also wondering if their are alternatives that are more readily
>> > explained and understood; after all, as I understand it there are an
>> > infinite number of fixed-point combinators which have similar
>>
>> The Y combinator is basically a pointless stupidity. It doesn't create
>> "support" for recursion. It only overcomes the lack of a mechanism for
>> establishing the binding of a function name such that the name is
>> visible to the body; i.e. the self-referential name lookup part of
>> recursion, not any aspect of the call itself.
>
> I.e. it answers the question "How do I make an anonymous, recursive
> function?"

It won't work if the underlying run-time doesn't support the nested
execution of the same function (due to using global storage for
parameters, or any other aspect of the function call, for instance).

Not to mention that it relies on lexical closures.

By the time you have all that working, named recursion is basically just
cutting the opening day ribbon.

[Kaz Kylheku]

On 2017-10-22, Robert Munyer <rob...@not-for-mail.invalid> wrote:
>> While it usually
>> seen as quite important among Lispers, even many experienced Lisp devs
>> (such as Barry above) have had trouble with it, or have simply never
>> felt the need for it.
>
> Probably because he isn't old enough to have needed it.
>
> One accomplishment of the Lisp 1.0 era (late '50s) was providing
> practical, "friendlier" constructs that could be used to express
> things that might otherwise be expressed with the Y combinator.
>
> To appreciate the difference, try writing some interesting
> programs in Lisp and then writing the same programs in Unlambda.
>
> I suspect that the Y combinator probably had great practical
> value, for people who were interested in functional programming
> _before_ the late '50s. From the '60s onward, not so much.

Do you have any historical references that the Y combinator
was actually used in early Lisp development?

Note that the usual way of expressing it with lambdas will not work
without lexical scope, which early Lisp lacked.

The self-referential binding which allows recursion through F persists
inside the function returned by the Y combinator, and that persistence
owes to the "indefinite extent" of lexical scope.

[josep...@gmail.com]

On Sunday, October 22, 2017 at 2:45:51 PM UTC-4, Kaz Kylheku wrote:

I tend to agree that the continued used of in coursework (such as in SICP - yes, I know, I know, but most of what it says applies to CL as well) is mainly a matter of making lambda calculus seem mysterious and astonishing.

However, I got the impression that the practical uses had nothing to do with the application of it for anonymous recursion, and more to do with finding transformations of functions - specifically, that it is used as a transform for generating candidate compiler optimizations when generating machine code. This would also dovetail with the use of it in code obfuscation, obviously.

This is why I asked, as it seems to me that such an application should work with other fixed-point combinators that have the same result, but are easier to understand.

Am I wrong in this? I don't know the details of the practical uses, just that those are uses mentioned in the Wikipedia article. If the article *is* correct, I would certainly want to learn more about that use, as code generation is very much a topic I want to learn advanced techniques for.

[josep...@gmail.com]

Just to clarify, the discussion of practical uses of fixed-point combinators and fixed points in general are in the article on fixed points, not the one on fixed-point combinators.

https://en.wikipedia.org/wiki/Fixed_point_(mathematics)

[Ben Bacarisse]

On the Y combinator:

josep...@gmail.com writes:
<snip>

> On Sunday, October 22, 2017 at 2:45:51 PM UTC-4, Kaz Kylheku wrote:
>> Why bother? Just implement LABELS at the kernel level.
>> It will likely be more efficient. It expresses a direct self-reference.
>>
>> The Y combinator is inherently inefficient if the combinator and the
>> function fragment are separately compiled. The function fragment body
>> has no idea that the binding F points back to itself. This is arranged
>> at run-time when the function is fed into the combinator.
>>
>> Pure dweebery, basically.

<snip>

> However, I got the impression that the practical uses had nothing to
> do with the application of it for anonymous recursion, and more to do
> with finding transformations of functions - specifically, that it is
> used as a transform for generating candidate compiler optimizations
> when generating machine code. This would also dovetail with the use of
> it in code obfuscation, obviously.
>
> This is why I asked, as it seems to me that such an application should
> work with other fixed-point combinators that have the same result, but
> are easier to understand.
>
> Am I wrong in this? I don't know the details of the practical uses,
> just that those are uses mentioned in the Wikipedia article. If the
> article *is* correct, I would certainly want to learn more about that
> use, as code generation is very much a topic I want to learn advanced
> techniques for.

I once implemented a functional language by "compiling" the source into
pure combinator code. Naturally, the simplest way to compile recursive
definitions ended up with a Y combinator, but this was only done for
local definitions where the lambda abstraction algorithm removes all the
bound names. It /could/ have been for the top-level names too, but it's
much simpler just to make a graph with a cycle in it.

It's a long time ago but I vaguely remember playing with three
definitions of Y. The first was a Y combinator written out in terms of
others like S, K, I, C and B (I don't recall the definition but I'm sure
I can look up up). The second simply implemented the Y reduction rule
and the third tied a loop in the graph and removed the Y after the first
time it was reduced. The last was the fastest, of course, but I seem to
remember that is was not trivial to get right. The code (in BCPL) was
lost a long time ago. I'm not sure if I am glad about that or sad about
that.

--
Ben.

[Robert Munyer]

Barry Margolin wrote:

> Javascript actually has this built in, as the "named function
> expression". When you use this syntax, the scope of the name is
> just the body of the function.

I've seen this in old Lisp code, mostly written by McCarthy himself.

For a not-so-old but very succinct example, see "A Micro-Manual For
LISP", McCarthy 1978.

[Robert Munyer]

Kaz Kylheku wrote:

> Do you have any historical references that the Y combinator
> was actually used in early Lisp development?

Actually I meant _before_ early Lisp, when people who were interested
in FP were using paper or chalkboard (not vacuum tubes), and probably
all of them could fit into a single schoolbus.

A good comment about Y combinator history:
http://news.ycombinator.com/item?id=8300408

[Madhu]

* josep...@gmail.com
Wrote on Mon, 23 Oct 2017 12:34:06 -0700 (PDT):

> Am I wrong in this? I don't know the details of the practical uses,
> just that those are uses mentioned in the Wikipedia article. If the
> article *is* correct, I would certainly want to learn more about that
> use, as code generation is very much a topic I want to learn advanced
> techniques for.

I tend to think Brouwer's fixed-point theorem was the single most
important doctoral dissertation in maths history (I am assuming he
described it in his thesis, but I may be wrong). This theorem is the
theoretical basis of Real Optimization and all that is based on it,
particularly what passes of as Machine Learning now,

But the theory is best expressed in the branch of topology.
A real world problem is mapped to (say) optimization of a function on
reals, and fixed point theorems establish there is a
solution: then one devises algorithms to find numerical solution (think
Newtons method) using probabilistic considerations, and that is mapped
back to the real world.

On the other hand Fixed point combinators in computation (say lambda
calculus) though they are the same concept are only useful as
theoretical constructs in advancing the theory.
There is no "practical" application possible as far as I can tell,
and especially to to "programming", which cannot be mapped,
I think this is a fundamental limitation which follows from turing.
(again, if you can show me to be wrong, I'd appreciate it)

[tar...@google.com]

On Monday, October 23, 2017 at 12:04:11 PM UTC-7, Kaz Kylheku wrote:

> Do you have any historical references that the Y combinator
> was actually used in early Lisp development?

I recall doing a seminar project in 1980 implementing a combinator
graph-reduction implementation of Lisp in order to get an efficient lazy
evaluation Lisp. This was based on an academic paper.

It used a Y-combinator for implementing recursive functions and a
Z-combinator for mutually recursive functions. The Y-combinator worked great,
but the Z-combinator was not a straight-forward extension. It turned out to
be a lot more complicated. And the paper didn't go into detail about it,
other than to say it worked "similarly". But I came up with a working system.

Unfortunately, I don't recall the paper that I built that system from,
although it looks like David Turner has done a lot of research with
combinator graph reductions in function languages. And the name does seem
a little bit familiar. Searching for papers didn't turn up anything that
looked like the one I wanted, though.

[trump...@gmail.com]

what did it do? what problem it solve?

[tar...@google.com]

It implemented a lazy-evaluation version of lisp efficiently.

The efficiency came from sharing graph structure so that when an item that ended up in many places was evaluated, that evaluation result became available in all of those places without having to go through the evaluation again.

[Paul Rubin]

tar...@google.com writes:
> It implemented a lazy-evaluation version of lisp efficiently.
> The efficiency came from sharing graph structure so that when an item
> that ended up in many places was evaluated, that evaluation result
> became available in all of those places without having to go through
> the evaluation again.

Simon Peyton Jones's book about functional programming implementation
has a lot of info about this:

https://www.microsoft.com/en-us/research/publication/the-implementation-of-functional-programming-languages/

But, I still think combinator calculus didn't historically have much to
do with practical Lisp implementation.

[trump...@gmail.com]

What are you saying?