I’ve been trying to implement memoizing existing recursive functions without the user needing to change the function’s definition. So for example: , with the original definition:
Memoizing is a rather simple operation, but one needs to make a few adaptations within the original function’s definition (or implementation, as IMO is a more fitting term). Since, as implied above, I strive to automate that process, I’m going to achieve that through metaprogramming. While I'm at it anyway, I want to include the memoizing process in one go. So I’m trying to implement two changes in a function’s definition - and the function may be any (recursive) reporter (or predicate) provided that its result is fully determined by its formal input parameters:
Replace any recursive calls with calls to the name of the new function. So far, this has proven to be the easy part.
Replace any REPORT (some expression) blocks with SET (value) TO (some expression); ADD (LIST (key) (value)) TO (memory); REPORT (value). This is the hard part.
In order to manipulate code it has to be transformed to a (usually multilevel) list using SPLIT (code) BY (block).
Annoyingly, if the code is only one block (“REPORT” …), the formal input parameters are the final items of the main list. If, however, the code consists of multiple blocks, the parameters are the final sub-items of item 1. Perhaps this is handy for the interpreter executing the code, but not so if one’s trying to change the code - I built a parameter stripper and a reassembler in order not to unnecessarily complicate other operations:
Thank you for reporting the problems and for the code to fix one of them! I'm theoretically writing a library to convert between the list representation made by SPLIT BY BLOCKS and a more coherent abstract syntax tree, so that'll be a starting point.
I agree that memoization is a great example for metaprogramming. (Although if you look up "Y Combinator" I think you'll find that this should theoretically be doable at the non-meta (functions as black boxes) level. You have to use the complicated version for applicative scope languages. I haven't actually experimented with it.)
I think if a toplevel expression in the SPLIT BY BLOCKS structure is a reporter, REPORT is implied. That's how to work around not having an explicit REPORT in the tree.
IMO the first step towards a easier-to-use list representation of code (and by implication, easier metaprogramming) would be to better document the current mechanism (quirks and all included) for advanced users - they'll find a way to work with it, share solutions, or may even be willing to write code for your as yet imaginary library (if you can specify what functions are required).
I didn’t find “Y combinator” in A&S, and don’t understand what Wikipedia has on it (the formal syntax of Lambda calculus defies me, to be honest). Could you present a simple example of using a (the?) Y combinator with a recursive function - say: factorial, or fibonacci - in Snap! ?
… or a predicate (which I consider a special kind of reporter) - I agree, and I can probably work around it, now that I know. Thx.
Sometimes I try to maintain a distinction between "reporter" meaning "Reporter or Predicate" and "Reporter" meaning "round not hexagonal." But I haven't been consistent about that because it's an unpronounceable distinction, the same reason I think identifiers should be case insensitive. ;~)
Ugh. I might be able to if I change the names of the variables so they're all unique. But I don't think I could do it better than you could... I could give you my Church numeral exercises just for fun, but that version of Y is so simplified as to require the changes to the procedure text that you're trying to avoid.
I'm not sure anyone but Jens knows all the quirks!
The idea of an abstract syntax tree is that instead of, for example, representing a procedure call as a tree whose head is the procedure, you make a tree whose head is the text "procedure call" with two children, one whose head is "procedure" and the other whose head is "inputs". The latter has children named "actual input expression", and so on. So, it's a way deeper tree, but it's trivial to convert to and from runnable code -- no quirks.
Besides if you want to convert to and from an abstract syntax tree you would need to know the quirks anyway. Unless the abstract syntax tree is going to be the primary storage format for code - which may be a wise goal to pursue, but that would probably take much more effort than creating some library functions (or am I misunderstanding the concept?)
That sounds great!
I understand some of it, but I'm not quite there yet. Considering this is an easy version of Y combinator, I'll stick with metaprogramming for now
The idea is that the library will be so wonderful that nobody will use the raw primitives, which were really designed to be minimal to implement rather than usable. :~) When it's done, it'll include hygienic macros, pattern matching, a non-quirky DEFINE, a layer of abstraction above all the unpleasantnesses you guys keep finding, starch, spaghetti, cholesterol, all the better things. And its blocks will all be the same color. (Overloading SPLIT and JOIN is a kludge imho.)
I said it when we talked recently! And I even thought you agreed with me that it'd be better if all the metaprogramming blocks were in the Control palette.
Lord, has it really been two years already? Time sure flies when you're not doing anything. :~/ Back then, I was so psyched that we finally had the capability that I wasn't going to tell you to redesign it, especially since this is just an instance of a larger disagreement we have about overloading blocks, e.g., LENGTH, and I didn't think there was any chance of convincing you at that point.
Not sure if I can... The first thing I notice is that the REPORT inside the RUN/CC never happens, because the continuation doesn't return to its caller, but rather to the caller of RUN/CC, i.e., the part of the script under the RUN/CC. But then I'd expect it to do the IF and the (final) REPORT, all with N=1. I tried adding logging instructions and indeed that seems to be what's happening.
But since the continuation was made with RUN/CC, not CALL/CC, I tried replacing your REPORT (CALL CONT) with just RUN CONT, and then RECURSIVE reports 1 as expected.
In my experience using block variables is just not advisable with recursive functions, as new instances are created with each recursive call. I'm still working on creating a memoizer that will take a naive recursive function as input, and I decided to use a global variable I have called "lookup tables":
About block variables and recursion in Snap!:
I probably exaggerated when I wrote that a new instance of any block variable is created with each recursive call. Still I encountered an issue with block variables and recursion. I created a recursive function and a little test script to demonstrate it:
Apparently, in the above demonstration, there are two instances of the block variable "count":
One that's used when the function is called by the user / script;
Another that's used when the function is called by itself (= recursion).
Perhaps this is what @dardoro referred to when he wrote: "Block variables are callsite bound & persistent".
Nevertheless, IMO, it implies that a block variable can (or should) not be used within a recursive function, QED.
, with the original definition: 
