CMSI 3802: Languages and Automata II: Homework #3 Answers

In Java
1. x+++-y is not a compile-time error (it parses as (x++)+(-y))
2. x---+y is not a compile-time error (it parses as (x--)-(+y))
3. Incrementing a read-only variable is a static semantic error, as there is no way in Java to tell whether a variable is read-only from the grammar alone.
4. Code in class C accessing a private field from class D is a static semantic error since access attributes are not attached to identifiers in the grammar.
5. Using an uninitialized variable is a static semantic error since not being initialized cannot be known from the grammar alone, and Java, unlike C, does not allow this.
6. Dereferencing a null reference is not a compile-time error. There is a chance a warning can occur if the compiler can prove the reference is always null. It’s not even a dynamic semantic error, since a deference just throws an exception that can be caught.
7. null instanceof C is not a compile-time error, but it’s kind of silly to write because it always returns false.
8. !!x is not a compile-time error (since, remember, the context of this problem is to assume the types make as much sense as they can).
9. x > y > z is a static semantic error since the expression is allowed by the grammar, but the > operator is not allowed on booleans!
10. if (a instanceof Dog d) {...} is not a compile-time error. The ... was not meant to be taken literally.
11. var s = """This is weird"""; is a syntax error because an opening triple-quote must end a line.
12. switch = 200; is a syntax error because switch is a reserved word.
13. x = switch (e) {case 1->5; default->8;}; is not a compile-time error as modern Java allows switch expressions.
JavaScript disallows this (at least in strict mode) because you cannot redeclare an identifier in a scope. Rust does allow shadowing, but in this case, it technically rejects because the first x is never used. The important thing to say is that in Rust, there are two variables here, not one.
In Java, a private member of an object is visible only in fields and methods within the same class as the object. In Ruby, a private function is one that may not be called with an explicit receiver; instead, the receiver is always implicitly self.
The important difference is that if we have two objects, x and y of class C, say, then in Java, a method called on x can call a private method on y, because the two objects have the same class. However, in Ruby, this can’t happen: a method on x can only call private methods on x itself! So Ruby private access is pretty much object-based, while in Java it’s class-based.
Example in Java:
```
jshell> class C {
... private String f() {return "hi";}
... String g(C other) {return other.f();}
...}
|  created class C

jshell> var a = new C();
a ==> C@77caeb3e

jshell> var b = new C();
b ==> C@3bfdc050

jshell> b.g(a)
$4 ==> "hi"
```
Note that in Java, you can change a private field of an object through a different object. This is very permissive! Not super secure.

This cannot be written in Ruby at all because (1) there is no way to refer to fields in other objects at all, and the lack of a receiver on a private method means there is no possible way to call a private method on a different object other than the current one (self).

In case you are interested is an example of how we would use private in Ruby:
cylinder.rb
```
# Illustration of private methods in Ruby. Private methods cannot have an
# explicit receiver so they always apply to the existing receiver. In other
# words, they are private to the current object.

class Cylinder
  def initialize(r = 1, h = 1)
    @r = r
    @h = h
  end
  def volume
    capArea * @h
  end
  def surfaceArea
    2 * capArea + sideArea
  end

  private

  def capArea
    Math::PI * @r * @r
  end
  def sideArea
    Math::PI * 2.0 * @r * @h
  end
end

c = Cylinder.new(10, 50)
puts c.volume
puts c.surfaceArea
```
Now it is true that if you subclass a class in Ruby, the subclass will have those private methods, too. This is different from Java, where private methods are not inherited. However, the “inherited” private methods can only work on a single object. Ruby never allows you to change a private field in one class by calling a method on a different class.
Yes! Suppose g were a function which modified the global variable a as a side effect. Then the expression f(a,g(b)) could yield different results depending on which order the arguments were evaluated. (I am hoping your answer shows an exact case!)
Carlos used to prohibit recursive structs because structs are value types and are (at least conceptually) stored directly rather than being allocated on the heap. Therefore a “recursive” struct would have infinite size. So when analyzing a struct type T, the compiler will look for any fields that have type T, and if it finds any, will generate an error. The search itself recurses into any fields of the struct which happen themselves to be structs. The code for this, which used to be on GitHub, is:
```
function includesAsField(structType, type) {
  // Whether the struct type has a field of type type, directly or indirectly
  return structType.fields.some(
    field =>
      field.type === type ||
      (field.type?.kind === "StructType" && includesAsField(field.type, type))
  )
}

function mustNotBeSelfContaining(structType, at) {
  const containsSelf = includesAsField(structType, structType)
  must(!containsSelf, "Struct type must not be self-containing", at)
}
```
In later versions of Carlos, this restriction was relaxed, allowing recursive struct type definitions to be written, for example:
```
struct Useless {
  useless: Useless
}
```
We ended up allowing this because it turns out not to matter because you cannot create an instance of this type anyway. Try it! (If you can prove me wrong, you will get 20 points of extra credit.)
The minimum value of a (non-empty) sequence is: (1) the first element, if the sequence has length one, or (2) the minium of the first element and the minimum value of the rest of the sequence. In pseudocode you might write:

function min_element(a)
    if len(a) == 1 then
        return a[0]
    else
        return min(a[0], min_element(a[1..]))
    end
end

However, this is not tail recursive, and is not an acceptable solution. To make it tail recursive you need the trick where your recursive function accepts a list and the current minimum so far. Here are some solutions to the tail-recursive part. In most cases these would need to be wrapped in a function which did not take in the “accumulator” min-so-far variable.

def minimum(a, min_so_far = math.inf):
    if not a:
        return min_so_far
    return minimum(a[1:], min(a[0], min_so_far))

double minimum(double *array, int len, double min_so_far) {
    if (len == 0) {
        return min_so_far;
    }
    double new_min = array[0] < min_so_far ? array[0] : min_so_far;
    return minimum(array+1, len-1, new_min);
}

function minimum(array, minSoFar = Infinity) {
    if (array.length === 0) return minSoFar
    return minimum(array.slice(1), Math.min(a[0], minSoFar))
}

// Thanks to ChatGPT for this
func minimum(array []float64, minSoFar float64) float64 {
    if len(array) == 0 {
        return minSoFar
    } else {
        newMin := minSoFar
        if minSoFar < array[0] {
            newMin = array[0]
        }
        return minimum(array[1:], newMin)
    }
}

minimum([], Min) -> Min;
minimum([Head | Tail], Min) -> minimum(Tail, min(Head, Min)).

fn minimum(arr: &[f64], min_so_far: f64) -> f64 {
    match arr {
        [] => min_so_far,
        [head, tail @ ..] =>
            minimum(tail, if *head < min_so_far { *head } else { min_so_far })
    }
}

The second friend’s code is passing undefined to the callback of setTimeout. This is an example where delayed execution is called for, so to fix it, you need to replace update(i) with ()=>update(i). There’s another way, too. You can invoke setTimeout with a third argument: setTimeout(1000, update, i). That’s a bit harder to read, but it does work!
Using SonarLint and PMD I found:
- The file is not in a named package.
- Should use a utility class (private constructor) since everything is static.
- Should use interface Map for the variable declaration, not HashMap.
- Since HashMap was used, the right hand side should have used a diamond.
- Empty constructor should be documented.
- Public constructor should be hidden.
- Should use a constant instead of a method for zero.
FindBugs and FindSecBugs might find more!