kfl
commented
1 year ago The reason is that the last six cases in canvas.compile isn't tail-recursive. For the given example, it's because the Onto case isn't tail-recursive.
Closed casperbrahe closed 1 year ago
kfl
commented
1 year ago The reason is that the last six cases in canvas.compile isn't tail-recursive. For the given example, it's because the Onto case isn't tail-recursive.
sporring
commented
1 year ago @kfl Jeg har ikke erfaring med dette, men løsningen lader til at være at bruge continuation-passing style (https://en.wikipedia.org/wiki/Continuation-passing_style). Onto i canvas.compile er implementeret som:
| Onto(p1, p2, rect) ->
let dc1 = compile next expFlag p1
let dc2 = compile next expFlag p2
let dc = Lowlevel.(<+>) dc2 dc1 // dc2 is drawn first
wrap Matrix3x2.Identity rect expFlag dcEr følgende en passende CPS omskrivning?
| Onto(p1, p2, rect) ->
let compile' p cont =
cont (compile next expFlag p)
let add' dc2 dc1 cont =
cont (Lowlevel.(<+>) dc2 dc1)
compile' p1 (fun dc1 ->
compile' p2 (fun dc2 ->
add' dc2 dc1 (fun dc ->
wrap Matrix3x2.Identity rect expFlag dc)))@sporring at omskrive med CPS vil altid virke (generelt resultat, der kan bevises, spørg bare Andrzej). Men det er også en "tung" omskrivning, som ofte vil resultere i flere/mange store allokeringer, og koden kommer til at drive mod højre med dyb indentering.
Umiddelbart ser din omskrivning rigtig ud for Onto. Dog så er den lokal og ikke-standard, dvs at den kun virker for Onto og hvad værre er så virker den ikke hvis man blander de ikke-rekursive matches. En mere standard CPS omskrivning ville være at compile også skal tage en continuation som argument (continuations navngives traditionelt k):
| Onto(p1, p2, rect) ->
let compile' p k =
compile next expFlag p k
let add' dc2 dc1 k =
k <| Lowlevel.(<+>) dc2 dc1
compile' p1 (fun dc1 ->
compile' p2 (fun dc2 ->
add' dc2 dc1 (fun dc ->
k <| wrap Matrix3x2.Identity rect expFlag dc)))Et alternativ er at bruge defunctionalisation, og få en mere konkrete repræsentation af continuation (se fx construct.loop eller flatten.traverse i lowlevel.fs.)
Bonus alternativ: Man kan bruge en CPS monade/computational expression til omskrivningen hvis man er til den slags.
kfl
commented
1 year ago @sporring jeg kan evt gøre et forsøg på at omskrive. Jeg ved ikke om jeg får tid i dag, men ellers kan jeg nok se på det på fredag.
kfl
commented
1 year ago Fixed by PR #33
@sporring @kfl
We have found that on windows 10/11 certain examples results in stack overflow. Adjusting the drawLines examples to show 100 lines instead of 1000 solves the issue.
Tested examples are: https://github.com/diku-dk/diku-canvas/blob/main/examples/drawLines.fsx
And circles (Slide 9 on 2.4Lecture.pdf):
Error message from Windows 10: