flicky frans | 11 Feb 22:46 2014
Picon

Lazy lists with with call-by-value reduction strategy.

Hello. I am currently writing lists with lazy semantics in the pure
lambda-calculus with call-by-value reduction strategy.
Here is an example: http://pastebin.com/SvQ5hCSD
Here is a simple interpetator: http://pastebin.com/mejCWqpu
Am I reinventing the wheel? Are there some sources, from where i can
learn more about lazy evaluation in the strict languages?
Kyle Marek-Spartz | 11 Feb 22:54 2014
Picon

Re: Lazy lists with with call-by-value reduction strategy.

SICP comes to mind: http://mitpress.mit.edu/sicp/full-text/sicp/book/node70.html

--  
Kyle Marek-Spartz

On February 11, 2014 at 3:47:09 PM, flicky frans (flickyfrans <at> gmail.com) wrote:
>  
> Hello. I am currently writing lists with lazy semantics in the  
> pure
> lambda-calculus with call-by-value reduction strategy.
> Here is an example: http://pastebin.com/SvQ5hCSD
> Here is a simple interpetator: http://pastebin.com/mejCWqpu  
> Am I reinventing the wheel? Are there some sources, from where  
> i can
> learn more about lazy evaluation in the strict languages?
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe  
>  

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
flicky frans | 11 Feb 23:42 2014
Picon

Re: Lazy lists with with call-by-value reduction strategy.

>interpetator
Sorry, interpreter.
Thanks, Kyle Marek-Spartz. I've read SICP a few years ago, but
completely forgot about this chapter. That's what I wrote modulo CPS,
but CPS is a significant part.

2014-02-12 0:54 GMT+03:00, Kyle Marek-Spartz <kyle.marek.spartz <at> gmail.com>:
> SICP comes to
> mind: http://mitpress.mit.edu/sicp/full-text/sicp/book/node70.html
>
> --
> Kyle Marek-Spartz
>
> On February 11, 2014 at 3:47:09 PM, flicky frans (flickyfrans <at> gmail.com)
> wrote:
>>
>> Hello. I am currently writing lists with lazy semantics in the
>> pure
>> lambda-calculus with call-by-value reduction strategy.
>> Here is an example: http://pastebin.com/SvQ5hCSD
>> Here is a simple interpetator: http://pastebin.com/mejCWqpu
>> Am I reinventing the wheel? Are there some sources, from where
>> i can
>> learn more about lazy evaluation in the strict languages?
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe <at> haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>
(Continue reading)

Roman Cheplyaka | 11 Feb 23:52 2014

Re: Lazy lists with with call-by-value reduction strategy.

Except Scheme is not pure — they use set! to achieve memoisation.

I don't think the OP bothers with memoisation in his/her encoding,
though.

Roman

* Kyle Marek-Spartz <kyle.marek.spartz <at> gmail.com> [2014-02-11 15:54:34-0600]
> SICP comes to mind: http://mitpress.mit.edu/sicp/full-text/sicp/book/node70.html
> 
> --  
> Kyle Marek-Spartz
> 
> On February 11, 2014 at 3:47:09 PM, flicky frans (flickyfrans <at> gmail.com) wrote:
> >  
> > Hello. I am currently writing lists with lazy semantics in the  
> > pure
> > lambda-calculus with call-by-value reduction strategy.
> > Here is an example: http://pastebin.com/SvQ5hCSD
> > Here is a simple interpetator: http://pastebin.com/mejCWqpu  
> > Am I reinventing the wheel? Are there some sources, from where  
> > i can
> > learn more about lazy evaluation in the strict languages?
> > _______________________________________________
> > Haskell-Cafe mailing list
> > Haskell-Cafe <at> haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe  
> >  
> 
> _______________________________________________
(Continue reading)

Kyle Miller | 12 Feb 04:24 2014
Picon

Re: Lazy lists with with call-by-value reduction strategy.

Please correct me if I'm wrong, but isn't Haskell secretly doing a set! when parts of an ADT are evaluated to memoize them?  In the vein of lazy lists, taking the tail of a list in Haskell would be one such example.

I noticed this secret set! when I was learning about its garbage collector: I was surprised at first that objects in older generations could ever have pointers to objects in newer generations!

Kyle


On Tue, Feb 11, 2014 at 5:52 PM, Roman Cheplyaka <roma <at> ro-che.info> wrote:
Except Scheme is not pure — they use set! to achieve memoisation.

I don't think the OP bothers with memoisation in his/her encoding,
though.

Roman

* Kyle Marek-Spartz <kyle.marek.spartz <at> gmail.com> [2014-02-11 15:54:34-0600]
> SICP comes to mind: http://mitpress.mit.edu/sicp/full-text/sicp/book/node70.html
>
> --
> Kyle Marek-Spartz
>
> On February 11, 2014 at 3:47:09 PM, flicky frans (flickyfrans <at> gmail.com) wrote:
> >
> > Hello. I am currently writing lists with lazy semantics in the
> > pure
> > lambda-calculus with call-by-value reduction strategy.
> > Here is an example: http://pastebin.com/SvQ5hCSD
> > Here is a simple interpetator: http://pastebin.com/mejCWqpu
> > Am I reinventing the wheel? Are there some sources, from where
> > i can
> > learn more about lazy evaluation in the strict languages?
> > _______________________________________________
> > Haskell-Cafe mailing list
> > Haskell-Cafe <at> haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Danny Gratzer | 12 Feb 04:45 2014
Picon

Re: Lazy lists with with call-by-value reduction strategy.

Yes. Edward Yang has a wonderful series on how Haskell's (GHC's) runtime works under the hood http://blog.ezyang.com/2011/04/the-haskell-heap/


Cheers,
Danny Gratzer


On Tue, Feb 11, 2014 at 9:24 PM, Kyle Miller <kmill31415 <at> gmail.com> wrote:
Please correct me if I'm wrong, but isn't Haskell secretly doing a set! when parts of an ADT are evaluated to memoize them?  In the vein of lazy lists, taking the tail of a list in Haskell would be one such example.

I noticed this secret set! when I was learning about its garbage collector: I was surprised at first that objects in older generations could ever have pointers to objects in newer generations!

Kyle


On Tue, Feb 11, 2014 at 5:52 PM, Roman Cheplyaka <roma <at> ro-che.info> wrote:
Except Scheme is not pure — they use set! to achieve memoisation.

I don't think the OP bothers with memoisation in his/her encoding,
though.

Roman

* Kyle Marek-Spartz <kyle.marek.spartz <at> gmail.com> [2014-02-11 15:54:34-0600]
> SICP comes to mind: http://mitpress.mit.edu/sicp/full-text/sicp/book/node70.html
>
> --
> Kyle Marek-Spartz
>
> On February 11, 2014 at 3:47:09 PM, flicky frans (flickyfrans <at> gmail.com) wrote:
> >
> > Hello. I am currently writing lists with lazy semantics in the
> > pure
> > lambda-calculus with call-by-value reduction strategy.
> > Here is an example: http://pastebin.com/SvQ5hCSD
> > Here is a simple interpetator: http://pastebin.com/mejCWqpu
> > Am I reinventing the wheel? Are there some sources, from where
> > i can
> > learn more about lazy evaluation in the strict languages?
> > _______________________________________________
> > Haskell-Cafe mailing list
> > Haskell-Cafe <at> haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Roman Cheplyaka | 12 Feb 00:31 2014

Re: Lazy lists with with call-by-value reduction strategy.

Do you know about the Church encoding?

I don't quite understand your encoding. Consider your cons function:

  cons    = \x xs f z. f (\_. x) (\f' _. xs f' z);

1. Why do you pass (\_. x) instead of x to f? This looks like an attempt
   to delay evaluation of x, but by the time cons is applied, x must
   have been evaluated already due to CBV.

2. Why do you ask for a new f' but ignore the new z' (as compared to f
   and z)?

Also, your interpreter doesn't seem to finish in a reasonable time on
your own input.

Roman

* flicky frans <flickyfrans <at> gmail.com> [2014-02-12 00:46:47+0300]
> Hello. I am currently writing lists with lazy semantics in the pure
> lambda-calculus with call-by-value reduction strategy.
> Here is an example: http://pastebin.com/SvQ5hCSD
> Here is a simple interpetator: http://pastebin.com/mejCWqpu
> Am I reinventing the wheel? Are there some sources, from where i can
> learn more about lazy evaluation in the strict languages?
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
flicky frans | 12 Feb 01:02 2014
Picon

Re: Lazy lists with with call-by-value reduction strategy.

>Do you know about the Church encoding?
Yes.
>1. Why do you pass (\_. x) instead of x to f? This looks like an attempt
>to delay evaluation of x, but by the time cons is applied, x must
>have been evaluated already due to CBV.
It's for constructing lists from the evaluated values. For lazy
purposes there is consC.
2. Why do you ask for a new f' but ignore the new z' (as compared to f
>and z)?
It's for the tail function, which is problematic in the standard
Church encoding. Here it is O(1). While folding, actual f passes over
the whole list.
>Also, your interpreter doesn't seem to finish in a reasonable time on
your own input.
It's very simple and unoptimized. And there is much arithmetic in the
code. It finishes, but if you don't want to wait, you can try "sum
(take (s (s z)) (cycle (take (s (s z)) (filter (leq (s z)) nats))))".

2014-02-12 2:31 GMT+03:00, Roman Cheplyaka <roma <at> ro-che.info>:
> Do you know about the Church encoding?
>
> I don't quite understand your encoding. Consider your cons function:
>
>   cons    = \x xs f z. f (\_. x) (\f' _. xs f' z);
>
> 1. Why do you pass (\_. x) instead of x to f? This looks like an attempt
>    to delay evaluation of x, but by the time cons is applied, x must
>    have been evaluated already due to CBV.
>
> 2. Why do you ask for a new f' but ignore the new z' (as compared to f
>    and z)?
>
> Also, your interpreter doesn't seem to finish in a reasonable time on
> your own input.
>
> Roman
>
> * flicky frans <flickyfrans <at> gmail.com> [2014-02-12 00:46:47+0300]
>> Hello. I am currently writing lists with lazy semantics in the pure
>> lambda-calculus with call-by-value reduction strategy.
>> Here is an example: http://pastebin.com/SvQ5hCSD
>> Here is a simple interpetator: http://pastebin.com/mejCWqpu
>> Am I reinventing the wheel? Are there some sources, from where i can
>> learn more about lazy evaluation in the strict languages?
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe <at> haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>

Gmane