April 2002 - Haskell - Haskell.org

free variables in lambda terms ?
by Konst Sushenko 26 Apr '02

26 Apr '02

hi, would someone please help me with the question below? i tried asking on comp.lang.functional list but noone responded... "konsu" <konsu(a)hotmail.com> wrote in message news:<ATOx8.42722%24t65.9246(a)nwrddc02.gnilink.net>... > hello, > > as an exercise, i am trying to implement a pure lambda calculus interpreter. > i am using normal order reduction with textual substitution of terms. > > a program that my interpreter accepts is a list of name/term declarations: > > <name 1> = <lambda term 1> > ... > <name N> = < lambda term N> > > each declaration defines a global name and binds a term to it, and the > interpreter starts evaluation with the term named 'main'. > > > i implemented all the functions necessary to evaluate a closed lambda term, > and now i got to the point where i need to handle free variables in a term. > my assumption is that free variables denote terms declared as above. > > my question is when should i expand free variables? i also would appreciate > any references to literature, etc. where this is discussed. > > so far i believe the way to do it is to reduce a term to its normal form > without handling free variables, and then, if it has free variables, look up > their definitions in the environment and replace them with their bodies, > evaluate the resulting term to its normal form again, and keep repeating > this process until no free variables are found. > > is this the right way to do it? or should i check for free variables when i > compute the WHNF, etc.? any advice from the experts? > > thanks > konst > >

2 1

RE: Syntax of functional dependencies
by Simon Marlow 26 Apr '02

26 Apr '02

> I errorneously specified categories as > > class (Eq object, Eq morphism) => > Category id object morphism | id ->, id -> morphism > where o :: id -> morphism -> morphism -> Maybe morphism > dom, cod :: id -> morphism -> object > > it should have been > > class (Eq object, Eq morphism) => > Category id object morphism | id -> object, id -> morphism > ... ^^^^^^ > > - but ghci 5.02.2 does not complain. Why? The syntax of a functional dependency is (from GHC's parser): fd : varids0 '->' varids0 varids0 : {- empty -} | varids0 tyvar so the list of tyvars on either side of the '->' can be empty. Functional dependency experts can correct me if I'm wrong, but I imagine though that 'a ->' is not a very useful functional dependency (isn't it the same as giving no functional dependency at all?), and '-> a' means that there can only ever be one instantiation for 'a' in the whole program. Cheers, Simon

1 0

Re: free variables in lambda terms ?
by John Hughes 26 Apr '02

26 Apr '02

"konsu" <konsu(a)hotmail.com> wrote in message news:<ATOx8.42722%24t65.9246(a)nwrddc02.gnilink.net>... > hello, > > as an exercise, i am trying to implement a pure lambda calculus interpreter. > i am using normal order reduction with textual substitution of terms. > > a program that my interpreter accepts is a list of name/term declarations: > > <name 1> = <lambda term 1> > ... > <name N> = < lambda term N> > > each declaration defines a global name and binds a term to it, and the > interpreter starts evaluation with the term named 'main'. > > > i implemented all the functions necessary to evaluate a closed lambda term, > and now i got to the point where i need to handle free variables in a term. > my assumption is that free variables denote terms declared as above. > > my question is when should i expand free variables? i also would appreciate > any references to literature, etc. where this is discussed. > > so far i believe the way to do it is to reduce a term to its normal form > without handling free variables, and then, if it has free variables, look up > their definitions in the environment and replace them with their bodies, > evaluate the resulting term to its normal form again, and keep repeating > this process until no free variables are found. > This is certainly one reasonable possibility. Alternatively, you could replace a free variable by its value as soon as you encounter it in a reduction context (i.e. at the point where your reducer would make the next reduction step). Since you're aiming for normal forms rather than weak head normal forms, you presumably will substitute for free variables under lambdas. I assume you're being careful not to capture variable names during substitution -- beware of cases like f = g g = 1 main = (\g.f) 2 where substituting for f in main must rename the local variable g to avoid a name clash with the global g. Given the Church-Rosser property, it doesn't really matter when you substitute for free variables -- you should get the same result in any case. The only thing to be careful of is that you don't substitute "too eagerly", and thus fall into an infinite loop. Global definitions are presumably the only way to achieve recursion in your system (apart from using Y); substituting too eagerly in recursive definitions will of course lead to loops. Just consider fac = \n. if (== n 0) 1 (* n (fac (- n 1))) where if you substitute for fac before applying the lambda-expression, you clearly fall into a loop. John Hughes

1 0

Re: some algorithms are hard to code in O(n) in Haskell
by Ch. A. Herrmann 25 Apr '02

25 Apr '02

Hi, first of, you should consider whether you really need O(n). Since you want to use Haskell, your aim is probably more on elegance than on performance. Maybe, an Theta(n * log n) program in Haskell would be easier to verify. Surely, you can program in imperative style in Haskell achieving optimal complexity, using arrays with destructive updates (check the Glasgow extensions). For some O(n) graph algorithms (like connected components), there is an elegant optimal solution by John Launchbury: "Graph algorithms with a functional flavour", Springer Lecture Notes in Computer Science 925, pp. 308--331, 1995. Good luck -- Christoph Herrmann

1 0

Syntax of functional dependencies
by Till Mossakowski 25 Apr '02

25 Apr '02

I errorneously specified categories as class (Eq object, Eq morphism) => Category id object morphism | id ->, id -> morphism where o :: id -> morphism -> morphism -> Maybe morphism dom, cod :: id -> morphism -> object it should have been class (Eq object, Eq morphism) => Category id object morphism | id -> object, id -> morphism ... ^^^^^^ - but ghci 5.02.2 does not complain. Why? Till Mossakowski -- Till Mossakowski Phone +49-421-218-4683 Dept. of Computer Science Fax +49-421-218-3054 University of Bremen till(a)tzi.de P.O.Box 330440, D-28334 Bremen http://www.tzi.de/~till

1 0

Announcement: WASH/CGI 1.0
by Peter Thiemann 25 Apr '02

25 Apr '02

WASH/CGI Web Authoring System for Haskell WASH/CGI is an embedded DSL for server-side Web scripting based on the purely functional programming language Haskell. Its implementation is based on the portable common gateway interface (CGI) supported by virtually all Web servers. WASH/CGI offers a unique and fully-typed approach to Web scripting. It offers the following features * a monadic interface to generating HTML output * type-safe compositional approach to specifying form elements * callback-style programming interface for forms * automatic error detection * complete interactive script in one program * type-safe interfaces to state with different scopes: interaction, persistent client-side (cookie-style), persistent server-side * integration with CSS yields compositional style descriptions * on-the-fly generated graphics * high-level interface to email generation Download WASH-CGI-1.0 from http://www.informatik.uni-freiburg.de/~thiemann/WASH/

1 0

RE: "do" notation and ">>"
by Simon Marlow 24 Apr '02

24 Apr '02

> > I don't believe that it will break many programs. How many programs > > produce large *input independent* output, that is not already > > literally in the source, in a caf with a long life-time? > > That sounds like a description of all the animation programs in Paul > Hudak's School of Expression book and there's plenty more examples > like that. > > [I haven't tested whether these programs do leak space with the > modified compiler - my point is that there is a large class of > programs with exactly the characteristics you describe.] > > -- > Alastair Reid > > ps I think your CAF restriction is a bit of a red herring - Koen's > modification to make his example leak in GHC (which GCs CAFs) shows > that the leak happens as long as the relevant thunk isn't collected. This whole discussion is a red herring. The Haskell report doesn't say anything about sharing - it doesn't even mandate laziness (look in the index - you won't find the term "lazy" :-). Different compilers will behave differently, GHC in particular will probably share <expr2> in Koen's example f = do <expr1> <expr2> regardless of whether the translation uses >> or >>=, because GHC implements full laziness (when -O is turned on). So you might reasonably argue that Haskell should provide more control over such things, and I might well agree. But there's no point in discussing whether using >>= or >> in the translation of do-notation is better: they're both equivalent as far as the current language specification is concerned. Cheers, Simon

2 1

CFP: 2002 Haskell Workshop ** 1 month until submission deadline **
by Manuel M. T. Chakravarty 24 Apr '02

24 Apr '02

[My apologies if you receive multiple copies of this message] ------------------------------- C A L L F O R P A P E R S ** 1 month until submission deadline ** ------------------------------- ACM SIGPLAN 2002 Haskell Workshop Pittsburgh, PA, USA 3rd October 2002 (as part of PLI'02) =================================== The purpose of the Haskell Workshop is to discuss experience with Haskell, and possible future development of the language. The scope of the workshop includes all aspects of the design, semantics, theory, application, implementation, and teaching of Haskell. Previous Haskell Workshops have been held in La Jolla (1995), Amsterdam (1997), Paris (1999), Montreal (2000), and Firenze (2001). For detailed information please consult http://www.cse.unsw.edu.au/~chak/hw2002/ Submission deadline: *** 24th May 2002 *** ** Haskell Users: P L E A S E N O T E ** * Have you used Haskell for a non-toy application? Or have you developed a new Haskell tool? If you are interested in demonstrating your application or tool at the workshop, please contact the PC chair <chak(a)cse.unsw.edu.au> until 1 May, so that we can judge demand.

1 0

Stunningteens.com 100% Original Content
by stunningteens＠cashnews.com 24 Apr '02

24 Apr '02

1 0

RE: "do" notation and ">>"
by Simon Peyton-Jones 24 Apr '02

24 Apr '02

| So, changing the translation in GHC might actually introduce | a very nasty space leak in existing programs! It might, conceivably. But the H98 report doesn't seem the right place to try to tweak full laziness. So I'm going to leave the report as it is. Hugs and GHC have changed to match. Simon

5 4