I’ve been trying to implement letrec metacircularly as follows [`(letrec ([,bind ,val]) ,body)
(letrec-eval body (let ([rec-env env])
(let ([val (letrec-eval val rec-env)])
(set! rec-env (lambda (x)
(if (eq? x bind)
val
(env x))))
rec-env)))] (rest of the code is https://github.com/iambrj/eopl/blob/master/src/recursive/letrec.rkt#L44\|here), but this doesn’t quite work - val keeps being evaluated in the environment before set! . Could someone please help me figure out how I can go about doing this?
> val keeps being evaluated in the environment before set! what I mean is, for example this does not work "letrec.rkt"> (letrec-eval '(letrec ([double (lambda (x)
(if (zero? x)
0
(+ 2 (double (- x 1)))))])
(double 5)))
; double: : missing binding [,bt for context]
(let ([rec-env env])
(let ([val (letrec-eval val rec-env)])
...)) Here you need to extend rec-env with a binding of bind to something before you evaluate (letrec-eval val rec-env) .
After obtaining the value, you will need to replace the original something.
The best way to do this depends on your representation of environments.
I’m using procedures, as in (define empty-env
(lambda (x)
(error x ": missing binding")))
(define (ext-env u v env)
(lambda (x)
(if (eq? x u)
v
(env x)))) also, I don’t quite understand why doing a set! on rec-env itself shouldn’t work? Could you please explain why set! -ing inside the environment would work, but set! the entire environment would not?
Well, for starters the semantics of letrec are (from R5RS): (letrec <bindings> <body>) Syntax: <Bindings> should have the form ((<variable1> <init1>) ...), and <body> should be a sequence of one or more expressions. It is an error for a <variable> to appear more than once in the list of variables being bound. Semantics: The <variable>s are bound to fresh locations holding undefined values, the <init>s are evaluated in the resulting environment (in some unspecified order), each <variable> is assigned to the result of the corresponding <init>, the <body> is evaluated in the resulting environment, and the value(s) of the last expression in <body> is(are) returned. Each binding of a <variable> has the entire letrec expression as its region, making it possible to define mutually recursive procedures.
The first step is there fore to bind the variable to a fresh location.
Given your representation of environments you can do this by binding it to a box containg false: (box #f).
(let ([rec-env (ext-env bind (box #f) env)])
(let ([val (letrec-eval val rec-env)])
...))
You can then use set-box! to change the value inside the box.
Also when evaluating a reference to the variable, you will need to use unbox to get the stored value back.
So why does the current (set! rec-env ...) not work? Well, it is too late. The semantics say the environment needs to be extended first and then val is evaluated.
What was the end result ? I’m curious ; this looks like material that would interest me
@soegaard2 thank you very much for the help, my evaluator can now handle non mutual recursion :smiley:. I shall try to generalize to mutual recursion now.
I think I have a working version now https://github.com/iambrj/eopl/blob/master/src/recursive/letrec.rkt#L30, I would be grateful if someone is willing to do a code review :)
I think @plragde is here occasionally
It looks great. I like you have added tests.
If you need some more tests, there are few letrec tests here: https://github.com/soegaard/meta/blob/master/runtime/racket-eval.rkt#L1412 and https://github.com/racket/racket/blob/46a191df038244199f83f2bb1235beb8ca137f9a/racket/src/ChezScheme/nanopass/tests/alltests.ss#L102
so I actually ended up jumping directly to implementing a hierarchy of universe types. I implemented a function sort-check to ensure that a given value had the type (Type _), and then used that when synthesizing
then when synthesizing an arrow I checked what tier the left and right hand side of the arrow was at, and took the maximum of the two.
(define (sort-check ctx expr)
(match (strong-reduce ctx (type-synth ctx expr))
[(Type n) (Type n)]
[_ (error 'sort-check "cannot check ~a as sort in context ~a\n"
(pretty-print-expr expr)
(pretty-print-context ctx))]))
I’m being bitten by something here.
#lang racket/base
(define (my-apply p args)
(apply p args))
(define (apply . ls)
(error 'apply "not the primitive apply"))
apply-order.rkt> (my-apply + '(1 1))
; apply: not the primitive apply I thought the first procedure would use the apply from racket/base. But it doesn’t. I thought lexical scope… meant that. What basic lecture have I missed here?
Since you’ve defined apply in your module, you’ve shadowed the original apply from racket/base. In module definitions or in a letrec, functions can be considered to share the same scope.
The scope of the module shadows the module language.
You could do (require (only-in racket/base [apply rkt:apply])
and then use rkt:apply in my-apply
So my understanding would be correct if I were talking about variables, but not procedures?
IIRC There isn’t any distinction in identifiers.
I mean, variables local to procedures.
I put in [my] mind that lexical scope takes the nearest value of a name and fixes that where the name occurs.
Sorry, I got that wrong. What I said about module and letrec scope apply to all variables, not just procedures.
@kellysmith12.21, I understood that I can overwrite procedures defined elsewhere — that’s nice. I’m understanding now that Racket’s semantics won’t let me have the same name pointing to two different procedures.
I can easily see now that it’s a good idea!
The form define has two purposes: declaring and initializing. What you saw, is that the declaration of apply means that is possible to define my-apply even though apply hasn’t been initialized yet. That happens later.
Now referring to a variable that haven’t been initialized is an error, so calling your my-apply like this is an error:
#lang racket/base
(define (my-apply p args)
(apply p args))
(my-apply + '(1 1))
(define (apply . ls)
(error 'apply "not the primitive apply"))
;; apply: undefined;
;; cannot reference an identifier before its definition
Because otherwise my code becomes order-dependent, which is bad. I also see the suggested solution by @samdphillips. Thanks. So now I just need to organize in my mind that lexical scope doesn’t mean what I thought it did. Maybe @soegaard2 is seeing my trouble. Let me check.
Yes, @soegaard2, I see that.
When I say #lang racket/base, I thought apply was already defined. So in the definition of my-apply , lexical scope would make sure that it refers to base’s apply , regardless of the fact that I define a new apply later on.
This is feeling like an exception to lexical scope. In a module, the value of something defined will be last definition in the module.
It’s not an unreasonable expectation. The current behaviour is a design decision. If I remember correctly, the initial implementation simply signalled an error in this situation. One had to explicitly filter out variables defined in the #lang language. For a single bindings this worked fine, but it was cumbersome for large amounts.
The current behaviour is more practical. If a user defines something called apply he probably mens his own apply when he refers to it :wink:
But note that lexical scope isn’t broken - you can still determine the scope by lexical means - here the scope just happens to be large - the entire module.
I’m actually happy with the behavior and it was my expectation there that was unreasonable. I basically expected a behavior that is too error prone. (My code would be order-dependent and two apply in the same module would point to different procedures.) Nevertheless, I thought that lexical scope would make that happen.
It does feel like an exception to me, but I do want this behavior of define. Also, getting an error every time we overwrite a procedure does seem a bit annoying. Besides, it’s powerful to be able to overwrite a procedure.
Yes, at times it is quite convenient.
Fwiw, your expectation is closer to how ML identifiers bind, and is why you have to either (a) write things bottom up (later definitions can only use earlier ones) or (b) use the and keyword to create (possibly) mutually-recursive declarations.
Personally, I think your expectation is not unreasonable at all. From my limited usage of OCaml, that’s exactly how it works
Yep
SML/NJ, but same idea :)
define is preferred by the style guide to let, because it doesn’t cause the code to drift rightward.
But there are two uses of define: use it like let, and use it like letrec
I love myself a good lexical binding though
I personally use it like let more, so I’m kinda annoyed with the current behavior.
> define is preferred by the style guide to let, because it doesn’t cause the code to drift rightward. Oh, is this true? I’m coming to Racket from Haskell, so I tend to use let everywhere (well, mostly let*), but if define is generally used instead of let, maybe I should switch over to using define instead.
I do appreciate that it doesn’t cause code to drift rightward.
Yes, it looks like this is true. Here’s the reference from the style guide: https://docs.racket-lang.org/style/Choosing_the_Right_Construct.html#%28part._.Definitions%29
I didn’t know this style guide is a thing. I’ll have to make sure I read through it.
In an internal definition (<https://docs.racket-lang.org/guide/define.html?q=internal-definitions#%28part._intdefs%29|guide entry>, <https://docs.racket-lang.org/reference/syntax-model.html?q=internal-definitions#%28part._intdef-body%29|reference entry>) a define is used as sugar for a let, so you can treat them the same.