mutually recursive definitions?

[ownwaterloo]

Mutually recursive definitions could be done by letrec in Scheme. It can't be done by with which introduces only one binding. How to define mutually recursive functions?

[wolfgangj]

For global definitions, we have declare. For locals, I don't see the need. Can you show me examples that illustrate their actual usefulness for real programs?

In general, Bone Lisp has a very different approach than Scheme: Simplicity of the implementation is quite important for Bone. Currently, I think letrec has too high a cost given it's IMO limited usefulness. But of course, I can be convinced that I am wrong. :)

[chrisosaurus]

I am unsure about letrec, however one example that convinced me a little was seeing them used to model a state machine in scheme as a set of co-recursive functions - that is each state would call the next state.

These functions were 'hidden' within a scope so that an outsider could not enter as an arbitrary state, there was a smaller set of valid starting states.

This worked due to scheme's TCO, otherwise this approach would blow up for large state machines.

Skimming the README it states that bone supports TCO.

For an example of this kind of state machine implementation please see http://www.ai.mit.edu/projects/dynlangs/ll1/shriram-talk.pdf pages 32 through 40.

[wolfgangj]

I have to admit, that's a really nice use case.

[ownwaterloo]

The lisp reader could be written as a group of mutually recursive subroutines(e.g. read and read-shortcut), right? On the other hand, obviously, it isn't the only way.

About declare , is it conflicted with hyperstatic?

For local helper subs you can use mysub, which does not require a docstring and introduces a binding that may be overwritten later. Note that the environment is hyperstatic (as in Forth): If you redefine something, the subs previously defined will continue to use the old definition.

What is the cost of letrec? Is it a runtime efficiency cost? Or it will complicate the implementation? Or something else? Thanks.

[wolfgangj]

For a reader implementation, you would use mutually recursive subs, but probably not define them locally with letrec. One reason is that defining them as global subs which can be called on their own makes testing them easier.

You're right, there is a small conflict between declare and a hyperstatic environment, i.e.

(declare foo)
(mysub (bar) (foo))
(mysub (foo) (say "foo 1\n"))
;; later, elsewhere:
(mysub (foo) (say "foo 2\n"))
(bar)
;; => prints "foo 2"

But I think without declare, you couldn't have mutual recursion in a hyperstatic environment at all. Adding a real module system would also solve this.

In practice, often one of the mutually called subs is a public interface, in which case there is also no problem:

(declare foo)
(mysub (bar) (foo))
(defsub (foo) "..."
  ...)

Since foo has been defined with defsub, it can not be redefined later.

The cost of letrec is that it makes the compiler implementation more complicated, which is already the most complex part. Will probably be quite hard to understand, maintain and debug. If there is an actual need for it, it makes sense to implement it. If nobody needs it urgently, it seems better to me leave it out (for now). A binding construct like traditional let (i.e. which makes the variable visible only after evaluating the expression) would be more urgently needed, I think, since not having it prevents things like nested aif. :-/

[ownwaterloo]

Thanks for explaining the cost of letrec and other bits.

When moving definitions from local to global:

• Their scopes will be extended.
• The local environment is invisible to them

For instance, suppose in this expression: (filter (lambda (x) (and (< lower x) (< x upper))) ...), < and and are resolved to their standard definitions and lower and upper are local bindings (or expressions depend on local environment). Alternatively, it could be a global definition: (define (between lower upper x) (and (< lower x) (< x upper))) and used locally by partial application: (lambda (x) (between lower upper x)).

When moving it from local to global:

• It must have a name. And this will make testing easier.
• It's better to have a descriptive name. between is still ambiguous. But between-exclusive-exclusive is too long. An module system could make this definitions invisible to other module, so between could be a reasonable name.
• There are some refactoring work: move local dependencies to parameters and then partial apply.

Mutually recursive definitions are the same as above except that the refactoring work is more difficult. The dependencies are transitive now. For example: g shall have additional parameters for f if f is called by g. On the other hand, I have to admit, I couldn't find a practical example to demonstrate this. I tried, failed and gave up. So I agree with you, local mutually recursive definitions is not urgent.

[wolfgangj]

I would just like to add that hyperstatic bindings (those defined with mysub) are not used in other modules by convention. So they are effectively invisible. It should be effortless to migrate code that follows this convention to a module system if desired.

[ownwaterloo]

I have no more problem on this topic. Thank you for the information!

[wolfgangj]

Okay, I'll close it.