Home > ICFP 2004 > Phec

Phec

Created by georg. Last edited by georg, 4 years and 126 days ago. Viewed 200 times. #1

[edit] [rdf]

labels

attachments

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.

pace_like_guard {
         drive       Move drive blocked
         blocked     Turn Left once_left
         once_left   Turn Left twice_left
         twice_left  Turn Left drive
        }

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

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).

Though this quite a silly example we can show how the example program given in the task description is written with the use of macros in the phec langauge.

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 }

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 it has found the desired condition.

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)
}

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

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.

Preprocessor

#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

where

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>

Please login to post a comment.