Download code

Jump to: navigation, search

Back to Unlambda_abstraction_elimination_(C_Plus_Plus)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

uae.cc

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Unlambda_abstraction_elimination_(C_Plus_Plus)?oldid=16427
 14 */
 15 
 16 // ************************************
 17 // *                                  *
 18 // * Unlambda abstraction elimination *
 19 // *                                  *
 20 // ************************************
 21 
 22 #include <iostream>
 23 #include <string>
 24 
 25 // test if the partial expression starting at index is valid Unlambda
 26 // + lambda expressions if the valid functions are the one-character
 27 // functions given in the second argument plus the special functions
 28 // .x and ?x. The index is updated to the end of the tested
 29 // expression.
 30 bool valid_with(std::string const& expression,
 31                 std::string const& functions,
 32                 std::string::size_type& index)
 33 {
 34   static std::string const special = "`.?^";
 35   int const stoplevel = 0;
 36 
 37   int level = 1;
 38   while (level > stoplevel && index < expression.size())
 39   {
 40     switch (char c = expression[index])
 41     {
 42     case '`':
 43       {
 44         ++level;
 45 	++index;
 46         break;
 47       }
 48     case '.':
 49     case '?':
 50       {
 51         ++index;
 52 	if (index >= expression.size())
 53 	  return false;
 54 	--level;
 55 	++index;
 56         break;
 57       }
 58     case '^': // lambda
 59       {
 60         ++index;
 61 	if (index >= expression.size())
 62 	  return false;
 63 	char const arg = expression[index];
 64 	// the argument may not be a valid function name or special symbol
 65 	if ((functions + special).find(arg) != std::string::npos)
 66 	  return false;
 67 	++index;
 68 	if (!valid_with(expression, functions + arg, index))
 69 	  return false;
 70 	--level;
 71         break;
 72       }
 73     default:
 74       {
 75         if (functions.find(c) == std::string::npos)
 76 	  return false;
 77 	--level;
 78 	++index;
 79         break;
 80       }
 81     }
 82   }
 83   return level == stoplevel;
 84 }
 85 
 86 // test if the expression is valid Unlambda + lambda expression
 87 bool valid(std::string const& expression)
 88 {
 89   std::string::size_type index = 0;
 90   // the second string contains all elementary Unlambda 2.0 functions
 91   // except for the two-character functions .x and ?x (those need
 92   // special handling)
 93   return valid_with(expression, "skivrdce|", index)
 94     && index == expression.size();
 95 }
 96 
 97 
 98 // find the end of a subexpression (assumes a valid Unlambda
 99 // expression starting at pos)
100 std::string::size_type find_end(std::string const& expr,
101                                 std::string::size_type pos)
102 {
103   int level = 1;
104   while (level > 0)
105   {
106     switch(expr[pos])
107     {
108     case '`':
109       ++level;
110       break;
111     case '.':
112     case '?':
113       ++pos;
114       // fall through
115     default:
116       --level;
117     }
118     ++pos;
119   }
120   return pos;
121 }
122 bool safe_for_constant_shortcut(std::string const& expression,
123                                 std::string::size_type start,
124                                 std::string::size_type end,
125                                 char arg)
126 {
127   int applications = 0;
128   for (; start < end; ++start)
129   {
130     switch (expression[start])
131     {
132     case '`':
133       ++applications;
134       break;
135     case 's':
136       {
137         if (applications > 2)
138           return false;
139         applications = 0;
140       }
141       break;
142     case 'k':
143       {
144         if (applications > 1)
145           return false;
146         applications = 0;
147       }
148       break;
149     case 'i':
150       {
151         if (applications > 1)
152           --applications;
153       }
154       break;
155     case 'd':
156       {
157         if (applications == 1)
158         {
159           std::string::size_type end = find_end(expression, start+1) - 1;
160           if (expression.find(arg, start+1) < end)
161             return false;
162           start = end-1;
163         }
164         else if (applications > 1)
165           --applications;
166       }
167       break;
168     case 'v':
169       applications = 0;
170       break;
171     default:
172       if (applications > 0 || expression[start] == arg)
173         return false;
174       if (expression[start] == '.' || expression[start] == '?')
175         ++start;
176       applications = 0;
177     }
178   }
179   return true;
180 }
181 bool safe_for_function_shortcut(std::string const& expression,
182                                 std::string::size_type start,
183                                 std::string::size_type end,
184                                 char arg)
185 {
186   std::string unsafe_chars = std::string(".rde@|") + arg;
187   std::string::size_type pos = start;
188   while (pos < end)
189   {
190     std::string::size_type failpos = expression.find_first_of(unsafe_chars, pos);
191 
192     if (failpos >= end)
193       break; // no bad character found
194     std::string::size_type questionpos = failpos-1;
195     while (questionpos >= start && expression[questionpos] == '?')
196       --questionpos;
197     if ((failpos - questionpos) % 2 == 1) // failpos - questionpos = 1 + number of question marks
198       return false;                       // an even number of question marks means the character is not quoted
199     pos = failpos+1;
200   }
201   return true; // no unquoted bad character found
202 }
203 
204 // eliminate abstraction (assumes a valid expression)
205 std::string eliminate_abstraction(std::string expression)
206 {
207   std::string::size_type pos;
208   while ((pos = expression.rfind('^')) != std::string::npos)
209   {
210     char const argument_name = expression[pos+1];
211     char const what = expression[pos+2];
212     if (what == argument_name)
213     {
214       expression.replace(pos, 3, "i");
215     }
216     else if (what == '`')
217     {
218       std::string::size_type
219         end1 = find_end(expression, pos+3),
220         end2 = find_end(expression, end1);
221       if (safe_for_constant_shortcut(expression, pos+2, end2, argument_name))
222       {
223         expression.replace(pos, 2, "`k");
224       }
225       else if (end2 == end1+1
226                && expression[end1] == argument_name
227                && safe_for_function_shortcut(expression, pos+3, end1, argument_name))
228       {
229         expression.replace(pos, end2-pos, expression.substr(pos+3,end1-pos-3)); // function call shortcut
230       }
231       else
232       {
233         expression.replace(pos, end2-pos,
234                            std::string("``s^") + argument_name
235                            + expression.substr(pos+3, end1-pos-3)
236                            + "^" + argument_name
237                            + expression.substr(end1, end2-end1));
238       }
239     }
240     else if (what == 'v')
241     {
242       expression.erase(pos, 2);
243     }
244     else
245     {
246       expression.replace(pos, 2, "`k");
247     }
248   }
249   return expression;
250 }
251 
252 int main()
253 {
254   std::string expr;
255   while(std::cout << "expression: "
256         && std::getline(std::cin, expr)
257         && expr != "q")
258   {
259     if (valid(expr))
260       std::cout << "result: " << eliminate_abstraction(expr) << "\n\n";
261     else
262       std::cout << "invalid expression\n\n";
263   }
264 }


hijacker
hijacker
hijacker
hijacker