Differences

This shows you the differences between two versions of the page.

Link to this comparison view

projects:icfp2004:phec [13.11.2008 22:34] (current)
Line 1: Line 1:
 +This is intended to document the phec language as used in our ant finite
 +state machine generator.
 +
 +=====General=====
 +The language is similiar to that of the ant finite state machine language.
 +Though the phec language contains some useful additions to the language of
 +the ants, the main progress is the use of names or labels, to refer to a
 +state of the machine. This means that code becomes far more easy to relocate
 +and in fact in the phec language each state does not necessarily have to start
 +on a new line. In order to further simplify the task of relocating and/or
 +re-using a block of code, the phec language introduces blocks so that labels
 +referring to states are confined within a block, this means that names for
 +labels can be re-used within separate blocks, avoiding the necessity for
 +the programmer to constantly come up with new names to avoid clashes.
 +This also means that we cannot jump to a state that is in the middle of a block
 +this can help the programmer avoid being in a state that was appropriate,​
 +for example every PickUp state may be within a block such that it can only
 +occur one we have checked that there is indeed food on the segment occupied
 +by the ant.
 +
 +=====Blocks=====
 +So time for some phec code, here is a block of code which
 +makes the ant go between two points on the board which it can't get past.
 +<code >​pace_like_guard {
 +         ​drive ​      Move drive blocked
 +         ​blocked ​    Turn Left once_left
 +         ​once_left ​  Turn Left twice_left
 +         ​twice_left ​ Turn Left drive
 +        }
 +</​code>​
 +Notice that we give the whole block a rather verbose name, but the names within
 +the block are quite concise. This avoids us having names such as blocked_while_pacing_like_a_guard.
 +
 +=====Macros=====
 +Blocks are useful, but what would be more useful is to be able to right a block
 +that is parameterised by some portion of the block within. To this end we
 +allow macros, or parameterised blocks. As we have seen state numbers have
 +already been replaced by names, but what may not have been obvious from the
 +code block about, is that the Turn direction is in fact also an identifier,
 +rather than a keyword as in the ant language. The same is true for the sense
 +directions, the sense conditions and the markers. So the above code could
 +have been written
 +<code >​pace_like_guard (turn_dir) {
 +         ​drive ​      Move drive blocked
 +         ​blocked ​    Turn turn_dir once
 +         ​once ​       Turn turn_dir twice
 +         ​twice ​      Turn turn_dir drive
 +        }
 +and then called this with either
 +&​pace_like_guard (Left)
 +or
 +&​pace_like_guard (Right).
 +</​code>​
 +
 +Though this quite a silly example we can show how the example program given
 +  - the task description is written with the use of macros in the phec langauge.
 +<code >​random_search {
 +  search (desire, return_address)
 +      { search ​      Sense Ahead return_address not_found desire
 +        not_found ​   Choose (links, recht, gerade)
 +        links        Turn TurnLeft search
 +        recht        Turn TurnRight search
 +        gerade ​      Move search not_found
 +      }
 +      search_for_food ​ &search (Food, found_food)
 +      found_food ​      ​PickUp go_home search_for_food ​    
 +
 +      go_home ​        &​search (Home, found_home)
 +      found_home ​     Drop search_for_food
 +}
 +</​code>​
 +
 +The search macro will search for the desired condition, here it is applied
 +searching for food and then searching for home. This example also demonstrates
 +that we now have a very primitive form of procedure, since the return address
 +can be passed in as a parameter.
 +
 +=====Choices and Conditional Expressions=====
 +The final major addition to the language is the ability to make a choice about
 +how the macro should be expanded based on (generally) one of it's parameter.
 +Here we use the If Then Else clause to make the search decide what to do once
 +  - has found the desired condition.
 +<code >​simple_beahaviour {
 +  search (desire)
 +      { search ​      Sense Ahead found not_found desire
 +        not_found ​   Choose (links, recht, gerade)
 +        links        Turn TurnLeft search
 +        recht        Turn TurnRight search
 +        gerade ​      Move search not_found
 +        found        If desire = Food Then
 +                    { collect ​    ​PickUp go_home search_for_food } Else
 +                    { drop_food ​  Drop search_for_food}
 +      }
 +      search_for_food &search (Food)
 +      go_home ​        &​search (Home)
 +}
 +</​code>​
 +
 +=====The Pre-Processor=====
 +The pre-processor gives further facilities to the programmer by removing ​
 +tedious tasks such as repeating blocks of code a set number of times and 
 +including the contents of other files, this assists with multiple developers
 +working on the ant specification simultaneously.
 +
 +=====Abstract Syntax=====
 +====Pheromone Language====
 +<code BNF>​Program ::= <​LabeledStatments>​*
 +
 +LabeledStatments ::= label <​Statement>​
 +
 +Statement ::= '​{'​ <​Program>​ '​}' ​         -- Block
 + | '​('​label*'​)'​ '​{'​ <​Program>​ '​}'​ -- Macro
 + | &label label '​('​ <​Identifier>​* '​)'​ -- MacroUse
 + | Choose '​('​label*'​)'​ -- comma seperated ​
 + | If <​BoolExpr>​ Then { <​Program>​ } Else { <​Program>​ }
 + | Sense <​SenseDir>​ label label <​Condition>​
 + | Mark <​Mark>​ label  ​
 + | Unmark <​Mark>​ label
 + | PickUp label label
 + | Drop label
 + | Turn <​TurnDir>​ label
 +        | Move label label
 + | Flip <Num> label label
 +
 +Mark    ::= Mark0 | Mark1 | Mark2 | Mark3 | Mark4 | Mark5
 +Marker ​ ::= Marker0 | Marker1 | Marker2 | Marker3 | Marker4 | Marker5
 +TurnDir ::= {Left | Right}
 +Num     ::= 0..
 +
 +BoolExpr ::= (<​BoolExpr>​)
 + | <​BoolExpr>​ && <​BoolExpr>​
 + | <​BoolExpr>​ || <​BoolExpr>​
 + | <​Identifier>​ = <​Identifier>​
 +
 +Identifier ::= {<​SenseDir>​ | <​TurnDir>​ | <​Condition> ​
 +         | <​Marker>​ | <​Mark>​ | label}
 +
 +Condition ::= Friend
 +            | Foe
 +            | FriendWithFood
 +            | FoeWithFood
 +            | Food
 +            | Rock
 +            | <​Marker>​
 +            | FoeMarker
 +     | Home
 +     | FoeHome ​
 +
 +SenseDir ::= Here 
 +            | Ahead  ​
 + ​  ​   | Left
 +     | Right
 +
 +
 +Commenting is in Haskell syntax: ​
 +    * for one line comment ​
 +    {- for multiple ​
 +    line comment -}
 +    ​comments can be nested.
 +</​code>​
 +     
 +
 +====Preprocessor====
 +
 +<code >#​include file.phec ​ -- includes file.phec at this position
 +
 +#times (Var) (Num)
 +    abitrary contents with some $<​ExprWithVar>​$ in which are
 +    evaluated for each copy of the block
 +#endtimes
 +</​code>​
 +
 +where 
 +<code BNF> ​   ExprWithVar ::= Var | Number | (<​ExprWithVar>​) ​
 +               | <​ExprWithVar>​ '​*'​ <​ExprWithVar>​
 +              | <​ExprWithVar>​ '/'​ <​ExprWithVar> ​
 +              | <​ExprWithVar>​ '​%'​ <​ExprWithVar> ​
 +              | <​ExprWithVar>​ '​+'​ <​ExprWithVar> ​
 +              | <​ExprWithVar>​ '​-'​ <​ExprWithVar>​
 +              | <​ExprWithVar>​ '​|'​ <​ExprWithVar> ​
 +              | <​ExprWithVar>​ '&'​ <​ExprWithVar>​
 +              | <​ExprWithVar>​ '​=='​ <​ExprWithVar>​
 +              | <​ExprWithVar>​ '/​='​ <​ExprWithVar>​
 +              | <​ExprWithVar>​ '<<'​ <​ExprWithVar>​
 +              | <​ExprWithVar>​ '>>'​ <​ExprWithVar>​
 +</​code>​
 +
 +
 +{{tag>​computing programming_contests haskell}}
  

projects/icfp2004/phec.txt · Last modified: 13.11.2008 22:34 (external edit)