Re: Functional programming

Jon Harrop <jon@ffconsultancy.com> writes:


  I wrote a purely functional parser in Java once for fun.

  That is, all assignments are final, thus, there are no
  storage modifications. No side effects used anywhere
  (except in the test code and in the debug code, which
  does the side-effect of printing.) Code is given below.

  The building scheme of the ?functional? methods
  of the scanner and parser below is always like:

let x0 = ...
    x1 = ...
    x2 = ...
in ...

  which, in Java, is written as

{ final x0 = ...;
  final x1 = ...;
  final x2 = ...;
  return ...; }

  (When replying to my post, please do not quote my complete
  post, but only those parts you directly refer to.
  Especially, please do not quote the complete source code.)

public class List
{
  // implementation of a dotted pair

  private final int car; private final List cdr;
  List( final int car, final List cdr ){ this.car = car; this.cdr = cdr; }

  // That was the actual class ?List?
  // The rest are static methods.

  // support for lists

  private static final boolean DEBUG = false;
  static List cons( final int car, final List cdr )
  { return new List( car, cdr ); }
  static int fst( final List l ){ return l == null ? INVALID : l.car; }
  static List rest( final List l ){ return l == null ? null : l.cdr; }
  static int snd( final List l ){ return fst( rest( l )); }
  static int caddr( final List l ){ return fst( rest( rest( l ))); }
  static List cddr( final List l ){ return rest( rest( l )); }
  static List cdddr( final List l ){ return rest( cddr( l )); }
  static String prints( final List l )
  { return l == null ? "" : "" + name( fst( l ))+ ", " + prints( rest( l )); }
  static List print( final List l )
  { if( DEBUG )System.out.println( "( "+ prints( l ) + " )" ); return l; }
  static List print( final String s, final List l )
  { if( DEBUG )System.out.println( s + "( "+ prints( l ) + " )" ); return l; }

  // main with some test cases

  public static void main( String[] args )
  { System.out.println( "" + evaluate( "(3+4)*2" ) + " [14]." );
    System.out.println( "" + evaluate( "2*10" ) + " [20]." );
    System.out.println( "" + evaluate( "(9+9)*9+9" ) + " [171]." );
    System.out.println( "" + evaluate( "3*(4+5)" ) + " [27]." );
    System.out.println( "" + evaluate( "3*(4*5)" ) + " [60]." );
    System.out.println( "" + evaluate( "3*(4+5)*2" ) + " [54]." );
    System.out.println( "" + evaluate( "3*(4*5)+2" ) + " [62]." );
    System.out.println( "" + evaluate( "1+1+1+1+1+1" ) + " [6]." );
    System.out.println( "" + evaluate( "2*2*2*2*2*2" ) + " [64]." );
    System.out.println( "" + evaluate( "1+1+(2*2*2)+1+1" ) + " [12]." );
    System.out.println( "" + evaluate( "1+1+(1+1+1)+1+1" ) + " [7]." );
    System.out.println( "" + evaluate( "2*2*(2+2+2)*2*2" ) + " [96]." );
    System.out.println( "" + evaluate( "2*2*(2*2*2)*2*2" ) + " [128]." );
    System.out.println( "" +
      evaluate( "2*2*((1+1)*2*2)*2*2" ) + " [128]." );
    System.out.println( "" +
      evaluate( "2*2*(2*(1+1)*2)*2*2" ) + " [128]." );
    System.out.println( "" +
      evaluate( "2*2*(2*2*(1+1))*2*2" ) + " [128]." );
    System.out.println( "" +
      evaluate( "2*2*(2*(1+1)*(1+1))*2*2" ) + " [128]." );
    System.out.println( "" +
      evaluate( "2*2*((1+1)*(1+1)*2)*2*2" ) + " [128]." );
    System.out.println( "" +
      evaluate( "2*2*((1+1)*(1+1)*(1+1))*2*2" ) + " [128]." );
    System.out.println( "" +
      evaluate( "0+2*2*((1+1)*(1+1+0)*(1+1))*2*2+0" ) + " [128]." );
    System.out.println( "" +
      evaluate( "10+2*2*((1+1)*(1+1+0)*(1+1))*2*2+10" ) + " [148]." );
    System.out.println( "" +
      evaluate( "10+2*2*((1+1)*(1+1+0)*(1+1))*2*2+100" ) +
      " [238]." ); }

  // the evaluator

  static int evaluate( final String string )
  { return fst( expression( tokenize( string ))); }

  // syntactical analyzer

  static List expression( final List arg )
  { final List tokens = term( arg );
    final int term = fst( tokens );
    final int operator = snd( tokens );
    final List tail = cddr( tokens );
    final List tailval = operator == PLUS ? expression( tail ) : null;
    return tail == null ? cons( term, null ) :
    operator == PLUS ? cons( term + fst( tailval ), rest( tailval )) :
    operator == R_PAREN ? cons( term, tail ) : null; }

  static List term( final List arg )
  { final List pair = factor( arg );
    final int result = fst( pair );
    final List tokens = rest( pair );
    final List tail = rest( tokens );
    final List tailval = factor( tail );
    return tail == null ? cons( result, null ) :
    fst( tokens ) == MUL ?
    term( cons( result * fst( tailval ), rest( tailval ))) :
    cons( result, tokens ); }

  static List factor( final List arg )
  { final int result = fst( arg );
    final List tokens = rest( arg );
    return result >= NUMBER ? cons( result, tokens ) :
    result == L_PAREN ? expression( tokens ) : null; }

  // support for the lexical analyzer

  static int numlen( final String s )
  { final boolean done = s.equals( "" );
    final boolean valid = !done;
    final String r = valid ? s.substring( 1, s.length() ): "";
    final char c = valid ? s.charAt( 0 ): 0;
    final boolean isdigit = Character.isDigit( c );
    return done ? 0 : isdigit ? 1 + numlen( r ) : 0; }

  static int max( final int i, final int j )
  { return i > j ? i : j; }

  // The lexical analyzer

  static final int NUMBER = 0;
  static final int INVALID = -1;
  static final int PLUS = -2;
  static final int MUL = -3;
  static final int L_PAREN = -4;
  static final int R_PAREN = -5;

  static String name( final int l )
  { return l >= NUMBER ? "" + l : l == INVALID ? "INVALID" :
    l == PLUS ? "PLUS" : l == MUL ? "MUL" : l == L_PAREN ? "L_PAREN" :
    l == R_PAREN ? "R_PAREN" : "(UNKNOWN)"; }

  static List tokenize( final String s )
  { final boolean done = s.equals( "" );
    final boolean valid = !done;
    final String r =
    valid ? s.substring( max( 1, numlen( s )), s.length() ): "";
    final char c = valid ? s.charAt( 0 ): 0;
    final boolean isdigit = Character.isDigit( c );
    final int d = isdigit ?
    Integer.valueOf( s.substring( 0, numlen( s ))).intValue() : 0;
    return done ? null : cons
    ( ( isdigit ? d : c == '+' ? PLUS : c == '*' ? MUL :
        c == '(' ? L_PAREN : c == ')' ? R_PAREN : INVALID ),
      tokenize( r )); }}

/*
171 [171].
27 [27].
60 [60].
54 [54].
62 [62].
6 [6].
64 [64].
12 [12].
7 [7].
96 [96].
128 [128].
128 [128].
128 [128].
128 [128].
128 [128].
128 [128].
128 [128].
128 [128].
148 [148].
238 [238].
*/

  When replying to my post, please do not quote my complete
  post, but only those parts you directly refer to.
  Especially, please do not quote the complete source code.