Tuesday, April 24, 2007

Lazy streams

I'm currently implementing a Prolog inference engine as a metalua extension, and I needed lazy streams (potentially infinite lists, whose elements are computed only when they're first needed). The variable substitutions which describe Prolog solutions are generated on demand and held in these immutable streams once computed. I guess there could have been a good solution based on coroutine + memoization, but it's just too hard not to think of this problem in Haskell. I'll try an hybrid solution (a stream fed on demand by a coroutine) once I've got a first prototype running Since streams are quite a common tool, I'm putting them in an external (tiny) lib. Usage sample here. The early lessons drawn from this attempt:
  • When writing functional code, I use extended syntaxes a lot. Hardly surprising, Lua always felt procedural, despite its functional-ready semantics.
  • These operators don't give a Lua feeling. Actually, the code above looks like some Perl... Maybe a textual syntax for the "?/," ternary operator would improve things. I also suspect that mandatory parentheses in function calls contribute to the visual messiness. An Haskell-style "$" operator would spare some of them, but might further perlify the code's appearance. If only statement separators were mandatory in Lua, that's one of those stuff which would be so easy to fix!
  • OTOH, functional metalua code is really terse, and that's a good thing.
  • The issue of functional programming in metalua is complex, and deserves much more investigation. Implementing a functional dialect would be at least interesting, and maybe even useful, if it could cohabit nicely with procedural fragments in a single source file.
Some notes about the syntax extensions used in the sources:
  • |a,b,c|foobar is the same as function(a,b,c) return foobar end (part of core metalua)
  • x?y,z evaluates to y if x is true, z if x is false (from -{extension "ternary"})
  • %{ ... } is a lazy table, i.e. the field values are computed only when they're first extracted (from -{extension "lazy"}).

No comments: