Friday, January 1, 2010

Constants To Functions

The better title would be "How to simulate Eagerness Lazily." But then, there's no solution yet.

The question is how in a lazy LCi calculus it is enforced that a call is strict in it's arguments. The answer, just doodling here, might be to shift the meaning of constants such that they are applied to the calls, i.e. constants are functions, under lazy reduction. A bit dirty, since constants and calls are seen as separate entities -have different semantics- under different rewrite strategies.

Thus, 'print (1 + 2) * 3' would be compiled to '((((2 1) +) 3) *) print,' where a bold emphasized constant denotes a lazy constant. It would reduce the following way:

    ((((2 1) +) 3) *) print
→  {reduce 2 1 to F, F expects a function taking two integers} 
    (((F +) 3) *) print
→  {reduce F + to 3}
     ((3 3) *) print
→  {reduce 3 3 to G}
     (G *) print
→  {reduce G * to 9}
     9 print

Ah well, reverse polish on a stack machine. Guess if you would know LC/ Haskell better than me this would be a standard technique. Or, should it be: '((((2 +) 1) *) 3) print'?

It breaks, for now, but the answer is somewhere there, I guess. Is '((1 2) +) (( 1 2) +) *' valid? Or, can you assume it would just never be generated? When an argument is fully reduced, swap the next argument to head position? Can you guarantee that a swap is the last thing to do lazily? It might just be impossible? I need a book...

The central idea: make arguments functions, evaluate arguments first, swap each argument with the next argument when it is reduced.

010210: I am pretty sure I am reinventing the encoding of integers in LC here, or something close to it. Just use those, or a more concrete representation, and make a call continue by evaluating the next call could be sufficient.

Back to C

No comments:

Post a Comment