What, if any, is wrong with this definition of letrec in Scheme?

Question

R5RS gives proposed macro definitions for library forms of syntax:

http://schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-10.html#%_sec_7.3

Which also defines letrec, in a very complicated way, certainly not how I would define it, I would simply use:

(define-syntax letrec2
  (syntax-rules ()
    ((letrec2 ((name val) ...) body bodies ...)
     ((lambda ()
       (define name val) ...
       body bodies ...)))))

As far as I understand the semantics of letrec, which I use very often as a named let. It works in this way, however as I've had my fair share of debates with philosophers who think they can just disprove special relativity or established phonological theories, I know that when you think you have a simple solution to a complex problem, it's probably WRONG. There has got to be some point where this macro does not satify the semantics of letrec else they'd probably have used it.

In this definition, the definitions are local to the body of the letrec, they can refer to each other for mutual recursion, I'm not quite sure what (if any) is wrong.

Lavine

Answer 1

Okay, I finally found the reason, it's as simple as useless, there is nothing wrong with my definition, and it is in fact due to some errors superior to the one in R5RS.

http://community.schemewiki.org/?scheme-faq-macros

Look for 'letrec', you all couldn't have answered my question of what was wrong, nothing was wrong apparently, R5RS had an 'erratum' in an informative section apparently. I'll be forced to accept my own answer now I guess...

What begs the question now is why the R5RS authors didn't choose this simple solution and went for a very complex one which even contained an error...

Lavine

Quoting me:"The internal define is a primitive form only in some implementations." Quoting schemewiki:"Still, there are some Scheme implementations which only provide a primitive top-leveldefine and implement internal defines in terms of letrecs..." Your definition only works in some implementations. I quoted the introduction to R5RS to show why I think the R5RS authors did not choose your implementation. If my point about R5RS's philosophy does not make sense, I am willing answer your questions about it. – Bremser

@Bremser Well, technically the definition will work in all implementations. It's just that in some implementations the internal defines it uses will be expanded into the native implementation of letrec. – Bourse

Answer 2

It seems to me that you have pushed the responsibility of the implementation from the macro to the compiler something the R5RS designers seem to be trying to avoid.

In fact local defines are implemented with letrec in R5RS. See 6.2.2 Internal definitions.

I think the designers intentions are summed up well in the introduction to the R5RS:

Programming languages should be designed not by piling feature on top of feature, but by removing the weaknesses and restrictions that make additional features appear necessary. Scheme demonstrates that a very small number of rules for forming expressions, with no restrictions on how they are composed, suffice to form a practical and efficient programming language that is flexible enough to support most of the major programming paradigms in use today.

edit1: Example of internal defines transformed to r5rs version of letrec. PLT scheme 4.2.5 collects/r5rs/main.ss

(define-syntax (r5rs:body stx)
(syntax-case stx (let)
  [(_ (let () . body))
   #'(let () . body)]
  [_
   ;; Convert internal definitions to `r5rs:letrec', as opposed
   ;; to `letrec'.
...

In PLT Scheme in R5RS mode does convert internal defines to the R5RS version of letrec. You can also test this for yourself by using DrScheme's macro expander on any code with internal defines.

Bremser

Well, define is a primitive form, not a library form unlike letrec. define and set! really can't be defined in terms of other functions. Also, for the rest I don't really get how your post relates to my point here, I have still kept it a macro. And letrec is part of the R5RS standard, though it's possible for an implementation to realize this as a macro, it's not required, as long as the semantics given in R5RS are met. And it still is a macro here, the macros in R5RS are 'suggestions'. – Lavine

@Lajla The internal define is a primitive form only in some implementations. Internal defines can and are defined in terms of letrec in some implementations. Your macro only works to define letrec when the internal define is primitive. The internal define often is defined in terms of letrec because it follows the philosophy which I quoted from the intro of R5RS. – Bremser

Do you have some citation that indicates that? Because if that's true that would obviously be the explanation. But as far as I know define is always primitive because it has completely unique semantics, as in, it cannot appear at a lot of places, and to define internal defines in terms of macros, an implementation would need to add letrec-syntax to every form which has a body. Your source only says it's equivalent, it's not explicit about how it's implemented, but if you can provide a citation to an implementation that does this, then it's the obvious answer to our problem. – Lavine

I edited my answer to give an example. I could not post the whole macro here but I did include the comments talking about the transformation. – Bremser

Well, I have DrScheme 4.2.4 in front of me right now and the macro expander does not expand internal defines at all. Also, my macro definition would not work and be circular then, and it works in PLT thus far. The sample I used was a crude identity function (lambda (x) (define (func a) a) (func x)). I usually have PLT to R5RS. Also, looking at this macro in my own PLT folders, which uses syntax-case, it seems to be R6RS. This is probably the reason why R5RS gives a definition of letrec that does not use define in the end though. Though I don't really see how it would be easier than reversed – Lavine

@lajla You have to make sure to turn off macro hiding at bottom of the expander. Choose custom then disable macro hiding. I just teste your function and it does expand to an R5RS:letrec. It is a syntax case macro that does the expansion but it expands internal definitions to letrec. I suggested reading the introductory quote and the introduction to R5RS again, I think it answers you question. It is not reversed because it necessitates a more define be a more complex primitive form. Which the R5RS tries to limit. "Scheme demonstrates that a very small number of rules ..." – Bremser

Answer 3

R5RS states that the semantics of letrec are exactly the same as those of internal definitions. See the section devoted to the latter for details; I quote the key fragment below:

A <body> containing internal definitions can always be converted into a completely equivalent letrec expression.

Thus defining letrec in terms of internal defines just shifts the problem around.

Also, I find it simpler to define a letrec macro and have lambda desugar internal defines into letrec than to stuff all that complex code into the lambda handler and build letrec on top of that. That's without touching on the question of which is the prettier form of introducing mutually recursive bindings in a non-top-level scope... ;-)

Bait

Answer 4

Good question.

I think the problem with a sequence of define is this:

"The order of evaluation of the expressions expr ... is unspecified, so a program must not evaluate a reference to any of the variables bound by the letrec expression before all of the values have been computed"

Here: http://www.scheme.com/tspl4/binding.html#./binding:s20

Exclosure

But this is what internal (and external) definitions do if I'm not mistaken. That is why they can freely refer to each other and mutually recurse. I also tried all the basic operations like a local factorial, mutually recursive even? and odd? functions, defining a named-let in terms of the letrec2, letting them form closures over their lexical environment which all seems to work. I'm pretty lost. Also, the R5RS standard seems to be defined towards this approach, as in, functions defined in letrec can access the defined functions, but not other values unless explicitly defined in the letrec. – Lavine

I believe you are mistaken. External and Internal defines are different from each other in R5RS. For external defines:(define a b) (define b 2) is a syntax error for the first define since b is not defined yet. For internal defines or letrec (letrec ((a b) (b 2) a)->#<undefined> and should not be a syntax error. The same with ((lambda () (define a b) (define b 2) a))->#<undefined> – Bremser

Hmm, I wanted to be more explicit but I had too little characters, yes, that is a syntax error, but: (define a (lambda (x) (+ (b 2) x))) (define b (lambda (x) (+ 1 x))) is not. As I said, they cannot access values not defined before, but they can access functions that are going to be defined later. This is identical in external and internal defines and (a 2) evaluates to the expected result of 5 in this example. Which is why I raised the point that letrec's semantics seem to have been tailored towards internal defines, as letrec explicitly says it can only refer to functions, not to values. – Lavine

The specification for internal defines in R5RS it says they follow the semantics of letrec. So internal defines are tailored to letrec not the other way around. – Bremser