kNobel Tutorial this Wednesday

Hello everyone,

We, the tutors, have decided that we are going to offer kNobel tutorials, if wanted. A kNobel tutorial is a tutorial you can visit if you feel like you have reasonably understood the material to be presented next tutorial.

In the kNobel tutorial, we discuss the material a bit deeper than we ususally would in a normal tutorial, and also look at some material beyond what is usually covered in Programming 2.

This Wednesday, the topic in the tutorial will be on Testing. In the kNobel tutorial, we will also talk about the kinds of tests and specification, but we might focus on more advanced kinds of tests like fuzzing.

We currently plan to have this tutorial at 14:30 on Wednesdays, so that you write your Minitest in the normal tutorial and then come over.

Because we are not sure whether you would enjoy this, here is a quick poll:

I want to attend this Wednesday
  • Yes, in English
  • Yes, in German

0 voters

Please choose all options that apply.

Edit: The voting period was too early. Therefore, we have reopened the poll. If you have already voted, please do not vote again. Your vote has already been taken into account.

1 Like

The Tutorial will be today at 14:30, in E1.3 - SR 016 . It will be in English. Please write the Minitest in your regular tutorial.

We will talk about testing and specifications and how you could automate this.

For those interested, here’s what we did last kNobel tutorial:

First, we did some of the exercises that were also done in the regular tutorial.

In general, we do not assume that you have visited the regular tutorial when you attend the kNobel tutorial. We thus spend some time doing a subset of the regular exercises from the regular sheet, so that you do not miss the material you are required to learn for the next test. If you visited the kNobel tutorial before/after your regular tutorial, that’s fine, too, you can just spend the time doing any other exercise.

Afterwards, we talked about fuzzing and automated tests. We had a look at how you might write a test case generator for a program that takes inputs generated by a formal grammar, like \varphi, \psi ::= n \ |\ \varphi + \psi \ |\ \varphi * \psi, the challenges you encounter when doing this in C, and possible solutions.

Afterwards, we had a short look at a fuzzer for the current wordle project. Unlike the first fuzzer, this one used differential testing, which means that we generate random inputs and compare the behavior of two programs. The particular programs were the wordle getFeedback C implementation, and a version of wordle formalized in Z3 (GitHub - NeuralCoder3/wordle_formally: A formalization of wordle in first-order logic), which we know is correct.

If you have time, you might want to write a program that uses your implementation of getFeedback, and then invokes the formalized solution validator to check whether your implementation was correct.


Also, there were several people who voted in the original poll, but did not show up to the tutorial. Please only participate in polls if you actually plan on showing up :slightly_smiling_face:

Since enough people were interested anyway, we will likely continue the kNobel tutorial in its current format, at 14:15/14:30, in the same place – E1.3 SR 016 – except that the next ones will hopefully be a bit more interactive than this particular one. If you have wishes, feedback, or any additional commentary, please tell me (or use the anonymous feedback form, this will reach me, too).

Until next time,
Johannes

4 Likes

Hey all, this Wednesday we will again have the kNobel tutorial. In general, you can assume that this kNobel tutorial takes place, unless we explicitly tell you that it does not.

For next Wednesday, we will again do some of the exercises that get you started with Java. I’m aware many of you may already know Java, but the tutorial is designed such that you can also attend if you do not already know Java (although we expect you to have watched and understood yesterday’s lecture).

Please bring a laptop, if you can, since we will spend a lot of time writing actual programs.

Note that today’s kNobel Tutorial is at 14:15, because you’re not going to write a minitest.

The topic will be regular expressions and (maybe) parsing, depending on what you want

Attention :warning: : Due to illness, the kNobel tutorial might be at 16:15 instead. Please check back here tomorrow for further information. 14:15 it is

Hey all,

tomorrow, the kNobel tutorial will be at 14:35(ish).

We will first look at the overloading-overwriting exercises that are most relevant for the exam.

Afterwards, we’ll have a deeper look at the expression problem, the maths behind it, and how one might use modern Java to solve it (because Visitors are interesting but cumbersome).

If there’s still time, we will look at (the concepts surrounding) Streams, the maths behind them (:wink:), and how to use them to solve practical problems. Since this heavily touches upon collections, which will only be covered next time, the major part of this rather large topic will be discussed in the kNobel tutorial the week afterwards.

Be reminded that the minitest must be written in your regular tutorial.

Until then,
Johannes

Hey all,

today we talked about records, sealed interfaces, and pattern-matching in switches. I prepared slides, find them here.

We also discussed overloading and overwriting.

Afterwards, we started talking about streams, starting at FlatMap. We will continue this next tutorial. If you could not attend this tutorial, but want to show up next time, that will not be an issue – we will start with a refresher.

1 Like

Today’s plan is to solve the TODOs in this repo: Johannes Matthias Hostert / kNobel Java Streams · GitLab

Today, we talked about Streams and Collectors and related topics. For further reading, I recommend the java.util.stream JavaDoc – it is really great.

In the end, I struggled a bit with the type checker. I was trying to demonstrate how a Collector, which is defined by

  • a state creator () -> A
  • a (side-effectful) accumulator (A, B) -> ()
  • a combiner (A, A) -> A

and which can fold a Stream<B> differs from the fold for a normal List<B> known from functional programming, which has:

  • a state creator () -> A – the starting element, corresponding to the empty list. Usually, it is just given as an A, not as a function computing A, since in a functional language, this makes no difference.
  • an accumulator (A,B) -> A – since a fold is purely functional, this returns the new state, whereas a Collector mutates state (specifically, the input state of type A).

The difference is because a stream might be parallelized, and thus consists of several different “strands” that might not get folded in a strictly linear order. For example, when folding a stream into a list (i.e. if we write Collectors.toList() ourselves), we would have

  • a state creator (green) () -> new ArrayList<>()
  • an accumulator (blue) (list,elem) -> list.add(elem) – note that this mutates list.
  • a combiner (yellow) (list1, list2) -> {list1.addAll(list2); return list1;} which combines two states. We could also create a new list here, and add both lists to it, that does not really matter.

For example, if we collect a stream of numbers 1…8 (which are in three “strands”) using this collector, it computes like this:
image

1 Like

There are now three more tutorials remaining. The topics for these are:

  • How compilers optimize programs – an intro to SSA and abstract interpretation
  • Program logics for programs manipulating the heap – an intro to Separation Logic

You notice that these are only two topics. This is because I’m kind of at loss regarding what to talk about during next week’s tutorial. If anyone has suggestions, please come forward. Otherwise, we might talk about “advanced” git (i.e. what is a rebase, and why is it not that evil?), and maybe other uses of hashing. Alternatively, we might split one or both of these topics up so that we can cover it more in-depth.

1 Like

Alright, we might talk about git internals, or about Hindley-Milner type inference. The latter is not really related to programming 2, except that we currently are talking about typing systems.

Today we talked about other uses of hashing, and in particular focused on some more advanced workflows in git. Here are some of my sources and further reading:

Next week, as mentioned, we will talk about SSA, compiler middle-ends and the kinds of optimizations that happen there. Note that this is only tangentially related to the compiler project – in particular, we do not expect you to implement the kinds of optimizations presented here.

2 Likes

:warning: Today’s kNobel Tutorial :warning:

Dear all,

unfortunately, we cannot offer a kNobel tutorial today due to illness. We are sorry for this. Please, go to your usual tutorial room instead.

all the best
Lisa :smiley:

1 Like

As you could infer from Lisa’s notice, I wasn’t able to hold a tutorial today. I woke up without my voice :speak_no_evil:

This means that unfortunately, you will miss out on either the seperation logic tutorial (i.e. the Semantics lecture speedrun) or the compiler optimization tutorial (i.e. the Compiler Construction speedrun). I will prepare both for next week and we’ll figure out together which one you might enjoy more. Neither is particularly relevant for the lecture/project (the compiler tutorial will not help you in the project), but both fit really well into the material covered in the last two weeks, and I find both very interesting. I’m really sorry we’re not covering both :cry:

Today we’ll again have a kNobel tutorial. You decide the topic, out of those offered above

1 Like

So, today we had the last kNobel tutorial. We talked about control flow graphs, dominance, SSA, SSA construction, and analysis using abstract domains (mainly constant propagation). The sources for this are mainly my remaining knowledge from attending the Compiler Construction course ~2 years ago.

3 Likes