bluespec.com Forum Index bluespec.com
Bluespec Forums
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

recursive modules

 
Post new topic   Reply to topic    bluespec.com Forum Index -> Non-technical discussions and questions
View previous topic :: View next topic  
Author Message
christinamsmith



Joined: 24 Aug 2012
Posts: 7

PostPosted: Mon Oct 01, 2012 11:03 am    Post subject: recursive modules Reply with quote

I am looking through the MIT 6.375 BSV lecture slides and ran into recursive modules.
Code:
module mkFix#(Tuple2#(Fetch, Execute) fe)
         (Tuple2#(Fetch, Execute));  
  match{.f, .e} = fe;  
  Fetch     fetch <- mkFetch(e);  
  Execute execute <- mkExecute(f);  
  return(tuple2(fetch,execute));
endmodule    

(* synthesize *) module mkCPU(Empty);  
  match {.fetch, .execute} <- moduleFix(mkFix);
endmodule

The comment "moduleFix is like the Y combinator F = Y F" is listed below the code. I am not familiar with the Y combinator and am hoping someone can help me clarify the connection between the Y combinator and moduleFix in this example.
Back to top
View user's profile Send private message
jnewbern



Joined: 18 Jul 2007
Posts: 71

PostPosted: Mon Oct 01, 2012 12:13 pm    Post subject: Reply with quote

Christina,

That slide is playing a little bit loose with the terminology. The Y combinator is a fixed point combinator in the untyped lambda calculus, but moduleFix is obviously not in an untyped lambda calculus setting. The mention of the Y combinator was a kind of short-hand analogy for anyone in the audience that was already familiar with the Y combinator. The actual definition given in the slide (F = Y F), is also just an evocative equation, not a formal definition.

The important thing to know is that moduleFix is a fixed point combinator for constructing recursive modules. It is a higher-order module that takes another module as an argument and constructs a possibly recursive module by evaluating that argument module repeatedly until a fixed point is reached. The type of the module argument should be such that is takes an argument and returns a value/interface of the same type as its argument. Because the argument and return types are the same, you can conceptually chain together instantiations of this module, passing the return value of one as the argument of the next. The type of moduleFix is such that it can take this module as an argument and construct a possibly recursive module through repeated application, returning the final interface. You can think of it as
Code:
moduleFix m = m(moduleFix(m));

if that helps to clarify the types and role of moduleFix. Obviously, the argument module m needs to terminate the recursion at some point by not instantiating a sub-module based on its argument.

YOU DO NOT NEED TO USE MODULEFIX TO CONSTRUCT RECURSIVE MODULES. A module is allowed to instantiate itself as a sub-module directly without using a fixed point combinator. The only time you really need to use moduleFix is to create MUTUALLY recursive modules, which is what is shown in that example: mkFetch and mkExecute each take each other's interface as arguments.

In code which will be exposed to users, it is generally best to avoid using moduleFix because no one will understand it. There are alternative solutions which are more verbose but easier to follow, by modifying the interfaces of the modules so that they can be individually instantiated as siblings which interact through Connectable methods and interfaces.

If you are interested in mastering moduleFix to satisfy your own curiosity, then I suggest that you start by studying fixed point combinators in the setting of functions. When that makes sense, then moduleFix will be easy to understand by analogy.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    bluespec.com Forum Index -> Non-technical discussions and questions All times are GMT - 4 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You cannot download files in this forum
bluespec.com topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group
Protected by Anti-Spam ACP