5 ms·

I agree short/dense/simple/linear code has huge benefits that most programmers haven't experienced, simply because it is so hard to create (especially in some l

I agree short/dense/simple/linear code has huge benefits that most programmers haven't experienced, simply because it is so hard to create (especially in some languages). Your code is both impressive and inspiring. What additionally interests me is the combination of points-free style and the kind of data structures you're processing in an array-biased language, could you give an insight on what that is like to work with? In particular, I presume from your description, and only a conceptual familiarity with APL, that most or all of this code is "functional", i.e. all data structures exist as values passed between the composed functions, and nowhere else (no globals or similar). I'd love to hear more about the predominant data structures and what shape they take. Somewhere else you mention Quad-XML, which seems to be a way to represent trees as arrays, with each element pre-fixed with its depth. I presume you use this for the AST? What kinds of operations are simpler on these arrays, and which are harder, compared to tree data structures used in other languages? For example, addressing the Nth child from a parent could be harder, since you have to search past the other children? I could imagine that operations like "set all fields X of the tree to Y" are a lot easier since no tree traversal is required. Does your ability to quickly refactor rely on this functional nature?

arcfide 10y ago
I've structured the points free style so that it's basically like working with any expression, I just am working with expressions that build functions instead of expressions that build values. The compiler is very functional in style, and the entire core of the compiler is just a single data-flow graph if you get right down to it. I'll discuss this more in the live session, but they operate in the Nanopass style over a mostly monotonically growing (along the field axis) matrix representation of the AST whose core "columns" correspond to the core columns of the Quad-XML format. Rather than a single "attributes" column I flatten the attributes column into multiple main columns, but otherwise its the same, and the "Xml" function in my compiler helps to convert to Quad-XML format and serialize the AST for those who want to store intermediate AST results. The challenging part, which is part of what the research is one, is doing tree transformations in an efficient manner. Because this is a pointerless representation, you have to be careful in how you design the structure to ensure that you maximize locality and parallelism. If you read my "Key" paper in the publications: https://github.com/arcfide/Co-dfns#publications https://github.com/arcfide/Co-dfns#publications You'll see how I manage one of the most tricky elements. By using the techniques I describe in that paper, I can perform arbitrary computation over any group of sub-trees in the AST selected by their parent-child relationships in a data-parallel fashion. This is largely accomplished by converting that depth vector in the Quad-XML format into a "path matrix" which allows for computing and reasoning about the parent child relationships of any two arbitrary nodes in the AST without reference to any other parts of the tree, without pointers. I can then optimize that path matrix representation for either ease of construction or for performance over certain types of common operations. That's really one of the most significant elements and sort of blows the whole problem wide open and actually makes it possible to do what I'm doing so easily. Once I replace the standard recursive transformation idioms with this new set of Key/Path Matrix idioms, I use the Nanopass architecture to allow refactoring. Nanopass is a style of compiler construction that builds on the idea of functional programming. So, yes, the compiler itself is very very functionally oriented, and that's a very big part of the refactorability of the code. But also, since I have done so in a way that results in so few variable names, that's also a major component, and it means that code is often highly "independent" and can be removed or deleted easily.
- Aardappel 10y ago
  Thanks, read your paper, that answers most of my questions. Fun to see such a completely different way of working with trees. Agree that point-free makes refactoring almost trivial.. one thing it shares with Forth style languages :)
arcfide 10y ago
As for what is harder and what is not, it's not really so much a matter of easier and harder. By replacing all of the normal techniques with equivalent ones, it's more just programming in a different style that nets more benefits. I wouldn't say it's fundamentally easier, because the hardest part of any problem is reasoning about the problem itself, but I do think that you get a lot of benefits for writing in this way that is not really harder than the traditional methods, either. There's a sort of 1 for 1 replacement of traditional programming techniques with new techniques. The new techniques solve similar problems, but are more parallel, and more concise.

arcfide 10y ago

I've structured the points free style so that it's basically like working with any expression, I just am working with expressions that build functions instead of expressions that build values. The compiler is very functional in style, and the entire core of the compiler is just a single data-flow graph if you get right down to it. I'll discuss this more in the live session, but they operate in the Nanopass style over a mostly monotonically growing (along the field axis) matrix representation of the AST whose core "columns" correspond to the core columns of the Quad-XML format. Rather than a single "attributes" column I flatten the attributes column into multiple main columns, but otherwise its the same, and the "Xml" function in my compiler helps to convert to Quad-XML format and serialize the AST for those who want to store intermediate AST results. The challenging part, which is part of what the research is one, is doing tree transformations in an efficient manner. Because this is a pointerless representation, you have to be careful in how you design the structure to ensure that you maximize locality and parallelism. If you read my "Key" paper in the publications: https://github.com/arcfide/Co-dfns#publications https://github.com/arcfide/Co-dfns#publications You'll see how I manage one of the most tricky elements. By using the techniques I describe in that paper, I can perform arbitrary computation over any group of sub-trees in the AST selected by their parent-child relationships in a data-parallel fashion. This is largely accomplished by converting that depth vector in the Quad-XML format into a "path matrix" which allows for computing and reasoning about the parent child relationships of any two arbitrary nodes in the AST without reference to any other parts of the tree, without pointers. I can then optimize that path matrix representation for either ease of construction or for performance over certain types of common operations. That's really one of the most significant elements and sort of blows the whole problem wide open and actually makes it possible to do what I'm doing so easily. Once I replace the standard recursive transformation idioms with this new set of Key/Path Matrix idioms, I use the Nanopass architecture to allow refactoring. Nanopass is a style of compiler construction that builds on the idea of functional programming. So, yes, the compiler itself is very very functionally oriented, and that's a very big part of the refactorability of the code. But also, since I have done so in a way that results in so few variable names, that's also a major component, and it means that code is often highly "independent" and can be removed or deleted easily.

Aardappel 10y ago
Thanks, read your paper, that answers most of my questions. Fun to see such a completely different way of working with trees. Agree that point-free makes refactoring almost trivial.. one thing it shares with Forth style languages :)

arcfide 10y ago

As for what is harder and what is not, it's not really so much a matter of easier and harder. By replacing all of the normal techniques with equivalent ones, it's more just programming in a different style that nets more benefits. I wouldn't say it's fundamentally easier, because the hardest part of any problem is reasoning about the problem itself, but I do think that you get a lot of benefits for writing in this way that is not really harder than the traditional methods, either. There's a sort of 1 for 1 replacement of traditional programming techniques with new techniques. The new techniques solve similar problems, but are more parallel, and more concise.