ChildsplayOSU / bogl

Haskell implementation of the BoGL language
https://bogl.engr.oregonstate.edu
BSD 3-Clause "New" or "Revised" License
7 stars 1 forks source link

Duplicate Values in Env #161

Closed montymxb closed 3 years ago

montymxb commented 3 years ago

This is related to the issue in #159, and the solution in #160. During that process I came across some suspicious behavior in the way the runtime environment is modified over a computation. It seems that repeated instances of existing local parameters, value equations, and function equations are pushed onto the env redundantly.

In the case of the fix in #160, the issue was related to BoGL attempting to extract a reference or function from the env by checking it from top to bottom. Normally, this isn't a problem, but for each subsequent let, if-then-else, while, function application, or reference, the corresponding evaluation environment may be modified depending on what follows next. This modification is always pushing new elements onto the env as far as I can tell, and so certain aspects like while loops can rapidly increase the environment's size. Despite this, the lazy aspect of haskell appears to let us get away with only needing to evaluate just enough to do a lookup for the first occurrence of a name, and so everything works okay. An example of this would be as follows for an example with a local 'x' and a couple functions:

[("x",True),
("x",True),
("x",True),
("maxX",5),
("explosion",\["x"] -> while True do and(x, x)),
("maxX",5),
("x",True),
("maxX",5),
("explosion",\["x"] -> while True do and(x, x)),
...]

This needs some investigation to see if this is a problem or not later on, but currently it seems benign. It would seem that modifications to the environment, if they produce a new environment under the Reader monad, could be done as replacements instead of additions, but that's just speculation. It is possible that due to lazy evaluation we may not have to worry about this at any point.

montymxb commented 3 years ago

Noting that Martin made an excellent suggestion that we should migrate the environment to a map of key:value pairs instead of a list. This would likely give us a small performance bump.