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.
— |
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}} | ||