home *** CD-ROM | disk | FTP | other *** search
/ Gold Fish 3 / goldfish_volume_3.bin / files / dev / e / amigae / src / lang / lambda.e < prev   
Text File  |  1992-09-02  |  2KB  |  75 lines
  1. /* lambda calc evaluator in E, makes heavy use of unification */
  2.  
  3. DEF nchar="a"
  4.  
  5. ENUM ATOM,LAMBDA,APP
  6.  
  7. PROC ev(exp)
  8.   DEF par,body,fun,arg
  9.   IF exp <=> [APP,fun,arg]
  10.     funval(fun) <=> [LAMBDA,par,body]
  11.     RETURN ev(replace(body,par,arg))
  12.   ELSE
  13.     RETURN exp
  14.   ENDIF
  15. ENDPROC
  16.  
  17. PROC funval(exp)
  18.   DEF x,y
  19.   IF exp <=> [APP,x,y]
  20.     RETURN funval(ev(exp))
  21.   ELSEIF exp <=> [ATOM,x]
  22.     RETURN funval(getdef(x))
  23.   ELSE
  24.     RETURN exp
  25.   ENDIF
  26. ENDPROC
  27.  
  28. PROC replace(exp,old,new)
  29.   DEF fun,arg,par,body,a,n
  30.   IF exp <=> [APP,fun,arg]
  31.     RETURN NEW [APP,replace(fun,old,new),replace(arg,old,new)]
  32.   ELSEIF exp <=> [ATOM,a]
  33.     RETURN IF a=old THEN new ELSE exp
  34.   ELSEIF exp <=> [LAMBDA,par,body]
  35.     new <=> [ATOM,a]
  36.     IF par=a
  37.       RETURN NEW [LAMBDA,n,replace(replace(body,par,NEW [ATOM,nchar++]),old,new)]
  38.     ELSE
  39.       RETURN NEW [LAMBDA,par,replace(body,old,new)]
  40.     ENDIF
  41.   ENDIF
  42. ENDPROC
  43.  
  44. PROC pretty(exp)
  45.   DEF x,y
  46.   IF exp <=> [APP,x,y]
  47.     pretty(x)
  48.     PutStr(' (')
  49.     pretty(y)
  50.     PutStr(')')
  51.   ELSEIF exp <=> [LAMBDA,x,y]
  52.     PrintF('\\\c.',x)
  53.     pretty(y)
  54.   ELSEIF exp <=> [ATOM,x]
  55.     PrintF('\c',x)
  56.   ENDIF
  57. ENDPROC
  58.  
  59. PROC getdef(a)
  60.   SELECT a
  61.     CASE "t"; RETURN [LAMBDA,"x",[LAMBDA,"y",[ATOM,"x"]]]
  62.     CASE "f"; RETURN [LAMBDA,"x",[LAMBDA,"y",[ATOM,"y"]]]
  63.     DEFAULT;  Raise()
  64.   ENDSELECT
  65. ENDPROC
  66.  
  67. PROC main()
  68.   DEF exp
  69.   exp:=[APP,[APP,[ATOM,"t"],[ATOM,"t"]],[ATOM,"f"]]
  70.   pretty(exp)
  71.   PutStr(' results in ')
  72.   pretty(ev(exp))            -> prints: 't (t) (f) results in t'
  73.   PutStr('\n')
  74. ENDPROC
  75.