miloignis/kraken
1
0
Fork 0
Code Issues Pull Requests Packages Projects Releases Wiki Activity

Commit Graph

  • 7e7a7c3b32 Merge branch 'master' of github.com:Limvot/kraken Nathan Braswell 2022-05-08 01:34:38 -04:00
  • 8dd28370c1 Ported RedBlack-Tree based on our new match. Seems to work, though compiled version crashes on memory-out-of-bounds while interpreted works - will have to debug later Nathan Braswell 2022-05-08 01:34:33 -04:00
  • 746933f21e Update README.md Nathan Braswell 2022-05-07 20:19:18 +00:00
  • ca68826fbc Clean up and rearrange Nathan Braswell 2022-05-07 16:09:16 -04:00
  • 08c01257f3 Add matching on quoted symbols Nathan Braswell 2022-05-07 15:07:03 -04:00
  • 6140a7a006 Comment out un-val error message generation, was taking an absurd amount of space in final binary Nathan Braswell 2022-05-07 14:52:32 -04:00
  • 9bb6104952 Much more real match with arrays and unquote, also added unquote to parser and made log return its last argument Nathan Braswell 2022-05-06 00:35:31 -04:00
  • c3b2a852b7 Fix debug not being called because of the function index renumbering, add calling debug for calling not a function in eval. For some reason this crashes redebug :/ Nathan Braswell 2022-05-03 23:25:56 -04:00
  • 172512f447 Fix array inequality case Nathan Braswell 2022-05-03 22:49:50 -04:00
  • 2a6ee6d8e4 Fix inlineing se not being set to nil (but default 0 by wasm) so it always equaled 0 Nathan Braswell 2022-05-03 22:09:37 -04:00
  • d420b6491f Fix regression - was using the wrong error when blocking recursion and treating as real error instead of stop recursion fallback Nathan Braswell 2022-04-25 09:19:14 -04:00
  • 223147f699 Initial inlining working - fib_let went from .4 something to .138. Suspect the remaining slowdown over fib is extra refcounting calls, but unsure. Compile error on fib_manual, need to see whether it was this change or the earlier find fixes Nathan Braswell 2022-04-25 09:07:42 -04:00
  • 40008ffa23 Add a palindrome test file. Marcus "Mark" Godwin 2022-04-25 01:45:07 -04:00
  • 8b3cab7a2f Fix multiple cond/slice bugs revealed by LotusRonin's new find testcase Nathan Braswell 2022-04-24 20:39:51 -04:00
  • 8a876a7b29 Merge pull request #6 from Limvot/md5_hash_func Nathan Braswell 2022-04-23 13:42:22 -04:00
  • 6c51639c6e Thread through inline_symbols and inline_level to prep for inlining impl Nathan Braswell 2022-04-23 01:41:52 -04:00
  • 18250e716f Ah, the remaining calls were to =. Added 'inlining' the = and comp_helper loop into repeated calls to comp_helper_helper, eliminating the param array overhead. Now fib only allocates 10 times (instead of 4 million), and runs in .107s, finally beating Python handilly and becoming about 2x as slow as Chez. Feels like a decent spot for now, and that was most all of the low hanging fruit. The only thing left now is inlining of user functions to get fib_let performing as well - it looks glacial now at .4s because of the 2 remaining closure calls that the let expands to Nathan Braswell 2022-04-21 01:09:10 -04:00
  • 1c9944acab Implement some string funcs Marcus "Mark" Godwin 2022-04-21 00:30:51 -04:00
  • 0cb52eb0b4 Add inlining of add and subtract, and now might be beating Python, though not by a statistically significant amount with the number of tests. Fib is still allocating 4 million times or so, which is weird, since +&- should have been the last calls to do so. Time to track that down Nathan Braswell 2022-04-20 23:47:36 -04:00
  • ec9f8d9d10 Implement unwrapped static calls! Modest speedup of 0.50 -> 0.43, I belive because calls to + and - still create the arrays. Still less than expected, though Nathan Braswell 2022-04-20 02:27:22 -04:00
  • c2dbac67f5 Add, and move setup to, wrapper func for each user func. Next need to actually call the non-wrapper version if applicable... Nathan Braswell 2022-04-19 02:00:56 -04:00
  • 5cdaafebe2 Change lapply to optionally take in an explicit env, make it optional for vapply so they match, then tweak Y such that it threads the dynamic env through, then implement eta-reduction in the compiler backend. This provides about the same speedup again from the Y elimination, as it's kinda the other half for fully getting rid of Y such that there's just static recursive calls. fib.kp went from 1.7 -> 1.1 -> 0.5, and fib_let similarly. fib.kp is now faster than fib_manual, but just by a bit. Nathan Braswell 2022-04-17 01:52:01 -04:00
  • c259031110 Merge branch 'master' into md5_hash_func Marcus "Mark" Godwin 2022-04-15 00:39:11 -04:00
  • 562770baf7 Add 32 bit int to hex string and leftrotate impls. Marcus "Mark" Godwin 2022-04-15 00:35:00 -04:00
  • 3009b62f5e Mostly eliminating Y combinator at compilation time by putting function values in memo early if we have env_val and we put in the anti-recursion hash from the partially evaled call that returned this comb, and then compiling calls also looks for its recursion-stopped hashes in memo. To finish the transformation, I need to perform an Eta-reduction as well, but we've already got over half of the speedup from eliminting the Y part and just leaving (lambda (& y) (lapply <now_const_func!> y)). Nathan Braswell 2022-04-14 02:49:00 -04:00
  • 8b21a6c55e Use hyperfine to benchmark, add builtin_fib as a comparison for how fast we could try to be Nathan Braswell 2022-04-13 00:25:53 -04:00
  • c6071dbbe1 bunch more testcases Nathan Braswell 2022-04-12 00:14:09 -04:00
  • 55afa8977e Add rust example Nathan Braswell 2022-04-11 16:07:11 -04:00
  • 645b9f7172 Perhaps over-compilicated attempt to only reify envs when actually necessary. Also got a speedup from simplifying params creation when neither varadic nor uses de, which is really the main speedup here. Hopefully this is still a step forwards that will become more apparent with the removal of reifing params too, and inlining. Might be being foiled by the recursive call going through Y or something. Did see a reduction in allocations with the no-reifying thing, but only from 35mil to 34mil. Seems like it should be more with the number of leaf calls in fib, not sure whats up. Maybe there's more overhead going through Y than I thought and its all of that? Nathan Braswell 2022-04-11 02:17:17 -04:00
  • d92f774c33 Add help message based on Marcus's suggestion Nathan Braswell 2022-04-10 10:45:52 -04:00
  • 1149363e62 Add debug_levels and turn off stack_traces by default, but save enough info about the last interaction with the top-level loop to enable re-running to problem spot with debugging on if it happens, and it works! This is the first step towards the opt/non-opt-wrap work while maintaining debugability Nathan Braswell 2022-04-09 00:45:58 -04:00
  • 7116012be1 Better debug parameter message Nathan Braswell 2022-04-06 00:24:34 -04:00
  • dcc81ac2eb make prints of top level strings not include the quotes Nathan Braswell 2022-04-06 00:13:46 -04:00
  • db7c258d39 Make printing stack/env nicer Nathan Braswell 2022-04-05 23:59:18 -04:00
  • 29f02810f8 More debug work, including adding the code tracking throught marked_array for the stack traces, calling into debug when eval has a symbol not defined error (just the first error spot to do this, we can add them all gradually), allowing abort for debug, and adding (exit val) for debug that resumes execution Nathan Braswell 2022-04-05 00:30:03 -04:00
  • 99e24ac6a0 Add rough stack trace Nathan Braswell 2022-04-04 01:35:06 -04:00
  • 00299a8d3a Fixed read, started in on a debug function with a repl and ability to exit. Haven't actually added any other debug functionality, but thought about how to do stack traces (linked list of env functional val pairs). Nathan Braswell 2022-04-02 01:01:34 -04:00
  • d5b11ca037 compile static calls to static wasm calls Nathan Braswell 2022-04-01 01:06:40 -04:00
  • b87afc6a12 Round allocated blocks up to the nearest 8 words, and split blocks that are >= 2x needed number of words. Now only allocates 1 wasm page for both compiled and interpreted versions at fib 30, a 269-538x improvement! Nathan Braswell 2022-03-30 21:27:01 -04:00
  • b85873b240 Fixed a terrible bug where turns out I used the same name for a block and a parameter in the comparison meta-function - they share the same namespace in the wasm DSL, so when I used it like a parameter in a loop it resolved to the number of scopes between the statement and the block'th parameter which had the same type and the calculation worked fine, but it overwrote the parameter I thought wasn't being used and called a function later with. Nathan Braswell 2022-03-29 23:49:51 -04:00
  • cb41fe3fc8 Added a singlely-linked list with the value-created 2 word header to mallocd blocks that tracks everything ever malloced, and an assertion on free that the refcount is 0. Found what I think was a (the?) key source of corruption - drop moving the ptr forwards to drop subs, but then freeing that moved ptr. Now fixed, things look much less weird, but there are remaining memory leaks to track down Nathan Braswell 2022-03-28 23:57:38 -04:00
  • f5ba367096 Debugging refcounting, fixed 3 mem leaks so far Nathan Braswell 2022-03-24 01:58:49 -04:00
  • 5c1473d32c Continue brain-dumping psudocode and notes. I think I've got most everything critical now Nathan Braswell 2022-03-21 23:50:59 -04:00
  • b3122f62d1 Started brain-dumping psudocode and descriptions of interesting points/contributions, the reason all macro-like combiners should be partially-evaled away, the invarients we must maintain, etc Nathan Braswell 2022-03-21 01:03:54 -04:00
  • 0c554078bd Found the offending code for the infinate recursion, though not exactly why it happens. Minimal reproducer seemingly found Nathan Braswell 2022-03-20 20:50:39 -04:00
  • eb3a732f99 Add fib_let test and script to run all of them. Indeed, the version with the let is worse when interpreted and the same/better when partially-evaled and compiled Nathan Braswell 2022-03-20 16:01:38 -04:00
  • 6fa2c44619 Add no_compile option to test more staight dynamic eval with a fib and fact test. Compiled is faster, though only 2x on fib - I imagine the hot inner loop isn't actually doing a lot that can be partial evaled, it's the outside. Will need tests that excercise more Nathan Braswell 2022-03-19 01:48:58 -04:00
  • f0d68c3efe Finally implemented runtime vau with varadic, which involved a half-rewrite Nathan Braswell 2022-03-17 23:20:22 -04:00
  • f10be4511f Add support for de to runtime vaus as well as parameter length checking. Do need to add support for varidac functions... Nathan Braswell 2022-03-17 00:35:21 -04:00
  • 1a2ecd65b0 Implemented runtime vau, but still need to add support for functions taking in the dynamic env (gotta shift those env arrays around) Nathan Braswell 2022-03-16 02:10:29 -04:00
  • 67ba716003 Add runtime version of cond Nathan Braswell 2022-03-15 02:13:42 -04:00
  • 31ee20be7b Implemented wasm eval and fixed slice Nathan Braswell 2022-03-13 22:56:04 -04:00
  • 1b220023bc Fix cond to not die on guarded errors, implement a new if in macro-style, port some more over to_compile.kp. Stopped just before 'vau, which seems to loop forever or somesuch Nathan Braswell 2022-03-13 15:11:30 -04:00
  • 947d854ebb Implement array functions (len idx slice concat) for strings in wasm versions. All work - note I think slice is broken (or at least exposes brokenness) for arrays (not the newly adding strings)! Nathan Braswell 2022-03-13 01:40:46 -05:00
  • d1b6e520f9 Added support for strings to array functions for evaluator (compiled is next) Nathan Braswell 2022-03-12 20:19:00 -05:00
  • d87f292c1c Additional optimization using intset for env_stack, some small bugfixes regarding not making a marked_array out of components that errored, moved over a lot of code to to_compile.kp. Nathan Braswell 2022-03-10 01:06:44 -05:00
  • a08415e1e6 Cleanup & some demo code for presentation Nathan Braswell 2022-03-08 15:55:59 -05:00
  • 7fed3a58f5 Added more to to_compile.kp and runtime started growing again - main bottleneck was the silly using lists as sets thing, changed the small-int uses of these to a new custom bitset and brought the time from 47s back down to 6s. There is a remaining hotspot where partial_eval_helper matches needed_for_progress vs the bitset, but that'll have to wait for tomorrow. Thinking of maintaining a env_stack bitset and adding a bitset_union_nonempty function. Note the new bitset does use some cons/car/cdr operations that'll be a bit different in Kraken, which I'll need to look at. Maybe when porting I can just use indexing if there's not a great way to unify them. Nathan Braswell 2022-03-08 02:54:26 -05:00
  • 90fe8e1bfa Bunch of optimization that took us from 3:50 to 0:04 for the current to_compile.kp. Mainly pulling len out of hot loops and using a naive binary tree instead of alists for maps Nathan Braswell 2022-03-07 02:10:42 -05:00
  • c8c9bba429 Have nodes carry around information about the additional non-real envs that aren't real because of a non-real env in their chain. These envs don't show up in needed partial idxs, since it's the up the chain env that actually needs progressing, but allow us to do check-for-env-id normally in essentially O(1). This made the function much more efficient by number of invocations and cut some of the other hottest functions by nearly an order of magnitude, but only took 15-20 seconds off of a 4 minute compile. This is unfortunate (Chez profile only shows invocation numbers, not time numbers, so this is hard to tell) but at least this part is better now. Nathan Braswell 2022-03-06 03:22:35 -05:00
  • bf1f81cdf3 Implement and and or. Looks like nil doesn't currently count as false, based false? and it seems to be avoided even with the compiled 'vcond, though it looks like it shouldn't (oh this is probs it being partially evaled ahead of time, isn't it?) Anyway, we might want to finish this and remove it from vcond too Nathan Braswell 2022-03-03 09:28:01 -05:00
  • 8cdf41826b Starting to port over & self-host! Nathan Braswell 2022-03-03 00:33:25 -05:00
  • 4a273c9ba2 Bigfix error infinite recursion, error printing, wrap_level not being in hash_comb, extend to_compile.kp a bit Nathan Braswell 2022-03-02 01:44:20 -05:00
  • dd0463d059 Comment out generated debugging and other log based code for large speedup - tried several other optimizations but they counterintitively made things worse Nathan Braswell 2022-02-28 23:47:02 -05:00
  • 3f26a3ad7d Finish porting mif and fixing up other inconsistancies. Fix bug for emitting signed numbers as hex in compile. Runs correctly in both Chez and Chicken interpreter now, which Chez being about 3x faster Nathan Braswell 2022-02-28 00:26:30 -05:00
  • ea15f48d6f Implement dlambda and correct dlet. More attempt at Gambit Nathan Braswell 2022-02-23 16:43:03 -05:00
  • 54097ac074 Port the let+ macro from http://www.phyast.pitt.edu/~micheles/scheme/scheme15.html over mostly, and it works in both Chez and Chicken! Will massage some more to get it to be the same as our previous dlet, but it is working! Nathan Braswell 2022-02-23 00:56:46 -05:00
  • f8bab2ada5 I caught the Chicken compiler red handed, it's compiled version has zip change behavior part way through, caught in the act with some prints. Where it does so changes based on optimization level, which is a bad sign. Starting a (hopfully quick) port to more standard scheme - looking to support Chez and Gambit in addition to Chicken, with at least some commented out code if not some sort of conditional compilation. We're off to a roaring start with define-syntax broken in Gambit 4.9.3, from 2019, but there was a new version released last month that I think should fix it. Nathan Braswell 2022-02-22 02:19:17 -05:00
  • 58f3d7858e Rework the destructuring lambda in what I'm now calling the true-macro-style, so that helper functions don't close over the dynamic env and cause it to not partially evaluate away Nathan Braswell 2022-02-20 23:42:09 -05:00
  • 2874be3332 Fix the bug with de getting seperate dynamic envs, now unified but no opts for now (doing it seperetly was broken because of tyring to access it from inner closures. Also add a lot more runtime logging Nathan Braswell 2022-02-20 22:12:21 -05:00
  • 7ce2db21ff Actually, make sure to always include it if there are other progress_idxs Nathan Braswell 2022-02-19 00:43:27 -05:00
  • 6cd9dd0831 Move over much more code, including the tricky destructuring lambda which revealed bug in the need_for_progress system - a call that takes in the dynamic env that failed and had to be re-constructed would set attempted on the call to true, but would not note the dynamic environment as one of the needed-for-progress idxs. Often I think it would be anyway, so this didn't come up too often, and of course finally revealed itself when doing nested let/lambda destructuring stuff. Fixed by having attempted record not just true or false, but in the case where it's a call that takes in the dynamic env, makes it that env's id, which gets added to the for_progress_idxs. Nathan Braswell 2022-02-19 00:14:36 -05:00
  • dd2191f75d Made vapply and lapply primitives for efficiency/partial eval reasons. It means they can exist in emitted code without calling out to eval, which is good. to_compile.kp now both compiles and runs! Now to add more Nathan Braswell 2022-02-15 23:16:27 -05:00
  • fd37fa9b00 Had missed handling the empty call case () as an error in compile, which will happen when specutively compiling as code a nil that should be passed unevaluated, etc Nathan Braswell 2022-02-12 12:10:08 -05:00
  • d5ea55fa08 And we're compiling again! Smaller tests seem to work, including compiling and running a minor factorial (not Y comb). to_compile.kp errors out with a weird nil coming from somewhere, that will be have to be investigated tomorrow. Nathan Braswell 2022-02-12 02:05:45 -05:00
  • bd00933763 Fixup cond to partially eval as much as it can without incuring infinate recursion! Nathan Braswell 2022-02-11 02:21:18 -05:00
  • 69fd587989 Fixed the Y combiner not partial evaluating as far as it should thing by adding infinite-recursion-blocking-hash-tracking to the needed_for_progress infrustracture. Only arrays need to track it, since at function boundries you won't want to reevaluate it anyway until the function is called. Having a hash from the IRBHT be not in your memo counts as a #t true need to re-partial eval. Nathan Braswell 2022-02-10 01:15:02 -05:00
  • 325afd773e Added partial_evaling to drop_redundent_veval (a bit hacky, have to pass partial_eval to it to break mutual recursion & had to add a 'force' option to partial_eval to force re-evaluation for situations where drop_rdundent_veval has changed something but the needed_for_progress wouldn't pick up on it.) This theme continues with the current problem with the Y combiner test, which is that recursion protection trips on the partial eval of the recursive application (x x) in the Y combiner, but it doesn't actually need any other external values, so when the time comes that it is actually needed as a value it skips it and ends up only evaluating a single level even for a value-only top level recursive invocation. Finally, still need to figure out a better situation for cond/vcond to partially evaluate itself without triggering even more infinate recursion (that's truely value-only, without a cond to stop it). Nathan Braswell 2022-02-09 22:49:06 -05:00
  • 6e18a66e3b Make drop_redundent_veval recursive, but realized we now need to re-partial eval in the cases where it does change. Added fail points with error messages for things I know I still need to do - veval is in a tricky space now because it *can't* have the main calling code re-evaluate it's parameters, but with the new prim comb works like regular change, it does. Maybe a negative evaluation level? Nathan Braswell 2022-02-09 01:11:13 -05:00
  • 5a67c704e0 Bugfixes and initial implementation for cond. Many tests passing now, though cond should further evaluate it's members without causing infinite recursion and drop_redundent_veval needs to be able to traverse for drops, since we allow returning whole function calls Nathan Braswell 2022-02-08 23:51:00 -05:00
  • 9daff0f482 Work in progress commit to make it so that anything unevaluated is already a value of the code that it is, which is the proper way to not have to ensure_unval which is fundamentally broken and causes mis-partial-evals. Refactor parameter evaluation and have prim combs mostly use that as well. Remaining is implementing cond properly and fixing bugs/typos Nathan Braswell 2022-02-08 02:48:40 -05:00
  • 931dd9a8f5 Implement drop_redundent_veval and make veval properly re-partially-eval and update the env it's called with. Y combiner test added and works now, map still seems not to, about to look at it Nathan Braswell 2022-02-07 00:31:51 -05:00
  • 31a8002a11 Finally excise what I belive to be the final exponential behavior, namely by adding memoization and better traversals to check_for_env_id_in_result Nathan Braswell 2022-02-06 16:34:47 -05:00
  • 76065d1957 Implement veval and combiner_return_ok enhancements, now let4.3 behaves like the proper macro expansion. Compiling our test doesn't work though, it doesn't partial evalaute the vaus away as expected - changing let1 implementations does have an effect. Will need to investigate, as well as add support for compiling away veval Nathan Braswell 2022-02-05 12:14:13 -05:00
  • 7310eeaee3 Fix up inverted condition on combiner_return_ok, fix regression on error checking for parameters in calls. Hopfully proper now, just needs better combiner_return_ok (both memo and allowing further partial eval) and allowing-further-partial-eval for eval Nathan Braswell 2022-02-04 01:28:18 -05:00
  • a8f8f9df89 Removed check_for_symbols, which was a bad idea generally. Simplify into combiner_return_ok, and fix *eval bug* - it didn't check for any sort of combiner_return_ok like thing, even though it's doing the same thing as a function call basically, by changing the env something is evaluated in. Also just re-write eval using the parital_eval wrapper, enforce it taking in total-values. Nathan Braswell 2022-02-03 02:41:14 -05:00
  • dd28087818 Some more updates based on feedback Nathan Braswell 2022-02-02 01:41:19 -05:00
  • 6f3d8d514b Added quote example Nathan Braswell 2022-02-01 00:50:36 -05:00
  • c05a7bd2d5 More slides work, expanding examples, proof reading, adding explanation Nathan Braswell 2022-01-31 23:42:27 -05:00
  • 2f395926d3 Fix Nathan Braswell 2022-01-31 18:35:14 -05:00
  • 3086ad4b01 First draft of presentation Nathan Braswell 2022-01-31 00:08:37 -05:00
  • df76ae51e2 Start to fill in Abstract/Introduction/Related Work/Issues/Solution Nathan Braswell 2022-01-30 20:20:16 -05:00
  • 7f220c97b8 Finally make a clean sweep and delete / organize old files. Add skeleton for LaTeX formal writeup in doc/ and change license (since this is all new code from the past few years) to BSD-2-Clause-Patent Nathan Braswell 2022-01-30 16:57:21 -05:00
  • 315ae20698 Clean up strip, have default memory allocation scale based on constants, added more until the next bug found, map seems not to be partially evaluating properly Nathan Braswell 2022-01-28 00:26:46 -05:00
  • 90750933fc Fixed the recursion! Memo has moved to just being the infinite recursion detector based on body and inner-env Nathan Braswell 2022-01-27 21:54:15 -05:00
  • 2746e1ca75 contains_symbols is/was exhibiting exponential behavior - probs memoizing or using needed_for_eval could fix it, but also it doesn't normally have to be called, so just doing that got us a 50x speedup or so Nathan Braswell 2022-01-26 23:43:50 -05:00
  • c8df8742d1 Actualy I'm just going to disable memo except for recursion detection Nathan Braswell 2022-01-26 22:45:16 -05:00
  • 3748610dea Can finally compile let! The memoization of partial_eval was allowing re-introduction of fake envs somehow. Temporarily disabled, also added a bunch of debugging aids like str_strip only printing envs in full the first time, need_value being passed through compile to fail faster, etc Nathan Braswell 2022-01-26 22:41:29 -05:00
  • 9bc658a1a4 Ah, found additional infinate recursion. In the process of fixing the second, trickier one, caused by compile & partial eval together. Should be fixed? but there's a nil coming out somewhere Nathan Braswell 2022-01-26 01:55:38 -05:00
  • d4752eddb4 Fixed the bug! ctx has env in it, and was being returned upwards, messing up the environment of subsequently compiled things. The key is to make sure things that modify the environment (compiling functions) return the env it was passed in the ctx Nathan Braswell 2022-01-25 16:51:06 -05:00