@lexi-lambda.bsky.social
1519 Followers · 8 Following
computers can be understood • she/her, ⚢ • Chicago
![;; fill-forced-tiles-in-mega-span!
;; : mega-tiles/c mega-placement-bound? mega-placement-bound?
;; #:set-full! (-> mega-index? any)
;; -> (values natural? line-affinity? line-affinity?)
;;
;; Given two mega placement bounds, fills any tiles forced by crosses along the
;; path bridging the two bounds. For example, suppose we have the following row:
;; ☒☐☐☐☐☐☐☒☐■
;; ■☐☐☒☐☐☐☐☐☐
;; This function will fill any tiles that must be filled to connect the two
;; filled boxes:
;; ☒☐■■■☐☐☒☐■
;; ■■☐☒☐☐■■■☐
;;
;; Along the way, it also calculates and returns the minimum number of tiles
;; that must be filled within the span, taking existing filled tiles into
;; account. It also returns two line affinities that can be used to calculate
;; the minimum cost of extending a placement with the given bounds backwards or
;; forwards, respectively. For example, given the row
;; ☐☐■☐☒☐☐☐
;; ☐☐☐☐☐■☐☐
;; then the results of this function applied with bounds (mega-placement-bound 0 2)
;; and (mega-placement-bound 1 5) will be as follows:
;;
;; 1. The returned minimum size will be 5, as at least 5 tiles must be filled
;; to bridge the two bounds.
;;
;; 2. The first line affinity will be #f, as one possible way to bridge the
;; two bounds is
;; ☐☐■☐☒☐☐☐
;; ☐☐■■■■☐☐
;; which fills both tiles in the first column. Therefore, it is possible to
;; extend the filled region backwards to either line at equal cost.
;;
;; 3. The second line affinity will be 1, as filling the tile in the first
;; line above the end bound would require filling 6 tiles, not five.
;; Therefore, extending the filled region forwards is biased towards the
;; second line.
;;
;; Note that the way this function interprets bounds with line 'both or 'either
;; can be somewhat counterintuitive; see Note [Filling forced tiles between
;; placement bounds] for an explanation.](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:fp4zjiflmhhaocasp4yblehe/bafkreiao5pacidkzzimcrpzuxxy3zki6hqltgxw2fyu2oelmsmkj4ytcmu)
![[excerpt from the linked answer that starts partway through]
When this function is called, result_location will record the address of wherever result happens to be stored on the stack. Control then yields to the enclosing continuation prompt, and some time later, the continuation is restored. Unless the stack frame for foo happens to be restored to precisely the same location, the write to *result_location will fail to update the new location of result and will instead clobber whatever now happens to be at that address.
Given this fundamental issue, most programming language implementors consider implementing delimited continuations that capture the C stack to be a complete non-starter.
Doing it anyway
Fortunately, Daan Leijen is not most programming language implementors. His audaciously-named 2017 publication Implementing Algebraic Effects in C describes an implementation strategy for delimited continuations that really do capture and restore C stack frames.
How does he do it? By simply always restoring the continuation to exactly the place it was captured from, of course! In § 4.3 Resuming, Leijen describes his implementation strategy:](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:fp4zjiflmhhaocasp4yblehe/bafkreidgzguyemf525vhz7efgbozyfegnyveufdqjanwuadms35ywhilei)
![Toolbox: Miscellaneous Utilities
This library provides a collection of miscellaneous Racket utilities that I use in my personal projects but I have not felt warrant being published as a separate package. Note that this library is intentionally not published on the Racket package server, as everything in this library should be considered unstable. In projects that use it, I include this repository as a Git submodule, pinning to a specific version.
[table of contents]](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:fp4zjiflmhhaocasp4yblehe/bafkreiddt4asrpqzalltaolcv63xv5vq6h6tvbpezf25pg72mh64w3dl54)