First fortnite 31/07/2021

I initally tried to research walther recursion as I had heard it was the normal way of specifying functions for total functional programming languages. But total functional programming and it's languages are poorly documented and the original paper on walther recursion was thousands of dollars so I gave up the effort.

I then wrote up the language specification (the most up to date link is here: https://docs.google.com/document/d/1VaQIqCRbHQcMX1CR2NVf0SVfpH9rvEA5TUewIfpVD3I/edit?usp=sharing). To show off here is the syntax bnf:
<program> ::= <line> ‘;’ <program> | <line> ‘<EOF>’
<line> ::= <primtive_definition> ‘=’ <expr>
<line> ::= <non-primitive_definition> ‘=’ <expr>
<primitive_definition> ::= NAME ‘(‘ <data_list> ‘)’
<non-primitive_definition> ::= NAME ‘{‘ <data_list> ‘}’
<data_list> ::= <successors> ‘,’ <data_list> | <successors>
<successors> ::= ‘s’ ‘[‘ <successors> ‘]’ | NAME | 0
<expr> ::= <primitive_call> | <non_primitive_call> | <successor_expr> | NAME
<primitive_call> ::= NAME ‘(‘ <list> ‘)’ | NAME ‘()’ 
<non_primtive_call> ::= NAME ‘{‘ <list> ‘}’ | NAME ‘{}’
<successor_expr> ::= ‘s’ ‘[‘ <expr> ‘]’ | 0
<list> ::= <expr> ‘,’ <list> | <expr>
(Assuming name is a non empty arbitrary string and that normal whitespace may be put anywhere when desired. note: the successor constructor is called ‘s’)

This syntax and this definition was written with the prototype in mind, in which there is only one type being the numbers defined in the peano arithmetic (successor functions). 
I also wrote the Lexer and Parser. I also decided that a stack based intermediate code would make some of the later execution engine easier to write. So I wrote one up. I then started on the execution engine but I made an architectural mistake. I wanted to avoid oop for spiritual reasons but instead of using oo I just used tuples. This ended up having all the inefficiencies of oo without the readability benefits. So I now have to re-write the execution engine. I will probably end up switching to oo, as the readability is that atrocious. Although I am considering other options with less of a price on my soul. 
  
In terms of the timeline I am roughly a little ahead of where I aimed to be, but the PDD timeline was very ambitious so I need to still work fast and hard. 
  
If you want to read the code please reference the github though I am particularly proud of my intermediate code generator which I have pasted below.
  
def func_call_gen(arr_in):
    if len(arr_in) <= 1: return arr_in
    return [(arr_in[0], arr_in[1])] + \
        reduce(lambda a,b: a+b, list(
                map(func_call_gen, arr_in[2])
        ))

def stackify_line(line_in):
    return ("DEFINE", func_call_gen(line_in[1]), func_call_gen(line_in[2]))

def Generate_IC(lines_in):
    return list(map(stackify_line, lines_in))

This code takes a parse tree (it's embedded lists in this representation) and converts it to a list of definitions with a definition being tuple ("DEFINE", arguments, function_definition) with both arguments and function_definition being a linear polish notation equivalent of the program. I am particularly proud of the func_call_gen function. I think it's simple and clear. 

The github for the code is https://github.com/Glubs9/total_functional_programming_language. 

Comments

Post a Comment

Popular posts from this blog

Fifth post

 This week I was reading a bit about maths and other things and discovered that my approach to primitive recursion has already been done. It is called structural recursion https://en.wikipedia.org/wiki/Structural_induction. (this is about my definition of primitive recursion, not the integration. Also as a side note, I am using primitive recursion in place of terminating recursion because I am lazy with my terminology, I apologize). I also realized that my project wasn't that interesting and that my type system especially was kinda lame. I feel as if I can go harder and make my type system more interesting and worth doing. I also feel that the amount of time I've given myself too much time so I'll end up not really doing much for most of it. Due to these reasons, I have been exploring some type theories to see if there's anything I can mangle into a type system for this assignment.  The main candidates (so far, this is early days of research) are: - Hindley Milner ...
Read more

Twelfth post (end post)

This is the conclusion of the project. As I write this I have completely finished the language to where I wanted it to be. I am very happy with how it turned out. I am currently trying to describe the project mathematically and write a proof that the non-deterministic execution environment that I wrote does in fact halt.  It was fun to work on a long-form project like this, I have never done something as massive as this before and it was cool to do. I think I got to 1.2k lines which doesn't sound like much but it is 1.2k lines of some serious thinking. Not a lot of filler code in the project. On that note I did really have to think hard creating this, there were a lot of algorithms that I didn't have the time to read about and learn so I had to write them myself. It was challenging and very fun.  I think at the start of this project I didn't really have the strongest grasp on the areas I was talking about, but as time has gone on, especially lately, I have come to really un...
Read more

Fourth Post

I did a little bit of commenting and added a tutorial to make the project suitable to submit. During this I discovered a problem with my defininition of primitive functions, but it is too late to fix before the prototype is due. I am planning to update the defintion to probably just be the primitive functions, although I am considering two alternatives, substructural or hilbert recursion. I then submitted the project and will do no further work for a few weeks while I catch up on other assignments. note: I did miss last weeks blog post and probably did the work listed above then, it's hard to remember, it's been very hectic. Sorry I'll try to stick closer to the one post a week format from now on.
Read more