projects:icfp2004:phec [Georg Martius]

A PCRE internal error occured. This might be caused by a faulty plugin

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

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

Back to top

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