• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Tim Cooke
  • Campbell Ritchie
  • Ron McLeod
  • Liutauras Vilda
  • Jeanne Boyarsky
Sheriffs:
  • Junilu Lacar
  • Rob Spoor
  • Paul Clapham
Saloon Keepers:
  • Tim Holloway
  • Tim Moores
  • Jesse Silverman
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Piet Souris
  • Frits Walraven

Appreciation for "return"

 
Saloon Keeper
Posts: 13477
304
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The last year, my Steam game library has slowly been filling with programming puzzles. Many of these games provide some very basic programming language that allow you to perform arithmetic, move robots around or let you control small pieces of machinery. The goal is to solve a series of puzzles (usually in the form of a bunch of hidden unit tests) with as few lines of code or as few instructions executed as possible.

While most of these games vary greatly in graphical presentation, the type of puzzle you solve, the language you use or the type of thing you control with the language, almost all of them have one thing in common:

The things you control are usually Finite State Automata.

This means that your memory is limited to a fixed number of slots (sometimes even just a single register!) and your decisions are usually made in the form of "if x jump to y".

I'm no stranger to computability theory, and I have occasionally implemented a full Turing Machine inside of different games, so I know about the limitations of different models of computation. Actually running into those limitations is a whole different thing. In particular, I have a completely new respect for Pushdown Automata. A pushdown automaton is like a finite state automaton, except you can also push data on and pop data off a stack. Such a stack is at the basis of being able to call subroutines and then returning from those functions back to where you were.

In short, take a short moment to appreciate "return" by imagining what your code would look like if you had to call "jump" instead.
 
Rancher
Posts: 1006
26
Netbeans IDE Oracle MySQL Database Tomcat Server C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
i know it well, as i am a assembly and machine language programmer retread.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic