Eleventh post

This week I made the semantics checkers. Normally when I write programming languages and code generally, I don't really care about errors or anything like that. This is the first time I have ever written any semantics checking and I feel proud of myself for doing it. My programming language feels so much more professional with compilation errors and everything like that. It is cool and I am having fun. 

I did most of that stuff Monday and Tuesday of last week. I then tried to start working on the presentation and I wanted to write an example of how the non-determinism worked. Although the first example I tried pointed out the glaring flaw in my initial idea. Basically, the problem is that we rely on how fast something runs to delete branches and the like. As we have tried to sidestep the halting problem, we are making guesses that aren't true. The other way you could think about the problem is that a function running forever and a function running normally is indistinguishable (via the halting problem). This has left me in a situation where I have to call it somewhere. And wherever I call that will lead to incorrect answers. I have the logic working, it's the collapsing of the non-deterministic execution tree that causes problems. 

I think I have discovered the core flaw with my plan and I now understand the choices made by total functional programming languages like codata much better.

This was a good learning experience for me.

I am going to finish this up, write the example with all the changes that make it work; and embrace the mistake.

edit (only 1 hour later): I FIXED IT! I am the god of code. all computers must kneel before my wrath! I'm kidding but fixing the bug that led to the example not working and having it work. The initial idea of non-deterministic stack stuff isn't 100% practical but honestly it's not that bad. This example also begins to highlight some of the logic programming stuff as well but wow! My gosh. A screenshot of the example is below:

Something that might lose you as you read this is that I added a feature to manually split the stacks using # in front of a function name. This could have been done using the normal primitive, non-prim stuff but it was clearer and easier to do it manually.

I can't believe this works.

The example generates a list of even numbers below the input number. The bit that makes it special is that the function to check if a number is even runs forever on odd numbers. It outputs the list!!!! how crazy is that!!! that's even possible. Wow. I must say it feels really good to have something done like this. Even with all the extra stuff you have to do. IT works! that's wild

Here's the output

It was run with every number below 7. 

Translate to normal list and number notation the output reads [6, 4, 2, 0].  I just cannot believe that actually worked. I am very pleased indeed.

I don't know if I told this blog about the repl! Last week I wanted to improve the repl so I made it really good by using rlwrap which allows input history and line editing using arrow keys. I also catch ctrl+c as a keyboard interrupt in my own language. I also have exiting being done with ctrl+d (like in ghci!). The repl is really good and honestly quite good. Very professional. Honestly this language is really complete at this point. It pretty much does the bare minimum to be a useable language. The only things it really needs now is a more complete API for accessing other stuff like files and the internet and stuff.

The other thing I want to do is show how we can do logic programming. Probably by doing 4 colouring of graphs.

I am glad and finished with this post. The next post is the last one in this series.

edit: returning to the problem of when to collapse the tree, I can think of three different ways of doing it. Easiest is just to put a time thing, like 2 seconds until this function is destroyed. The other idea is that we could do a time efficiency, like O(n^2) type thing. This would probably be better, although it would require a rather drastic re-write to the executor. The last thing we could do is introduce dependent typing (maybe using the cfg but probably not. Need something turning complete I think) which would do a good job of pruning the tree. I am thinking specifically around the example from before where we had to prune it depending on the length of the list which is something that dependent typing is good at. Although I won't be able to implement any of this until after the assignment. I would also like to understand martin lof type theory better before trying dependent typing.

edit (4 hours later): you know what, it's done. I am incredibly satisfied with what I did and I think the example I made proves it's worth enough. I don't really need to do anything else. I don't even know if I will have the time to cover it in the presentation. As well as the fact that it's no longer presenting to any professionals or anything so it's not like I have to pull out all the stops. I will stop myself here. Stop the perfectionism or whatever. I am very proud of what I made and it is finished. I will now continue on to the presentation and other stuff around submitting it.