lamp issueshttps://gitlab.epfl.ch/groups/lamp/-/issues2021-12-21T17:46:03Zhttps://gitlab.epfl.ch/lamp/cs210/-/issues/104Church encodings in Scala2021-12-21T17:46:03ZMatt BovelChurch encodings in Scala*Follow-up of https://discord.com/channels/885109005469511700/885109005469511704/922863225689759804.*
Representing Church encodings in Scala is not trivial, and we didn't want to show something like that because we did not want to confu...*Follow-up of https://discord.com/channels/885109005469511700/885109005469511704/922863225689759804.*
Representing Church encodings in Scala is not trivial, and we didn't want to show something like that because we did not want to confuse you.
But as some of you tried, here are some examples of how this could be done following what was posted on Discord:
```scala
type ChurchNum[T] = (T => T) => T => T // By Fran.
def zero [T]: ChurchNum[T] = f => z => z // By Fran.
def one [T]: ChurchNum[T] = f => z => f(z) // By Fran.
def two [T]: ChurchNum[T] = f => z => f(f(z)) // By Fran.
def three[T]: ChurchNum[T] = f => z => f(f(f(z))) // By Fran.
def toInt[T](i: ChurchNum[Int]): Int = i(_ + 1)(0)
assert(toInt(three) == 3)
def succ[T]: ChurchNum[T] => ChurchNum[T] = (n: ChurchNum[T]) => f => z => f(n(f)(z))
// Trick to make this version work: set type of `n` to `ChurchNum[ChurchNum[T]]`
def add[T]: ChurchNum[ChurchNum[T]] => ChurchNum[T] => ChurchNum[T] = n => m => n(succ)(m)
def add2[T]: ChurchNum[T] => ChurchNum[T] => ChurchNum[T] = a => b => f => z => a(f)(b(f)(z)) // By David Kalajdzic
assert(toInt(add(zero)(one)) == 1)
assert(toInt(add(two)(three)) == 5)
assert(toInt(add2(zero)(one)) == 1)
assert(toInt(add2(two)(three)) == 5)
```
However, the trick used for `add` is limited. With these typings we can only refer to a specific instance of the type `ChurchNum` at a time; typing `n` as `ChurchNum[ChurchNum[T]]` excludes using it as `ChurchNum[T]` for example.
To encode Church numerals more faithfully, we could use Scala 3's _polymorphic function types_: https://docs.scala-lang.org/scala3/reference/new-types/polymorphic-function-types.html. Note that this is advanced material, **outside of the scope of this course**.
Polymorphic function types allow us to encode the fact that a Church numeral is a function that can be instantiated with any type (a polymorphic function in due form):
```scala
type ChurchNum = [T] => (T => T) => T => T
val zero: ChurchNum = [T] => (f: T => T) => (z: T) => z
val one: ChurchNum = [T] => (f: T => T) => (z: T) => f(z)
val two: ChurchNum = [T] => (f: T => T) => (z: T) => f(f(z))
val three: ChurchNum = [T] => (f: T => T) => (z: T) => f(f(f(z)))
def toInt(i: ChurchNum): Int = i[Int](_ + 1)(0)
assert(toInt(three) == 3)
val succ: ChurchNum => ChurchNum = (n: ChurchNum) => [T] => (f: T => T) => (z: T) => f(n(f)(z))
val add: ChurchNum => ChurchNum => ChurchNum = n => m => n(succ)(m)
val add2: ChurchNum => ChurchNum => ChurchNum = a => b => [T] => (f: T => T) => (z: T) => a(f)(b(f)(z))
assert(toInt(add(zero)(one)) == 1)
assert(toInt(add(two)(three)) == 5)
assert(toInt(add2(zero)(one)) == 1)
assert(toInt(add2(two)(three)) == 5)
```
We could represent Church Booleans similarly:
```scala
type ChurchBool = [T] => T => T => T
val tru: ChurchBool = [T] => (x: T) => (y: T) => x
val fls: ChurchBool = [T] => (x: T) => (y: T) => y
val not2 /*: ChurchBool => ChurchBool*/ = (a: ChurchBool) => [T] => (x: T) => (y: T) => a(y)(x)
val and: ChurchBool => ChurchBool => ChurchBool = (a: ChurchBool) => (b: ChurchBool) => a(b)(fls)
val nand: ChurchBool => ChurchBool => ChurchBool = (a: ChurchBool) => (b: ChurchBool) => a(not2(b))(not2(a))
val nand2: ChurchBool => ChurchBool => ChurchBool = (a: ChurchBool) => (b: ChurchBool) => a(not2(b))(tru)
def toBool(b: ChurchBool): Boolean = b(true)(false)
assert(toBool(not2(nand2(tru)(tru))) == true)
```
This is not prefect, as inference does not always work as expected (or at least I could not make it work, see the `not2` case for example).
Also, we can not represent church lists as we'd need a recursive type definition which is not supported yet:
```scala
type ChurchList = [A, L] => (n: L) => (c: A => ChurchList => L) => L
// illegal cyclic type reference
```
Anyway, if these thoughts can help some of you to better understand Church encodings, good. Otherwise, if this yields to more confusion, just forget it :wink:https://gitlab.epfl.ch/lamp/cs210/-/issues/103ex 8 question 1 final 2019 ex3 type class2021-12-21T09:50:38ZDavid Loïck Claude Lacourex 8 question 1 final 2019 ex3 type classSorry, I don't understand why in exercise 8 we have: (using Eq[T])
given EqList[T] (using Eq[T]): Eq[List[T]] with
extension (x: List[T])
def === (y: List[T]): Boolean =
(x, y) match
case (hx :: tx, hy :: ty) => hx =...Sorry, I don't understand why in exercise 8 we have: (using Eq[T])
given EqList[T] (using Eq[T]): Eq[List[T]] with
extension (x: List[T])
def === (y: List[T]): Boolean =
(x, y) match
case (hx :: tx, hy :: ty) => hx === hy && tx === ty
case (Nil, Nil) => true
case _ => false
and in exam 2019 ex 3 we have : ( given Hash[T], Hash[U],Hash[S] )
given TripleHash[T,U,S] (given Hash[T],Hash[U],Hash[S]): Hash[(T,U)]
def hash(triple:(T,U,S): Long=
mix(mix(digest(triple._1,digest(triple._2)),digest(triple._3)))
Is it because the language changed?
thank you in advancehttps://gitlab.epfl.ch/lamp/cs210/-/issues/102Exercise Session 8, question 22021-12-21T16:07:19ZJiangfan LiExercise Session 8, question 2Using the solution codes, I got `add(S(Z), S(S(Z))) // : S[S[Nat]] = S(S(Z))`. It's not right, isn't it?
To figure out this problem, I added a new given instance `given succZ: S[Z] = S(Z)`, and the compiler told me:
```
ambiguous impli...Using the solution codes, I got `add(S(Z), S(S(Z))) // : S[S[Nat]] = S(S(Z))`. It's not right, isn't it?
To figure out this problem, I added a new given instance `given succZ: S[Z] = S(Z)`, and the compiler told me:
```
ambiguous implicit arguments of type App.this.Sum[App.this.S[App.this.Z.type],
App.this.S[App.this.S[App.this.Z.type]]
, App.this.Nat] found for parameter sum of method add in class App.
I found:
this.sumS[N, App.this.S[App.this.S[App.this.Z.type]], R](
this.sumZ[App.this.S[App.this.S[App.this.Z.type]]](
this.succ[App.this.S[App.this.Z.type]](
/* ambiguous: both given instance succZ in class App and given instance zero in class App match type App.this.S[App.this.Z.type] */
summon[App.this.S[App.this.Z.type]]
)
)
)
But both given instance succZ in class App and given instance zero in class App match type App.this.S[App.this.Z.type].mdoc
```
So the compiler regards `zero` and `succZ` the same.
Why does it believe `Z` is the same as `S[Z]`? And this leads to the wrong answer for `add(S(Z), S(S(Z)))`?
Thanks in advance.https://gitlab.epfl.ch/lamp/cs210/-/issues/100Constraint programming, Lisp, Streams2021-12-20T17:18:04ZZied MasmoudiConstraint programming, Lisp, StreamsHello,
In previous years exams, some exercises are about constraint programming "Formula", some about Lisp and others about Streams. Will we be tested on those 3 notions?Hello,
In previous years exams, some exercises are about constraint programming "Formula", some about Lisp and others about Streams. Will we be tested on those 3 notions?https://gitlab.epfl.ch/lamp/cs210/-/issues/99evalE2021-12-18T20:03:50ZLina BerrayanaevalE![FUNPROG](/uploads/0252ffe038fb00304ae9505babc21f6a/FUNPROG.png)
Hello !
In the case the expression is call f(f(v)) with function f(a) = a+1, the initial environment is {(v,1)} # v=1
the in NewEnv we'll have {(v,1), (a,1) #cause the la...![FUNPROG](/uploads/0252ffe038fb00304ae9505babc21f6a/FUNPROG.png)
Hello !
In the case the expression is call f(f(v)) with function f(a) = a+1, the initial environment is {(v,1)} # v=1
the in NewEnv we'll have {(v,1), (a,1) #cause the last arg a=v, (a,2)#then arg a=f(a)}
Wouldn't that cause a problem ?
Thank youhttps://gitlab.epfl.ch/lamp/cs210/-/issues/97Final Exam 20192021-12-20T23:59:27ZZied MasmoudiFinal Exam 2019Hello,
In exercise 1 of final exam of 2019, we don't need to reverse the obtained list at the end no? because with the cons we already get right order. x1 :: rec(xs, seen) gives x1 :: x2 :: rec(xxs, seen) for example right? and it will ...Hello,
In exercise 1 of final exam of 2019, we don't need to reverse the obtained list at the end no? because with the cons we already get right order. x1 :: rec(xs, seen) gives x1 :: x2 :: rec(xxs, seen) for example right? and it will be in the correct order![image](/uploads/2e6f9b6bd86cce448f98e563fe5500a5/image.png)https://gitlab.epfl.ch/lamp/cs210/-/issues/96Understanding exercise session 082021-12-21T16:07:15ZPeter Charbel Abdel MassihUnderstanding exercise session 08Hello, while playing around a little with the code of the exercise session 08, i found that add1 and add have different behaviors, Moreover I can't seem to wrap my head around how is the code running and which given instance is calling w...Hello, while playing around a little with the code of the exercise session 08, i found that add1 and add have different behaviors, Moreover I can't seem to wrap my head around how is the code running and which given instance is calling which, could someone please help me clarify the idea of this exercise in my head. ( Maybe clearly showing the different calls to functions will help me understand )
Here are the different behavior of the add1 and add methods :
![Screen_Shot_2021-12-16_at_3.33.45_PM](/uploads/42a319ab8175b9d337d1a057c3fd2669/Screen_Shot_2021-12-16_at_3.33.45_PM.png)https://gitlab.epfl.ch/lamp/cs210/-/issues/86streams lab − equality of sets − Finding Neighbors2021-11-24T09:30:41ZMarwan Azuzstreams lab − equality of sets − Finding NeighborsHello,
I am facing an issue about Scala's set equality on the [Finding Neighbors](https://gitlab.epfl.ch/lamp/cs210/-/blob/master/labs/lab-07.md#finding-neighbors) step. As said in this note from #79 (or from its definition), Sets are u...Hello,
I am facing an issue about Scala's set equality on the [Finding Neighbors](https://gitlab.epfl.ch/lamp/cs210/-/blob/master/labs/lab-07.md#finding-neighbors) step. As said in this note from #79 (or from its definition), Sets are unordered. Hence, the equality between two sets would be defined with their contents.
However, I faced a quite strange issue when implementing the test and I can not find by my own why it does not work, despite testing.
My test simply consisted of copy-pasting the given example.
```scala
test("my own test") {
new Level1:
assert( neighborsWithHistory(Block(Pos(1,1),Pos(1,1)), List(Move.Left,Move.Up)).toSet == Set(
(Block(Pos(1,2),Pos(1,3)), List(Right,Left,Move.Up)),
(Block(Pos(2,1),Pos(3,1)), List(Move.Down,Left,Move.Up))
))
}
```
But this test is marked as failed… :(
```
==> X streams.BloxorzSuite.my own test 0.071s munit.FailException: C:\…\cs210-streams\src\test\scala\streams\BloxorzSuite.scala:48 assertion failed
47: (Block(Pos(2,1),Pos(3,1)), List(Move.Down,Left,Move.Up))
48: ))
49: }
at munit.FunSuite.assert(FunSuite.scala:11)
at streams.BloxorzSuite$$anon$1.<init>(BloxorzSuite.scala:15)
at streams.BloxorzSuite.$init$$$anonfun$1(BloxorzSuite.scala:48)
```
Printing the two sets followed by the equality check gives me this (in the test itself which is not a pretty good practice):
```
streams.BloxorzSuite:
Set((Block(Pos(2,1),Pos(3,1)),List(Down, Left, Up)), (Block(Pos(1,2),Pos(1,3)),List(Right, Left, Up)))
Set((Block(Pos(1,2),Pos(1,3)),List(Right, Left, Up)), (Block(Pos(2,1),Pos(3,1)),List(Down, Left, Up)))
false
==> X streams.BloxorzSuite.my own test
```
And testing on a worksheet gives **true** ??
```
…
class Test extends SolutionChecker :
/* copy of level1 */
val level =
"""ooo-------
|oSoooo----
|ooooooooo-
|-ooooooooo
|-----ooToo
|------ooo-""".stripMargin
import Move.*
def lel = neighborsWithHistory(Block(Pos(1,1),Pos(1,1)), List(Move.Left,Move.Up)).toSet == Set(
(Block(Pos(1,2),Pos(1,3)), List(Right,Left,Move.Up)),
(Block(Pos(2,1),Pos(3,1)), List(Move.Down,Left,Move.Up))
)
val scala = new Test // : Test = repl.MdocSession$App$Test@7d3016c1
scala.lel // : Boolean = true
```
Using `import Move._` inside my test makes everything working back again. So, I ask myself this question: why? I would assume that Scala considers `Move.Right` and `Right` to be equal, no? It is the same object.https://gitlab.epfl.ch/lamp/cs210/-/issues/84Midterm 2017 ex32021-11-09T19:06:26ZZied MasmoudiMidterm 2017 ex3In midterm 2017, ex 3, why aren't the last lines all filled with X. In the exercise description we say: FixedChan[P, +R] so it's invariant in its argument parameter no? so we can't say which one is a supertype/subtype of which when comp...In midterm 2017, ex 3, why aren't the last lines all filled with X. In the exercise description we say: FixedChan[P, +R] so it's invariant in its argument parameter no? so we can't say which one is a supertype/subtype of which when comparing 2 FixedChan or a Chan and a FxedChan![image](/uploads/06f8dbe5d577f54c2039a6846ed7d2b4/image.png)