letrec

Isn't
(letrec ([is-even? (lambda (n)
                    (or (zero? n)
                        (is-odd? (sub1 n))))]
         [is-odd? (lambda (n)
                   (and (not (zero? n))
                        (is-even? (sub1 n))))])
        (is-odd? 11))

equivalent to...

(let
    ([is-even? nil]
     [is-odd? nil])
    (set! is-even? (lambda (n)
                    (or (zero? n)
                        (is-odd? (sub1 n)))))
    (set! is-odd? (lambda (n)
                   (and (not (zero? n))
                        (is-even? (sub1 n)))))
    (is-odd? 11))

Sorry for the wait, but it's almost Christmas and I had things to do.

>>7
Incidentally, I'm that person. I'll explain why delconts are more powerful/expressive than call/cc without mutable state (if you add mutable state in the mix, their expressive power are equivalent), and why >>1's code breaks with call/cc.

So, let's start.

What's a continuation?
A continuation is a kind-of-procedure-but-not-really representing what's to do next, or the future of a computation.
This is not helpful, and it's confusing, so let's make an example:

We have this code: (+ 1 3). Assuming strict evaluation, we need to evaluate +, then 1, then 3, and apply the resulting procedure + to the results of 1 and 3: ([]s mark the piece of code currently being evaluated)
[(+ 1 3)] ; start
 ([+] 1 2) ; evaluate +
 (#<proc> [1] 2) ; evaluate 1
 (#<proc> 1 [2]) ; evaluate 2
[(#<proc> 1 2)] ; apply #<proc> to 1 and 2
3
That was pretty pointless, how is that related to continuations?
The []s represent the current evaluation point, and what's outside of them is the continuation of it.
Look at the second line, ([+] 1 2). + is being evaluated, and ([] 1 2) is its continuation, because, after its evaluation is done, that' how the computation will continue.
Basically, ([] 1 2) is pretty much equivalent to (lambda (x) (x 1 2), and the evaluation of + in the context ([] 1 2) is like ((lambda (x) (x 1 2)) +). Instead of returning a value, we're passing an argument to a procedure, called continuation.
Extend that idea to the whole expression, or even the whole program, and you get Continuation Passing Style, CPS for short, where every expression is in tail position, and every procedure takes an extra ``continuation'' argument.

Example:

(define (fact x) ; factorial
 (if (zero? x) 1
     (* x (fact (- x 1)))))

(define (fact-cps x cont)     ; CPSed factorial
 (zero?-cps x                 ; `zero?-cps' is the CPS version of `zero?',
  (lambda (is-zero?)          ; and `is-zero?' is the return value of `zero?-cps'.
                              ; This procedure is the continuation of the (zero? x) expression: (if [] 1 (* x (fact (- x 1)))).
   (if is-zero?
       (cont 1)               ; ``return'' 1 to our continuation.
       (--cps x 1             ; CPSed `-'.
        (lambda (x-1)         ; return value of (- x 1)
                              ; Same as before, this procedure is the continuation of (- x 1): (* x (fact []))
         (fact-cps x-1
          (lambda (x2)        ; x2 = (fact (- x 1)), continuation: (* x [])
           (*-cps x x2 cont)) ; (* x []) is in tail position, it has the same continuation of the original `fact-cps' call.
                              ; A bad person who doesn't optimize his tail calls would have written
                              ; (*-cps x x2 (lambda (x3) (cont x3))) instead.
           )))))))

I know this is a bad explaination, so please, if you don't understand something, ask me anything.

What's call/cc?
Usually, when we code, continuations are implicit, and are only made explicit when the code is converted in CPS.
call-with-current-continuation calls a procedure with, well, the current continuation. Except that the continuation procedure given by call/cc is special: it does not only represent the captured continuation, but, when called, it totally replaces the continuation of where it is called with the original one.

Example time:
Say we have this expression: (+ (call/cc f) 2), and that f is something like (lambda (x) (set! c x) 1).
The continuation of (call/cc f) is (+ [] 2), or (lambda (x) (+ x 2)) if you want.
So, f receives a procedure similar to (lambda (x) (+ x 2)), stores it in c, and returns 1.
The whole thing, now (+ 1 2), evaluates to 3. Yay.

We have, now, (/ (c 2) 0), where c still holds the continuation (+ [] 2).
The continuation of (c 2) is (/ [] 0). That's bad, it's a division by zero, it will fail as soon as we evaluate it, and that's right after (c 2) returns!
But, c is a continuation reified by call/cc, so it will replace the continuation (/ [] 0) with its original (+ [] 2), the resulting expression will be (+ 2 2), and it will return 4. No division by zero error.
That's call/cc.

In CPS, it is implemented as:

(define (call/cc fun cont) ; cont is the current continuation
 (let ((reified-cont (lambda (x new-cont) (cont x)))) ; disregard the new continuation, return `x' to the old continuation.
  (fun reified-cont cont))) ; fun is given the reified continuation, and returns to the old continuation.

Example:
[code]
(define c #f)

(+ (call/cc (lambda (x) (set! c x) 1)) 2)
; =>
(call/cc (lambda (x cont) (set! c x) (cont 1))
         (lambda (x) (+ x 2))) ; (+ [] 2)
; evaluate:
(let ((reified-cont (lambda (x new-cont)
                      ((lambda (x) (+ x 2)) x))))
 ((lambda (x cont) (set! c x) (cont 1))
  reified-cont
  (lambda (x) (+ x 2))))
; evaluate:
(set! c reified-cont)
((lambda (x) (+ x 2)) 1)
; evaluate:
(+ 1 2) ; => 3, and c is now reified-cont.

(/ (c 2) 0)
; =>
(c 2 (lambda (x) (/ x 0)) ; (/ [] 0)
; c = reified-cont, so:
((lambda (x new-cont)
 ((lambda (x) (+ x 2)) x))
 2
 (lambda (x) (/ x 0))
; evaluate:
((lambda (x) (+ x 2)) 2) ; at this point, (lambda (x) (/ x 0)) is already discarded, as it was bound to new-cont.
; evaluate:
(+ 2 2) ; => 4


More in the next post.

What are delimited continuations?
http://dis.4chan.org/read/prog/1135170518/97,101

How are they strictly more expressive than call/cc, without mutable state?
http://www.cs.bham.ac.uk/~hxt/research/exncontjournal.pdf
Basically, given a statically typed lambda calculus without recursion, if we augment it with unchecked exceptions, it will become Turing-complete, but it will not when extended with call/cc, proving that unchecked exceptions are strictly more powerful than call/cc.

You can write a fixpoint combinator with delimited continuations, and implement exceptions without mutable state. Since they're Turing-complete, they're strictly more expressive than call/cc.


(define (fix f)
  (let ((g (lambda (x)
             (control k (f (lambda (y) ((prompt (k values) (k values)) y)))))))
    (prompt (g values) (g values))))

((fix (lambda (fact)
        (lambda (x)
          (if (zero? x) 1
              (* x (fact (- x 1)))))))
 5)
; => 120

I'm going to sleep now. Good night.

>>14
Why have you renamed shift/reset to prompt/control?

>>14
What are delimited continuations?
And there is a much better explanation http://community.schemewiki.org/?composable-continuations-tutorial

it also has an example, how delimited continuations can free your code from a crapload of ugly boilerplate.

Toulouse-Letrec

>>1
It's, but Scheme probably uses y-combinator or first-class environment instead. set! doesn't really give you anything, you cant do with a bunch lambdas, including set! itself.

>>12
I know this is a bad explaination, so please, if you don't understand something, ask me anything.
Don't ask him. Read original Lambda Papers by Steely and Sussman (they use plain old assembly language for explanation) then SICP (still The Best).

>>16

his for-each stream maker can be expressed pretty easily in lua using coroutines, and coroutines aren't that difficult to implement in scheme using continuations. Therefore, his thingy is poop.


#!/usr/bin/lua

-- ARGS:
-- for_each(operator_function) -> nil
--   operator_function will be called as operator_function(element)
--   for every element in some collection.
--
-- RETURNS:
-- a function of the form fn(), where successive calls to fn
-- will return the objects that for_each would normally call operator_function on.
function for_each_to_stream(for_each)
  return coroutine.wrap(function()
    for_each(coroutine.yield)
  end)
end

-- ARGS:
-- for_each(operator_function, collection)
--   operator_function will be called as operator_function(element),
--   for every element contained within collection.
--
-- RETURNS:
-- a function of the form:
-- fn(collection) -> f()
-- successive calls to f will return elements of collection.
function for_each_to_stream_maker(for_each)
  return function(collection)
    local for_each_function_for_this_collection = function(operator_function)
      return for_each(operator_function, collection)
    end
    return for_each_to_stream(for_each_function_for_this_collection)
  end
end


function for_each_in_range_1_10(operator_function)
  for i=1,10 do
    operator_function(i)
  end
end

stream_1_10 = for_each_to_stream(for_each_in_range_1_10)

for x in stream_1_10 do
  print(x)
end
-- output:
-- 1
-- 2
-- 3
-- 4
-- 5
-- 6
-- 7
-- 8
-- 9
-- 10

function for_each_divisor(operator_function, n)
  for i=1,n do
    if math.mod(n, i) == 0 then
      operator_function(i)
    end
  end
end

for_each_divisor(print, 10)
-- output:
-- 1
-- 2
-- 5
-- 10

-- make_divisor_stream(n) -> iterator for divisors of n
make_divisor_stream = for_each_to_stream_maker(for_each_divisor)

for i in make_divisor_stream(10) do
  print(i)
end
-- output:
-- 1
-- 2
-- 5
-- 10

>>20
Your code isn't the same. I.e. you just do crappy iteration, instead of more flexible lazy-list.

>>21

they are equivalent.

>>21

the code basically translates crappy iteration to a lazy list.

>>22>>23
where is "lazy list"?

>>24

A closure that evaluates and returns the ith value of the lazy list after the ith function call is equivalent to a lazy list, which is also equivalent to a seeples forward iterator.

Thank you again, >>12,14.  You are awesome.  Would you mind answering my initial question, that of why

(letrec
    [(x-1 expr-1)
     (x-2 expr-2)
       :  :
     (x-n expr-n)]
    body...)

is not equivalent to...

(let
    [(x-1 nil)
     (x-2 nil)
       :   :
     (x-n nil)]
    (set! x-1 expr-1)
    (set! x-2 expr-2)
       :   :      :
    (set! x-n expr-n)
    body...)

>>26

I suppose it would come down to finding the right scheme expression to put in expr-i to break the equivalence, and >>12,14-san may have thought you could break the equivalence using call/cc.

>>26

but if each expr-i is just a lambda, then I think it would be equivalent.

>>25
WTF is "local" and what does function(operator_function) do? LUA is cryptic as Perl.

>>28
Using letrec with anything than lambdas considered harmful!^!!.

>>19
too bad SICP doesn't cover call/cc...

>>29

local makes a variable that is local to the function. If you didn't have the local, the variable would be global. I think variables are local by default in python? That lua code is only cryptic because it is doing weird stuff. It also doesn't help that you have to guess which arguments to the function are actually functions, and what their usages are.


function(operator_function)
  operator_function(blah)
end

is the same as:


function(f)
  f(blah)
end

It's a function that takes as an argument, another function, which is then applied to something some number of times. There are times where this can be useful, and it is one way you can get some polymorphism in C. If you've never seen this style before, or if you've never seen continuations, coroutines before, you should note that this example isn't very useful, and there are times where they can be less complex and more practical.

http://lua-users.org/wiki/CoroutinesTutorial
http://www.lua.org/pil/9.1.html

In my experiences, I've only used coroutines to create iterators. Say you have some algorithm that calculates some sequence of numbers, and you would like to iterate through these numbers. One simple solution could be to have the function that calculates the sequence fill the numbers into an array, and then you can iterate through the array. One problem with this is that you need to predict in advance how many numbers from the sequence you need to iterate through. Another is the amount of memory needed for the large array. In some situations, it would be nice to generate the sequence of numbers as you need them. That way, you can iterate through the sequence of numbers indefinitely. So what you can do is create two threads, running at the same time. Thread A will generate the sequence of numbers, passing to thread B, which will then do something with the numbers. Thread A only runs when B asks A for a number. A calculates the number, hands it to B, and then passes execution over to B. When B needs another number, it will pass execution back to A. A will resume from the same state that it was in before it stopped before, and it will then generate the next number.

So:


A = coroutine.wrap(function()
  coroutine.yield(1)
  coroutine.yield(2)
  coroutine.yield(3)
  coroutine.yield(4)
  coroutine.yield(5)
end)

function B()
  print(A()) -- prints 1
  print(A()) -- prints 2
  print(A()) -- prints 3
  print(A()) -- prints 4
  print(A()) -- prints 5
  print(A()) -- prints nil
end

This might not look very useful, but note that you can put coroutine.yield inside of a loop, or in a recursive call. The function call stack and all that is saved and execution will continue later.

You can do other things with coroutines, but so far, I haven't gone there yet.

>>15
Because shift introduces two new prompts (at call site, and inside the reified continuation), control only one (at call site). prompt and reset are the same thing.

>>26
I knew I forgot something. Well, letrec's evaluation order is unspecified (they are first evaluated, then bound), your code is equivalent to letrec*, whose evaluation order is sequential (and they are bound right after evaluation).call/cc simply can make the sequential evaluation order apparent:


(define-syntax letrec1
  (syntax-rules ()
    ((letrec ((a x) ...) body ...)
     (let ((a #f) ...)
       (set! a x)
       ...
       body ...))))
(define-syntax letrec2
  (syntax-rules ()
    ((letrec ((a t x) ...) body ...) ; the t variables because I'm lazy.
     (let ((a #f) ... (t x) ...)
         (set! a t)
         ...
         body ...))))

(define (g)
  (let ((cont #f))
    (letrec1 ((x (call/cc (lambda (c) (set! cont c) 0)))
              (y (call/cc (lambda (c) (set! cont c) 0))))
      (if cont
          (let ((c cont))
            (set! cont #f)
            (set! x 1)
            (set! y 1)
            (c 0))
          (+ x y)))))

(define (h)
  (let ((cont #f))
    (letrec2 ((x t1 (call/cc (lambda (c) (set! cont c) 0)))
              (y t2 (call/cc (lambda (c) (set! cont c) 0))))
      (if cont
          (let ((c cont))
            (set! cont #f)
            (set! x 1)
            (set! y 1)
            (c 0))
          (+ x y)))))

(display (g))
(display (h))

The call to g will return 1, the call to h will return 0. The trick is in the two (set! x 1) (set! y 1):

(let ((cont #f))
 (let ((x #f) (y #f))
  (set! x (call/cc (lambda (c) (set! cont c) 0))) ; yes, both the calls to call/cc are needed, to prevent you to cheat by evaluating the expressions in reverse order.
  (set! y (call/cc (lambda (c) (set! cont c) 0)))
  (if cont
      (let ((c cont))
        (set! cont #f)
        (set! x 1)
        (set! y 1)
        (c 0))
       (+ x y))))

You start evaluating that code, x and y are bound to 0, and that's ok.
cont is bound to this continuation, though:
(lambda (x)
 (set! y x)
 (if cont blah blah))
In this continuation, x has already been evaluated and bound to 0.
So, when we do:
(set! x 1) (set! y 1) (c 0)
The continuation is called, but x is not re-evaluated and re-bound to 0, it will still be the 1 we set!ed right now.
Thus, with x = 1, y = 0, cont = #f, the whole expression will return (+ x y) => (+ 1 0) => 1.

If the order was unspecified, it would return 0. Understanding why is left as an exercise for the reader.

A R5RS letrec is equivalent to this:

(letrec ((even? (lambda (x) (or (zero? x) (not (odd? (- x 1))))))
         (odd?  (lambda (x) (and (not (zero? x)) (even? (- x 1))))))
  (odd? 11))

;=>

(let ((even? #<unspecified>) (odd? #<unspecified>))
 (let ((tmp1 (lambda (x) (or (zero? x) (not (odd? (- x 1))))))
       (tmp2 (lambda (x) (and (not (zero? x)) (even? (- x 1))))))
  (set! even? tmp1)
  (set! odd?  tmp2)
  (odd? 11)))

The two lets can be merged safely.

>>33
Well, letrec's evaluation order is unspecified
Reminds me of C/C++. Language with unspecified behaviour can't be Enterprise Quality.

>>34
Unspecified order != unspecified behaviour. let's evaluation order is unspecified to make code like:
(let ((x (f x))) ; (f x) refers to the outer x
 ...)
possible. letrec's semantics (which are well-defined) being inferior to letrec*'s is another thing.
Go back to /g/, or stop talking out your ass.

>>35
let's evaluation order is unspecified
Let is defined through lambda application, which has undefined or implementation dependent order. That is enough to make code non-portable.

>>36

the idea is that no one should write code using let where the order of evaluation matters, and they should instead use let* and pick an ordering that suits them.

>>37
The original idea was:
http://www.jwz.org/doc/worse-is-better.html
>Correctness-the design must be correct in all observable aspects. Incorrectness is simply not allowed.
Consistency-the design must not be inconsistent. A design is allowed to be slightly less simple and less complete to avoid inconsistency. Consistency is as important as correctness.
Why Scheme people interpreted it as "undefined behaviour is consistent" is beyond me.

>>38

undefined behavior is consistent. It is consistently undefined, and should never be invoked. It is never a problem if you never invoke it. There are advantages to leaving the order undefined. If something is only logically correct when evaluated in a certain order, there are probably more opportunities for bugs. If something can be logically correct, regardless of the order of evaluation, then its correctness likely pretty solid and simple. It provides the compiler with opportunities for parallelization, but this is kind of advanced, and may end up introducing overhead if the compiler isn't wise about it.

>>38

the author of that website is an idiot.

>>39
Yay! Undefined behaviour makes interface simple, correct, consistent and complete! Yay! Scheme! So randum! Yay!

>>40
You antisemite-nazi scum! JWZ is one of the best jewish programmers, even Spolsky says so!

>>42

well, he isn't necessarily an idiot, but he says many idiotic things in the website, and it looks like it is just an effort to get his name out there.

>>41

you seem to think you can learn everything you need to know about scheme by reading one critical article written by one dude on the internet. Try using it and develop your own opinion.

>>43
you seem to think you can learn everything you need to know about scheme by reading one critical article written by one dude on the internet. Try using it and develop your own opinion.
Cant you see, undefined behaviour just invites bugs: a little change in compiler's eval-order could break your whole program.

http://www.cygwin.com/ml/glibc-bugs/2011-02/msg00090.html
That is why Unix sucks. They changed memcpy implementation and broke tons of code that depended on undefine behavior. But Worse is Better, of course.

>>44

But specifying things like that prevent implementations from providing the main functionality in the fastest way possible. I gather the problem with the memcpy thing is that some implementations would copy from back to front, while others would copy from front to back, causing strange effects if the regions overlapped? So if you specified the order of the copy, then overlapping in one direction would always work, and overlapping in the other would always fail. But what if you had some processor A that could implement back to front copying really fast (maybe it had a single instruction for it or something), and it couldn't do it the other way as quickly. The order of the copying is irrelevant for correct usages of memcpy, and insisting that the slower order always be taken will piss off people using processor A who use memcpy the correct way. The solution isn't to make memcpy do memmove, it's to educate people to use memmove when needed instead of depending on undefined behavior of memcpy, and to use memcpy when memcpy's behavior is defined.

Again, it's not undefined behaviour, let's sematics are well-defined. The definition is, the evaluation order is unspecified. If you want, you can rephrase that as ``every expression is conceptually evaluated at the same time''. Goddamn /g/tards.

>>44
The correct course of action is not to assume undefined behaviour as valid behaviour.

>>45
But specifying things like that prevent implementations from providing the main functionality in the fastest way possible. I
So, for you speed is more important than simplicity and consistency? Why wont you use C/C++ or Fortran then?

>>47
The correct course of action is to eliminate undefined behaviour.

>>46
If you want, you can rephrase that as ``every expression is conceptually evaluated at the same time''.
You can close your eyes, but it wont change the order.

>>32
>I hate lazy lists
>I KNOW, I'LL CREATE TWO THREADS EQUIVALENT TO ONE THREAD WITH A LAZY LIST
ENTERPRISE PROGRAMMING

>>50

Actually, my scheme implementation interfaces with my web cam to detect when I've closed my eyes, and it then evaluates let, letrec, and map using random order, and when my eyes are open, it evaluates them from front to back.

>>51

I love lazy lists, which is why I choose to use an implementation of lazy lists that allows me to use a function call stack when generating the elements of the lazy list.

HASKAL
Lazy shit doesnt do anything until it has to show its doing its job.

>>54
lisp is shit.


[sub]my[/sub]anus[sub]all[/sub]

_myanus_all