8
$\begingroup$

Background: I am trying to write a program that can execute scheme in Mathematica.

Now I have things like {"+", 3, {"-", 2, {"'", {"*", 1, 3}}}}. The syntax converting function I have now is:

convertlist[expr_] := 
Hold[expr] //. {a_, b___} :> scmfun[a][b] // ReleaseHold

Which works fine with expressions without '. ' in scheme means hold all the expression inside, but none of the non-standard evaluation function can stop the substitution, and lots of small changes won't work because ReplaceRepeated will eventually get to the inside expression . and the workaround I currently have seems to be very strange and complex (have to give up this simple design).

My question is that can this function be modified so that everything inside ' is unchanged, i.e.:convertlist[{"+", 3, {"-", 2, {"'", {"*", 1, 3}}}}] will return

scmfun["+"][3, scmfun["-"][2, {"*", 1, 3}]] 

instead of

scmfun["+"][3, scmfun["-"][2, scmfun["'"][scmfun["*"][1, 3]]]]
$\endgroup$
  • $\begingroup$ maybe convertlist2[expr_] := Hold[expr] /. {{"'", {x__}} :> foo[x]} //. {a_, b___} :> scmfun[a][b] /. foo -> List // ReleaseHold? $\endgroup$ – kglr Apr 3 '16 at 9:39
  • $\begingroup$ @kglr thanks for your idea, but this function can only hold one level of the expression, i.e. convertlist2[{"+", 3, {"-", 2, {"'", {1, {"+", 2, 3}}}}}] should be scmfun["+"][3, scmfun["-"][2, {1, {"+", 2, 3}}]], instead of scmfun["+"][3, scmfun["-"][2, {1, scmfun["+"][2, 3]}]] $\endgroup$ – vapor Apr 3 '16 at 9:51
9
$\begingroup$

This is IMO one of the cases where local rules are not a good match for the problem, and one is better off using custom expression parsers. The problem with rules is that the whole expression is transparent to them, and it is hard to make certain parts of it immune to their application. Nevertheless, I will show both approaches below, so that one can compare them.

An approach based on expression parsers

Assuming that your scmfun is an inert symbol that doesn't have non-trivial evaluation rules attached, we can ignore the evaluation leaks problem, and then have simply this:

ClearAll[convertlist];
convertlist[{"'", inner_List}] := inner;
convertlist[elem_?AtomQ] := elem;
convertlist[{f_, args___}] := scmfun[f] @@ Map[convertlist, {args}];

which works as you requested:

convertlist[{"+", 3, {"-", 2, {"'", {"*", 1, 3}}}}]

(* scmfun["+"][3, scmfun["-"][2, {"*", 1, 3}]] *)

A rule-based approach

For completeness, let me show a possible approach based on rules. This will do literally what you requested. Since there isn't a built-in function that would shield expression's parts from rules application, we will have to develop it. It may be useful in its own right also more generally.

Shielding parts of expression from rule application

We will need a helper function, shieldExpression. It will shield specific parts of an expression, matching a given pattern, from rule application, by temporarily replacing them with a certain inert dummy expression (I will use the form symbol[i], for i-th shielded part). It will return the transformed expression wrapped in Hold, together with the rules to perform back-substitutions, in an association. Here is a possible implementation:

ClearAll[shieldExpression];
SetAttributes[shieldExpression, HoldAll];
shieldExpression[expr_, shieldPattern_, shieldSymbol_] := 
  Module[{result, rules, i = 0},
    {result, rules} = 
      Reap[Hold[ expr] /. (p : shieldPattern) :> 
        RuleCondition[
          With[{ind = ++i},
            Sow[shieldSymbol[ind] :> p]; shieldSymbol[ind]
          ]]];
    If[rules =!= {}, rules = Dispatch @ First @ rules];
    <|"HeldExpression" -> result, "ShieldingRules" -> rules|>
  ]

Here is an example:

shieldExpression[{"+",3,{"-",2,{"'",{"*",1,3}}}},{"'",___}, dummy]

(* 
   <|
     HeldExpression->Hold[{+,3,{-,2,dummy[1]}}],
     ShieldingRules->Dispatch[Length: 1]
   |>
*)

Based on this function, we can now write a version of ReplaceRepeated, that would shield certain parts of an expression from the "main rule" application, and apply some different transformation rule to those parts after the main rule has been applied:

ClearAll[replaceRepeatedShielded];
replaceRepeatedShielded[
  expr_, sr : (Rule | RuleDelayed)[shieldPattern_, _], mainRule_
] :=
  Module[{shielded, dummy},
    shielded = shieldExpression[expr, shieldPattern, dummy];
    Fold[
      ReplaceRepeated,
      ReleaseHold @ shielded["HeldExpression"],
      { mainRule, shielded["ShieldingRules"], sr}
    ]
  ]

As is clear from the code, it first shields the parts of the original expression that match the pattern shieldPattern from the application of the mainRule, then performs main rule substitution, then reconstructs the shielded pieces in the transformed expression, and finally applies a special transformation rule to them.

Here is an example:

replaceRepeatedShielded[
  f[a, b, {c, d}, g[{i, j}], h[{k, l}]], 
  p_g :> newHead @@ p, 
  l_List :> Total[l]
]

(* f[a, b, c + d, newHead[{i, j}], h[k + l]] *)

where expressions with the head g are shielded from the main rule application, and treated specially.

The case at hand

Here is the main function then:

ClearAll[convertlistRB];
convertlistRB[expr_] :=
  replaceRepeatedShielded[
    expr, {"'", inner_List} :> inner, {a_, b___} :> scmfun[a][b]
  ]

Of course, it returns the same result, as in the first method:

convertlistRB[{"+", 3, {"-", 2, {"'", {"*", 1, 3}}}}]

(* scmfun["+"][3, scmfun["-"][2, {"*", 1, 3}]] *)

Summary

I presented two different ways to solve this problem. The way I personally prefer is based on the construction of a custom expression parser, that performs a specific traversal through the expression. I prefer it because, in my view, it is easier to write, control, understand and extend. The method based on rule application required additional rather complicated machinery to shield parts of expression from rule substitution. While here it is probably an overkill, I can imagine cases where such approach would be beneficial, which is the main reason why I included this method in my answer.

| improve this answer | |
$\endgroup$
  • $\begingroup$ This is really awesome! $\endgroup$ – vapor Apr 3 '16 at 16:42
  • $\begingroup$ @Felix Was glad to help. Thanks for the accept. $\endgroup$ – Leonid Shifrin Apr 3 '16 at 17:36
4
$\begingroup$

A slight modification in @kglr proposition in the comments:

expr = {"+", 3, {"-", 2, {"'", {1, {"+", 2, 3}}}}}

expr /. {"'", x__} :> (x /. List -> f) //. {a_, b__} -> scmfun[a][b] /. f -> List

scmfun["+"][3, scmfun["-"][2, {1, {"+", 2, 3}}]]

| improve this answer | |
$\endgroup$
4
$\begingroup$

When I want to shield expression parts during a ReplaceAll, I just include a null rule for the pattern I want to shield. For instance:

convertList[expr_] := ReplaceRepeated[
    Hold[expr],
    {{"'", b_} :> {"'", b}, {a_, b___} :> scmfun[a][b]}
] /. {"'", b_} :> b //ReleaseHold

For your example:

convertList[{"+", 3, {"-", 2, {"'", {"*", 1, 3}}}}]

scmfun["+"][3, scmfun["-"][2, {"*", 1, 3}]]

| improve this answer | |
$\endgroup$
  • $\begingroup$ Can't remember now why I didn't suggest this method (which I have also been using for a long time), and instead went with the more complex suggestion. But it is clearly very relevant here, big +1. $\endgroup$ – Leonid Shifrin Nov 15 '17 at 10:34
3
$\begingroup$

(* For fun *) you can undo the action of ReplaceRepeated selectively:

convertlistF[expr_] := Hold[expr] //. {a_, b___} :> scmfun[a][b] //. 
   scmfun["'"][b__] :> (b //. scmfun[a_][c__] :> {a, c}) // ReleaseHold

Examples:

convertlistF[{"+", 3, {"-", 2, {"'", {"*", 1, 3}}}}]

scmfun["+"][3, scmfun["-"][2, {"*", 1, 3}]]

convertlistF[{"+", 3, {"-", 2, {"'", {1, {"+", 2, 3}}}}}] 

scmfun["+"][3, scmfun["-"][2, {1, {"+", 2, 3}}]]

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.