Talk:Mascarpone

(For history of this page before this edit, see Talk:Emmental.)

• The [ ] and ' operations are able to return to the previous interpreter after they've done their job. Does that mean there's actually "current interpreters" are stacked, like function calls? Or does that mean the interpreter created by ' is never the same, and include information about the context in which it was created? It's even worse for [ and ], since apparently their meaning seems to be changing when going more deeply into nested levels. Does that mean that a new interpreter is created at every nested [ and ] encountered? Or are interpreters allowed to "create their own environment", for instance creating a variable to store the nesting depth?
• The @ operation looks overly unspecified to me. If I were to write an interpreter for Mascarpone, and I simply made @ equivalent to 1 except that it pushes any symbol (enclosed in a string, whatever) before pushing the interpreter, I think I'd still be consistent with the specifications.

Anyway, I'm a little confused right now because it's much more abstract than Emmental was, so I need to play with it a little before I can really understand how it works! But it looks very exciting already. --Koen (talk) 13:05, 18 October 2012 (UTC)

Is there a stack of interpreters? IIRC, yes, in the sense that each interpreter contains (a link to?) the previous interpreter (as well as a link to the interpreter it was derived from? I think. It's been a while.) And yes, again IIRC, [ actually brings into play a new interpreter (one that does quoting) and ] reverts to the previous. Not sure about interpreters "creating their own environments". @ was intentionally left very loose, and yes, it could push any symbol and then an interpreter which interprets that symbol to do what the original operation did -- I gave reasons in the doc (not necessarily good reasons, but I remember reading them earlier today.) Chris Pressey (talk) 13:24, 18 October 2012 (UTC)

So I've written an interpreter. It still has bugs but I have a few questions:

• After writing it I looked at the example programs from your implementation (I have not looked at the implementation itself) and tried to execute them. As expected my interpreter apparently does not do what it's supposed to yet; do you guarantee they are all supposed to work fine?
• I used the specifications from readme.markdown to make my interpreter. It doesn't specify what is the parent of the initial interpreter (I assumed it should be null), nor what is the parent of an interpreter created with the "uniform" operation (once again I assumed it should be null, but maybe it should be the current interpreter, or something). Neither does it explicitly specify what should the parent of all "quotemode" interpreters be, so I used that to implement nesting levels:

  | Deepquote ->
    let f s = match s with
      | '[' -> [Push '['; Reify; Reify; Set_parent; Deify]
      | ']' -> [Push ']'; Reify; Get_parent; Deify]
      | _ -> [Push s]
    in push (Symbol '['); current := { mci = f; parent = !current }
  | Quotesym ->
    let f x = [Push x; Reify; Get_parent; Deify] in
    current := { mci = f; parent = !current }

In fact, I'm not sure I understand what you meant with "There is, at any given time in a Mascarpone, a current interpreter: this is the interpreter that is in force, that is being used to interpret symbols. The parent interpreter of the current interpreter is generally the interpreter that was used to execute the current operation (that is, the operation currently being interpreted; it consists of a string of symbols is interpreted by the current interpreter.)". When implementing Emmental I was able to use a single list (LIFO) that mapped symbols to strings of symbols, so that interpreting a symbol meant "look for that symbol in the list, then interpret every symbol in the string, using the remainder of the list as the mci" (with the empty list representing the initial mci). But for Mascarpone things are slightly more complicated since you can manipulate Symbols, Operations and MCIs; in my implementation, operations are no longer dependent on symbols, they are just lists of "atom operations" (in the above example, you can see that MCIs are functions that map symbols to lists of atom operations). Therefore no interpreter is needed to execute an operation. Really I don't see what the hierarchy between interpreters is supposed to be - with Emmental that was pretty clear, since the only way to create a "new" interpreter was to add a (symbol -> symbol string) thing on top on the previous interpreter; but with Mascarpone I don't see that.

• Why doesn't the null interpreter have a parent? Is trying to get its parent an error? I don't like that idea. I made the null interpreter an interpreter similar to every other, except that it mapped all symbols to the "error" operation. I also made it its own parent: let rec null_mci = { mci = (function x -> [Error]); parent = null_mci }
• Would having an infinite number of symbols be such a problem? Well, granted, it would not really be useful. But I mean, I'm okay with there being an infinite number of atom operations - after all, I was not gonna bother with writing the quote interpreters manually for every ASCII char, so the set of atom operations I chose is Error | Push of symbol | Reify | Deify | Extract | Install | Get_parent | Set_parent | Create | Expand | Perform | Null | Uniform | Deepquote | Quotesym | Output | Input | Dup | Pop | Swap. As you can see "Push x" already represent 256 different operations. In fact that's why I made interpreters be functions rather than association lists: I started with associations lists (like for Emmental) but then I had to make distinctions for "what the empty list means" - for the initial interpreter that would be "all symbols are nops", for the null interpreter "all symbols are errors". So I added a field "remainder" which was an operation to which map all symbols that are not mapped by the association list. But then it didn't work for quotes: because every different symbol maps to a different operation. So I made "remainder" a function, and eventually discarded the list completely.
• Is it OK if I write a wiki page for Mascarpone someday?

Thank you for your answers! --Koen (talk) 23:36, 30 November 2012 (UTC)

BTW, there's no way to access non-printable characters, is there? I thought not having arithmetics over symbols would be a cool thing, but that also means that you're restricted to the symbols in the string representation of the program. I guess escape sequences should be acceptable in that case - I'd consider them not part of the language itself, but transcriptions from a reduced set of printable characters to an abstract set of symbols. --Koen (talk) 02:19, 1 December 2012 (UTC)

Woo, ok, I'll try to answer these from easiest to hardest...

By all means, start a wiki article for Mascarpone (and move this section to its talk page). I think I consider it "esoteric enough" at this point.

The example programs should do what the descriptions say they do. Last time I checked (which I think was not too long ago, like, after your first set of questions), they did.

You are restricted to the symbols in the program, but on the other hand, you're not restricted to any particular superset of the symbols listed in the spec. So non-printables should be fine, unfortunately you'd have to include them literally in the program somewhere.

(Ye cats, looking at this language again is giving me a headache)

From the reference implementation: Yes, the parent of the initial interpreter is the "null interpreter", i.e. what you get when you execute 0 in the initial interpreter. Yes, this also the parent of a uniform interpreter. The parent of a quoting interpreter that you get when you say [ looks like it's the current interpreter... so using it to do nesting levels like you say is probably the right thing.

My confusing statement is trying to explain the hierarchy of interpreters. Here's my attempt to make it clearer which might just make it worse: The parent interpreter is the interpreter that interpreted the instruction that you're currently interpreting the contents of with the current interpreter. It is, admitted, not as straightforward as a simple linked list. There is a comment in the reference interpreter which may or may not shed more light on it:

Note that when we call an operation that was defined using a "captured"
interpreter, we do the following:

1. We attach the current interpreter as the parent interpreter of the
captured interpreter
2. We interpret the symbols in the operation definition using the captured
interpreter
3. When we have reached the end, we extract the parent interpreter of the
captured interpreter and use it as the new current interpreter

Note that this means two things:

1. The operation definition may modify its current interpreter (the
captured interpreter) to its heart's content; this will not modify
our current interpreter (the parent interpreter)
2. The operation definition may modify our current interpreter by
modifying the parent interpreter of its current interpreter.

I'm no longer clear on what "captured interpreter" means, so this might, again, just be making things worse, but it's definitely about the relationship between interpreters...

The null interpreter probably doesn't have a parent because I wanted the set of interpreters to be well-founded or something (silly me) and I probably couldn't imagine how you'd access the parent of the null interpreter anyway (can you? probably somehow.)

My head's spinning so I'll give this a break and come back to it later, in the hopes that you might be able to do something with the partial information I've given so far... Chris Pressey (talk) 11:42, 1 December 2012 (UTC)

Accessing the null interpreter's parent: 0{. It's pretty straightforward: push the null interpreter on the stack, then "pop an interpreter from the stack and push its parent". I'm actually less happy about quote interpreters, since the only way to access them is by actually setting them as the current interpreter - at which point you lose all access to other operations, so you can't actually build anything with those interpreters.

With your explanations I understand why I didn't understand the hierarchy between interpreters. That hierarchy was pretty clear in Emmental: the current interpreter I maps a symbol X to a string of symbols ABC plus the interpreter J that was used when X was defined (you called that "early binding"); that "captured" interpreter J will then map A, B and C in a similar way. In that case I can be said to be the parent of J, because after having interpreted symbols A, B and C you need a way back to I to interpret the next symbol after X. That child->parent link was not explicit in the implementation because that's what functional programming does, implicitly returning to its caller after having been executed. My point is that my Mascarpone implementation doesn't have this "symbol -> more symbols -> even more symbols -> ... -> initial meaning of symbols" thingy (where '->' means 'interpreted as'). Instead it has only one level of "symbols -> operation"; you say "In Mascarpone, an interpreter is a map that takes symbols to operations, and an operation is a sequence of symbols that is given meaning by some interpreter.", which would be very similar to Emmental, but precisely my implementation defines operations independently from symbols and interpreters. With that in mind there is no longer this relation between interpreters, because there are no captured interpreters at all. Now I realize that this may not exactly be the semantics you had in mind for Mascarpone - specifically, an operation expected to modify "its current interpreter" will modify the current interpreter, because this interpreter has never been replaced by a "captured interpreter" since there is no captured interpreted. --Koen (talk) 13:11, 1 December 2012 (UTC)

I'm not entirely sure I've digested what you say, and of course I've forgotten about a lot of the details, but let's assume I understand it. Emmental and Mascarpone do differ in the respect I think you are talking about; in Emmental, each new interpreter "inherits" from the previously-used interpreter, but in Mascarpone, this is not necessarily the case. While you still can make a new interpreter based on some previously-used interpreter, you can also make a brand new interpreter "from scratch", and use that instead. This is possible because interpreters are first-class in Mascarpone, whereas they aren't in Emmental so you don't really have this choice. Chris Pressey (talk) 13:29, 1 December 2012 (UTC)

Apparently I wasn't clear enough. I was not talking about inheritance, but about parents and children. Imagine an implementation of Emmental in which interpreters were defined as:

type mci = ((symbol * symbol list) * mci) list

where the element ((a, str), i) in an mci j would mean "the symbol a is mapped to the sequence of symbols str, and when interpreting a, every symbol in str should be interpreted using the mci i. Now that would not be a very clever way of implementing Emmental, precisely because it doesn't exploit the fact that in Emmental interpreters don't need to be "first-class objects", and that each new interpreter "inherits" from the previously-used interpreter, so storing a lot of interpreters is a useless loss of memory, but that's not my point. Point is: yes, when interpreting a, one must interpret every symbol in str, which means switching to the mci i; in that case, I would say that the mci i is "captured" in the operation described by ((a, str), i), and the mci j is the parent interpreter of i. SO now we kinda have a definition for "captured" and the parent-child hierarchy is clear. Now back to Mascarpone: in Mascarpone we have a new object, the "operation" (in Emmental there really was only "symbol" and "mci"). So interpreters can be defined as:

type mci = (symbol * operation) list

...and as you can see, with that definition, there is no captured interpreter, because interpreting a symbol isn't "make it a sequence of symbols and switch to a captured interpreter to interpret those new symbols", but rather "immediately perform the operation assigned to that symbol". And since there is no captured interpreter to switch to, there is no captured interpreter's parent interpreter to switch back to afterwards. Which means, the "parent" of an interpreter is something completely artificial whose only purpose is to be manipulated with operations like "set parent" and "get parent".

But with all you've said, I believe that is not how you intended interpreters to be implemented - and judging by the comment from your implementation, it is not how you did implement it, and the difference is substantial because "no switching to a captured interpreter" means that operations that "affect their current interpreter" actually affect the current interpreter. Hope I've expressed myself in a more understandable fashion this time!

For the anecdote: my first plan did involve captured interpreters, because of the "In Mascarpone, an interpreter is a map that takes symbols to operations, and an operation is a sequence of symbols that is given meaning by some interpreter." comment in README.markdown, and when Ocaml's first reaction was to childishly complain about operations and interpreters being mutually recursive types, Oerjan popped in and suggested I make operations be straightforward functions. --Koen (talk) 02:44, 2 December 2012 (UTC)

You were probably plenty clear, it's just that a lot of my reasoning is still based largely on (dim) recollections...

I can't think of why I would or wouldn't have intended it to be implemented one way or another, but I do remember trying to implement it and coming to an "oh damn" point where I realized I'd need to establish more relationships internally that I thought I would have to. (That's why that comment was written, I'm pretty sure.) Given your type

type mci = (symbol * operation) list

what immediately springs to my mind (esp. based on the sentence you quote just above) is that the type of operations is then

type operation = (symbol list) * mci

which immediately suggests that's where the "captured interpreter" lives; an operation is a kind of closure. (Unless I'm way off base.) Possibly I unwound this, in my implementation, to avoid a recursive type, too (Haskell doesn't like them either. And, actually, this wouldn't have been the first or last time I've shaken my fist at this restriction. I mean, OK, I get why it doesn't let you, but at the same time, it would be really nice to have some sort of compromise. Maybe one could write a more natural implementation in a dynamic language like Python or Ruby. Heck, even C would let you write these types, I think.) But also: making an operation a function should let it close over the mci just as well. (But then, the Mascarpone-language-level "get parent" operation is a bit awkward to implement, I imagine.) I'm no expert functional programmer, so I won't exclude the possibility that there is some other way to juggle the types so that everything is tidy.

Of course, it may turn out that the parent interpreter is a totally artificial concept; but I believe I used it to argue that Mascarpone could be Turing-complete (using two stacks: the data stack, and a stack of interpreters related by parentage.) So that might have been the reason for keeping it around despite it not being crucial to how first-class mci's work. Chris Pressey (talk) 10:45, 2 December 2012 (UTC)

Fwiw, apparently the reference OCaml implementation lets you have recursive types if you pass the -rectypes option to the compiler. Now I'm looking for something equivalent for Haskell, because it would be really useful everytime I come up with one of these horrible languages where everything is defined in terms of everything else :) Chris Pressey (talk) 17:15, 2 December 2012 (UTC) (Meh, looks like newtype is as close as it gets. Chris Pressey (talk) 17:45, 2 December 2012 (UTC))

I cannot give you something more convenient than newtype for getting around recursive types, but from my brief look at your Mascarpone interpreter I think you might benefit from using record field names and record update. (Or lenses, although that's an extra library. I should learn them some day.) --Ørjan (talk) 22:43, 2 December 2012 (UTC)

BTW I mean this both in general (it was my first impression on seeing the code) and as something that slightly diminishes the noise of using newtypes. --Ørjan (talk) 23:44, 2 December 2012 (UTC)

Yeah, it's an extremely bad habit of mine. I don't really program in Haskell when I program in Haskell. Meaning, there is this large set of things that Haskell lets you do that I never do. Records are the element of that set that I have the least excuse for adopting in my programming... I should make a conscious effort. Chris Pressey (talk) 11:35, 5 December 2012 (UTC)

Answering (to Chris Pressey, and this is Koen) with examples. As far as I know, -rectypes is about disabling restrictions over recursive types, which was not exactly my issue here.

type 'a list1 = Empty | Cons of 'a * 'a list
(* is always correct in Ocaml *)

type 'a option = None | Some of 'a
type 'a list2 = ('a * 'a list) option
(* needs -rectypes, otherwise Ocaml complains it's cyclic or something because *)
(* there is no obvious 'halt condition' for the recursion *)
(* since the halt condition is only a consequence of 'a option *)

(* But my issue was with "mutually recursive" types, not so much about recursivity itself but with scopes: *)
type mci = (symbol * operation) list
(* Ocaml stops here and display an error because it has never heard of the word 'operation' before *)
(* and of course if you swap the two lines it will tell you it's never heard of 'mci' *)
type operation = (symbol list) * mci

(* you certainly don't have this problem in C because you can use *)
(* "prototypes" or something (typedef?) to teach it new words before teaching it their meaning. *)
(* I don't know whether something similar to prototypes can be *)
(* used in Ocaml to solve the problem. It's not a very serious problem though, I'm sure there's a solution. *)

(* For instance rather than using a named type in your definition you can use its constituants: *)
type mci = (symbol * ((symbol list) * mci)) list
type operation = (symbol list) * mci
(* though technically here you'd need -rectypes to avoid "Error: The type abbreviation mci is cyclic" *)

Anyway, back on topic: my point is precisely that eventually I did not make it type operation = (symbol list) * mci (which was indeed the first idea in my mind and which would be exactly like Emmental) but rather... Well, take a look at how my interpreter begins:

type symbol = char
type init_op =
  | Error | Push of symbol | Reify | Deify | Extract | Install | Get_parent | Set_parent | Create | Expand
  | Perform | Null | Uniform | Deepquote | Quotesym | Output | Input | Dup | Pop | Swap
type op = init_op list
type mci = { mci: symbol -> op; parent: mci }

type element = Symbol of symbol | Op of op | MCI of mci

let stack = (Stack.create () : element Stack.t)

let rec null_mci =
  { mci = (function x -> [Error]); parent = null_mci }
let init_mci =
  { mci = (function
      | 'v' -> [Reify]
      | '^' -> [Deify]
      | '>' -> [Extract]

[...]

      | '$' -> [Pop]
      | '/' -> [Swap]
      | _ -> []);
    parent = null_mci }

let current = ref init_mci

[...]

let rec execute_init s =
  match s with
  | Error -> raise (Spin_off_into_space_never_to_be_heard_again)
  | Push s -> push (Symbol s)
  | Reify -> push (MCI !current)
  | Deify -> current := pop_mci ()

[...]

(* then repeat "List.iter execute_init (!current.mci (next symbol in the program))" until end of program *)

So basically symbol is char, init_op is atom function (given meaning by execute_init), operation is sequence of atom functions (given meaning by List.iter execute_init), and there are no recursive definitions at all (well except for the 'parent' field but it's never used anywhere save for Get_parent, Set_parent, Deepquote and Quotesym). --Koen (talk) 23:17, 2 December 2012 (UTC)

I was just made aware that type x = A of y and y = B of x works fine (and doesn't even need -rectypes, for whatever reason). --Koen (talk) 00:17, 3 December 2012 (UTC)

New thought about using an unbounded set of symbols: I was wondering about how to implement "expand". This could be done very boringly as "Pop an operation from the stack, then push a single random symbol (that is, the length-1 program string that consists in that single symbol), then push an interpreter where all symbols (or at least that one random symbol) is associated with that operation. So basically that would be exactly the same thing as the "uniform" operation, except that you push an extra random symbol on the stack. Boring, and certainly not fulfilling the "explore the intrinsic meanings of stuff" expectation. So here is another idea: since in my implementation, operations are sequences of 'atom operations' (the meaning of which is described directly in the Ocaml language, rather than in a Mascarpony way), "expand" could be "Pop an operation (a sequence of atom operations) then push a program string that copy the pattern of that sequence (with a bijection between symbols and atom operations), then push an interpreter that explicits this bijection.
(For instance, if the popped operation is [Push '['; Reify; Reify; Set_parent; Deify] then the program string could be ABBCD and the interpreter function | 'A' -> [Push '['] | 'B' -> [Reify] | 'C' -> [Set_parent] | 'D' -> [Deify] | _ -> [Error])
This would be satisfying, I think. Unfortunately it's not quite always possible, because the number of symbols is strictly less than the number of atom operations... Because for every symbol X, Push X is an atom operation. So this version of expand wouldn't work if the expanded operation used more than 256 different atom operations, and I'm not satisfied. Which brings back the thought about the unbounded alphabet: in that case, we wouldn't have a problem and that implementation of expand would be very satisfying to me. For instance, imagine if the set of symbols is the set of natural numbers. That set is unbounded, so the number of different possible atom operation is also infinite (because of Push 0, Push 1, Push 2, ...), but the operation popped by 'expand' is necessarily a finite sequence of symbols; say its length is n, then the program string pushed to the stack could simply be 0 1 2 3... n-1 and the interpreter pushed to the stack would map every k < n to the kth atom operation in the sequence (and to be even better you can do the pattern thing; that is, having n be the number of different symbols in the sequence rather than the total number of symbols).
Uh, I apologize. That thought was both very clear and very brief in my head, dunno why it took so many words here... --Koen (talk) 02:02, 2 December 2012 (UTC)

I have started completely rewriting my interpreter according to what you said. Now I'm using

type op = L of (symbol list * mci) | A of atom
and mci = { mci: symbol -> op; parent: mci }

This raises a question about switching to a captured interpreter when in the process of interpreting an operation. Here is my current code:

let rec execute_op op =
  match op with
  | A a -> execute_atom a
  | L (seq, mci) -> List.iter (execute_symbol mci) seq
and execute_symbol mci s =
  current := { mci = mci.mci; parent = !current };
  execute_op (mci.mci s);
  current := !current.parent
and execute_atom a =
  match a with
  | Reify -> push (MCI !current)
  | Deify -> current := pop_mci ()
  [...]

Here execute_op iterates "interpret a symbol in the captured mci" on the sequence on symbols; and switching to the captured interpreter then back to the previous current interpreter is done by execute_symbol, which means it is repeated for every symbol in the sequence. In other words, the iterated function is "1) switch to captured interpreter. 2) execute the operation corresponding to that symbol in that interpreter. 3) switch back to previous current interpreter.". Steps 1) and 3) will cancel out in most situations, so this would be equivalent to "Do step 1). Iterate step 2) for every symbol. Do step 3)."... except that step 2) can modify the current interpreter (for instance using Reify or Quotesym). My question is : what is correct according to the specifications, "iterate 1)2)3) for every symbol", or "1). iterate 2) for every symbol. 3)"? The difference being that repeating steps 3) and 1) would somewhat "protect" the captured interpreter by restoring it for every symbol rather than allowing some symbols to change it. --Koen (talk) 14:33, 4 December 2012 (UTC)

Based on the comment from the reference implementation that I posted, it appears that the "captured" interpreter is free to be modified by the operation-description it is interpreting, and these modifications are in effect until the operation-description ends. So there is no need (in fact, it would be wrong) to try to protect the captured interpreter from being modified in the process of interpreting the operation-description. When the end of the operation-description is reached, the captured interpreter is thrown away. (Of course, the operation-description may have modified the parent of the captured interpreter also, and those modification need to be retained, in (what is now) the current interpreter (after the operation-description interpreting is finished.) Chris Pressey (talk) 11:32, 5 December 2012 (UTC)

Truth-machine

Untested.

        v
          [
                v
                '1:.
              >
            !
          ]
          v
        *
        '1
      <
      ['0.]v*
      '0
    <
    ,
  >
!

Indentation shows what's the argument of what. The outter function, ! ("perform") takes one argument, an operation, and that operation is given by > ("extract"). "Extract" takes two arguments: , (the symbol taken from input, either 0 or 1 since this is a truth-machine), and an interpreter, and that interpreter is given by < ("install"). "Install" install a copy of the current interpreter (the initial Mascarpone interpreter) with two extra (symbol -> operation): the symbol 0 maps to output 0 and the symbol 1 maps to output 1, then execute the operation associated with 1 under the current interpreter.--Koen (talk) 01:47, 25 September 2013 (UTC)

Mascarpone is Turing-Complete

Just thought I'd let you know, Mascarpone is Turing Complete by translation of the TC subset of Underload ():^:

(  ->  [
)  ->  ]v*
:  ->  :
^  ->  !

Challenger5 (talk) 16:25, 21 May 2017 (UTC)

Also, it doesn't fulfill the "input-universality" criterion that you mention on Paneer. Consider the language "output the last symbol in the program." This language is impossible to convert into Mascarpone. You can't output after every command since there's no way to "undo" the output of previous commands, but you can't output at the end either, since there's no way to distinguish between the last symbol and any other symbol. In any case, I believe Takeover fulfills this (assuming it is Turing-complete), as might ///.

Challenger5 (talk) 05:45, 4 April 2018 (UTC)