Download code

From LiteratePrograms

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 /* Copyright (c) 2010 the authors listed at the following URL, and/or
  2 the authors of referenced articles or incorporated external code:
  3 http://en.literateprograms.org/Unlambda_abstraction_elimination_(C_Plus_Plus)?action=history&offset=20090506073126
  4 
  5 Permission is hereby granted, free of charge, to any person obtaining
  6 a copy of this software and associated documentation files (the
  7 "Software"), to deal in the Software without restriction, including
  8 without limitation the rights to use, copy, modify, merge, publish,
  9 distribute, sublicense, and/or sell copies of the Software, and to
 10 permit persons to whom the Software is furnished to do so, subject to
 11 the following conditions:
 12 
 13 The above copyright notice and this permission notice shall be
 14 included in all copies or substantial portions of the Software.
 15 
 16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 17 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 18 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 19 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 20 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 21 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 22 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 23 
 24 Retrieved from: http://en.literateprograms.org/Unlambda_abstraction_elimination_(C_Plus_Plus)?oldid=16427
 25 */
 26 
 27 // ************************************

 28 // *                                  *

 29 // * Unlambda abstraction elimination *

 30 // *                                  *

 31 // ************************************

 32 
 33 #include <iostream>

 34 #include <string>

 35 
 36 // test if the partial expression starting at index is valid Unlambda

 37 // + lambda expressions if the valid functions are the one-character

 38 // functions given in the second argument plus the special functions

 39 // .x and ?x. The index is updated to the end of the tested

 40 // expression.

 41 bool valid_with(std::string const& expression,
 42                 std::string const& functions,
 43                 std::string::size_type& index)
 44 {
 45   static std::string const special = "`.?^";
 46 
 47   int const stoplevel = 0;
 48 
 49   int level = 1;
 50   while (level > stoplevel && index < expression.size())
 51   {
 52     switch (char c = expression[index])
 53     {
 54     case '`':
 55       {
 56         ++level;
 57 	++index;
 58 
 59         break;
 60       }
 61     case '.':
 62     case '?':
 63       {
 64         ++index;
 65 	if (index >= expression.size())
 66 	  return false;
 67 	--level;
 68 	++index;
 69 
 70         break;
 71       }
 72     case '^': // lambda

 73       {
 74         ++index;
 75 	if (index >= expression.size())
 76 	  return false;
 77 	char const arg = expression[index];
 78 
 79 	// the argument may not be a valid function name or special symbol

 80 	if ((functions + special).find(arg) != std::string::npos)
 81 	  return false;
 82 
 83 	++index;
 84 	if (!valid_with(expression, functions + arg, index))
 85 	  return false;
 86 
 87 	--level;
 88 
 89         break;
 90       }
 91     default:
 92       {
 93         if (functions.find(c) == std::string::npos)
 94 	  return false;
 95 	--level;
 96 	++index;
 97 
 98         break;
 99       }
100     }
101 
102   }
103 
104   return level == stoplevel;
105 
106 }
107 
108 // test if the expression is valid Unlambda + lambda expression

109 bool valid(std::string const& expression)
110 {
111   std::string::size_type index = 0;
112   // the second string contains all elementary Unlambda 2.0 functions

113   // except for the two-character functions .x and ?x (those need

114   // special handling)

115   return valid_with(expression, "skivrdce|", index)
116     && index == expression.size();
117 }
118 
119 
120 
121 // find the end of a subexpression (assumes a valid Unlambda

122 // expression starting at pos)

123 std::string::size_type find_end(std::string const& expr,
124                                 std::string::size_type pos)
125 {
126   int level = 1;
127   while (level > 0)
128   {
129     switch(expr[pos])
130     {
131     case '`':
132       ++level;
133       break;
134     case '.':
135     case '?':
136       ++pos;
137       // fall through

138     default:
139       --level;
140     }
141     ++pos;
142   }
143   return pos;
144 }
145 
146 bool safe_for_constant_shortcut(std::string const& expression,
147                                 std::string::size_type start,
148                                 std::string::size_type end,
149                                 char arg)
150 {
151   int applications = 0;
152   for (; start < end; ++start)
153   {
154     switch (expression[start])
155     {
156     case '`':
157       ++applications;
158       break;
159     case 's':
160       {
161         if (applications > 2)
162           return false;
163         applications = 0;
164       }
165       break;
166 
167     case 'k':
168       {
169         if (applications > 1)
170           return false;
171         applications = 0;
172       }
173       break;
174 
175     case 'i':
176       {
177         if (applications > 1)
178           --applications;
179       }
180       break;
181 
182     case 'd':
183       {
184         if (applications == 1)
185         {
186           std::string::size_type end = find_end(expression, start+1) - 1;
187           if (expression.find(arg, start+1) < end)
188             return false;
189           start = end-1;
190         }
191         else if (applications > 1)
192           --applications;
193       }
194       break;
195 
196     case 'v':
197       applications = 0;
198       break;
199 
200     default:
201       if (applications > 0 || expression[start] == arg)
202         return false;
203       if (expression[start] == '.' || expression[start] == '?')
204         ++start;
205       applications = 0;
206 
207     }
208   }
209   return true;
210 }
211 
212 bool safe_for_function_shortcut(std::string const& expression,
213                                 std::string::size_type start,
214                                 std::string::size_type end,
215                                 char arg)
216 {
217   std::string unsafe_chars = std::string(".rde@|") + arg;
218 
219   std::string::size_type pos = start;
220   while (pos < end)
221   {
222     std::string::size_type failpos = expression.find_first_of(unsafe_chars, pos);
223 
224     if (failpos >= end)
225       break; // no bad character found

226 
227     std::string::size_type questionpos = failpos-1;
228     while (questionpos >= start && expression[questionpos] == '?')
229       --questionpos;
230     if ((failpos - questionpos) % 2 == 1) // failpos - questionpos = 1 + number of question marks

231       return false;                       // an even number of question marks means the character is not quoted

232 
233     pos = failpos+1;
234 
235   }
236   return true; // no unquoted bad character found

237 
238 }
239 
240 
241 // eliminate abstraction (assumes a valid expression)

242 std::string eliminate_abstraction(std::string expression)
243 {
244   std::string::size_type pos;
245   while ((pos = expression.rfind('^')) != std::string::npos)
246   {
247     char const argument_name = expression[pos+1];
248     char const what = expression[pos+2];
249     if (what == argument_name)
250     {
251       expression.replace(pos, 3, "i");
252 
253     }
254     else if (what == '`')
255     {
256       std::string::size_type
257         end1 = find_end(expression, pos+3),
258         end2 = find_end(expression, end1);
259 
260       if (safe_for_constant_shortcut(expression, pos+2, end2, argument_name))
261       {
262         expression.replace(pos, 2, "`k");
263       }
264 
265       else if (end2 == end1+1
266                && expression[end1] == argument_name
267                && safe_for_function_shortcut(expression, pos+3, end1, argument_name))
268       {
269         expression.replace(pos, end2-pos, expression.substr(pos+3,end1-pos-3)); // function call shortcut

270       }
271 
272       else
273       {
274         expression.replace(pos, end2-pos,
275                            std::string("``s^") + argument_name
276                            + expression.substr(pos+3, end1-pos-3)
277                            + "^" + argument_name
278                            + expression.substr(end1, end2-end1));
279       }
280 
281     }
282     else if (what == 'v')
283     {
284       expression.erase(pos, 2);
285 
286     }
287     else
288     {
289       expression.replace(pos, 2, "`k");
290 
291     }
292 
293   }
294   return expression;
295 
296 }
297 
298 
299 
300 int main()
301 {
302   std::string expr;
303   while(std::cout << "expression: "
304         && std::getline(std::cin, expr)
305         && expr != "q")
306   {
307     if (valid(expr))
308       std::cout << "result: " << eliminate_abstraction(expr) << "\n\n";
309     else
310       std::cout << "invalid expression\n\n";
311   }
312 }
313


Retrieved from "http://en.literateprograms.org/Special:Downloadcode"
Views
Personal tools