š¾ Archived View for soviet.circumlunar.space āŗ zwatotem āŗ snapshot āŗ solution āŗ visual.gmi captured on 2024-12-17 at 10:31:49. Gemini links have been rewritten to link to archived content
ā¬ ļø Previous capture (2024-09-29)
-=-=-=-=-=-=-
Current document describes Visual Solution to the Expression Problem.
Since its inception, the bulk of research focused on Expression Problemās modularity aspect with solutions delivering methods of extending the existing data types and operations through additive means, such that it is possible to extend a domain contained in a compiled module. While research on this aspect can turn out very influential on the patterns of use of external libraries and evolution of code ecosystems, there are other aspects of Expression Problem that may prove beneficial, when tackled.
The aspect this work focuses on is code organization in a self-contained program, i.e. extension does not necessarily occur across module boundaries (although modularity is also considered as a secondary concern). As organization I will understand a property of code that mandates the placement of syntactic units (especially method implementation) in wider grouping structures and sequentially within these structures. Two programs can be equivalent in semantics, but differ in organization, such that one is subjectively more pleasant to work with, than the other. Organization can either be a result of language rules, conventions of a framework or design pattern (potentially one directed at solving the Expression Problem), or a design decision taken deliberately by the programmer.
If we look at organization schemes provided by existing solutions, we can distinguish three styles of organization.
Outcomes of these organization schemes may not be fully satisfactory in every scenario, even in the lifecycle of one software product. For illustration, let us construct such an example.
Let us assume a software with a type hierarchy and a set of operations on these types. As the software evolves, in arbitrary order new types and operations are added, and existing ones change their scope (e.g. User stores more personal detail, collision function calculates collision result instead of Boolean value).
For operations where data types are added or changed object-oriented organization would be optimal, as it would allow work on a contiguous fragment of code, without navigating to distant parts of the code and separate files. However, for all operations involving addition or change of operations object-oriented organization mandates navigation through all units or organization.
When an operation is added or modified, functional organization is optimal, because it localizes all implementation variants of a given method, contrary to object-oriented organization, however with a degradation of experience to changes and addition of data types.
Procedural organization would seem an appropriate choice for all additions. It allows to group the newly added implementations regardless whether they are connected by a concern of common data type, or common operation. This strength, however, causes a natural formation of an unpredictable organization pattern (see Figure 3.1), which complicates the process of modifying types/operations, as it is hard to localize implementations and navigate between them.
Example in Figure 3.1 demonstrates, how the organizational aspect of code is virtually unsolvable. While it is possible to align the code with some concern, at a later stage in the program development a cross-cutting concern will necessarily render the organization suboptimal.
To solve aforementioned problems this work takes inspiration from spreadsheet software, specifically a construct known as a pivot table, which allows to view the same data aggregated with different criteria in a visual way. While the data appears different to the user of the pivot table depending on the aggregation axis, filtering, sorting and grouping settings, the represented data stays constant throughout these operations of the pivot table. Similarly, presented Visual Solution will rely on the separation of the program semantics, kept in the underlying environment, and the program representation ā visible to the programmer.
Previously implementations of visual programming for code organization appeared for Smalltalk language (Borne, 1993; Giffen & Tomek, 1997). Smalltalk as a dynamic language is not an object of the expression problem. However, these examples are still an invaluable study subject in visual programming, which is a sparse research direction.
The action, programmer can take in programming environment of Visual Solution, can be divided into two categories: transformative and non-transformative. The former are actions that change the semantics of the underlying program representation, causing it to behave differently in runtime or change external public interface in case of library development. The latter is any action of changing the view of the program, that does not change semantics of it. This distinction is important, as it can lead to confusion, if not communicated clearly to the programmer.
The specific implementation of the program representation in programming environment can differ, from a binary in-memory representation to a serial representation, such as programming language code, or low-level intermediate code. That representation is used as a compilation or interpretation target, depending on the implementation specifics. The Visual Solution is therefore a layer that can be applied to an existing solution, to improve its extensibility.
The programming model of the solution consists of three main constructs: classes, methods and concepts. For the rest of the chapter, these will be italicized to avoid confusion with classes, methods and concepts in their colloquial meaning as well as in existing programming languages.
Class is defined as either a primitive, or a tuple of classes. This declaration makes classes, equivalent to product types in languages with algebraic type systems. A class, which is a primitive is an arbitrarily defined set of values. Definitions of specific primitive can differ depending on specific implementation of Visual Solution.
In this programming model classes represent data structures, just like classes in object-oriented programming.
Model does not contain an equivalent to union types, as their role of providing polymorphism is fulfilled through concepts (described later).
Function is a general recursive function from a tuple of classes to some set R. Method is a tuple (P,š½), where P is (pā,ā¦,pā) ā a list of parameters (each parameter consisting of requirement and name) and š½ is a set of functions. For each combination of classes (cā,ā¦,cā), such that cįµ¢ meets the requirement of parameter pįµ¢ for i=1,ā¦,n exists exactly one function (cā,ā¦,cā)āR in š½. A method is thus essentially equivalent to Multimethods.
It has not been defined yet, what it means for a class to meet a requirement of a parameter. This ambiguity will be resolved after defining the concept.
Role for a pair (m,p), where p is a parameter of the method m, is a predicate parametrized with a class c that tells whether c has a complete subset of implementations (functions) with class c at a position of p, i.e. for all possible choices of classes for other parameters of m.
This definition puts a role as a rough equivalent of a singleton trait or singleton interface, however whereas a singleton interface mandates, that a certain method is implemented for a class, role mandates that class has implementation for a certain method, for a certain parameter. This makes roles a more focused construct, better adapted for the use with multimethods. In Visual Solution, all roles are defined implicitly, following the definition of a method and its parameter.
Concept is either a role, or a logic conjunction of other concepts. Each concept can be then easily broken down into a conjunction of roles.
Concept corresponds to a trait/interface in existing programming languages. It is defined explicitly; by roles, but one can determine all the classes adhering to the concept and view it as a parent (generalization) of these classes.
A concept is a construct that can be used as a requirement of a parameter. As such it is de-facto a type in this programming model. Any expression in the program has either a type of a class, or a concept. Expression typed with a class shares member access. Expression typed with a concept shares availability to be used as input parameter in a method, if that parameter-method pair defines a role included in that concept.
Other aspects of the environment, such as encapsulation, state management & mutability, side effect management, data ownership, etc. are less important to the solution of the organizational Expression Problem and can be integrated into this model in various configurations.
These aspects may contribute to the way individual function implementations are being defined, however the only essential requirements for function definitions are syntax for object construction and method calling.
The programming environment provides several perspectives of the program that help organizing it by a single concern at a time. Below these perspectives are presented and explained.
Figure 3.2/1: Implementation view with type switch for the Collides method.
Figure 3.2/2: Implementation view with object constructor for the Shrink method.
This view is an element of all views presented below. This view represents implementation of a function or multiple functions. It can represent an expression or a block of statements depending on the specifics of underlying programming model. In particular however, it should support constructs for object construction, method calling, and type matching, as these are parts of the programming model required by the Visual Solution.
This view presents all information concerned with a single class. First subsection contains classās name and allows to change it. Next, subsection contains class definition, that is: an editable list of all the fields; their names and types. Third subsection contains a list of implementations of methods, separately for different roles within each method. Programmer can edit the methods here. Implementation view inside a class view is context aware, and will omit parameter name, treating it like optional this in object-oriented languages. Tokens like object.radius, or collider.center can be simply written as radius, center (see Figure 3.3).
This view presents all information concerned with a single method. First subsection contains the name and return type of the method and allows to change them. The return type places a restriction on the set of returnable values. The implementations will be type-checked against that type.
Next subsection contains an editable list of parameters. For each parameter programmer can specify its requirement in a form of a concept and the name. As mentioned in Section 3.1.2.2, each parameter, together with its method defines a role. The role is implicit and not listed anywhere in this view, as this would cause unnecessary redundance. However, all the places, where one can specify a concept (for example in the parameter type dropdown) all the roles are also selectable. This has a consequence of emerging recursive design pattern, where one can put the role defined by a parameter as that parameterās requirement. This results in parameter accepting any class, since by implementing the method that class immediately meets the requirement.
The third section gives an overview to the matrix of functions. Depending on the number of parameters this section has one of two variants. For one parameter, the functions are arranged in a list, each designated to the particular parameter type. For two and more parameters, the implementations are laid out on a two-dimensional matrix, columns of which discriminate types of one parameter, and rows discriminate types of a different parameter. In each cell a function is presented. If number of parameters is greater than two, the topmost construct in each cell will be a type switch, further subdividing the implementations. The programmer has control over which parameters are displayed in columns, rows, and inside cells, while the environment responds to these commands by changing the representation in cells. Programmer can also take a transformative action of editing the implementations and adding new implementations.
This view presents information for a single concept. It consists of two subsections. First allows to see and rename the concept. Second presents a matrix of implementations. Programmer can swap the rows and columns of the matrix, but for clarity of explanation we will assume one configuration. In columns are the roles, that define the concept. Programmer can add and remove these roles, effectively changing the definition of the concept. In rows of the matrix are the classes that qualify to the concept. In every cell at the crossing of row with class C and column with role R there is an implementation of the method where C plays the role R. If the method has multiple parameters, the varied implementation based on those different parameters is presented with a type switch inside the cell.
Programmer can edit the method implementations as well as add roles and classes. The addition of either is a multi-step process, as every implementation needs to be defined in order to achieve consistency. In the state, where a class is added, but not all methods are implemented that class is marked as a candidate for the concept, which will be marked in other views as well. During that process, one can toggle off the implementations to allow for compilation and evaluation of other areas of the program. That helps the programmer plan and manage a big multistep process between consistent states of a program and achieve the consistency transactionally. Similarly, when a role is added to the conceptās definition, all the existing classes are treated as candidate, until all implementations are added, and toggling that role off is also possible.
Let us follow the running example solved visually. First, one may create an abstraction, concept Expression which is temporarily empty.
Figure 3.6: Empty concept view
Then programmer can add new classes to the concept, opening their respective editors. Since the concept is unconstrained by any methods yet, classes qualify immediately.
Figure 3.7: Class view for Literal with properties defined
Figure 3.8: Class view for Addition with properties defined
Next, a method is declared in the method view.
Figure 3.9: Method view for Evaluate with signature entered but no implementation present
The method is visible at the concept view for Expression. Literal and Addition are now suspended as members of Expression until the Evaluate method is implemented.
One can then fill the implementations in either the concept view, the method view or the class views. After filling in the implementation, the basic expressions are implemented.
Figure 3.11: Concept view for Expression with all implementations entered.
After exporting the functionality as a compiled module, it can be loaded by an extending module. If the source is also shared, it can be displayed with the extended module. The boundary between modules is invisible in the environment.
The Negation class and Stringify method can be added analogically as previous constructs. Stringify is added to Expression with its parameter as new role contributing to the definition of Expression. Then Stringify is defined for existing classes as shown on Figure 3.12.
Figure 3.12: Method view for Stringify
Negation is added as a new candidate class for Expression. Then, in class view all details of Negation can be defined: fields and method implementations.
Figure 3.13: Class view for Negation
The final overview of Expression can be seen on concept view (Figure 3.14).
Figure 3.14: Concept view for extended Expression concept with old and new types and methods.
Programmer can alternatively (and equivalently) add Negation and Stringify in reversed order. Thanks lack of dominant organization scheme in Visual Solution these additions will take the same amount of view changes ā only one per construct added.
To properly assess the Visual Solution, the same points of critique will be applied, as was for the previous solutions. For consistency, solution is assumed to be backed by a low-level mechanism modelled after multimethods.
Visual Solution is statically typed, with no mechanism of type erasure or casting, which ensures static type safety. The environment also ensures that every method has a full implementation coverage, avoiding the problem of missing dispatch target.
As has been discussed before, Visual Solution supports many styles of organization at the same time, minimizing scattering regardless of the concern of the programmer. Thanks to the two-dimensional character of visual programming, the solution can ensure coherence in two concerns at the same time, which is not possible with traditional, textual programming environments.
The extensibility of constructs from Visual Solution can depend on the underlying implementation. I will show, that through translation to constructs of YOMM2 it is possible to achieve extensibility. Again, constructs from Visual Solution will be italicized, while constructs from C++ will stay undecorated for easy distinction. Let us consider the following translation procedure:
The question may arise, if it is type safe and semantic preserving to translate a concept ā abstraction over classes defined implicitly by their method implementations ā into an abstract class ā an abstraction defined explicitly for a closed set of classes. To that, we must note, that a module can only compile, when all the implementations are provided. At this point, all the complying classes can be uniquely found and gathered for each concept, which makes the definition of corresponding abstract class type-safe and free of potential runtime dispatch errors.
In the dependant module, a newly defined class can derive from an external class, as is standard for C++. Even if concept, definition is extended, this concept is not retranslated. Instead, the original abstract class is reused, both for composition and for virtual types for multimethod parameters. Newly defined methods can be defined for external types, as shown in the example involving YOMM2 (see Listing 2.7.2).
Extensibility of Visual Solution is therefore at least as capable as that of multimethods.
Similarly, as for extensibility, we can show that Visual Solutionās composability is the same degree as Multimethods. That means, that modulesā diamond problem is solvable (see Figure 1.1).
However, a similar, but more restrictive āY problemā is not solvable, or at least solution is not known yet. To swiftly describe such āY problemā: let us consider module A, which defines a concept Ī©, module B, which adds a new method m and new role R based on that method, and then uses R to extend the definition of Ī©, and finally, an independent module X which defines a class c. In this scenario module B cannot implement R for c and register c as adhering to Ī©. This is because cįµ (means: cās translation) is a baseless class, and m requires cįµ to be a subclass of Ī©įµ in order to be registered in mįµ (multimethod).
This problem may prove to be a major hinderance in real-world utility of Visual Solution, although it requires further research to determine, if it can actually be solved within the confines of Visual Solution, either by different translation procedure, or by more generalized multimethod implementation.
In Visual Solution the concept plays the role of an abstraction, as it is used as a type for both parameters and return values, making it a de-facto compile time expression type. Based on this abstraction, runtime polymorphism is achievable. Methods (functionally equal to YOMM2 multimethods) build a virtual table of calls to dynamically dispatch functions based on concrete types of parameters in runtime.
At the same time static polymorphism is also possible based on static analysis. If at a call site a some of the parameters are statically known, such that a set of functions they correspond to have a common return type, narrower than the method return type, that common type can be used instead, as the actual return type of this call. This process could not only improve accuracy of the type system and reduce number of classes handled, but also improve performance, by reducing the dimensionality of the dispatch table, or potentially dispatching that call statically altogether.
Visual Solutionās primary aim is to minimize overhead. An observation, that many solutions create singleton abstractions, i.e. one-method interfaces led to introduction of roles, which have the same uses, but are defined implicitly.
Concepts with concept view serve as a macroscale perspective on the code, providing for a convenient table of contents; from which hyperlinked navigations can be performed to more focused: class and method views. They also serve as a basis for macroscale operations, like redefinitions of concept semantics.
These optimizations should lead to a smaller number of non-transformative operations (such as movement between code sites in textual programming languages, or navigations between views in Visual Solution) needed to perform a semantic change in a program, which in turn should increase developer experience and productivity.
