Skip to content

Environment closures - #7

Merged
8dcc merged 5 commits into
copy-referencesfrom
env-closure
Feb 15, 2025
Merged

Environment closures#7
8dcc merged 5 commits into
copy-referencesfrom
env-closure

Conversation

@8dcc

@8dcc 8dcc commented Feb 15, 2025 •
edited
Loading

Copy link
Copy Markdown
Owner

Add support for environment closures. This pull request needs the changes of the copy-references branch in order to work.

The environment of a lambda used to be created when the lambda was created, but its parent environment was not set until the lambda was called. This was a problem because, in the following code:

(define get-inner
  (lambda (a)          ; Outer lambda
    (lambda (b)        ; Inner lambda
      (+ a b))))

(define inner (get-inner 10))  ; Call to outer lambda
(inner 20)                     ; Call to inner lambda

The parent environment of the inner lambda was set whenever it was called, so in that example b was not declared, and the last expression returned an error.

After this PR, the parent environment is set when the lambda is created, so the new environment layout is:

 Global env
     ^
     |
Env of 'outer'
     ^
     |
Env of 'inner'

Rather than:

 Global env         Global env
     ^                  ^
     |                  |
Env of 'outer'     Env of 'inner'

The apply diagram needs to be updated.

Changes

  • Add is_used member to Env, for storing whether or not it's being used somewhere else.
  • Unmark environments in gc_unmark_all (by setting is_used).
  • Mark environments in gc_mark_expr as used.
  • Don't collect expressions if their associated environment is marked as in use.
  • Set the parent environment on lambda creation, instead of on call.
  • Mark each expression of a lambda's environment whenever the lambda is marked for garbage collection.
  • Add pool_item_is_gcmarked, move pool_item_is_free to expr_pool.h, make arguments of pool_item_flags constant.

8dcc added 5 commits February 15, 2025 14:02
@8dcc
Don't free lambdas whose environment is in use somewhere else
a607592 
The code of this commit is a bit messy, as explained in the comments.

* Add 'is_used' member to 'Env', for storing whether or not it's being used
  somewhere else.
* Unmark environments in 'gc_unmark_all'.
* Mark environments in 'gc_mark_expr'.
* Don't collect expressions if their associated environment is still in use.
@8dcc
Set the parent environment on lambda creation, instead of on call
0c6eca2 
This commit doesn't currently work, because we still work with copies.
@8dcc
Merge branch 'copy-references' into env-closure
cc6970a
@8dcc
Merge branch 'main' into env-closure
0f374d3
@8dcc
Mark expressions inside a lambda's environment
c7ccde3 
From 'gc_mark_expr'.
@8dcc
8dcc merged commit 8da6f98 into copy-references Feb 15, 2025
@8dcc
8dcc deleted the env-closure branch February 15, 2025 14:06
@8dcc

8dcc commented Feb 15, 2025

Copy link
Copy Markdown
Owner Author

Even with this PR, at commit 00e2a2d, the Y combinator crashes the program by trying to access a freed environment.

Code

Y combinator:

;; For more information on the Y combinator, see my blog article:
;; https://8dcc.github.io/programming/understanding-y-combinator.html

(define Y
  (lambda (f)
    ((lambda (x) (f (lambda (n) ((x x) n))))
     (lambda (x) (f (lambda (n) ((x x) n)))))))

(define fact-generator
  (lambda (self)
    (lambda (n)
      (if (equal? n 0)
          1
          (* n (self (- n 1)))))))

(define fact
  (Y fact-generator))

(fact 5)

Valgrind backtrace:

==630579== Invalid read of size 8
==630579==    at 0x10D6D6: env_get_binding (env.c:269)
==630579==    by 0x10D74C: env_get_binding (env.c:278)
==630579==    by 0x10D7B7: env_get_flags (env.c:290)
==630579==    by 0x1145F9: is_special_form (eval.c:43)
==630579==    by 0x114773: eval_function_call (eval.c:96)
==630579==    by 0x1149D8: eval (eval.c:164)
==630579==    by 0x114789: eval_function_call (eval.c:104)
==630579==    by 0x1149D8: eval (eval.c:164)
==630579==    by 0x1112C3: lambdactx_eval_body (lambda.c:313)
==630579==    by 0x111370: lambda_call (lambda.c:324)
==630579==    by 0x114CAD: apply (eval.c:229)
==630579==    by 0x1148C3: eval_function_call (eval.c:145)
==630579==  Address 0x4befc18 is 8 bytes inside a block of size 32 free'd
==630579==    at 0x4848A3B: free (vg_replace_malloc.c:989)
==630579==    by 0x10D2E7: env_free (env.c:202)
==630579==    by 0x110E2F: lambdactx_free (lambda.c:209)
==630579==    by 0x10F860: free_heap_expr_members (expr_pool.c:79)
==630579==    by 0x11063A: pool_free (expr_pool.c:255)
==630579==    by 0x11233F: gc_collect (garbage_collector.c:119)
==630579==    by 0x10A823: repl_until_eof (main.c:102)
==630579==    by 0x10A9F2: main (main.c:136)
==630579==  Block was alloc'd at
==630579==    at 0x48457C2: malloc (vg_replace_malloc.c:446)
==630579==    by 0x111B63: mem_alloc (memory.c:30)
==630579==    by 0x10AA28: env_new (env.c:52)
==630579==    by 0x110C27: lambdactx_init (lambda.c:131)
==630579==    by 0x11560D: prim_lambda (prim_special.c:248)
==630579==    by 0x114C90: apply (eval.c:219)
==630579==    by 0x1148C3: eval_function_call (eval.c:145)
==630579==    by 0x1149D8: eval (eval.c:164)
==630579==    by 0x114789: eval_function_call (eval.c:104)
==630579==    by 0x1149D8: eval (eval.c:164)
==630579==    by 0x1112C3: lambdactx_eval_body (lambda.c:313)
==630579==    by 0x111370: lambda_call (lambda.c:324)

@8dcc

8dcc commented Feb 16, 2025

Copy link
Copy Markdown
Owner Author

The issue mentioned in the previous comment was fixed in commit 5758c96.

@8dcc 8dcc mentioned this pull request Feb 16, 2025
Merged
8dcc added a commit that referenced this pull request Feb 16, 2025
@8dcc
Merge pull request #8 from 8dcc/copy-references
8527988 
Work with references, instead of always returning copies. This change was
possible thanks to #5 (which needed #4), #6 and #7. Some changes were merged
into this 'copy-references' branch in #7.

Major changes:

* Remove most calls to 'expr_clone', for working with references instead of
  copies.
* Return or store references in 'car', 'cdr', 'cons', 'nth', 'quote' and
  'backquote' primitives.
* Add proper environment closures, setting the parent environments whenever a
  lambda is created, not when it's called. See #7.
* Change how GC handles lambdas, add 'is_used' member to 'Env'. Mostly included
  in #7, but not completely (see 5758c96).
* Don't mark globals ('g_nil', 'g_tru' and 'g_debug_trace_list') for garbage
  collection, since their references are being stored in the environment.

Minor changes:

* Add 'gc_mark_env' and 'gc_mark_env_and_parents' static functions to
  'garbage_collector.c'.
* Add an 'Env*' parameter to 'lambdactx_init', remove it from
  'lambdactx_eval_body'.
* Don't make the 'Expr*' parameter of 'env_bind' and 'env_bind_global' constant.
* Add closure test to 'test/lambdas.lisp'. See #7.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

1 participant

@8dcc