I woke up late today and was not as productive as I hoped but by following my time blocks system (which I will describe in another post) I managed to get some work done.

I continued to work on HW 1 for Stanford’s CS242: Programming Languages. This is a new topic for me but since I have been programming for several years now, the ideas make more sense than they might have done if I had studied the course earlier.

The first unit of the course covers Syntax and Semantics. HW1 has 2 parts each of which have 2 questions. I have been working on the first 3 questions, which are as follows:

Part 1

  1. Write a grammar for a JSON schema
    • You need to define what a property $p$ can be. Only strings or numbers have propertiesFor example a property is that a number is (<3 v >9) ^ =6 or that a string = ‘z’.
    • Then you need to define a schema $\tau$ which specifies what the JSON string should match, in terms of the properties.
    • This was not too difficult once I understood what the question was asking. However it is possible that I am missing something given my doubts about the solution to the next question which follows on from this one.

  2. Define inference rules to determine if a given JSON string is valid according to the schema
    • There is a tilde $\sim$ they use. For example a valid schema could include a boolean defined as bool which leads to the unconditional rules true $\sim$ bool and false $\sim$ bool. I thought it meant “equivalent” but from the text I think it means “matches”. I learned from Wikipedia that $\sim$ (preceded by “=”) is used for regex matching so that makes some sense.
    • From the notes I knew that some rules would have to terminate and others would be recursive but I needed to figure out that the rules needed to be written in terms of whether the properties $p$ were satisified. Everything in the string terminates at a string, number or boolean. A boolean is always valid if bool is allowed in the schema but strings and numbers are only valid if they satisfied the properties required of them in the schema.
    • They tell you that the reference solution has 13 rules. I am able to get different numbers depending on whether or not I introduced intermediate definitions grouping together different unary and logical operators. I have managed to get fewer than 13 with some of the groupings but never 13 so I wonder what I can be missing.

Part 2

  1. Write operational semantics for JSON accessors
    • Accessors are indices in an array or keys in a dict. They had another kind of accessor $|a$ which I have not encountered before but means apply this accessor to every element in a list.
    • You have to write rules about what happens when you apply an accessor to a JSON object. The accessor can be something like $[1]’x’[2]|[9]’y’$ which I think means
      [i[9]['y'] for i in j[1]['x'][2]].
    • The important thing is that each rule must only involve one step e.g. going from $j$ to $j[1]$.
    • They give you some examples which helps. This time I managed to end up with 4 rules. I will have a better sense of whether I am on the track when I do the final question which follows on from this.

  2. TODO: (I will add some notes here when I’m done with this)

Next steps

The HW1 doesn’t have solutions so I can’t be sure that what I have done is right but my feeling is that after progressing further through the course I will have a better sense of whether or not I was on the right track.

I am going to have a go at writing solutions for all the 4 problems. Then I will move on to the next section. The bits I don’t understand will probably make sense afterwards. I will try to keep to the weekly rhythm. I am not taking this a university course so I don’t have any barriers to cross other than to feel satisfied that I understand enough to move ahead.

At some point in the course I would like to work on a project probably something involving AI and I will have “passed” the course if I manage to acquire knowledge and skills enough to achieve that.