Dagaz: Factorial is easy!

    imageScripting is perhaps the most important (though not the most difficult) part of my project . In order for it to work, I need a general-purpose language, with variables, conditional execution, loops, and exceptions. I don’t need anything complicated like anonymous functions or closures . Most likely, even recursion will not come in handy for me , in any case, so far, there are no applications for it, in any of my case- s. There will be no syntactic sugar at all in this language , since XSLT will take care of all metaprogramming tasks . In general, this language will be as simple as possible, but ... not easier. 

    Let me remind you that the script, in my understanding, contains not only the definition of a number of functions that determine the "behavior" of the objects participating in the game, but, in addition, it must determine the structure of rather complex objects, such as a "board", "pieces", etc. P. Here is an example of a similar description:

    The definition of `` board ''
          (grid (dimensions "A_J" "1")
                (direction (name forward)   1 0)
                (direction (name backward) -1 0)
          (grid (dimensions "A_J" "2")
                (direction (name forward)  -1 0)
                (direction (name backward)  1 0)
          (grid (dimensions "A_K" "3")
                (direction (name forward)   1 0)
                (direction (name backward) -1 0)
          (grid (dimensions "a_d"))
          (link (name forward)  (J1 J2) (A2 A3) (K3 K3))
          (link (name backward) (J2 J1) (A3 A2) (K3 K3))
          (zone (name rebirth)  (positions F2))
          (zone (name protect)  (positions F3 G3 H3 I3 J3))
          (zone (name beauty)   (positions F3))
          (zone (name water)    (positions G3))
          (zone (name truth)    (positions H3))
          (zone (name ra)       (positions I3))
          (zone (name stop)     (positions F3 K3))
          (zone (name end)      (positions K3))
          (zone (name dices)    (positions a b c d))

    This definition is a kind of “card” for a board game, and it can be very complex. It was for analyzing such hierarchical structures that I needed XPath , which, in turn, led to the need to use XML for the internal representation of the script in memory. Analysis of such structures is verbose , but rather straightforward. Code is another matter.

    (define (factorial n a)
      (if (<= n 1)
         (factorial (- n 1) (* a n))
    (define (factorial n)
      (factorial n 1)
    (define main
      (set! out (factorial 5))

    I hope you recognize him. Yes, the factorial value is calculated here using tail-recursion, and no, I'm not going to do tail-recursion optimization. As I said, recursion is unlikely to be necessary for me. For those who suddenly don’t know what “tail recursion” is and why it may need to be optimized, I recommend reading this wonderful book .

    This code is just a compact test, covering as much as possible all the functionality that interests me at the moment. It uses a conditional statement, calls and function definitions, overloadingand work with parameters. Since I / O operators are not provided in the language (they are not required), in the test, the output will be emulated by assigning the final value of the “variable” out .

    By the way
    The complexity of the selected test proved itself to be quite good. Calculating the factorial of three, I noticed that the obtained value of "2" is somewhat different from the expected one. An investigation of this situation led to the following fix . I could well not notice this error using a simpler test.

    You may notice that all control structures of the language are functions, in the sense that they always return a certain value . For example, the result of a sequence of expressions is the result of the last expression executed. Separately, it is worth mentioning the exceptions :

    (define dice-drop
       (check (in-zone? dices))
       (check is-empty?)

    At any time, a validation of a certain Boolean expression can be performed. If the obtained value is false, the execution should be immediately interrupted. I do not know a tool more suitable for this task than exceptions. CheckExpression calculates the value of its argument in a Boolean context and throws a CheckException if the condition is violated (it is obvious that this function will always return the true value, if only it comes to returning the value).

    The values ​​of the arguments of the functions will be calculated strictly , before the transfer of control to the functions. There will be no total " laziness " of calculations, but functions such as if , and oror will only compute the value of their arguments if necessary. To call arbitrary functions (defined in the body of the script), the ApplyExpression construct is intended . The resulting argument values ​​are nothing more than local variables whose scope is limited by the function being called. All variables are accessed through the IEnvironment interface , passed to each expression being evaluated:

    public interface IEnvironment {
    	void   letValue(String name, IValue value) throws EvaluationException;
    	void   setValue(String name, IValue value) throws EvaluationException;
    	IValue getValue(String name, boolean isQuoted) throws ValueNotFoundException;

    Using this interface, you can create local variables (with the let function ), change their value (with the set! Function ), and also get the value by name. For the last of these operations, a special function is not provided. Any atom that is not a string or numeric literal will be considered as a reference to a variable (or function parameter), provided that the function with the same name and arity was not defined in the script .

    Details for the curious
    Collisions between function calls and variable calls could be avoided by always bracing function calls with brackets, as follows:

    (define dice-drop

    I found such a record unnecessarily cumbersome. In addition, there was a problem with the internal representation of such structures in XML. Another unrealized feature is to calculate the name of the called function:

    ((if (< a b) "+" else "-") a b)

    In any case, I do not think that the use of such structures is necessary.

    In order to simplify the language as much as possible, I did not implement the QUOTE operator explicitly (therefore, writing Quine in this language is unlikely to succeed). Quoting is in the language, but it is implicit. For example, expressions such as let and set! They “know” that the first argument does not need to be calculated (the redefined method IExpression.isQuoted is responsible for this ). Thus, the first argument, in these expressions, is perceived as the name of the variable, and not an attempt to obtain its value.

    More details
    In the application code, more complex situations associated with implicit citation can also be encountered:

    (define (piece-move direction)
       (check up)
       (check direction)
       (piece-move north)
       (piece-move south)
       (piece-move east)
       (piece-move west)

    Similar code will occur very often. Here, the atoms north , south , east and west should be interpreted as the names of directions, but only on condition that such directions on the board are defined (otherwise, this is an appeal to variables). Thus, the direction parameter will contain a string with the name of the corresponding direction.

    Positioning and navigation are carried out by referring to pseudo-variables with the corresponding names. Turning to the “variable” up (provided that such a direction is determined on the board) will move the marker of the current position (as a side effect), and also return trueif this move was successful.

    But what happens when accessing the direction parameter ? If no further action is taken, a non-empty string value will be obtained, which, in a Boolean context, will be interpreted as true . This is clearly not what we would like. To correct the situation, the module providing access to the status of the calculation of the course must check whether the received line is the name of the position or direction. If so, the get operation must be repeated and its result must already be returned to the dial peer. This is a good illustration of the thesis that simplification of a language can lead to a complication of its implementation.

    With all of the above, code generation is becoming quite trivial . All that is needed is to find function definitions in XML and recursively build hierarchies of their corresponding expressions. Expressions themselves are created by ExpressionFactory , which makes it easy to expand the list of supported system functions (up to the implementation of new language constructs).

    Of course, this is not the end of the road. In order to benefit from such scripting, it is necessary to associate it with navigation in the game space and a change in the state of the calculation of the course. Need to determine the mass of system functions that work in terms of the subject area, such as is-friend? or is-empty? . Finally, to implement the move generator, you will need to realize the opportunitynon-deterministic computing . Compared to all of these things, factorial is really easy.

    Also popular now: