[HN Gopher] Befreak is a purely reversible two-dimensional progr...
       ___________________________________________________________________
        
       Befreak is a purely reversible two-dimensional programming language
       (2003)
        
       Author : akkartik
       Score  : 22 points
       Date   : 2024-05-02 20:48 UTC (3 days ago)
        
 (HTM) web link (tunes.org)
 (TXT) w3m dump (tunes.org)
        
       | parlortricks wrote:
       | Interesting language, but took me a bit to work out what way the
       | directions were. It would have helped to at least have up, down,
       | left, right for the first time the compass directions were
       | mentioned.
        
       | free_bip wrote:
       | Seems pretty obviously limited - it's not Turing complete because
       | it can't calculate e.g. periodic functions. Are there any
       | practical uses for a language where every operation must be
       | invertible like this?
        
         | sshine wrote:
         | Reversible computing is sort of hypothetical at heart. Besides
         | cryptography and encoders, it's mostly "if quantum computers
         | eventually fit our model's for reversible computing, then
         | Landauer's limit gives us energy-free computing as long as we
         | never extract an answer!"
        
         | eigenket wrote:
         | Can you be more explicit about the functions it can't compute?
         | I'm pretty sure it can output at least some periodic things
         | (e.g. it's trivial to make it output 01010101 forever).
         | 
         | Edit: just looking at it I'm pretty sure this language is
         | Turing complete, I can't see any reason why it wouldn't be
        
           | free_bip wrote:
           | Remainder after division is one. E.g. 12 mod 4 = 0. There's
           | no way to reverse that operation given only the output and
           | the modulus. (x mod 4 = 0 has infinite solutions)
           | 
           | Bitwise operators are another. A & B, A | B, A << B, A >> B
           | are all in general not invertible given the output and B.
           | (e.g. A | 1 = 1, is A 0 or 1?)
           | 
           | Now I haven't looked at the language in detail, maybe there's
           | a way around this, but it sounds like if truly every single
           | operation is invertible, then there would be no way to
           | calculate these simple functions.
        
             | LegionMammal978 wrote:
             | In general, one solution is to just keep the original
             | inputs around as necessary. So instead of x -> x mod 4,
             | take the function x -> (x, x mod 4); the inverse is just
             | (x, y) -> x.
             | 
             | The actual % operator in this language is defined as (x, y)
             | -> (y, x / y, x % y), acting as a divmod. The + and -
             | operators are defined as (x, y) -> (x + y, y) and (x, y) ->
             | (x - y, y). And so on, making sure enough inputs are left
             | on the stack to reconstruct the others.
        
       | stevage wrote:
       | Are there more conventional (non 2d) reversible languages?
        
       ___________________________________________________________________
       (page generated 2024-05-05 23:01 UTC)