Path: utzoo!attcan!uunet!seismo!ukma!rex!fs From: fs@rex.cs.tulane.edu (Frank Silbermann) Newsgroups: comp.lang.functional Subject: Laziness and Leftmost Rule Message-ID: <3462@rex.cs.tulane.edu> Date: 1 Jun 90 17:57:01 GMT References: <1539@sys.uea.ac.uk> Organization: Computer Science Dept., Tulane Univ., New Orleans, LA Lines: 39 Bjorn Lisper > But there must be cases where some argument > to a non-strict function has to be evaluated > in order to determine what is to be done next, > even in a lazy language. In all languages I've seen, > lazy or not, this is done on a left to right basis. The theoretical justifications for purely leftmost evaluation were developed for in syntactic term-rewriting systems and also for the pure untyped lambda calculus. Many assume that the justifications carry over to more complicated languages. This is not always true. > The fact that leftmost-outermost reduction works > for the lambda calculus (in the sense that this strategy > will find the normal form of any lambda expression > which has one) is an uninteresting quirk ... So, > there's a problem with the very theoretical foundations > of functional programming! Conventional wisdom is that the pure untyped lambda calculus is the theoretical basis of Lisp-like functional programming. If you choose to view logical and mathamatical primitives as syntactic sugar for pure lambda expressions (whose operational behavior seems to simulate execution of these primitives), then you have no right to complain if these simulated operators sometimes do not behave the way logical and mathamatical primitives ought. If you want numbers and booleans to behave according to the rules, then you should base your language on a lambda calculus which admits numbers and booleans as distinct expression types (i.e. a typed lambda calculus). Then you can throw in arithmetic and boolean primitives whose parallel evaluation mechanisms have nothing to do with beta-reduction. Frank Silbermann Tulane University, New Orleans, Louisianna, USA fs@rex.cs.tulane.edu