Three Levels of Multidimensional Insanity
Saturday, 8. October 2005, 14:26:00
When a programmer has nothing better to do, or he just needs an exercise for the brain, he starts having these weird ideas. Like Esoteric programming languages.
All our boring programs are grossly one-dimensional. The memory is linear, the stack is sequential, the program is transcribed in a serialized form. Even things that are naturally two-dimensional, such as the on-screen picture, are reduced to linear for computer processing. The idea of taking programming beyond the one-dimensional space isn't new and has already generated a whole family of esoteric programming languages called fungeoids after the first of the kind, Befunge. The common feature of these languages is transcription of the program as a two-dimensional matrix containing the operation codes. The interpreter moves proceeds from one cell to another in one of the several possible directions. This way, a loop in Befunge can indeed have a loopy look. Some of these languages use memory registers isolated from the program storage space and are addressed by one-dimensional indices; others use the Von Neumann architecture and store data in the same two-dimensional memory as the code, which also creates interesting possibilities for writing self-modifying programs.
The reader might ask why anyone would need any of it, whether someone indeed has nothing better to do, and what kind of mild drugs the author uses, so I'll have to answer. No particular reason. Simply put, it's for fun. Hey, ask some solid scientists specializing in pure mathematics why they have to study objects like… well, not just an algebra, and not even en algebra of algebræ, but an nth order algebra, an algebra of algebræ of algrebræ… n times. I suppose their elaborate answers can be effectively reduced to something like: “Hey, it's fun!” So is an esoteric programming language fun. It's an original joke, and a complicated mathematical abstraction to study, and a puzzle. Taking something to the point of absurdity is fun in itself, so today I've taken it to my hand to carry the idea of multidimensional programming to absurdity. Let's do it in three nonsensical steps. I'll be writing about the two-dimensional case, but it's trivial (?) to generalize for the case of n dimensions.
First level. Here lie the “arrow programming” languages of the fungeoid family. The memory is two-dimensional. In a more interesting variation, the memory is shared between code and data. On this level, each memory cell stores an ordinary number, such as one byte. Let's call the data unit stored in one cell a word, as in traditional computing. Two-dimensional memory uses two-dimensional addresses, such as (i, j). The current instruction pointer (IP) also looks like this. Most fungeoids allow to change the direction in which IP is incremented to one of the four ways, but it's not necessary for Turing completeness: a single direction and a conditional jump to a two-dimensional address is enough. However, the changeable direction of execution flow is the fungeoids' zest which makes programming in them especially unlike the traditional and allows transcribing of loops as rings and linear programs as spirals. Two-dimensional memory organization inspires thoughts of measurement units such as square kilobytes (Kb2), makes you think about what the operating system should do when it gets a request to allocate a wide memory block while only tall and narrow areas are available, and gives rise to an interesting problem of defragmentation of rectangular files in two-dimensional mass storage. The compiler could optimize code not only for speed but also for the area taken, and storage of raster images would be natural as never before. Finally, programming languages can be described by two-dimensional grammars specified in BNF2.
Second level. Unlike the first level represented by numerous fungeoids, I've never encountered anything that would fit my second or third level. In the second level, something strange happens to the very numbers: they are not simple bytes anymore but rather complex values. Addressing a cell of the two-dimensional memory becomes natural. Addition and subtraction are straightforward, multiplication and division are slightly more complicated, and there is a new operation: complex conjugation. One could even go further and say that the cells contain two-dimensional matrices of bits. For example, a word can be comprised of 16 square bits (4×4), which, of course, spawns a new set of arithmetical operations. With regular addition, the overflow bits are carried in one direction — to the left; with two-dimensional addition, bits can be carried both to the left and up. This makes at least two types of addition and subtraction. Shifts and rotations can be done in four instead of two directions, and new operations are possible, such as turns and transposition. When multiplying, shifts are made in both directions. It's not obvious, though, how a two-dimensional word should be interpreted as a regular number for purposes of addressing and counting. Speaking of data exchange in networks, instead of two possible bit orders (little-endian or big-endian) we get eight equally reasonable ways to serialize a word.
Third level. At the third level of absurdity, time becomes two-dimensional. Who cares that it doesn't apply to our Universe? The model is interesting anyway. A moment of time is described with two variables (t, u) rather than one. With regard to a single moment, there isn't just something that happens before or after; there are some moments to the right from this moment in time, some below, and some both to the right and below. The causality spreads in both directions, and what happens in a moment of time is a consequence of both what happened to the left and above in time. Clock frequency is measured in square Hertz, and the state of the machine at clock (t, u) is derived from its states at clocks (t – 1, u) and (t, u – 1). The program stored in the two-dimensional memory runs both horizontally and vertically. In the next clock by t the CPU proceeds to the command to the right of the current, and in the next clock by u it moves to the command below. A bicyclic algorithm can have toroidal topology. In a square second, a communication channel can be used to transfer a number of square bits, therefore the throughput is measured traditionally, in bits per second. The task of optimizing the speed of an algorithm can be defined more accurately: which of the time dimensions is more important to optimize.
Fourth level. If someone comes up with a fourth level to complement the three above, I'd like to discuss it with youbefore they come to take both of us away.
По-русски: Три уровня многомерного безумия
All our boring programs are grossly one-dimensional. The memory is linear, the stack is sequential, the program is transcribed in a serialized form. Even things that are naturally two-dimensional, such as the on-screen picture, are reduced to linear for computer processing. The idea of taking programming beyond the one-dimensional space isn't new and has already generated a whole family of esoteric programming languages called fungeoids after the first of the kind, Befunge. The common feature of these languages is transcription of the program as a two-dimensional matrix containing the operation codes. The interpreter moves proceeds from one cell to another in one of the several possible directions. This way, a loop in Befunge can indeed have a loopy look. Some of these languages use memory registers isolated from the program storage space and are addressed by one-dimensional indices; others use the Von Neumann architecture and store data in the same two-dimensional memory as the code, which also creates interesting possibilities for writing self-modifying programs.
The reader might ask why anyone would need any of it, whether someone indeed has nothing better to do, and what kind of mild drugs the author uses, so I'll have to answer. No particular reason. Simply put, it's for fun. Hey, ask some solid scientists specializing in pure mathematics why they have to study objects like… well, not just an algebra, and not even en algebra of algebræ, but an nth order algebra, an algebra of algebræ of algrebræ… n times. I suppose their elaborate answers can be effectively reduced to something like: “Hey, it's fun!” So is an esoteric programming language fun. It's an original joke, and a complicated mathematical abstraction to study, and a puzzle. Taking something to the point of absurdity is fun in itself, so today I've taken it to my hand to carry the idea of multidimensional programming to absurdity. Let's do it in three nonsensical steps. I'll be writing about the two-dimensional case, but it's trivial (?) to generalize for the case of n dimensions.
First level. Here lie the “arrow programming” languages of the fungeoid family. The memory is two-dimensional. In a more interesting variation, the memory is shared between code and data. On this level, each memory cell stores an ordinary number, such as one byte. Let's call the data unit stored in one cell a word, as in traditional computing. Two-dimensional memory uses two-dimensional addresses, such as (i, j). The current instruction pointer (IP) also looks like this. Most fungeoids allow to change the direction in which IP is incremented to one of the four ways, but it's not necessary for Turing completeness: a single direction and a conditional jump to a two-dimensional address is enough. However, the changeable direction of execution flow is the fungeoids' zest which makes programming in them especially unlike the traditional and allows transcribing of loops as rings and linear programs as spirals. Two-dimensional memory organization inspires thoughts of measurement units such as square kilobytes (Kb2), makes you think about what the operating system should do when it gets a request to allocate a wide memory block while only tall and narrow areas are available, and gives rise to an interesting problem of defragmentation of rectangular files in two-dimensional mass storage. The compiler could optimize code not only for speed but also for the area taken, and storage of raster images would be natural as never before. Finally, programming languages can be described by two-dimensional grammars specified in BNF2.
Second level. Unlike the first level represented by numerous fungeoids, I've never encountered anything that would fit my second or third level. In the second level, something strange happens to the very numbers: they are not simple bytes anymore but rather complex values. Addressing a cell of the two-dimensional memory becomes natural. Addition and subtraction are straightforward, multiplication and division are slightly more complicated, and there is a new operation: complex conjugation. One could even go further and say that the cells contain two-dimensional matrices of bits. For example, a word can be comprised of 16 square bits (4×4), which, of course, spawns a new set of arithmetical operations. With regular addition, the overflow bits are carried in one direction — to the left; with two-dimensional addition, bits can be carried both to the left and up. This makes at least two types of addition and subtraction. Shifts and rotations can be done in four instead of two directions, and new operations are possible, such as turns and transposition. When multiplying, shifts are made in both directions. It's not obvious, though, how a two-dimensional word should be interpreted as a regular number for purposes of addressing and counting. Speaking of data exchange in networks, instead of two possible bit orders (little-endian or big-endian) we get eight equally reasonable ways to serialize a word.
Third level. At the third level of absurdity, time becomes two-dimensional. Who cares that it doesn't apply to our Universe? The model is interesting anyway. A moment of time is described with two variables (t, u) rather than one. With regard to a single moment, there isn't just something that happens before or after; there are some moments to the right from this moment in time, some below, and some both to the right and below. The causality spreads in both directions, and what happens in a moment of time is a consequence of both what happened to the left and above in time. Clock frequency is measured in square Hertz, and the state of the machine at clock (t, u) is derived from its states at clocks (t – 1, u) and (t, u – 1). The program stored in the two-dimensional memory runs both horizontally and vertically. In the next clock by t the CPU proceeds to the command to the right of the current, and in the next clock by u it moves to the command below. A bicyclic algorithm can have toroidal topology. In a square second, a communication channel can be used to transfer a number of square bits, therefore the throughput is measured traditionally, in bits per second. The task of optimizing the speed of an algorithm can be defined more accurately: which of the time dimensions is more important to optimize.
Fourth level. If someone comes up with a fourth level to complement the three above, I'd like to discuss it with you
По-русски: Три уровня многомерного безумия
WIDGETIZE
How to use Quote function: