Facade Functional Programming Suite

Post your working scripts, libraries and tools
[Shambles]
Posts: 74
Joined: 20 May 2014, 21:24

Re: Facade Functional Programming Suite

21 Jul 2019, 11:18

I updated Facade’s Op library today. It is one of the oldest libraries and had not received much attention for a long time.

It became more Lisp-like and less like Python’s operator library, both of which have been inspirations.

Op_Pow was renamed Op_Expt.

Op_Neg was removed. Use Op_Sub with 1 argument instead.

Op_Mul, Op_Div, Op_Add, Op_Sub, Op_BitAnd, Op_BitXor, Op_BitOr, and the relational functions became variadic.

The String library’s case-insensitive relational functions also became variadic.

This should further reduce verbosity. The documentation mentions potentially non-obvious uses for these features.

I noticed AutoHotkey’s floor division operator is broken and corrected Op_FloorDiv accordingly (along with several internal uses :headwall: ). It now always performs floor division and always returns an integer, which is what you want in practice.

I removed Op_Rem because it does not appear to be useful when you have Op_Mod. Floor division and modulo, both based on floor division, have a relationship similar to that of quotient and remainder, both based on truncation. Floor division and modulo are more useful in practice.

I also renamed some other things in an attempt to make the libraries more consistent and easier to understand.

Op_GetAttr was renamed Op_GetProp because AutoHotkey seems to prefer the term property to attribute.

Op_GetItem was renamed back to Op_Get.

The names getattr and getitem were taken from Python, where there are related setattr (for the outside) and setitem (for the inside) methods. This flailing is the result of me trying to find the best way to cope with AutoHotkey conflating arrays and dictionaries, conflating objects’ outside with their insides, and using 1-based indexing. Op_GetProp just tries to read what might be an attribute (i.e. it reads the outside). To be clear, it will not try to use a Get(Key) method to read what it was told. Op_Get tries to use a Get(Key) method to read what it was told if the object is of a type other than Object (i.e. it reads the inside). It will read AutoHotkey's property-key abomination if a Get(Key) method does not exist. The difference can matter if you have an AutoHotkey object with both properties and a Get(Key) method. Array_Get performs index adjustment when reading from Objects so that you can pretend you are using 0-based indexing when you need to calculate an index. Op_Get does not because integers are perfectly reasonable keys and you would not want index adjustment unless you were using an Object as an Array.

The Cons functions were renamed to Prepend functions. This makes them less Lisp-like but hopefully more understandable, like using first and rest instead of car and cdr. I am pretty sure nobody outside the Lisp community wants me to reintroduce that cdadar stuff.

I included a demonstration of using Facade to solve constraint programming problems in the documentation about a week ago and forgot to mention it here. It shows how to solve the 8 Queens problem using Facade’s Streams.
burque505
Posts: 1074
Joined: 22 Jan 2017, 19:37

Re: Facade Functional Programming Suite

21 Jul 2019, 13:11

@Shambles, thank you for your continued work on these libraries. I greatly appreciate it!
Regards,
burque505
[Shambles]
Posts: 74
Joined: 20 May 2014, 21:24

Re: Facade Functional Programming Suite

26 Jul 2019, 13:57

The bitwise functions had their "Bit" prefix changed to just "B". This is more popular according to Google. It seems to have been popularized by LuaJIT.

The not, and, or, if, and while combinators gained a "C" prefix. This stands for combinator and is consistent with the naming of the bitwise functions. The while combinator lost its pre- and post-processing functions. Use the composition combinator to add pre- and post-processing if you want it.

Func_FromDll became Func_DllFunc to try to emphasize the relationship between it and the built-in Func.

String_NatSortPred(A, B) became String_NatSorted(Args*), which is variadic like the other relational functions, and like the other relational functions, it can now easily be used to determine if an Array's elements are in the desired order.

Array_Fill became Array_FromBadArray and Array_Empty became Array_ToBadArray to make them more consistent with Dict_FromObject and Dict_ToObject.

BadArray is not a real type, though it acts like one. Specifically, it acts like a supertype to a proper Array type (i.e. an Array will work everywhere a BadArray can work, but a BadArray will not work everywhere an Array can work). It is just an Array with (potentially) missing elements. I considered calling it SparseArray because AutoHotkey's Arrays are similar to the data structure you would use to implement a dictionary of keys sparse array, but a sparse array should consider missing elements to be 0, which AutoHotkey's Arrays do not. The term BadArray was already in use internally for this concept, and it is short and meaningful, so I chose that.

All this renaming is not without good cause. I am trying to find a way to abstract Facade's collection functions over different types. This would reduce the number of functions programmers using Facade have to learn and remember, and it would make it possible for other programmers to define their own collection types so that they work with Facade's functions.

I believe it is better to have a small number of types and a large number of functions that work with each type than a large number of types and a small number of functions that work with each type. That increases the potential for code reuse. For the last 30 years, mainstream programming has ignored this, first with object-oriented programming and then with functional programming with complex static type systems. Those complex static type systems keep growing more complex as they try to claw back some of the generality they lost by abandoning designs with a small number of types and dynamic type checking. This is a major source of accidental complexity.

However, I also believe it is important to have an adequate number of types (e.g. do not create array-dictionary conflations in the attempt to avoid learning about, or to prevent others from learning about, different data structures), allow the programmer to choose the right type for the job (so that time and space are not wasted), and provide a consistent interface. Not doing these things is another major source of accidental complexity (witness PHP, which is a particularly good example of violating these principles).

When I first set out to write Facade, I knew I really wanted a better programming language, but I was limited to writing functions because writing anything complex in AutoHotkey was too difficult, so I used the best example I was aware of as a model, Scheme. Scheme is a beautiful programming language built atop simple functions that were designed to work well together. Facade currently strongly resembles Scheme without closures or macros and where dynamic arrays are the preferred sequence type instead of singly linked lists.

As I started rewriting Facade’s design document, I was forced to ask myself whether I had lived up to my design principles. This resulted in me noticing several flaws in Facade. How embarrassing to be weighed according to one’s own principles and be found wanting! I have been correcting them since then. I do not want Facade to make things worse or to require its own facade.

I now believe it is better to build a programming language atop simple interfaces designed to work well together than simple functions designed to work well together. This results in a greater potential for code reuse and simpler interfaces for the person using the programming language.

Highly consistent programming languages with the ability to define new types (there is no standard way to do that in Scheme), like Smalltalk, often achieve this without special constructs. You just follow standards to make your type work with everything that already exists.

Unfortunately, AutoHotkey does not work that way and it is difficult to shoehorn in after the fact. For example, how could you add a standard interface for comparisons to built-in types like Array? Could you do it without monkey patching that might break someone else’s monkey patching?

I have some ideas, but I am not sure if they will work. They will almost certainly not work for all preexisting types.

If nothing else, thinking about how to do it is helping eliminate more inconsistency and improving naming (e.g. you would prepend, not cons, to a deque).
Last edited by [Shambles] on 28 Jul 2019, 01:36, edited 2 times in total.
robodesign
Posts: 553
Joined: 30 Sep 2017, 03:59
Facebook: marius.sucan
GitHub: mariussucan
Location: Romania
Contact:

Re: Facade Functional Programming Suite

26 Jul 2019, 16:09

I'm impressed with your work and dedication to the project.

Before I try to actually wrap my head around this library... I have a question. Would it help with increased performance when working with very large arrays? I find that AHK is much faster at creating an array, lets say, of 750 thousand entries than, later, retrieving those entries.

An array of this style :
Arr[1] := "long string"
Arr[2] := "another long string"

Thank you. Apologies if I asked something silly.

Best regards, Marius.
-------------------------
KeyPress OSD v4: GitHub or forum. (presentation video)
My home page.
[Shambles]
Posts: 74
Joined: 20 May 2014, 21:24

Re: Facade Functional Programming Suite

26 Jul 2019, 18:09

robodesign wrote:
26 Jul 2019, 16:09
Before I try to actually wrap my head around this library... I have a question. Would it help with increased performance when working with very large arrays? I find that AHK is much faster at creating an array, lets say, of 750 thousand entries than, later, retrieving those entries.

An array of this style :
Arr[1] := "long string"
Arr[2] := "another long string"

Thank you. Apologies if I asked something silly.
Unfortunately, no. Facade is an abstraction that does not optimize away to precomputed values, and like all such abstractions, it can only reduce the time efficiency of code that uses it. This is true of all abstractions in AutoHotkey because it lacks Lisp-like macros and does not use an optimizing compiler.

This was not a silly question, and the reason for your observation and my answer is deeper than you might expect.

AutoHotkey arrays and dictionaries are conflated. I find the interpreter's code very difficult to understand, but as far as I can tell an Object (a sort of broken dictionary that forms the basis of arrays and user-defined types, but has no relation to other kinds of objects in AutoHotkey) is implemented as a strip of memory containing different types of different sizes where some calculations are done to avoid indexing into the middle of a value and lookups are performed by binary search. The binary search is the reason Objects must store integer and string keys in sorted order. It is also why it is slower than an array would normally be to both build and index.

One thing that makes Facade especially slow at working with Arrays is validating that an argument is, in fact, an Array.

Recall that arrays and dictionaries are conflated in AutoHotkey. By that I mean that an array is just a dictionary with integer keys. They are not even necessarily consecutive integer keys because AutoHotkey arrays can have missing elements. Worse, they may have to have missing elements because that is how you indicate you want to use the default for an argument when calling a procedure variadically (as in F(AnArray*)).

How would you determine that it is safe to treat an array as if they were a real array (e.g. for sorting)? By that I mean the usual data structure that is just a strip of memory and represents a sequence without any missing elements.

As far as I can tell, the only way is to test for the existence of every key between 1 and the value returned by Length() (AutoHotkey, unfortunately, uses 1-based arrays) to determine if there are missing elements, then test if the value returned by Length() is equal to the value returned by Count() to determine if there are integer keys less than 1 or any non-integer keys.

Now consider that every function that is intended to be used on arrays must perform this operation every time it is called.

You might protest that surely the result of the last several validations can be cached!

You could cache the results of this validation by retaining a reference to the last N arrays passed to the procedure that performs the validation, but that would 'leak' an unbounded amount of memory because AutoHotkey does not provide weak references. Only storing the addresses of the last N arrays is unsafe because the address might get reused for a different type. So caching is impractical.

In a normal interpreter for a dynamically type checked language, each value is actually a record that contains a type tag and a value (and potentially other information). The type tag is normally an integer representing a built-in type or a reference (pointer) to the class of a user-defined type. That means type checking is a simple integer equality test, not some complex algorithm. Normal interpreters have different type tags for different types. Normal interpreters also do not hide errors and attempt to continue executing. Unfortunately, AutoHotkey is not normal, and its differences from the norm are not desirable except for its I/O and self-extracting archive features.

I care about the efficiency of the algorithms I chose in Facade, and most should be reasonably efficient when AutoHotkey makes that possible, but I did not attempt to squeeze out every drop of efficiency, and efficiency is a lost cause in this programming language (e.g. Whitespace can reduce efficiency by up to 35% according to the manual!). I am aware that the MinKBy and MaxKBy algorithms could be more time efficient for large values of K if they used heap data structures, however that would have made them less efficient for the much more common case of small values of K and it would have made the code much more complex (i.e. much less maintainable). Similarly, I could have used TimSort instead of merge sort for sorting arrays, and that would have made sorting more efficient for all array lengths, but it would have made the code vastly more complex (i.e. vastly less maintainable).

I also made some conscious design decisions that harm the efficiency of Facade, specifically, the decision to always return a copy of a mutable data structure from functions that can return a different value for that data structure. For example, an array of less than 2 elements can be returned as is from a sorting algorithm, but if programmers forget that and mutate the array that was returned, assuming that the sorting algorithm always returns a copy because it usually does, they can create subtle defects in their code that are quite difficult to track down because they only occur when arrays of less than 2 elements are involved. Safety is more important than efficiency.

Most engineering properties of code are more important than execution time efficiency. When execution time efficiency is of a concern, most real world programs are I/O bound, not processor bound, so no amount of optimizing the code (except potentially the I/O-related code) will help. Also, C programming culture, dragged into the mainstream by Unix, tends to value execution time efficiency above everything else including correctness and human time efficiency. If you want the most time and space efficient code and you don't care about correctness, it is impossible to beat the empty program so you may as well stop programming.

Facade is more about improving the time efficiency of humans than improving the time efficiency of computers. The primary forces that brought it into existence were the desire for error reporting, the desire for less dangerous, more practical constructs to build programs atop, and the inability to get any help from those that maintain AutoHotkey.

Nothing about it is academic or frivolous. In fact, it is only based on functional programming because that happens to work better in this context. AutoHotkey's functions are less broken than its objects, and functional programming is less dangerous than object-oriented programming in the face of multiple 'threads' resulting from hotkeys being pressed.
robodesign
Posts: 553
Joined: 30 Sep 2017, 03:59
Facebook: marius.sucan
GitHub: mariussucan
Location: Romania
Contact:

Re: Facade Functional Programming Suite

27 Jul 2019, 02:46

Thank you for your comprehensive reply.

I admit, I'm in the camp of those who are all about the execution efficiency... Yet, I see the value of your library, because ahk does too many things "abnormally", as you previously explained. I just hope v2 will improve things.

Best regards, Marius.
-------------------------
KeyPress OSD v4: GitHub or forum. (presentation video)
My home page.
[Shambles]
Posts: 74
Joined: 20 May 2014, 21:24

Re: Facade Functional Programming Suite

27 Jul 2019, 15:23

robodesign wrote:
27 Jul 2019, 02:46
Thank you for your comprehensive reply.

I admit, I'm in the camp of those who are all about the execution efficiency... Yet, I see the value of your library, because ahk does too many things "abnormally", as you previously explained. I just hope v2 will improve things.
In 1996, with the introduction of the Pentium MMX, PCs became SIMD machines like supercomputers had been for some time. It was at that time that programming languages believed to be fast like Fortran or (to a lesser extent due to potential pointer aliasing) C became obsolete.

In 2001, with the advent of GPGPU, processing that needed to be fast started moving to graphics cards. This eventually led to standardized programming languages for this purpose, first OpenCL, now Vulkan.

These modern array programming languages work a lot like (a subset of) Facade in that they are designed to process entire arrays at once. The primary differences are anything that involves pointers will be heavily restricted or eliminated so that the compiler can recognize opportunities to optimize better, the only types that are supported well will be numbers, and the underlying hardware works like the programming language (processing several hundred elements of an array at once).

That last part, that the hardware works like the programming language, reduces the cost of the abstraction providing whole array processing.

What has been lost is the awareness that there is more to computing than processing arrays of numbers and that hardware should serve humans instead of humans serving hardware. In the past, when progress in hardware beyond gate shrinkage occurred, there were computers designed to efficiently process pointer-heavy data structures (like the Lisp machines) or dictionaries (like the Goodyear STARAN), among other things. The party line is that these machines were inferior to the PC because the PC eventually outperformed them. The truth is that only occurred because economies of scale allowed the PC to use more gates to do the same work (i.e. to be less efficient) at a lower price. It is not that the PC is somehow the 'correct' design.

With that we lost the awareness that it is not so much that some programming languages are less efficient than others (though the more that can change at run-time the less efficient the programming language can be made) as there is a greater difference between some programming languages and the hardware they run on than others.

And with that the demonization of overhead began. Overhead is in much the same position as side effects among modern programming language zealots. They like to forget that a program that performs no processing at run-time is useless. They like to forget that a program that performs no side effects is useless. These things are problematic, yet they are also the only reason programs have value.

In short, if you really care about performance you should be using Vulkan today. It is the only programming language that works the way modern fast hardware does, and therefore has minimal overhead. Just don't lie to yourself about whether you really care about performance and continue to use AutoHotkey, C, or C++ as if they were somehow capable of being efficient on remotely modern fast hardware (again, that ship sailed in 1996). This is entirely separate from whether their implementations are performant, and AutoHotkey's implementation is very far from being performant (recall that bit about properly formatting your source code costing you up to 35% of your performance... no other programming language implementation I know of has that problem).
[Shambles]
Posts: 74
Joined: 20 May 2014, 21:24

Re: Facade Functional Programming Suite

13 Aug 2019, 17:39

String_NatSorted(Args*) became String_IsNatSorted(Args*) so that it is consistent with other predicates that are not operators.

Dict_Merge, Dict_Union, Dict_Intersection, Dict_Difference, and Dict_IsDisjoint became variadic to reduce verbosity.

I improved the error reporting for Math_Log(X) and Math_Ln(X).

There were many other changes to the Type Checking and Facade libraries, but most of them would go unnoticed to people using them. The regular expressions used should be faster.
burque505
Posts: 1074
Joined: 22 Jan 2017, 19:37

Re: Facade Functional Programming Suite

13 Aug 2019, 18:14

@Shambles, thanks yet again. Your efforts are not going unappreciated, believe me. Not everybody is a diehard OOP fan. I like Brian Will's videos on the topic, like this one.
Regards,
burque505
User avatar
Chunjee
Posts: 239
Joined: 18 Apr 2014, 19:05
GitHub: Chunjee

Re: Facade Functional Programming Suite

04 Sep 2019, 06:04

Wow I read all of design.txt and major portions of this thread. I feel like I am walking in your shoes.

Thankfully most of it is over my head, but I do run up on some of the inconstancies and seemingly odd ahk choices with unsettling frequency.


I will be using this! As soon as I figure out how to...
[Shambles]
Posts: 74
Joined: 20 May 2014, 21:24

Re: Facade Functional Programming Suite

07 Oct 2019, 15:28

I added Array_FilterApply, Stream_FilterApply, Array_MapApply, and Stream_MapApply today. The 8 Queens example is slightly shorter because of them.

If you have a sequence of values that you wish to execute a function with an unsuitable signature on, there are many ways to go about it.

If the elements are Arrays, applying the function to each element (for filtering or mapping) might suffice. That is what the new functions do. They save you from having to manually write the specialization of Func_Apply every time.

The need for this often arises when using the list of successes technique because it usually involves generating Arrays of arguments (as in the 8 Queens example).

If the elements of each Array are not in the order the function requires, you should probably use Func_Rearg to get a copy of the function that matches the order of the Arrays' elements. This should not happen when you are generating Arrays of arguments because you can control the order.

If the elements of the sequence are anything other than Arrays, you should probably use Func_ApplyArgsWith to get a copy of the function that can extract the information it needs from each element.

If anyone reading Facade’s implementation wonders why Func_Rearg is not implemented atop Func_ApplyArgsWith, the answer is that Func_Rearg can construct variadic functions. I did notice the relationship.

Feedback is welcome.
[Shambles]
Posts: 74
Joined: 20 May 2014, 21:24

Re: Facade Functional Programming Suite

09 Nov 2019, 01:45

I removed Func_BindMethod(Method, Obj, Args*) and included Func_CCond(Clauses*).

Func_MethodCaller(Method, Args*) can do everything Func_BindMethod(Method, Obj, Args*) can do and more. It is rarely useful to bind both the object and the method (except when using a data structure as a function, and that is what Func_Applicable(Obj) is for). It is often useful to bind only the method (e.g. to filter or map over the elements of a collection).

If you do want to bind both the object and the method and Func_Applicable(Obj) is inadequate, you can use
Func_MethodCaller(Method, Args*).Bind(Obj)

Assume T1, E1, T2, E2, T3, and E3 are suitable function objects.

The following code is theoretically equivalent. Both construct a function object that performs case analysis.

Code: Select all

CaseAnalysis := Func_CIf(T1, E1
               ,Func_CIf(T2, E2
               ,Func_CIf(T3, E3
               ,Func_Const(""))))

Code: Select all

CaseAnalysis := Func_CCond([T1, E1]
                          ,[T2, E2]
                          ,[T3, E3])
The latter is less verbose and more readable. It is also less likely to cause stack overflow. AutoHotkey's call stack is only about 384 calls deep. Applying a function constructed by Facade often consumes several levels of that call stack. Functions constructed by Func_CIf(Pred, ThenFunc, ElseFunc) are nested (consuming more call stack space the deeper evaluation goes into the "if" chains). Functions constructed by Func_CCond(Clauses*) are flat (performing only one call at a time).

I expect Func_CIf(Pred, ThenFunc, ElseFunc) will be used much more often than Func_CCond(Clauses*) because the former is often what is needed, but Func_CCond(Clauses*) is important for completeness.

If you have not experimented with Facade because of the rate of design churn, please start doing so now. Almost all effort is being put into finishing the Design and Lessons Learned documentation. The design is not changing much any more. I am only trying to correct design flaws and implementation defects. You could consider the current state a release candidate. It is important that I receive feedback on what works well and what does not before problems become more difficult to correct.
[Shambles]
Posts: 74
Joined: 20 May 2014, 21:24

Re: Facade Functional Programming Suite

08 Dec 2019, 07:23

I updated the following libraries:
* Type Checking
* Facade

Type Checking's Is(Value, Type) function became IsType(Type, Value). This makes specializing it with Bind as easy as possible and it is more consistent with the other type checking functions. This also makes it possible to port to AutoHotkey v2. I included an Is.ahk file to prevent existing code from breaking for now. If you only use Type Checking indirectly, you do not need it. If you do use Type Checking directly, please migrate your code to the new function soon. Backwards compatibility will eventually be removed.

I developed the Type Checking library so that Facade could report errors because AutoHotkey does not. I unquestioningly adopted the is operator's design from AutoHotkey v2. I only started noticing problems when using it myself and when documenting its design.

Facade's directionless functions (e.g. Fold, Fold1, Scan, Scan1, and GroupByWFold1Map) now specify a (left) direction. This makes the interface slightly simpler and more consistent. No functionality changed, only names.

Facade originally used dictionaries that did not preserve order. I did not notice the names could be improved until now.

These are the kinds of problems people using the libraries might notice. If something seems wrong, please say something.

Return to “Scripts and Functions”

Who is online

Users browsing this forum: need4speed, robodesign, Tre4shunter and 65 guests